Skip to Main content Skip to Navigation
Journal articles

Kleinberg's grid unchained

Abstract : One of the key features of small-world networks is the ability to route messages in a few hops, using a decentralized algorithm in which each node has a limited knowledge of the topology. In 2000, Kleinberg proposed a model based on an augmented grid that asymptotically exhibits such a property. In this paper, we revisit the original model with the help of numerical simulations. Our approach is fueled by a new algorithm that can sample augmenting links in an almost constant time. The speed gain allows us to perform detailed numerical evaluations. We first observe that, in practice, the augmented scheme proposed by Kleinberg is more robust than what is predicted by the asymptotic behavior, even in very large finite grids. We also propose tighter bounds on the asymtotic performance of Kleinberg's greedy routing algorithm. We finally show that, if the model is fed with realistic parameters, the results are in line with real-life experiments.
Document type :
Journal articles
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-02052607
Contributor : Fabien Mathieu <>
Submitted on : Thursday, February 28, 2019 - 3:18:41 PM
Last modification on : Tuesday, September 8, 2020 - 3:28:53 AM
Long-term archiving on: : Wednesday, May 29, 2019 - 5:38:14 PM

File

kleinberg_revised_hal.pdf
Files produced by the author(s)

Identifiers

Citation

Céline Comte, Fabien Mathieu. Kleinberg's grid unchained. Theoretical Computer Science, Elsevier, 2020, 826-827, pp.25-39. ⟨10.1016/j.tcs.2018.09.025⟩. ⟨hal-02052607⟩

Share

Metrics

Record views

131

Files downloads

177