New Results on Multipath Routing

Multipath routing of traffic demands, known also as bifurcated routing or load sharing, has been studied for various telecommunication networks for a long time. An advantage of multipath routing is that it gives a demand the opportunity to use multiple paths through the network to send its traffic. In a single-commodity situation, this benefit can be clearly seen. When multiple demands (multi-commodity situation) compete for the same resources in a network, we focus on the problem of how many demands can take real advantage of multiple paths. In this context, we present new results on multipath routing for a number of network traffic objectives. We show that under certain traffic conditions and topological structures, multipath routing provides virtually no gain compared to single-path routing when the traffic is offered for all demand pairs in a network. We also present results on how different network objectives influence the ability of taking advantage of multipath routing. Our results, based on the basic properties of linear programming, are somewhat against a rather common belief (expressed by the term ”load sharing”) that multipath routing is significantly more effective in carrying traffic than single-path routing.