P2P中的核心技术

承接上一篇文章P2P协议概述
随着P2P应用的蓬勃发展,作为P2P应用中核心问题的发现技术除了遵循技术本身的逻辑以外,也受到某些技术的发展趋势、需求趋势的深刻影响。 

度数和直径的折衷关系(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]

P2P发现技术研究的成果与不足

P2P发现技术中最重要的研究成果应该是基于small world理论的非结构化发现算法和基于DHT的结构化发现算法。尤其是DHT及其发现技术为资源的组织与查找提供了一种新的方法。

随着P2P系统实际应用的发展,物理网络中影响路由的一些因素开始影响P2P发现算法的效率。一方面,实际网络中结点之间体现出较大的差异,即异质性。由于客户机/服务器模式在Internet和分布式领域十几年的应用和大量种类的电子设备的普及,如手提电脑、移动电话或PDA。这些设备在计算能力、存储空间和电池容量上差别很大。另外,实际网络被路由器和交换机分割成不同的自治区域,体现出严密的层次性。

另一方面,网络波动的程度严重影响发现算法的效率。网络波动(Churn、fluctuation of network)包括结点的加入、退出、失败、迁移、并发加入过程、网络分割等。DHT的发现算法如Chord、CAN、Koorde等都是考虑网络波动的最差情况下的设计与实现。由于每个结点的度数尽量保持最小,这样需要响应的成员关系变化的维护可以比较小,从而可以快速恢复网络波动造成的影响。但是每个结点仅有少量路由状态的代价是发现算法的高延时,因为每一次查找需要联系多个结点,在稳定的网络中这种思路是不必要的。

同时,作为一种资源组织与发现技术必然要支持复杂的查询,如关键词、内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术,由于DHT精确关键词映射的特性阻碍了DHT在复杂查询方面的应用。

P2P网络拓扑模型

Internet作为当今人类社会信息化的标志,其规模正以指数速度高速增长.如今Internet的“面貌”已与其原型ARPANET大相径庭,依其高度的复杂性,可以将其看作一个由计算机构成的“生态系统”.虽然Internet是人类亲手建造的,但却没有人能说出这个庞然大物看上去到底是个什么样子,运作得如何.Internet拓扑建模研究就是探求在这个看似混乱的网络之中蕴含着哪些还不为我们所知的规律.发现Internet拓扑的内在机制是认识Internet的必然过程,是在更高层次上开发利用Internet的基础.然而,Internet与生俱来的异构性动态性发展的非集中性以及如今庞大的规模都给拓扑建模带来巨大挑战.Internet拓扑建模至今仍然是一个开放性问题,在计算机网络研究中占有重要地位.

Internet拓扑作为Internet这个自组织系统的“骨骼”,与流量协议共同构成模拟Internet的3个组成部分,即在拓扑网络中节点间执行协议,形成流量.Internet拓扑模型是建立Internet系统模型的基础,由此而体现的拓扑建模意义也可以说就是Internet建模的意义,即作为一种工具,人们用其来对Internet进行分析预报决策或控制.Internet模型中的拓扑部分刻画的是Internet在宏观上的特征,反映一种总体趋势,所以其应用也都是在大尺度上展开的.对Internet拓扑模型的需求主要来自以下几个方面:(1) 许多新应用或实验不适合直接应用于Internet,其中一些具有危害性,如蠕虫病毒在大规模网络上的传播模拟;(2) 对于一些依赖于网络拓扑的协议(如多播协议),在其研发阶段,当前Internet拓扑只能提供一份测试样本,无法对协议进行全面评估,需要提供多个模拟拓扑环境来进行实验;(3) 从国家安全角度考虑,需要在线控制网络行为,如美国国防高级研究计划局(DARPA)的NMS(network modeling and simulation)项目.

1、随机网络与拓扑模型
随机网络是由N个顶点构成的图中,可以存在条边,我们从中随机连接M条边所构成的网络。还有一种生成随机网络的方法是,给一个概率p,对于中任何一个可能连接,我们都尝试一遍以概率p的连接。如果我们选择M = p,这两种随机网络模型就可以联系起来。对于如此简单的随机网络模型,其几何性质的研究却不是同样的简单。随机网络几何性质的研究是由Paul,Alfréd Rényi和Béla Bollobás在五十年代到六十年代之间完成的。随机网络在Internet的拓扑中占有很重要的位置。

2、随机网络参数
描述随机网络有一些重要的参数。一个节点所拥有的度是该节点与其他节点相关联的边数,度是描述网络局部特性的基本参数。网络中并不是所有节点都具有相同的度,系统中节点度的分布情况,可以用分布函数描述,度分布函数反映了网络系统的宏观统计特征。理论上利用度分布可以计算出其他表征全局特性参数的量化数值。
聚集系数是描述与第三个节点连接的一对节点被连接的概率。从连接节点的边的意义上,若为第i个节点的度,在由k.个近邻节点构成的子网中,实际存在的边数E(i)与全部k.个节点完全连接时的总边数充的比值定义为节点i的聚集系数

3、拓扑模型
Internet拓扑模型可分为两类:一类是描述Internet拓扑特征,包括Waxman模型,Tiers,Transit -Stub和幂律;另一类是描述拓扑特征形成的机理,包括Barabási与Albert提出的BA和ESF以及一种改进模型GLP.由于后一类模型对Internet幂律形成机理的描述还不成熟,更多的是作为一种产生幂律的图生成算法。对于第1类模型来说,Internet拓扑特征的发现,实际上就是刻画该特征的度量(metric)的发现.一个属于第一类的拓扑模型就是包含若干已存在的或新发现的度量,然后根据实际的Internet拓扑数据求出这些度量的值.因此,对这类模型进行评价需要从两方面入手:一方面,对它所采用的拓扑数据进行评价;另一方面,对其度量进行评价.在所有已经发现的Internet拓扑度量中,最为基本的就是节点出度频率fd.其分布是判断一幅拓扑图是否与Internet拓扑相类似的最重要的依据.在研究早期,研究人员或者认为Internet节点出度是完全随机的(如Waxman模型),或者认为节点出度是正规的(如Tiers模型).而幂律的发现证明了Internet拓扑结构介于两者之间,呈幂率分布.根据对出度频率分布的刻画,可将Internet拓扑模型分为以下3类:

(1) 随机型,即认为Internet拓扑图处于一个完全无序的状态,在大尺度上是均一的.Waxman模型,是一种类似于Erds-Rényi模型的随机模型,出度频率呈泊松分布.这个模型有两个版本:RG1,先将节点随机布置在直角坐标网格中,节点间的距离就是其欧几里德距离;RG2,依据(0,L)均匀随机分布为节点对指定距离.两个版本中,节点间相接的概率P(u,v)与其距离相关,服从泊松分布,距离越近,概率越大.

其中,d(u,v)表示节点u与v之间的距离,L为节点间最长距离,á与a取值范围是(0,1).

(2) 层次型,来自对Internet结构所具有的层次特征的认识,在同一层上的节点出度接近,不同层间节点出度差别很大.对同一层上的节点布置借用Waxman模型方法.Tiers(等级)模型将Internet划分为LAN(局域网),MAN(城域网)和WAN(广域网)3个层次.在该模型中,WAN只有一个,通过指定LAN和MAN数量以及各自内部所包含节点的数量来构造拓扑图.Transit-Stub模型将AS域划分为Transit类和Stub类.在该模型中,Transit节点彼此互联构成一个节点群,一个或多个Transit节点群构成拓扑图的核心,而Stub节点分布在Transit节点群四周与Transit节点相连.Transit -Stub是GT-ITM(georgia tech Internetwork topology models)软件包的一部分,有时GT-ITM也就是指Transit-Stub模型.

(3) 幂率型.1999年,Faloutsos等人对NLANR(National Lab for Applied Network Research)在1997~1998年间的3份BGP数据以及1995年的一份traceroute测量数据进行分析,发现Internet拓扑中存在着4条幂律.

幂律是指形如的方程,对于两个变量X和Y,存在一个常数C,使得Y与X的C次幂成比例.有两个声明:(1) 节点v的等级为,v是在按出度降序排列序列中的索引值;(2) 邻接矩阵特征值按降序排列,第i个特征值为li.幂律1(等级指数R):节点出度dv与该节点等级rv的R次幂成比例.幂律2(出度指数O):出度频率fd与该出度d的O次幂成比例.

近似幂律(hop-plot指数H):h跳内节点对(pairs of nodes)的数量与h的H次幂成比例.幂律3(特征指数E):特征值li与其次序i的E次幂成比例.

Small World网络

在现实的Internet环境中,网络拓扑并不完全满足随机网络拓扑。Watt和Strogatz发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。改动的方法是,对于规则网络的每一个顶点的所有边,以概率p断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择,如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。当p = 0时就是规则网络,p = 1则为随机网络,对于0 < p < 1的情况,存在一个很大的p的区域,同时拥有较大的集聚程度和较小的最小距离。Small World网络的几何性质如图所示。

  • 平均路径。图中被随机选择又重新连结后的线称为捷径,它对整个网络的平均路径有着很大影响,分析表明:当p>=21(NK),即在保证系统中至少出现一条捷径的情况下,系统的平均路径开始下降。即使是相当少的捷径也能够显著地减小网络的平均路径长度。这是因为每出现一条捷径,它对整个系统的影响是非线性的,它不仅影响到被这条线直接连着的两点,也影响到了这两点的最近邻、次近邻,以及次次近邻等。
  • WS网络的集团系数。r1初始固定的节点数可计算t1{ p=0时规则网络的聚集系数为C(0), C(0)取决于网络结构而与尺寸N无关,因此有相对较大的值。随着边按一定的概率p随机化,聚集系数在CYO}的附近变化。
  • 度分布。WS模型是介于规则网络和随机网络
JouyPub wechat
欢迎订阅「K叔区块链」 - 专注于区块链技术学习