Building a Network-Aware and Load-Balanced Structured Peer-to-Peer System for Range Query

We present a structured P2P system called Donuts, which exploits proximity, achieves load balance, and supports range query. The motivation is that range query incurs many overlay contiguous traverses, so making overlay neighbors physically nearby can significantly reduce communication costs. However, building a proximity-aware network may compromise load balance, as efficient load balance requires flexibility of node placement so that a lightly loaded node can leave its position to join beside a heavily loaded node to share its load. To resolve the conflict, we introduce a new concept - grouping. The idea is to cluster physically nearby nodes into several overlay sections to increase the flexibility of proximity join, routing, and load balancing while maintaining key ranges in neighboring nodes adjacent. Moreover, grouping can improve search efficiency by taking advantage of cache. It can also increase fault tolerance, especially to local catastrophes. In the following we introduce Donuts by starting from a simple model and gradually moving into a refined and sophisticated one.