Neighbor-of-Neighbor Routing In Small-World Networks With Power-Law Degree - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance Access content directly
Master Thesis Year : 2013

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.
Fichier principal
Vignette du fichier
Olivier_Ruas.pdf (385.59 Ko) Télécharger le fichier
Loading...

Dates and versions

dumas-00854954 , version 1 (28-08-2013)

Identifiers

  • HAL Id : dumas-00854954 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More