Problem statement

4.BACKUP PATH PROTECTION ALGORITHM:- 

Problem Formulation: 

The multiple next-hops found by MNP can be utilized to detour around failed 

links. However, there is no guarantee that such backup next-hops can always be 

found, and thus the protection capability of MNP is limited (so do the other 

cooperationfree mechanisms). To further improve the network availability, we 

propose backup path protection (BPP) to find backup paths when MNP fails to 

do so. Since forwarding along such paths needs additional cooperation/signaling 

mechanisms, we want to utilize them as little as possible. Given a network 

---

 

G(V,E) and the set of next-hops computed by MNP, our objective is to find a 

set of links and the corresponding backup paths, such that the network 

availability requirement (A(G) ≥ R, where R is a parameter chosen by network 

designers or operators) can be satisfied, while the number of such links is 

minimized. 

Algorithm: 

Algorithm 3 illustrates the framework of BPP.  

 

---

 

 

 

5.CONCLUSION 

 Traditional intra-domain routing protocols react to network failures by globally 

exchanging link state advertisements and recalculating routing table. This 

mechanism will greatly increase the convergence time, resulting in large 

number of packets are discarded when network failures occur. Therefore, lots of 

routing protection schemes have been proposed to enhance network availability 

to support mission-critical and real-time applications in the internet. However, 

all of the aforementioned algorithms cannot strike a good balance between the 

implementation of efficiency and network availability. Unlike the above works, 

however, our main concerns are computational efficiency and network 

availability, as these are critical for the algorithm. Therefore, we presented HLP 

as a novel link protection scheme to achieve high network availability for link-

state routing networks. We described how HLP improves network availability 

by combining MNP-e and BPP. HLP first computes multiple nexthops for 

source-destination pairs, then selects a minimum number of links to protect, so 

that it can meet network availability requirement without inducing significant 

overhead. Evaluation results on real and synthetic networks show that HLP can 

provide high network availability with low overhead. We believe networks can 

be made more efficient and reliable by adopting this mechanism 

 

---

 

References: - 

1.)J. Zheng, H. Xu, X. Zhu, G. Chen, and Y. Geng, “Sentinel: Failure recovery 

in centralized traffic engineering,” IEEE/ACM Trans. Netw., vol. 27, no. 5, pp. 

1859–1872, 2019. 

 2.) S. Wang, H. Xu, L. Huang, X. Yang, and J. Liu, “Fast recovery for single 

link failure with segment routing in SDNs,” in Proc. IEEE 

HPCC/SmartCity/DSS, Aug. 2019, pp. 2013–2018. 

3

.) https://ieeexplore.ieee.org/document/9042897

 

4.)

https://ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&que

ryText=computer%20network