projects 2012

Independent Directed Acyclic Graphs for Resilient Multipath Routing

Networking,   projects 2012 Feb

Technology Used: Java


In order to achieve resilient multipath routing we introduce the concept of Independent Directed Acyclic Graphs (IDAGs) in this study. 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, 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


The increasing use of streaming multimedia and voiceover- IP, precipitated by decreasing cost of handheld multimedia devices and netbooks, necessitates increased bandwidth provisioning and fast recovery from network failures. Thus, present day IP networks employ several different strategies for improved end-to-end bandwidth and load balancing (using multipath routing) and fast recovery from link and node failures (using fast rerouting strategies). Multipath routing is a promising routing scheme to accommodate these requirements by using multiple pairs of routes between a source and a destination.

Techniques developed for multipath routing are often based on employing multiple spanning trees or directed acyclic graphs (DAGs). When multiple routing tables are employed, a packet has to carry in its header the routing table to be used for forwarding. When the corresponding forwarding edge is not available, the packet needs to be dropped. This dropping is forced due to the potential looping of packets when transferred from one routing table to another. In the case of DAGs, computed by adding edges to the shortest path tree, one cannot guarantee that a single link failure will not disconnect one or more nodes from the destination.


Techniques developed for fast recovery from single link failures provide more than one forwarding edge to route a packet to a destination. The techniques may be classified depending on the nature in which the backup edges are employed. A method to augment any given tree rooted at a destination with “backup forwarding ports.” Whenever the default forwarding edge fails or a packet is received from the node attached to the default forwarding edge for the destination, the packets are re-routed on the backup ports.

Maximum Alternative Routing Algorithm (MARA) constructs a DAG that utilizes all edges in the network to increase the number of paths significantly.


Whenever the default forwarding edge fails or a packet is received from the node attached to the default forwarding edge for the destination, the packets are re-routed on the backup ports.

Maximum Alternative Routing Algorithm (MARA) does not provide a mechanism for backup forwarding when encountering a single link or node failure.


Two trees are constructed per destination node such that the paths from any node to the root on the two trees are disjoint. The trees may be constructed to obtain link-disjoint or node-disjoint paths if the network is two-edge or two-vertex connected, respectively. This approach is similar to those employing multiple routing tables, except that only two tables are required. Every packet may carry an extra bit in its header to indicate the tree to be used for routing. This overhead bit may be avoided by employing a routing based on the destination address and the incoming edge over which the packet was received, as every incoming edge will be present on exactly one of the trees.

The colored tree approach allows every node to split its traffic between the two trees, thus offering disjoint multipath routing. In addition, when a forwarding link on a tree fails, the packet may be switched to the other tree. A packet may be transferred from one tree to another at most once as the colored tree approach is guaranteed to recover from only a single link failure. The colored trees are also referred to as “independent trees” in the literature.



Load balancing

Bandwidth aggregation

Congestion reduction and


By admin

One thought on “Independent Directed Acyclic Graphs for Resilient Multipath Routing”

Leave a Reply

Your email address will not be published. Required fields are marked *