TypeSampler:一种基于gossip 的类型采样方法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(60873215); 国家重点基础研究发展计划(973)(2011CB302601); 湖南省自然科学杰出青年基金(S2010J5050); 高等学校博士学科点专项科研基金(200899980003)


TypeSampler: A Type Sampling Approach Based on Gossip
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在很多P2P 应用中,节点可以根据其兴趣或资源划分为不同的类型,而以特定类型节点为目标的基于覆盖网的路由也就成为实现数据分发及查询的关键.非结构化覆盖网具有维护开销低、鲁棒性高的优点,却也因此难以保证路由效率.提出了一种基于gossip 的类型采样方法——TypeSampler,它以等概率采样不同类型的节点(称为类型采样),以此保证在任意节点发现特定类型邻居节点的概率下界,进而保证非结构化覆盖网中的路由效率.为了实现类型采样,TypeSampler 首先通过基于gossip 的节点采样及反熵聚集估计各类型节点的比例,然后,TypeSampler 再根据这些比例估计值周期性地维护每个节点的类型采样表.理论分析与实验结果表明,TypeSampler 能够实现精确的类型比例估计以及近似均匀随机的类型采样,并能适应动态的网络环境.而且相对于已有的方法,TypeSampler 能够支持更高效的路由,且具有更好的可扩展性.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

郑重,王意洁,马行空,杨永滔. TypeSampler:一种基于gossip 的类型采样方法.软件学报,2012,23(7):1849-1868

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-03-05
  • 最后修改日期:2011-05-18
  • 录用日期:
  • 在线发布日期: 2012-07-03
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号