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.