CE Seminar: Srinivasan Ramasubramanian, "Disjoint Multipath Routing in Packet-Switched Networks" Wed 12 March, 11:00-12:00 in ECE 530
|Date:||W 12 Mar 2008, 11:00-12:00 (note special time, and a Wednesday)|
|Title:||Disjoint Multipath Routing in Packet-Switched Networks|
Packet-switched networks traditionally forward packets to a destination along one path. However, forwarding packets over disjoint multiple paths help 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.
Srinivasan Ramasubramanian is an Assistant Professor in the Department of Electrical and Computer Engineering at University of Arizona since 2002. He received the B.E. (Hons.) degree in Electrical and Electronics Engineering from Birla Institute of Technology and Science (BITS), Pilani, India, in 1997, and the Ph.D. degree in Computer Engineering from Iowa State University, Ames, in 2002. He is a co-developer of the Hierarchical Modeling and Analysis Package (HIMAP), a reliability modeling and analysis tool, which is currently being used at Boeing, Honeywell, and several other companies and universities. His research interests include architectures and algorithms for optical and wireless networks, multipath routing, fault tolerance, system modeling, and performance analysis. He has served as the TPC Co-Chair of BROADNETS 2005 and ICCCN 2008 conferences and is an editor of the Springer Wireless Networks Journal.