Packet-switched networks traditionally forward packets to a destination along one path.  However, forwarding packets over disjoint multiple paths helps achieve load balancing, congestion reduction, and robustness to link and node failures.  Implementation of disjoint multiple paths in packet-switched network poses two significant challenges: loop-free route computation and efficient forwarding of packets.

In this talk, we will introduce a novel approach called "colored trees" that addresses the above two challenges.  In this approach, two trees, namely red and blue, are constructed rooted at the destination such that the path from any node to the destination on the two trees are (link- or node-) disjoint.  We develop a distributed algorithm to construct the trees with only neighborhood information.  The message and time complexities of the algorithm are linear in the number of links and nodes, respectively.  We will extend the colored trees approach to dual-homing networks and sensor networks, where data may be transmitted to a few of many possible destinations.  In applications where a node may simultaneously transmit data on both the trees, the two trees will need to be reconstructed after a link or node failure.  We develop an algorithm to reconstruct the colored trees upon failures with only local repairs.

We will demonstrate that the colored tree construction and reconstruction algorithms developed outperform previously known techniques in the literature.  Finally, we will highlight possible extensions of the colored trees concept for tolerating multiple link/node failures.