On Power-Law Relationships of the Internet Toplogy

This paper examines several maps of the internet topology, three at the autonomous system level (derived from a BGP peering point) from over just over a years time in 1997-1998 and one of the router-level topology from 1995.

The authors demonstrate that these four graphs have what the authors call power laws: that is, relationships of the form y ≈ A*x^B for some A, B over some properties of parts of the graph x and y. The power laws they find empirically are:

• between the outdegree rank (position in list of nodes sorted by outdegree) of a node and outdegree of a node;
  
• between the frequency of an outdegree in the graph and the outdegree itself;
  
• between the number of pairs of node within a distance of each other and the distance;
  
• between the eigenvalues of the graph (presumably of its adjacency matrix though the authors appear to forget to specify this) and their ranks
  

As applications for these observations, the authors primarily propose using these observations to more realistic evaluate applications for the Internet. They observe that prior work which ignored these power laws made some poor estimates about properties of the internet graph: for example, they implicitly assumed a roughly uniform distribution of outdegrees and thus assumed that most nodes had much smaller 2 or 3 or 4-hop than actually occured. Toward the end of using these properties for evaluation, the authors try to extract properties that can be used directly to produce synthetic graphs for Internet protocol evaluation (for example, a division into a core/tree structure and a direct estimator of AS and router hop counts).

The authors also using these properties to produce test environments that will continue to reflect the Internet in the future. They suggest that these power laws will continue to exist over future topology graphs and so can be used to construct reasonable evaluations for future Internet protocols intended for a larger Internet.

Though the formulas for diameter, neighborhood size, etc. are good qualitative summaries of the Internet topology (and thus useful for protocol design, etc.), I find it hard to believe that one would really prefer to use them as is to evaluate protocols intended for the current topology when one could sample from an actual topology map.

It is disappointing that the authors did not have a very long time span of data to analyze. I found it strange that the authors did not attempt to collect a (inevitably partial) 1997 or 1998 map of the router-level topology of the Internet to allow for a several-year analysis of the evolution of the topology (which seems to be one of the major goals of the work). And, for the BGP views, the authors did not attempt to quantify how complete their graphs were (since some links may not be visible from some BGP peering points).