With an increasing urgent demand for fast recovery routing mechanisms in largescale 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 singlelink 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 largescale networks. Therefore, this study proposes an efficient intradomain routing protection algorithm (ERPA) in largescale 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.
In recent years, the Internet has become a widely used platform for various network applications. With the rapid development of the Internet, several realtime and missioncritical applications, such as VoIP and video and online games, are deployed [
To improve the availability of intradomain routing, the routing protection scheme is usually applied in the academia and industry [
In this work, we focus on the first type of scheme. We also confine our work in linkstate routing networks. Most ISPs prefer linkstate routing instead of distancevector routing in their intradomain system because of its merits, such as fast convergence and good support for metrics. Layer2 networks also incorporate linkstate routing into their network architecture, such as the standardized transparent interconnection of lots of links. Furthermore, during topology changes caused by link or node failure, millisecondlevel fast convergence, which poses stringent performance requirement to route computation, is preferred.
Among all of the hopbyhop routing protection schemes, downstream path criterion (DC) [
However, the deployment of DC in real ISP networks is difficult because of the substantial computational overhead. Therefore, an efficient DCbased algorithm is required to be easily deployed in ISP. Thus, a lightweight IPFRR scheme is desired to provide costefficient routing protection effectively. Therefore, this study investigates the application of incremental shortest path first algorithm to reduce the computational overhead of the DC implementation. In particular, our contributions can be summarized as follows:
We propose an efficient intradomain routing protection algorithm (ERPA) in largescale networks.
Theoretical analysis indicates that the computation complexity of ERPA is less than that of constructing a shortest path tree (SPT).
Theoretical analysis indicates that ERPA can provide the same network availability as DC.
In terms of computation overhead and network availability, the theoretical analysis and experimental results are consistent.
Nowadays, network failures have become routine events rather than exceptions [
In this section, we will first show the network model and then describe the key problems that need to be solved in this work. For ease of reading, some of the symbols used in this paper are summarized in
Network topology  
Neighbor set of 

Shortest path tree rooted at 

Descendants of 

Weight of link 

Shortest cost from 

Default nexthop from 

Backup nexthop set form 
The currently deployed intradomain routing protocols (e.g., OSPF and ISIS) only employ the shortest paths to forward packets. Thus, they need to reconverge when network component failures occur. The packets may be dropped because of invalid routing information. These protocols never exploit the inherent diversity of Internet topology and cannot handle network failure flexibly. Therefore, DC has been proposed to cope with all the singlelink failure scenarios. The DC can be expressed as follows:
To implement DC rule at node
Given a computing node
The time complexity of the algorithm is less than that of constructing a SPT.
It can provide the same network availability with DC.
ERPA will be discussed in detail to solve the above problem in this section. The problem can be presented to compute
Given that
We will use an example to explain
According to the above discussions, ERPA is proposed to compute the backup nexthop set that satisfies the DC rule. The inputs of ERPA include the network topology


1: 
2: 
3: 
4: employ iSPF to construct 
5: 
6: 
7: 
8: 
9: 
10: 
In this section, we will show the performance of the algorithm, including the time complexity and the number of backup nexthop computed by ERPA. Theorem 3 suggests that the computational complexity of ERPA is less than that of constructing a SPT. In Theorem 4, ERPA can compute all the backup nexthop sets that satisfy the DC Rule. We will describe Theorems 3 and 4 in detail and prove their correctness.
Considering
In this section, we will evaluate ERPA in terms of computation overhead and network availability. To indicate the performance of ERPA, we compare the results with TBFH, DMPA, and DC. All the algorithms are implemented on a PC (Intel i7, 3.7 GHz CPU, and 8G memory). All of the experimental results correspond to the average values of 15 random experiments. To truly reflect the link failure distribution, the failure probability of links in this paper adopts Weibull distribution
We conduct the simulations on a wide space of relevant topologies, including real, inferred, and synthetic ones. The real topology includes Abilene, USLD, ITALY, NJLATA, and TORONTO [
Topology Name  #Node  #Link 

Telstra  108  153 
Sprint  315  972 
Ebone  87  162 
Tiscali  161  328 
Exodus  79  147 
Abovenet  128  372 
Abilene  11  14 
USLD  28  45 
ITALY  21  36 
NJLATA  11  23 
TORONTO  25  55 
Model  N  HS  LS 

Waxman  20–200  1000  100 
m  NodePlacement  GrowthType  alpha 
2–25  Random  Incremental  0.15 
beta  BWDist  BwMinBwMax  model 
0.2  Constant  10.0–1024.0  Router 
Theoretical analysis has indicated that the time complexity of ERPA is less than that of constructing a SPT, which has a great advantage over DC, TBFH, and DMPA. To further verify computational performance, we make simulations on different types of topologies. In this section, we evaluate the computational overhead of different algorithms on three types of topologies to avoid the uncertain impact of factors on the algorithm’s performance. The computational overhead of an algorithm is defined as the ratio of computation time of the algorithm to that of constructing a SPT.
In this section, we will employ network availability as our main evaluation criterion to assess the reliability of the network. Network availability
where
According to the inclusion–exclusion principle,
where
Network  Network Availability (%)  

ERPA  DC  TBFH  DMPA  
Telstra  98.35  98.35  95.34  96.21 
Sprint  97.23  97.23  93.46  95.36 
Ebone  96.45  96.45  94.32  95.57 
Tiscali  98.23  98.23  95.43  96.46 
Exodus  92.34  92.34  86.45  89.45 
Abovenet  95.34  95.34  92.34  93.76 
Abilene  97.85  97.85  94.34  95.71 
USLD  91.35  91.35  85.49  87.37 
ITALY  92.84  92.84  86.39  88.28 
NJLATA  91.27  91.27  86.45  89.64 
TORONTO  90.65  90.65  85.86  88.29 
This study proposed an efficient scheme called ERPA to implement DCbased hopbyhop routing protection. The computation complexity of ERPA is irrespective of the degree of the calculating router and is less than a full SPT calculation. We simulate ERPA on numerous topologies in comparison with DC, DMPA, and TBFH. The theoretical and experimental results show that ERPA can reduce the computational overhead and can provide the same network availability as DC dramatically. We are convinced that our proposed scheme ERPA takes a big step toward actual deployment.