18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers
SAT-Match: A Self-Adaptive Topology Matching Method to Achieve Low Lookup Latency in Structured P2P Overlay Networks
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
A peer-to-peer (P2P) system is built upon an overlay network whose topology is independent of the underlying physical network. A well-routed message path in an overlay network with a small number of logical hops can result in a long delay and excessive traffic due to undesirably long distances in some physical links. In this paper, we propose an effective method, called SAT-Match, to adaptively construct structured P2P overlay networks, aiming at significantly reducing the lookup routing latency. In this method, each joining peer is initially guided to find a physically close neighbor to connect with. After then, its overlay location is adaptively adjusted whenever a location mismatch is detected. The topology matching optimization in our method solely relies on local neighborhood information. Compared with existing topology matching methods, our method addresses their three limitations: (1) heavily relying on global information about the Internet by using landmark-based measurements, (2) lacking adaptation to frequent peer movement in a dynamic environment, such as mobile networks, and (3) insufficiently accurate in topology matching due to the lack of adaptive topology adjustment. We have evaluated our method in the Content-Addressable Network (CAN), a representative structured P2P system with a strong tolerance to frequent peer arrivals/departures. Through intensive simulation experiments on large scale CAN overlays, we have shown the effectiveness of SATMatch. Our method can achieve average logical/physical link latency reduction rate by up to 40% . It also outperforms "landmark binning", a method utilizing global information by up to 20%. Finally, combining with the landmark binning method, SAT-Match can achieve up to 60% latency reduction.
Citation:
Shansi Ren, Lei Guo, Song Jiang, Xiaodong Zhang, "SAT-Match: A Self-Adaptive Topology Matching Method to Achieve Low Lookup Latency in Structured P2P Overlay Networks," ipdps, vol. 1, pp.83a, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers, 2004