P2P系统原理(P2P技术的应用P2P的组织结构.ppt

《P2P系统原理(P2P技术的应用P2P的组织结构.ppt》由会员分享，可在线阅读，更多相关《P2P系统原理(P2P技术的应用P2P的组织结构.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、P2P系统原理第一页，编辑于星期六：十三点 十三分。n1 引言n2 P2P技术的主要应用n3 P2P的组织结构 （8个原理） P2P与Overlay网络 有结构的P2P网络 无结构的P2P网络4 P2P的应用(Bt Emule 迅雷) 第二页，编辑于星期六：十三点 十三分。引言n意义 Peer-to-Peer技术是一种基于对等网络的新兴技术。和传统客户端/服务器模式不同，P2P技术的最大意义在于其不依赖中心节点而依靠网络边缘结点自组织与对等协作的资源发现和共享形式。n 优点自组织、自管理、可扩展性好、鲁棒性强、负载均衡。 第三页，编辑于星期六：十三点 十三分。n应用领域目前，P2P技术广泛应用

2、于文件共享、网络视频及网络通话等领域，以其分布式资源共享和分布式并行传输的特点，为用户提供了更多的存储资源、更高的可用带宽和更好的服务质量。n缺点P2P应用已占运营商业务总量60%-80%,成为网络带宽最大的消费者，对底层网络产生的巨大影响。就实现原理来说，P2P并不是一种高效率的传输模式。传输过程中有很多重复的数据分组，占用大量的网络带宽，甚至造成网络拥塞，从而降低了其他业务的性能。第四页，编辑于星期六：十三点 十三分。n需解决的问题 由于目前P2P没有统一的网络协议标准，种类多、形式多样，使用传统的流量管理手段难以对P2P流量进行有效管理。 所以，如何管理P2P软件的使用，控制P2P流量对

3、网络其它正常流量的负面影响是运营商需要解决的重要问题。第五页，编辑于星期六：十三点 十三分。P2P技术的主要应用n分类文件分发语音服务流媒体n非实时流媒体应用：视频点播（VOD）等流媒体应用n实时流媒体应用：基于组播树（Tree-based）和网状结构Mesh-based流媒体应用第六页，编辑于星期六：十三点 十三分。国内外比较流行的P2P的应用n比特精灵完全免费、高速稳定、功能强大、不包含广告的BitTorrent客户端。只需一个监听端口即可满足所有的下载需要。n迅雷新型的基于多资源、多线程技术的下载软件。nMaze北大开发的一款功能强大的PIC（个人信息中心）文件系统。相比于其他软件，Ma

4、ze在机制方面提供了积分原则和排队策略。目前在中国教育网上使用十分广泛。nSkype目前最流行的网络语音工具，可以实现与其他用户的高清晰语音对话，亦可以拨打国内国际电话，还具备IM所需的其他功能。第七页，编辑于星期六：十三点 十三分。P2P与OverLay网络nP2P应用的组织结构的发展可以简单的分成三代：第一代 特点：集中控制缺点：鲁棒性 可扩展性相对较差应用代表：Napster第二代特点：无中心的分布式网络，所有的查询和响应都在节点间完成。以广播的方式散发查询消息，容错性好缺点：查询请求在网络中广泛传播，带宽消耗较大代表：Gnutella KaZaA Freenet等第三代特点：混合式的体

5、系结构，具有合理的查询时间和良好的可扩展性，对现有网络有很好的适应性。应用：PPLive PPStream 等提供商业服务的网站均采用这种体系结构第八页，编辑于星期六：十三点 十三分。P2P与覆盖网络的联系n应用层网络又称为覆盖网络，它的基本含义是在现有的Internet传输网络之上构建一个完全位于应用层的网络系统。无论是OSI模型还是Internet模型，网络具有层次结构。应用层位于层次结构的最高层，它利用传输层提供的服务完成相应的应用功能，如 Web浏览，FTP服务，电子邮件服务等。但是随着应用的模式越来越复杂，这种只依赖于传输层的应用层已经不能满足需要了。第九页，编辑于星期六：十三点 十

6、三分。nP2P系统中每台计算机及时服务器又是客户机，在这种情况下，P2P系统本身就是一个覆盖网络。Peer自己进行服务器发现，选择到其它Peer的路由等，这些功能都是由P2P系统提供的服务模式相关，所以不能利用传输层完成。第十页，编辑于星期六：十三点 十三分。nP2P系统在本质上是一个没有层次结构也没有集中控制的分布式系统。节点通过自组织的Overlay网络来实现文件分发文件分发、流媒体以及语音等服务。nOverlay网络的组织方式可以分成有结构的和无结构的两种。n有结构的P2POverlay 网络指的是Overlay 的网络有确定的拓扑特征，目的是使其内容的存放也相对有序。 通常使用分布式哈

7、希表来实现对文件资源的标识。n无结构的P2POverlay 网络通过一些松散的规则组织自在一起，文件的存放也表现出很大的随机性和不确定性。不能保证查询的正确性。第十一页，编辑于星期六：十三点 十三分。有结构的P2P网络n有结构的P2P网络也有很多种不同的实现方法，比较著名的有Chord、CAN、Pastry和Taperstry等。第十二页，编辑于星期六：十三点 十三分。Chord 原理n实现了这样一种操作：给定一个关键字（key），将key映射到某个节点。如果给对等网络应用的每个数据都分配一个key，那么对等网络中的数据查询问题可以用Chord解决。第十三页，编辑于星期六：十三点 十三分。nC

8、hord采用了相容哈希的一种变体为节点分配关键字。n相容哈希特点：哈希函数可以做到负载平衡（所有的节点可以接收到基本相同数量的关键字）当第N个节点加入或者离开网络时，只有1/N 的关键字需要移动到另外的位置。第十四页，编辑于星期六：十三点 十三分。nChord 对相容哈希进行改善：每个节点值需要知道关于其他节点的少量路由信息。在由N个节点组成的网络中，每个节点只需要维护其它O（logN）个节点的信息，同样每次查找只需要O（logN）条消息。当节点加入或离开网络时，Chord需要更新路由信息，每次加入或离开需要传递O（log2N）条消息。第十五页，编辑于星期六：十三点 十三分。n具体实现：利用相

9、容哈希函数，为每个节点和关键字分配m位的标识符。此标识符可用SHA-1（安全哈希算法）等哈希函数产生。节点的标识符通过哈希节点的IP地址产生，关键字的标识符通过哈希此关键字产生。例如：IP：198.10.10.1 通过SHA-1哈希后的标识符为123，关键字LetItBe哈希后的关键字为60。标识符长度m必须足够长，这样才能保证两个节点或者关键字哈希到同一个标识符上的概率小到可以忽略不计。第十六页，编辑于星期六：十三点 十三分。相容哈希中，每个关键字都保存到他的后继节点（节点标识符大于等于关键字k标识符的第一个节点）中。我们将其记为successor（k）。第十七页，编辑于星期六：十三点 十三

10、分。n当节点n加入网络时，为了保持相容哈希映射，某些原来分配给n的后继结点的关键字将分配给n。当节点n离开网络时，所有分配给他的关键字重新分配给n的后继节点。第十八页，编辑于星期六：十三点 十三分。n结点维护一个有m（ID位数）项的路由表，也称“指向表”（finger table），其中第i项指向结点s，s=successor(n+2i-1)，1im，即s是在顺时针方向到n的距离至少为2i-1的第一个结点，记做n.fingeri.nodenChord路由表的特点：n每个结点只保存很少的其它结点信息，并且对离它越远的结点所知越少nChord结点不能从自己的路由表中看出对象k的后继第十九页，编辑于

11、星期六：十三点 十三分。n为确定对象k的后继（k所在的结点）,结点n在自己的路由表中查找在k之前且离k最近的结点j，让j去找离k最近的结点，递归查找，最终可以找到对象k的前驱（在k之前离k最近的结点，记做predecessor(k)，类似，结点n的前驱记做n.predecessor）n前驱中必然有后继的路由表项，定位成功第二十页，编辑于星期六：十三点 十三分。nChord结点n的路由各项属性及其定义属性定义fingerk.start(n+2k-1)mod2m, 1km.intervalfingerk.start, fingerk+1.start).noden.fingerk.start的第一个

12、结点successor后继结点，即finger1.nodepredecessor前驱结点第二十一页，编辑于星期六：十三点 十三分。假设结点3要找到对象1的后继n在结点3的路由表中，1属于3.finger3.interval即7,3)n结点3让3.finger3.node即结点0去找1n结点0在路由表中发现自己的后继1恰好是对象1的后继，因此将1返回给结点3n结点3由此知道对象1放在结点1中第二十二页，编辑于星期六：十三点 十三分。Chord结点加入算法nChord的自适应需要保持两个不变的属性n每个结点的后继始终正确n对每个对象k，结点successor(k)始终负责k的索引n为此，新结点n的

13、加入需要完成三个任务n初始化n的前驱和路由表项n更新网络其他结点的前驱和路由表项n告诉其后继将应该由n负责的数据对象索引传递给nn新结点n连接到某个众所周知结点n，通过调用join(n)初始化自己的状态信息，并将自己加入到Chord网络第二十三页，编辑于星期六：十三点 十三分。节点失效n当节点n失效时，所有在指针表中包括n的节点都把n替换成n的后继结点。为了便于维护正确的后继指针，每个节点都维护一张包括r个最近后继的后继列表，如果节点n的后继节点失效了，就从后继列表中第一个正常节点替换失效节点。第二十四页，编辑于星期六：十三点 十三分。Content-Addressable NetworkCA

14、N内容寻址网络n可以在Internet规模的大型对等网络上提供类似哈希表的功能，CAN 的设计是完全分布式的，不需要任何形式的中央控制点。nCAN 具有很好的可扩展性，结点只需要维护少量的控制状态而且状态数量与系统中的结点数量无关；CAN 支持容错特性，结点可以绕过错误结点进行路由。CAN 基于虚拟的d 维笛卡儿坐标空间实现其数据的组织和查找功能，它将整个坐标空间动态地分配给系统中的所有结点，每个结点都拥有独立的互不相交的一块区域。第二十五页，编辑于星期六：十三点 十三分。n可以把整个CAN 系统看成一张保存（ key，value）对的大哈希表。CAN 的基本操作包括插入、查找和删除（ key

15、，value）对。其中key 是对被搜索资源的关键字（如文件名）哈希后的值，而value 则是资源的存储位置（ 如IP 地址和目录）。n整个CAN 系统由许多独立的结点组成，每个结点保存哈希表的一部分，称之为一个区。此外，每个结点在邻接表中还保存了少量邻接区的信息。对指定关键字的插入（ 或者查找、删除）请求被中间的CAN 结点路由到区里含有该关键字的CAN 结点。第二十六页，编辑于星期六：十三点 十三分。n下图给出了一个2 维的0，10，1的笛卡儿坐标空间划分成五个结点区域的情况。从图1 中可以看到，虚拟坐标空间中的每个区被动态地分配给CAN 中的某个结点，如坐标空间（0. 5 - 1，0.

16、0 - 0. 5）被分配给结点B。CAN 中的路由实际上就是穿过笛卡儿空间从源坐标到目的坐标的一条直线段路径。在CAN 中，每个结点都维护一张坐标路由表，此表用来存放该结点所有邻居的IP 地址和虚拟坐标区。在d 维坐标空间中，如果两个结点的坐标在d - 1维上重叠而在另一维上相邻接，则称这两个结点是邻居关系。第二十七页，编辑于星期六：十三点 十三分。CAN 的路由机制 由此，不难看出，对于d 维的坐标空间，每个结点有2d 个邻居结点，因此每个结点的坐标路由表会维护2d 个邻居的IP 地址和坐标信息。如2 维的坐标空间，每个结点有4个邻居结点，因此每个结点将维护4 个邻居结点的IP 地址和坐标空

17、间。因为每条CAN 消息都包含目的坐标，结点在路由时会将该消息转发给坐标路由表中距目的坐标最近的结点，直到目的坐标。第二十八页，编辑于星期六：十三点 十三分。n虚拟坐标空间采用下面的方法来保存（key，value）对：n当要保存（K1，V1）时，首先通过统一的哈希函数把关键字K1映射成坐标空间中的某个点P 的坐标，相应的（key，value）对即存放在点P 所在区的结点内。当需要查询关键字K1 对应的值时，任何结点都可以使用同样的哈希函数找到K1 对应的点P，并从点P 所在区的结点取出相应的值。n如果点P 所在区的结点不是发起查询请求的结点或其邻居，则CAN 负责将此查询请求路由到点P 所在区

18、的结点。因此，在CAN 中，有效的路由机制是一个关键问题。第二十九页，编辑于星期六：十三点 十三分。n。图2 给出了一个路由例子，虚线是点1 到点（x，y）的路由，图2 中还标明了在结点7 加入系统前结点1 的邻居结点集为2，3，4，5。n图2 路由例子对于划分成n 个同等大小的d 维坐标空间，平均路由长度为（d / 4）（n1 / d）跳，每个结点维护2d 个邻居的信息，这就意味着可以在不增加每个结点状态的同时增加网络结点数，而平均路由长度只以O（n1 / d）的数量级增长。而且，坐标空间中两个结点之间有多条不同路径，如果结点的一个或更多个邻居失效，结点可以自动沿着其它可用的路径路由第三十页

19、，编辑于星期六：十三点 十三分。新结点的加入n整个CAN 空间是由当前系统里所有的结点来动态划分的。每当新的结点加入时，系统必须为它分配相应的坐标空间。一般的做法是：n系统中某个现有的结点将自己的区域一分为二，自己保留一半，将另一半分配给新的结点。整个过程包括：n1）新的结点必须找到一个在CAN 中已经存在的结点；n2）通过CAN 的路由机制，新结点必须找到一个区域将要被分割的结点；n3）进行区域划分操作，并通知被分割区域的邻居有新的结点加入以便在邻居的坐标路由表中包含新的结点。第三十一页，编辑于星期六：十三点 十三分。在结点7 加入系统前结点1的邻居结点集为2，3，4，5。首先结点7 找到要

20、划分区域的结点，即结点1；然后，结点1 将自己的区域一分为二，自己保留一半，并将另一半区域分配给结点7；区域重新分割后，结点1 的邻居集变为2，3，4，7，结点7 的邻居集为1，2，4，5。第三十二页，编辑于星期六：十三点 十三分。结点离开，恢复n当结点离开CAN 系统时，要保证空出的区能移交给剩下的结点。正常的过程是结点明确地将它的区和相关的（ key，value）数据库移交给其中的一个邻居。如果某个邻居的区可以合并该区并产生单个有效的区，那么任务就完成了；如果不行，那么就将该区移交给区最小的邻居结点，该结点将暂时负责两个区。第三十三页，编辑于星期六：十三点 十三分。n正常情况下，结点周期性

21、地发布更新消息给它的每个邻居，更新消息中包含自己和邻居的区坐标列表。如果某个结点在给定时间内未收到邻居结点的更新消息，则说明该邻居结点失效。一旦某个结点失效，则它的每个邻居结点会分别初始化接管算法并启动接管定时器，定时器的大小和该结点拥有的区大小成比例。当定时器超时，每个邻居结点向其他所有邻居结点发送TAKEOVER 消息，消息中含有自己的区信息。每当收到一条TAKEOVER 消息时，每个邻居结点都会做同样的操作：比较自己的区和消息中的区，当消息中的区小于自己的区时，结点会取消自己的定时器，反之则回应自己的TAKEOVER 消息。用这种方法，可以有效地选择区小的存活邻居结点，由这个邻居结点接管

22、失效结点的区。第三十四页，编辑于星期六：十三点 十三分。Pastry 原理n功能：Pastry网络中每个节点都有一个唯一的节点号（nodeId）。当给定一条消息和一个关键字时，Pastry节点将会把这条信息路由到当前所有的Pastry节点中nodeId和关键字最接近的那个节点。路由过程的复杂度是O（logN），这里N是网络中Pastry节点的总数。n目标:Pastry考虑了网络的位置信息，使消息传递的距离最短。距离采用类似于IP路由的hop数的标量距离度量。 采用了启发式的算法，可以使关键字首先路由到在节点空间中与消息产生的节点距离最近的包括查找关键字的节点。第三十五页，编辑于星期六：十三点

23、十三分。Pastry原理节点分配制度nPastry系统中的每个节点都被分配一个128位的节点号。节点号用于在节点空间中标识节点的位置。节点号是在节点加入系统时随机分配的。分配策略是在节点空间中均匀分布。n节点号的获取：通过计算节点公钥或者IP地址的哈希函数值来获得。第三十六页，编辑于星期六：十三点 十三分。n为了进行路，我们把节点号和关键字表示为一串以2b 为基德数。Pastry吧消息路由到节点号从数值上最接近关键字的节点。具体过程如下：n在每个路由步骤中，但前节点将把消息路由给节点号和消息关键字的共同前缀长度至少比当前值长一个数位（b个二进制位）的节点。n如果不存在这样的节点，消息将传递给前

24、缀长度相同但是节点号更接近的关键字的节点。为了支持这样的路由过程，每个节点必须维护一定的路由状态。第三十七页，编辑于星期六：十三点 十三分。n每个Pastry节点都需要维护一张路由表，一个邻居节点集合和一个叶子节点集合。n路由表由log2 bN 的上取整行组成，每行包括2b -1个表项。第n行的2b -1个表项分别指向前n个数位和当前节点的前n个数位相同，而第n+1个数位取遍2b -1的可能的值（除掉当前节点第n+1位）。n这里b的大小的选择反应了在路由表大小和任意两点间路由需要的最大步数之间的折衷。n例如：b=4，网络中有106 个节点，每个节点的路由平均包括75个表项，预期的路由步数为5。

25、第三十八页，编辑于星期六：十三点 十三分。n邻居节点集合包括离当前节点最近的节点的标识符和IP地址。（正常的路由操作时用不到）。n主要作用：维护路由的位置属性。（保证路由表中每个表项指向的节点都是离当前节点最近的节点。）n叶子节点：存放的是与当前节点的标识符从数值上看最接近的节点。其中一半是节点号大于当前节点的，另一半是节点号小于当前节点的。叶子及诶按集合在消息路由时需要用到。n一般来说这两个集合的大小为2b 或2b *2。第三十九页，编辑于星期六：十三点 十三分。少图b=2节点号 10233102 所有的数均是四进制的路由表最上面的一行为0行。路由表中阴影项表示当前节点号对应的位，每项表示为

26、与10233102的共同前缀-下一数位-节点号的剩余位第四十页，编辑于星期六：十三点 十三分。Pastry的路由过程n当收到一条消息时，节点首先检查消息的关键字是否落在叶子节点的集合中。 n是，直接把消息转发给对应的节点，也就是说叶子节点的集合中节点号和关键字最接近的节点。n 否，使用路由表进行路由。当前节点把消息发送给节点号和关键字直接的共同前缀至少比现在节点长一个数位的节点。如果，路由表对应表项为空，或者路由表对应的节点不可达。这时消息会被转发给共同前缀一样长的及诶单。这个节点从数值上比当前节点更接近关键字。这样的节点一定位于叶子节点的集合中。第四十一页，编辑于星期六：十三点 十三分。节点

27、的加入n假定新加入的节点为X，X在加入Pastry前，需要知道一个相邻节点A的位置信息。X的加入过程分为以下两步：n1）初始化自己的节点数据结构n2）通知其他节点自己已经加入系统第四十二页，编辑于星期六：十三点 十三分。nX首先要求A的路由加入一条加入信息，消息的关键字就是X的节点号。与其他消息一样，这条消息会最终到达具有和X最接近的节点号的节点Z。n作为响应，节点A与节点Z以及A到Z的路径上的所有其它所有节点都会把自己的数据结构传给X。X利用这些信息初始化自己的数据结构。n初始化完成后，X将通知其它及诶单它已经加入了系统。按照消息数量来衡量，节点加入操作的复杂度为O（log2 bN）。第四十

28、三页，编辑于星期六：十三点 十三分。节点的失效n当相邻节点不能和某个Pastry节点通信时，就认为该节点发生了失效。n如果是叶子节点的集合L中的节点失效，则当前节点会要求当前叶子节点集合中最大节点号或最小节点号（根据失效节点的节点号决定，如果失效节点号比当前节点号大，则用最大节点号的节点，反之则用最小节点号的节点）的节点把它的叶子节点的集合L发送过来，L中必然存在L中没有的节点，当前节点将从中选择一个代替失效节点，在替代前，需要首先验证该节点是否还在系统中。第四十四页，编辑于星期六：十三点 十三分。n如果是路由表中某项对应的节点失效，那么当前节点将从该项所在的路由表行中选择另一个节点，要求它把

29、自己的路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点将从路由表的下一行中选择一个节点，这个过程继续，直到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由表为止。第四十五页，编辑于星期六：十三点 十三分。Tapestry原理nTapestry是用于覆盖网络的定位和路由机制，它可以对消息进行位置无关的路由，把消息传递到最近的存放所要求的对象拷贝的节点。n特点：自我管理、容错和灵活平衡负载等特点。nTapestry是基于Plaxton提出的定位和路由机制进行优化的。第四十六页，编辑于星期六：十三点 十三分。nPlaxton等人提出了一种分布式

30、数据结构，用于在网络范围内通过名称定位对象，并且将消息路由到这个对象。Plaxton中使用的数据结构称之为Plaxton mesh。Plaxton中，每个节点都可以承担服务器（保存对象）、路由器（转发消息）和客户端（请求发送者）的功能。对象和节点的标识符用一些算法（SHA-1哈希）确定（与位置和具体内容无关）。第四十七页，编辑于星期六：十三点 十三分。邻居映射表nPlaxton中每个节点都保存一张邻居映射表，这个表是用来把消息按照目的地址一位一位的向前传递。ne.g. 从*8到*98到*598到目的节点4598（*为通配符）这里的匹配方式 是从右稻作进行（与路由机制无关） 这种方式类似于IP分

31、组转发中的最长前缀匹配。第四十八页，编辑于星期六：十三点 十三分。n节点N的邻居映射表分为多个级别，每个级别表示的前缀长度对应于该级别在标识符中的位置，而每个级别包含的项的数量则等于标识符表示法的基数。ne.g. 级别j的第i项是以i+suffix（N，j-1）结尾的离当前节点最近的节点的标识符。 节点325AE 的邻居映射表中第四级第九项（j=4，i=9）是网络中以95AE结尾的离325AE最近的节点的标识符。第四十九页，编辑于星期六：十三点 十三分。n由上面的描述可知，当一条消息达到传递过程中的第n个节点时，该节点和目的节点的共同前缀长度至少大于n。为了进行转发，改进诶点将查找邻居映射表的

32、第n+1级，并选择其中的与目的节点标识符的下一位对应的项。转发过程将在每个节点中依次进行，直到到达目的节点。第五十页，编辑于星期六：十三点 十三分。Plaxton定位机制n允许一个客户端定位一个保存于服务器中的命名对象，并给该对象发送消息。服务器S通过给对象O的根节点发送消息来通知该节点保存着对象O。在这条路径上的每个节点都保存了一条关于对象O的位置信息（Object-ID（O），Server-ID（S），这里的位置信息是一个指向S的指针。当有多个对象存在时，只保存指向离根节点最近的对象的位置的指针。当需要定位一个对象时，客户方向对象的根节点发出消息，消息转发过程中如果碰到包括O的位置信息的节

33、点，则直接专项服务器S，否则，消息将到达O的根节点，然后从根节点转到服务器S。第五十一页，编辑于星期六：十三点 十三分。优点：错误处理简单 可扩展性好缺点：n构造Plaxton mesh时需要知道全局信息，从而导致节点的加入和离开操作相当复杂。n每个对象的根节点实际上成了一个单一失效点，如果该节点失效，该节点保存的对象将可能无法被访问到。n缺乏适应动态查询的能力。第五十二页，编辑于星期六：十三点 十三分。Plaxton的改进-Tapestryn路由机制：每张邻居映射表都按照路由层次组织，每个层次都包括匹配该层次对应的前缀并离该节点最近的一组节点。每个节点还维护一张后向指针列表指向把自己作为邻居

34、的那些节点。n定位机制：与Plaxton的定位机制类似，但其保存了所有的拷贝的位置信息以增加灵活性。Tapestry允许应用来决定如何在这多份数据拷贝中进行选择。第五十三页，编辑于星期六：十三点 十三分。n图5-9 第五十四页，编辑于星期六：十三点 十三分。节点失效n检测正常操作过程中的链路和服务器失效，可以用TCP连接超时机制。除此之外，每个Tapestry节点都使用后向指针周期性的发送UDP分组给把自己加入邻居映射表的节点。每个节点可以根据自己收到的UDP分组来决定自己的邻居映射表中是否有节点失效。在邻居节点表中，除了主邻居节点，每个路由项还保存了两个备份邻居节点，当检测到主邻居节点失效时

35、，邻居节点表将顺序选择备份邻居节点。第五十五页，编辑于星期六：十三点 十三分。节点的加入n类似Pastry，节点N加入Tapestry网络之前，需要已知一个已经在网络中的节点G。然后N通过G发出路由自己的节点ID的请求，根据经过的节点对应的邻居节点表构造自己的邻居节点表。构造完自己的数据结构后，节点N将通知网络中的其他节点自己已经加入网络，通知只针对在N的邻居映射表中的主邻居节点和二级邻居节点进行。第五十六页，编辑于星期六：十三点 十三分。节点的退出nTapestry采用两种机制处理节点的退出n节点从网络中自行消失（主要原因是节点失效），这时，它的邻居可以检测到它已经退出网络并可以相应的调整路

36、由表。n节点在退出系统之前通知 后向指针通知所有把它当做邻居的节点，这些节点会相应的调整路由表，并通知对象服务器该节点已经退出网络。第五十七页，编辑于星期六：十三点 十三分。n表5-2基于哈希表的路由机制有无法解决的问题。经过哈希后，节点的位置信息破坏了，来自同一个子网的站点很可能节点号相距甚远，这不利用查询性能的优化基于哈希表的系统不能利用应用本身的信息，许多应用（文件系统）的数据本身是按照层次结构组织的，使用哈希函数后，层次信息丢失了TerraDir提出了一种面向层次结构的查询机制。该机制通过缓存机制可以进一步提高查询性能。第五十八页，编辑于星期六：十三点 十三分。无结构的P2P网络nFr

37、eenet原理 Freenet是一种自适应的P2P网络，节点自己负责文件的查找和数据的交换。每个节点维护一个动态的路由表，该路由表中包含其他节点的地址和拥有的文件。每个文件用唯一的关键字key来表示，通过SHA1算法生成一个160位的二进制字符串作为文件的唯一标识。第五十九页，编辑于星期六：十三点 十三分。n缺点：没有机制来保证不会出现不同文件具有相同的Key。这一点依赖于SHA1的哈希算法本身的均匀性。第六十页，编辑于星期六：十三点 十三分。7116512AFEDCB348910012文件请求回复请求失败Peer with ObjectPeer requestFreenet 查询过程第六十一

38、页，编辑于星期六：十三点 十三分。Gnutella原理n非集中式控制的协议，应用较广泛。n特点：采用分布式的文件定位和相应方法。第六十二页，编辑于星期六：十三点 十三分。回复查询查询查询PeerPeerPeerPeerPeer查询回复下载Gnutella文件定位方法第六十三页，编辑于星期六：十三点 十三分。n为了控制这种广播流量，Guntella会设置TTL值（Time To Live）限制广播的半径。n优势：良好的健壮性和可扩展性。n缺点：查询开销很大n节点想要加入Gnutella网络，首先需要连接一些众所周知的可以连接的点，一旦建立连接，节点通告其它节点它的存在，这种通告以广播的方式进行。

39、每个消息赋予一个唯一的随机产生的标识，其它节点记录到该节点的路由信息，用来防止重新广播和向后传播。最后消息打上TTL和经过的跳数信息来控制消息的洪泛的范围。这些功能使得Gnutella成为了一个动态的、自组织的、具有独立实体的网络。n网络本身没有严格的拓扑结构，使得网络呈现幂率分布。第六十四页，编辑于星期六：十三点 十三分。FastTrack原理n基于超级节点的无结构文件分发网络。它的体系结构十分有利于文件的查找和定位。超级节点：具备高带宽、大磁盘以及较强CPU计算能力的节点，并且自愿为其它节点提供查询服务。超级节点间通过洪泛的方式进行查询。tipsn 优点：引入了超级节点，率先实现了层次化的

40、P2P网络。著名的Skype软件就是基于FastTrack协议的。第六十五页，编辑于星期六：十三点 十三分。对象上传Peer3：对象3对象上传回复地址：peer2查询对象2Super nodeSuper nodeSuper nodePeer 1Peer3Peer 2Peer2：对象2Peer3：对象3获得对象Peer2：对象2FastTrack工作机制第六十六页，编辑于星期六：十三点 十三分。KaZaA原理nKaZaA就是使用FastTrack的一个P2P应用。n超级节点具有很高的可用带宽，并且在相关的超级节点上存储量很多经常被请求的文件，且所有的查询都是指向超级节点的。KaZaA的数据传输是

41、通过非加密的HTTP协议完成的，但是所有的HTTP头都包含特定的特征码，从而很容易检测到KaZaA和普通的HTTP流量的区别。第六十七页，编辑于星期六：十三点 十三分。nKaZaA用户之间频繁的交互各自的超级节点信息，根据列表发现更多可用、稳定的资源，提高KaZaA的稳定性和自适应性。它采用动态端口，从而避免了使用固定端口的脆弱性，同时提供了连接反转的方法，解决了NAT问题。第六十八页，编辑于星期六：十三点 十三分。典型的P2P系统分析nBitTorrentnBitTorrent的客户端需要完成以下功能：n解析Torrent文件，获取要下载的文件的详细信息，并在磁盘上创建空文件。n与Track

42、er服务器建立连接，并交互信息。n根据从Tracker得到的信息，与其他Peers建立连接，并下载需要的文件片段。n监听某端口，等待其他peer的连接，并提供文件片段的上传。nBitTorrent客户端需要处理以下两种协议：n与Tracker服务器交互的TrackHTTP协议n与其他peer交互的BitTorrent对等协议第六十九页，编辑于星期六：十三点 十三分。nBitTorrent软件用户首先从Web服务器上获得下载文件的种子文件，种子文件中包含下载文件名及数据部分的哈希值，还包含一个或者多个的索引(Tracker)服务器地址。n它的工作过程如下：客户端向索引服务器发一个超文本传输协议(

43、HTTP)的GET请求，并把它自己的私有信息和下载文件的哈希值放在GET的参数中；索引服务器根据请求的哈希值查找内部的数据字典，随机地返回正在下载该文件的一组节点，客户端连接这些节点，下载需要的文件片段。第七十页，编辑于星期六：十三点 十三分。n因此可以将索引服务器的文件下载过程简单地分成两个部分：n与索引服务器通信的HTTP，与其他客户端通信并传输数据的协议，我们称为BitTorrent对等协议。BitTorrent协议也处在不断变化中，可以通过数据报协议(UDP)、Tracker服务器或者DHT的方法获得可用的传输节点信息，新版的bitComet允许同行连接DHT和Tracker，而不是仅

44、仅通过原有的HTTP，这种方法使得BitTorrent应用更加灵活，（完全不连接上Tracker服务器的情况下，也可以很好的下载，因为可以再DHT网络中寻找下载同一文件的其他用户。）提BitTorrent用户的下载体验。第七十一页，编辑于星期六：十三点 十三分。n通过Tracker服务器返回可用节点列表，Tracker服务器维护一个四级的字典结构，当用户请求到达时，Tracker会查询二级字典的HashID，从而获得三级字典的内容，即下载这个文件的所有peer。四级字典详细的描述了这个peer的IP地址和端口情况。Tracker无武器调用函数Peerlist随即返回给用户一个三级字典的子集。客

45、户端根据返回的列表连接并下载所需要的数据。第七十二页，编辑于星期六：十三点 十三分。EmuleneMule软件基于eDonkey协议改进后的协议，同时兼容eDonkey协议。n每个eMule客户端都预先设置好了一个服务器列表和一个本地共享文件列表，客户端通过TCP连接到eMule服务器进行登录，得到想要的文件的信息以及可用的客户端的信息。一个客户端可以从多个其他的EMule客户端下载同一个文件，并从不同的客户端取得不同的数据片段。neMule同时扩展了eDonkey的能力，允许客户端之间互相交换关于服务器、其他客户端和文件的信息。eMule服务器不保存任何文件，它只是文件位置信息的中心索引。n

46、eMule客户端一启动就会自动使用传输控制协议(TCP)连接到eMule服务器上。服务器给客户端提供一个客户端标识(ID)，它仅在客户端服务器连接的生命周期内有效。连接建立后，客户端把其共享的文件列表发送给服务器。服务器将这个列表保存在内部数据库内。eMule客户端也会发送请求下载列表。连接建立以后，eMule服务器给客户端返回一个列表，包括哪些客户端可以提供请求文件的下载。然后，客户端再和它们主动建立连接下载文件。第七十三页，编辑于星期六：十三点 十三分。neMule基本原理与BitTorrent类似，客户端通过索引服务器获得文件下载信息，但eMule客户端与BitTorrent不同的是，e

47、Mule可以做自定义的地址过滤，可以屏蔽掉一些IP的请求和传输。eMule同时允许客户端之间传递服务器信息，BitTorrent只能通过索引服务器或者DHT获得。eMule共享的是整个文件目录，而BitTorrent只共享下载任务，这使得BitTorrent更适合分发热门文件，eMule倾向于一般热门文件的下载。与此同时，Emule支持任务优先级和用户优先级策略，因此客户端可以根据自己的需求，制定相应的节点选择策略。第七十四页，编辑于星期六：十三点 十三分。迅雷n迅雷是一款新型的基于多资源多线程技术的下载软件，迅雷拥有比目前用户常用的下载软件快710倍的下载速度。n迅雷的技术主要分成两个部分，

48、一部分是对现有Internet下载资源的搜索和整合，将现有Internet上的下载资源进行校验，将相同校验值的统一资源定位(URL)信息进行聚合。当用户点击某个下载连接时，迅雷服务器按照一定的策略返回该URL信息所在聚合的子集，并将该用户的信息返回给迅雷服务器。另一部分是迅雷客户端通过多资源多线程下载所需要的文件，提高下载速率。迅雷高速稳定下载的根本原因在于同时整合多个稳定服务器的资源实现多资源多线程的数据传输。多资源多线程技术使得迅雷在不降低用户体验的前提下，对服务器资源进行均衡，有效降低了服务器负载。n每个用户在网上下载的文件都会在迅雷的服务器中进行数据记录，如有其他用户再下载同样的文件，迅雷的服务器会在它的数据库中搜索曾经下载过这些文件的用户，服务器再连接这些用户，通过用户已下载文件中的记录进行判断，如用户下载文件中仍存在此文件(文件如改名或改变保存位置则无效)，用户将在不知不觉中扮演下载中间服务角色，上传文件。第七十五页，编辑于星期六：十三点 十三分。第七十六页，编辑于星期六：十三点 十三分。