An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph

Geng Haijun; Meng Zhuo; Yao Shanshan; Yang Jing; Chi Haotian; Yin Xia

doi:10.7544/issn1000-1239.202220914

Journal of Computer Research and Development > 2024 > 61(2): 529-538. > DOI: 10.7544/issn1000-1239.202220914

Geng Haijun, Meng Zhuo, Yao Shanshan, Yang Jing, Chi Haotian, Yin Xia. An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph[J]. Journal of Computer Research and Development, 2024, 61(2): 529-538. DOI: 10.7544/issn1000-1239.202220914

Citation:

PDF (1138 KB)

An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph

Geng Haijun^{1, 2, 3,},
Meng Zhuo^{1, 3},
Yao Shanshan^{1, 3},
Yang Jing^{2, 3},
Chi Haotian²,
Yin Xia^4, ,

1.
School of Computer and Information Technology, Shanxi University, Taiyuan 030006
2.
School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
3.
Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006
4.
Department of Computer Science and Technology, Tsinghua University, Beijing 100084

Funds: This work was supported by the Fundamental Research Program of Shanxi Province (20210302123444, 20210302123455), the Scientific and Technological Innovation Programs of Higher Education Institutions in Shanxi province (2022L002), the Ministry of Education (CN) Industry-University-Research Innovation Fundation (2021FNA02009), the National Natural Science Foundation of China (61702315, 61906115), the Key Research and Development Program of Shanxi Province (201903D421003, 202202020101004), and the National Key Research and Development Program of China( 2018YFB1800401).

More Information

Author Bio:
Geng Haijun: born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

Meng Zhuo: born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

Yao Shanshan: born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

Yang Jing: born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

Chi Haotian: born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

Yin Xia: born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing
Received Date: November 02, 2022
Revised Date: April 13, 2023
Available Online: November 13, 2023

Graphical Abstract

Abstract

Abstract

Currently, intra-domain routing protocols which are deployed on the Internet respond to network failures through a global convergence mechanism. In the process of routing convergence, a large number of data packets will be discarded, leading to network interruption. The industry proposes to use routing protection methods to solve the above problem. However, the existing routing protection methods have the following four problems: 1) they cannot cope with all possible single failures in the network; 2) they need the assistance of additional auxiliary mechanisms; 3) they do not support incremental deployment; 4) each node stores multiple backup next hops for each destination, increasing storage and computation costs. We propose an intra-domain routing protection algorithm based on forwarding graph (RPBFG) to solve the above four problems of existing routing protection algorithms. We first establish a routing protection model with the goal of maximizing the failure protection ratio and the constraint that the forwarding graph contains the reverse shortest path tree; then a genetic algorithm is proposed to construct a forwarding graph that satisfies the above goal; finally, the backup next hop of all nodes arriving at the destination node is calculated according to the constructed forwarding graph. We compare the performance of RPBFG, NPC, U-turn, MARA-MA and MARA-SPE in 11 real topologies, including failure protection ratio and path stretch. The experimental results show that RPBFG can deal with all possible single failures in the network, and that is to say the failure protection ratio of RPBFG is 100%, while the average failure protection ratio of NPC, U-turn, MARA-MA and MARA-SPE is 45.05%, 74.53%, 89.78% and 91.24% respectively. In the aspect of path stretch, RPBFG decreased by 0.11%, 0.72%, 37.79% and 36.26% respectively compared with NPC, U-turn, MARA-MA and MARA-SPE. The research results will help to promote the progress of Internet service providers in deploying intra-domain routing protection schemes in real networks.
- routing protection,
- network failure,
- failure protection ratio,
- path stretch,
- directed acyclic graph,
- forwarding graph

FullText(HTML)

References (30)

References

[1]	Moy J. RFC 2328 OSPF Version 2 [S/OL]. The Internet Engineering Task Force, 1998[2022-09-06].https://www.ietf.org/rfc/rfc2328
[2]	David O. RFC 1142 OSI IS-IS Intra-domain Routing Protocol [S/OL]. The Internet Engineering Task Force, 1990[2022-08-12].https://www.ietf.org/rfc/rfc1142
[3]	Duijn I V, Jensen P G, Jensen J S, et al. Automata-theoretic approach to verification of MPLS networks under link failures[J]. IEEE/ACM Transactions on Networking, 2022, 30(2): 766−781 doi: 10.1109/TNET.2021.3126572
[4]	Foerster K T, Kamisiski A, Pignolet Y A, et al. Improved fast rerouting using postprocessing[J]. IEEE Transactions on Dependable and Secure Computing, 2022, 19(1): 537−550 doi: 10.1109/TDSC.2020.2998019
[5]	Yang Ze, Yeung K L. SDN candidate selection in hybrid IP/SDN networks for single link failure protection[J]. IEEE/ACM Transactions on Networking, 2020, 28(1): 312−321 doi: 10.1109/TNET.2019.2959588
[6]	Geng Haijun, Zhang Han, Shi Xingang, et al. Efficient computation of loop-free alternates[J]. Journal of Network and Computer Applications, 2020, 151: 1−12
[7]	Jia Xuya, Li Dan, Zhu Jing, et al. Metro: An efficient traffic fast rerouting scheme with low overhead[J]. IEEE/ACM Transactions on Networking, 2019, 27(5): 2015−2027 doi: 10.1109/TNET.2019.2935382
[8]	Borokhovich M, Pignolet Y A, Schmid S, et al. Load-optimal local fast rerouting for dense networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2583−2597 doi: 10.1109/TNET.2018.2871089
[9]	Yang Yuan, Xu Minwei, Li Qi. Fast rerouting against multi-link failures without topology constraint[J]. IEEE/ACM Transactions on Networking, 2018, 26(1): 384−397 doi: 10.1109/TNET.2017.2780852
[10]	Shukla A, Foerster K T. Shortcutting fast failover routes in the data plane [C] //Proc of the 16th Symp on Architectures for Networking and Communications Systems. Piscataway, NJ: IEEE, 2021: 15−22
[11]	Atlas A, Zinin A. RFC 5286 Basic Specification for IP Fast Reroute: Loop-free Alternates [S/OL]. The Internet Engineering Task Force, 2008[2022-10-08].https://www.ietf.org/rfc/rfc5286
[12]	耿海军,施新刚,王之梁,等. 基于最小路径交叉度的域内路由保护方案[J]. 软件学报,2020,31(5):1536−1548 Geng Haijun, Shi Xingang, Wang Zhiliang, et al. Intra-domain routing protection scheme based on minimum intersection paths[J]. Journal of Software, 2020, 31(5): 1536−1548 (in Chinese)
[13]	Yang Xiaowei, Wetherall D. Source selectable path diversity via routing deflections[J]. Computer Communication Review, 2006, 36(4): 159−170 doi: 10.1145/1151659.1159933
[14]	Ohara Y , Imahori S , Meter R V. MARA: Maximum alternative routing algorithm[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 298−306
[15]	Vo H Q, Lysne O, Kvalbein A. Routing with Joker links for maximized robustness[C/OL] //Proc of the 12th Int Conf on IFIP Networking Conf. Piscataway, NJ: IEEE, 2013[202-10-17].https://ieeexplore.ieee.org/document/6663494
[16]	Schneider K, Zhang Beichuang, Benmohamed L. Hop-by-hop multipath routing: Choosing the right nexthop set[C] //Proc of the 39th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2020: 2273−2282
[17]	Menth M, Hartmann M, Martin R, et al. Loop-free alternates and not-via addresses: A proper combination for IP fast reroute?[J]. Computer Networks, 2010, 54(8): 1300−1315 doi: 10.1016/j.comnet.2009.10.020
[18]	Anbiah A, Sivalingam K M. Efficient failure recovery techniques for segment-routed networks[J]. Computer Communications, 2022, 182: 1−12 doi: 10.1016/j.comcom.2021.10.033
[19]	Markopoulou A, Iannaccone G, Bhattacharyya S, et al. Characterization of failures in an operational IP backbone network[J]. IEEE/ACM Transactions on Networking, 2008, 16(4): 749−762 doi: 10.1109/TNET.2007.902727
[20]	Chiesa M, Kamisinski A, Rak J, et al. A survey of fast-recovery mechanisms in packet-switched networks[J]. IEEE Communications Surveys and Tutorials, 2021, 23(2): 1253−1301 doi: 10.1109/COMST.2021.3063980
[21]	Kwong K W, Gao Lixin, Guérin R. On the feasibility and efficacy of protection routing in IP networks[J]. IEEE/ACM Transactions on Networking, 2011, 19(5): 1543−1556 doi: 10.1109/TNET.2011.2123916
[22]	Rétvári G, Csikor L, Tapolcai J, et al. Optimizing IGP link costs for improving IP-level resilience with loop-free alternates[J]. Computer Communications, 2013, 36(6): 645−655 doi: 10.1016/j.comcom.2012.09.004
[23]	Rétvári G, Tapolcai J, Enyedi G, et al. IP fast reroute: Loop free alternates revisited[C] //Proc of the 30th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2011: 2948−2956
[24]	Francois P, Bonaventure O. An evaluation of IP-based fast reroute techniques[C] //Proc of the ACM Conf on Emerging Network Experiment and Technology. New York: ACM, 2005: 244−245
[25]	Enyedi G, Szilágyi P, Rétvári G, et al. IP fast reroute: Lightweight not-via without additional addresses[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 2771−2775
[26]	Zheng Jiaqi, Xu Hong, Zhu Xiaojun, et al. We've got you covered: Failure recovery with backup tunnels in traffic engineering[C/OL] //Proc of the 24th Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2016[2022-09-18]. https://ieeexplore.ieee.org/document/7784449
[27]	Kvalbein A, Hansen A F, Čičić T, et al. Fast IP network recovery using multiple routing configurations[C] //Proc of the 25th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1677−1687
[28]	Lakshminarayanan K, Caesar M, Rangan M, et al. Achieving convergence-free routing using failure-carrying packets[J]. Computer Communication Review, 2007, 37(4): 241−252 doi: 10.1145/1282427.1282408
[29]	周明华,汪国昭. 基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合[J]. 计算机研究与发展,2005,42(1):134−143 doi: 10.1360/crad20050118 Zhou Minghua, Wang Guozhao. Genetic algorithm based least square fitting of B-spline and Bézier curves[J]. Journal of Computer Research and Development, 2005, 42(1): 134−143 (in Chinese) doi: 10.1360/crad20050118
[30]	University of Adelaide. The Internet topology zoo [EB/OL]. [2022-09-07]. http://www.topology-zoo.org/

[1]	Li Junwei, Liu Quan, Huang Zhigang, Xu Yapeng. A Diversity-Enriched Option-Critic Algorithm with Interest Functions[J]. Journal of Computer Research and Development, 2024, 61(12): 3108-3120. DOI: 10.7544/issn1000-1239.202220970
[2]	Zhao Rongmei, Sun Siyu, Yan Fanli, Peng Jian, Ju Shenggen. Multi-Interest Aware Sequential Recommender System Based on Contrastive Learning[J]. Journal of Computer Research and Development, 2024, 61(7): 1730-1740. DOI: 10.7544/issn1000-1239.202330622
[3]	Zhu Haiping, Wang Ziyu, Zhao Chengcheng, Chen Yan, Liu Jun, Tian Feng. Learning Resource Recommendation Method Based on Spatio-Temporal Multi-Granularity Interest Modeling[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440249
[4]	Liu Haijiao, Ma Huifang, Zhao Qiqi, Li Zhixin. Target Community Detection with User Interest Preferences and Influence[J]. Journal of Computer Research and Development, 2021, 58(1): 70-82. DOI: 10.7544/issn1000-1239.2021.20190775
[5]	Guo Kaihong, Han Hailong. Personalized Recommendation Model Based on Quantifier Induced by Preference[J]. Journal of Computer Research and Development, 2020, 57(1): 124-135. DOI: 10.7544/issn1000-1239.2020.20190166
[6]	Gao Ling, Gao Quanli, Wang Hai, Wang Wei, Yang Kang. A Preference Prediction Method Based on the Optimization of Basic Similarity Space Distribution[J]. Journal of Computer Research and Development, 2018, 55(5): 977-985. DOI: 10.7544/issn1000-1239.2018.20160924
[7]	Guo Chi, Wang Lina, Guan Yiping, Zhang Xiaoying. A Network Immunization Strategy Based on Dynamic Preference Scan[J]. Journal of Computer Research and Development, 2012, 49(4): 717-724.
[8]	Zou Bowei, Zhang Yu, Fan Jili, Zheng Wei, and Liu Ting. Research on Personalized Information Retrieval Based on User’s New Interest Detection[J]. Journal of Computer Research and Development, 2009, 46(9): 1594-1600.
[9]	Wang Zhenzhen, Xing Hancheng, and Chen Hanwu. On a Preference System of Agent and Its Construction[J]. Journal of Computer Research and Development, 2009, 46(2): 253-260.
[10]	Wu Jing, Zhang Pin, Luo Xin, Sheng Hao, and Xiong Zhang. Mining Interests and Navigation Patterns in Personalization on Portal[J]. Journal of Computer Research and Development, 2007, 44(8): 1284-1292.