论文:2015,Vol:33,Issue(2):342-350
引用本文:
卢苇, 周韬, 邢薇薇. 一种改进的非结构化P2P网络洪泛搜索机制[J]. 西北工业大学学报
Lu Wei, Zhou Tao, Xing Weiwei. An Improved Flooding Based Search Mechanism in Unstructured P2P Network[J]. Northwestern polytechnical university

一种改进的非结构化P2P网络洪泛搜索机制
卢苇, 周韬, 邢薇薇
北京交通大学软件学院, 北京 100044
摘要:
非结构化P2P网络使用基于洪泛的查询算法来进行资源搜索。然而,这种搜索机制随着网络节点的增多,网络规模的增大,将产生大量的冗余查询消息,会导致网络流量急剧增加,引起网络拥塞。提出了一种基于转发区间的洪泛搜索机制FIFSM(forwarding interval based flooding search mechanism),通过为消息分配不相交的转发区间,使其沿着一棵生成树的结构传播,消除了消息环路,从而避免冗余消息的产生。FIFSM机制采用高效的网络维护策略,能够在动态环境下以较低的开销保证网络的稳定性。实验结果表明,FIFSM机制能够降低洪泛开销,保证资源搜索的高成功率和低延迟,是一种有效的非结构化P2P网络资源搜索机制。
关键词:    算法    计算机系统    资源优化    故障检测    容错性    网络管理    网络性能    丢包率    对等网络    可靠性分析    稳定性    时延    拓扑结构    非结构化P2P网络    洪泛搜索    转发区间    生成树   
An Improved Flooding Based Search Mechanism in Unstructured P2P Network
Lu Wei, Zhou Tao, Xing Weiwei
School of Software Engineering, Beijing Jiaotong University, Beijing 100044, China
Abstract:
In the unstructured P2P networks, the flooding-based search algorithm is used to search resources; however, with increasing nodes and network scale, flooding-based search will produce large amount of redundant query messages, which will lead to heavy traffic and congestion of the network. We propose a Forwarding Interval based Flooding Search Mechanism (FIFSM). By assigning a disjoint forwarding interval to each message, they spread along a spanning tree to avoid message loops, thus eliminating redundant messages. The efficient network maintenance strategy is presented in FIFSM; this ensures the stability of the network in dynamic environment at a very low cost. Experimental results and their analysis show preliminarily that FIFSM, as an efficient search mechanism in unstructured P2P network, can reduce flooding overhead and achieve high success rate of resource search and low latency.
Key words:    algorithms    computer system    cost reduction    fault detection    fault tolerance    network management    network performance    packet loss    peer to peer networks    reliability analysis    stability    time delay    topology    unstructured P2P networks    flooding search    forwarding interval    spanning tree   
收稿日期: 2014-09-02     修回日期:
DOI:
基金项目: 国家自然科学基金(61100143、61370128、61272353)、教育部新世纪人才计划项目(NCET-13-0659)与北京高校青年英才计划项目(YETP0583)资助
通讯作者:     Email:
作者简介: 卢苇(1963-),北京交通大学教授,主要从事软件服务工程研究。
相关功能
PDF(1419KB) Free
打印本文
把本文推荐给朋友
作者相关文章
卢苇  在本刊中的所有文章
周韬  在本刊中的所有文章
邢薇薇  在本刊中的所有文章

参考文献:
[1] Ratnasamy S, Francis P, Handley M, et al. A Scalable Content-Addressable Network[C] //Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, New York:ACM Press, 2001:149-160
[2] Rowstron A I T, Druschel P. Pastry:Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[C] //Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Springer-Verlag, 2001
[3] Stoica I, Morris R. Chord:A Scalable Peer-to-Peer Lookup Service for Internet Applications[J]. ACM Sigcomm Computer Communication Review, 2001, 31(4):149-160
[4] Clip2com. The Gnutella Protocol Specification. http://rfc-gnutella.sourceforge.net/Development, 2010
[5] Cohen E, Shenker S. Replication Strategies in Unstructured Peer-to-Peer Networks[J]. ACM Sigcomm Computer Communication Review, 2002, 32(4):177-190
[6] Morselli R, Bhattacharjee B. Efficient Lookup on Unstructured Topologies[J]. IEEE Journal of Communications, 2007, 25(1):62-72
[7] Ritter J. Why Gnutella Can't Scale. No, Rea-lly. http://www.darkridge.com/~jpr5/doc/gnutella.html, 2001
[8] 朱桂明,郭得科,金士尧,等.基于副本复制和Bloom Filter的P2P概率路由算法[J].软件学报,2011, 22(4):773-781 Zhu Guiming, Guo Deke, Jin Shiyao, et al. P2P Probabilistic Routing Algorithm Based on Data Copying and Bloom Filter[J]. Journal of Software, 2011, 22(4):773-781(in Chinese)
[9] Kitamura H, Fujita S. A Biased k-Random Walk to Find Useful Files in Unstructured Peer-to-Peer Networks[C] //2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, 2009:210-216
[10] 叶培顺.非结构化P2P网络的一种改进搜索算法[J].计算机与现代化, 2013(12):44-47 Ye Peishun. Improved Search Algorithm for Unstructured P2P Network[J]. Computer and Modernization, 2013(12):44-47(in Chinese)
[11] 马文明,孟祥武,张玉洁.面向非结构化P2P网络的双向随机漫步搜索机制[J].软件学报, 2012, 23(4):894-911 Ma Wenming, Meng Xiangwu, Zhang YuJie. Bidirectional Random Walk Search Mecha-Nism for Unstructured P2P Network[J]. Journal of Software, 2012, 23(4):894-911(in Chinese)
[12] Gkantsidis C, Mihail M, Saberi A. Random Walks in Peer-to-Peer Networks[C] //IEEE Conference on Computer Communications, 2004:120-130
[13] Jagadish H V, Ooi B C, Vu Q H. BATON:a Balanced Tree Structure for Peer-to-Peer Networks[C] //Proceedings of the 31st International Conference on Very Large Data Bases, 2005
[14] Hu Z. Improved Algorithm of Unstructured P2P Network Topology Structure[C] //2009 International Symposium on Intelligent Ubiquitous Computing and Education, 2009:358-361
[15] 杨亚,宋俊德.一种适合异构P2P网络的树形结构覆盖层[J].高技术通讯, 2009, 19(3):230-236 Yang Ya, Song Junde. TSOHEN:a Tree Structure Overlay for Heterogeneous P2P Networks[J]. Chinese High Technology Letters, 2009, 19(3):230-236(in Chinese)
[16] Castro M, Costa M, Rowstron A. Should We Build Gnutella on a Structured Overlay?[J] ACM Siggomm Computer Communication Review, 2004, 34(1):131-136
[17] Elansary S, Alima L O, et al. Efficient Broadcast in Structured P2P Networks[J]. Peer-to-Peer Systems Ⅱ, 2003, 2735:304-314
[18] 林雅榕,侯整风.对哈希算法SHA-1的分析和改进[J].计算机技术与发展, 2006, 16(3):124-126 Lin Yarong, Hou Zhengfeng. Analysis and Improvement to Algorithm of SHA-1[J]. Computer Technology And Development, 2006, 16(3):124-126(in Chinese)
[19] Melamed R, Keidar I. Araneola:A Scalable Reliable Multicast System for Dynamic Environments[J]. Journal of Parallel and Distributed Computing, 2008, 68(12):1539-1560
相关文献:
1.杨立本, 章卫国, 黄得刚, 车军.欠驱动四旋翼飞行器反演模糊自适应控制[J]. 西北工业大学学报, 2015,33(3): 495-499
2.郑炜, 李知隆, 靳如一.基于频率差异积分的故障定位算法研究[J]. 西北工业大学学报, 2013,31(3): 435-439
3.周勇, 张玉峰, 张超, 张举中.基于Sage-Husa的线性自适应平方根卡尔曼滤波算法[J]. 西北工业大学学报, 2013,31(1): 89-93