对P2P技术的影响

yaomingwei_ren

一、度数和直径的这种关系（tradeoff）对发现算法的影响
    DHT发现技术完全建立在确定性拓扑结构的基础上，从而表现出对网络中路由的指导性和网络中节点与数据管理的较强控制力。但是，对确定性结构的认识又限制了发现算法效率的提升。研究分析了目前基于DHT的发现算法，发现衡量发现算法的两个参数度数（表示邻居关系数，路由表容量）和链路长度（发现算法的凭据路径长度）之间存在渐进曲线的关系。
    采用图论中度数（Degree）和直径（Diameter）两个参数研究DHT发现算法，发现这些DHT发现算法在度数和直径之间存在渐进曲线关系。在N个节点网络中，当度数为N时，发现算法的直径为O(1)，；当每个节点仅维护一个邻居时，发现算法的直径为O(N)。这是度数和直径关系的2种极端情况。同时，研究以图论的理论分析了O(d)的O(d)的直径的算法是不可能的。
    从渐进曲线关系可以看出，如果想要获得更短的路径长度，必然导致度数的增加；而网络实际连接状态的变化造成大度数邻居关系的维护复杂程度增加。另外，研究者证明O(logN)甚至O(logN/loglogN)的平均路径长度也不能满足转台变化剧烈的网络应用的需求。新的发现算法受到这种这种关系制约的根本原因在于DHT对网络拓扑结构的确定性认识。

二、Small world理论对P2P发现技术的影响
    非结构化P2P系统中发现技术一直采用洪泛转发的方式，与DHT的启发式发现算法相比，可靠性差，对网络资源的消耗较大。最新的研究从提高发现算法的可靠性和寻找随即图中的最短路径两个方面展开。也就是对重叠网络的重新认识。其中，small world特征和幂规律证明实际网络的拓扑结构既不是非结构化系统所认识的一个完全随机图，也不是DHT发现算法采用的确定性拓扑结构。
    实际网络体现的幂规律分布的含义可以简单解释为在网络总少数节点有较高的“度”，多数节点的“度”较低。度数高的节点同其他节点的联系比较多，通过它找到待查信息的概率较高。
    small-world模型的特性：网络拓扑具有高聚集度和短链的特性。在符合small world特性的网络模型中，可以根据节点的聚集度将节点划分为若干簇(Cluster)，在每个簇中至少存在一个度最高的节点为中心节点。研究证明以Gnutella为代表的P2P网络符合small world特征，也就是网络中存在大量高连通节点，部分节点之间存在“短链”现象。因此，P2P发现算法中如何缩短路径长度的问题变成了如何找到这些“短链”的问题。尤其是在DHT发现算法中，如何产生和找到“短链”是发现算法设计的一个新思路。small world特征的引入会对P2P发现算法产生重大影响。
三、语义查询和DHT的矛盾
    现有DHT算法由于采用分布式散列函数，所以只适合于准确的查找，如果要支持目前Web上搜索殷勤具有的多关键字查找的功能，还要引入新的方法。主要的原因在于DHT的工作方式。
    基于DHT的P2P系统采用容易散列函数根据精确关键词进行对象的定位与发现。散列函数总是试图保证声称的散列值均匀随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两个节点上。因此，DHT可以提供精确匹配查询，但是支持语义是非常困难的。
    目前在DHT基础上开展带有语义的资源管理技术的研究还非常少。由于DHT的精确关键词映射的特性决定了无法和信息检索等领域的研究成果结合，阻碍了基于DHT的P2P系统的大规模应用。[
a
]


DHT的发现算法如Chord、CAN、Koorde等都是考虑网络波动的最差情况下的设计与实现。由于每个节点的度数尽量保持最小，这样需要影响的成员关系变化的维护可以比较小，从而可以快速恢复网络波动造成的影响。但是每个节点仅有少量路由状态的代价是发现算法的高延时，因为每一次查找需要联系多个节点，在稳定的网络中这种思想是不必要的。
    作为一种资源组织与发现技术必然要支持复杂的查询，如关键字、内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术，由于DHT精确关键词应设的特性阻碍了DHT在复杂查询方面的应用。



本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/11238/showart_66522.html