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.
Loading...