面向业务的GMPLS网络动态生存性算法

朱国晖，史浩山

(1．西北工业大学电子信息学院，陕西西安710072;2．西安邮电学院 信 息与通信学院，陕西西安710061)

通用MPLS(GMPLS)是MPLS向光网络扩展的必然产物，它为了适应对智能光网络进行动态控制和传送信令的要求而对传统的MPLS进行了扩展、更新．在智能光网络中，基于GMPLS协议完成是实现光网络节点控制平面的主要途径，光网络节点通过GMPLS协议可完成信令、路由、链路管理等功能，真正实现了光传输网与业务交换网的集成，为发展新业务创造了良好的条件．

对于网络的流量工程问题，人们提出了多种解决方法，但较传统的解决方案相比，GMPLS实施流量工程具有更多的优势．GMPLS流量工程的问题最终可以归结为数据流传输的路径确定问题，即显式路径的确立问题，所以研究流量工程动态路由算法的约束条件和目标函数，对于动态实现基于MPLS的流量工程具有特别重要的意义［1-2］．

1 基于约束的路由选择算法

基于约束的动态路由选择-CR(constraint-based dynamic routing)是流量工程的重要组成部分，也是实现QoS的关键．相对于传统路由协议只考虑最短路径算法(SFP)来说，基于约束的选路需要根据多个约束条件选择路由，利用现有路由协议的扩展协议，从流量需求和网络资源角度考虑，得出路径需要满足的一系列约束条件和目标函数，计算出由入口路由器到出口路由器间的多条路径．

1．1 CSPF 的应用

基于约束的最短路径优先(CSPF)是流量工程中的核心技术，也是实现QoS业务的关键．基于约束的路由选择既可以是采用QoS的约束条件，也可以是其他策略性的约束条件，例如从提高全网的网络性能方面的考虑．通过网络的呼叫拒绝率降低反映出网络的性能的提高．在确定一条路径时，基于约束的最短路径优先路由选择不仅考虑网络的拓扑，还要考虑流的要求、链路的资源供应及由网络管理员设定的别的策略［3-5］．

图1 CSPF计算过程Fig．1 CSPF calculation process

CSPF路由计算的基本过程是首先根据计算请求从TED中读取相应的网络拓扑信息和约束条件，然后根据约束条件对网络拓扑进行裁减，除去不符合要求的链路和节点，再在新生成的网络拓扑中进行路由计算，得到路径［6-9］．

1．2 QoS路由问题的抽象描述

令 e∈E，c(e)、d(e)、b(e)、j(e)和 l(e)分别表示链路 e的代价、延时、带宽、延时抖动和丢包率［10-11］．求解QoS路由问题就是要在源点 V1到终点Vk之间找到一条最佳路径P，使P代价最小，并且路径带宽不小于最小带宽需求，延时、延时抖动和丢包率均不超过特定上限．此时，QoS路由问题可以运用如下数学模型表示:

式中:C(p)、D(p)、B(p)、J(p)和 L*(p)分别表示路径P的代价、延时、带宽、延时抖动和报文传输成功率;△Bandwidth表示最小带宽，△delay表示最大延时，△jitter表示最大延时抖动，△loss表示最大丢包率，P(V1，Vk)表示从源点V1到终点Vk之间所有可达路径集．

为了在满足业务量要求的前提下，使网络的资源尽可能均匀地使用，避免出现部分网络拥塞而其余链路空闲或利用率较低的不均衡状态，本论文提出了一种新的动态路由生存性算法-SDSA．

2 SRLG的概念

在动态业务的环境中，当网络中到达一条业务请求时，为其建立2条“物理分离”的LSP，分别为工作路由和保护路由．只有业务的2条LSP均存在，才认为业务成功分配了资源，否则业务请求被阻塞．

IETF在草案文本中提出共享风险链路组［12］(SRLG)的概念，对＂物理分离＂概念进一步抽象和扩展．SRLG是指共享相同物理资源(也就是具有共同失效风险)的一组链路．每个SRLG都对应一个唯一的标识，称为 SRLG ID［13］．

设Ck(l)为寻找工作路由时使用的链路权重，Cp(l)为寻找保护路由时使用的链路权重．

设C为链路l的实际物理权重，这个值受到很多因素的影响，如物理长度、物理设备价格、风险约束等的影响．B为链路l的总带宽，U为链路已被占用带宽，B-U为链路剩余带宽．W表示工作路由所经过的链路集，S表示工作路由所经过链路的SRLG标识集．在为到达的新业务计算保护路由时，应根据式(7)更新链路的权值．再利用Dijkstra算法进行寻路，如能找到一条，则该路由同当前业务的工作路由SRLG无关．

式(6)和式(7)［14］是为网络中每条链路设置的2个动态权重，一个用于寻找工作路由，另一个用于寻找保护路由．2个权重值都根据各链路负载情况实时变化．目的是使业务请求尽量建立在空闲波长资源比较富裕的路由上，来均衡链路的负载，避免因为某些链路的波长资源耗尽而产生的网络阻塞．可以看出，空闲波长资源越多(B-U越大)，其链路代价值越小．因此本算法会鼓励工作通路尽可能经过空闲资源多的链路，负载就更均匀地分散到网络中．其中ε1、ε2为负载均衡调整参数．

为了避免SRLG自陷问题已有很多文献进行了研究，提出了各种解决办法［15-16］，本文对链路l的工作权重函数和保护权重函数做如下处理:式(7)中，M为一较大的常数，之所以没有将这种情况下的链路代价设为∞，是因为要利用M来找到造成自陷的链路，从而避免陷阱．

3 面向业务的GMPLS动态生存性算法

3．1 SDSA算法描述

算法基本的步骤:

1)等待业务请求:

如果为连接建立请求，则执行2);

如果为连接释放请求，则执行5);

2)建立工作路由:

根据到达请求的带宽要求b，决定链路的权值函数，然后，利用Dijkstra算法寻找一条工作LSP．

如果没有找到，则拒绝该请求，转至2);

否则，转至3);

3)建立保护路由:

根据式(6)修改拓扑图中链路的权值函数，如是考虑负载均衡的专用通路保护算法，然后利用Dijkstra算法找一条SRLG尽量分离的保护LSP，如果找到，转至4);

否则，拒绝该请求，转至2);

4)分配资源:

根据到达业务请求在工作路由和保护路由上预留相应的带宽资源．然后修改两条通路相应链路的剩余带宽值减去b，转至2);

5)释放资源:

释放所占资源，修改它对应的工作通路和保护通路所经链路的剩余带宽值，将剩余带宽值加上b．

采用Dijsktra最短路算法为业务请求计算工作通路和保护通路．在算法中，考虑2个约束:负载均衡度和资源共享度．针对这2个约束，设计了2个链路代价函数分别针对工作通路和保护通路的计算．

从式(6)可以看出:随着空闲资源增多，链路代价逐渐减小．因此Dijkstra算法会鼓励工作通路尽可能经过空闲资源多的链路，负载就能更均匀地分散到网络中．而负载均衡会导致更多的工作通路满足SRLG分离，其对应的保护通路能共享资源，从而提高了资源利用率．

针对保护通路的链路代价函数．找到工作路径后，在计算保护通路前，根据需要再次调整链路代价．该算法以链路利用率来反映负载均衡情况，从两方面进行考虑:链路和路径．从链路的角度出发，链路的带宽利用率反映链路的负载情况，所有链路的负载状况就可以反映整个网络的流量均衡程度．显然，当网络中所有链路的负载都较轻时，网络不会出现拥塞，所有用户的QoS都能得到保证．

3．2 算法复杂度分析

算法的关键步骤是入口-出口节点对之间的可选路径计算，网络中计算最短路径的复杂度是O(n3)，计算第二最短路径的复杂度是O(n4)，计算第M最短路径的复杂度是O(nM+2)．综合分析算法各步骤，其最终的计算复杂度取决于算法实现中所确定的需要计算的第M条最短路径的复杂度，即O(nM+2)．

4 性能仿真与结论

4．1 仿真实验

为了证明SDSA算法的有效性及其优越性，针对图2所示的网络拓扑进行实验仿真．

图2 美国NFS网络拓扑示意图Fig．2 The USA NFS network topology

对一个业务请求，工作通道和保护通道均按照Dijkstra最短路算法选择路由．工作通道和保护通道两者之间任何一个建路不成功时，业务即被阻塞，不允许为工作通道或保护通道重路由或发起多次重复建路的尝试．

在仿真程序中，指定某一个节点为源节点(如节点0)，依次计算出源节点到其他节点的最短路径和备用路径．

表1 工作LSP和保护LSP对比Table1 Work LSP and protection LSP comparison

由表1可以看出，SDSA算法在选择生存性方面已经部分避开了主用LSP经过的路径．其他计算的一些参数如表2所示．

表2 其他参数Table 2 Other parameters

从上述分析可知，本算法体现流量工程在满足业务QoS参数要求的前提下均衡网络资源的利用率这一目标．

4．2 仿真结论

由仿真实验可知，本文提出的SDSA算法的特点:

1)SDSA算法比普通的OSPF，对于缓解由于流量对引起的资源竞争具有显著的效果;

2)SDSA算法由于优先选择剩余带宽多的链路，因此能够更加有效地降低了资源利用率，避免瓶颈链路的产生;

3)SDSA算法能更好地调节流量在整个网络上的分布，使网络资源得到均衡分布;

4)SDSA算法考虑了SRLG对路由的影响，在避开具有相关链路组的前提下提高了连接请求的接通率．

5 结束语

本文针对MPLS网络，通过对路由算法的分析与研究，提出了一种新的动态路由算法-SDSA，详细介绍了该算法的具体实现，在证明了该算法的正确性的同时，通过仿真实验验证了该算法较传统的路由算法能够更有效利用网络资源的同时，提高网络的吞吐量．

［1］ZHANG X J，KIM S，LUMETTA S S．Reduced flow routing:leveraging residual capacity to reduce blocking in GMPLS networks［C］//Broadnets 2007．［s．l．］，2007:394-403．

［2］KIM S，JUKAN A，LUMETTA S S．Coordinated resource scheduling in high-performance optical grids［C］//Proceedings of the Optical Fiber Communication Conference．Anaheim，USA，2007:1-3．

［3］KIM S，NWANZE N ，ZHANG X J，et al．QoT-guaranteed protection:survivability under physical layer impairments［C］//Broadnets 2008．London，United Kingdom，2008:619-26．

［4］ZHANG X J，KIM S，LUMETTA S S．On resource provisioning for multi-domain networks［C］//Proceedings of the Optical Fiber Communication Conference．San Diego，USA 2009:1-3．

［5］MOHAN G，TIEN E C．QoS routing in GMPLS-capable integrated IP/WDM networks with router cost constraints［J］．Computer Communications，2008，31(1):19-34．

［6］RUEPP S，ANDRIOLLI N，BURON J，et al．Restoration in all-optical GMPLS networks with limited wavelength conversion［J］．Computer Networks and ISDN Systems-CN，2008，52(10):1951-1964．

［7］SINGH Y，SONI M K，SWARUP A．Bandwidth sensitive multi-path routing algorithm［C］//Proceedings of the Eighth IASTED International Conference on Wireless and Optical Communications．Quebec City，Canada，2008:26-28．

［8］LOA A，Ross C，RAM D，et al．Constraint-Based LSP Setup using LDP，IETF work in progress［EB/OL］．［2010-10-13］．http:11 tools．ietf．org/html/draft-ietf-mpls-cr-ldp-05．

［9］LEE Y，SEOK Y，CHOI Y．A constrained multipath traffic engineering scheme for MPLS networks［C］//ICC'02．New York，2002:2431-2436．

［10］王宏．MPLS流量工程中动态路由算法研究［D］．沈阳:辽宁工程技术大学，2005:42-44．WANG Hong．Research of dynamic routing algorithm in MPLS traffic engineering［D］．Shenyang:Liaoning Technical University，2005:42-44．

［11］薛希俊，孙雨耕，刘振肖．基于带宽和跳数的流量工程动态路由选择算法研究［J］．电子学报，2002，30(2):274-278．

XUE Xijun，SUN Yugeng，LIU Zhenxiao．Traffic engineering dynamic routing based on bandwidth and hops［J］．Acta Electronica Sinica，2002，30(2):274-278．

［12］XIA Ming，TORNATORE M，MARTEL C，et al．Risk-aware routing for optical transport networks［C］//Proceedings of the 29th Conference on Information Communications．［s．l．］，2010:588-595．

［13］VELASCO L，SPADARO S，COMELLAS J，et al．Introducing OMS protection in GMPLS-based optical ring networks［J］．The International Journal of Computer and Telecommunications Networking，2008，52:1975-1987．

［14］吕航，孙雨耕，吴雪．流量工程中静态路由算法的研究［J］．电子与信息学报，2003，25(10):1403-1410．

LÜ Hang，SUN Yugeng，WU Xue．Research on static routing algorithm with traffic engineering［J］．Journnal of E-lectronics＆ Information Technology，2003，25(10):1403-1410．

［15］姚婕．面向流量工程的约束路由的研究和实现［D］．南京:东南大学，2005:20-23．

YAO Jie．Study on traffic engineering based on constraintbased routing in MPLS networks［D］．Nanjing:South-East University，2005:20-23．

［16］黄河，李伟琴．MPLS流量工程体系结构优化研究［J］．北京航空航天大学学报，2003，29(3):221-224．

HUANG He，LI Weiqin．Optimization of MPLS traffic engineering architecture［J］．Journal of Beijing University of Aeronautics and Astronautics，2003，29(3):221-224．