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-Konemann [14], when the maximal path length is small. Copyright © 2007 ACM.