Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'488'730
Articles rated: 2609

29 March 2024
 
  » arxiv » cond-mat/0308288

 Article overview


Compact Routing on Internet-Like Graphs
Dmitri Krioukov ; Kevin Fall ; Xiaowei Yang ;
Date 14 Aug 2003
Subject Statistical Mechanics; Disordered Systems and Neural Networks; Networking and Internet Architecture | cond-mat.stat-mech cond-mat.dis-nn cs.NI
AbstractThe 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) $ar{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 $ar{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 $ar{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.
Source arXiv, cond-mat/0308288
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser claudebot






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica