主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
朱桂明,郭得科,金士尧.基于衰落Bloom Filter 的P2P 网络弱状态路由算法.软件学报,2011,22(11):2810-2819
基于衰落Bloom Filter 的P2P 网络弱状态路由算法
P2P Weak State Routing Scheme Based on Decaying Bloom Filters
投稿时间:2009-07-07  修订日期:2010-03-01
DOI:10.3724/SP.J.1001.2011.03863
中文关键词:  对等计算  有向随机网络  弱状态路由  衰落Bloom Filter  噪音
英文关键词:peer-to-peer computing  directed random network  weak state routing  decaying Bloom Filter  disturbance
基金项目:国家自然科学基金(60903206, 61170284, 60970094, 61003304); 中国博士后科学基金(201104439); 湖南省自然科学基金(09ZZ4034); 国防科学技术大学预先研究项目(JC10-05-01)
作者单位E-mail
朱桂明 国防科学技术大学 计算机学院 并行与分布处理国防科技重点实验室,湖南 长沙 410073
江南计算技术研究所,江苏 无锡 214083 
guiming.zhu@yahoo.com.cn 
郭得科 国防科学技术大学 信息系统与管理学院 信息系统工程国防科技重点实验室,湖南 长沙 410073  
金士尧 国防科学技术大学 计算机学院 并行与分布处理国防科技重点实验室,湖南 长沙 410073  
摘要点击次数: 2999
全文下载次数: 3089
中文摘要:
      在P2P 网络中,基于衰落Bloom Filter 的弱状态路由算法试图将每条查询消息沿着成员资格信息量最强的方向传递,并最终以较低的传输代价和传输时延确保较高的查准率.衰落Bloom Filter 在传递过程中存在严重的多径叠加和噪音问题,这直接导致查询消息会以很高的概率沿着错误的方向传播,甚至会退化为泛洪路由算法.为了解决这一挑战性难题,提出了DWalker 这种基于衰落Bloom Filter 的高效弱状态路由算法.DWalker 基于有向随机网络,采用指数衰落Bloom Filter 来发布和传播每个节点共享资源的信息,且其最大传播距离小于网络中任意两点之间距离的期望值,从而有效抑制了衰落Bloom Filter 在传播过程中的多径叠加问题.DWalker 采用多个Bloom Filter 而不是单个Bloom Filter 来表达一项路由条目,在单个Bloom Filter 的错误发生概率达到设计上限时,可按需动态增加新的Bloom Filter,以将更多资源对象信息纳入到当前路由条目中.DWalker 仅根据当前节点的各项路由条目中值为1 的比特位所占的最大比例,以及查询消息在正确转发方向对应的路由条目中对应比特位中值为1 的个数的临界值,就能使进入目标对象传播范围内的查询消息以较高的概率辨认出正确的路由方向.理论分析和实验结果表明,DWalker 能够以较低的查询消息代价、较小的路由条目存储开销以及较短的查询时延,使绝大多数查询消息沿正确方向转发,从而获得较高的查准率.
英文摘要:
      The current weak state routing schemes cannot facilitate in-network queries effectively. When a query is given for an item at an arbitrary node, disturbance in unrelated routing entries are likely stronger than the useful information in the right routing entries. Consequently, the majority of queries are moved towards wrong nodes. To solve this problem, this paper presents DWalker, an efficient weak state routing scheme-based design based on decaying bloom filters. DWalker uses a bloom filter to represent the summary information of resources at each node and then propagated a bloom filter within a propagation range. The amount of information in each bloom filter decreases exponentially with the distance from the source. DWalker makes the max propagation range less than the expected distance between any two nodes; hence, effectively tackling the problem of multi-path propagation of a decaying bloom filter. DWalker replaces a single bloom filter with multiple bloom filters as a routing entry and holds more routing information. DWalker can ensure that any query can be forwarded in the right direction with high a probability that is based on the proportion of bits set to 1 in a bloom filter and the least number of bits set to 1 in an entry bloom filter for a query. The analysis and simulation of results show that DWalker can make many queries that can be forwarded in the right direction to achieve a high query hit rate with low cost and low delay.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利