基于SRv6的域内路由保护方案研究

doi:10.3778/j.issn.1002-8331.2210-0463

摘要/Abstract

摘要： 网络故障导致大量的数据包丢失，并且严重影响网络性能，如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。目前，比较有效的方法是互联网部署的开放式最短路径优先（open shortest path first， OSPF）和中间系统到中间系统（intermediate system-to-intermediate system，IS-IS），通过动态路由协议解决网络故障，但是在协议动态收敛的过程中仍会有大量的报文被丢弃。因此，路由器厂商广泛采用了性能更好的路由保护方法来克服网络故障，然而，已有的路由保护方案普遍存在实现复杂度较高或者故障保护率偏低情况。针对上述问题，在SRv6实现了网络可编程性的基础上，提出一种基于SRv6的域内路由保护方案（research on intra-domain routing protection scheme based on SRv6，RPSRv6），方案首先提出了备份路径的计算规则，并根据备份路径计算规则在生成的增量最短路径树上，为所有受链路故障影响的源目的结点对计算备份路径，在此基础上，提出了Segment List的计算规则，即计算出Segment List中SID的值与个数。在计算备份路径的过程中，每个受故障影响的结点和其他结点最多被访问一次，因此RPSRv6的时间复杂度具有较好的表现。实验结果表明，与已有的实现DC（downstream criterion）规则和U-Turn算法相比较，RPSRv6算法在故障保护率和路径拉伸度两个度量指标具有更好的实验效果，达到了100%的故障保护率并且在路径拉伸度方面达到了最优路径。

关键词: SRv6, 域内路由, 路由保护, 网络故障, 路由可用性, 增量最短路径树

Abstract: Network failures cause a large number of packet losses and seriously affect network performance. How to deal with network failures efficiently and quickly is the basic requirement and main task of designing routing protocols. Currently, the most effective methods for Internet deployment are open shortest path first (OSPF) and intermediate system-to-intermediate system (IS-IS). Network faults are resolved by dynamic routing protocols, but a large number of packets are still discarded during the dynamic convergence of protocols. Therefore, router manufacturers widely adopt the route protection method with better performance to overcome network faults. However, the existing route protection schemes generally have high implementation complexity or low fault protection rate. Aiming at the above problems, this paper realizes the network programmability based on SRv6. In this paper, a research on intra-domain routing protection scheme based on SRv6 (RPSRv6) is proposed. Firstly, the calculation rules of backup paths are proposed. According to the backup path calculation rule, the backup path is calculated for all pairs of source and destination nodes affected by link failure in the incremental shortest path tree generated. On this basis, the calculation rule of Segment List is proposed, that is, the value and number of SIDs in the Segment List are calculated. In the process of calculating the backup path, each node affected by the fault and other nodes can be accessed at most once, so the time complexity of RPSRv6 has good performance. The experimental results show that compared with existing DC (downstream criterion) rules and U-Turn algorithms, RPSRv6 algorithm has better experimental results in fault protection rate and path stretch, reaching 100% fault protection rate and the optimal path in path stretch.

Key words: SRv6, intradomain routing, routing protection, network failure, routing availability, incremental shortest path tree

耿海军, 张琪栋. 基于SRv6的域内路由保护方案研究[J]. 计算机工程与应用, 2024, 60(6): 293-300.

GENG Haijun, ZHANG Qidong. Research on Intra-Domain Routing Protection Scheme Based on SRv6[J]. Computer Engineering and Applications, 2024, 60(6): 293-300.

参考文献

[1] GOPALAN A, RAMASUBRAMANIAN S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees[J]. IEEE/ACM Transactions on Networking, 2018, 24 (3): 1336-1349.
[2] SINGH V, BHARTI A K, CHANDRA N. Edge computing: a soul to internet of things (IoT) data[M]//Artificial intelligence and machine learning for EDGE computing. New York: Academic Press, 2022: 355-372.
[3] SHUKLA S, HASSAN M, TRAN D C, et al. Improving latency in internet-of-things and cloud computing for real-time data transmission: a systematic literature review (SLR)[J]. Cluster Computing, 2021, 26(1): 1-24.
[4] TAPOLCAI J, RETVARI G, BABARCZI P, et al. Scalable and efficient multipath routing: complexity and algorithms[C]//2015 IEEE 23rd International Conference on Network Protocols (ICNP), San Francisco, USA, Nov 10-13, 2015. Piscataway: IEEE, 2016: 1092-1648.
[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 International Symposium on Quality of Service, Alberta, Canada, Jun 4-6, 2018. Piscataway: IEEE, 2018:1-10.
[6] MANI S, NENE M J. Data loss prevention due to link-flapping using software defined networking[C]//2021 6th International Conference for Convergence in Technology (I2CT), Maharashtra, India, April 2-4, 2021. Piscataway: IEEE, 2021:1-5.
[7] BOGLE J, BHATIA N, GHOBADI M, et al. Teavar: striking the right utilization-availability balance in WAN traffic engineering[C]//Proceedings of ACM Special Interest Group on Data Communication, Beijing, China, Aug 19-23, 2019. New York: ACM Press, 2019: 29-43.
[8] QIU K, ZHAO J, WANG X, et al. Efficient recovery path computation for fast reroute in large-scale software defined networks[J].IEEE Journal on Selected Areas in Communications, 2019, 37(8): 1755-1768.
[9] 耿海军, 施新刚, 王之梁, 等. 基于最小路径交叉度的域内路由保护方案[J].软件学报, 2020, 31(5):1536-1548.
GENG H J, SHI X G, WANG Z L, et al. Intra-domain routing protection scheme based on minimum intersection paths[J]. Journal of Software, 2020, 31(5):1536-1548.
[10] JIANG J F, HAN G J. Routing protocols for unmanned aerial vehicles[J]. IEEE Communications Magazine, 2018, 56(1):58-63.
[11] SCHNEIDER K, ZHANG B, BENMOHAMED L. Hop-by-hop multipath routing: choosing the right next hop set[C]//IEEE 2020 International Conference on Computer Communications, Jul 6-9, 2020. Piscataway: IEEE, 2020: 2273-2282.
[12] MOY J. OSPF version 2: RFC 2328[S/OL]. IETF STD 54 (1998-04)[2022-06-12]. https://www.rfc-editor.org/rfc/rfc2178.html.
[13] SHAND M, BRYANT S. IP fast reroute framework: RFC 5714[S/OL]. Fremont: IETF (2010-01) [2022-08-02]. https://tools.ietf.org/html/rfc5714.
[14] ATLAS A.U-turn alternates for IP/LDP fast-reroute[S]. USA: ISOC Internet Society, 2006.
[15] YANG X W, WETHERALL D. Source selectable path diversity via routing deflections[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4):159-170.
[16] CEVHER S, ULUTAS M, ALTUN S, et al. Multiple routing configurations for fast re-route in software defined networks[C]//2016 24th Signal Processing and Communication Application Conference (SIU), Zonguldak, Turkey, May 16-19, 2016. Piscataway: IEEE, 2016: 993-996.
[17] FILSFILS C, PREVIDI S, GINSBERG L, et al. Segment routing architecture: RFC 8402[S]. IETF, July 2018.
[18] CHENG W, LI Z, LI C, et al. Generalized SRv6 network programming for SRv6 compression[S]. IETF Datatracker, 2020.
[19] FILSFILS C, NAINAR N K, PIGNATARO C, et al. The segment routing architecture[C]//IEEE Global Communications Conference, San Diego, USA Dec 6-10, 2015. Piscataway: IEEE, 2015.
[20] LI Z, HU Z, LI C. SRv6 network programming: ushering in a new era of IP networks[M]. Boca Raton: CRC Press, 2021.
[21] XU A, BI J, ZHANG B B, et al. Failure inference for shortening traffic detours [C]//IEEE/ACM International Symposium on Quality of Service, Vilanova i la Geltrú, Spain, Jun 14-16, 2017. Piscataway: IEEE, 2017:1-10.