``SAT-Match: a self-adaptive topology matching method to achieve 
low lookup latency in structured P2P overlay networks"  

Shansi Ren, Lei Guo, Song Jiang, and Xiaodong Zhang 

Proceedings of the 18th International Parallel and Distributed Processing 
Symposium (IPDPS'04), April 26-30, 2004. 

Abstract

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 SAT-Match. 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.