Problem statement

Basic Architecture: 

The main objective of our hybrid link protection (HLP) scheme is to explore 

path diversity and pre-compute backup paths, so that when link failures happen, 

a working path can be instantly activated to avert these links. HLP is 

implemented in two stages. Stage one computes multiple next-hops for each 

destination based on LFC, where loop-freeness of the induced forwarding path 

can be guaranteed. 

 

---

 

3.EFFICIENT LOOP-FREE CRITERION BASED SCHEMES:- 

Theorem : Given any two nodes u and v (u, v 6= c) in the shortest path tree Tc, 

let Dc(v, u) = Cc(u) − Cc(Bc(u)) + L(u, v). If Dc(v, u) < CBc(u)(c) + Cc(v). (5) 

We say u can contribute to v, and add Bc(u) to Nc(v). If packets destined to v 

are always forwarded by c to the next-hops in Nc(v), the resulting paths are 

loop-free and will reach the destination. Proof: CBc(u)(v) is the cost from Bc(u) 

to v in the SPT TBc(u) , and is also the lowest cost from Bc(u) to v in the 

network. Since Cc(u) − Cc(Bc(u)) + L(u, v) is the cost of a path from Bc(u) to u 

to v, it must be no smaller than CBc(u)(v), so CBc(u)(v) ≤ 

Cc(u)−Cc(Bc(u))+L(u, v) < CBc(u)(c)+Cc(v). This satisfies (4) in Theorem 1, 

and thus the statement is true.  

✷ The condition in (5) is a little more strict than that in (4), however, checking 

whether it is satisfied by two nodes u and v can be accomplished in a much 

simpler way as follows. When constructing the SPT Tc, whenever we insert a 

new node u, we only need to verify (5) against a node v that is u’s neighbor and 

is already in Tc, since if u and v are not neighbors, L(u, v) = ∞ and it is not 

possible to satisfy (5). In this way, we can compute Nc(v) for any node v by 

constructing a single SPT, which is much faster than other multipath algorithms.