Enhancing Shortest Path Routing for Resilience and Load Balancing

Download Now Date Added: Feb 2011
Format: PDF

This paper develops a new resilient multipath routing technique, referred to as SPT-DAG, that has the following characteristics: provides multipath routing over Directed Acyclic Graphs (DAG); the shortest path tree is guaranteed to be part of the DAG; and provides guaranteed recovery from single link failures. The authors develop a polynomial time algorithm to compute the SPT-DAG and a routing protocol to forward packets over the SPT-DAG using one overhead bit in the packet. They consider different load-balancing approaches for forwarding a packet when the packet has not encountered a failure.