对等网络概念原理机制及应用.doc

《对等网络概念原理机制及应用.doc》由会员分享，可在线阅读，更多相关《对等网络概念原理机制及应用.doc（17页珍藏版）》请在三一办公上搜索。

1、对等网络概念原理及应用一、对等网络概述1.1 对等网络的定义集中式管理与控制模式 网络结点在功能上是不平等的，总有一些少数结点在网络中占居中心主导地位，管理其它从属结点可执行的操作，控制它们间的信息交互。其特点是网络管理复杂度小且易于控制，但不足是网络工作效率低、规模扩展性不好且存在单点故障。分布式管理与控制模式 网络结点在功能上是平等的，网络中没有结点比其它结点拥有更大的特权，网络的管理与控制有各个结点间的相互协作来完成的。其特点是网络工作效率高、规模扩展性强，但网络管理复杂度大且不易于控制。虽着因特网规模的不断扩大与应用功能的不断扩展，目前因特网主流应用模式-客户服务器模式已不能满足用户的

2、实际需求。迫切需要新的应用模式。对等计算思想本质：打破传统的网络集中管理与控制的客户服务器模式，使网络成员享有自由、平等、互联的权力。对等网络（Peer-to-Peer network，P2P）：分布式系统与计算机网络相结合的产物，是采用对等计算模式工作的计算机网络（应用服务）。每个节点在行为上是自由的，在功能上是平等的，在关系上是互联的。所有节点分布式地自组织成一个整体网络，能够极大地提高网络效率，充分地利用网络带宽，发挥每个网络节点的潜能。对等计算起源于1956年，但由于当时的网络技术条件的限制与网络应用没有充分地发展起来，一直未引起学术、工业与商业界重视，因此，它的发展十分缓慢。网络应用

3、实践表明：任何一种思想、理论与技术的流行通常需要一个杀手级的应用（killer application）,以一种征服性的力量冲击人们的传统思维。对等网络的杀手锏级的应用则出现在1999年，第一个应用性对等网络Napster，一种音乐下载软件，创造了在半年时间内拥有5000万用户的网络奇迹，向世人展示了对等网络的优异性能和巨大潜力。继Napster之后，又有一系列随着人们耳熟能详的对等网络应用软件，如Gnutella、KaZaA、BitTorrent、eDonkey/eMule、Skype等，进入了日常网络应用之中，其流量占据Internet总流量的一半以上，已成为改变Internet的新一代网

4、络应用技术从对等网络的设计思想出发，兼顾已有的网络体系结构和出现的时间两方面因素，对等网络可分为三代：第一代 混合式对等网络 它是C/S与P2P两种模式的混合结果；第二代 无结构对等网络 它以分布、松散的结构来组织网络；第三代 结构化对等网络 它以准确、严格的结构来组织网络，并能有效地定位节点和数据。对等网络与已有的TCP/IP的关系 对等网络应用与以前讲述的客户/服务器模式、集中式系统与分布式系统等均都是指工作在应用层上的工作方式，而TCP/IP体系的下三层通常采用标准与单一的工作方式，为应用层不同的工作方式提供服务的。对等网络的核心机制对等网络是在应用层建立逻辑上的覆盖网络（Overlay

5、 Network）,它不考虑下面三层是如何工作的，将注意力集中于覆盖网络的设计与优化上。注意覆盖网络中两个节点间的路径序列与其对应在IP网络中路径序列常常是不一致的。（图陈贵海p.5图1.1.4）对等网络的核心机制是由围绕在一个确定覆盖网络结构上采用某种方法能准确与快速地路由消息和定位数据对象的一系列处理过程组成。这些处理过程主要如下：覆盖网拓扑结构、分布式散列表、路由和定位、 查询和搜索、动态结点算法以及容错性。例如 在有结构的覆盖网络上依靠分布式散列函数（ Distributed Hash Table,DHT）能准确与快速地路由消息和定位数据对象。这个核心机制的不足是语义模糊查询的困难和对

6、动态网络环境中错误行为的容忍性下降。1.2 对等网络的发展历程 第一阶段（1999-2000）：混合结构的对等网络1999年Shawn Fanning 开发了世界第一个应用性P2P网络软件Napster，它是第一代P2P网络-混合式P2P体系（Hybrid P2P architecture）中最杰出的代表，向世界传达P2P思想精髓，展现其巨大的潜力。2000年3月第一个无结构的P2P网络Gnutella诞生于NullSoft公司，揭开无结构对等网络应用的序幕。与前两个系统主要用于交换文件的应用目的不同，一“自由、安全与匿名”著称的无结构网络-Freenet问世了，其目的是共享Internet上

7、的计算机资源。实际上，它是一个不受限制、不受审查得信息发布与获取平台。还有kaZaA、eDonkey等系统。2000年，著名出版人OReilly组治疗一次意义重大的P2P峰会。2000年8月Intel公司宣布成立P2P工作组，IBM,HP等公司纷纷加入其中。2002年Intel公司发布了基于.NET基础架构的P2P Accelerator Kit （P2P加速工具包）和P2P安全API软件包，从而使人们能在微软环境下迅速地建立P2P安全Web应用。IBM与HP利用P2P技术共同推出了开放存储系统，使用户可以方便地从用户硬盘向服务器上复制数据。HP公司还基于P2P技术的对等网网络打印机。第二阶段

8、（2001-2003）：无结构的对等网络此阶段结构化的P2P体系的对等网络出现，其典型结构有：Chord、CAN、TapeStry,CFS、OceanStore、PAST等。2004年Ray Ozzie创立了Groove公司，开发了Groove Virtual Office(虚拟办公室)，其目标是利用P2P技术营造一个Internet协同办公平台。2002年5月Merkur 继承eDonkey的主要功能，开发了eMule系统，获得了比eDonkey系统更好的性能。2002年10月，新一代混合式P2P网络Bit Torrent(BT)推出，它基于文件的分散式服务器，将共享同一个文件的用户组成一个

9、独立的子网。2003年，商业上诞生了一颗璀璨的新星-Skype公司，它是全球第一家基于P2P技术的及时通信公司。它采用P2P技术为用户提供免费或廉价的语音通话服务，使用端到端的加密技术保证通信的安全可靠。微软公司开发了windows XP P2P 软件开发包，使用户能在XP上编写P2P应用程序。 第三阶段（2004-2006）：结构化的对等网络2004年，在IPDPS会议上基于CCC拓扑的Cycloid常数度P2P模型被提出，它兼有常数度、超立方体、环形等多种属性，可看成是对此前诸多结构化P2P模型的一个总结。从Cycloid的提出可以看出，P2P网络的主要问题、核心机制、整体架构已形成，人们

10、对这些重大问题的看法已达成共识，下一步的工作应该主要放在更具体、更高效、更实用的方面。例如将各种不同P2P系统，像web应用那样整合起来，甚至将P2P与Web整合起来。1.3 对等网络特征 自由、平等与互联是对等网络的主要特征。 自由节点自主决定自己的行为。 平等节点无主次之分。 互联节点可依据某种关系与其它节点建立逻辑连接，从而构成应用层覆盖网络。对等网络区别于其它系统的本质特征具体体现如下网络拓扑结构严格 该网络在网络应用层构建了一个有严格拓扑结构的覆盖网。该结构对对等网络功能的实现具有基础意义。常见的结构有：星型结构、随机图结构、双层结构、带玄环结构、超立方体结构、多维空间结构、蝴蝶结构

11、及CCC结构等。节点和数据对象位置确定 通过基于一致散列函数提供物理网上的节点与数据到覆盖网上的节点与数据映射，并在覆盖网上实现节点与数据对象的某种关联，这对结构化的对等网络来说，它能保证准确定位到节点与数据上。高效路由 任意两个节点间的定位所需的覆盖网络的路由跳数的典型值为TTL（对无结构网络）或LogN（结构化网络），其中TTL为跳数限制，N为覆盖网络中节点的个数。注意：覆盖网与物理网的互联拓扑结构的不一致，实际IP路由跳数会高于覆盖网路由跳数，但仍可控制在LogN的常数倍范围内。负载均衡 由于采用一致散列函数，所有的节点都大致均匀地分布在网络结构上，所有的数据都大致均匀地分布在已存在的节

12、点上。容错与动态自适应 采用冗余和周期性检测等方法，处理覆盖网上节点的增删与这些节点上存放数据的调整，数据对象的增删。行为的自由与匿名性 因采用一致散列函数，它将用户信息与数据对象信息映射到一个表面上看起来没有任何意义数值标识(ID)，这个标识惟一代表了用户和数据，由于安全散列函数的单向性和抗冲突性，不可能从此ID破解出它所代表的信息，P2P网络上用户是匿名的。1.4 对等网络优点网络工作效率高 C/S模式是基于集中控制的，存在一个网络工作效率的中心节点。P2P模式采用非集中处理结构，不存在一个网络工作效率的中心节点。它在网络应用层构建了一个有（严格）拓扑结构的覆盖网络。采用一致性散列函数（C

13、onsistant hashing）将网络节点和数据对象高效、均匀地映射到覆盖网络中，使得它有很高的路由效率（查找时间约为logN）。充分利用网络带宽 C/S模式是基于集中控制的，网络带宽受服务器性能和客户端的数量限制。P2P模式中任意对等节点间平等地互联、自主的交换信息中不受其它节点控制，数据传输速率只取决于网络带宽，因此，它能充分利用网络带宽。发挥每个网络节点的潜力 C/S模式中几乎所有的计算任务都在核心节点服务器上执行。P2P模式中将网络的核心从服务器转变为每一个网络节点，数据分散地存储在所有的节点上，计算任务由各个结点分布、协同地完成，每个节点都是网络的主体。 高可扩展性 C/S模式当

14、网络结点总数增加时，服务器负载也会随之线性地增加，其服务性能也会随之降低。P2P模式中当网络结点总数增加时，随之增加的通信量被更多的节点所分担，每个节点承担的负载并不会增大太多，也不需要增加额外设备且P2P网络路由跳数的增量非常少。容错性强 由于网络的动态变化，网络上节点的动态增删与数据对象的动态增删会使网络节点的状态变的陈旧，与实际网络应有的状态不一致，进而影响网络工作效率。采用冗余和周期性检测等方法，处理这种情况。1.5 对等网络的应用文件共享系统名称功能NapsterBit Torrent GnutellaFast Track/KaZaAeDonkey/eMuleFreenetMaze

15、多媒体传输系统名称功能Skype PeerCast AnySeeMercoraPPLive、TvAnts、CCIPTV、QQ实时通信系统名称功能QQPoPo MSN MessengerICQJabberGoogle Talk协同工作系统名称功能Groove分布式数据存取系统名称功能CFSPASTOceanStoreGranary分布式计算系统名称功能GPUSETIHomeEntropiaDP2P搜索引擎系统名称功能PandangoPASTOceanStoreGranary其它应用系统名称功能TinyP2PHamachi 迅雷基于P2P技术的多源下载工具，主要作为Web插件集成到Web浏览器中。

16、JXTASun公司提供的一个开放、通用互操作的P2P开发平台BayeuxUC berkely 开发的P2P多播应用SCRIBEMicrosoft Research开发的通用、可扩展的组通信和事件发布系统，提供应用层多播和任意播SQUIRRELMicrosoft Research开发的分布式协同Web缓存，似的用户Web浏览器能共享缓存。二、 P2P网络的核心工作机制覆盖网拓扑结构 适当拓扑结构有利于P2P应用可靠、稳定、有效地工作。 分布式散列表 它是P2P网络的一个核心设施，完成节点和数据对象在覆盖网中的位置映射，还能提供匿名性功能。 路由和定位 定位是确定节点和数据对象位置的过程。路由是实

17、现定位的基本步骤，其作用是将信息送到离目的地更近的节点。路由与定位的方式取决于覆盖网拓扑结构和路由表结构。路由与定位的方法和计算复杂度混合结构： 一次请求和响应法计算复杂度O（1）；无结构：泛洪法、扩展环、随机法、超节点路由和导向路由法，计算复杂度限制在TTL之内；结构化：分布式局部性的贪心路由算法算法计算复杂度O（logN）；查询和搜索 查询是指根据制定的内容来定位，内容可以是节点名或数据对象名。查询与定位同义。搜索是指模糊查询，即根据设定的内容，如指定的一个或几个关键字，定位与这些内容相关的一系列结果。查询和搜索的方法无结构对等网络的路由和定位方法： 随机走法、导向搜索、基于相似内容组的搜

18、索。结构对等网络的路由和定位方法：关键码搜索（散列法）和语义搜索分。动态结点算法 如何处理节点的加入、离开和失效方法，使网络能够有效地工作。混合结构的动态节点算法： 有服务器集中处理节点的动态性，一次请求和响应法，计算复杂度O（1）；无结构对等网络的动态节点方法： PING-PON法、KaZaA法；结构对等网络的路由和定位方法：Chord法、Pastry法和CAN法。容错性 对失效节点的容错性，也称为“自适应”。常用的方法是冗余法和周期性检查。三、对等网络工作原理3.1 混合结构对等网络工作原理 我们以典型的Napster网络为例，说明这种结构网络的工作原理。混合结构对等网络Napster结构

19、由两部分组成：Napster网站Napster用户。Napster网站是一个服务器群，每个服务器保存一部分用户的共享文件索引信息，所有的服务器以全连接的形式互联起来，形成一个“更多文件索引信息”服务器，以整体向网站外Napster用户提供统一的访问接口。对每一个用户而言，他访问的是同一个服务器。 Napster用户将他愿意与其他用户共享的文件信息发送给一台服务器，该服务器记录这些信息及该用户的位置，并将它们做成一条索引，添加到原有的索引表中。 当用户要查询一个文件时，首先将“查询”消息发送给与其相连的的服务器，该服务器收到这个“查询”后，与其它服务器协作处理这个查询，处理完毕后将“回复”消息返

20、回给那个用户，这条消息中包含一个表，列有所查到的所有匹配的索引。用户收到“回复”消息后，在表单中选择想要的文件。然后，根据所选文件索引中对应的位置，直接到那个用户主机上下载文件。Napster网站一方面维护用户的共享文件索引，另一方面监控系统中每个用户的状态，如跟踪记录用户的连接带宽、接入的时间及掉线情况等，这些信息对服务器保证文件索引的时效性和用户选择哪些存放信息的用户建立连接十分重要。3.2 无结构对等网络工作原理我们以典型的Gnutella网络为例，说明这种结构网络的工作原理。 与Napster结构所不同，Gnutella所采用的对等网络结构中只有一种节点，称为对等实体（peer），它既

21、是服务器，又是用户。即它既能向其它Peer点发送查询请求并获得查询结果，又能接受其它Peer发的查询请求并将查询结果或返回给请求者或将此请求路由给其它Peer。另外，每个Peer还负责监控网络局部的通信状态，相互协作以保证整个网络的完整性与一致性。 这种结构的网络连接是由每个Peer所保存的“邻居节点”信息确定的，有一个邻居节点就对应有一条边。 网络上用户通过一个Gnutella中的“众所周之”的节点（自举节点，入口节点）接入Gnutella网络中的。 该协议设有三种消息：成员组消息（PING,PONG），查询消息（QUERY,QUERY RESPONSE）以及文件传输消息（GET,PUSH）

22、。 该协议通过有限泛洪方式来维持节点与数据的时效性的。3.3结构化对等网络工作原理我们以典型的Chord网络为例，说明这种结构网络的工作原理。Chord 是最简单、最精确的环形P2P模型，它是基于带弦环拓扑结构的分布式散列表(DHT)构建于的P2P 网络。若将Chord 看成是一个分布式散列表，它的功能是将节点和数据对象映射到覆盖网中。在一个有N个节点的网络中，Chord 基于安全的一致性散列函数来分配节点ID和对象ID,每个Chord 节点保存O(logN)个其他节点的信息，查找数据对象需要的覆盖网路由跳数也是O(logN)。当有节点加入或离开网络时，为了维持网络结构、保持自适应性所需要的消

23、息数也在O(log2N) 复杂性上。当有新节点P加入时，依P节点的标识符的值在环上选择适当的位置，将它后继节点上存储的数据对象标识移至P节点上。 当有旧的节点Q离开时，原来由Q节点存储的数据对象标识，全部移至Q的后继节点上。它具有几乎最优的路由效率、确定性的对象查询、负载均衡高及扩展性以及良好的容错性与自适应。若将Chord看成是一个P2P网络，那么它是一个基于带弦拓扑结构的分布式系统，提供数据对象的存储、查询、复制、缓存以及在它之上还可以架构更高层次的分布式数据存取系统CFS( cooperative file system) 3.3.1 Chord 环结构的构建 Step1 生成节点和关键

24、字标识符 利用安全散列函数（如SHA-1）对给定的每个网络节点和每个数据对象分配唯一的ID。Node_IDH（node属性），Node属性节点IP地址、端口号、公钥、随机数或他们的组合。Object_IDH(object 属性），Object属性数据对象的名称、内容、长度发布者或者他们的组合 H是散列函数，其值长度m（位数）应足够大(一般为160位，这就保证了所产生的ID几乎不可能出现重复，所以认为标识是唯一的。Step2 形成节点环 按节点标识符值从小到大排列，以顺时针方向将各节点标识符放置一个环上（每个节点占据2m-1个位置中的某一个）。每个节点有其后继，节点标识符n的后继是环上紧随n(其

25、值大于n的）的第一个节点，记为n.successor。Step 3. 将数据对象的标识符放到环中适当节点（位置）上将数据对象k以顺时针方向放入环中节点标识符值大于等于该数据对象标识符的那个节点上（注意，该节点的标识符值可能等于数据对象标识符的值），该节点又被称为数据对象k的后继，记为successor(k),successor(k) n，数据对象k的后继就是存储数据对象k的节点。例 设有一散列函数H的hash值二进制的位数为m=3，当前有3个节点的节点标识符分别为0、1和3，有3个数据的数据对象标识符分别为1、2和6。试利用Chord构造算法构造Chord环结构？解 采用Chord构造算法构造

26、Chord环结构如图所示： 按节点标识符值从小到大排列，以顺时针方向将各节点标识符放置一个环上（每个节点占据2m-1个位置中的某一个），本题将0,1,3放入相应的位置上去。将数据对象k以顺时针方向放入环中节点标识符值大于等于该数据对象标识符的那个节点上。对于k=1的数据对象，因k只能存入节点标识符值大于等于k的节点上，由于节点标识符值为1的节点存在，故将k=1数据对象存入节点1上。对于k=2的数据对象，因k只能存入节点标识符值大于等于k的节点上，由于节点标识符值为2的节点不存在，故将只能将k=2数据对象存入大于节点2以后的第一个实际存在节点上，即只能存入第3号节点上。对于k=6的数据对象，由于

27、节点标识符值为6的节点不存在，故将只能将k=6数据对象存入大于节点6以后的第一个实际存在的节点上，即第0号节点上。3.3.2 Chord环结构的动态演变Step1. 当有新节点P加入时，依P节点的标识符的值在环上选择适当的位置，再将它后继节点上存储的数据对象标识移至P节点上。Step2. 当有旧的节点Q离开时，将原来由Q节点存储的数据对象标识，全部移至Q的后继节点上。3.3.3 基于Chord环结构的查询考虑由N个节点组成的Chord环，有两种查询方法。方法一：设每个节点都知道整个网络中的节点的关键字的信息，即每个节点都维护O(N)个大小的路由表。若给定一个关键字，查询的时间复杂度为O(1)。

28、缺点是当网络规模很大时，维护节点上路由表的代价太大而变得不能实用。方法二：若环中每个节点只知道其后继节点的信息，即每个后继只维护一个后继节点的路由表，若给定一个关键字，查询将沿着其后继节点遍历环，查询的时间复杂度为O(N)，该方法的优点是可维护性好，缺点是查询速度慢。这两种方法在网络规模很大时效率低，为此人们又综合这两种方法的优点，提出了Chord查询方法。设环上每个节点维护少量的路由表项，路由表呈现两个特点：它只知道距离本节点近的一些节点信息；其二是它不能直接找到数据对象k的后继（存放对象k的节点）。对给定的查找数据对象k，求数据对象k的后继节点，即存放数据对象k的节点。查找处理思想 针对节

29、点n提出的查询数据对象k的请求，通过将k与节点上路由表中每个指针的间隔区间相比教(匹配)，在路由表中找到一个比自己(节点n)离数据对象k近的节点j，然后，再在节点j上的路由表中找到一个比自己离数据对象k更近的节点i，如此递归下去，最终结果是在k的后继节点上找到k并将这个节点标识符返回给提出查询请求的节点，或者是查询无结果。 如何构造路由表才能支持数据对象的查询呢？ 构造Chord环中节点的路由表设某节点在环上节点标识符为n, m为节点标识符和数据对象标识符的位数（采用二进制），每个节点的路由表（指针表）的容量为m。每一表项或指针项共有5列，其表结构如下： 第一列 表示节点标识符n上路由表中第k

30、个指针，它指向环中一个节点标识值为(n+2k1) mod 2 m （1km ）的节点，它是以顺时针方向距节点标识符n的距离至少为2k1的第一个节点，记为n.fingerk.start（或n.fingerk.node ,或n.successor）；第二列 表示节点标识符n上路由表中第k个指针所指向的节点到第k+1指针所指向的节点所构成的节点标识符区间。该区域主要用于检查数据对象标识是否存放在此节点区域中的；第三列 表示节点标识符n上路由表中第k个指针所指向的节点的后继节点,即 n.fingerk.start的第一个节点；第四列 表示节点标识符n上路由表中第k个指针所指向的节点的实际存在的后继节点

31、，记为n.fingerk.node，即第k个指针所指向的节点的第一个实际存在的后继节点；第五列 表示节点标识符n路由表中第k个指针所指向的节点标识符的前驱节点,predecessor（n.fingerk.node）。例：设Chord环的Hash函数位数=3，若有三个节点，经过Hash处理后节点标识符ID分别为0、1、2，试构造这三个实际存在节点的路由表（徐P.133，图5-4）。解：因m=3,故Chord环上最多8个节点。依题意，目前环上只有3的节点。按照Chord环节点路由表计算方法第一列 表示节点标识符n上路由表中第k个指针指向环中一个节点标识值为(n+2k1) mod 2 m （1km

32、）的节点，它是以顺时针方向距节点标识符n的距离至少为2k1的第一个节点，记为n.fingerk.start（或n.fingerk.node ,或n.successor）；第二列 表示节点标识符n上路由表中第k个指针所指向的节点到第k+1指针所指向的节点所构成的节点标识符区间；第三列 表示节点标识符n上路由表中第k个指针所指向的节点的后继节点,即 n.fingerk.start的第一个节点；第四列 表示节点标识符n上路由表中第k个指针所指向的节点的实际存在的后继节点，记为n.fingerk.node，即第k个指针所指向的节点的第一个实际存在的后继节点；第五列 表示节点标识符n路由表中第k个指针所

33、指向的节点标识符的前驱节点。对节点0，n=0： k=1 fingerk.start=(n+2k1) mod 2 m=(0+211) mod 23 =1; Interval= fingerk.start，fingerk+1.start) = finger1.start，finger2.start) =(0+211) mod 23, (0+221) mod 23)=1,2) Node=(n.fingerk.start)=(0.finger1.start)=1 Successor=(n.fingerk.node)= Successor ( 0.finger1.node)=1 Predecessor(

34、n .fingerk.node)= Predecessor (0. .finger1.node)=0k=2 fingerk.start=(n+2k1) mod 2 m=(0+221) mod 23 =2; Interval= fingerk.start，fingerk+1.start) = finger2.start，finger3.start) =(0+221) mod 23, (0+231) mod 23)=2,4) Node=(n.fingerk.start)=(0.finger2.start)=2 Successor=(n.fingerk.node)= Successor ( 0.fi

35、nger2.node)=3 Predecessor(n .fingerk.node)= Predecessor (0. .finger2.node)=1k=3 fingerk.start=(n+2k1) mod 2 m=(0+231) mod 23 =4; Interval= fingerk.start，fingerk+1.start) = finger3.start，finger4.start) =(0+231) mod 23, (0+241) mod 23)=4,0) Node=(n.fingerk.start)=(0.finger3.start)=5 Successor=(n.finge

36、rk.node)= Successor ( 0.finger3.node)=0 Predecessor(n .fingerk.node)= Predecessor (0. .finger3.node)=3Startintervalsuccessor 11,21 22,4344,00对节点1，n=1： k=1 fingerk.start=(n+2k1) mod 2 m=(1+211) mod 23 =2; Interval= fingerk.start，fingerk+1.start) = finger1.start，finger2.start) =(1+211) mod 23, (1+221)

37、 mod 23)=2,3) Node=(n.fingerk.start)=(1.finger1.start)=2 Successor=(n.fingerk.node)= Successor ( 1.finger1.node)=3 Predecessor(n .fingerk.node)= Predecessor (1.finger1.node)=1k=2 fingerk.start=(n+2k1) mod 2 m=(2+221) mod 23 =4; Interval= fingerk.start，fingerk+1.start) = finger2.start，finger3.start)

38、=(1+221) mod 23, (1+231) mod 23)=3,5) Node=(n.fingerk.start)=(1.finger2.start)=4 Successor=(n.fingerk.node)= Successor ( 1.finger2.node)=3 Predecessor(n .fingerk.node)= Predecessor (1.finger2.node)=1k=3 fingerk.start=(n+2k1) mod 2 m=(1+231) mod 23 =5; Interval= fingerk.start，fingerk+1.start) = finge

39、r3.start，finger4.start) =(1+231) mod 23, (1+241) mod 23)=5,1) Node=(n.fingerk.start)=(1.finger3.start)=6 Successor=(n.fingerk.node)= Successor ( 1.finger3.node)=0 Predecessor(n .fingerk.node)= Predecessor (1.finger3.node)=4Startintervalsuccessor 22,3)3 33,5)355, 1)0对节点3，n=3：Startintervalsuccessor 44

40、,5)0 55,7)077, 3)0关键字的查询流程Step1若某节点提出查询请求为k, 则该节点逐项查找本节点的路由表，寻找到距关键标识符k的后继节点最近的节点j (即k的后继节点的前趋 )。这项工作主要是查看关键字k是否可能落入位于路由表中某个表项指针所的节点标识符区间中。Step2 如果寻找到那个节点j是k的后继节点的前趋，则节点j逐项在本节点的路由表继续寻找关键字k的后继节点。Step3 循环，直到新节点发现关键字k的后继节点就是新节点本身,然后将新节点本身标号返回给提出查询请求的节点。 查找处理流程： 输入某节点提出查询请求，记为k； 在该节点上逐项查找本节点的路由表，具体通过将k与

41、节点上路由表中每个指针的间隔区间相比较(匹配)，寻找到离关键标识符k的后继节点最近的节点； 判断节点是否是k的后继节点的前趋，若是转 ，否则转； 判断k的后继节点上是否存有数据对象k，若有，置查找成功标志，向查询请求提出节点发送新节点标识符。否则，置查找失败标志，向查询请求提出节点发送失败标志； 结束算法流程：查询请求节点n寻找id的后继（id所存放的位置）find_successor(id) / 寻找对象id的后继节点 n = find_ predecessor(id) ; / n表示远程节点return n.successor ;find_ predecessor(id) /寻找环上最终可

42、以到达对象id位置的前驱节点 n = n; While ( id ( n, n.successor) )n = n.closet_ preceding_ finger(id);return n; closet_ preceding _finger(id) / 在节点自己的路由表中，从前往后找到在id并且与id最近的节点 for i = m down to 1if ( fingeri.node (n., id) ) return fingeri.node;return n; 例假定Chord环的Hash函数位数=3。有三个节点，经过Hash处理后节点标识符ID分别为0、1、2。有三个关键词，经过

43、Hash处理后节点标识符ID分别为1、2和6，它们分别被映射到环上的1,2,0节点上。当前环上这三个实际存在节点的路由表如图所示。求解：（1）若在节点3上，查询k=1的关键字，试给出查询过程？（2）若在节点3上，查询k=4的关键字，试给出查询过程？解：（1） k=1时，在节点3上逐项查找路由指针。由于数据对象k（=1）只能存入节点标识符值大于等于1节点，故从节点3的路由表中的第一个表项开始，判断K=1n.finger(i).Int, 如是，跳到3.finger(i).succ表示的节点上继续查找，即跳到节点0上继续查找。判断节点0上的数据对象是否等k（=1）,不等，则又从节点0的路由表中的第一个表项开始，判断K=10.finger(i).Int, 如是，跳到0.finger(i).succ表示的节点上继续查找，即跳到节点1上继续查找。判断节点1上的数据对象是否等k（=1）,相等，则将查找到的信息传给节点3.（2）k=4时，在节点3上逐项查找路由指针。由于数据对象k（=1）只能存入节点标识符值大于等于节点，故从节点3的路由表中的第一个表项开始，判断K=1n.finger(i).Int, 如是，跳到3.finger(i).succ表示的节点上继续查找，即跳到节点0上继续查找。判断节点0上的数据对象是否等k（=4）,不