Is Multipath Routing Beneficial?

It's often believed that multipath routing is always beneficial. Taking a traffic engineering perspective, we consider commonly used goals such as congestion minimization, minimum average delay, and minimum cost routing. Using a well-known result from linear programming, we show that numbers of paths taken by all demands at optimality is limited by the total number of demands and links in a network. When all node pairs (demands) in a network have traffic,  multipath routing essentially becomes single-path routing, especially as the network becomes large. Under certain traffic conditions, single-path routing is found to be optimal. We will also present results on a number of traffic scenarios and load conditions using topologies used by ISPs and in data center networks. These observations are counter-intuitive due to our commonly held belief about multipath routing. 

Deep Medhi is Curators' Professor in the Department of Computer Science and Electrical Engineering at the University of Missouri- Kansas City, USA. He received B.Sc. 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, USA. 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. He is the Editor-in-Chief of Springer’s Journal of Network and Systems Management, and is 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.