Collision Avoidance in Hierarchical Peer-to-Peer Systems

In a two-level chord-based hierarchical peer-to-peer system, nodes from the first-level overlay network, called supernodes, act as gateways to peers organized in the second-level overlay. Collision occurs when peer-to-peer operations create more than one supernode with the same node identifier in the first-level overlay. Collisions are reported to enlarge first-level overlay by more than 12 times the ideal size and thus increase the lookup path length. Other consequences of collisions include lookup failures even though the lookup resources exist in the network and reduced scalability of the system. In contrast to collision detection and correction techniques, this paper proposes: (i) a collision-free approach for the join and leave operations, and (ii) a new stabilization scheme to recover from second-level overlay node failures. However, avoiding collision due to supernode failures is complex and remains a challenge. Simulation results show that collisions can be avoided and our algorithms improve the overall system performance.