An efficient load balancing method for constant degree P2P systems

Constant degree P2P systems are turning into the P2P domain´s promising hotspot due to their good properties. However, it is often hard to convert a standard constant degree digraph to a flexible DHT schema adapting to dynamic P2P environments. Thus, most research about constant degree P2P focus on DHT´s construction and maintenance, while leaving optimization and supporting to upper-layer application behind, such as complex query, load balance, etc. Combining constant degree topology´s bit-shift routing schema, we presents an efficient load balancing algorithm based on Reverse Spanning Tree (REST) for constant degree P2P systems. Using the statistic information in joining process, REST judges how many Virtual Servers that a new join super peer can run, and then join all virtual servers evenly and fast with low cost based on the Spanning Tree Peer Set. Experimental results show, without additional data structure, REST keeps the constant degree P2P system load-balanced by assuring each peer of owning a key space proportional to its capability.