Kleinberg's Grid Reloaded

Abstract : One of the key features of small-worlds is the ability to route messages with few hops only using local knowledge of the topology. In 2000, Kleinberg proposed a model based on an augmented grid that asymptotically exhibits such property. In this paper, we propose to revisit the original model from a simulation-based perspective. Our approach is fueled by a new algorithm that uses dynamic rejection sampling to draw augmenting links. The speed gain offered by the algorithm enables a detailed numerical evaluation. We show for example that in practice, the augmented scheme proposed by Kleinberg is more robust than predicted by the asymptotic behavior, even for very large finite grids. We also propose tighter bounds on the performance of Kleinberg's routing algorithm. At last, we show that fed with realistic parameters, the model gives results in line with real-life experiments.
Type de document :
Communication dans un congrès
20th International Conference on Principles of Distributed Systems (OPODIS 2016), Dec 2016, Madrid, Spain. 〈http://opodis2016.etsisi.upm.es/〉. 〈10.4230/LIPIcs.OPODIS.2016.21〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01417096
Contributeur : Fabien Mathieu <>
Soumis le : jeudi 15 décembre 2016 - 11:57:15
Dernière modification le : dimanche 18 décembre 2016 - 01:02:40
Document(s) archivé(s) le : jeudi 16 mars 2017 - 17:57:52

Fichiers

OPODIS2016-camera-ready-paper9...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Relations

Citation

Fabien Mathieu. Kleinberg's Grid Reloaded. 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Dec 2016, Madrid, Spain. 〈http://opodis2016.etsisi.upm.es/〉. 〈10.4230/LIPIcs.OPODIS.2016.21〉. 〈hal-01417096〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

52