分组传送网的环保护和生存机制

基金项目：国家高技术研究发展计划(“863”计划)课题(2007AA01Z252)

    三重播放(3-Play)等新兴宽带数据业务、企事业单位的以太网专线业务、二层虚拟专用网(L2VPN)业务、普通宽带用户的接入量和速率提升等是推动城域传送网转型的主要驱动力，业务IP化和承载IP化推动着基础传送网向分组传送网络(PTN)[1]演进。

    分组传送网络技术保持了传统同步数字体系(SDH)传送网的优点，具有良好的网络扩展性、丰富的运行操作维护(OAM)、快速的保护倒换等。同时增加了适应数据业务的特性：分组交换、统计复用、面向连接的标签交换、分组服务质量(QoS)保证、灵活动态控制。这些特性是网络融合的重要基础性技术。在传送方式上，分组传送网不仅能够提供分组数据业务，兼容传统的时分复用(TDM)业务，还能够提供适合3G移动传输需求的ATM反向复用(IMA)[2]、异步传输模式(ATM)、多等级优先占(用MLPPP)等功能。配套组网需求，设备利用多种封装和适配技术，PTN可以将多种不同的TDM和数据业务统一到分组传送平面，从而成为基于统一分组交换的多业务传输平台[3]。

    众多需求，众多的应用环境、场合都集中存在一个问题：分组传送网络的生存性。分组传送网络的生存性直接影响网络的组网方式(环、格状、星型)。分组传送网络的生存性还直接影响业务建立的方式(1+1或1:1通道保护)，进而影响业务(如标记交换路径建立的阻塞率、资源的利用率、资源分配的协调)[4]。分组传送网络不同于同步数字体系(SDH)网络，其保护机制尚在研究中。PTN在性能上还有待提高，多种类型保护资源互补性小，造成阻塞率高。

    分组传送网络的保护和恢复策略是目前影响业务性能、网络资源利用率、网络生存性的重要因素。随着对分组传送网络生存性要求的提高，对分组传送网络的保护和恢复策略的研究就显得更加重要。保护和恢复机制研究合理，由TDM向分组承载的平滑演进、网络融合和网络全业务化才有可能。

1 分组传送网络研究现状
    面向分组传送网络主要有传送多协议标记交换(T-MPLS)[5]/多协议标记交换-流量工程(MPLS-TE)[6]、运营商骨干桥接/运营商骨干网传输(PBB/PBT)[7]，其生存性策略的研究已经受到业界的关注。国际上许多著名研究机构，如Alcatel[8]、Nortel[7]、Cisco[9]、Sycamore[10]、欧盟FP7[11]、美国Texas大学[12]、Stanford大学[13]、Bell Labs[14]等，都正致力于PTN的生存性机制的研究。中国厂商，如中兴通讯、华为、烽火等也对生存性策略进行了研究。

    国际电信联盟电信标准部门(ITU-T)和因特网工程任务组(IETF)都提出了各自的需求。T-MPLS支持1＋1和1:1线性保护(G.8131)以及Wrapping和Steering环网保护[15](G.8132)。IETF倾向于采用多协议标记交换(MPLS)的快速重路由(FRR)[16]完成1:N线性和环网保护。

    中国对分组传送网络的保护恢复技术处于讨论、研究的阶段。网络设备厂商重点研究电信级的保护倒换策略。

    中国通信标准化协会(CCSA)前年成立了一个论坛专门讨论基于统一交换平面的传送设备，2010年将开始讨论T-MPLS保护机制。

    总体来说研究重点主要是针对T-MPLS支持1＋1和1∶1线性保护能不能适应目前不同业务对保护恢复机制的不同需求。需要通过通道级、链路级保护，以及基于通用多协议标记交换(GMPLS)智能化软件来控制业务的快速选路、重选路，以达到多层次多等级的保护和恢复。

    国际上，对基于分组网络的保护早已有之，例如W.Grover最早提出了用于IP网络的预配置环(P-cycle)的概念[17]。在故障发生前，预先配置好一组P-cycle，遍历所有被保护的节点和链路并预留资源，当故障发生时，按照预先设计好的环进行倒换动作。Robert Sultan在公开的专利中提出了一种基于服务器轨迹的消息通告机制，提高了在拥塞网络中业务的恢复可能[18]。Sycamore的Raymond Xie提出在EtherOptics体系结构分组传送网络中引入智能化的保护恢复机制[19-20]。

2 分组传送网络生存性存在的挑战
    分组传送网络是近几年开展的研究项目。分组传送网络生存性还存在较多挑战，是电信级分组传送网络走向实用的重要环节。

    (1)生存性评估和优化方法
    分组传送网络生存性是网络中重点被关心的问题，对网络生存性的评估本身就是一个比较难以确定的问题，需要确定合理的指标。而对网络生存性的优化存在优化方法和优化技术的限制。由于目前人类认知能力不够和计算机计算能力的有限，使很多优化问题成为难题。人类还不知道最好的网络是什么。计算能力的有限使穷举之路走不通。分组传送网络生存性的优化只能借助于“遗传算法”、“贪婪算法”等找到一个比较好的解，合理解决分布式网络的生存性。

    (2)分布式死锁和资源竞争解决方法
    分组传送网络在快速标记交换路径(LSP)建立、1∶N保护中的抢建、快速LSP重选路等方面都不同程度遇到分布式死锁和资源竞争。目前常采用“鸵鸟算法”来解决，可以满足IP网络的要求，但性能达不到快速保护恢复的要求。分布式死锁这个问题没有得到彻底解决。死锁问题在计算机操作系统和网络中是最头疼的问题。在计算机操作系统理论中，Dijkstra提出了“银行家算法”，但实用性不强。在MPLS中，死锁问题不被重视，但在GMPLS中，Zafar Ali等开始重视死锁问题，并在IETF提出了该问题。目前该问题正在研究中。

    (3)面向分组传送网络保护恢复部署的阻塞率
    现有类SDH的保护机制已经开始被分组传送网络所采用，但在分布式选路的环境下，由于要建条件苛刻的保护通道，阻塞率非常高。为了解决该问题，必须提出条件宽松的保护和恢复机制，与传统严格保护机制互补，满足分组传送网络的特殊需要。

    (4)OAM故障检测性能
    OAM主要是通过周期性交互连通检测报文实现P2P的连通性状态检测，并辅以各种方法实现丢包率、延时、抖动的检测，实现环回、告警抑制、告警回告等。通过自动保护倒换(APS)协议来实现端对端(E2E)两条通道间的相互保护。而类SDH保护必须提供满足电信级50 ms保护的需求。OAM引擎完成通道故障检测报文周期不能超时太多，故障发生25 ms内检测到故障并触发倒换才能保证总倒换时间小于50 ms。所以OAM故障检测性能非常重要。

3 分组传送网络环保护和生存性机制解决方案
    目前分组传送网络核心网以网状网结构为主，所以分组传送网络的环保护有别于类SDH的保护方式。本文介绍北京邮电大学在分组传送网环保护和生存性机制方面的一些研究成果。

    (1)交迭段保护机制
    本文通过对约束机制和交迭段保护机制的深入分析，将两者相结合并根据工作和保护路径分别采用动态链路权重调整，从而提出一种交迭段共享保护算法[21]。交迭段保护机制为整个工作路由提供了多个交迭的保护段，并给出了一种能够合理有效选择这些交迭保护段的方法。与以往保护算法相比，交迭段共享保护可提高网络连接的可靠性，而且还通过不同交迭保护段间资源的合理共享有效地提高网络资源的利用率。

    段保护机制通过使用多个备份保护段来为整条端到端的工作路径提供保护。与通道保护相比，段保护方式的主要优点是缩小了恢复的范围。当一处链路或节点发生故障时，只有与之相对应的保护段被激活，因此缩短了恢复的时间。另外，段保护方式并不是为工作路径中的每条链路都提供一个保护段，因而它比起链路保护又具有更高的资源利用率。交迭段保护机制是按照工作路径中的每个工作段分别提供相交迭的备用保护段。某些工作链路受到多于一条的备份段的保护，从而在提高了网络生存性的同时，对于网络资源的分配也更加灵活可变。传统的非交迭段保护无法提供对段间节点的保护，而交迭段保护成功克服了这个缺点。由于相邻段之间的交迭，所以段间节点的故障不会导致工作和保护段同时失效。交迭和非交迭段保护如图1所示。

    (2)预规划多环方案
    针对网状网中保护发生故障点恢复不确定的问题，本文提出一种新的预规划多环(P-mcycle)恢复方案。该方案应用了P-mcycle生成的ILP优化算法和Sub-cycle二次选路算法，在故障业务恢复时间有效的前提下提高了故障保护成功率和预留保护资源的容量效率，从而改善了分组传送网络快速恢复的有效性和可靠性。
P-mcycle生成算法基于整数线性规划(ILP)，以ILP为基础形成故障独立通道保护P环，但计算时间复杂度过大。小型网络计算需要1 h，大型网络计算会达到2 d。ILP优化算法由于将动态业务分布、业务对称性等变量和约束条件放至二次选路时独立解决，纯ILP模型仅用于寻找最优的P环组合，计算量显著减少，从而变成网络拓扑的静态规划。

    由于变量数和约束条件的减少，计算复杂度大为降低，将采用一种有效的预选择方法来缩小ILP问题的解空间。在给定的网络拓扑中使用改进的深度优先搜索算法(DFS)搜索出全部简单环，在环集合中依次判断环上链路是否满足限制。选取M个AE值最大的环构成次优解搜索空间，使用ILP优化算法求解出一组P-mcycle，既满足保护所有的工作波长，又不超过网络中预先设置的最大预留波长。即用最少的预留资源实现100%业务恢复能力。

    这里应用了P-mcycle生成算法及二次选路算法。使用二次选路分担了传统P-cycle预配置的计算复杂度，而且优化了切换保护选路。改进的P-mcycle故障恢复时间符合分组传送网络严格的生存性要求，并且在故障保护成功率、保护资源占用率、容量效率等方面比传统P-cycle有所提高。据仿真数据显示在平均节点度低的格状网(Mesh)网络优化效果更加明显。

    后续工作将着重于以下几个方向的进一步研究：根据节点故障恢复，多链路/多节点恢复实现基于P-mcycle算法的优化；在P-mcycle建立候选环的过程中引入对业务分布的动态变化，生成更加合理的P-mcycle资源分布更加合理；考虑业务的方向性，进一步研究二次选路的流量工程，以更少的网络资源，实现更高的业务保护成功率。

    (3)冲突避免算法降低建路和保护阻塞率
    在建路的时候会出现下面一种情况，两个路径请求在一条链路的两端同时预留相同的资源(端口或者波长λ)并发出预定消息。当预定消息到达链路的对端时，发现资源已经被占用。过去采用的方法是在发现资源被占时，节点认为建路失败，回复预定错误消息。这样一条链路的两端同时发现资源被占，同时认为建路失败，浪费了建路资源。

    这里构想了一种新的方法避免这种冲突。如图2所示。原理是对同时发出的预定消息采用一种优先级比较策略，使其中一条路建成[22]。如，在节点C和D之间发生冲突，C为路径(Path)1分配的资源和D为路径2分配的资源相同。当C向D发的预约(Resv)1消息到达D端时发现资源已经被占用了，这时D端只能认为建路失败；同样C端在收到D发的预约2消息时也同样认为建路失败。两条路都无法建成。冲突避免算法在发路径消息的时候携带一个计数器i，在源节点将其设为0。当路径消息到达一个节点的时候计数器加1，同时在节点存放当前计数器的值。当路径消息到达目的节点的时候i的值就是建路成功需要经过的链路数。图中A到E建路需要经过5条链路，E到B建路需要经过4条链路。

    采用冲突避免算法在长距离建路时，成功的概率可能比较小。例如一个请求A建路需要经过7条链路，另一个B请求只需要3条。其中发生冲突的链路距离A请求源节点有2条链路而离B请求源节点还有1条链路的情况下，B请求建路成功，而A失败，这样A请求之前建成的5条路就都必须拆掉，浪费了很多的资源。

    (4)延时恢复算法
    延时恢复算法是在网络出现故障的时候所采用的一种机制。其主要的思想是在网络故障恢复的过程中采用一种顺序延时的处理方法。

    采用的方法是在发生故障以后，让业务的源节点延时发送通报(Notify)消息。如图3所示。两条通报消息之间插入一段时间间隔t发送。采用这样处理方法，会减小在故障恢复时业务的再路由和发信令过程中发生资源冲突的几率。图3中，两条方向相对的业务在恢复的时候，顺序发信令过程中没有发生资源冲突的问题。

4 结束语
    分组传送网是未来发展的一个重要方向，它的环保护和生存性是直接影响服务质量的重要技术。但目前在故障检测、网络部署、保护恢复的新方案方面还存在很多挑战。传统现有的一些保护恢复方法已不能满足分组传送网的需求，需要新型网络保护和恢复机制。这些挑战在未来会得到逐渐的解决。

5 参考文献
[1] NEC. Packet transport network tech makes NGNs reliable[EB/OL]. [2007-04-26]. http://www.eetindia.co.in/ART_8800462498_1800006_NT_e79940b5.htm.
[2] LEE D S, SENGUPTA B. Queueing analysis of a threshold based priority scheme for ATM networks[J]. IEEE/ACM Transactions on Networking,2003,1(6): 709-717.
[3] VAINSHTEIN S, FROST T. Emulation of TDM circuits over MPLS using raw encapsulation implementation agreement[R]. MFA Technical Committee, MFA 8.0.0. 2004.
[4] ITU-T Study Group- Question 9/15.Transport equipment and network protection/ restoration[R]. 2009.
[5] ITU-T Recommendation G.8110.1/Y.1370.1-2006. Architecture of transport MPLS (T-MPLS) layer network[S]. 2006:8-15.
[6] IETF RFC 3812. Multiprotocol label switching (MPLS) traffic engineering (TE) [S]. 2004.
[7] Nortel. Provider backbone bridges (PBB) and provider backbone transport (PBT) [EB/OL]. [2006-02-15]. http://www2.nortel.com/go/solution_content.jsp?segId=0&catId=0&parId=0&prod_id=55120.
[8] Alcatel. PWE3 response to ITU-T SG15Q9 Liaison on TMPLS ring protection [EB/OL]. [2008-02-09]. http://www.ietf.org/mail-archive/web/pwe3/current/msg09503.html.
[9] Cisco. Multipoint TMPLS[EB/OL]. [2007-01-25]. http://www.ietf.org/ mail-archive/web/pwe3/current/ msg08706.html.
[10] 2nd VIOLA Workshop, Mar 22-23, 2006, Bonn, Germany[C]//e-Photon/ONe+/IST Phosphorous Meeting, Sep 16,2007, Berlin, Germany.
[11] YOO S J B. Network interoperability - The role of optical technologies[C]// e-Photon/ONe+/IST Phosphorous Meeting, Sep 16,2007, Berlin,Germany.
[12] Fall 2008 graduate research day[R]. Dallas, TX, USA: University of Texas. 2008.
[13] Ixia to provide IP testing horsepower in the largest public carrier Ethernet interoperability test [EB/OL]. [2008-09-24]. http://www.reuters.com/article/pressRelease/idUS181350+22-Sep-2008+BW20080922.
[14] Alcatel-Lucent Bell Labs. Alcatel-Lucent Bell Labs and NTT Photonics Labs sign collaborative agreement related to optical packet switch technology[EB/OL]. [2008-05-05]. http://goliath.ecnext.com/coms2/gi_0199-7956799/Alcatel-Lucent-Bell-Labs-and.html.
[15] LEE, B J, BACQUE J B. Protection system and method for resilient packet ring (RPR) interconnection: US, 7274656 [P]. 2007-09-25.
[16] MPLS FRR protection overview[EB/OL]. [2009-04-01]. http://www.juniper.net/ techpubs/software/nog/nog-mpls-frr/html/frr-overview.html.
[17] GROVER W D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning network restoration Communications[C]//Proceedings of International Conference on Communications (ICC'98):Vol 1, Jun 7-11, 1998, Atlanta, GA, USA. Piscataway, NJ, USA:IEEE, 1998:537-543.
[18] Packet transport: It’s time to clear up the confusion[J]. Fibre Systems Europe, 2008(3):21.
[19] SULTAN R,?YONG L. Dunbar l. Network availability enhancement technique for packet transport networks:US, 370235[P]. 2008-11-13．
[20] XIE R. ‘EtherOptics’ optimizes intelligent IP/Ethernet transport [J]. Lightwave, 2008,25(5).
[21] 孙翔, 陆月明, 纪越峰. 基于SRLG约束和资源共享的交迭段保护机制研究[J]. 光子学报, 2009,38(6):1386-1391.
[22] 陆月明, 赵同, 弓伟丽, 等. 光网络实时连接恢复中资源分配死锁解除方法[J]. 通信学报, 2008,29(12):91-95.
[23] 王贤茜, 王淼, 陆月明, 等. 串行同源故障通告机制及其在ASON中的应用[J]. 通信学报, 2009,30(5):74-81.

收稿日期：2010-03-15

[摘要] 在保护和恢复机制方面，分组传送网络面临运行操作与维护(OAM)检测性能、网络资源优化、资源分配死锁、资源部署阻塞等众多挑战。传统的保护和恢复机制已不能满足分组传送网络的需求。为了提高分组传送网络保护恢复性能、网络资源的利用率、业务恢复可能性，减少业务部署的阻塞率，文章对交迭段保护机制、预规划多环、冲突避免算法、延时恢复算法等新型保护恢复机制进行了研究，得出观点：保护和恢复机制合理，由时分复用向分组承载的平滑演进、网络融合和网络全业务化才有可能。

[关键词] 分组传送网络；保护；恢复；阻塞率

[Abstract] In its protection and restoration mechanisms, Packet Transport Networking (PTN), is facing many challenges. Such challenges arise in the areas of Operation Administration and Maintenance (OAM) detection performance, network resource optimization, resource allocation deadlock, and resource deployment blocking. Traditional mechanisms of protection and restoration cannot meet the requirements of Packet Transport Networks. In order to improve protection and restoration, network resource use, probability of service restoration, and to decrease the probability of service blocking, this paper introduces mechanisms such as overlay section protection, pre-configure pre-planned cycle, conflict-release algorithm, and delay restoration algorithm. Finally, it concludes that only the protection and restoration mechanism can reasonably achieve network integration, network operation, and the smooth evolution from TDM to packet bearing networks.

[Keywords] packet transport network; protection; restoration; blocking