基于Small-World网络的非结构化DHT算法

目前，非结构化的P2P路由算法面临着搜索效率低下的严峻问题，这严重影响了非结构算法的应用领域．提出一种基于关键字聚类的分布式哈希表算法，主要思路是将环状关键字空间分成上下两层，下层(AUT层)负责关键字管理，上层(HUB层)负责节点路由．每个节点用一个随机数值作为它的聚类中心，从过往的路由消息中本地节点将抽取文件关键字和节点聚类中心，以聚类原则将这些数据记录到本地路由表中．除了改进非结构化算法的数据组织无序性，另一个目标是提高搜索效率．于是，上述算法的增强算法利用了small-world理论，在HUB层中加入远距离节点的聚类中心，将确定性聚类转化为概率性聚类，故能保证路由长度为O(log^2N)．

A Peer-to-Peer DHT Algorithm Based on Small-World Network

Efficient search technology is a primary key to peer-to-peer systems. In order to address the inefficient routing problem, a DHT algorithm is presented based on the policy of clustering keys of sharing files. Under the key clustering algorithm, the ring-like key space is divided into two layers. Meanwhile, each node obtains a randomly assigned numeric value as its clustering center in key space. The lower layer, which is called AUT layer, is responsible for managing files' keys. The upper layer, HUB layer, is responsible for maintaining the clustering center of nodes. According to the AUT layer and the HUB layer separately, file keys and node clustering centers discovered from bypassing routing messages are clustered towards the clustering center of local node. The algorithm solves the problems of present unstructured algorithms in some degree, in which the datum is organized in a confused situation and routing is proceed in a disordered manner. Further, the outcome of small-world is used to cut down latency of routing hops. To improve the algorithm, a few connections to remote nodes are introduced with a suitable probability into routing table of clustering keys. In another word, the criterion of clustering is not of determination, but of probability. In this way, it is possible to route overlay network with average latency of O (log2 N) hops.