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
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy Connect in order to contact the contributor
Submitted on : Wednesday, August 28, 2013 - 2:05:51 PM
Last modification on : Tuesday, October 19, 2021 - 11:58:53 PM
Long-term archiving on: : Monday, December 2, 2013 - 8:50:40 AM


  • HAL Id : dumas-00854954, version 1


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



Record views


Files downloads