多域光网络的保护算法-资源利用率

摘要随着光网络的快速开展，有关保护算法的研究逐渐由单域网络转移到多域网络。多域光网络保护算法的研究涉及拓扑聚合、路由策略等课题，具有一定的复杂性。本文介绍了WDM光网络的根本概念，对相关生存性技术做了归纳总结，重点分析了共享分段保护技术，并且在已有的算法根底上提出了改良。最后通过仿真改良前和改良后的算法在网络中的表现，比拟了两者的性能差异。关键词：WDM光网络，多域，生存性，保护算法，共享分段保护ABSTRACTWiththerapiddevelopmentofopticalnetworks,researchontheprotectionofthealgorithmgraduallyshiftsfromsingle-domaintomulti-domain.Multi-domainopticalnetworkprotectionreferstosomecomplicatedtopicssuchastopologyaggregationandrouting.Inthispaper,thebasicconceptsabouttheWDMopticalnetworksisintroduced,asummaryofthesurvivalofthetechnologyisdone,thefocusoftheresearchisonthesegment-sharedprotection,andtheimprovementsbasedontheexistingalgorithmisputforward.Finally,throughthesimulationofthetwoalgorithmsinthenetwork'sperformance,wegetthedifference.Keywords:Opticalmeshnetworks,Multi-domains,Survivability,Segment-sharedprotection目录第1章引言[21]中的回归共享分段保护。局部文献中由于假设了多域网络的整体和局部信息的情况，实际局限在了单域网络的问题中。此文献中考虑的多域网络是指有大量中间域的网络，提出一种两步启发式算法。首先，多域网络进行拓扑聚合变成一个紧凑的域间网，可以得到一个初步的路由。然后，在各个域中分别得到详细的路由。聚合拓扑的使用可以保证可测量性的限制。第一步路由可以通过贪婪算法或动态规划算法得到。在提供的解决方案中，工作分段和保护分段的长度也是受到限制的，已经知道故障恢复时间是由故障发现时间和保护分段激活时间组成的。前者是由工作分段长度决定的而后者是由保护分段长度决定的。因此，工作分段和保护分段的长度限制将确保快速的恢复。下面简要说明文献[10]中的域间路由使用贪婪算法GROS(GreedyOverlappingShortsegmentsharedprotection)的路由过程。路由目标在于将新连接的工作路和保护路消耗的总带宽最小化，总带宽可以表示为公式3-1。(3-1)在域间网络(虚拟拓扑)中，可以等同于公式3-2。(3-2)在多域网络中，通路可能会比拟长。为了确保快速的恢复，设置工作分段和保护分段的门限值分别为LW和LB，即为分段长度限制。两步路由如下：域间步骤首先优化(1)，其中虚链路和域间链路被赋予代价和，并且将工作长度限制也考虑进去。事实上，此时的路由问题已经成为一个单域路由问题，任何OSSP的单域路由算法都可以使用，只要满足虚拟链路的代价和分段长度限制。下面简要说明GROS的流程。1〕找到用表示的源到目的最短工作路。2〕工作路被贪婪的分为分段，第一个分段从源节点开始。每一个分段的尾节点选择原那么是在分段长度限制LW下尽可能的取长一些。然而，如果不能找到这样的尾节点，那么指定离头节点最近的节点为尾节点。从尾节点朝头节点返回最小的跳数，直到找到一个节点度大于2的新节点，此节点是下一个分段的头节点。这个过程持续到到达目的节点。3〕对于每一个先前确定的工作分段，找到用表示的工作分段端节点之间的最短保护分段，保护分段的长度不能大于LB。域内步骤对每一个分段对，工作分段的虚链路先映射成为相应最小代价的域内路径。完整的工作分段得到以后，保护分段的虚链路也映射成为相应最小代价的域内路径。需要说明的是为了确保工作分段和保护分段是别离的，需要在映射保护分段的时候排除工作分段的节点。每次使用最短路算法的映射只是在一个域内，这样可以很好地满足可测量性要求。一个请求可能在域间路由的时候成功，但是在域内路由的时候由于带宽缺乏等或需要保证和工作分段别离等原因导致域内路由阻塞。为了防止这种情况，文中提出一种“Blocking-go-backoption〞的策略，即域间路由的迭代。该次路由只需要在域间路由之前将阻塞的虚链路去除，后续步骤和第一次一致。这样，就可以防止重复前面的阻塞。需要指出的是，虽然“Blocking-go-back〞降低了阻塞率，但是会花费更长的时间。分段共享保护算法LSSP研究问题描述假定WDM网状网的物理拓扑为G{,GL}(1r)，虚拟拓扑为Gv{,GL}(1r)，两个拓扑都由个域组成，其中，={GNr,INr,ILr,W}(1r),={GNr,VLr}(1r)，GL是连接不同域的网关节点的链路。考虑到网关节点之间的链路相对很少，可以配置成专用保护的模式，其保护不需要动态路由计算。一些重要的符号表示如下所示：GNr:：域r的网关节点。每一个网关节点都有一个路由表，其内容包含域r的物理拓扑信息以及整个多域网络的虚拟拓扑信息。INr：域r的内部节点。每个内部节点都与一个路由表，其内容只包含域r的物理拓扑信息。ILr和W：分别表示域r的内部链路和每个链路上的波长数目。既然内部链路比网关节点之间的链路多得多，其保护需要动态路由——共享保护。VLr：域r的虚拟链路。每个虚拟链路可以提前计算和确定，它包含一些物理链路并且表示了域r中两个网关节点之间的路由。这里，主要研究针对每个域中最多有一条链路失效那么多域网络中多链路失效的问题，也就是说，有Q个域的情况下，在同一时刻，最多有Q条链路失效。基于上述网络模型，动态路由分成两步：工作路路由和保护分段路由。工作路路由分成域内路由和域间路由。保护分段路由只需要域内路由即可。路由过程的流程如图3-3所示。可以看到，多域光网络中的路由问题主要集中在解决域间路由上。在LSSP中，将多域光网络中的域间路由问题分成三大步来完成。第一步是通过比拟源节点到所有网关节点的路径代价找到源网关节点。第二步是在通过拓扑聚合得到的虚拓扑中，通过比拟源网关节点到目的域的所有网关节点的路径代价找到目的网关节点。第三步那么为找出目的网关节点到目的节点最短路径。在域间路由完成之后，再通过最短路算法将域间路由中得到的用虚链路表示的路径映射成实际的物理路径。从LSSP的路由步骤中可以看到，在寻找源网关节点时，是通过源节点到网关节点的路由比拟得到的。而域间路由的关键也在于找到源网关节点，这样仅仅通过域内的信息并没有考虑整个网络拓扑信息的情况下得到的源域网关节点是否是最优的值得讨论。所以从这方面出发，我们在LSSP算法的根底上提出了一些改良。详细的算法分析见3.4。LSSP算法流程图算法详细描述详细介绍算法之前，先说明算法中使用的符号含义。：从源节点s到目的节点d的连接请求n：的工作路，可以是域内或域间。：在域r中从节点v1到节点v2的分段。如果s和d都在同一个域内，那么=。：在域r中与对应的保护分段。如果s和d都在同一个域中，那么=。：链路e上的自由波长数：链路e上的工作波长数。：链路e上的保护波长数。(ILr)：工作分段经过链路f并且保护分段经过链路e的工作分段集合。：集合中的元素个数。：链路e的代价，是由当前网络信息决定的。：虚链路e的代价。如果该虚链路可以成功映射成为物理链路，那么取值为1，否那么取值为0。下面详细介绍启发式过程。输入：={GNr,INr,ILr,W}(1r),={GNr,VLr}(1r)和输出：工作路和保护路；或者工作分段及其在各个域中对应的保护分段。第一步：如果，让，转入第二步；否那么转入第五步。第二步：通过公式(3-3),得到链路的链路代价，计算出域r内从v1到v2的最小链路代价和的工作路，如果找到，转入第三步；否那么返回空值。(3-3)第三步：通过公式(3-4)，得到计算保护分段时链路的代价。如果可以找到，转入第四步；否那么返回空值。表示新增共享资源值，其计算在共享保护的实现中详细说明。(3-4)第四步：如果，让，并且返回得到的解；否那么，记录下此分段并在域m选择下一个工作分段。如果所有的工作分段都选择完毕，那么返回解。否那么，让并返回第三步。第五步：在域r中，通过公式(3-3)得到的链路代价计算从源节点s到网关节点g的最小链路代价的工作分段。如果找到，那么转到第六步；否那么返回空值。第六步：通过公式(3-5)的得到的链路代价，可以在虚拓扑中计算出从源网关节点到目的网关节点的最小链路代价路径M。如果可以找到M,那么转到第七步；否那么返回空值。(3-5)第七步：通过公式(3-3)链路的代价可以得到域t中从网关节点k到目的节点d的最小链路代价的工作分段。如果可以找到，那么转到第八步；否那么返回空值。第八步：将虚路径M映射成实际的工作分段。将所有工作分段连接起来那么形成工作路。选择源节点和源网关节点，让，返回第三步。物理拓扑和虚拓扑在保护算法的研究中，网络拓扑的输入是重要的一个环节。拓扑文件格式一定程度上会影响算法执行的策略。由于是多域光网络的保护问题，拓扑分成物理拓扑和虚拓扑两种。在本文的算法实现中，将物理拓扑和虚拓扑放在一个拓扑文件中，简化了输入文件，但是对拓扑文件的格式做出了一些规定以满足读取拓扑信息的需要，输入拓扑文件格式如表3-1所示：拓扑文件格式链路ID源节点－目的节点域ID链路属性Link00－110(false)例如中表示链路0的源节点为0，目的节点为1，其所在域为域1，链路属性为0(false)表示是实际物理链路，为1(true)表示是域间链路或虚链路。链路属性为true的时候应该考虑到两种情况：一种是域间链路，域间链路是专用保护，但是增减自由波长数目的时候都应该考虑到，但是注意因为域间链路使用的是专用保护，那么不考虑共享波长数目的变化。另一种是虚链路，涉及到刷新波长数和刷新连接编号数的时候都不应该考虑。并且值得一提的是，工作路路由和保护路路由不包含这种虚链路。如果包含，那么说明路径映射的时候出现了问题。最短路算法实现中，会遍历所有节点。这样就存在两种情况来执行最短路算法。一种是虚拓扑中的所有节点，另一种是单域物理拓扑中的所有节点。可见，需要区分节点属性来实现这两种情况。为了得到节点的属性，可以利用域ID这一参数。如果链路是域间链路，那么设置域ID为0，如果读取到域ID的值为0就可以知道该链路的源节点和目的节点都是网关节点，这些就是虚拓扑里最短路算法中遍历的节点，其他的那么是物理拓扑里最短路算法中遍历的节点。编程实现中，通过上述拓扑文件格式，只需要知道整个拓扑链路的属性，就可以方便的得到虚拓扑和物理拓扑。例如，当需要虚拓扑的时候，遍历链路，只要链路属性为0(false),那么将其链路代价设置为无穷大，显然使用最短路算法找路时代价为无穷大的链路不起作用，从而到达提取虚拓扑的目的。同样的原理，只需将除开域间链路和虚链路的其他链路代价设为无穷大，就可以获得物理拓扑。上述方法简化了多域网络的拓扑文件的复杂性，提高了效率。连接的动态产生为了使仿真结果更接近实际情况，采用了动态产生连接请求的方式。已经知道，网络中的连接请求到达时刻服从泊松分布，持续时间服从负指数分布。下面附上产生泊松流，处理连接请求的伪码。/*产生泊松流、到达事件及离开事件的重要伪码*/begin/*变量初始化*/stream(6);//初始化随机产生函数的时间种子Simulation_Clock=0.0;//模拟时钟清0/*到达事件初始化：产生第一次到达事件及离开事件表，到达事件服从泊松分布*/First_Arrival_Interval=Exponential(1.0/Arrival_Rate_Lambda);Arrival_time=Simulation_Clock+First_Arrival_Interval;LeaveEvents.clear(); //离开事件表为空Stop_Alarm_On=FALSE; Leave_Event_Over=TRUE;/*主程序：调用定时程序以确定下次事件；调用相应的子程序对下次事件进行处理*///根据发生时间确定下次事件的类型 找出最近结束的事件停止时间stop_timeif((stop._time)<Arrival_time){//Cond1LeavebeforeArrivalNext_Event=LEAVING;Simulation_Clock=stop_time;}elseif(stop_time>Arrival_time){//Cond2ArrivalbeforeLeaveNext_Event=ARRIVING;Simulation_Clock=stop_time;}else{//cond3Arrival=Leave,Killthecomputer! Next_Event=LEAVING; Simulation_Clock=stop_time; }/*调用下次事件对应的子程序：到达或离开*///CallthesubroutineoftheNext_Eventswitch(Next_Event){caseARRIVING:Arriving_Event(); //调用到达事件处理模块break;caseLEAVING:Leaving_Event(); //调用离开事件处理模块Leave_Counter++;break;caseNOEVENT:break;}endwhileend到达事件处理子程序Arriving_Event()begin/*在处理当前到达事件前，产生下一次到达事件发生的时间间隔，进而计算下一次到达事件的发生时间*/Next_Arrival_Interval=Exponential(1.0/Arrival_Rate_Lambda);Arrival_time=Simulation_Clock+Next_Arrival_Interval;Choose_Demand(&src,&dst,&bandwidth);//确定到达事件的源、宿及带宽需求等。/*保护计算局部，在此不详细展开说明*/调用相应保护算法对业务连接请求进行工作路和备份路计算。Iffindarouteforthisdemandrequest /*成功找到路径，更新网络状态分配相应资源，产生离开事件*/Resource_Allocation();//分配资源Leave_Event_Over=FALSE;Service_Time=(double)exponential(1.0/Service_Rate_mu);leave_time=Simulation_Clock+Service_Time;构造一新的离开事件结构;endifend离开事件处理子程序Leaving_Event()beginRead_Leave_event();//得到当前离开事件 Release_Primary_Resource();//释放该工作通路所占用网络资源 Update_Backup_Resource(); //更新保护通路经过的链路上的预留资源end共享保护的实现在共享分段保护中，为了确保在单链路或单节点失效的情况下100%的保护，只有在工作分段是链路和节点别离时，其共享分段才可以共享带宽。图3-4给出了解释。情况(a)中，从v1到v2的工作分段请求带宽为d1,从v5到v6的请求带宽为d2，两个工作分段是链路和节点别离的。因此，它们的保护分段可以共享链路(v4,v3)上的带宽，这样，两个保护分段在这条链路上使用的带宽就是max{d1,d2}。情况(b)中，两个工作分段都经过节点v7,所以它们的保护分段必须使用别离的保护带宽，两个保护分段在链路(v4,v3)上使用的带宽就是d1+d2,显然大于情况(a)中的使用带宽。保护带宽可以共享(a)和不能共享(b)例如下面对共享保护实现的理论加以说明。保护带宽共享例如图3-5(a)表示了链路e上的带宽(波长数目)结构。显然，链路e上的可以共享的保护带宽是-。共享保护会存在两种情况：1〕可以共享的带宽小于等于连接请求带宽d，链路e上需要额外的新增共享资源，如图3-5(b)所示；2〕可以共享的带宽大于连接请求带款d，不需要额外的新增共享资源，那么，如图3-5(c)所示。可以得到公式3-6：(3-6)结合上述理论根底，我们可以得到计算保护分段时，确定全网链路的代价的方法。令E为全网链路集合，表示工作路经过链路g共享保护路经过链路l的所有业务带宽之和，表示链路e上用于共享保护的资源，WP为业务的工作路，d为业务带宽，为工作路上的链路集合,那么如果业务的工作路经过链路e1，而业务的保护路经过e2，那么e2上新增共享资源为(3-7)为了保护工作路任一链路那么链路e2上应至少新增的共享资源为(3-8)下面附上实现共享保护的重要伪代码。/*共享保护过程*/beginif当前链路类型为域间链路，那么应该采用专用保护//专用保护将工作路由压栈将保护路由压栈〔专用保护中，保护路由和工作路由相同〕endifif当前链路类型为域内链路，那么应该采用共享保护//共享保护调用保护权重分配函数，根据工作分段路由重新分配权重将工作路由经过的链路权重设为无穷大，使得工作分段和保护分段链路别离调用最短路算法计算与工作分段对应的保护分段endifend/*权重分配函数*/begin if工作路属性为共享路调用新增共享资源计算函数，计算每条链路上的新增共享资源，endifif当前链路属性为域间链路or虚链路权重设为无穷大elseif新增共享资源大于剩余资源权重设为无穷大else按照公式计算得出权重endifendifend/*新增共享资源计算函数*/beginif当前链路为域间链路or虚链路 跳出//防止将域间链路和虚链路参加新增共享波长数的计算else记录经过每条链路的工作路信息 endif 通过已经记录的每条链路上的工作路ID和保护路ID得到公式(3-8)中的ifendifif//假设每个连接请求一个波长出错 elseendifend基于LSSP的算法改良问题描述已经知道，LSSP中在源域中寻找出口网关节点时，是通过比拟源节点到所有源网关节点的路由找到最短路得到。但是，这样找到的源网关节点有可能不是最正确选择。如图3-6所示，连接请求A到P，假定当前所有域内物理链路的代价相等，即域内路由由跳数决定。在LSSP中，先由源节点A寻找到所有网关节点的最短路，得到出口网关节点G1，再由G1通过虚拓扑的域间路由得到目的网关节点G6，最后的路径为：A-G1-G4-C-G8-G6-P，该路径经过了两条域间链路。LSSP在寻找域内出口网关节点时存在的问题例如但是，实际网络情况是域间链路的代价会远大于域内链路，域间链路的选择一定程度上会决定路径的优劣。基于对整体拓扑详细情况了解的情况下，我们可以得到从源节点A到目的节点Q的最短路径为A-G1-K-G2-G6-P，只经过了一条域间链路，显然比先前通过LSSP找到的最短路径代价更小。可见，LSSP会存在找不到最优路的情形，本文将针对这一点加以改良，改良方法归结为动态地将源、宿节点参加虚拓扑。改良后的算法流程如图3-7所示。和前面介绍的LSSP算法的差异主要在寻找源网关节点方面。改良后的算法中，主要方案是将源节点和目的节点都参加虚拓扑中。当然二者参加虚拓扑之前需要做出一些预处理，即参加源、宿节点与网关节点之间的虚链路的前提是实际的物理路径路由成功，否那么就不添加相应的虚链路。将源、宿节点参加虚拓扑中，域间路由就直接在源节点和目的节点之间进行，这样就免去了通过源节点域内路由寻找源网关节点的步骤，一定程度上考虑了全局信息。改良的算法流程源、宿节点参加虚拓扑的实现将源节点参加虚拓扑，需要在路由之前更改源、宿节点到网关节点的链路属性，分别增加源、目节点到同域网关节点的虚链路，路由之后将图恢复成初始化的情况，以便后续的路径映射的实施。根据图3-6中的物理拓扑得到单纯提取虚拓扑和源节点参加虚拓扑的两种情形，如图3-8所示，节点A为连接请求的源节点。(a)改良前(b)改良后虚拓扑提取：改良前和改良后将源、宿节点参加虚拓扑后，可以有效找到使路径代价更小的源网关节点，这样会使找路更准确。以域1到域3的路由为例，其出口网关节点选择G2会优于G1，LSSP是单纯通过源节点到所有网关节点路径的比拟会得到出口网关节点G1，而采用改良后的LSSP算法那么可以选择到较为准确的出口网关节点G2。在第4章中将会对两种算法的性能进行编程仿真和详细的分析。值得一提的是，在编程实现中，存储链路信息的数据结构采用了C++中的map结构，对于将源、宿节点参加虚拓扑需要做出一些处理以满足编程环境中数据结构的要求，具体程序参见附录。仿真结果与分析仿真使用增长流量模型。在该模型中，连接是动态产生的，假设所有业务请求的到达速率服从均值为β的泊松分布，所建业务的持续时间服从均值为1/μ的指数分布，即全网总负载为β/μ爱尔兰(Erlang)，仿真时取μ=1。到达业务请求的源、宿节点在所有节点对之间随机选择，如果业务连接建立失败那么立即丢弃，即无等待队列。为了更精确地仿真网络真实情况，产生连接数需要到达106以上。连接请求是依次到达网络的，一旦分配资源，连接请求不能重配置，并且假定每个请求带宽就是一个波长。仿真用的网络拓扑如图3-6所示，网络包含三个不同的域。在单个域中，节点对之间是由双向光纤链路连通的。在两个不同的域之间，节点对是由一条双向工作路光纤和一条双向专用保护路光纤连接的。每条光纤链路设置成有128个波长，为了获得较好的性能和简化仿真过程，认为每个节点都有波长转换容量和光电光(O-E-O)波长变换能力。连接的动态产生，尤其需要注意的是资源的占用和资源的释放问题。资源的占用和释放都可以分成从工作分段和保护分段不同分成两类。资源占用中，工作分段每条链路的工作波长数应该增加，并且记录连接编号数；保护分段的所有链路通过计算新增共享资源值确定自己的共享波长数，并且记录连接编号数。资源释放中，工作分段只需要将每条链路的工作波长数减一，并且删除记录的当前应该释放的连接编号；保护分段资源的释放问题比拟复杂。在共享保护中，设计多条工作分段共享保护链路的问题，资源释放的时候不仅要考虑当前释放连接，更要考虑到这些链路保护的其他连接。本文中采用的方式是通过保护分段链路上的共享连接编号集来确定这些链路需要保护的工作分段，从工作分段出发，重新计算保护分段上所有链路的共享资源。保护分段的共享资源释放的代码见附录。我们将改良后的算法与改良前的分段保护算法LSSP(LocalSegment-SharedProtection)进行了比照研究，主要研究资源利用率(ResourceUtilizationRatio，RUR)。资源利用率定义为总的保护波长资源与总的工作波长资源的比值，资源利用率越小，说明保护预留资源越少。可以得到，资源利用率越高，后续业务请求可用的空闲资源就越多，阻塞率就会越低，网络性能越好。仿真结果如图4-1所示。X轴都是用Erlang表示的网络负载，Y轴分别为资源利用率和阻塞率。可以清楚的看到，在不同的网络负载下，改良后的算法RUR有所降低，即网络性能有所提高。改良后的算法将源、宿节点参加虚拓扑中，一定程度上减少了找路是对出口网关节点的依赖，相对于LSSP中依靠源节点到源域所有网关节点的路径比拟得到出口网关节点的方式，无论是准确性还是资源利用方面，改良后的算法性能都优于LSSP。资源利用率的比拟总结及展望在WDM光网络中，网络部件失效时可能遭受比传统网络更大的损失，比方一根光纤断裂将导致所有经过该光纤的光路都失效，而每条光路都能以Gb/ps的速率传输数据，这样的失效对网络中业务的影响是非常巨大的。因此，网络生存性问题对WDM光网络是一个非常重要的问题。本文研究了大量已有的多域光网络中动态连接下的保护算法，特别是共享分段保护算法，对其中一种算法进行了详细的分析和研究，在此根底上提出了改良，并通过编程仿真对算法性能进行了验证和评价。本章5.1节是对全文研究工作的归纳总结，5.2节提出了有待解决的问题和改良的方向。研究工作总结通过前面的工作，了解了WDM光网络的特点，结构以及光交换技术等光网络根本概念，对网络生存性技术有了较为深刻的认识，进而拓展到多域光网络的保护算法研究上。本文在以下几个方面做了相关研究。连接的动态产生模型动态产生连接请求，按照连接到达时刻服从泊松分布，持续时间服从复指数分布构建数学模型。通过伪时钟控制连接的到达和结束，从而到达仿真网络连接情况的目的。拓扑聚合拓扑聚合是多域网络中域间传递拓扑信息必须的技术，多域光网络的保护算法的前序步骤也是拓扑聚合。拓扑聚合后，在保证准确的前提下，网关节点之间传递少量的交互信息来实现域间路由等功能，提高了网络性能。共享保护相较于专用保护，共享保护可以大大提高资源利用率。保护算法一般都是基于共享保护进行研究，共享保护的原理见3.3.5小节。基于LSSP算法的改良在对已经提出的LSSP的重现过程中，发现在寻找源域的出口网关节点时可以改良。提出的改良方法是，将源、宿节点参加拓扑聚合后的虚拓扑中，这样就将寻找出口网关节点这一环节省略掉，从而提高寻找最短路的准确性。展望本文提出的改良的算法仍然存在可以提升的空间。在源、宿节点参加虚拓扑后，计算源、宿之间的路由时只是简单的将可以映射的虚拟链路权重设为1，这样和真实情况存在出入，可以在虚拓扑权重设置上做出改良，例如结合网关节点预先存储的信息估算虚链路的权重。所以，该算法有待进一步完善。通过对多域光网络的保护算法有了比拟深入的研究，发现该研究方向还存在很多可以突破和改良的地方，现列举如下：1〕目前的研究大多集中于给定网络的失效情况，比方LSSP中限制了一个域最多有一个故障。然而，如果网络中的故障数不确定，以前提出的生存性机制或保护算法就不再适用。因此，需要普遍适用的保护算法。2〕现有的保护算法多是基于“两步路由〞的框架，即先域间路由再域内路由。可以尝试在整体框架上作一些改良。3〕拓扑聚合方面的改良。在本文中，拓扑聚合只是简单地采用了全连通聚合，但是这种聚合方式只适用于规模较小的网络，如果网络规模较大，那么拓扑聚合的代价相当大，所以应该考虑其他聚合方式来提高网络性能。4〕参加限制的保护算法。本文的实现的分段保护算法中，并没有考虑参加跳数限制等限制因素，这和实际网络情况有差异，可以进一步改良。5〕区分业务可靠度。本文实现的保护算法没有区分业务，不同业务对可靠度的要求通常都不一样，要使得工作路和保护路的可靠度满足连接请求的可靠度要求。6〕本文实现的保护算法中，域间的链路是使用的专用保护，可以将其改良为共享保护。参考文献徐宁榕,周春燕,WDM技术与应用.北京:人民邮电出版社,2002罗洪斌,抗毁WDM网状网中的保护算法研究:[博士学位论文].成都:电子科技大学,2006纪越峰,王宏祥,光突发交换网络,北京:北京邮电大学出版社,2005GregBermstein,BalaRajagopalan,DebanjanSaha,黄蔚等译,智能光网络－体系结构、协议和标准,北京:人民邮电出版社,2007崔延军,李健,张志珊,顾畹仪.智能光网络的多域生存性研究.量子电子学报,2006,Vol.23,No.3:420~423S.Ramamurthy,LaxmanSahasrabuddhe.SurvivableWDMMeshNetworks.Journaloflightwavetechnology,2003,Vol.21,No.4:870~883刘爱波,陆月明,纪越峰.智能光网络路由及其关键技术分析.光通信技术,2004,第8期:29~31BaruchAwerbuch,YiDu,etal.RoutingThroughNetworkswithHierarchicalTopologyAggregation.JournalofHigh-SpeedNetworks,1998,Vol.7,No.1:57~73SuleymanUludag,King-ShanLui,KlaraNahrstedt,GregBrewster.ComparativeAnalysisofTopologyAggregationTechniquesandApproachesfortheScalabilityofQoSRouting,2005.雷蕾,郭林,纪越峰.一种应用于不对称网络中的生成树拓扑抽象算法.电子与信息学报,2006,Vol.28,No.10:1917~1920D.L.Truong,B.Thiongane.Dynamicroutingforsharedpathprotectioninmulti-domainopticalmeshnetworks.Journalofopticalnetworking,2006,Vol.5,No.1:58~74LeiGuo.LSSP:Anovellocalsegment-sharedprotectionformulti-domainopticalmeshnetworks.ComputerCommunications,2007,30(2007)1794-1801D.L.Truong,B.Jaumard.OverlappedSegmentSharedProtectioninMulti-domainNetworks.Proc.ofSPIE,2006,Vol.635463541K-1Dieu-LinhTruong,BrigitteJaumard.UsingTopologyAggregationforEfficientSharedSegmentProtectionSolutionsinMulti-DomainNetworks.IEEEJournalonselectedareasincommunications,2007,Vol.25,No.9:96~107S.RamamurtyandB.Mukherjee,SurvivableWDMmeshnetworks,partI-protection,1999.P.-H.Ho,J.Tapolcai,andT.Clinkler.Segmentsharedprotectioninmeshcommunicationsnetworkswithbandwidthguaranteedtunnels.IEEE/ACMtransactionsonnetworking,2004,Vol.12,No.6:1105~1118G.Ranjith,G.P.Krishna,andC.S.R.Murthy.Adistributedprimary-segmentedbackupschemefordependablereal-timecommunicationinmulti-hopnetworks.ProceedingsoftheInternationalParallelandDistributedProcessingSymposium,2002--.SparecapacityallocationforWDMmeshnetworkswithpartialwavelengthconversioncapacity,2003.P.-H.HoandH.T.Mouftah,Aframeworkforservice-guaranteedsharedprotectioninWDMmeshnetworks.IEEECommunicationsMagazine,2002,02:97~103D.Xu,C.Qiao,andY.Xiong,Protectionwithmulti-segments(PROMISE)innetworkswithsharedrisklinkgroups(SRLG).IEEE/ACMTransactionsonNetworking(TON),2002J.Cao,L.Guo,H.Yu,andL.Li,AnovelrecursivesharedsegmentprotectionalgorithminsurvivableWDMnetworks.JournalofNetworkandComputerApplications,2007,Vol.30,No.2:677~694致谢本文无论是选题还是具体的研究工作，以至于论文的撰写都得到我的指导老师虞红芳副教授无微不至的关心和悉心指导。您严谨的治学态度、渊博的知识、朴实的生活作风，令我敬佩万分！值此论文完成之际，向您献上我诚挚的敬意和深深的感谢！由衷的感谢所有关心我的老师、同学和朋友，尤其是章小宁博士、董拥拥师兄和缪金明同学，正是通过和你们的交流、讨论和你们的帮助，我才能克服种种困难，顺利地完成课题，我为能够得到你们的帮助而深表感谢！附录附录一工作路路由过程〔改良后〕核心代码boolCallData::Connect_Call(CGraph&graph,VertexIDsourceid,VertexIDsinkid)//找工作路{UINTs1,s2,n;UINTtz=0;boola;list<Edge*>::iteratoreit;list<Edge*>::iteratorwe_it;list<Vertex*>::iteratorwv_it;map<pair<VertexID,VertexID>,Path>::iteratorvp_it;Pathtemp_path;ofstreamout_file;out_file.open("out.txt",ofstream::app);s1=graph.Vertex_vector[sourceid].GetDomain_ID();s2=graph.Vertex_vector[sinkid].GetDomain_ID(); if(s1==s2)//源节点和目的节点在同一个域中 { graph.GetPgraph();//得到单域的物理拓扑a=graph.ShortestPath(sourceid,sinkid,temp_path,s1);//域内节点之间最短路算法if(a==false) {returnfalse; }WP.push_back(temp_path);//将工作路放入对应的业务数据结构中temp_path.ClearPathInfo(); } else//源、宿节点不在同一个域中 {graph.GetVgraph(sourceid,sinkid);//得到多域的虚拟拓扑a=graph.ShortestPath(sourceid,sinkid,graph.gpath,0);//域间节点之间最短路算法if(a==false) {returnfalse; }EraseNewEdge(graph);//将参加虚拓扑的源节点和目的节点删除graph.ChangeNode_prop(sourceid,sinkid);for(eit=graph.gpath.EdgeList.begin();eit!=graph.gpath.EdgeList.end();eit++) { if((**eit).GetDomain_id()==0) {//域的链路即为域间网关节点之间的链路，保护为专用保护，直接将节点和链路放入路径信息中temp_path.ExpendVertex(&graph.Vertex_vector[(**eit).GetSource_ID()]);temp_path.ExpendEdge(*eit);temp_path.ExpendVertex(&graph.Vertex_vector[(**eit).GetSink_ID()]);WP.push_back(temp_path);temp_path.ClearPathInfo();continue; }else {//链路需要路径映射graph.GetPgraph();//得到单域的物理拓扑n=graph.path_map((**eit).GetSource_ID(),(**eit).GetSink_ID());//将虚链路映射为实际链路if(n==0) {returnfalse; }if(WP.empty()!=true) {Joint_path(graph.tpath);//将同一域的分段连接起来 }else {WP.push_back(graph.tpath); }WP.push_back(graph.tpath); } }graph.gpath.ClearPathInfo();//去除暂存路径信息graph.tpath.ClearPathInfo(); }returntrue;}附录二共享保护过程核心代码boolCGraph::SharedProtectProcess(CallData&call_data){VertexIDsourceid,sinkid;RouteWorkRoute,ProtectRoute,temp;DemandIDDemandId;DomainIDdomainid;DemandId=call_data.GetDemandId();UINTi,tz,b;Pathtemp_path,path1,path2;boola;list<Vertex*>::iteratorvit;ofstreamfileout;fileout.open("out.txt",ofstream::app);tz=static_cast<UINT>(call_data.WP.size());for(i=0;i<tz;i++) { path1.ClearPathInfo();path1=call_data.WP[i];Edge*ef_it;ef_it=path1.EdgeList.front();if((*ef_it).GetL_type()==1) {//路径中链路属性为true的链路使用专用保护path2=path1;PathToRoute(path1,WorkRoute);WorkRoute.SetOwnerDemandId(DemandId);//设置连接编号WorkRoute.SetPathType(Work_Path);//设置路径属性为工作路AllocateResource(WorkRoute,DemandId);//工作路经过的链路记录当前连接编号PathToRoute(path2,ProtectRoute);ProtectRoute.SetOwnerDemandId(DemandId);ProtectRoute.SetPathType(Dedicated_Path);//设置路径属性为专用保护路AllocateResource(ProtectRoute,DemandId);//专用保护路经过的链路记录当前连接编号call_data.work_route.push_back(WorkRoute);//存储工作路分段call_data.backup_route.push_back(ProtectRoute);//存储保护路分段WorkRoute.ClearRouteInfo();ProtectRoute.ClearRouteInfo();continue; }PathToRoute(path1,WorkRoute);WorkRoute.SetOwnerDemandId(DemandId);WorkRoute.SetPathType(Work_Path);AllocateResource(WorkRoute,DemandId);b=AssignWeight(Shared_Path,WorkRoute);//通过计算每条链路的新增共享资源值设置权重if(b==0) {returnfalse; }ForbiddenPath(path1);//为了是保护路和工作路别离，将工作路经过的链路屏蔽vit=path1.VertexList.begin();domainid=(**vit).GetDomain_ID();sourceid=(*path1.VertexList.front()).GetVertex_ID();sinkid=(*path1.VertexList.back()).GetVertex_ID();a=ShortestPath(sourceid,sinkid,temp_path,domainid);//通过最短路算法找到保护路分段if(a==false) {returnfalse; }else {path2.ClearPathInfo();path2=temp_path;PathToRoute(path2,ProtectRoute);ProtectRoute.SetOwnerDemandId(DemandId);ProtectRoute.SetPathType(Shared_Path); AllocateResource(ProtectRoute,DemandId);call_data.work_route.push_back(WorkRoute);call_data.backup_route.push_back(ProtectRoute); }WorkRoute.ClearRouteInfo();ProtectRoute.ClearRouteInfo(); }returntrue;附录三共享资源释放过程核心代码//呼叫结束Current_timer=LeastStopCallIT->GetStopTime();DemandIDdemandid;demandid=LeastStopCallIT->GetDemandId();cout<<"连接"<<demandid<<"*"<<LeastStopCallIT->GetSourceNode()<<""<<LeastStopCallIT->GetDestNode()<<"结束，释放资源"<<endl;wr_it=LeastStopCallIT->work_route.begin();//释放工作路资源for(;wr_it!=LeastStopCallIT->work_route.end();wr_it++){for(we_it=(*wr_it).LinkList.begin();we_it!=(*wr_it).LinkList.end();we_it++) {(**we_it).WorkDemandId.erase(find((**we_it).WorkDemandId.begin(),(**we_it).WorkDemandId.end(),demandid)); (**we_it).SetfreeWave_Num(graph1.Getwave_Num()); } }UINTcnt,tcnt;list<Edge*>::iteratorbe_it;list<Edge*>::iteratoreit;list<vector<UINT>>::iteratorListOfVectorIT;list<DemandID>::iteratorDemandIT;list<DemandID>::iteratorWD_it;vector<Route>cun_route;UINTCanntShare=0;UINTMaxCanntShare=0;//释放保护路资源for(cnt=0;cnt<static_cast<UINT>(LeastStopCallIT->backup_route.size());cnt++){ for(be_it=LeastStopCallIT->backup_route[cnt].LinkList.begin();be_it!=LeastStopCallIT->backup_route[cnt].LinkList.end();be_it++) {if((**be_it).GetL_type()==1) {continue; }else { (**be_it).SharedDemandId.erase(find((**be_it).SharedDemandId.begin(),(**be_it).SharedDemandId.end(),demandid)); }MaxCanntShare=0;//同时保护sharedDemandID中的连接，Max应该最大化for(CallIT=m_cCall.begin();CallIT!=m_cCall.end();CallIT++) {WD_it=find((*be_it)->SharedDemandId.begin(),(*be_it)->SharedDemandId.end(),CallIT->GetDemandId());if(WD_it!=(*be_it)->SharedDemandId.end()) {cun_route=CallIT->work_route;//存储当前链路保护的工作路由for(tcnt=0;tcnt<static_cast<UINT>(cun_route.size());tcnt++) {for(eit=cun_route[tcnt].LinkList.begin();eit!=cun_route[tcnt].LinkList.end();eit++) {cun_route[tcnt].ListOfVector.clear();if((**eit).GetL_type()==true) {continue; }UINTDemandNum=Counter+1;vector<DemandID>temp_vector(DemandNum,0);for(DemandIT=(*eit)->WorkDemandId.begin();DemandIT!=(*eit)->WorkDemandId.end();DemandIT++) {temp_vector[*DemandIT]=1; }cun_route[tcnt].ListOfVector.push_back(temp_vector); }for(ListOfVectorIT=cun_route[tcnt].ListOfVector.begin();ListOfVectorIT!=cun_route[tcnt].ListOfVector.end();ListOfVectorIT++) {CanntShare=0;for(DemandIT=(*be_it)->SharedDemandId.begin();DemandIT!=(*be_it)->SharedDemandId.end();DemandIT++) {CanntShare+=(*ListOfVectorIT)[*DemandIT]; }if(MaxCanntShare<CanntShare) {MaxCanntShare=CanntShare; } } } } }if((*be_it)->GetSharedWaveNum()>MaxCanntShare) { (*be_it)->SetSharedWaveNum(MaxCanntShare); (*be_it)->SetfreeWave_Num(64); } }}m_cCall.erase(LeastStopCallIT);外文资料原文LSSP:Anovellocalsegment-sharedprotectionformulti-domainopticalmeshnetworksLeiGuoAbstract—Thispaperinvestigatesthesurvivabilityinmulti-domainopticalmeshnetworksandpresentsanewmodelofmultiplefailuresthatisdefinedthatthereisonefailedlinkineachsingle-domainandaremultiplefailedlinksinthewholemulti-domains.SincetheconventionalExtended-Path-SharedProtection(EPSP)approachcannotprovide100%protectionabilityforthismodel,weproposeanovelapproachcalledLocalSegment-SharedProtection(LSSP)toprovideefficientsurvivabilityforthismodel.Inourapproach,LSSPfirstcomputesoneinter-domainprimarypathforeachconnectionrequestandfollowstocomputeoneintra-domainlink-disjointlocalsegment-backuppathforeachprimary-segmentpathineachsingle-domain,respectively,wherethebackupresourcescanbesharedbydifferentsegment-backuppathsifthecorrespondingprimary-segmentpathsarelink-disjoint.ComparedwiththeconventionalEPSP,althoughLSSPincreasesmoderatebackupresourcesconsumption,itnotonlycanprovide100%protectionabilityformultiplefailuresbutalsocanperformmuchfasterrecoverytimeandeasiersurvivableoperationandmanagement.Thesimulationresultsareshowntobepromising.1.IntroductionSurvivabilityhasbeenanimportantissueinWDMopticalnetworksandalsohasbeenstudiedformanyyears[1–5].Sincethesingle-fiber-linkfailurescenarioisdominantinWDMopticalnetworks,previousmanyworkshavefocusedtheprotectionforsingle-linkfailureandalsoproposedthecorrespondingsurvivableapproaches,inwhichthePath-SharedProtection(PSP)iseasierconfiguredandalsohasbetterresourceutilizationthanotherapproaches[4,5].InPSP,eachconnectionrequestwillbeassignedtooneprimarypathandonelink-disjointbackuppathfromthesourcenodetodestinationnode,andtwobackuppathscansharethebackupresourcesifthecorrespondingprimarypathsarelink-disjoint.AlthoughPSPcanprovidecompleteprotectionabilityforsingle-linkfailureandperformefficientend-to-endrouting,itisonlysuitableforsingle-domainnetworkinwhicheachnetworknodeneedstoviewtheglobenetworkinformation[6],e.g.,physicaltopology,bandwidthallocation,etc.Inreal-world,howeveranopticalWDMnetworkcontainsmulti-domainsbecausedifferentcarriersorserviceprovidersmaywanttomanagetheirownpartsofthenetwork[7–9].Anotherreasonisthatdifferentpartsofthetransportnetworkmayusedifferenttechnologies.Inmulti-domainnetworks,eachsingle-domainhastwokindsofnodes,whichareinteriornodeandgatewaynode.Eachinteriornodeonlycanviewthelocalnetworkinformationofphysicaltopologyinitsownsingle-domain,andthegatewaynodecanviewboththelocalnetworkinformationofphysicaltopologyandtheglobenetworkinformationofvictualtopology.Therefore,lackofglobenetworkinformationtheconventionalPSPneedstobemodifiedtoprovideefficientinter-domainsurvivableroutinginmulti-domainnetworks.In[6],theauthorsproposedanExtended-PSP(EPSP)approachthatcontainstowstepstoachieveinter-domainsurvivablerouting.Inthefirststep,aroughroutingsolutionissketchedinthevirtualnetworkthatisthetopologyaggregationofthemulti-domainnetwork.Acompleteroutingisthendeterminedbysolvingroutingproblemswithineachoriginalsingle-domainnetwork.Finally,anend-to-endinter-domainroutingpairwithoneprimarypathandonelink-disjointbackuppathcanbeestablishedfromthesourcenodetodestinationnode.ItisobviousthatEPSPcanprovidecompleteprotectionforthesingle-linkfailureandalsohasthesameefficientresourcesutilizationwithPSP.However,EPSPisasimpleextendedapproachfromthesingle-domaintomulti-domains,sothatitmaynotbesuitableforsurvivableroutinginreal-worldmulti-domainnetworks.Inpracticalmulti-domainnetworks,eachsingle-domainhasthecarrierorserviceproviderwhomaywanttomanageitsownpartsofthenetwork.Therefore,eachsingle-domaincanberegardedasanindependentnetworkthathasitsownlocalrulesofoperationandmanagementtoprovideservices.TheindependentlocalrulesofoperationandmanagementmayleadtosomeproblemsthatcannotbesolvedbyEPSP.ForexampleinFig.1,theblacknodesarethegatewaynodesthatcanviewboththelocalnetworkinformationofphysicaltopologyinitsownsingle-domainshowninFig.1(a)andtheglobenetworkinformationofvirtualtopologyshowninFig.1(b),andothernodesaretheinteriornodesthatonlycanviewthelocalnetworkinformationofphysicaltopologyinitsownsingle-domainshowninFig.1(a).InFig.1(c),weassumethereisaconnectionrequestestablishedbyEPSPfromsourcenodeAindomain1todestinationnodeKindomain3.Duetoindependentlocalrulesindifferentdomains,thefirstproblemisthattheremaybeexistonefailedlinkineachsingle-domainatatimepoint.Forexample,ifthefailedlinkA-G1isindomain1,thefailedlinkG4-Eisindomain2,andthefailedlinkJ-Kisindomain3,thisconnectionrequestwithaprimarypathA-G1-G4-E-G5-G6-KandabackuppathA-B-G2-G7-J-KprovidedbyEPSPwillbeblockedsincetheprimarypathandbackuppatharebothunavailable.ThesecondproblemisthattherecoverytimeofEPSPislongthatmaynotsatisfytherequirementofeachsingle-domain.Forexample,ifdomain3requires3msrecoverytimeconstraintsandhowevertherecoverytimeofEPSPfromsourcenodeAtodestinationnodeKis5ms,thedestinationnodeKindomain3willconsiderthattherecoveryprocedurefailsandthisconnectionrequestwillbeblocked.Thethirdproblemisthattheinter-domainbackupsmayrequiremuchcomplicatedoperationandmanagementsincetheinter-domainbackuppathmaytraversemultipledomainsandneedtoconfiguremanyinter-domainsignals,messagesandgatewaysnodes.Inordertoovercometheaboveproblems,weproposeanovelLocalSegment-SharedProtection(LSSP)approach.InLSSP,eachinter-domainprimarypathcanbedividedtomultiplesegment-primarypathsaccordingtodifferentdomains,andeachsegment-primarypathcanbeassignedtooneintra-domainlink-disjointsegment-backuppath.InLSSP,twosegment-backuppathsinthesamedomaincansharethebackupresourcesifthecorrespon