查看文章

We investigate the notion of Long Range Contact graphs. Roughly speaking, such a graph is defined by (1) an underlying network topology G, and (2) one (or possibly more) extra link connecting every node u to a “long distance” neighbor, called the long range contact of u. This extra link represents the a priori knowledge that a node has about far nodes and is set up randomly according to some probability distributions p. To illustrate the claim that Long Range Contact graphs are a good model for the small world phenomenon, we study greedy routing in these graphs. Greedy routing is the distributed routing protocol in which a node u makes use of its long range contact to progress toward a target, if this contact is closer to the target, than the other neighbors. We give upper and lower bounds on greedy routing on the n-node ring C _n augmented with links chosen using the r …