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).

One line summary: This paper provides three power laws that describe fundamental properties of the Internet topology, as well as several novel metrics and methods for estimating them, all of which are useful for developing and analyzing new Internet protocols and creating artificial models of the Internet for simulation purposes.

Summary

In this paper, the authors discover three power laws that describe various graph properties of the Internet topology. According to the authors, these power laws are very useful in three respects: (1) they aid in the design of efficient network protocols that can take advantage of the knowledge of the topological properties of the Internet provided by the power laws, (2) they can help researchers create more accurate artificial models of the Internet for simulation purposes, and (3) they can allow researchers to derive estimates of various topological parameters that will be useful for protocol analysis and speculation about future Internet topology. Power laws are expressions of the form y∝xa, which reads “y is proportional to x to the a,” where a is a constant and x and y are measures of interest. The important observation of the authors’ work is that there is some exponent for each graph instance, although the exponents can change over time.

To derive the power laws, the authors used three Internet instances collected at six-month intervals over a period of one year, 1998. These graphs are at the inter-domain level, where each node is a domain or an AS. They also use another graph from 1995 that is at the router level. The authors note that previously used metrics tend to be based on average, minimum, and maximum values, which are not good descriptors of skewed distributions such as those found in studying Internet topology. They also note that it would be useful to be able to characterize a certain aspect of a graph or plot using just one number, to facilitate comparisons. With this in mind, the authors propose several graph metrics for use in defining their power laws: f(d) is the frequency of outdegree d, or the number of nodes with outdegree d, r is the rank of a node, which is the index in the sequence of all nodes ordered by decreasing outdegree, P(h) is the total number of pairs of nodes within h or fewer hops, including self-pairs and counting all other pairs twice, and NN(h) is the average number of nodes in a neighborhood of h hops. They also define λ as the eigenvalue of the graph and i the order of an eigenvalue.

Given this, we can summarize the authors’ power laws. The first power law (rank exponent) states that the outdegree d of a node is proportional to its rank r to the power of a constant. The authors provide a method for estimating this constant. The difference in this constant between the interdomain graphs and the router graph suggests that it can distinguish between graphs of different types. Intuitively, the authors state that this law captures the trade-off between the gain and cost of adding an edge from a financial and functional point of view. The second power law (outdegree exponent) states that the frequency f of an outdegree d is proportional to the outdegree d to the power of a constant. The value of this constant is practically the same across all graphs which suggests that this law describes a fundamental property of the Internet topology, and that it could be useful for testing the realism of a graph intended to represent Internet topology. This power law indicates that the distribution of outdegree is not arbitrary and that lower degrees are more frequent. The third power law (eigen exponent) states that the eigenvalues of a graph are proportional to their order to the power of a constant. Again, as with the first law, this constant is nearly the same for the interdomain graphs but different for the router graph, suggesting that it could be useful for distinguishing among different types of graphs.

Lastly, the authors also describe their novel way to characterize graph connectivity, stated as an approximation (hop-plot exponent): the total number of pairs of nodes P(h) within h hops is proportional to the number of hops h to the power of a constant. This constant also allows for distinguishing among different families of graphs using a single number, and the authors give several examples. They also show how this approximation is useful for estimating how many hops are required to reach a sufficiently large part of the network. In conjunction with this approximation, the authors also provide definitions for the effective diameter of a graph and for the average neighborhood size. The effective diameter is the distance that any two nodes are from each other with high probability. The average neighborhood size is a common parameter used in analyzing the performance of network protocols, and the authors demonstrate the superiority of their estimation method. Finally, the authors conclude by giving several examples of how these power laws could be useful and by arguing that the power laws must characterize fundamental properties of the Internet due to the statistical unlikelihood of their several graphs obeying these laws simply by chance.

Critique

It was nice change of pace to read a paper with a more theoretical bent. I mostly liked this paper. It would be interesting to try and derive the exponents for the power laws using graphs of today’s Internet and see how it compares to those in this paper or see if the power laws even still hold now, especially considering the trend of content providers directly connecting to customers and circumventing the large backbone providers as we discussed in class. One critique of this paper is that they should have used more data. Another thing I would have liked to see is more visual examples of graphs with the kinds of properties the paper highlights via the power laws.