Distributed network monitoring and multicommodity flows: a primal-dual approach

ABSTRACT

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other:

• • Passive Commodity Monitoring: minimize the total cost of monitoring devices used to measure the network traffic on all paths.
• • Maximum Throughput Multicommodity flow: maximize the total value of the flow with bounded edge capacities.

.

We present the first known distributed algorithms for both of these problems that converge to (1+ε)-approximate solutions in poly-logarithmic time with communication and space overheads that depend on the maximal path length but are almost independent of the size of the entire network. Previous distributed solutions achieving similar approximations required convergence time, communication, or space overheads that depend polynomially on the size of the entire network. The sequential simulation of our algorithm is more efficient than the fastest known approximation algorithms for multicommodity flows, e.g., Garg-Könemann [14], when the maximal path length is small.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 2: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 3: B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
• 4: B. Awerbuch and R. G. Gallager. Distributed BFS algorithms. In FOCS, 1985.
• 5: 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]
• 6: 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
• 7: B. Awerbuch and T. Leighton. A simple local-control approximation algorithm for multicommodity flow. In FOCS, 1993.
• 8: 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]
• 9: B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead. In FOCS, 1990.
• 10: B. Awerbuch and D. Peleg. Sparse partitions. In FOCS, 1990.
• 11: 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]
• 12: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 13: Chuck Fraleigh , Christophe Diot , Bryan Lyles , Sue B. Moon , Philippe Owezarski , Dina Papagiannaki , Fouad A. Tobagi, Design and Deployment of a Passive Monitoring Infrastructure, Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet, p.556-575, September 17-20, 2001
• 14: 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
• 15: M. Kaart et al. The importance of internet measurements for internet policy (extended abstract).
• 16: 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]
• 17: Mehryar Mohri, Semiring frameworks and algorithms for shortest-distance problems, Journal of Automata, Languages and Combinatorics, v.7 n.3, p.321-350, January 2002
• 18: M. Murray and K. Claffy. Measuring the immeasurable: Global internet measurement infrastructure. In PAM - A workshop on Passive and Active Measurements, 2001.
• 19: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 20: Yuval Shavitt , Eran Shir, DIMES: let the internet measure itself, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096546]
• 21: C. R. Simpson, Jr., and G. F. Riley. Netiυhome: A distributed approach to collecting end-to-end network performance measurements.
• 22: 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, passive network measurement