Loops in Multicommodity Flows,
Abstract
Given the traffic flow from each source to each destination in a network and given the aggregate traffic in each link, find if there is any looping of traffic. A careful definition of looping shows that the question is equivalent to whether some of the aggregate link flows can be reduced without increasing any of the others. It is then shown, through the use of duality in linear programming, that an aggregate flow is loop free if all the traffic follows shortest routes for some assignment of positive lengths to the links. It is further shown that there is a finite set of these length assignments, dependent only on the topology of the network, such that every shortest route flow is a shortest route flow for one of those special assignments. Finally, it is shown that any loopfree flow can be realized by a routing in which the sum, over all destinations, of the number of alternate route links required to reach that destination, is at most the number of links minus the number of nodes.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1977
- Accession Number
- ADA047483
Entities
People
- Robert G. Gallager
Organizations
- Massachusetts Institute of Technology