XRing: Achieving High-Performance Routing Adaptively in Structured P2P

  • Zheng Zhang ,
  • Qiao Lian ,
  • Yu Chen

MSR-TR-2004-93 |

P2P DHT has emerged as a scalable way to pool together potentially an unlimited amount of resources in a complete self-organizing manner. Many of the current proposals, however, are dominated by the minimalist principle, i.e. achieving O(logN) performance with O(logN) state. These designs, while elegant, undershoot in a number of interesting deployment situations where either the churn rate is low or system size is moderate. We argue that the amount of state is not an issue, the quality and the associated efforts are. From this perspective, an ideal DHT should reach the optimal performance for a given bandwidth budget. It should also be robust, in the sense that the system should weather storm of events during which the performance degrades gracefully and rapidly return to normal level afterwards. The research and development of XRing is our attempt to strive towards this goal. XRing embeds an O(logN) finger table that guarantees the worst-case O(logN) performance, much like other approaches. The novelty of XRing is to turn these fingers into a reliable broadcast venue instead and therefore delivers 1-hop routing to any nodes when system size is moderate (e.g. 4K) or churn rate is low (e.g. corporate internal cluster), with a very low bandwidth budget (e.g. 5kb/s). By combining intelligent buffering that prunes away redundant traffic and optimal shaping of routing table, we show how XRing can adaptively yield O(1) performance for very large system size robustly.