《P2P覆盖网中的聚类研究综述.doc》由会员分享，可在线阅读，更多相关《P2P覆盖网中的聚类研究综述.doc（11页珍藏版）》请在三一文库上搜索。
1、P2P覆盖网中的聚类研究综述doi:10.3969/j.issn.1001-3695.2010.03.002 Survey on P2P overlay clustering technology research ZHENG Li-ming1a,2, LI Xiao-dong1b, LI Xiao-yong2, SUN Wei-dong2 (1. a.Information & Technology Teaching & Researching Section, b.Research Section, Chengdu Commanding College of the CAPF, Cheng
2、du 610213, China; 2. National Key Laboratory for Parallel & Distributed Processing, School of Computer, National University of Defense Technology, Changsha 410073, China) Abstract:Firstly, this paper reviewed the classification of the clustering methods in P2P overlay, and based on which, introduced
3、 and compared many typical methods. Lastly, reviewed the future research trends of clustering methods in P2P overlay. Key words:P2P; network clustering; network community structure; overlay; network distance 对于网络聚类的研究已经有较长的历史,几十年来,其重要性及与其他研究方向的交叉特性得到人们的肯定。聚类是数据挖掘、模式识别、分布式网络等研究方向的重要研究内容之一。对等网络(peer-t
4、o-peer network,P2P网络)作为一种新兴的计算机网络结构,已经成为当前互联网研究的热点方向15。然而,随着P2P技术的迅猛发展、需求与应用的不断拓展、用户数量的急剧增加以及交互方式的日益多样化,P2P网络本身及其所处的网络环境均呈现出爆炸式的复杂性增长趋势。面对这种情形,当前用于构造P2P系统的思想、方法和技术正面临着严峻的挑战,P2P网络安全问题也愈加突出,急需从新的角度理解网络的结构与网络行为之间的关系,进而考虑改善网络的行为,使之一方面能够真实反映和正确利用网络的结构特征,另一方面能够更好地适应这种爆炸式的复杂性增长趋势。 P2P覆盖网是一种通过网络节点自组织形成的并构建于
5、物理网络之上的分布式应用层网络,是由节点和逻辑链路组成的一种虚拟的网络。近年来对P2P覆盖网的研究已经成为P2P领域的研究热点之一。目前已涌现出一大批基于覆盖网的应用,如Napster、Gnutella、OceanStore6、Kademlia7等文件共享系统;SplitStream8、PROMISE9、Bullet10等大型数据分发系统;基于分布式哈希表(DHT)的结构化P2P1,4,5,11,12应用以及内容分发网络(CDN)等。上述应用利用基于拓扑感知的相关技术,如覆盖网路由13、应用层组播14,15、拓扑聚合16、最近服务器选择1719、拓扑感知覆盖网构建1921等,均能够显著地提高性
6、能,因此研究拓扑感知具有明显的现实意义。P2P覆盖网中聚类技术的研究则是研究拓扑感知技术的关键,性能优越的聚类方法能够有效支撑覆盖网路由、应用层组播、资源有效放置、感知拓扑构建等,极大地提高了P2P网络的性能。因此,研究P2P覆盖网中的聚类方法具有深远的理论意义和现实应用价值。 1 P2P覆盖网聚类方法分类 对等网络作为当前计算机网络中的重要研究领域,不仅P2P网络中的节点规模庞大,而且网络节点存在较大的异构性,如节点的地理位置、处理能力和网络路径等存在差异。在P2P网络中,通常采用的聚类方式是通过研究网络节点之间的距离来进行聚类,网络距离是一种抽象概念,通常是指网络延迟,一般以RTT(rou
7、nd-trip time)表示。根据所获得的距离信息进行聚类,是一种常用的聚类研究思想。 从P2P网络的特殊性出发,根据网络距离信息获取方式以及聚类策略的不同,可将P2P网络中基于距离信息的聚类方法划分为基于参考点的方法、基于网络层协助的方法、基于等级模式的方法、基于网络坐标的方法以及基于距离抽样的方法五类。基于参考点的方法是指为了获取节点之间的网络距离信息,通过直接或间接地引入相关的辅助节点或服务器以支持距离获取的方法;基于网络坐标的方法是指利用对网络节点进行数学空间建模,通过网络坐标的形式定位坐标空间中的节点,并通过节点之间的坐标信息获得网络距离,并加以聚类的方法;基于距离抽样的方法是指在
8、已探测网络距离的基础上,通过距离抽样的方式,利用一定的迭代搜索策略获取邻近节点,从而实现节点聚类的方法。整个P2P网络中聚类方法的分类如图1所示。 2 基于网络距离的聚类方法 在P2P覆盖网中,拓扑感知的目的在于降低覆盖网的延迟伸展率(latency stretch,定义为在逻辑覆盖网中节点间的延迟与在物理网络中对应节点间的延迟之比),从而需要可扩展地获取底层物理网络节点之间的延迟信息。可见,网络距离是实现拓扑感知的基础。利用相关的距离信息进行聚类是一种有效的重要的方式。对于距离较小的节点或者相对邻近的节点可将其划分于相应的簇中,此为基于网络距离的聚类方法的根本出发点。对于网络距离的研究,根据
9、网络距离值或者邻近性等计算或获得方式的不同,可将基于网络距离的聚类方法分为基于参考点、基于网络层协助、基于等级模式、基于网络坐标以及基于距离抽样五种聚类方法。 2.1 基于参考点的方法 基于参考点的方法是为了避免进行完全测量(即对所有节点之间距离的测量),增强邻近搜索的可扩展性,主动引入一些测量参考点用于收集测量信息。这些测量参考点主要包括地标(Landmark22、Beacon23、Tracer24、Lighthouse node25、index node26等)、中间路由器(intermediate routers,称做Milestones27)、内容分发网络(CDN)中的副本服务器19等
10、。这类方法一般利用测量参考点收集的信息,采用集中式的策略进行搜索。Guyton等人28为这类方法提供了经典的范例。假定N个地标分别为Bi(1iN),任意一个服务器S的坐标表示为一个N元组(由Hotz定义):S=s1,s2,sN,表示si到第i个地标的距离(跳数);类似地定义一个客户端C的坐标:C=c1,c2,cN。这样,S与C之间的网络距离表示为? 最典型的是2006年宾夕法尼亚大学的Mao等人34提出的IDES方法,该方法通过采用SVD(singular value decomposition)和NMF(non-negative matrix factorization)两种矩阵分解技术来建
11、模子优化和非对称路由策略;为每个节点赋予一个入向量和出向量,根据出向量和入向量的内积确定网络距离。该方法摆脱了对称性和三角不等性的约束,然而它假设距离矩阵中存在大量线性相关的向量,即利用分簇性原理,当出现错误分簇时,IDES的预测精度会明显降低。 此外,不少研究人员还提出了一些模拟物理过程的坐标计算方法,如BBS(big-bang simulation)3537、Vivaldi38、PCoord39,40等。BBS方法模拟了粒子在由于嵌入误差所产生的力场中的爆炸行为,它将网络中的所有节点视做一个粒子集合,粒子之间可能相互吸引或者排斥,可能由于力场的作用加速,也可能由于摩擦力作用而减速。Viva
12、ldi方法则模拟了节点在嵌入误差产生的弹簧力场作用下的运动过程,它假定任意两个节点之间都存在一根弹簧,通过节点间弹力的作用来修正节点的坐标。PCoord方法则在坐标更新的过程中引入摩擦力机制来提高坐标的收敛速度,从而提高坐标的精确性和可用性。综合以上各种基于网络坐标的聚类方法,从方法对应的主要技术、地标分布性、分簇的精确性、计算开销、TIV问题的解决以及安全性检测方面归纳为表2。 表2 不同的网络坐标聚类方法的对比 propertiesmaintechniquecentra-lizedembed-ding typeaccu-racyphysicalprocesscomputecostsolvi
13、ngTIVsecu-rity GNPabsolute coordinatesimplex downhillyesEuc-lideanmode-ratenobignoignore ICSPCA and LipschizembeddingyesLip-schizmode-ratenosmallnoignore virtuallandmarkPCA andLipschizyesLip-schizmode-ratenosmallnoignore lighthouseGram-Schmidt,vector basetranslationyesEuc-lideanmode-ratenosmallnoign
14、ore BBSsimulate particleexplosionnoEuclidean/Hyperbolicmode-rateyesmediumyesignore VivaldiSimulate springforce field andpiggy-backcommunicationnoEuc-lidean/with highvectorhighyessmallyesignore PICimprove GNP withdifferent landmarkselection strategiesnoEuc-lideanhighnosmallnocheck PCoordactive exchan
15、geinformation;sample weight,force of friction,Damping mechanismnoEuc-lideanmode-rateyesbignoignore IDESmatrixfactorization:SVD and NMFnoEuc-lideanhighnosmallyesignore Hierarchicalmethodmulti-coordinatesnoEuc-lideanhighnobignoignore HNDPdivide Internetinto many diffe-rent regionsnoEuc-lideanmode-rate
16、nobignoignore 2.3 基于距离抽样的方法 基于距离抽样的方法,通过随机选取一些节点作为邻居,并且根据距离远近将其部署在某种数据结构中。采用邻近搜索贪心策略,通过不断追溯当前最近邻的邻居来发现更近的节点,直至结束。 Meridian41利用基于直接测量形成的松散结构的同心环状覆盖网结构,结合Gossip协议来交换节点间的信息,以迭代转发查询匹配信息的方式来定位最优的邻近节点。从某种意义上说,Meridian设计了一种“小世界”,通过不断追溯当前最近邻的邻居的贪心路由方式,以O(log N)的跳数寻找到最近邻。尽管Meridian考虑了同心环成员多样化的问题,仍然难以避免搜索过程陷入
17、局部最优。其查询原理如图9所示,client节点向覆盖网节点A发出请求,寻找目标节点T的最近邻。A先探测与T的距离d,然后要求离自己(1-)d(1+)d之间的环成员节点探测与T的距离,并反馈给A,查询将转发给当前最近邻。 Mithos42在覆盖网构造阶段,新节点通过接触bootstrap node得到自己的候选邻居,然后获取这些候选邻居的直接邻居,探测到所有这些邻居的延迟以寻找更近的邻居,同时作为新的候选邻居。这个过程迭代进行,直至没有进展。当然,上述过程容易陷入局部最优。Castro等人提出一种在Pastry中寻找邻近种子节点(seed node)的分布式算法PNS-CG。它充分利用由Pas
18、try节点维护的叶集和路由表,沿着路由表各层自底向上进行搜索,不断向最近的节点逼近。这种方法不需要额外的维护开销。 3 未来研究趋势 P2P覆盖网中的聚类方法,对于覆盖网路由、应用层组播、拓扑聚合、最近服务器选择、拓扑感知覆盖网构建等P2P优化技术具有强烈的支撑作用,对提高P2P网络的性能具有直接的、重大的理论意义和应用价值。本文从P2P覆盖网中聚类方法的特殊性出发,从P2P网络的角度探讨P2P网络中的聚类方法,将相关技术的优缺点进行对比并对于具体应用具体分析,是研究聚类方法的重点,也是计算机学科中P2P网络研究中的关键技术。根据P2P覆盖网的特殊性,利用P2P网络专有的特点,根据P2P覆盖网
19、的相关度量属性进行有效聚类是研究P2P覆盖网的重点手段。目前P2P网络中的聚类研究已取得了不小的进步,但是同样存在不少需要解决的问题,主要包括如下几个方面: a)网络嵌入模型的研究。Internet建模能对聚类提供有效支持,目前很多聚类方法都使用了相关的模型。然而,对Internet建模是一项复杂的任务,因为现实Internet环境中存在诸多如高度动态性43、网络节点不可达性44以及TIV等特征。目前虽然已有欧式空间、双曲空间以及Lee等人45提出的混合空间等嵌入模型用于P2P聚类的建模计算,但是这些模型均不能很精确地描述现实Internet的特征。因此,研究如何对Internet环境建模,寻
20、找一种最优的空间模型是数学界和计算机界共同需要解决的问题。 b)高效稳定的聚类方法研究。由前面分析可知,要实现高效稳定的网络聚类方法,需要考查技术的可扩展性、计算开销、通信开销、精确性、稳定性、收敛性、安全性等诸多方面。而与之密切相关的研究主要包括坐标类型选择、计算过程模拟、分簇算法、现实部署性等。在网络坐标计算方法中,采用非线性方法进行绝对坐标计算其收敛性好,但是开销大;采用线性方法进行相对坐标计算其计算开销小,却需要节点的分簇性假设;采用模拟物理过程的方法如Vivaldi,其计算和通信开销小,但是收敛速度慢且不能保证能够收敛到稳定状态,不便于实际应用。在基于参考点的方法中,代理节点或者服务
21、器节点部署的数目、方式以及开销等现实部署性问题,以及寻找最优的分簇算法仍然值得深究。 c)安全性方面的研究。安全性方面的研究主要针对于基于网络坐标的聚类方法,当前许多对网络坐标安全性的研究4650表明,网络坐标系统在面对实际Internet时是很脆弱的,极易遭受来自各方面的攻击。网络的动态性和异构性等复杂特征使得恶意节点的攻击形式多样化,使得对网络坐标安全性的研究是极其复杂。为此Kaafar等人46,48,49在最近几年内进行了尝试,他们将恶意节点的攻击分为扰乱(disorder)、隔离(isolation)、排斥(repulsion)、系统控制(system control)四种情形来考察坐
22、标系统的安全性,并提出利用检查员基础设施(surveyor infrastructure)来检测恶意节点的行为,此方法在一定程度上增强了坐标系统的安全性。然而,安全性研究目前还处在研究的初级阶段,由于坐标安全性研究的复杂性和必要性,决定了对此方面的研究将是一个长期的过程。 4 结束语 P2P网络中的聚类技术研究作为P2P网络中新兴的热点研究领域,是一个融合了复杂系统、计算机、数学、物理学、生物学、社会学等多个学科的技术研究。从整体上讲,目前在P2P网络中的聚类技术研究还不够成熟,尚未建立起一套完整的理论体系和方法体系,而且从技术理论的完善到真正聚类系统可靠的部署应用还距离甚远。本文回顾了当前学术界在P2P网络中聚类技术研究领域的主要研究成果,从P2P网络自身的特殊性方面介绍了P2P网络中的聚类技术研究的多种方法和关键技术,在分类的基础上分析比较了各种具有代表性的聚类方法,最后指出了未来研究的趋势。