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.