Distributed linear time construction of colored trees for disjoint multipath routing

Srinivasan Ramasubramanian, Mithun Harkara, Marwan Krunz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


Disjoint multipath routing (DMPR) is an effective strategy to achieve robustness in networks, where data is forwarded along multiple link- or node-disjoint paths. DMPR poses significant challenges in terms of obtaining loop-free multiple (disjoint) paths and effectively forwarding the data over the multiple paths, the latter being particularly significant in datagram networks. One approach to reduce the number of routing table entries for multipath forwarding is to construct two trees, namely red and blue, rooted at a destination node such that the paths from a source to the destination on the two trees are link/node-disjoint. This paper develops the first distributed algorithm for constructing the colored trees whose running time is linear in the number of links in the network. The paper also demonstrates the effectiveness of employing generalized low-point concept rather than traditional low-point concept in the DFS-tree to reduce the average path lengths on the colored trees.

Original languageEnglish (US)
Title of host publicationNetworking 2006 - Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Com. Syst. - 5th Int. IFIP-TC6 Netw. Conf. Proc.
EditorsThomas Plagemann, Burkhard Stiller, Cedric Westphal, Fernando Boavida, Edmundo Monteiro
Number of pages13
ISBN (Electronic)9783540341925
ISBN (Print)3540341927, 9783540341925
StatePublished - 2006
Event5th International IFIP-TC6 Networking Conference, Networking 2006 - Coimbra, Portugal
Duration: May 15 2006May 19 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3976 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th International IFIP-TC6 Networking Conference, Networking 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Distributed linear time construction of colored trees for disjoint multipath routing'. Together they form a unique fingerprint.

Cite this