First-Principles Approach to Understanding Internet Router-Level Topology

This paper also attempts to understand how routers interconnect in the Internet, but instead of using power laws, they use a "first principles" approach by taking into account both technology restrictions of routers and the economic principles guiding ASs to interconnect routers--- this means looking at hierarchies of ASs and routers as well. That is, taking into account that ASs can be level-1, level-2, or level-3 and therefore have proportional traffic to their level.

Criticizing the previous paper's methodology, the authors rightly claim that power laws hold for graphs that look much different from each other; edge rerouting schemes can take one power law graph and turn it into another with very different connectivity and radius but with the same distribution, for example, of ranks. They also point out that there is little evidence the power law means anything for the topologies since there were so few data points.

I think the methodology here is much more sound. First, they actually use subsets of the internet as well as a model of how routers can connect hierarchically in the ideal case; the internet topology is found to be in a region that, measured with their "likelihood" metric, can only have come about by using non-random strategies to connect routers. Therefore generating graphs randomly, even if they follow some distribution of ranks and other metrics, does not seem like a good way to create a representative topology.