This paper proposes a new scheme for p2p networks. The main contributions are an extensive use of randomization techniques and a novel usage of tree-data structure. The combination of these two ingredients allows a great flexibility of network parameters, such as: load balance among the peers, fast lookups and reduced memory usage. For instance, with routing tables of size $(d-1) log_d n$, the average number of hops for a lookup is of the order of $1/d((d-1) log_d n +1)$, where n is the number of peers in the network and d is the ariety of the tree data structure. Further, we propose a few new optimization mechanisms that can be adopted in DHT. Extensive simulations support these results.
BaRT, balanced randomized tree: A scalable and distributed protocol for lookup in peer-to-peer networks
2004
Abstract
This paper proposes a new scheme for p2p networks. The main contributions are an extensive use of randomization techniques and a novel usage of tree-data structure. The combination of these two ingredients allows a great flexibility of network parameters, such as: load balance among the peers, fast lookups and reduced memory usage. For instance, with routing tables of size $(d-1) log_d n$, the average number of hops for a lookup is of the order of $1/d((d-1) log_d n +1)$, where n is the number of peers in the network and d is the ariety of the tree data structure. Further, we propose a few new optimization mechanisms that can be adopted in DHT. Extensive simulations support these results.File | Dimensione | Formato | |
---|---|---|---|
prod_91058-doc_125340.pdf
solo utenti autorizzati
Descrizione: BaRT, Balanced Randomized Tree: A scalable and distributed protocol for lookup in peer-to-peer networks
Tipologia:
Versione Editoriale (PDF)
Dimensione
126.84 kB
Formato
Adobe PDF
|
126.84 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.