On Power-Law Relationships of the Internet Topology

M. Faloutsos, P. Faloutsos, C. Faloutsos, "On Power-Law Relationships of the Internet Topology," ACM SIGCOMM Conference, (September 1999).

This paper talks about some very interesting power laws that exist in the Internet. Despite the widespread randomness of the Internet, the authors discover some surprisingly simple power laws of the Internet topology. These were discovered by extensive real world measurement data and using least square fit methods subsequently on the plots. The correlation coefficients of 96% or higher imply that the power laws are more that just a coincidental discovery.

Power-laws are expressions of the form y = k * x^a where k and a is a constants, x and y are the measures of interest. The entire work is based on extensive measurements of the Internet. The authors had to their disposal 4 datasets, 3 of which consisted of inter-domain topology data from Nov 1997 to Dec 1998 and the 4th consisted of the router topology data in 1995. The following were the 3 power laws discovered:

Power-Law 1 (rank exponent): The outdegree, dv, of a node v, is proportional to the rank of the node, rv, to the power of a constant R.

Power-Law 2 (outdegree exponent): The frequency fd of an outdegree d is proportional to the outdegree of the power of a constant O.

Power-Law 3 (eigen exponent): The eigenvalues of a graph are proportional to the order of the graph to the power of a constant E.

Comments

An important take-away from this paper is that most of the distributions of interest are skewed (as illustrated by the power law) which makes the use of 'average values' totally misleading while studying the Internet. Power laws are no doubt really helpful in predicting the future of the internet and as well as studying the performances of new protocols that are being created for the Internet. However, my only point of critique about this otherwise very well written paper would be an inadequate analysis of why exactly these power laws hold in the Internet. As highlighted by the authors in the beginning, that in case of some drastic changes in policies or topologies, these power laws may fail to hold. I think it would have been really great had the authors talked a bit more about what these 'drastic changes' may be. Specifically, what are the underlying assumptions that make the power law hold. This would have been very important particularly in the current scenario in which the whole Internet is divided into various ASes and their policy decisions have the potential of having considerable effect on the Internet routing.