基于软管模型光虚拟专用网的分层路由及时延优化算法研究

南京邮电大学硕士学位论文基于软管模型光虚拟专用网的分层路由及时延优化算法研究姓名：钱炎琛申请学位级别：硕士专业：光学工程指导教师：刘逢清2011-03-01南京邮电大学硕士研究生学位论文摘要I摘要光虚拟专用网，是最具智能光网络特色的业务。这一业务的开展不仅能为运营商减少网络建设和运营成本，而且能使客户具有控制和管理所在专用网相关资源的能力，就像拥有自己的光网络一样。光虚拟专用网为用户在公用网络上提供了安全可靠的服务，而为了保证服务质量，必须在链路上预留足够的带宽资源。如何寻找合适的路径使链路总预留带宽最小并且支持QoS，成为光虚拟专用网络设计领域的热点。本文主要研究了软管业务模型下构建光虚拟专用网的路由问题，其特点在于仅对节点流入流出业务总流量进行限制，而任意节点对之间业务不确定。针对总预留带宽最小化及总平均时延最小化的优化目标，本文提出了一种较为少见的分层式路由算法。算法首先在不考虑实际物理网络的“上层”虚拟专用网用户间构建满足优化目标的虚拟逻辑拓扑，然后依据不同优化目标将虚拟逻辑拓扑映射至实际物理网络获得最优化网络拓扑。为了协调总预留带宽及总平均时延这两个优化目标，本文定义了用户倾向参数来进行区分，即依据用户实际要求，来选择优化目标，构建优化网络结构，使网络较具灵活性。仿真结果表明，当用户选择优化总平均时延时，其总平均时延较仅优化总预留带宽时减少近30%。而无论用户选择任一优化目标，通过本文算法所需的总预留带宽及总平均时延均少于原始对偶算法及典型的深度优先算法。最后，本文针对实际组网中物理参数的影响，简单探讨了在光虚拟专用网优化设计中应考虑链路损耗优化问题，在本文算法基础上进行了简单仿真，证明想法的可行性。关键词：光虚拟专用网、软管模型、分层路由、总预留带宽、总平均时延南京邮电大学硕士研究生学位论文ABSTRACTIIABSTRACTOpticalvirtualprivatenetworks(OVPNs)isoneofthemostimportantservicesinintelligentopticalnetworks.Itnotonlyallowsoperatorstoreducetheircost,butalsoenablescustomerstocontrolandmanagesomeresourcesoftheprivatenetwork.SecurityandstabilityareprovidedbyOVPNforcustomersoverasharednetwork.Bandwidthinalinkhastobereservedtoguaranteethequalityofservice(QoS).Therefore,howtofindaproperpathwithaleasttotalreservedbandwidthandmeetingthedemandofQoShasbecomeahotpotwhendesigningOVPN.ThispapermainlystudiestheroutingproblemofOVPNinhosemodel.Hosemodelspecifiesupperboundsforboththeingressandegressbandwidthofanendpoint.Tominimizethetotalreservedbandwidthandtotalaveragedelay,thispaperproposedanovelhierarchicalroutingalgorithm.Firstly,itconstructsalogicaltopologyamongVPNendpointswithoutconsideringitsunderlyingphysicaltopology.Secondly,itmapsthelogicaltopologyintothephysicalnetworkintermsofdifferentoptimalaims.Tobalancetheoptimaltargetsbetweenminimumtotalreservedbandwidthandminimumtotalaveragedelay,acustomer-inclinedparameterisintroduced.Itenablescustomerstochoosetheoptimaltopologyflexiblyaccordingtotheirownrequirements.Thefollowingconclusionscanbederivedfromnumericalresults:whencustomerschoosetooptimizethetotalaveragedelay,thetotalaveragedelaywillbereducedbyabout30%comparingwithoptimizationofthetotalreservedbandwidth;Moreover,whenchoosinganyofthetwooptimaltargets,italwaysrequireslesstotalreservedbandwidththanboththeprimal-dualalgorithmandthedepth-firstspanningtreealgorithm.Atlast,consideringtheinfluenceofphysicalparametersinnetworkdeployment,thispaperoptimizesthelinkloss,andsomenumericalresultsarederivedtodemonstratethefeasibilityoftheidea.Keywords:opticalvirtualprivatenetwork,hosemodel,hierarchicalrouting,totalreservedbandwidth,totalaveragedelay南京邮电大学硕士研究生学位论文缩略语III缩略语ADMAddDropMultiplexer分插复用器ASONAutomaticallySwitchedOpticalNetwork自动交换光网络ATMAsynchronousTransferMode异步传输模式BERBitErrorRate误码率CECommunicationEdge终端设备DFSDepthFirstSearch深度优先搜索DXCDigitalCrossConnect数字交叉连接设备IETFTheInternetEngineeringTaskForce互联网工程任务组ILPIntegerLinearprogramming整型线性规划IPInternetProtocol网络之间互连的协议ITU-TInternationalTelecommunicationsUnion国际电信联盟LPLinearprogramming线性规划LTDLogicalTopologyDesigning逻辑拓扑设计MPLSMultiprotocolLabelSwitching多协议标签交换ONEOpticalNetworkEquipment光网络设备OSIOpenSystemInterconnection开放系统互连OTNOpticalTransportNetwork光传送网OVPNOpticalVirtualPrivateNetwork光虚拟专用网PEProviderEdge提供商网络边缘设备QoSQualityofService服务质量RWARoutingWavelengthAssignment路由波长分配SDHSynchronousDigitalHierarchy同步数字体系SLAServiceLevelAgreement服务等级协议SONETSynchronousOpticalNetwork同步光纤网络WDMWavelengthDivisionMultiplexing波分复用VPNVirtualPrivateNetwork虚拟专用网络南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。南京邮电大学学位论文使用授权声明南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。研究生签名：_____________日期：____________研究生签名：____________导师签名：____________日期：_____________南京邮电大学硕士研究生学位论文第一章绪论1第一章绪论随着互联网的迅速发展，网络经济腾飞，网络活动日愈频繁，各企业、机构及个人对网络的需求急速增长。网络终端用户于是面临两种选择：一是通信解决方案的选择，另一则是服务运营商的选择。终端用户既不想背负建设专用网络的沉重负担，又想要能根据通信需求而灵活改变的通信方式。这样的用户需求给服务提供商提供了重大的商机。VPN（VirtualPrivateNetwork，虚拟专用网）技术应运而生，其定义为：使用共享网络的一系列用户点（site）之间的通信[1]。同一专用网中的多个端点可以通过公用网络进行通信。与传统意义上使用专用设备的专用网相比，VPN没有相应的物理拓扑，其网络是构架在公用网之上的，只有一组预先定义的拥有独立地址、拓扑及路由方式的实体可以接入多个互相通信的用户点（固定/移动）的集合。VPN特点在于多个私有的地理上分散的企业网络能连接在一个或多个业务提供商的网络上，共享服务提供商的资源，并且从使用共享资源的其他用户的观点来看网络能透明的承载信息流。OVPN（OpticalVirtualPrivateNetwork，光虚拟专用网）是一种新兴的虚拟专用网业务，也称L1VPN业务，是VPN服务向光层的延伸，其试图将第二、三层虚拟专用网的控制管理技术应用至第一层网络即光传送网中，为用户提供光传送层上的高带宽通道，在该通道上能支持不同的传输技术，因此可以组建基于不同传输技术的OVPN网络，如基于IP、ATM（AsynchronousTransferMode，异步传输模式）或者SDH（SynchronousDigitalHierarchy，同步数字体系）的OVPN网络。1.1研究背景及研究意义从光纤通信技术本身的发展来看，光网络是当前最活跃的领域[3]。光网络的规划与设计，无论对网络整体性能还是对运营商来说，都具有很重要的意义。良好的网络规划和设计不但可以节约大量的投资，也能保证光网络的服务质量，促进网络的发展；不但能充分利用网络资源，实现投资快速收益，而且能够及时满足社会的需要，促进社会的发展。OVPN服务作为自动交换光网络（ASON）[1][2]中极具吸引力的新兴业务，对OVPN网络的规划设计进行研究对于用户、服务提供商和社会都有重要的意义。光虚拟专用网特点为：1）提供受限连接，即只有同一OVPN网络的用户之间才能建立连接；2）为每个OVPN提供独立的控制和管理能力，这些功能可通过该OVPN提供给客户，使得客户具有控制和管理所在OVPN相关资源的能力，就像拥有自己的光网络一样。它的出南京邮电大学硕士研究生学位论文第一章绪论2现主要是由智能光网络[3]的自动交换、快速业务配置和智能业务管理等特性所带来的。ITU-T提出的自动交换网络（ASON）就是这样一种智能光网络解决方案，它在光传送