Compact routing on Internet-like graphs

The Thorup-Zwick (TZ) compact routing scheme is the first generic stretch-3 routing scheme delivering a nearly optimal per-node memory upper bound. Using both direct analysis and simulation, we derive the stretch distribution of this routing scheme on Internet-like inter-domain topologies. By investigating the TZ scheme on random graphs with power-law node degree distributions, P/sub k//spl sime/k/sup -/spl gamma//, we find that the average TZ stretch is quite low and virtually independent of /spl gamma/. In particular, for the Internet inter-domain graph with /spl gamma//spl sime/2.1, the average TZ stretch is around 1.1, with up to 70% of all pairwise paths being stretch-1 (shortest possible). As the network grows, the average stretch slowly decreases. We find routing table sizes to be very small (around 50 records for 104-node networks), well below their theoretical upper bounds. Furthermore, we find that both the average shortest path length (i.e. distance) d~ and width of the distance distribution /spl sigma/ observed in the real Internet inter-AS graph have values that are very close to the minimums of the average stretch in the d~- and /spl sigma/ -directions. This leads us to the discovery of a unique critical point of the average TZ stretch as a function of d~ and /spl sigma/. The Internet's distance distribution is located in a close neighborhood of this point. This is remarkable given the fact that the Internet inter-domain topology has evolved without any direct attention paid to properties of the stretch distribution. It suggests the average stretch function may be an indirect indicator of the optimization criteria influencing the Internet's inter-domain topology evolution.

I. Introduction

Tile question as to what drives the evolutionary process, of the Internet's topology is of interest to many researchers. While various models of its topological structure appear to describe it reasonably well, most neither aid in understanding why the Internet's graph has evolved as it has, nor offer the “metric” which is effectively being optimized by its implementers as it grows.¹

Several authors are currently pursuing such models, however. For one of the latest examples, See [1].

In addition, as the network grows, its global routing scalability is being stressed [2], leading several groups to explore alternatives to the present Internet routing system. We believe that a better understanding of the Internet's topological growth process, coupled with knowledge of the theoretical underpinnings of the routing problem on graphs, could help in evaluating these proposals (or developing others). In particular, we are interested in the performance of the most scalable theoretical routing algorithms on realistic topology graphs.