Efficient Routing Protection Algorithm in Large-Scale Networks  

作　　者：Haijun Geng Han Zhang Yangyang Zhang 

机构地区：[1]School of Software Engineering,Shanxi University,Taiyuan,030006,China [2]Institute 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

出　　处：《Computers, Materials & Continua》2021年第2期1733-1744,共12页计算机、材料和连续体（英文）

基　　金：the National Natural Science Foundation of China(No.61702315);the Key R&D program(international science and technology cooperation project)of Shanxi Province China(No.201903D421003);the National Key Research and Development Program of China(No.2018YFB1800401).

摘　　要：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 

分 类 号：TN9[电子电信—信息与通信工程]