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.