《P2P技术及其资源发现与定位》由会员分享，可在线阅读，更多相关《P2P技术及其资源发现与定位（5页珍藏版）》请在金锄头文库上搜索。
1、1P2P 技术及其资源发现与定位摘 要 P2P 主要指计算机之间以对等方式形成的网络连接，弱化或完全取消了服务器的作用。文章从分析 P2P 的基本概念、需求和发展入手,讨论了 P2P 与网格和 C/S 的联系和区别，并列举了现今 P2P 的主要应用，最后，对目前 P2P 中存在的资源发现与定位问题做了分析和论述。关键字 P2P、资源管理、Gnutella、哈希查找1 P2P 技术简介1.1 概念及特征P2P 是 peer to peer 的缩写，是指：通过使用分布资源，借助于分布计算技术来完成关键任务的系统和应用的总称。这里的分布式资源包括计算能力、数据（包括存储介质和内容）、网络带宽和其它资
2、源（如计算机、人力资源等）；分布计算包括算法、数据、元数据等，或者是三者总体；关键任务包括分布计算、数据（或内容）共享、通信与协作，或者是平台服务等。 P2P 技术的主要特征是弱化服务器作用，甚至取消服务器，使分布式系统中的各个节点逻辑对等，这种技术出现的目的就是希望能够充分利用网络中所蕴含的潜在资源。与 C/S 模型不同，P2P 模型中每个节点既可以是服务（或者资源）的提供者，也可以是使用者，充其量就是提供的服务（或资源）的类型不同。1.2 需求与背景随着网络技术的飞速发展和网络规模的不断扩大，接入网络的主机增加，可用资源丰富，然而目前的互联网仍然是以 C/S 模式为主，尤其是 Web 技术
3、的发展使得许多 Web 服务器成为信息的主要提供源，整个 Internet 系统依附于这些少量的服务器节点，而大量的个人主机中的资源却成了网络中的信息孤岛，无法得到充分2利用，能否发挥这些闲散资源的使用效率（或者作用）构成了人们关注 P2P 的理由。1.3 P2P 与网格的联系与区别网格与 P2P 在技术上没有本质区别，都是在广域网条件下实现资源共享和分布计算。正因如此，全球网格论坛（GGF）与对等网络研究小组（P2PWG）已宣布合并。但二者也有一定的区别。网格类似于电力系统，格点（或者节点）类似发电站，通过整个网络输送给用户，相对于 P2P，更象是将一些大型资源组织起来，供社会共享，我国目前
4、正在实施的生物研究网格和网络教育服务网格都可作为其辅证；P2P 则泛指闲散资源的组织。（1）应用面网格较侧重于重大科学计算和大型专业性的协同，其一个或多个主要节点仍有较重的服务器色彩；P2P 提供普通的信息、计算服务，每个参与者明显地兼有客户、服务器双重身份。（2）访问对象网格访问计算资源、数据资源、软件资源，相对来说，有较固定的目标；P2P 完全是随机访问，随机使用。（3）安全性网格中每个节点都有身份鉴定、授权、防火墙保护的能力；P2P 每个参与者不保证这些能力，甚至是匿名的。（4）控制网格在资源监视/分配和作业调度上仍有较多的集中控制；P2P 仅有很少的或没有集中控制，主要靠自行组织。（5
5、）服务质量网格确保可靠的服务质量；P2P 只有部分的保证，某些参与者甚至是不可信的。3以上这些区别是相对而言，随着不断发展和改进，这些区别会逐步缩小。1.4 P2P 与 C/S 的联系从某种程度上说，也许不应该将 P2P 和 C/S 模式完全的对立起来，就某项特定的应用，以及特定的时间，P2P 网络也许是以 C/S 方式进行工作的。例如：如果每个用户都有一些软件资源（例如文字处理程序）或者硬件设施（例如：打印机），自然，可以采用 P2P 的方式进行可控共享，此时，提供打印机的客户（本地的某个进程）就临时充当了服务器的角色。再分析一下目前的 Web 工作方式，我们更多的应用是文件（或者资料）的查
6、找，Web 页面成为文件资源的目录，存储对应文件的主机成为提供者，原理上，该主机可以独立于 Web 服务器，这也可认为是 P2P 的一种形式。2 P2P 资源发现与定位目前 P2P 技术已在文件交换，分布式计算，搜索，信息共享，协同工作，即时通信，网络游戏等等方面得到了广泛的应用，还有一些公司在开发基于 P2P 的平台。但是，无论是通信、P2P 协作、分布式搜索引擎还是共享计算和交互式游戏等功能的实现，都只能以很好解决网内资源的迅速准确定位问题为前提。所以，P2P 网络中资源发现是及其重要的。目前，资源的定位一般采用的是“地址查询”的方法，即：每个资源有一个全局唯一标识符 OID 和一个包含其
7、所在地址的指针 P，系统将OID,P保存起来，当用户需要访问该资源时，根据 OID 来查询 P，从而进行定位。定位机制有不同的实现方法。按照实现系统的体系结构，主要可以分为两类：集中目录式、泛洪请求式2.1 集中目录式在集中目录式（Central Index Server）中，有一个类似于服务器的节点集中提供资4源索引信息。当用户共享资源时，需将资源的OID,P向索引服务器进行资源注册，索引服务器中保存着系统中所有资源的标识符和指针列表。当用户需要查找资源时，首先通过资源标识符查询索引服务器，服务器返回该资源的指针，用户通过该指针定位。当定位到资源的存储位置后，资源的下载在节点之间直接进行，与
8、索引服务器没有关系。集中式的优点是：简单、容易实现。大多数的分布式系统采用的都是这种方法，例如：三种分布式对象计算环境（CORBA,DCOM,JAVA RMI）提供的分布对象名字服务、大量的通用目录服务（如 X.500、LDAP 和 NIS）和一些实用分布式系统（如Napster）的资源定位方法等。集中式的缺点很明显：类似于 C/S 模式，缺乏可扩展性和存在单点故障问题。 图 1 集中目录式 图 2 泛洪请求式 图 3 分布式 Hash 式2.2 泛洪请求式与集中目录式不同，泛洪请求式（Flooding Request）没有中央目录服务器，用户的请求通过所有连接的节点传递，这些节点或者响应该请
9、求，或者在不能满足请求时，将该请求向与自己相连的其他节点广播，直到请求得到响应为止（泛洪）。为了减少广播带来的网络带宽浪费，一般将广播传递限制在 78 跳以内，即如果请求在经过有限的循环广播之后，仍不能得到响应，则发送请求的节点将得到一个错误信息。 Gnutella 是泛洪的经典之作，Gnutella 协议设置了三种机制来控制消息数量的指数增长。机制一:消息生存时间(Time-to-Live 简称 TTL) 消息生存时间主要是控制消息在网络中传播时能够生存的时间，是消息头中的一个字段，在消息生成时被赋予一个初始值。当消息被发送出去，其它主机结点接5收到该消息时，首先将该消息的 TTL 值减 1
10、，如果为零，则将该消息丢弃掉。否则，发给它的邻居结点。TTL 值越大，消息能传播的距离就越远，反之，就越近。机制二:消息的唯一标识符(Unique Message Identification 简称 UID).消息的唯一标识符是为了避免一个消息在同一个主机节点重复传播而设计的。UID 也被包含在消息头中，每个消息的标识符都是不一样的。当消息被发送出去，其它主机结点接收到该消息时，取出它的消息头中的 UID 字段，同本地记录的UID 列表相比较，如果该消息的 UID 己经在列表中，说明该主机结点己经看过这条消息，它将直接把这条消息丢弃掉。否则，如果该消息的 UID 不在本地列表中，该主机结点将储
11、存这条消息的 UID 到本地 UID 列表，然后将该消息传播出去。机制三:路径标识符(Path Identification)。路径标识符是为了防止消息循环的出现及指导返回消息按原路返回而设置的。路径标识符其实是一个地址列表，记录了该消息所经过的结点的地址。当一个主机结点接收到一条消息后，该主机结点会检查自己的主机地址是否在消息所经过的地址列表中，若在，说明该条消息已经到过该主机结点，则该主机结点会将这条消息直接丢弃。否则，该主机将自己的地址加入消息的地址列表中，然后发送出去。以上三个控制机制保证了消息在网络中不会被无限制的扩散，从而确保 Gnutella网络可以正常的运行。但是，这三种控制机
12、制也不是尽善尽美，也会导致很多问题，其中之一便是短路效应。泛洪请求式由于通过广播方式进行查找和定位，因此一般扩展性差，但在小范围内效率高，可靠性好。此外如果在系统中存在一些所谓的超级节点（即该节点拥有大量的资源信息），则可以显著减少带宽的浪费。目前第二代泛洪请求式的资源定位主要采用分布式 Hash 表算法：赋予系统中每6个节点一个全局唯一标识符 NID，通过一个哈希函数建立起资源唯一标识符 OID和 NID 之间的对应关系：NIDHASH(OID)，NID 与 OID 是一对多的关系。将资源的定位信息OID,P保存到节点标识符为 HASH（OID）的节点上。当用户需要查找对象时，首先通过 OI
13、D 和哈希函数计算出该资源定位信息所在节点的标识符 HASH(OID)，然后将该请求发送到该节点上，即可找到该对象。由于 P2P 中，任意两个节点可以通讯，并且各个节点上的哈希函数都相同，因此，只要知道对象的 OID，用户可以从任何一个节点出发找到该对象。根据节点的 NID 与 OID 之间的映射关系不同，分布式 Hash 表算法有许多不同的实现形式，如 Chord、CAN、Pastry、Tapestry 等。目前的最好效率是发现资源需要的路由表长度为 logN（N 为 P2P 网络总节点数），查询资源需要的通信量为logN。2.3 现有的问题与改进图 4 短路效应的成因如上所述，Gnutel
14、la 中存在着短路效应。如图 4 所示，假设 Gnutella 网络上有A,B,C 三台主机，当有消息 M(TTL=t)由主机 A 发出，假设有两条路径可以到达主机 B，一条路径是沿 Ll(x1,x2 ,xp),路径长度为 p；一条是 L2(y 1,y2 ,yq)，路径长度为 q。另有一条由主机 B 到主机 C 的路径 L3(z1, zr)，路径长度为 r，其中有 p+rt 且 q+rt。设从路径 Ll 传递的消息称为 M1，把从路径 L2 传递的消息称为 M2。按照 Gnutella 的传输协议及以上介绍的三种控制机制，从主机 A 发出的消息，应该能够到达所有的符合以下条件的主机：这些主机距
15、离主机 A 的跳数小于初始 TTL 值(从一个主机到另外一个与它直接相连的主机的距离称之为一跳)。按照这条规则，从主机 A 发出的消息 M 也应该能够到达主机 C，因为存在这7样一条路径（y1，yq,z1 ,，zr)，该路径长度(q+r)小于消息的初始 TTL 值 t。但是，由于网络异构延迟的影响，消息 M 却可能无法到达主机 C。原因在于从主机A 到主机 B 的传输过程中，假设从路径 Ll 传递的消息 M1 先于从路径 L2 传递的消息 M2 到达主机 B，主机 B 在收到 M1 后，检查它的 UID 及 TTL，发现此 UID并不在本地的消息列表中，它的 TTL 值 t-p 也大于 0，所
16、以它会先记录 M1 的 UID到本地的消息列表，然后将 TTL 值减去 1，最后将 M1 发送给它的所有的邻居。但是 M1 肯定无法到达主机 C，因为从主机 A 到主机 C 的跳数 p+r 大于消息的初始 TTL 值。在主机 B 处理过消息 M1 后，沿路径 L2 的消息 M2 也将到达该主机。因为 M2 和 M1 都是同一条消息的两个副本，它们的 UID 也必然相同，因而当主机 B 检查消息 M2 的 UID 时，会发现该 UID 己经存在于本地的 UID 列表中，按照控制机制二，主机 B 会丢弃消息 M2。如此一来，便没有可以到达主机 C 的消息。这就是短路效应。需要说明的是，当网络规模大到一定的程度时，由于网络结构、带宽等的差异，异构延迟现象的存在是很正常并且是很普遍的。实验表明，在现在的 Gnutella 网络中，在异构延迟的影响下，消息的可达率一般在 55%左右，即一条消息发出后，在应该收到该消息的主机中，约有一半数量的主机实际上收不到这条消息。这就大大降低了整个 Gnutella 网络的查询效率。在原来的机制二中，主机结点在检查完消息的 UID 后，如
