Routing and Congestion in Power Law Graphs

We investigate a simple model of packet routing on a power law (scale free) graph where packets arrive at each node at a given rate and are routed to a randomly chosen destination along the shortest path between the source and destination. This mimics the Shortest Path Routing protocol used in the internet. It was previously found that there is a critical rate of packet arrival beyond which there is an onset of congestion and packets start accumulating on the network. This critical rate depends on the maximum betweenness incurred on the network when shortest path routing is used. We analytically find a bound on the maximal betweenness incurred in shortest path routing and compare it to the optimal (least possible) maximal betweenness that can be acheived using an arbitrary routing protocol. This provides an effective quantitative measure of the optimality of Shortest Path Routing.