Single node failure routing protection algorithm based on segment routing
GENG Haijun1, LIU Jieqi1, YIN Xia2
1. 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.
[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. [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. [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. [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. [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. [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. [15] MORENO E, BEGHELLI A, CUGINI F. Traffic engineering in segment routing networks[J]. Computer Networks, 2017, 114:23-31.
2018, Vol. 58 
