When: January 27, 2017, 2:00 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4401, firstname.lastname@example.org
How Beneficial is Multipath Routing?
It’s often believed that multipath routing is always beneficial. Taking a traffic engineering perspective for computer networks, we consider commonly used objectives such as congestion minimization, minimum average delay, and minimum cost routing in a multi-commodity network flow framework. Using a well-known result from linear programming, we highlight that the number of paths taken by all demands at optimality is limited by the total number of demands and links in a network. We generalize this result for any objectives. When all node pairs (demands) in a network have traffic, multipath routing essentially becomes single-path routing, especially as the network becomes large when the number of links is in the order of nodes. Under certain traffic and capacity conditions, single-path routing is shown to be optimal. We will also present results on a number of traffic scenarios and load conditions using topologies used by large backbone Internet service providers and in data center networks.
Deep Medhi is Curators’ Distinguished Professor in the Department of Computer Science and Electrical Engineering at the University of Missouri- Kansas City, USA. He received B.Sc. (Hons) in Mathematics from Cotton College, Gauhati University, India, M.Sc. in Mathematics from the University of Delhi, India, and his Ph.D. in Computer Sciences from the University of Wisconsin-Madison. Prior to joining UMKC in 1989, he was a member of the technical staff at AT&T Bell Laboratories. He was an invited visiting professor at the Technical University of Denmark, a visiting research fellow at Lund Institute of Technology, Sweden, a research visitor at University of Campinas, Brazil under the Brazilian Science Mobility Program and served as a Fulbright Senior Specialist. His short term visits include Princeton University and MIT. He is the Editor-in-Chief of Springer’s Journal of Network and Systems Management, and serves on the editorial board of IEEE/ACM Transactions on Networking, IEEE Transactions on Network and Service Management, and IEEE Communications Surveys & Tutorials. He is co-author of the books, Routing, Flow, and Capacity Design in Communication and Computer Networks (2004) and Network Routing: Algorithms, Protocols, and Architectures (2007), both published by Morgan Kauffman/Elsevier.