Z-Ring: Fast Prefix Routing via a Low Maintenance Membership Protocol
Qiao Lian
Wei Chen
Zheng Zhang
Shaomei Wu
Ben Y. Zhao
13th IEEE International Conference on Network Protocols (ICNP 2005)
[Full Text in PDF Format, 416KB]
Paper Abstract
We introduce Z-Ring, a fast prefix routing protocol for peer-to-peer
overlay networks. Z-Ring incorporates a cost-efficient membership protocol to achieve
fast routing with low maintenance costs. Z-Ring achieves routing in log_G(N) steps,
where N is the network size and G is the size of a group that can be maintained by a
membership protocol with low cost. With G=4096, it translates to one-hop routing for
intranet environments (N<4096), two-hop routing for mid-scale internet applications
(N<16 million), and three-hop routing for ultra-large internet applications (N<64
billion). Z-Ring maintains good routing success rates under churn and low maintenance
costs even at large network sizes. Its modularized use of the membership protocol also
makes it adaptive to dynamic and wide-range network size changes.