Abstract : The internet is playing an increasingly crucial role inboth personal and business activities. In addition, with the emer-gence of real-time, delay sensitive and mission-critical applications,stringent network availability requirement is put forward for inter-net service providers (ISPs). However, commonly deployed intra-domain link-state routing protocols react to link failures by glob-ally exchanging link state advertisements and recalculating rout-ing table, inevitably causing significant forwarding discontinuityafter a failure. Therefore, the loop-free criterion (LFC) approachhas been widely deployed by many ISPs for coping with the singlenetwork component failure scenario in large internet backbones.The success of LFC lies in its inherent simplicity, but this comesat the expense of letting certain failure scenarios go unprotected.To achieve full failure coverage with LFC without incurring signif-icant extra overhead, we propose a novel link protection scheme,hybrid link protection (HLP), to achieve failure resilient routing.Compared to previous schemes, HLP ensures high network avail-ability in a more efficient way. HLP is implemented in two stages.Stage one provides an efficient LFC based method (MNP-e). Thecomplexity of the algorithm is less than that of Dijkstra’s algo-rithm and can provide the similar network availability with LFC.Stage two provides backup path protection (BPP) based on MNP-e,where only a minimum number of links need to be protected, usingspecial paths and packet headers, to meet the network availabil-ity requirement. We evaluate these algorithms in a wide spread ofrelevant topologies, both real and synthetic, and the results revealthat HLP can achieve high network availability without introduc-ing conspicuous overhead. HLP not only needs around 10% time ofthat of full protection, but also provides full protection capabilitiesthat full protection provide.
Index terms : Incremental shortest path first, loop-free, multipath routing, network availability, network link failure