Hierarchical P2P Systems in a Small World

Hierarchical organizations in general boost overall system scalability. Some existing research work organizes peers into different hierarchical structures. In these systems, the top-tier overlay is either a completely-connected graph or a CHORD ring. These overlays can achieve good routing latency ()1(O or)(lognO), where n is the number of groups. However, each node has to keep a large number (n or)(lognO) of TCP connections to other nodes on the top-tier. More connections means more work on the underlying network and more interference between nodes. In this paper, we propose a novel small-world top-tier overlay that reduces the routing state to)1(O. The routing latency is)(log2 nO. In our approach, each peer on the top-tier overlay is equipped with some short links and some random long links. The simulation result demonstrates the effectiveness of our approach