收藏切换
An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph
收藏切换
Haijun Geng1, 2, 3, Zhuo Meng1, 3, Shanshan Yao1, 3, Jing Yang2, 3, Haotian Chi2, Xia Yin4, *
Journal of Computer Research and Development | 2024, 61(2) : 529 - 538
Less
收藏切换
Journal of Computer Research and Development | 2024, 61(2): 529-538
• Network Technology •
An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph
Full
Haijun Geng1, 2, 3, Zhuo Meng1, 3, Shanshan Yao1, 3, Jing Yang2, 3, Haotian Chi2, Xia Yin4, *
Affiliations
  • 1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
  • 2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
  • 3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006
  • 4Department of Computer Science and Technology, Tsinghua University, Beijing 100084
  • born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

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

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

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

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

    born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

About Author:

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

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

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

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

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

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

Published: 2024-02-02 doi: 10.7544/issn1000-1239.202220914
Outline
收藏切换

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
耿海军, 孟卓, 姚姗姗, 杨静, 池浩田, 尹霞. 一种基于转发图的域内路由保护算法. 计算机研究与发展, 2024 , 61 (2) : 529 -538 . DOI: 10.7544/issn1000-1239.202220914
Haijun Geng, Zhuo Meng, Shanshan Yao, Jing Yang, Haotian Chi, Xia Yin. 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
Year 2024 volume 61 Issue 2
83
39
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202220914
  • Receive Date:2022-11-03
  • Online Date:2026-11-17
  • Published:2024-02-02
Article Data
Affiliations
History
  • Received:2022-11-03
  • Revised:2023-04-14
Affiliations
    1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
    2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
    3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006
    4Department of Computer Science and Technology, Tsinghua University, Beijing 100084
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202220914
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT