Abstract
Many large-scaled servers are implemented as a peer-to-peer (P2P) distributed system to avoid centralized management and increase scalability. Traditional P2P lookup protocols often utilize binomial lookup trees to shorten lookup paths. Such a lookup protocol introduces routing bottlenecks when certain nodes become hot spots. In this paper, we present a scalable and load-balanced P2P lookup protocol called SCALLOP. This protocol utilizes balanced lookup trees to evenly distribute routing traffic among nodes and, therefore, reduce or eliminate the occurrence of routing bottlenecks. SCALLOP achieves scalability by storing in each node O(log N) routing information in an N-node distributed system. Furthermore, a self-organized mechanism is proposed to efficiently recover a system when nodes join, leave, and fail dynamically. We conduct a series of experiments to compare SCALLOP and Chord, the most-referenced and representative binomial lookup protocol. The experimental results show that, with balanced lookup trees, SCALLOP delivers more balanced routing loads and avoids routing bottlenecks. In addition, its customizable feature reduces lookup paths and the total number of routed requests at the cost of larger lookup tables.