Degree-Optimal Routing for P2P Systems |
| |
Authors: | Giovanni Chiola Gennaro Cordasco Luisa Gargano Mikael Hammar Alberto Negro Vittorio Scarano |
| |
Affiliation: | (1) DISI, Università di Genova, via Dodecaneso 35, 16146 Genova, Italy;(2) DIA, Università di Salerno, via Ponte don Melillo, 84084 Fisciano (SA), Italy;(3) Research & Development, Apptus Technologies AB, IDEON, 223 70 Lund, Sweden |
| |
Abstract: | We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g.
optimal average path length O(log 2
n/δlog δ) with δ degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Ω(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, 2004).
Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing
the NoN technique to be implemented without adding any overhead to the corresponding deterministic network.
We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case (c=1) to an “almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages
of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system.
We also provide a matching lower bound for the average path length of the routing schemes for any c.
This work was partially supported by the Italian FIRB project “WEB-MINDS” (Wide-scalE, Broadband MIddleware for Network Distributed
Services), . |
| |
Keywords: | Peer-to-peer Overlay network Greedy routing |
本文献已被 SpringerLink 等数据库收录! |
|