Greedy distributed optimization of multi-commodity flows

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+ε) approximation, with running time O(logP•log^O(1)m•(1/ε)^O(1) where P is the number of flow-paths in the network. No prior results exist for our model.

Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg-Könemann [17]. 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.

REFERENCES

• 1: B. Awerbuch and Y. Azar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. FOCS, 1994.
• 2: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 3: B. Awerbuch, Y. Azar, Y. Richter, and D. Tsur. Tradeoffs in worst-case equilibria. WAOA, 2004.
• 4: Baruch Awerbuch , Rohit Khandekar, Distributed network monitoring and multicommodity flows: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281141]
• 5: Baruch Awerbuch , Rohit Khandekar , Satish Rao, Distributed algorithms for multicommodity flow problems via approximate steepest descent framework, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.949-957, January 07-09, 2007, New Orleans, Louisiana
• 6: B. Awerbuch and T. Leighton. A simple local-control approximation algorithm for multicommodity flow. FOCS, 1993.
• 7: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 8: Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• 9: Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
• 10: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 11: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 12: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 13: Shlomo Dalev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.103-117, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93407]
• 14: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 16: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073868]
• 17: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 18: Naveen Garg , Neal E. Young, On-Line End-to-End Congestion Control, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.303-312, November 16-19, 2002
• 19: Mohamed G. Gouda , Nicholas J. Multari, Stabilizing Communication Protocols, University of Texas at Austin, Austin, TX, 1990
• 20: R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
• 21: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 22: P. Klein, S. Plotkin, C. Stein, and E. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. STOC, 1990.
• 23: Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
• 24: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Lecture Notes in Computer Science, 1563:404--413, 1999.
• 25: James F. Kurose , Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Pearson Benjamin Cummings, 2004
• 26: C. Labovitz, A. Ahuja, and F. Jahanian. Experimental study of internet stability and wide-area backbone failures. Technical Report CSE-TR-382-98, University of Michigan, 1998.
• 27: Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Selected papers of the 23rd annual ACM symposium on Theory of computing, p.228-243, April 1995, New Orleans, Louisiana, United States
• 28: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 29: J. McQuillan, I. Richer, and E. Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Commun., 28(5):711--719, May 1980.
• 30: J. M. McQuillan, G. Falk, and I. Richer. A review of the development and performance of the arpanet routing algorithm. IEEE Trans. on Commun., 26(12):1802--1811, Dec. 1978.
• 31: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 32: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 33: J. Rexford. Handbook of Optimization in Telecommunications, Chapter on Route optimization in IP networks. Kluwer Academic Publishers, 2005.
• 34: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, Cornell University, Ithaca, NY, 2002
• 35: N. Young, Sequential and Parallel Algorithms for Mixed Packing and Covering, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.538, October 14-17, 2001

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 algorithms, multi-commodity flows, self-stabilization, statelessness