Analysis of the autonomous system network topology

ABSTRACT

Mapping the Internet is a major challenge for network researchers. It is the key to building a successful modeling tool able to generate realistic graphs for use in networking simulations. In this paper we provide a detailed analysis of the inter-domain topology of the Internet. The collected data and the resulting analysis began in November 1997 and cover a period of two and a half years. We give results concerning major topology properties (nodes and edges number, average degree and distance, routing policy, etc.) and main distributions (degree, distance, etc.). We also present many results about the trees of this network. The evolution of these properties is reviewed and major trends are highlighted. We propose some empirical laws that match this current evolution. Four new power-laws concerning the number of shortest paths between node pairs and the tree size distribution are provided with their detailed validation.

REFERENCES

• 1: 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
• 2: V. Fuller, T. Li, J. Yu, and K. Varadhan. Classless inter-domain routing (cidr) : an address assignment and aggregation strategy. Request For Comments 1519, Internet Engineering Task Force, September 1993.
• 3: 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
• 4: R. Govindan and H. Tangmunarunkit. Heuristics for internet map discovery. In Proceedings of IEEE Infocom'00, Tel Aviv, Israël, 2000.
• 5: D. Grad, J.-J. Pansiot, and S. Marc-Zwecker. Distributed computation of reduced multicast trees. In Proceedings of TDP'96, pages 91-107, La Londe les Maures, June 1996.
• 6: J. Hawkinson and T. Bates. Guidelines for creation, selection and registration of an autonomous system (as). Request For Comments 1930, Internet Engineering Task Force, March 1996.
• 7: K. Hubbard, M. Kosters, D. Conrad, D. Karrenberg, and J. Postel. Internet registry ip allocation guidelines. Request For Comments 2050, Internet Engineering Task Force, November 1996.
• 8: J. Kenney and E. Keeping. Mathematics of Statistics, chapter 15, Linear Regression and Correlation, pages 252-285. Van Nostrand, 3rd edition, 1962.
• 9: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 10: National Laboratory for Applied Network Research, http://moat.nlanr.net/Routing/rawdata/. BGP data from route-views. Supported by NSF.
• 11: 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]
• 12: J.-J. Pansiot, D. Grad, and S. Marc-Zwecker. Towards a logical addressing and routing sublayer for internet multicasting. In Proceedings of PROMS'95, pages 521-535, Salzburg, Austria, October 1995.
• 13: 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]
• 14: Y. Rekhter and P. Gross. Application of the border gateway protocol in the internet. Request For Comments 1772, Internet Engineering Task Force, March 1995.
• 15: Y. Rekhter and T. Li. An architecture for ip address allocation with cidr. Request For Comments 1518, Internet Engineering Task Force, September 1993.
• 16: Y. Rekhter and T. Li. A border gateway protocol 4 (bgp-4). Request For Comments 1771, Internet Engineering Task Force, March 1995.
• 17: Y. Rekhter and T. Li. Implications of various address allocation policies for internet routing. Request For Comments 2008, Internet Engineering Task Force, October 1996.
• 18: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The impact of routing policy on internet paths. In Proceedings of IEEE Infocom'01, Anchorage, Alaska, USA, 2001.
• 19: E. Whittaker and G. Robinson. The Calculus of Observations: A Treatise on Numerical Mathematics, chapter 9, The Method of Least Squares. Dover, 4th edition, 1967.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Measurement

Keywords:
AS network topology analysis, Autonomous System, power laws