@article{67ddcbdb4cda4591ba0ed56d776cc249,
title = "Linear time distributed construction of colored trees for disjoint multipath routing",
abstract = "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 data over the multiple paths, the latter being particularly significant in datagram networks. One approach to reduce the number of routing table entries for disjoint 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.",
keywords = "Colored trees, Disjoint routing, Multipath routing, Redundant trees",
author = "Srinivasan Ramasubramanian and Mithun Harkara and Marwan Krunz",
note = "Funding Information: The research developed in this paper is supported by National Science Foundation under Grants 0325979, 0435490, and EEC-0333046. Parts of the research developed in this paper has appeared in the IFIP Networking Conference [1] . Funding Information: Marwan M. Krunz received the Ph.D. degree in electrical engineering from Michigan State University, East Lansing, Michigan, in 1995. From 1995 to 1997, he was a Postdoctoral Research Associate with the Department of Computer Science and the Institute for Advanced Computer Studies (UMIACS) at the University of Maryland, College Park. In January 1997, he joined the University of Arizona, where he is currently an Associate Professor of Electrical and Computer Engineering. His research is in the field of packet networks (both wireline and wireless), with particular interest in its performance evaluation, protocol design, and traffic management aspects. Currently, his group is involved in projects related to power and rate control for medium access protocols in wireless ad hoc networks, routing protocols for ad hoc networks, quality-of-service routing (including path computation, stateless routing, topology aggregation, and scalable state dissemination), media streaming over wireless networks, optical packet networks, caching and prefetching for the WWW, traffic modeling, and adaptive packet encapsulation (see Broadband Networking Laboratory for details). Previously, he worked on projects related to packet scheduling, quality of service provisioning, bandwidth allocation, video-traffic modeling, and video-on-demand systems. He has published more than 80 journal articles and refereed conference papers in these areas (see Publications for details). He is a recipient of the National Science Foundation CAREER Award (1998–2002). He served as a TPC chair for the IEEE INFOCOM 2004 Conference (Hong Kong, March 7–11, 2004) and for the 9th Hot Interconnects Symposium (Stanford University, August 2001). He also served on the executive committees of various international conferences, including INFOCOM 2003 (publicity chair), MobiCom 2002 (publicity chair), INFOCOM 2001 (tutorials chair), INFOCOM + 99 (panels chair), etc. He served and continues to serve on the technical program committees of many international conferences. He currently serves on the editorial board for the IEEE/ACM Transactions on Networking and the Computer Communications Journal. Previously, he served on the editorial board for IEEE Communications. He was a guest co-editor for a special issue on Hot Interconnects (IEEE Micro, Jan. 2002) and of a Feature Topic on QoS Routing (IEEE Communications, June 2002). He frequently serves as a panelist for NSF proposals. He consults for several corporations in the telecommunications industry. He is a Senior Member of the IEEE.",
year = "2007",
month = jul,
day = "11",
doi = "10.1016/j.comnet.2006.11.029",
language = "English (US)",
volume = "51",
pages = "2854--2866",
journal = "Computer Networks",
issn = "1389-1286",
publisher = "Elsevier B.V.",
number = "10",
}