Router Topology

This paper states that measurements like degree properties are insufficient to properly construct a network topology that truly resembles the internet. It presents several different construction mechanisms for graphs with the same degree distributions, and then compares them in terms of both their likelihood and their achieved bandwidth. Likelihood is defined as a ratio between L_max - L(graph) and L_max - L_min. The value L(graph) is given by \sum_{(i,j)\in E} d_i * d_j, where d_i is the degree of node i, and the (i,j) are the edges in the graph.

The paper first spends a lot of time stating that even though two different networks may have similar degree distributions, their topologies may be very different. Near the end, it describes several different methods for creating the graphs of which it speaks. Some of the graphs are as follows:

• Preferential Attachment - Start with 3 connected nodes, then each new node attaches to one with probability proportional to its current degree. Add additional links until the degree distribution works out.
  
• GRG - uses the numbers from PA to create a randomly (possibly unconnected) graph. Results in highly connected central nodes.
• Heuristically Optimal Topology - starts with a few lightly connected core routers, and then high degree gateways attached to these routers, spanning out into trees of edge routers.
• Abilene-inspired Topology - I wasn't exactly sure what this was.
• Sub-optimal Topology - The core routers are a chain, instead of being lightly connected.

It then compares the bandwidths of these topologies, which all have the same degree distribution. It finds that the HOT has the highest bandwidth, followed by the Abilene-inspired Topology. It also finds that in general, the high bandwidth topologies have lower likelihoods.

Overall, this paper builds nicely on the previous power laws paper, but I would like to see a comparison of the other properties of these topologies that were explored in the power laws paper (such as the expected neighborhood size per number of hops, and the eigenvalues). Still, it actually provides a method for constructing an internet-resembling topology, which is good for simulations and theoretical calculations.