AuthorsH. Vo, O. Lysne and A. Kvalbein
TitleIncreased Robustness With Interface Based Permutation Routing
AfilliationCommunication Systems
Project(s)No Simula project
Publication TypeTechnical reports
Year of Publication2012
PublisherSimula Research Laboratory

A prime objective of fault tolerant routing methods is the availability of multiple routing options at each hop. The methods that are currently implemented in IP networks, such as Equal-Cost Multi-Path (ECMP) and Loop Free Alternates (LFA), share the following four properties: First, they work with a hop-by-hop forwarding strategy optimized for the fault free case. Second, they do not require information associated with network faults included in the packet header. Third, they do not form forwarding loops, even under multiple failures in the network. Finally, they are compatible with standard link state routing protocols. However, ECMP and LFA give very poor fault coverage; in most cases fewer than 50% of primary next-hops are protected when using typical link weight settings. This paper presents a new routing method that combines the concept of permutations with interface based routing. Our method results in a routing strategy that strictly adheres to the four stated design properties. Through experiments we show that we protect more than 97% of the primary next-hops for all tested ISP networks.

Citation KeySimula.simula.1540