A Virtual Ring Method for Building Small-World Structured P2P Overlays

This paper presents a general virtual ring method to design and analyze small-world structured P2P networks on the base topologies embedded in ID spaces with distance metric. Its basic idea is to abstract a virtual ring from the base topology according to the distance metric, then build small-world long links in the virtual ring and map the links back onto the real network to construct the small-world routing tables for achieving logarithmic greedy routing efficiency. Four properties are proposed to characterize the base topologies that can be turned into small-world by the virtual ring method. The virtual ring method is applied to the base topologies of d-torus with Manhattan distance, high dimensional d-torus base topologies, and other base topologies including the unbalanced d-torus and the ring topology with tree distance. Theoretical analysis and simulation experiments demonstrate the efficiency and the resilience of the proposed overlays.