Long Range Contacts in Overlay Networks

F. Araújo and L. Rodrigues

Selected sections of this report will be published in the Proceedings of the Euro-Par 2005, Lisboa, Portugal, August 2005.

Abstract

In this paper we present and evaluate a novel mechanism, called Hop Level, that creates and maintains long range contacts (LRCs) in overlay networks. The Hop Level mechanism owns the following characteristics: i) lazy creation of the LRCs, ii) support for unbalanced node distribution, iii) support for multidimensional spaces and iv) near-optimal path lenght/node degree trade-off. These characteristics make Hop Level specially suited for overlay networks that support range data queries (as opposed to distributed hash tables that only support exact queries) with one or more dimensions. Furthermore, and unlike previous similar work, Hop Level can handle churn very well, because it postpones creation of the LRCs until it is necessary. In this way, nodes that have short lives do not overload the network with their state update requests.

Also available extended report, (pdf) .

Luís Rodrigues