Scaling properties of the Internet graph

As the Intemet grows in size, it becomes crucial to understand bow the speeds of links in the network must improve in order to sustain the pressure of new end-nodes being added each day. Although the speeds of links in the core and at the edges roughly improve accord-ing to Moore's law, this improvement alone might not be enough. Indeed, the structure of the Internet graph and routing in the net-work might necessitate much faster improvements in the speeds of key links in the network. In this paper, using a combination of analysis and extensive sim-ulations, we show that the worgt congestion in the Internet in fact scales poorly with the network size (n 1+f2(1), where n is the num-ber of nodes), when shortest-path routing is used. We also show, somewhat surprisingly, that policy-based routing does not exac-erbate the maximum congestion when compared to shortest-path routing. Our results how that it is crucial to identify ways to alleviate this congestion to avoid some links from being perpetually congested. To this end, we show that the congestion scaling properties of the Internet graph can be improved ramatically by introducing mod-erate amounts of redundancy in the graph in terms of parallel edges between pairs of adjacent nodes