Independent Directed Acyclic Graphs for Resilient Multipath Routing
In order to achieve resilient multipath routing the authors introduce the concept of Independent Directed Acyclic Graphs (IDAGs) in this paper. 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: provides multipath routing; utilizes all possible edges; guarantees recovery from single link failure; and achieves all these with at most one bit per packet as overhead when routing is based on destination address and incoming edge.