Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ken Carlberg , Jon Crowcroft, Building shared trees using a one-to-many joining mechanism, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.5-11, Jan. 1997  [doi>10.1145/251007.251008]
	2	J. Chuang and M. Sirbu. Pricing multicast communications: A cost based approach. In Proc. of the {NET'98, 1998.
	3	Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.160-169, May 1996
	4	D. M. Cvetkovii~, M. Boob, and H. Sachs. Spectra of Graphs. Academic press, 1979.
	5	M. Doar. A better model for generating test networks. Proc. Global Internet, IEEE, Nov. 1996.
	6	Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States  [doi>10.1145/182591.182593]
	7	Michalis Faloutsos , Anindo Banerjea , Rajesh Pankaj, QoSMIC: quality of service sensitive multicast Internet protocol, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.144-153, Oct. 1998
	8	M. Faloutsos, P. FaIoutsos, and C. Faloutsos. Power-laws of the Internet topology. Technical Report UCR-CS-99-01, University of California Riverside, Computer Science, 1999.
	9	National Laboratory for Applied Network Research. Routing data. Supported by NSF, http://moat.nlanr.net/Routing/rawdata/, 1998.
	10	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
	11	Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994  [doi>10.1109/90.282603]
	12	B. Mandelbrot. Fractal Geometry of Nature. W.H. Freeman, New York, I977.
	13	John Moy, Multicast routing extensions for OSPF, Communications of the ACM, v.37 n.8, p.61-ff., Aug. 1994  [doi>10.1145/179606.179654]
	14	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]
	15	Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995  [doi>10.1109/90.392383]
	16	Vern Paxson , Sally Floyd, Why we don't know how to simulate the Internet, Proceedings of the 29th conference on Winter simulation, p.1037-1044, December 07-10, 1997, Atlanta, Georgia, United States  [doi>10.1145/268437.268737]
	17	Graham Phillips , Scott Shenker , Hongsuda Tangmunarunkit, Scaling of multicast trees: comments on the Chuang-Sirbu scaling law, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.41-51, Oct. 1999
	18	William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C. Cambridge University Press, 2nd edition, 1992.
	19	Y. Rekhter and T. Li (Eds). A Border Gateway Protocol 4 (BGP-4). Internet-Draft:draft-ietf-idr-bgp4-08.txt available from ftp://ftp.ietf, org/internet-drafts/, 1998.
	20	S. R. Resnick. Heavy tail modeling and teletraffic data. Annals of Statistics, 25(5):1805-1869, 1997.
	21	Manfred Schroeder. Fructals, Chaos. Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, 1991.
	22	D. Waitzman, C. Partridge, and S. Deering. Distance vector multicast routing protocol. IETF RFC 1075, 1998.
	23	B. M. Waxman. Routing of multipoint connections. IEEE Journal of Selected Areas in Communications, pages 1617- 1622, 1988.
	24	Walter Willinger , Vern Paxson , Murad S. Taqqu, Self-similarity and heavy tails: structural modeling of network traffic, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
	25	Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level, ACM SIGCOMM Computer Communication Review, v.25 n.4, p.100-113, Oct. 1995
	26	D. Zappala, D. Estrin, and S. Shenker. Alternate path routing and pinning for interdomain multicast routing. Technical Report USC CS TR 97-655, U. of South California, 1997.
	27	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]
	28	G.K. Zipf. Human Behavior and Principle of Least Effort: An Introduction to Human Ecology. Addison Wesley, Cambridge, Massachusetts, 1949.