Skip to main content

Compact routing on internet-like graphs

Publication ,  Journal Article
Krioukov, D; Fall, K; Yang, X
Published in: Proceedings - IEEE INFOCOM
November 22, 2004

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 k ≃ k -γ, we find that the average TZ stretch is quite low and virtually independent of γ. In particular, for the Internet inter-domain graph with γ ≃ 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 10 4-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 σ 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 σ-directions. This leads us to the discovery of a unique critical point of the average TZ stretch as a function of d̄ and σ. 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.

Duke Scholars

Published In

Proceedings - IEEE INFOCOM

ISSN

0743-166X

Publication Date

November 22, 2004

Volume

1

Start / End Page

209 / 219
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Krioukov, D., Fall, K., & Yang, X. (2004). Compact routing on internet-like graphs. Proceedings - IEEE INFOCOM, 1, 209–219.
Krioukov, D., K. Fall, and X. Yang. “Compact routing on internet-like graphs.” Proceedings - IEEE INFOCOM 1 (November 22, 2004): 209–19.
Krioukov D, Fall K, Yang X. Compact routing on internet-like graphs. Proceedings - IEEE INFOCOM. 2004 Nov 22;1:209–19.
Krioukov, D., et al. “Compact routing on internet-like graphs.” Proceedings - IEEE INFOCOM, vol. 1, Nov. 2004, pp. 209–19.
Krioukov D, Fall K, Yang X. Compact routing on internet-like graphs. Proceedings - IEEE INFOCOM. 2004 Nov 22;1:209–219.

Published In

Proceedings - IEEE INFOCOM

ISSN

0743-166X

Publication Date

November 22, 2004

Volume

1

Start / End Page

209 / 219