主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
郑重,王意洁,马行空,杨永滔.TypeSampler:一种基于gossip 的类型采样方法.软件学报,2012,23(7):1849-1868
TypeSampler:一种基于gossip 的类型采样方法
TypeSampler: A Type Sampling Approach Based on Gossip
投稿时间:2011-03-05  修订日期:2011-05-18
DOI:10.3724/SP.J.1001.2012.04097
中文关键词:  类型采样  比例估计  路由  非结构化覆盖网  P2P
英文关键词:type sampling  proportion estimation  routing  unstructured overlay network  P2P
基金项目:国家自然科学基金(60873215); 国家重点基础研究发展计划(973)(2011CB302601); 湖南省自然科学杰出青年基金(S2010J5050); 高等学校博士学科点专项科研基金(200899980003)
作者单位E-mail
郑重 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073 zhengzhong@nudt.edu.cn 
王意洁 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073  
马行空 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073  
杨永滔 国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073  
摘要点击次数: 2909
全文下载次数: 3092
中文摘要:
      在很多P2P 应用中,节点可以根据其兴趣或资源划分为不同的类型,而以特定类型节点为目标的基于覆盖网的路由也就成为实现数据分发及查询的关键.非结构化覆盖网具有维护开销低、鲁棒性高的优点,却也因此难以保证路由效率.提出了一种基于gossip 的类型采样方法——TypeSampler,它以等概率采样不同类型的节点(称为类型采样),以此保证在任意节点发现特定类型邻居节点的概率下界,进而保证非结构化覆盖网中的路由效率.为了实现类型采样,TypeSampler 首先通过基于gossip 的节点采样及反熵聚集估计各类型节点的比例,然后,TypeSampler 再根据这些比例估计值周期性地维护每个节点的类型采样表.理论分析与实验结果表明,TypeSampler 能够实现精确的类型比例估计以及近似均匀随机的类型采样,并能适应动态的网络环境.而且相对于已有的方法,TypeSampler 能够支持更高效的路由,且具有更好的可扩展性.
英文摘要:
      In many P2P applications, nodes can be classified into different types according to their interests or resources, and the routing for the nodes with a specified type over overlay networks is the key for data distribution and query in these applications. Unstructured overlays have a low maintenance cost and high robustness, but fail to ensure the routing efficiency. This paper proposes a gossip-based type sampling approach—TypeSampler, which samples the nodes of different types with the same probability (called type sampling). The type sampling ensures the lower bound probability of finding a neighbor node with a specified type at any node, and thus ensures the routing efficiency over the unstructured overlay. For type sampling, TypeSampler first implements the proportion estimation of types through peer sampling and anti-entropy aggregation based on gossip. Next, TypeSampler maintains a type sampling table at each node, periodically, based on the estimated proportion values. Theoretical analysis and experimental results reveal that TypeSampler can not only achieve precise proportion estimation and approximately uniform random type sampling, but can also work well even in the dynamic network environment. Moreover, TypeSampler can support more efficient routing and has better scalability compared to the existing approaches.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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