一种基于节点异质性降低跳图维护代价的方法  

A New Algorithm to Reduce Maintenance Overhead of Skip Graphs Based on Node Heterogeneity

作　　者：吴恒奎[1] 高德云[1] 张宏科[1] 

机构地区：[1]北京交通大学电子信息工程学院,北京100044

出　　处：《北京交通大学学报》2010年第2期43-47,共5页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

基　　金：国家"973"计划项目资助(2007CB307106;2007CB307101);国家自然科学基金资助项目(60833002)

摘　　要：Skip Graphs提供了一种新的P2P查找算法,但是其系统查询和维护的消息流量巨大,限制了其应用.本文通过构造节点异质性模型,充分考虑节点异质性和节点负载的关系,提出新的Skip Graphs++算法,有效降低系统的维护代价10%～30%,并从理论和仿真两方面进行证明.Skip Graphs can provide novel distributed data structures for peer-to-peer（P2P） searching,but they suffer from the problems of high storage requirements and high volume of repair-mechanism message traffic.In order to solve these problems,we propose a new algorithm,Skip Graphs＋＋,which constructs a new node capacity model to evaluate the performance of nodes in the system and builds the relationship between the loads and the capacities of nodes.Theoretical and experimental results show that the maintenance overhead can be reduced by 10%～30% with the node heterogeneity.

关 键 词：跳表 跳图 维护代价 异质性 P2P网络 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术]