Minimizing the total cost of network measurements in a distributed manner: a primal-dual approach

ABSTRACT

We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation, for which most of the previous distributed algorithms apply, has an exponential number of variables, one for each path.

We present first known distributed (1+ε) approximation algorithm for this problem that converges in time that is linear in the maximal path length and poly-logarithmic in the size of the entire network and has polynomial computational overhead. Previous distributed solutions achieving similar approximations required either convergence time that is polynomial or computational overhead that is exponential in the size of the entire network.

REFERENCES

• 1: Baruch Awerbuch and Yossi Azar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In FOCS, 1994.
• 2: 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]
• 3: 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
• 4: 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
• 5: 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
• 6: 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]
• 7: 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 optimization, network measurements, packing and covering linear programs