Efficient beacon placement for network tomography

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+<i>ln</i>(|<i>E</i>|) 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%.

REFERENCES

• 1: CAIDA, "Skitter," http://www.caida.org/tools/measurement/skitter.
• 2: M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Processing Magazine, May 2002.
• 3: K. Claffy, T.E. Monk, and D. McRobb, "Internet tomography," Nature, 1999.
• 4: Y. Bejerano and R. Rastogi, "Robust monitoring of link delays and faults in ip networks," in Proceedings of the 2003 ACM INFOCOM, 2003.
• 5: N.G. Duffield and F. Lo Presti, "Multicast inference of packet delay variance at interior network links," in INFOCOM (3), 2000, pp. 1351--1360.
• 6: Nick G. Duffield , Joseph Horowitz , Francesco Lo Presti , Donald F. Towsley, Network Delay Tomography from End-to-End Unicast Measurements, Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet, p.576-595, September 17-20, 2001
• 7: Joseph D. Horton , Alejandro López-Ortiz, On the number of distributed measurement points for network tomography, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948231]
• 8: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: R. Kumar and J. Kaur, "Efficient beacon placement for network tomography," Technical Report, Department of Computer Science, University of North Carolina at Chapel Hill, August 2004.
• 10: A. Shriram and J. Kaur, "Identifying bottleneck links using distributed end-to-end available bandwidth measurements," First ISMA Bandwidth Estimation Workshop, December 2003.
• 11: Postel et. al., "Rfc 791: Internet protocol," Request for Comments, pp. 17--18, 1999.
• 12: H.X. Nguyen and P. Thiran, "Active measurement for multiple link failures diagnosis in ip networks," in Proceedings of Passive and Active Measurement Workshop (PAM), April 2004.
• 13: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 16: Renata Teixeira , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, In search of path diversity in ISP networks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948247]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Algorithms, Management

Keywords:
beacon placement, network monitoring, optimality, tomography