Bidirectional random walk search mechanism for unstructured P2P network

被引：6
作者：
Ma, Wen-Ming [1 ,2 ]
Meng, Xiang-Wu [1 ,2 ]
Zhang, Yu-Jie [1 ,2 ]
机构：
[1] Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications
[2] School of Computer Science, Beijing University of Posts and Telecommunications
来源：
Ruan Jian Xue Bao/Journal of Software | 2012年 / 23卷 / 04期
关键词：
Peer-to-peer; Random walk; Search; Tolerance for churn; Topology;
D O I：
10.3724/SP.J.1001.2012.04086
中图分类号：
学科分类号：
摘要：
The improvements of random walk search mainly depend on allocating weight for neighbor peers, which is always incurred on a high overhead and are not very helpful for rare items. This paper proposes a bidirectional random walk search mechanism (short for BRWS) for unstructured P2P network, according to the analysis of basic properties about random walk as well as the special property that random walk tends toward high degree nodes. The mechanism is proved theoretically in this paper, and can improve search success rate, including searching for rare items. It also has a high tolerance for churn. In the static and dynamic environment, comparisons were made among Random Walk, APS (adaptive probabilistic search), PQR (path-traceable query routing), P2PBSN (peer-to-peer based on social network) and BRWS based on three topologies: Random graph, scale free, small world. The experimental results show that BRWS can actually improve the search success rate with lower overhead even when searching rare resources. The method proposed in this paper can apply in P2P file sharing networks. © 2012 ISCAS.
引用
收藏
页码：894 / 911
页数：17
相关论文
共 19 条
  • [1] Zhao B.Y., Kubiatowicz J.D., Joseph A.D., Tapestry: An infrastructure for fault-tolerant wide-area location and routing, pp. 1-27, (2001)
  • [2] Stoica I., Morris R., Karger D., Kaashoek M.F., Balakrishnan H., Chord: A scalable peer-to-peer lookup service for Internet applications, ACM SIGCOMM Computer Communication Reviewm, 31, 4, pp. 149-160, (2001)
  • [3] Druschel P., Rowstron A., PAST: A large-scale, persistent peer-to-peer storage utility, Proc. of the 8th Workshop on Hot Topics in Operating Systems, pp. 75-80, (2001)
  • [4] Rowstron A., Druschel P., Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, ACM SIGOPS Operating Systems Review, 35, 5, pp. 188-201, (2001)
  • [5] Malkhi D., Naor M., Ratajczak D., Viceroy: A scalable and dynamic emulation of the butterfly, Proc. of the Principles of Distributed Computing, pp. 183-192, (2002)
  • [6] Yang B., Garcia-Molina H., Improving search in peer-to-peer networks, Proc. of the 22nd Int'l Conf. on Distributed Computing Systems, pp. 5-14, (2002)
  • [7] Lu Q., Cao P., Cohen E., Li K., Shenker S., Search and replication in unstructured peer-to-peer networks, Proc. of the ACM SIGMETRICS, 2002 Int'l Conf. on Measurement and Modeling of Computer Systems, pp. 258-259, (2002)
  • [8] Kalogeraki V., Gunopulos D., Zeinalipour-Yazti D., A local search mechanism for peer-to-peer networks, Proc. of the Information and Knowledge Management, pp. 300-307, (2002)
  • [9] Gkantsidis C., Mihail M., Saberi A., Random walks in peer-to-peer networks, Proc. of the 23rd AnnualJoint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2004), (2004)
  • [10] Tsoumakos D., Roussopoulos N., Adaptive probabilistic search for peer-to-peer networks, Proc. of the 3rd Int'l Conf. on Peer-to-Peer Computing (P2P 2003), pp. 102-109, (2003)
12