On the number of distributed measurement points for network tomography

ABSTRACT

Internet topology information is only made available in aggregate form by standard routing protocols. Connectivity information and latency characteristics must therefore be inferred using indirect techniques. In this paper we consider measurements using a distributed set of measurement points or beacons. We show that computing the minimum number of required beacons on a network under a BGP-like routing policy is NP-hard and at best Ω(log n)-approximable. In the worst case at least (n-1)/3 and at most (n+1)/3 beacons are required for a network with n nodes. We then introduce some observations that allow us to propose a relatively small candidate set of beacons for the current Internet topology. The set proposed has properties with relevant applications for all-paths routing on the public Internet and performance based routing.

REFERENCES

• 1: A. Adams, T. Bu, R. Caceres, N. Duffield, T.Friedman, J. Horowitz, F. Lo Presti, S.B. Moon, V. Paxson, D. Towsley. The Use of End-to-end Multicast Measurements for Characterizing Internal Network Behavior, IEEE Comm., 2000.
• 2: A. Adams, J. Mahdavi, M. Mathis, and V. Paxson, Creating a Scalable Architecture for Internet Measurement. Proc. 8th Internet Society Conf. (INET), 1998.
• 3: A. Adams, and M. Mathis. A system for flexible network performance measurement. Proc. 10th INET Conf., 2000.
• 4: Micah Adler , Tian Bu , Ramesh K. Sitaraman , Donald F. Towsley, Tree Layout for Internal Network Characterizations in Multicast Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.189-204, November 07-09, 2001
• 5: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: Asia Pacific Network Information Centre (APNIC). Daily BGP statistics. http://www.apnic.net/stats/bgp1. May 5, 2001.
• 7: Cooperative Association for Internet Data Analysis (CAIDA). The Skitter Project. http://www.caida.org/tools/measurement/skitter/index.html, 2001.
• 8: Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505204]
• 9: O. Bonaventure, S. De Cnodder, J. haas, B. Quoitin, R. White. Controlling the redistribution of BGP routes. Internet draft.
• 10: Steve Branigan , Hal Burch , Bill Cheswick , Frank Wojcik, What Can You Do with Traceroute?, IEEE Internet Computing, v.5 n.5, p.96, September 2001 [doi>10.1109/4236.957902]
• 11: Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 12: R. Caceres, N.G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network internal loss characteristics. IEEE Transactions on Information Theory, v.45, n.7, 1999, pp. 2462--2480.
• 13: Bill Cheswick, Hal Burch, and Steve Branigan. Mapping and Visualizing the Internet. Proc. USENIX Technical Conf., 2000.
• 14: K. Claffy, G. Miller and K. Thompson. The nature of the beast: recent traffic measurements from an Internet backbone. Proc. 8th Internet Soc. Conf. (INET), 1998.
• 15: K. Claffy, T.E. Monk and D. McRobb. Internet Tomography. Nature, 7th January 1999.
• 16: X. Deng. Short Term Behaviour of Ping Measurements. MSc thesis, Univ. of Waikato, 1999.
• 17: N. Feamster, J. Borkengham, J. Rexford. Controlling the Impact of BGP Policy Changes on IP Traffic. Technical Memorandum, AT&T Labs Research.
• 18: P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gryniewicz, Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. Proc. IEEE Conf. on Comp. Comm. (INFOCOM), 1999, pp. 210-217
• 19: 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
• 20: R. Govindan, H. Tangmunarunkit. Heuristics for Internet Map Discovery. Proc. IEEE Conf. on Comp. Comm. (INFOCOM), 2000, pp. 1371-1380
• 21: I. D. Graham, S. F. Donelly, S. Martin, J. Martens and J. G. Cleary. Nonintrusive and accurate measurements of unidirectional delay and delay variation in the Internet. Proc. 8th Internet Society Conf. (INET), 1998.
• 22: R. Gúerin and A. Orda. QoS-based routing in networks with inaccurate information. Proc. IEEE Conf. on Comp. Comm.ons (INFOCOM), 1997.
• 23: Bassam Halabi, Internet Routing Architectures, Cisco Press, 1997
• 24: Internet Software Consortium. http://www.isc.org/ds/WWW-200301/index.html.
• 25: S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, L. Zhang. On the Placement of Internet Instrumentation. IEEE Conf. on Comp. Comm. (INFOCOM), 2000, pp. 295--304.
• 26: S. Kalidindi and M. J. Zekauskas. Surveyor: An infrastructure for Internet performance measurements. Proc. 9th Internet Soc. Conf. (INET), 1999.
• 27: G. Robert Malan , Farnam Jahanian, An extensible probe architecture for network protocol performance measurement, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.215-227, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 28: A. Odlyzko. The current state and likely evolution of the Internet Proc. Globecom'99, IEEE, pp. 1869--1875, 1999.
• 29: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 30: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 31: V. Paxson, J. Mahdavi, A. Adams and M. Mathis, An Architecture for Large-Scale Internet Measurement. IEEE Comm., v.36, n.8, 1998, pp. 48--54.
• 32: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 33: A. Scherrer. 127,781,000 Internet Hosts: How Matrix.net gets its host counts. http://www.matrix.net/isr/library/how_matrix_gets_its_host_counts.html, 2001, Access: May 2001.
• 34: P. Savola. Multihoming using IPv6 addressing derived from AS numbers. draft-savola-multi6-asn-pi-00.txt, work in progress. IETF internet draft, January 2003.
• 35: S. Seshan, M. Stemm, and R.H. Katz. SPAND: Share Passive Network Performance Discovery. Proc. 1st Usenix Symp. on Internet Technologies and Systems, 1997.
• 36: R. Siamwalla, R. Sharma, and S. Keshav. Discovering Internet Topology. Technical Report, Cornell Univ., July 1998.
• 37: Donald F. Towsley, Network Tomography through End-to-End Measurements, Revised Papers from the Third International Workshop on Algorithm Engineering and Experimentation, p.60, January 05-06, 2001
• 38: X. Xiao and L. M. Ni. Reducing routing table computation cost in OSPF. Proc. 9th Internet Society Conf. (INET), 1999.

INDEX TERMS

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

General Terms:
Measurement, Theory

Keywords:
NP-hard, approximation algorithms, internet tomography, network measurements, resilient overlay networks, topology discovery