Skip to Main content Skip to Navigation
Master Thesis

Neighbor-of-Neighbor Routing In Small-World Networks With Power-Law Degree

Abstract : During this internship, we have studied decentralized routing in small-world networks. Our model is a variant of Kleinberg's model: we use a 1-dimensional grid in which the number of long-range contacts is not a constant but instead follows a power law probability distribution, the edges are considered bidirectional and drawn independently: they follow a harmonic distribution as in Fraigniaud and Giakkoupis work ([13]). We increase the number of neighbors to an expected O(ln n) number of neighbors instead of a constant expectation as in the previous work. We also increase knowledge to every node: they know the neighbors of their neighbors. This model was motivated by Kleinberg in [16] and by the work of Manku, Naor and Wieder ([23]) who have shown that this improves the e fficiency of routing to an optimal expected value in their model. We proved that the expected number of steps for routing a message in this model using a greedy algorithm, with respect to the knowledge the nodes have, is O(1) which is optimal.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://dumas.ccsd.cnrs.fr/dumas-00854954
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy <>
Submitted on : Wednesday, August 28, 2013 - 2:05:51 PM
Last modification on : Monday, February 15, 2021 - 10:38:28 AM
Long-term archiving on: : Monday, December 2, 2013 - 8:50:40 AM

Identifiers

  • HAL Id : dumas-00854954, version 1

Citation

Olivier Ruas. Neighbor-of-Neighbor Routing In Small-World Networks With Power-Law Degree. Distributed, Parallel, and Cluster Computing [cs.DC]. 2013. ⟨dumas-00854954⟩

Share

Metrics

Record views

423

Files downloads

218