Structured Peer-to-Peer (P2P) protocols provide efficient and scalable key location in overlay networks. These P2P algorithms realize key to node mappings through a Distributed Hash Table (DHT) and assume no centralized components. One of the most appealing features of structured P2P algorithms is their ability to guarantee lookup and memory bounds in the face of frequent membership changes.
Unfortunately, P2P lookup guarantees are given with respect to forwarding hops in the overlay network. Because nodes are uniformly distributed over the P2P identifier space, in practice many inefficiencies occur due to the underlying physical network. In addition, the strict structure of these algorithms also assumes an implicit degree of node uniformity whereas experience has demonstrated ample node heterogeneity.
Chord [1], CAN [2] and Pastry [3] are three of the most studied structured P2P algorithms. A large amount of research has explored various designs that improve on the perceived weaknesses of these systems.
Several designs attempt to mitigate the adverse effects of the network topology by gathering network information and making informed decisions while building the overlay. Ratnasamy et al. [4] use landmark nodes by which nodes measure their RTT. Li [5] explores the potential for utilizing autonomous system information in forming P2P networks.
As part of the Regions project [6], this work explores reorganization and optimization in P2P overlays by using reinforcement learning techniques in the presence of highly heterogenous nodes.