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(log2 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. 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.

Degree-Optimal Routing for P2P Systems

GARGANO, Luisa;NEGRO, Alberto;SCARANO, Vittorio
2009

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(log2 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. 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/2500052
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact