对等网络中一种新的非集中式查找算法

A Novel Decentralized Location Algorithm for Peer-to-Peer Networks

提出了一种适用于对等网络环境的非集中式查找算法,它具有可扩展、自组织、高容错等特性,能够自动适应网络中节点的加入、退出和失效.该算法的时间复杂度和空间复杂度均为O(logN).算法的基本思想是:将有限大小的线性空间平均划分为M等份,对每等份的子空间递归划分为M等份,直到每个子空间对应一个点;采用Hash算法将网络中的数据或节点映射为线性空间中的一点,每个节点本地存储一个路由表,其内容为其各个划分层次中的对应点所在位置信息;这样,一个节点可以在不超过O(logN)次转跳的情况下找到目的节点.仿真实验结果表明:当M增大时,算法的查找性能也会提高;当M=16,网络规模为104个节点时,算法的平均查找长度仅是Pastry、Tapestry算法的70%左右.

This paper sketched out the design of a decentralized, scalable, self-organizing and fault-tolerant location algorithm for peer-to-peer networks. The principle of the algorithm is as follows. A finite linear space, whose size is M^k, is evenly divided into M parts. Again, the sub-part is recursively divided into M equal parts until all sub-parts can only contain one unit(point). Data and nodes' identifiers can be mapped onto the points of the linear space by using a hash function. Each node's routing table contains the location information of a small subset of other nodes, whose identifiers have some special relations to the present node's identifier in the linear space. With the routing table, one node can locate other node that is responsible for the given data items within O(log N) hops. The results from simulation experiments show that increasing the value of M can enhance the routing performance of the algorithm. In a simulation network with 10~4 nodes, if the value of M is 16, the average locating path length of the algorithm is only 70% of that of Pastry and Tapestry.