Title: On Selecting Nodes for Monitoring A Network

Speaker: Howard Karloff, AT&T Labs--Research


I will start by discussing a recently proposed scheme for monitoring an ISP's
customer's end-to-end performance in a network.  
To efficiently implement the scheme, one needs to solve the following 
Monitor Placement problem: We are given a graph with weights
on its edges,  a subset B of ``branch nodes'' b, and a subset M
of ``potential monitoring nodes'' m.  The goal is to choose a
smallest subset M' of M such that for each specified branch node b,
there are two distinct monitoring nodes m1, m2 in M' such that all shortest
paths from b to m1 are vertex disjoint (except for b) from all shortest paths
from b to m2.

While the problem is provably hard to solve, even approximately
(unless P=NP), we give a fast algorithm called Double Hitting Set
which, on our testbed, often finds the exact integral optimum.
What's more, it shows how to find a good lower bound on the
optimum, proving that Double Hitting Set's output is
(usually) very close to the optimum.

I will also discuss other algorithms our group developed for Monitor
Placement.

This is joint work with many people.