A structured P2P network based on the small world phenomenon |
| |
Authors: | Jie Xu Hai Jin |
| |
Affiliation: | (1) Services Computing Technology and System Lab., Cluster and Grid Computing Lab., School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China;(2) Faculty of Mathematics and Computer Science, Hubei University, Wuhan, 430062, China |
| |
Abstract: | In this paper, we propose a new structured P2P overlay network, named SW-Uinta(small-world). In order to reduce the routing
latency, we firstly construct the Uinta network in which both physical characteristics of network and data semantic are considered.
Furthermore, based on Uinta, a nondeterministic caching strategy is employed to allow for poly-logarithmic search time while
having only a constant cache size. Compared with the deterministic caching strategy proposed by previous P2P systems, the
nondeterministic caching strategy can reduce communication overhead for maintaining the routing cache table. Cache entries
in the cache table of peer nodes can be updated by subsequent queries rather than only by running stabilization periodically.
In the following, a novel cache replacement scheme, named the SW cache replacement scheme, is used to improve lookup performance,
which has proved to satisfy the small-world principle. So we call this network SW-Uinta(small-world). After that, according
to the theoretical analysis, it can be proved that SW-Uinta(small-world) can get O((log 2
N)/k) search time with O(k) cache size. Lastly, the performance of SW-Uinta(small-world) is compared with those of other structured P2P networks such
as Chord and Uinta. It shows that SW-Uinta(small-world) can achieve improved object lookup performance and reduce maintenance
cost.
|
| |
Keywords: | Peer-to-peer Physical topology Small world phenomenon Cache replacement scheme |
本文献已被 SpringerLink 等数据库收录! |
|