Compact Routing on Internet-Like Graphs

Abstract

The Thorup-Zwick (TZ) routing scheme is the first generic stretch-3 routing scheme delivering a nearly optimal local memory upper bound. Using both direct analysis and simulation, we calculate the stretch distribution of this routing scheme on random graphs with power-law node degree distributions, $P_k\sim k^{-\gamma }$. We find that the average stretch is very low and virtually independent of $\gamma$. In particular, for the Internet interdomain graph, $\gamma \sim 2.1$, the average stretch is around 1.1, with up to 70% of paths being shortest. As the network grows, the average stretch slowly decreases. The routing table is very small, too. It is well below its upper bounds, and its size is around 50 records for $10^4$-node networks. Furthermore, we find that both the average shortest path length (i.e. distance) $\bar{d}$ and width of the distance distribution $\sigma$ observed in the real Internet inter-AS graph have values that are very close to the minimums of the average stretch in the $\bar{d}$- and $\sigma$-directions. This leads us to the discovery of a unique critical quasi-stationary point of the average TZ stretch as a function of $\bar{d}$ and $\sigma$. The Internet distance distribution is located in a close neighborhood of this point. This observation suggests the analytical structure of the average stretch function may be an indirect indicator of some hidden optimization criteria influencing the Internet's interdomain topology evolution.

29 pages, 16 figures

References in corpus (20)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure of scientific collaboration networks
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Classes of behavior of small-world networks
• Hierarchical Organization in Complex Networks
• Scale-Free Networks are Ultrasmall
• Large-scale topological and dynamical properties of Internet
• Pseudofractal Scale-free Web
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Random graphs as models of networks
• Accurately modeling the Internet topology
• Compact Routing on Internet-Like Graphs
• Metric structure of random networks
• Internet topology at the router and autonomous system level
• On the Tomography of Networks and Multicast Trees

Cited by in corpus (14)

• On Compact Routing for the Internet
• Systematic Topology Analysis and Generation Using Degree Correlations
• Compact Routing on Internet-Like Graphs
• Lessons from Three Views of the Internet Topology
• The Workshop on Internet Topology (WIT) Report
• A critical look at power law modelling of the Internet
• Toward Compact Interdomain Routing
• Near-optimal adjacency labeling scheme for power-law graphs
• Compact Oblivious Routing
• Compact Oblivious Routing in Weighted Graphs
• Evidence of spatial embedding in the IPv4 router-level Internet network
• On the Estimation and Use of Statistical Modelling in Information Retrieval
• Remarks on "Toward Compact Interdomain Routing"
• Scalable Routing on Flat Names