Keep Forwarding: Towards k-link failure resilient routing

Abstract

Handling link failures is the fundamental task of routing schemes. Routing protocols based on link state (e.g., OSPF) require a global state advertisement and re-computation when link failure happens, and will cause inevitable delivery failures. To improve the routing resilience without introducing significant extra overhead, we propose a new routing approach, Keep Forwarding (KF) to achieve k-link failure resilience using inport-aware forwarding. KF is (i) flexible to handle multiple failures (or k-failure) with only small path stretch, (ii) efficient in recovery speed by instant and local lookup, (iii) bounded on memory requirement. Besides, the proposed approach is compatible with existing Internet protocols and routing infrastructures (e.g., requires no packet labeling or state recording), and the pre-computation has a linear temporal complexity. Experimental results on real ISP and datacenter networks reveal that KF guarantees near-optimal resilience (99.9%∼100% for single failure and over 99.7% for multiple failures), with the average path stretch increment less than 5%. © 2014 IEEE.