IP fast reroute: NotVia with early decapsulation

Network survivability is an important topic for the Internet. To improve the performance of the Internet during failure, IP Fast Reroute (IPFRR) mechanisms are proposed to establish backup routes for failure-affected packets. NotVia, a most prominent one, provides 100% protection coverage for single-node failures. However, it brings in nontrivial computing and memory pressure to routers with special NotVia addresses, in which only some are necessary for a specific router. Besides, the protection path of NotVia is 20% longer than the optimal path on average. In this paper, we propose early decapsulated NotVia (ED-NotVia) handling the aforementioned problems and thus making NotVia more practical. We first analyze the properties of necessary NotVia addresses to any specific node. Then we develop a heuristic Nec-NotVia Algorithm for a node to find the necessary NotVia addresses and compute routes for them, where unnecessary addresses are eliminated. Based on this elimination, early decapsulation is imported to optimize the protection path with marginal overhead. We evaluate our algorithm and demonstrate the effectiveness of ED-NotVia using topologies from Rocketfuel and Brite. The results show that 1) only 5% to 20% of SPT(Shortest Path Tree)-related NotVia addresses (1.23% to 6.41% of all the NotVia addresses) in an AS are necessary for a node; 2) by computing the routes for 15% to 40% SPT-related NotVia addresses, ED-NotVia provides 98% protection coverage; and 3) the protection path stretch ratio of ED-NotVia is only 1.03 on average as compared to 1.20 for NotVia.