Kleinberg's grid unchained - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2020

Kleinberg's grid unchained

(1, 2, 3) , (1, 3)


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.
Fichier principal
Vignette du fichier
kleinberg_revised_hal.pdf (508.48 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02052607 , version 1 (28-02-2019)



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



Gmail Facebook Twitter LinkedIn More