Locality-Aware and Low Maintenance Overhead P2P System

C.-J. Wu, D.-K. Liu, and R.-H. Hwang (Taiwan)


Peer-to-Peer, Overlay Network


This work describes a novel locality-aware structured peer-to-peer (P2P) overlay network, referred to as LAPTOP. One important aspect of constructing a structured P2P network is how to reduce the maintenance overheads while maintaining efficient routing and network locality. LAPTOP organizes nodes into a tree based overlay network in a self-organizing manner and builds the routing table by taking network locality into account. The tree-based overlay network enables LAPTOP to utilize the parental relation to reduce the overheads of overlay maintenance. Moreover, LAPTOP adopts proximity neighbor selection (PNS) in the routing table construction to achieve low routing latency. Mathematical analysis and simulations are conducted to evaluate the efficiency and scalability of LAPTOP. The mathematical analysis performed here demonstrates that the routing table size of a node is bounded by logd N ×(d 1), the routing path length is bounded by logd N, and the joining and leaving overhead is bounded by d logd N, where N denotes the number of nodes in the system and d represents the maximum degree of each node on the overlay tree. Our simulation results show that the average path stretch and routing path length are just 1.48 and 3.8, respectively, in a system of 100 000 nodes with a maximum degree of 16 . Compared to previous research, the proposed LAPTOP approach reduces overlay maintenance overheads while still providing efficient routing.

Important Links:

Go Back