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

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

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.