Open Access

ARTICLE

Efficient Routing Protection Algorithm in Large-Scale Networks

Haijun Geng^1,2,*, Han Zhang³, Yangyang Zhang⁴

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:

Computers, Materials & Continua 2021, 66(2), 1733-1744. https://doi.org/10.32604/cmc.2020.013355

Received 04 August 2020; Accepted 20 September 2020; Issue published 26 November 2020

Abstract

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.

---

Keywords

---