对等网络中分布式查找算法的分析比较

A Survey of Decentralized Lookup Algorithms in Peer-to-Peer Networks

对等网络中的分布式查找算法可分为结构性和非结构性的,它们在查找机制、网络拓扑和查找效率等方面存在一些共性及区别.经过综合比较后发现,查找算法在不同指标上存在一定的权衡,如为了提高某一个指标(如时间复杂性),必然以牺牲另外的指标(如空间复杂性或网络负载)为代价.在将复杂查询加以改进后可以将文件查找算法应用到其他领域(如网格计算)中作为分布式查找的基础,为设计新的查找算法和扩展P2P查找算法的应用领域提供了重要参考.

The paper divided the decentralized lookup algorithms in peer-to-peer networks into two classes: structured and unstructured. The lookup mechanisms, network topology and lookup efficiency of these two types of algorithms were compared. From the comparison, it is concluded that there exists tradeoff in lookup algorithms. For example, to improve the time efficiency, the algorithm has to increase the routing table size or network overhead. The paper can be a reference for the design of new lookup algorithms or...