On the marginal utility of network topology measurements

ABSTRACT

The cost and complexity of deploying measurement infrastructure in the Internet for the purpose of analyzing its structure and behavior is considerable. Basic questions about the utility of increasing the number of measurements and measurement sites have not yet been addressed which has led to a "more is better" approach to wide-area ,measurement studies. In this paper, we step toward a more quantifiable understanding of the marginal utility of performing wide-area ,measurements in the context of Internet topology discovery. We characterize the observable topology in terms of nodes, links, node degree distribution, and distribution of end-to-end flows using statistical and information-theoretic techniques. We classify nodes discovered on the routes between a set of 8 sources and 1277 destinations to differentiate nodes which make up the so called "backbone" from those which border the backbone and those on links between the border nodes and destination nodes. This process includes reducing nodes that advertise multiple interfaces to single IP addresses. We show that the utility of adding sources beyond the second source quickly diminishes from the perspective of interface, node, link and node degree discovery. We also show that the utility of adding destinations is constant for interfaces, nodes, links and node degree indicating that it is more important to add destinations than sources.

REFERENCES

• 1: N. Abramson. Information Theory and Coding. McGraw-Hill, 1963.
• 2: A. Adams, J. Mahdavi, M. Mathis, and V. Paxson. Creating a Scalable Architecture for Internet Measurement. In Proceedings of INET '98, 1998.
• 3: Paul Barford , Mark Crovella, Measuring Web performance in the wide area, ACM SIGMETRICS Performance Evaluation Review, v.27 n.2, p.37-48, 9.1.99 [doi>10.1145/332944.332953]
• 4: H-W Braun and KC. Claffy. Global ISP interconnectivity by AS number. http://moat.nlanr.net/AS/.
• 5: A. Broido and K. Claffy. Connectivity of IP Graphs. In Proceedings of SPIE ITCom '01, Scalability and Traffic Control in IP Networks, August 2001.
• 6: H. Chang, S. Jamin, and W. Willinger. On Inferring AS- Level Connectivity from BGP Routing Tables. Available at http://topology.eecs.umich.edu/archive/igp.ps.
• 7: H. Chang, S. Jamin, and W. Willinger. Inferring AS-level Internet Topology from Router-level Traceroutes. In Proceedings of SPIE ITCom '01, Scalability and Traffic Control in IP Networks, August 2001.
• 8: B. Cheswick. Internet mapping project. http://www.cs.belllabs.comlwho/ches/map/.
• 9: J. Chuang and M. Sirbu. Pricing multicast communication: A cost-based approach. In Proceedings of INET '98, 1998.
• 10: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 11: Cooperative Association for Internet Data Analysis (CAIDA). The Skitter project. http://www.caida.orglIbols/Skitter.
• 12: P. Francis, S. Jamin, V. Paxson, L. Zhang, D. Gryniewicz, and Y. Jin. An Architecture for a Global Host Distance Estimation Service. In Proceedings of IEEE INFOCOM '99, March 1999.
• 13: R. Govindan , A. Reddy, An Analysis of Internet Inter-Domain Topology and Route Stability, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.850, April 09-11, 1997
• 14: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of IEEE INFOCOM '00, April 2000.
• 15: Robert M. Gray, Entropy and information theory, Springer-Verlag New York, Inc., New York, NY, 1990
• 16: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 17: V. Jacobson. traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.Z, 1989.
• 18: S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. On the Placement of Internet Instrumentation. In Proceedings of IEEE INFOCOM 2000, March 2000.
• 19: Jean-Jacques Pansiot , Dominique Grad, On routes and multicast trees in the Internet, ACM SIGCOMM Computer Communication Review, v.28 n.1, p.41-50, Jan. 1998 [doi>10.1145/280549.280555]
• 20: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 21: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 22: 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]
• 23: Graham Phillips , Scott Shenker , Hongsuda Tangmunarunkit, Scaling of multicast trees: comments on the Chuang-Sirbu scaling law, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.41-51, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 24: The SCAN Project. http:/iwww.isi.edu/scani.
• 25: The Surveyor Project. http:Nwww.advanced.org/, 1998.
• 26: Internet Traffic Report. http:Nwww.intemettrafficreport.com/.
• 27: The Internet Weather Report. http://www3.mids.org/weather/index.html, 2000.
• 28: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 29: C. Shannon. A Mathematical Theory of Communication. Bell Systems Technical Journal, 47:143-157, 1948.
• 30: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 31: R. Siamwalla, R. Sharma, and S. Keshav. Discovering Internet Topology. Technical report, Cornell University Computer Science Department, July 1998. http://www.cs.cornell.edu/skeshav/papers/discovery.pdf.
• 32: H. Tangmunamnkit, R. Govindan, S. Shenker, and D. Estrin. The Impact of Policy on Internet Paths. In Proceedings of IEEE IN- FOCOM '01, April 2001.
• 33: Ellen W. Zegura , Kenneth L. Calvert , Michael J. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.770-783, Dec. 1997 [doi>10.1109/90.650138]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Experimentation, Measurement, Theory

Keywords:
internet tomography, network measurement, topology discovery, traceroute