, 刘洁琦1, 尹霞2 1. 山西大学 软件学院, 太原 030006;
2. 清华大学 计算机科学与技术系, 北京 100084
收稿日期：2018-01-02
基金项目：国家“八六三”高技术项目（2015AA016105）；国家自然科学基金资助项目（61702315）
作者简介：耿海军(1983-), 男, 讲师。E-mail:ghj123025449@163.com
摘要：针对已有的路由保护方案没有很好权衡路由保护算法的故障保护率和路径拉伸度之间的关系，该文提出了一种基于段路由（SR）体系结构的快速重路由算法IPFRRBSR。IPFRRBSR为每个源-目的对计算两条路径，其中一条是最短路径，另外一条是利用段标签构造的备份路径。当网络没有故障时利用最短路径转发报文，当网络出现故障时利用备份路径转发报文。最短路径和备份路径（除去源和目的）没有公共节点，因此二者几乎不会同时发生故障。实验结果表明：该算法不仅可以应对网络中任意的单节点故障情形，并且具有较小的路径拉伸度。
关键词：计算机网络网络故障路由保护段路由段标签
Single node failure routing protection algorithm based on segment routing
GENG Haijun1
, LIU Jieqi1, YIN Xia21.School of Software Engineering, Shanxi University, Taiyuan 030006, China;
2.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Abstract: Existing routing protection schemes do not accurately consider the relationships between the failure protection ratio and the path stretch. A simple IP fast reroute based on the segment routing (IPFRRBSR) algorithm is given here to consider these relationships. IPFRRBSR calculates two paths between each source-destination pair with one being the shortest path and the other being a backup path constructed using segment labels. The packets are forwarded along the shortest path when the network is in the normal state, but are forwarded along the backup path when a network failure occurs. Since the shortest path and the backup path (except for the source and destination nodes) do not have any common nodes, the probability of them failing simultaneously is very low. Tests show that IPFRRBSR can deal with single node failures in the network and has a small path stretch.
Key words: computer networknetwork failurerouting protectionsegment routingsegment label
在过去的几十年里, 互联网已经从一个最初支持发送邮件等业务的小型网络迅速演变为支持社交网络、视频流和云计算等的大型基础设施[1-2]。与此同时, 用户对互联网服务提供商(Internet service provider, ISP)的服务质量提出了更加严格的要求, 例如给用户提供无间断服务、低延迟服务和高带宽服务等[3-7], 其中如何向用户提供无间断服务是ISP面临的一个严峻挑战。在传统网络体系结构中, 学术界提出利用节点保护条件(node protection condition, NPC)[8]、网络故障不敏感路由(failure insensitive routing, FIR)[9]、Not-Via[10]以及多协议标签交换(multi-protocol label switching, MPLS)[11]等技术来提供无间断服务, 以应对网络中的突发故障情形。虽然NPC的实现方式简单, 但是无法很好地应对网络中的单节点故障。FIR、Not-Via和MPLS虽然可以应对网络中所有可能的单节点故障情形, 但是其实现过于复杂。NPC、FIR、Not-Via和MPLS等技术的重路由的路径拉伸度也比较高, 大大增加了网络的延迟, 降低了ISP的服务质量。因此, NPC、FIR、Not-Via和MPLS都没有很好地权衡算法实现复杂度、故障保护率和路径拉伸度之间的关系。
段路由(segment routing, SR)[12-15]旨在支持具有严格的服务等级协议(service level agreement, SLA)保证的服务, 其核心思想是利用一系列的分段来构建特定的端到端的路径。在段路由结构中, 需要将段标签加入到数据包的头部, 然后利用这些标签完成报文的转发。段路由中有两种段标签, 分别是节点标签和邻接标签。节点标签表示一个路由器, 而邻接标签表示当前路由器的一个本地接口。目前, 主要的网络供应商已经支持SR, 并且将会进一步大部署规模。SR建立在现有的网络路由和连接管理协议的基础上, 其重要特征之一就是当网络出现故障时可以实现自动重新路由连接。因此, 可以利用SR实现基于IP的快速重路由机制。
本文首先描述了如何利用SR解决网络中单节点故障问题, 然后提出了一种基于SR的IP快速重路由(IP fast reroute based on SR, IPFRRBSR)算法, 该算法包括如何计算段标签和备份路径两部分内容, 最后在大量拓扑结构上进行了实验模拟。
1 网络模型和问题描述网络拓扑可以表示为图G=(V, E)。在图G中，V表示网络拓扑中所有节点的集合, E表示网络拓扑中所有链路的集合, 即对于图G中
本文的问题可以描述为：给定网络拓扑G=(V, E), 计算图中所有(o, d)(o≠d)对的段标签, 使得利用段标签计算出的备份路径可以应对网络中所有可能的单节点故障。
输入：网络拓扑结构G=(V, E),
输出：r(o, d), o, d∈V, o≠d,
目标：Converge(o, d, l, p′)=1。
r(o, d)表示(o, d)(o≠d)之间的段标签的集合, Converge(o, d, l, p′)=1表示对于所有的(o, d)(o≠d)计算出的备份路径p′可以应对网络中所有的单节点故障。本文讨论的网络是一个健壮性网络。健壮性网络可以定义为当该网络中任意一个节点断开时, 网络依然保持连通。选择健壮性网络是因为对于一个非健壮性网络, 讨论单节点故障没有实际意义。
2 IPFRRBSR算法2.1 算法需要解决的关键问题下面通过2个步骤来解决第1节中提出的问题：
步骤1??计算出所有(o, d)(o≠d)之间的段标签。
步骤2??对于每一个(o, d)(o≠d), 通过计算出的段标签来计算二者之间的备份路径。
在上述2个步骤中, 步骤2较为简单, 备份路径可以用公式p′(o, d, r(o, d))=p(o, r1, G)° p(r1, r2, G)°…°p(rn, d, G)表示。其中：r1, r2, r3, …, rn表示(o, d)对之间共有n个段标签, rn用来表示r(o, d)中的第n个段标签; p(o, rn, G)表示从o到rn的最短路径。对于(o, d)(o≠d), 如果随意计算它们之间的段标签, 则它们之间的备份路径就可能无法应对网络中所有的单节点故障。下面将详细描述如何计算源-目的对之间的段标签, 从而实现本文提出的目标。
2.2 算法实现图 1详细描述了IPFRRBSR的执行过程。算法输入为网络拓扑G=(V, E), 输出为拓扑中所有(o, d)对的r(o, d)的集合U。对于节点v, 构造以该节点为根的最短路径树(算法第2行)。将该树中除去节点v以外的其他节点按照深度优先的顺序存储在队列Q(v?Q)中(第3行)。算法需要一系列的迭代过程, 在每次迭代过程中, 从队列Q(v?Q)中取出第1个元素o(第4—6行), 这样就形成一个(o, d)对。为了解决算法中可能遇到的最后下一跳问题, 将所有链路I(b(o, d, G))从拓扑G中删除得到G′, 并且计算(o, d)对之间的最短路径p(o, d, G′)(第7—8行)。通过函数Relaynode(o, d, p(o, d, G), p(o, d, G′))计算出(o, d)对间的段标签r(o, d), 将计算好的r(o, d)并入集合U中(第9—10行)。最后, 输出集合U(第13行)。
 |
| 图 1 算法IPFRRBSR的执行过程 |
| 图选项 |
算法IPFRRBSR中的第9行调用了函数SRLABEL, 图 2描述了SRLABEL函数的执行过程。首先, 需要给该函数输入网络拓扑G和一个(o, d)对, 以及算法IPFRRBSR第8行计算出的p(o, d, G′)。p(o, d, G′)在这里表示为{o, v1, v2…vn, d}。函数输出为一个(o, d)对的段标签集合r(o, d)。如果p(o, d, G′)={o, d}, 即b(o, d, G′)=d, 则这个(o, d)对不存在段标签(第1—3行)。该函数定义了3个临时变量o′, d′, n′, 其中o′, d′∈{o, v1, v2…vn, d}, 因此p(o′, d′, G′)
 |
| 图 2 函数SRLABEL的执行过程 |
| 图选项 |
2.3 算法复杂度分析在IPFRRBSR中, 对于网络中的每个节点, 需要计算一棵以该节点为根的最短路径树, 这部分的时间复杂度为|V|·O(|V|lg|V|+|E|)。计算节点对之间的段标签的最坏时间复杂度为O(|V|), 即节点间的路径包含的最大节点数, 为所有节点对计算段标签的时间复杂度为V2·O(|V|)。因为计算以该节点为根的最短路径树可以并行计算, 所以该部分的算法复杂度可以为O(|V|lg|V|+|E|)。同理, 计算段标签也可以并行计算, 该部分的算法复杂度为O(|V|)。因此, IPFRRBSR的算法复杂度为O(|V|lg|V|+|E|)。
2.4 算法收敛性分析IPFRRBSR算法主要执行Dijkstra算法和字符串匹配算法。当计算两个节点之间的段标签时, 首先根据图 1算法的第2行计算出的最短路径树构造出这两个节点之间的最短路径, 然后根据图 1算法的第7—8行重新计算这两个节点之间新的最短路径。然后, 调用函数SRLABEL执行字符串匹配算法, 函数SRLABEL详细讨论了节点间所有段标签的可能情况, 因此IPFRRBSR必定会收敛。
3 实验利用模拟实验来评价本文提出的算法IPFRRBSR的性能, 并且与算法NPC和Not-Via进行比较。模拟实验的评价指标主要包括故障保护率和路径拉伸度。为了说明IPFRRBSR不会引入过多的额外负担, 计算IPFRRBSR在不同拓扑结构中对应的段标签的个数。
为了衡量算法的性能, 本文采用了两种类型的拓扑结构, 包括2个真实拓扑结构NJLATA和TORONTO[6], 以及4个利用Brite软件生成的拓扑结构。Brite(n, m)表示该拓扑的节点个数为n, 度数为m。
3.1 故障保护率本节通过故障保护率来测试不同算法应对单节点故障的能力。表 1列出了不同算法在两种类型的拓扑中对应的故障保护率。从表 1可知, IPFRRBSR和Not-Via的故障保护率都为100%, 但是NPC的故障保护率在80%~98%之间。
表 1 故障保护率
| 网络拓扑 | IPFRRBSR/% | Not-Via/% | NPC/% |
| NJLATA | 100 | 100 | 80 |
| TORONTO | 100 | 100 | 90 |
| Brite(40, 4) | 100 | 100 | 95 |
| Brite(60, 4) | 100 | 100 | 97 |
| Brite(80, 4) | 100 | 100 | 97 |
| Brite(100, 4) | 100 | 100 | 98 |
表选项
3.2 路径拉伸度本节将衡量当网络中出现单节点故障时, 报文的实际转发路径和发生该故障后对应的最短路径的比值, 即路径拉伸度。因为NPC算法的故障保护率不是100%, 所以在做此实验时, 仅仅比较NPC算法中能够被保护的路径对应的路径拉伸度。表 2列出了不同算法对应的平均路径拉伸度。由表 2可知, 在其中所有拓扑结构中, IPFRRBSR的路径拉伸度最小, NPC的路径拉伸度最大。特别地, 在拓扑NJLATA中, IPFRRBSR的路径拉伸度为1, 而NPC的路径拉伸度为1.072 326。
表 2 平均路径拉伸度
| 网络拓扑 | IPFRRBSR | Not-Via | NPC |
| NJLATA | 1.000 000 | 1.004 849 | 1.072 326 |
| TORONTO | 1.048 470 | 1.121 292 | 1.126 542 |
| Brite(40, 4) | 1.031 865 | 1.065 413 | 1.298 922 |
| Brite(60, 4) | 1.044 457 | 1.093 645 | 1.349 561 |
| Brite(80, 4) | 1.063 775 | 1.134 678 | 1.318 934 |
| Brite(100, 4) | 1.067 956 | 1.146 474 | 1.341 906 |
表选项
为了更加精细地描述路径拉伸度, 本文统计了不同算法对应的每个源-目的的路径拉伸度。图 3和4分别表示不同算法在拓扑NJLATA和拓扑TORONTO中路径拉伸度的累积概率分布。从图 3中可知, IPFRRBSR中所有源-目的的路径拉伸度均为1, 远远小于Not-Via和NPC的路径拉伸度。由图 4可知, IPFRRBSR中源-目的的路径拉伸度为1的比例为72%, 路径拉伸度小于1.5的比例为98%。
 |
| 图 3 (网络版彩图)不同算法在NJLATA的路径拉伸度 |
| 图选项 |
 |
| 图 4 (网络版彩图)不同算法在TORONTO的路径拉伸度 |
| 图选项 |
3.3 段标签个数本节将描述算法IPFRRBSR在不同拓扑结构中对应的段标签的个数。由表 3可知, IPFRRBSR算法对应的平均段标签的个数均小于1.2, 因此不会增加过多的额外负担。
表 3 段标签平均个数
| 网络拓扑 | 段标签平均个数 |
| NJLATA | 1.125 000 |
| TORONTO | 1.085 366 |
| Brite(40, 4) | 1.024 194 |
| Brite(60, 4) | 1.031 699 |
| Brite(80, 4) | 1.035 035 |
| Brite(100, 4) | 1.020 440 |
表选项
图 5描述了算法IPFRRBSR在两种拓扑中每个源-目的对的段标签个数累积概率分布。从图 5可知, 除去NJLATA, 在剩余拓扑中92%以上的源-目的对的段标签个数为1, 只有不到8%的源-目的对的段标签个数为2。NJLATA中仅仅有0.001%的源-目的对的段标签个数为3。
 |
| 图 5 (网络版彩图)段标签个数累积概率分布 |
| 图选项 |
4 结论本文提出了一种基于SR的域内路由保护算法, 即IPFRRBSR算法。IPFRRBSR算法计算节点对(o, d)之间段标签的方法如下：首先计算二者之间的最短路径；然后从原拓扑结构中删除节点o到节点d的最优下一跳, 在新的拓扑中重新计算二者之间的最短路径；最后根据这两条最短路径的匹配情况计算二者之间的段标签。因为利用IPFRRBSR计算出的节点对之间的备份路径和节点对之间的最短路径不包含公共节点(除去源和目的节点), 所以IPFRRBSR可以应对网络中的单故障情形。实验结果表明：IPFRRBSR不仅可以提供100%单故障保护率, 并且路径拉伸度较低, 很好地解决了目前路由保护方案无法平衡故障保护率和路径拉伸度的难题。IPFRRBSR可以为ISP解决域内路由可用性提供一种有效的解决方案。
参考文献
| [1] | GENG H J, SHI X G, YIN X, et al. Algebra and algorithms for multipath QoS routing in link state networks[J]. Journal of Communications and Networks, 2017, 19(2): 189-200. DOI:10.1109/JCN.2017.000028 |
| [2] | GENG H J, SHI X G, WANG Z L, et al. A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J]. Computer Communications, 2018, 116: 225-239. DOI:10.1016/j.comcom.2017.12.008 |
| [3] | ZHENG J Q, XU H, ZHU X J, et al. We've got you covered: Failure recovery with backup tunnels in traffic engineering[C]//Proceedings of the 24th IEEE International Conference on Network Protocols (ICNP). Singapore, 2016: 1-10. |
| [4] | ELHOURANI T, GOPALAN A, RAMASUBRAMANIAN S, et al. IP fast rerouting for multi-link failures[J]. IEEE/ACM Transactions on Networking, 2016, 24(5): 3014-3025. DOI:10.1109/TNET.2016.2516442 |
| [5] | YANG Y, XU M W, LI Q. Tunneling on demand: A lightweight approach for IP fast rerouting against multi-link failures[C]//Proceedings of the 24th IEEE International Symposium on Quality of Service (IWQoS). Beijing, 2016: 1-6. |
| [6] | ANTONAKOPOULOS S, BEJERANO Y, KOPPOL P. Full protection made easy:The DisPath IP fast reroute scheme[J]. IEEE/ACM Transactions on Networking, 2016, 23(4): 1229-1242. |
| [7] | GOPALAN A, RAMASUBRAMANIAN S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees[J]. IEEE/ACM Transactions on Networking, 2016, 24(3): 1336-1349. DOI:10.1109/TNET.2015.2440179 |
| [8] | ATLAS A, ZININ A. Basic specification for IP fast reroute: Loop-free alternates: RFC 5286[S]. Reston, USA: Internet Society (ISOC), 2008. |
| [9] | LEE S, YU Y Z, NELAKUDITI S, et al. Proactive vs reactive approaches to failure resilient routing[C]//Proceedings of the Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Hong Kong, China, 2004: 1-9. |
| [10] | ENYEDI G, SZILAGYI P, RéTVáRI G, et al. IP fast reroute: Lightweight Not-Via without additional addresses[C]//Proceedings of the 8th International IFIP-TC6 Networking Conference NETWORKING: International Conference on Research in Networking (INFOCOM). Rio de Janeiro, Brazil, 2009: 2771-2775. |
| [11] | SOMMERS J, BARFORD P, ERIKSSON B. On the prevalence and characteristics of MPLS deployments in the open Internet[C]//Proceedings of 2011 ACM SIGCOMM Conference on Internet Measurement Conference. Berlin, Germany, 2011: 445-462. |
| [12] | HAO F, KODIALAM M, LAKSHMAN T V. Optimizing restoration with segment routing[C]//Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). San Francisco, USA, 2016: 1-9. |
| [13] | CIANFRANI A, LISTANTI M, POLVERINI M. Incremental deployment of segment routing into an ISP network:A traffic engineering perspective[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 3146-3160. DOI:10.1109/TNET.2017.2731419 |
| [14] | HARTERT R, VISSICCHIO S, SCHAUS P. A declarative and expressive approach to control forwarding paths in carrier-grade networks[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(5): 15-28. DOI:10.1145/2829988 |
| [15] | MORENO E, BEGHELLI A, CUGINI F. Traffic engineering in segment routing networks[J]. Computer Networks, 2017, 114: 23-31. DOI:10.1016/j.comnet.2017.01.006 |
