Greedy distributed optimization of unsplittable multicommodity flows

ABSTRACT

We consider solutions for distributed unsplittable multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. A requirement here is that each commodity routes its entire demand along a single path at any point in time. Assuming that the minimum capacity of any edge is at least polylogarithmic factor larger than the maximum demand of any commodity, we present a greedy distributed randomized algorithm, which with high probability, achieves 1+ε approximation, in O(H · log^O(1)) m · (1/ε)⁰⁽¹⁾) iterations where H ≤ n is an upper bound on the number edges allowed on any flow-path. No prior results exist for our distributed model.

Our algorithm is based on simulating the splittable multicommodity flow solution of [1] and picking a path for routing the entire flow according to the probability distribution given by the splittable flow. We use Chernoff bounds to show that the real edge-congestions are sufficiently close to the edge-congestions in the simulation for the analysis of [1] to hold.

REFERENCES

• 1: Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281140]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
distributed, multicommodity flows, unsplittable