Optimal flow control and routing in multi-path networks
We propose two flow control algorithms for networks with multiple paths between each source–destination pair. Both are distributed algorithms over the network to maximize aggregate source utility. Algorithm 1 is a first order Lagrangian method applied to a modified objective function that has the same optimal solution as the original objective function but has a better convergence property. Algorithm 2 is based on the idea that, at optimality, only paths with the minimum price carry positive flows, and naturally decomposes the overall decision into flow control (determines total transmission rate based on minimum path price) and routing (determines how to split the flow among available paths). Both algorithms can be implemented as simply a source-based mechanism in which no link algorithm nor feedback is needed. We present numerical examples to illustrate their behavior.
© 2002 Elsevier Science B.V. Available online 7 January 2003. An earlier version of this paper was presented at the Internet Performance and Control of Network Systems Conference, R.D. van der Mei, F. Huebner-Szaba de Bucs (Eds.), Proceedings of SPIE, vol. 4523, Denver, CO, 21–22 August 2001, The International Society for Optical Engineering. This work was supported by the Australian Research Council through grant A49930405. The authors are very grateful to the anonymous reviewers for their valuable suggestions on and corrections of the manuscript.