Multipath routing and dual link failure recovery in IP networks using three link-independent trees

We develop an approach for disjoint multipath routing and fast recovery in IP networks that guarantees recovery from arbitrary two link failures. We employ three link-independent trees, referred to as red, blue, and green trees, rooted at every destination. The path from a source to the destination on the trees are mutually link-disjoint. The routing of packets is based on the destination address and the input interface over which the packet was received. We discuss different ways of employing the three link-independent trees for multipath routing and/or failure recovery. If the trees are employed exclusively for multipath routing, then no packet overhead is required. If the trees are employed for failure recovery, then the overhead bits will range from 0 to 2 bits depending on the flexibility sought in routing. We evaluate the performance of the trees in fast recovery by comparing the path lengths provided under single and dual link failures with an earlier approach based on tunneling.