License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.21
URN: urn:nbn:de:0030-drops-70908
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7090/
Go to the corresponding LIPIcs Volume Portal

Mathieu, Fabien

Kleinberg’s Grid Reloaded

pdf-format:
LIPIcs-OPODIS-2016-21.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{mathieu:LIPIcs:2017:7090,
  author =	{Fabien Mathieu},
  title =	{{Kleinberg’s Grid Reloaded}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7090},
  URN =		{urn:nbn:de:0030-drops-70908},
  doi =		{10.4230/LIPIcs.OPODIS.2016.21},
  annote =	{Keywords: Small-World Routing,Kleinberg’s Grid, Simulation, Rejection Sampling}
}

Keywords: Small-World Routing,Kleinberg’s Grid, Simulation, Rejection Sampling
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI