Brief announcement: 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. Copyright © 2007 ACM.