13-11-2012, 02:15 PM
Independent Directed Acyclic Graphs for Resilient Multipath Routing
ABSTRACT
In order to achieve resilient multipath routing, we
introduce the concept of independent directed acyclic
graphs (IDAGs) in this paper. Link-independent (nodeindependent)
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, we develop
polynomial- time algorithms to compute link-independent
and node-independent DAGs. The algorithm developed in
this paper: 1) provides multipath routing; 2) utilizes all
possible edges; 3) guarantees recovery from single link
failure; and 4) achieves all these with at most one bit per
packet as overhead when routing is based on destination
address and incoming edge. We show the effectiveness of
the proposed IDAGs approach by comparing key
performance indices to that of the independent trees and
multiple pairs of independent trees techniques through
extensive simulations.