Hybrid Overlay Structure Based on Random Walks

Ruixiong Tian
Yongqiang Xiong
Qian Zhang
Bo Li
Ben Y. Zhao
Xing Li

Fourth International Workshop on Peer-to-Peer Systems (IPTPS 2005)

[Full Text in GZIP PS Format, 316KB]
[Full Text in PDF Format, 410KB]


Paper Abstract

Application-level multicast on structured overlays often suffer several drawbacks: 1) The regularity of the architecture makes it difficult to adapt to topology changes; 2) the uniformity of the protocol generally does not consider node heterogeneity. It would be ideal to combine the scalability of these overlays with the flexibility of an unstructured topology. In this paper, we propose a locality-aware hybrid overlay that combines the scalability and interface of a structured network with the connection flexibility of an unstructured network. Nodes self-organize into structured clusters based on network locality, while connections between clusters are created adaptively through random walks. Simulations show that this structure is efficient in both delay and bandwidth. The network also supports the scalable fast rendezvous interface provided by structured overlays, resulting in fast membership operations.