We define a family of distributed hash table systems whose aim is to combine routing efficiency of the randomized networks - i.e. average path length O(log n/log log n) vs. the O(log n) average path length of the deterministic system - with the programmability and startup efficiency of a uniform system - that is a system in which the overlay network is transitive, and greedy routing is optimal. It is known that Ω(logn) is a lower bound to the average path length for uniform systems with O(log n) degree. The proposed family is parameterized with a positive integer c which measures the amount of randomness that is used. Indeed, edges are partitioned into c equivalence classes. 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 routing with 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 family of routing schemes for any c. Moreover, we show how to extend the result to other overlay networks.

Overlay networks with class

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

Abstract

We define a family of distributed hash table systems whose aim is to combine routing efficiency of the randomized networks - i.e. average path length O(log n/log log n) vs. the O(log n) average path length of the deterministic system - with the programmability and startup efficiency of a uniform system - that is a system in which the overlay network is transitive, and greedy routing is optimal. It is known that Ω(logn) is a lower bound to the average path length for uniform systems with O(log n) degree. The proposed family is parameterized with a positive integer c which measures the amount of randomness that is used. Indeed, edges are partitioned into c equivalence classes. 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 routing with 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 family of routing schemes for any c. Moreover, we show how to extend the result to other overlay networks.
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/3136857
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 1
social impact