Optimal
Node Placement for Path Disjoint Monitoring
Lee Breslau, Ilias Diakonikolas, Nicholas Duffield, Yu Gu, MohammadTaghi Hajiaghayi, David S. Johnson, Howard Karloff, Mauricio Resende, Subhabrata Sen
Under submission, 2008.
Abstract:
We consider the problem of placement of
measurement hosts in a monitoring system intended to provide scalable end-to-end
performance measurements. In this system, pairs of measurement hosts are used
to estimate the performance of a component of a path using multicast inferencing. For each router to be monitored, a pair of
measurement hosts is needed such that the paths from the router to each of the
measurement hosts are edge-disjoint. A challenge in deploying such a monitoring
system is to locate a minimal set of measurement hosts that allows coverage of
the set of all routers to be monitored.
We show that this problem can be mapped to a
related combinatorial problem and propose a collection of algorithms that build
solutions and determine lower bounds on the optimum solution. The algorithms
are evaluated on several large ISP topologies and on synthetic networks, designed
to reflect real world network structure and routing tables and to allow us to
investigate the scalability of the algorithms. The best of the algorithms
typically finds solutions that are very close to optimal, despite the fact that
the problem is provably very hard to approximate in the worst case. These
solutions greatly reduce the number of measurement hosts needed to monitor the
network relative to the naive solution of placing measurement hosts adjacent to
every router to be monitored. By providing practical algorithms that can be
applied to this host placement problem, we have demonstrated the feasibility of
deploying such a monitoring application.
Full version: to be posted