Efficient Routing in Networks with Long Range Contacts

摘要: 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 "long distance" neighbor, called long range contact u. This represents priori knowledge that has about far nodes set up randomly according some probability distributions p. To illustrate claim graphs are good model for small world phenomenon, we study greedy routing in these Greedy distributed protocol which makes use its progress toward target, if this closer than other neighbors. give upper lower bounds on n-node ring Cn augmented with links chosen using r-harmonic distributions. In particular, show tight ?(log2 n)-bound expected number steps required 1-harmonic distribution. Hence, our shows Kleinberg [11] can be simplified rather mesh while preserving main features model. Our also demonstrates significant difference (in term both diameter routing) between contacts harmonic distribution random matching as introduced Bollobas Chung [3]. Finally, epimorphisms onto another, any how define p performance G For appropriate embeddings (if they exist), turns out O(log2 n).