On Power-Law Relationships of the Internet Topology

Summary
This paper attempts to derive some power laws for the inter-domain topology of the Internet. These are relationships of the form y α x^a, relating some property of the graph of node connectivity to another. These relationships can be used to check the validity of models of the Internet used in simulation, as well as to predict the growth of the network.

The authors use three data sets for their study, collected by the National Laboratory for Applied Network Research, about six months apart, the first collected in November 1997. The information is gleaned from a route server from the BGP routing tables of some distributed routers connected to that server. There is also a router level graph used, to provide data at a different level.

There are a few definitions used in the laws:

• rank - the rank of a node is its place in the list of nodes sorted by decreasing outdegree
• frequency - the frequency of an outdegree d is the number of nodes with outdegree d

The authors derive three main power-laws:

1. The rank exponent - This law states that the outdegree of a node is proportional to the rank of the node to the power of a constant R. R is a single number that can characterize an entire graph. Indeed, in the sample data the R value is similar for all three inter-domain graphs. This suggests that a graph that has a quite different value of R is not a good representation of Internet topology.
   
   
2. The outdegree exponent - This law states that the frequency of an outdegree d is proportional to the outdegree to the power of a constant O. Again the inter-domain graphs all exhibit very similar O values, indicating a common structure.
   
   
3. The hop-plot exponent - This law states that the total number of pairs of nodes, within h hopes, is proportional to the number of hops to the power of a constant H. The authors argue that since the interdomain graphs all have a similar value for H, but the router graph has a different one, that H is a good way of characterizing families of graphs.

Finally the authors argue that using power-laws is a better way of characterizing graphs of the Internet than previous methods as the relationships are often skewed. For example, 85% of nodes have an outdegree less than the average in one of their graphs.

Comments
I thought this was an interesting paper. It presents a concise and simple derivation of the various laws, and does a good job explaining why their results might be useful. I'm concerned that all the laws are derived from graphs from a single source, however. This could indicate some fundamental properties of the particular connections the source saw, but not properties of the Internet as a whole. One hopes the chances of this are minimized by the collection points being distributed geographically.

Some of their derivations also relied on too little data, in my opinion. For example the hop-count metric has only four points in the interdomain graphs, which seems far too few to derive any real relationship.

Finally, given the time I'd like to look up the actual numbers for the numbers the paper predicts, but my Google skills are failing me at the moment. All in all, an interesting paper, and one I'd keep on the syllabus.