A Novel Approach for Resilient Multipath Routing by Using Independent Directed Acyclic Graphs

Abstract

In this paper, we introduce the concept of Independent Directed Acyclic Graphs (IDAGs) to achieve resilient multipath routing. The algorithm developed in this paper: (1) achieves multipath routing; (2) guarantees recovery from single link failure. The multipath routing scheme consists of an algorithm to determine a set of multiple disjoint or partially disjoint paths and a mechanism for distributing traffic over a multipath route to reduce the traffic load on a congested link. Multipath routing is capable of aggregating the resources of multiple paths and reducing the blocking capabilities in QoS oriented networks, allowing data transfer at higher rate when compared to single path. To improve the failure resiliency without jeopardizing the routing stability, we propose a local rerouting based approach called failure insensitive routing. Under this approach, upon a link failure, adjacent router suppresses global updating and instead initiates local rerouting. We demonstrate that the proposed approach provides higher service availability than the existing routing schemes.