A First-Principles Approach to Understanding the Internet’s Router-level Topology

I liked this paper. This paper looks at Internet topology generation work from a different angle: how well do the generated networks perform given physical constraints on router technology (number of ports vs bandwidth)? The answer is that they perform poorly. This means that while the generated networks match the degree distributions seen in the real Internet - which is not surprising because it is exactly how the generators were designed - just choosing random graphs with this degree distribution does not give "good", well-performing network designs. The real Internet is not built by a fully random process - it's built by people who are trying to provide good performance! Your random network can't match the performance properties of the real Internet if your generator doesn't also strive for performance. This makes a lot of topology generation work and work in algorithms evaluated using random topologies look fairly dubious.

I liked that there is a good explanation of why the different networks perform differently. The idea is that if you want a high-performing network, you want edge routers to have high degrees (servicing many users) and core routers to have relatively lower degrees (thus supporting higher-bandwidth links). The random graph models fail to do this. I also liked the methodology for showing what a heuristically optimal topology looks like (take a graph and change it while preserving degrees), and the plot of performance vs likelihood under the random graph model which basically means that well-performing graphs are unlikely to arise by chance (network engineers really do earn their pay).

It was pretty surprising that this paper came out in 2004, almost ten years after the previous paper and the surrounding flurry of work on topology generators. That's a long time of looking only at arbitrary graph properties instead of trying to see whether the generated networks are in any way realistic! It's disconcerting that many routing algorithms, etc were designed for these random topologies and may do bad things on a network that actually looks like the Internet. This all goes to show that real implementation is the best evaluation. Finally, the idea of looking at a generated network's performance and trying to make generators work like real network designers seems obvious in hindsight, but it seems to be one of those obvious ideas that people have trouble coming up with until someone else points it out to them.