Date Added: Feb 2010
In this paper, the authors introduce the concept of Independent Directed Acyclic Graphs (IDAGs) to achieve resilient multipath routing. Link-independent (Node-independent) DAGs satisfy the property that any path from a source to the root on one DAG is link-disjoint (node-disjoint) with any path from the source to the root on the other DAG. Given a network, they develop polynomial time algorithms to compute link-independent and node-independent DAGs. The algorithm developed in this paper: achieves multipath routing; guarantees recovery from single link failure; utilizes all possible edges; and achieves all these with at most one bit per packet as overhead when routing is based on destination address and incoming link.