Greedy distributed optimization of multi-commodity flows |
| |
Authors: | Baruch Awerbuch Rohit Khandekar |
| |
Affiliation: | 1. Computer Science Department, Johns Hopins University, 3400 N. Charles Street, 224 NEB, Baltimore, MD, 21218, USA 2. IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY, 10598, USA
|
| |
Abstract: | The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely, our algorithm achieves ${1+\varepsilon}The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically
important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions
for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated
manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely,
our algorithm achieves 1+e{1+\varepsilon} approximation, with running time O(H· logO(1)m· (1/e)O(1)){O(H{\cdot} \log^{O(1)}m{\cdot} (1{/}\varepsilon)^{O(1)})} where H is the number of edges on any allowed flow-path. No prior results exist for our model. Our algorithm is a reasonable alternative
to existing polynomial sequential approximation algorithms, such as Garg–K?nemann (Proceedings of the 39th Annual Symposium
on Foundations of Computer Science, Palo Alto, CA, USA, pp. 300–309, 1998). The algorithm is simple and can be easily implemented
or taught in a classroom. Remarkably, our algorithm requires that the increase in the flow rate on a link is more aggressive than the decrease in the rate. Essentially all of the existing flow-control heuristics are variations of TCP, which uses
a conservative cap on the increase (e.g., additive), and a rather liberal cap on the decrease (e.g., multiplicative). In contrast,
our algorithm requires the increase to be multiplicative, and that this increase is dramatically more aggressive than the decrease. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|