对等网络(P2P)总结整理解析_p2p对等网络

对等网络(P2P)总结整理解析由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“p2p对等网络”。

对等网络(P2P

一、概述(一定义

对等网络(P2P网络是分布式系统和计算机网络相结合的产物,在应用领域和学术界获得了广泛的重视和成功,被称为“改变Internet的新一代网络技术”。

对等网络(P2P:Peer to Peer。peer指网络结点在: 1行为上是自由的—任意加入、退出,不受其它结点限制,匿名;2功能上是平等的—不管实际能力的差异;3连接上是互联的—直接/间接,任两结点可建立逻辑链接,对应物理网上的一条IP路径。

(二P2P网络的优势

1、充分利用网络带宽

P2P不通过服务器进行信息交换,无服务器瓶颈,无单点失效,充分利用网络带宽,如BT下载多个文件,可接近实际最大带宽,HTTP及FTP很少有这样的效果

2、提高网络工作效率

结构化P2P有严格拓扑结构,基于DHT,将网络结点、数据对象高效均匀地映射到覆盖网中,路由效率高

3、开发了每个网络结点的潜力

结点资源是指计算能力及存储容量,个人计算机并非永久联网,是临时性的动态结点,称为“网络边缘结点”。P2P使内容“位于中心”转变为“位于边缘”,计算模式由“服务器集中计算”转变为“分布式协同计算”。

4、具有高可扩展性(scalability 当网络结点总数增加时,可进行可扩展性衡量。P2P网络中,结点间分摊通信开销,无需增加设备,路由跳数增量小。

5、良好的容错性

主要体现在:冗余方法、周期性检测、结点自适应状态维护。

二、第一代混合式P2P网络(一主要代表

混合式P2P网络,它是C/S和P2P两种模式的混合;有两个主要代表:

1、Napster——P2P网络的先驱

2、BitTorrent——分片优化的新一代混合式P2P网络(二第一代P2P网络的特点

1、拓扑结构 1混合式(C/S+P2P 2星型拓扑结构,以服务器为核心

2、查询与路由

1用户向服务器发出查询请求,服务器返回文件索引 2用户根据索引与其它用户进行数据传输 3路由跳数为O(1,即常数跳

3、容错性:取决于服务器的故障概率(实际网络中,由于成本原因,可用性较低。

4、自适应:靠服务器监控实现自组织与自适应,只要服务器正常工作即可有效维护网络

和结点信息。

5、匿名性:一般不提供,但支持

6、增强机制:BT的文件分片、双向传输、防范攻击

三、第二代无结构P2P网络(一主要代表

1、Gnutella:纯分布式无结构P2P网络

2、KaZaA:基于超节点的无结构P2P网络

3、eDonkey/eMule:分块下载的双层无结构P2P网络

4、Freenet:自由、安全、匿名的无结构P2P网络(二第二代P2P网络的特点

1、覆盖网拓扑结构

无结构,指覆盖网没有固定、严格的拓扑结构,而是一个随机生成、松散组织的普通图,但总是符合某种模型。

1小世界模型:20世纪60年代美国科学家的实验,任何一个美国人通过5-6层关系就能找到自己想找的人,小世界现象。1998年,Watts和Srogatz引入Small-world model,指任意两个网络结点间的距离一般很短,并且对每个结点而言,其邻居结点相识(互相连接的概率很高,所以结点集群现象明显。

2幂律模型:1999年,多位网络技术研究者指出很多实际网络如Internet的拓扑结构符合幂律模型(power-law model,即网络中拥有连接数L的结点占网络结点总数的份额正比于L-a,a是取决于网络本身的常数因子,因此网络中大多数结点连接数很少,少数结点连接数很多。

3Gnutella、Freenet等无结构P2P网络显然可以认为符合小世界模型;虽然不符合严格的幂律模型,但可以看成是它们与其他模型的合成体,具有面对随机结点失效的高容错性等特征。

2、路由和定位方法

Routing、location含义接近,此处路由指消息走过的路径上的每一跳选择,定位看成是由多次路由组成的。无结构网络没有全局路由表,不可能预先知道要找的数据在哪里,只能随机路由,通常以洪泛法为基础,通过TTL限制搜索半径。

四种典型的P2P随机路由方法:洪泛法、扩展环、随机走、超结点路由。1洪泛法

1绝大多数现存无结构P2P网络实际采用 2路由覆盖范围是一个以TTL为半径的圆 3不保证找到实际存在的文件 2扩展环(expanding ring 1试探性的洪泛法

2逐步增加TTL,直至查询成功或者达到上限,从而形成一个个环 3效率稍高

3随机走(random walks 1结点收到查询消息时只随机选择一个邻居结点发送该消息,直到数据被找到或TTL 用完

2因网络开销仅随跳数增加线性增加,故TTL可以较大 3改进方法:带检测的随机走,行者ID 4超结点路由(supernode routing 1超结点自组织成一个网络,普通结点向其发起查询 2可以在超结点网络中采用洪泛法 3eDonkey、KaZaA的流行,证明可行性(三优势和缺陷

1、优势

1网络拓扑简单易实现

2容错性、自适应性都好于结构化P2P 3可以具有很强的安全性和匿名性 4数据复制方案很多

2、缺陷 1路由效率低 2可扩展性差 3数据无法准确定位

四、第三代结构化P2P网络(一主要代表

1、Chord与CFS:简单、精确的环形P2P网络

2、CAN:简单、容错的多维空间P2P网络

3、Tapestry与OceanStore:广域的超立方体结构P2P网络

4、Pastry与PAST:容错的混合式结构P2P网络(二结构化P2P的核心机制

1、覆盖网拓扑结构

结构化P2P网络最大的特点在于它们都有一个严格的覆盖网拓扑结构,下面是结构化P2P网络的几种主要拓扑结构: 1带弦环——Chord、Pastry、Kademlia、Cycloid等

1Chord:最纯粹的带弦环,其弦是指数间隔的,下标越大的弦指的越远 2Pastry:混合了环形和超立方体 3Kademlia:基于异或度量的带弦环 4Cycloid:带环的立方体结构 2多维空间——CAN 所有结点被组织在一个多维笛卡尔空间里,每个结点有自己在空间中的邻居。3超立方体——Tapestry、Pastry 所有结点被组织在一个超立方体中。4蝴蝶形——Viceroy 蝴蝶网中,每个结点有它的“层”,每层的结点通常维护两个下边、一个上边以及两个同层边。

5de Bruijn图——Koorde 每个节点有两条出边:一条指向结点2m(mod2b,一条指向结点2m+1(mod2b,b 为ID位数。

6CCC——Cycloid 一个d维带环立方体CCC是每个结点被一个包含d个结点的圆环所取代的d维超立方体,因此,每个结点度为3。

7其它形状(如跳表——SkipNet2、分布式散列表

所有的结构化P2P网络都使用分布式散列表(DHT来将结点、数据对象映射到覆盖网中。为使这种映射唯

一、均匀、随机,分布式散列表都使用安全的一致性散列函数,其中

最著名、也被大多数P2P系统采用的安全散列函数是SHA-1(安全散列算法,它能产生均匀、随机、与输入无关的160位散列值,并且散列值冲突的概率极小。

3、路由和定位

路由和定位的方式通常取决于两个因素:覆盖网拓扑结构和路由表结构。结构化P2P网络通常都维护一个比较小的路由表,采用分布式、局部性的贪心路由算法,逐步缩小当前结点与目的结点之间的ID差异。

结构化P2P网络主要的路由方式有如下几种: 1数值临近路由(chord 这里的“数值”通常指结点ID值。路由过程中每一步,当前都在自己的路由表 中选择与目的ID最邻近的结点作为下一跳,因此,路由路径中每一跳结点ID

与目的ID的差距会越来越小,直至最接近目的ID的结点为止。2逐位匹配路由(Tapestry、Pastry 基于层次化的路由表,每一步通常都能与目的ID多匹配至少一位,因此逐位匹 配路由的效率等价于ID的位数。3位置临近路由(CAN 每个结点的路由表记录自己在多维空间中的邻居,每次选择离目的结点最近的 邻居作为下一跳。4层次路由(Viceroy、SikpNet 不少P2P网络将结点组织到多个层次上,路由过程常常先从低层爬到高层,再 从高层爬到低层。5混合式路由(Cycloid4、动态结点算法(自组织、自适应 1结点加入

几乎所有结构化P2P网络的结点加入算法都大同小异,通常分三步工作: 1初始化自己的路由表

2告诉其他结点自己的到来,更新它们的路由表

3应由新结点N负责的对象索引必须从现存结点移交给N 2结点离开

旧结点离开结构化P2P网络所要做的工作,可以看成加入时所做工作的逆过程:首先移交对象索引,然后通知其他结点在路由表中删除自己,最后离开网络。

3结点失效

结点失效是被动发生的、不可预料的。结构化P2P对待失效问题主要有两种解决方法: 1按需的:当某个操作发现有结点失效时再做处理

2周期性的:每隔一段时间检测一次,如果有失效情况再做修复

4Chord采用称为“稳定化”的周期性检测方法来处理失效问题,检测到失效后,先修理后继关系,再修理路由表。

5、容错性与安全性

结构化P2P网络的容错性、安全性通常不及无结构P2P网络,因为拓扑结构越严格、定位越准确,维护起来就越复杂,暴露给攻击者的弱点也就越多。

为了提高容错性,结构化P2P网络的设计者多从路由表上做工作,如chord使用“后继列表”来取代单后继。

结构化P2P网络的安全性难以完备,也更复杂。现有系统都实现了某个方面的安全机制,但通常是很不够的,结构化P2P应用系统CFS通过散列方法来保证数据完整性,同时使用“现时”回馈的方法防止恶意结点伪造ID或虚报IP。

6、局部性

1网络局部性:局部性的目的通常在于提高覆盖网与物理网的一致性,从而减少通信时延。例如,CFS在其chord层加入了服务器选择方法。

2语义局部性:2003年提出的SkipNet网络,基于“跳表”数据结构,提供路由、数据内容两个方面的语义局部性。

(三结构化P2P的增强机制

在具有最核心、最基础的部件之后,P2P网络就可以正常工作了,为了构建一个高效率、高可用、高安全的P2P网络,我们就需要去分析P2P网络所追求的性能,发现所存在的问题,研究可采用的方法,设计并实现合理的软件。这些工作合起来,称为“P2P增强机制”。

1、复制与缓存

结构化P2P网络普遍采用“ID邻近复制”,即将数据对象复制到ID邻近的k个结点上。这有两个原因:①ID邻近的结点能很快找到;②ID邻近的结点往往均匀分布在网络中(物理网,它们同时失效的可能性很小,因此提高了数据可用性。

结构化P2P网络基本上使用“路径缓存”,将数据缓存到查询路径上,原因在于:结构化P2P网络由于对象位置确定、拓扑结构严格,不同结点查询同一对象的定位路径往往会有重叠,并且越接近对象保存的结点,路由重叠的可能性越大。

2、分片

传统的分片方法把一个文件分成多个等大小的片,将这些分片分散存储或者分开传输,从而获得并发效果,以提高效率。结构化P2P应用系统CFS将每个文件分块,而使用DHash 中间层来分布和获取这些分块。

3、负载均衡

结构化P2P网络中最先提出各尽所能的“负载均衡”方法的是chord,它让每个实际的网络节点负责多个“虚拟服务器”,由于每个虚拟服务器都负责chord环上连续的一小段,所以每个实际的网络节点都负责了chord环上多个不连续的小段,也就是承受了多个不同的负载。当某个结点负载过重时,它会把自己的负载转移一部分给那些负载较轻的结点,负载转移的基本单位正是“虚拟服务器”。所以说:“虚拟服务器”的数目既反映了结点当前承受的工作负载,又反映了结点能力的高低。

4、热点问题

热点:某个网络资源在极短的时间内,对它的获取请求发生了不可预料的、大量的、快速的增长,这种突然爆发的流行性导致网络某个结点造成难以应付的拥挤。

结构化P2P网络中“热点”问题的根源是一个对象的索引只能放在某个特定结点上,造成此结点的负载过重。“缓存”是解决热点问题的常用方法。

在结构化P2P网络中,由于定位对象的路径是确定的,所以路由过程中越接近对象索引时,路径重复的概率越大,在此情况下采取“路径缓存”,将对象索引信息缓存到定位路径上,这个简单的方法能很好地缓解索引的“热点”问题。

五、P2P网络的应用

1、文件共享:代替ftp,前述典型的P2P模型。

2、多媒体传输:Skype(语音,PPLive(视频。

3、实时通信:QQ、MSN Meenger、Skype,都支持C/S、P2P模式。

4、协同工作:Groove虚拟办公室。

5、分布式数据存取:广域、海量,CFS、PAST、OceanStore、Granary。

6、分布式计算:GPU,Gnutella全球处理单元,计算任务由对等结点而非服务器分配, SETI@Home,U.C.Berkeley搜索外星文明。

7、P2P搜索引擎:第三代搜索引擎技术,离实用有差距。