Maintaining Colored Trees for Disjoint Multipath Routing Under Node Failures

Colored Trees (CTs) is an efficient approach to route packets along link- or node-disjoint paths in packet-switched networks. In this approach, two trees, namely red and blue, are constructed rooted at a drain such that the path from any node to the drain is link- or node-disjoint. For applications where both the trees are used simultaneously, it is critical to maintain the trees after link or node failures. To this end, this paper develops an algorithm, referred to as SimCT that efficiently constructs and maintains colored trees under failures using only local information.