摘  要： 随着网络承载数据量的不断增加和实时业务的迅速发展，要求网络故障的恢复时间越来越短，而传统路由协议收敛时间过长，已不能满足其要求，并且多故障同时发生的情况也在增多，这些都影响了IP网络的稳定运行，严重时甚至会造成一定的经济损失。提出一种改进的IP网络多故障情况下的快速恢复算法，可以用少量的备份拓扑应对同时发生的多个链路和节点故障。与传统算法相比，有效节省了网络存储资源，增强了网络的可扩展性，具有良好的实用价值。
关键词： IP网络；故障恢复；MRC；备份拓扑

    互联网在设计之初主要用于传输非实时业务，如收发电子邮件、浏览网页等。当网络发生故障时，应用传统路由协议（OSPF、IS-IS等）进行全网路由收敛，耗费时间长达数秒[1]，对于非实时业务，这个时间是可以接受的。然而，近年来网络实时业务（如在线游戏、VoIP、视频播放等）不断发展，要求网络故障的恢复时间达到毫秒级，传统路由协议已不能满足此要求，因此IP网络的故障快速恢复技术成为当前的研究热点。网络中大部分故障为单链路或节点故障[2]，这种情况下的快速恢复技术比较多，主要有快速重路由算法（IP FRR）、故障不敏感路由算法（FIR）、偏转路由算法（DR）等[1]。但是随着网络的迅速发展和其规模的不断扩大，承载的数据流越来越多，多个链路和节点同时发生故障的概率也逐渐增加，带来的影响比较大，可是由于这种情况以前发生概率很小，国内外学者关注的并不多，其研究成果主要是将弹性路由层算法（RRL）和多路由配置算法（MRC）应用于多个故障的快速恢复中，但都存在一些不足之处。本文将在比较总结RRL算法和MRC算法的基础上，提出一种改进的IP网络多故障快速恢复算法，并进行仿真实验验证其优化效果。
1 两种主要的多故障快速恢复算法
    目前，在IP网络中处理多故障快速恢复问题的方法主要是先应式的多拓扑（MT）技术，基本思想是由网络原始拓扑图生成多个备份拓扑来保护所有链路和节点。如果某些链路和节点同时发生故障，则快速切换到能保护这些组件的备份拓扑，被保护的网络组件在对应的备份拓扑中不会转发任何数据流，从而实现故障时数据流的正常传输。该技术的重点是如何根据网络原始拓扑图构建备份拓扑集，使得其中包含的备份拓扑数量尽可能少，并且每个节点对之间的最佳传输路径长度尽可能短。
1.1 弹性路由层算法
    RRL算法基于“路由层”描述备份拓扑，每个层包含网络中的部分链路和所有节点，如果某一层中不包含原始拓扑的某条链路，则该链路在此层中被保护；如果在该层中某个节点只有一条链路与之相连，则该节点在此层中同样被保护[3]。
1.2 多路由配置算法
    MRC算法基于“配置图”描述备份拓扑，每个图包含有正常链路、孤立链路、受限链路和正常节点、孤立节点。算法中孤立链路被赋予一个无穷大的度量值，故其在对应的备份拓扑中不会被用来转发数据流。受限链路被赋予一个有限但很大的度量值，其在对应的备份拓扑中仅能作为第一跳或最后一跳链路接收和发送数据[4]。只有孤立链路和受限链路才可以连接到孤立节点。算法的实现过程是通过将前一个备份拓扑中孤立节点连接的受限链路和其对端节点，在下一个备份拓扑中孤立出来，如此循环直到每个网络组件都被孤立出来为止。
    综上所述，RRL算法生成的每个“路由层”只包含网络中的所有节点和部分链路，去除了其保护的那部分链路，故生成的备份拓扑实际上改变了原始拓扑图结构。MRC算法与之不同，其生成的“配置图”不改变拓扑图结构，只是设置链路度量值使数据流传输时不经过故障部件，相比RRL算法简单可行。但是MRC算法生成的备份拓扑数量过多，造成相应的转发表项和链路状态信息报文过多，消耗大量的存储资源，在网络规模较大时，节点不能存储所有的备份拓扑信息，从而影响网络的扩展性。
2 算法改进
    针对MRC算法存在的问题提出一种改进算法，能够有效生成数量尽可能少的备份拓扑，但同样可以保护网络所有链路和节点，旨在用最少的存储资源实现多故障下的快速恢复。该算法中孤立链路、受限链路和孤立节点的定义与前文所述一致。改进算法将自动生成网络无向图G=(N，E)的备份拓扑集，图1是其实现流程图。

    算法先初始化所有参数，随机产生一组用于生成最小生成树的链路权值集。该链路权值与链路度量值不同，因为改进算法中第一个最小生成树将影响以后创建备份拓扑，如果由链路度量值决定权值，那么只能生成一个确定的最小生成树，而它可能并不适合用来创建其他备份拓扑，所以这里使用一组随机产生的链路权值来生成最小生成树，如果它不适合用来进一步创建其他备份拓扑，就循环执行整个算法，随机产生另外一组合适的链路初始权值集来生成最小生成树。
    初始化完成后，会得到一个最小生成树，一部分权值较大的链路被分离出来，将其设为孤立链路（链路的度量值设为无穷大值），最小生成树的叶子节点设为孤立节点，与孤立节点相连的链路设为受限链路（链路的度量值设为一个有限但很大的值）。由此，依据原始拓扑图的最小生成树就可以得到第一个备份拓扑，其中孤立和受限链路的度量值被重新设置，其他链路保持不变。然后，检查是否满足结束条件。算法中维护一个包含尚未被孤立出来的所有链路和节点的集合G′，如果G′为空，表明备份拓扑集已经能保护所有网络组件，则结束整个算法；如果G′不为空，结束条件不满足，则算法将对最小生成树的相关链路权值进行多次（M次）调整，尝试产生最佳的下一个备份拓扑，可以尽可能多地保护尚未被孤立的链路和节点。权值调整具体方法为：对尚未被保护的链路权值增加一个任意值，那么调整后生成的最小生成树就可以使该链路孤立出来；将之前备份拓扑连接到非孤立节点的某一条链路的权值设为一个更小的值，而与该节点相连的其他链路的权值设为一个更大的值，则在调整后生成的最小生成树中该节点就会成为叶子节点。经过M次调整后选取一组最佳权值，用于产生下一个备份拓扑，它能最大数目地保护尚未被孤立的链路和节点，最终减少备份拓扑的个数。最后，循环执行直到获得的备份拓扑集满足要求为止，即所有的链路和节点都至少被一个备份拓扑保护。
3 算法仿真与性能分析
    对改进算法和传统MRC算法在不同网络拓扑模型中的表现进行仿真实验，验证其在减少备份拓扑个数和节省网络存储资源方面具有比较好的性能。实验中采用的网络拓扑模型是随机型的Waxman模型和幂律型的BA模型。
    图2和图3是分别对Waxman模型和BA模型的拓扑实例进行仿真的结果。表明相同情况下，改进算法产生的备份拓扑总数一直都少于传统MRC算法。网络拓扑中节点数越多，这种差别越明显。备份拓扑总数减少将对应减少节点中存储的转发表项和网络中的链路状态信息报文，从而节省有限的存储资源。

    结果还表明，无论是Waxman模型还是BA模型，随着网络中节点个数的增加，传统算法生成的备份拓扑总数会同时增加很多，而改进算法中这种变化比较平缓。这是因为由传统MRC算法相继生成的备份拓扑中，孤立链路和孤立节点总是处在相邻的位置上，其他不在此范围内的链路和节点要一直等到循环到达，才能被孤立出来。所以当网络规模扩大时，就需要生成更多的备份拓扑；而改进算法由最小生成树尽最大可能孤立出所有链路和节点，其受网络规模的影响较小，因此当网络中节点数增加时，算法生成的备份拓扑个数变化并不大。此外，虽然改进算法在两个拓扑模型中都有良好的表现，但在BA模型中表现更好，这是由于两种模型中节点度分布不同造成的。BA模型中节点度分布服从幂律分布特性，小部分节点需承担大量的链路负载；Waxman模型中节点度的分布则比较均衡，而改进算法总是将度量值大的链路优先孤立出来，故其在BA模型中表现更好。目前网络服务提供商(ISP)的网络拓扑大多服从幂律分布特性[5]，因此改进算法更适合应用于实际网络中。
    本文提出了一种改进的IP网络多故障情况下的快速恢复算法，相比传统MRC算法，它可以用较少的备份拓扑应对同时发生的多个链路和节点故障，能有效节省网络存储资源，并且受网络中节点个数变化的影响较小，在其生成的备份拓扑中应用最短路径算法就可以获得每个节点对之间长度最短的传输路径。该算法在服从幂律分布特性的实际大规模网络中表现更优，具有良好的实用价值。
参考文献
[1] 张民贵，刘斌.IP网络的快速故障恢复[J].电子学报，2008，36(8)：26－28.
[2] MARKOPOULOU A，IANNACCONE G，BHATTACHARYYA S，et al.Characterization of failures in an IP backbone[C]. Proceedings of IEEE INFOCOMM’04.HK，2004.
[3] HANSEN A F，CICIC T，GJESSING S，et al.Resilient routing layers for recovery in packet networks[C].The International Conference on Dependable Systems and Networks(DSN)，2005.
[4] KVALBEIN A，HANSEN A F，CICIC T，et al.Fast IP network recovery using multiple routing configurations[C]. Proceedings of IEEE Infocom，2006.
[5] MEDINA A，LAKHINA A，MATTA I，et al.BRITE：an  approach to universal topology generation[C].IEEE MASCOTS，2001.