P2P技术及其发现与定位

1、P2P技术及其资源发现与定位摘要P2P主要指计算机之间以对等方式形成的网络连接，弱化或完全取消了效劳器的作用。文章从分析P2P的根本概念、需求和开展入手,讨论了P2P与网格和/S的联络和区别，并列举了现今P2P的主要应用，最后，对目前P2P中存在的资源发现与定位问题做了分析和阐述。关键字P2P、资源管理、Gnutella、哈希查找1P2P技术简介1.1概念及特征P2P是peertpeer的缩写，是指：通过使用分布资源，借助于分布计算技术来完成关键任务的系统和应用的总称。这里的分布式资源包括计算才能、数据包括存储介质和内容、网络带宽和其它资源如计算机、人力资源等；分布计算包括算法、数据、元数据等

2、，或者是三者总体；关键任务包括分布计算、数据或内容共享、通信与协作，或者是平台效劳等。P2P技术的主要特征是弱化效劳器作用，甚至取消效劳器，使分布式系统中的各个节点逻辑对等，这种技术出现的目的就是希望可以充分利用网络中所蕴含的潜在资源。与/S模型不同，P2P模型中每个节点既可以是效劳或者资源的提供者，也可以是使用者，充其量就是提供的效劳或资源的类型不同。1.2需求与背景随着网络技术的飞速开展和网络规模的不断扩大，接入网络的主机增加，可用资源丰富，然而目前的互联网仍然是以/S形式为主，尤其是eb技术的开展使得许多eb效劳器成为信息的主要提供源，整个Internet系统依附于这些少量的效劳器节点，

3、而大量的个人主机中的资源却成了网络中的信息孤岛，无法得到充分利用，能否发挥这些闲散资源的使用效率或者作用构成了人们关注P2P的理由。1.3P2P与网格的联络与区别网格与P2P在技术上没有本质区别，都是在广域网条件下实现资源共享和分布计算。正因如此，全球网格论坛GGF与对等网络研究小组P2PG已宣布合并。但二者也有一定的区别。网格类似于电力系统，格点或者节点类似发电站，通过整个网络输送给用户，相对于P2P，更象是将一些大型资源组织起来，供社会共享，我国目前正在施行的生物研究网格和网络教育效劳网格都可作为其辅证；P2P那么泛指闲散资源的组织。1应用面网格较侧重于重大科学计算和大型专业性的协同，其一

4、个或多个主要节点仍有较重的效劳器色彩；P2P提供普通的信息、计算效劳，每个参与者明显地兼有客户、效劳器双重身份。2访问对象网格访问计算资源、数据资源、软件资源，相对来说，有较固定的目的；P2P完全是随机访问，随机使用。3平安性网格中每个节点都有身份鉴定、受权、防火墙保护的才能；P2P每个参与者不保证这些才能，甚至是匿名的。4控制网格在资源监视/分配和作业调度上仍有较多的集中控制；P2P仅有很少的或没有集中控制，主要靠自行组织。5效劳质量网格确保可靠的效劳质量；P2P只有局部的保证，某些参与者甚至是不可信的。以上这些区别是相对而言，随着不断开展和改良，这些区别会逐步缩校1.4P2P与/S的联络从

5、某种程度上说，也许不应该将P2P和/S形式完全的对立起来，就某项特定的应用，以及特定的时间，P2P网络也许是以/S方式进展工作的。例如：假如每个用户都有一些软件资源例如文字处理程序或者硬件设施例如：打印机，自然，可以采用P2P的方式进展可控共享，此时，提供打印机的客户本地的某个进程就临时充当了效劳器的角色。再分析一下目前的eb工作方式，我们更多的应用是文件或者资料的查找，eb页面成为文件资源的目录，存储对应文件的主机成为提供者，原理上，该主机可以独立于eb效劳器，这也可认为是P2P的一种形式。2P2P资源发现与定位目前P2P技术已在文件交换，分布式计算，搜索，信息共享，协同工作，即时通信，网络

6、游戏等等方面得到了广泛的应用，还有一些公司在开发基于P2P的平台。但是，无论是通信、P2P协作、分布式搜索引擎还是共享计算和交互式游戏等功能的实现，都只能以很好解决网内资源的迅速准确定位问题为前提。所以，P2P网络中资源发现是及其重要的。目前，资源的定位一般采用的是“地址查询的方法，即：每个资源有一个全局唯一标识符ID和一个包含其所在地址的指针P，系统将ID,P保存起来，当用户需要访问该资源时，根据ID来查询P，从而进展定位。定位机制有不同的实现方法。按照实现系统的体系构造，主要可以分为两类：集中目录式、泛洪恳求式2.1集中目录式在集中目录式entralIndexServer中，有一个类似于效

7、劳器的节点集中提供资源索引信息。当用户共享资源时，需将资源的ID,P向索引效劳器进展资源注册，索引效劳器中保存着系统中所有资源的标识符和指针列表。当用户需要查找资源时，首先通过资源标识符查询索引效劳器，效劳器返回该资源的指针，用户通过该指针定位。当定位到资源的存储位置后，资源的下载在节点之间直接进展，与索引效劳器没有关系。集中式的优点是：简单、容易实现。大多数的分布式系统采用的都是这种方法，例如：三种分布式对象计算环境RBA,D,JAVARI提供的分布对象名字效劳、大量的通用目录效劳如X.500、LDAP和NIS和一些实用分布式系统如Napster的资源定位方法等。集中式的缺点很明显：类似于/

8、S形式，缺乏可扩展性和存在单点故障问题。图1集中目录式图2泛洪恳求式图3分布式Hash式2.2泛洪恳求式与集中目录式不同，泛洪恳求式FldingRequest没有中央目录效劳器，用户的恳求通过所有连接的节点传递，这些节点或者响应该恳求，或者在不能满足恳求时，将该恳求向与自己相连的其他节点播送，直到恳求得到响应为止泛洪。为了减少播送带来的网络带宽浪费，一般将播送传递限制在78跳以内，即假如恳求在经过有限的循环播送之后，仍不能得到响应，那么发送恳求的节点将得到一个错误信息。Gnutella是泛洪的经典之作，Gnutella协议设置了三种机制来控制消息数量的指数增长。机制一:消息生存时间(Tie-t

9、-Live简称TTL)消息生存时间主要是控制消息在网络中传播时可以生存的时间，是消息头中的一个字段，在消息生成时被赋予一个初始值。当消息被发送出去，其它主机结点接收到该消息时，首先将该消息的TTL值减1，假如为零，那么将该消息丢弃掉。否那么，发给它的邻居结点。TTL值越大，消息能传播的间隔 就越远，反之，就越近。机制二:消息的唯一标识符(UniqueessageIdentifiatin简称UID).消息的唯一标识符是为了防止一个消息在同一个主机节点重复传播而设计的。UID也被包含在消息头中，每个消息的标识符都是不一样的。当消息被发送出去，其它主机结点接收到该消息时，取出它的消息头中的UID字段

10、，同本地记录的UID列表相比拟，假如该消息的UID己经在列表中，说明该主机结点己经看过这条消息，它将直接把这条消息丢弃掉。否那么，假如该消息的UID不在本地列表中，该主机结点将储存这条消息的UID到本地UID列表，然后将该消息传播出去。机制三:途径标识符(PathIdentifiatin)。途径标识符是为了防止消息循环的出现及指导返回消息按原路返回而设置的。途径标识符其实是一个地址列表，记录了该消息所经过的结点的地址。当一个主机结点接收到一条消息后，该主机结点会检查自己的主机地址是否在消息所经过的地址列表中，假设在，说明该条消息已经到过该主机结点，那么该主机结点会将这条消息直接丢弃。否那么，该

11、主机将自己的地址参加消息的地址列表中，然后发送出去。以上三个控制机制保证了消息在网络中不会被无限制的扩散，从而确保Gnutella网络可以正常的运行。但是，这三种控制机制也不是尽善尽美，也会导致很多问题，其中之一便是短路效应。泛洪恳求式由于通过播送方式进展查找和定位，因此一般扩展性差，但在小范围内效率高，可靠性好。此外假如在系统中存在一些所谓的超级节点即该节点拥有大量的资源信息，那么可以显著减少带宽的浪费。目前第二代泛洪恳求式的资源定位主要采用分布式Hash表算法：赋予系统中每个节点一个全局唯一标识符NID，通过一个哈希函数建立起资源唯一标识符ID和NID之间的对应关系：NIDHASH(ID)

12、，NID与ID是一对多的关系。将资源的定位信息ID,P保存到节点标识符为HASHID的节点上。当用户需要查找对象时，首先通过ID和哈希函数计算出该资源定位信息所在节点的标识符HASH(ID)，然后将该恳求发送到该节点上，即可找到该对象。由于P2P中，任意两个节点可以通讯，并且各个节点上的哈希函数都一样，因此，只要知道对象的ID，用户可以从任何一个节点出发找到该对象。根据节点的NID与ID之间的映射关系不同，分布式Hash表算法有许多不同的实现形式，如hrd、AN、Pastry、Tapestry等。目前的最好效率是发现资源需要的路由表长度为lgNN为P2P网络总节点数，查询资源需要的通信量为lg

13、N。2.3现有的问题与改良图4短路效应的成因如上所述，Gnutella中存在着短路效应。如图4所示，假设Gnutella网络上有A,B,三台主机，当有消息(TTL=t)由主机A发出，假设有两条途径可以到达主机B，一条途径是沿Ll(x1,x2,xp),途径长度为p；一条是L2(y1,y2,yq)，途径长度为q。另有一条由主机B到主机的途径L3(z1,zr)，途径长度为r，其中有p+rt且q+rt。设从途径Ll传递的消息称为1，把从途径L2传递的消息称为2。按照Gnutella的传输协议及以上介绍的三种控制机制，从主机A发出的消息，应该可以到达所有的符合以下条件的主机：这些主机间隔 主机A的跳数小

14、于初始TTL值(从一个主机到另外一个与它直接相连的主机的间隔 称之为一跳)。按照这条规那么，从主机A发出的消息也应该可以到达主机，因为存在这样一条途径y1，yq,z1,，zr)，该途径长度(q+r)小于消息的初始TTL值t。但是，由于网络异构延迟的影响，消息却可能无法到达主机。原因在于从主机A到主机B的传输过程中，假设从途径Ll传递的消息1先于从途径L2传递的消息2到达主机B，主机B在收到1后，检查它的UID及TTL，发现此UID并不在本地的消息列表中，它的TTL值t-p也大于0，所以它会先记录1的UID到本地的消息列表，然后将TTL值减去1，最后将1发送给它的所有的邻居。但是1肯定无法到达主

15、机，因为从主机A到主机的跳数p+r大于消息的初始TTL值。在主机B处理过消息1后，沿途径L2的消息2也将到达该主机。因为2和1都是同一条消息的两个副本，它们的UID也必然一样，因此当主机B检查消息2的UID时，会发现该UID己经存在于本地的UID列表中，按照控制机制二，主机B会丢弃消息2。如此一来，便没有可以到达主机的消息。这就是短路效应。需要说明的是，当网络规模大到一定的程度时，由于网络构造、带宽等的差异，异构延迟现象的存在是很正常并且是很普遍的。实验说明，在如今的Gnutella网络中，在异构延迟的影响下，消息的可达率一般在55%左右，即一条消息发出后，在应该收到该消息的主机中，约有一半数

16、量的主机实际上收不到这条消息。这就大大降低了整个Gnutella网络的查询效率。在原来的机制二中，主机结点在检查完消息的UID后，假如发现该UID已经在本地的消息列表中，那么直接就将它丢弃了。从以上的分析知道，这是不合理的，因为该消息有可能到达比己经存在的那条消息更远的间隔 。因此，可以首先保存每一条消息的TTL值，当一个主机结点检查一条消息的UID，发现该UID已经存在时，再检查该消息的TTL值，假如新的消息的TTL值比原来保存的TTL值要大，那么将用较大的TTL值交换较小的TTL值，并将该消息继续前传播。这里用较大的TTL值交换较小的TTL值，是考虑到假如后面还有另一个网络延迟更厉害但TT

17、L值更大的副本到达时，主机不会把它丢弃掉。但是，这样改良之后还会引发另外一个返回结果的问题。如图4，当1到达主机B后，假如它有主机A要查询的数据，那么主机B会产生一条回应消息，沿着1来时的途径传送到主机A。那么当消息2到达时，主机B还会产生一条回应消息，沿着2的途径传送到主机A。但是2的回应消息己经没有必要，因为一是2的途径延迟要比1厉害，二是多发送的那条消息是重复的，白白占用了网络的带宽。因此做一个规定，当一个主机先后接收到一样UID的消息后，假如需要回应，只回应第一条消息，其它的在做完TTL及UID检查后，或丢弃，或只简单的传给它的邻居结点。3完毕语虽然P2P的概念出现由来已久，但是随着I

18、nternet的迅猛开展近年来对其的研究和应用日益成为热点。目前Intel，SUN等多家国际IT企业都在投入相当大的力量研究适用的P2P计算模型及其实现。由于P2P技术在对等计算、协同工作方面的强大优势，今后肯定会在这两个方面迅猛开展；将P2P技术和/S形式的互联网结合起来，在搜索引擎、文件共享方面国内外已经有不少商业化产品投入使用，但由于P2P技术本身存在不易管理、平安性差等缺陷，造成P2P技术自出现以来，并没有大规模应用，而且这两个问题假如得不到有效解决，将会成为P2P技术在这两个方面开展的主要瓶颈。参考文献1.L.TassiulasandA.Ephreides,StabilityprpertiesfnstrainedqueuEingsystesandshedulingpliiesfraxiuthrughputinultihpradinetrks.IEEETransatinsnAutatintrl，Vl37,N12,De.