Efficient Beacon Placement for Network Tomography
IMC - Internet Measurement Conference
October 25th - 27th, 2004
Taormina, Sicily, Italy
Download [PDF][PPT]
October 25th - 27th, 2004
Taormina, Sicily, Italy
Download [PDF][PPT]
Technical Report
August, 2004
Department of Computer Science
University of North Carolina at Chapel Hill
Download [PDF]
August, 2004
Department of Computer Science
University of North Carolina at Chapel Hill
Download [PDF]
Abstract
Recent interest in using tomography for network monitoring has
raised the fundamental issue of whether it is possible to use only a
small number of probing nodes (beacons) for monitoring all edges
of a network in the presence of dynamic routing. Past work has
shown that minimizing the number of beacons is NP-hard, and has
provided approximate solutions that may be fairly suboptimal. In
this paper, we use a two-pronged approach to compute an efficient
beacon set: (i) we formulate the need for, and design algorithms
for, computing the set of edges that can be monitored by a beacon
under all possible routing states; and (ii) we minimize the number
of beacons used to monitor all network edges. We show that the
latter problem is NP-complete and use an approximate placement
algorithm that yields beacon sets of sizes within 1+ln(|E|) of the
optimal solution, where E is the set of edges to be monitored. Beacon
set computations for several Rocketfuel ISP topologies indicate
that our algorithm may reduce the number of beacons yielded by
past solutions by more than 50%.
The following graph shows the results of our beacon set algorithms on 10 rocketfuel topologies. Note that our approach (the black and gray bars) yield much smaller beacon sets than previous approaches (the white bar).
Bibtex Entry
IMC 2004 Proceedings:
@inproceedings{
ritesh04-beacon,
author = {Ritesh Kumar and Jasleen Kaur},
title = {Efficient Beacon Placement for Network Tomography},
booktitle = {Proceedings of IMC 2004},
month = October,
year = 2004,
location = {Taormina, Sicily, Italy}
}
UNC Technical Report:
@article{
Kumar04-tr,
author = {R. Kumar and J. Kaur},
title = {Efficient Beacon Placement for Network Tomography},
journal = {Technical Report, Department of Computer Science,
University of North Carolina at Chapel Hill},
month = {August},
year = {2004}
}