Vol.66, No.2, 2021, pp.1733-1744, doi:10.32604/cmc.2020.013355
Efficient Routing Protection Algorithm in Large-Scale Networks
  • Haijun Geng1,2,*, Han Zhang3, Yangyang Zhang4
1 School of Software Engineering, Shanxi University, Taiyuan, 030006, China
2 2Institute of Big Data Science and Industry, Shanxi University, Taiyuan, 030006, China
3 School of Cyber Space and Technology, Beihang University, Beijing, 100191, China
4 College of Engineering Northeastern University, Boston, 02115, USA
* Corresponding Author: Haijun Geng. Email:
Received 04 August 2020; Accepted 20 September 2020; Issue published 26 November 2020
With an increasing urgent demand for fast recovery routing mechanisms in large-scale networks, minimizing network disruption caused by network failure has become critical. However, a large number of relevant studies have shown that network failures occur on the Internet inevitably and frequently. The current routing protocols deployed on the Internet adopt the reconvergence mechanism to cope with network failures. During the reconvergence process, the packets may be lost because of inconsistent routing information, which reduces the network’s availability greatly and affects the Internet service provider’s (ISP’s) service quality and reputation seriously. Therefore, improving network availability has become an urgent problem. As such, the Internet Engineering Task Force suggests the use of downstream path criterion (DC) to address all single-link failure scenarios. However, existing methods for implementing DC schemes are time consuming, require a large amount of router CPU resources, and may deteriorate router capability. Thus, the computation overhead introduced by existing DC schemes is significant, especially in large-scale networks. Therefore, this study proposes an efficient intra-domain routing protection algorithm (ERPA) in large-scale networks. Theoretical analysis indicates that the time complexity of ERPA is less than that of constructing a shortest path tree. Experimental results show that ERPA can reduce the computation overhead significantly compared with the existing algorithms while offering the same network availability as DC.
Large-scale network; shortest path tree; time complexity; network failure; real-time and mission-critical applications
Cite This Article
H. Geng, H. Zhang and Y. Zhang, "Efficient routing protection algorithm in large-scale networks," Computers, Materials & Continua, vol. 66, no.2, pp. 1733–1744, 2021.
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.