| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
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 | 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) $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 |
|
|
No review found.
Did you like this article?
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
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |