（计算机应用技术专业论文）对等网络中的资源定位方法研究与应用.pdf

摘要 本文首先针对p 2 p 网络中的核心问题一资源定位算法，做了深 入的分析和探讨。针对不同类型的p 2 p 网络，本文分析，比较了三 种最典型的对等网资源定位算法一集中式对等网络算法、非结构化 对等网和结构化对等刚算法，并结合g u n t e l l a 、n a p s t e r 、c h o r d 和 c a n 等实例对这三种算法的实际应用效果进行了比较分析。结果表明 洪泛算法实现简单、收敛快，但是不具有很好的扩展性，并容易导 致广播风暴；目录算法具有简单的协议和较高的查找效率，但是它 所采用的目录服务器是网络中的单一故障点，同时也成为了系统进 一步扩展的瓶颈；结构化是p 2 p 研究中的热点，它具有天然的散列 性和动态性，并且具有快速查找的性能，但是尚未实现实际的应用。 本文在结构化c h o r d 模型基础上，作者提出了一个t l c h o r d 混 合结构算法。该算法具有以下两个方面的改进： 首先t l c h o r d 算法充分考虑到了非结构网络区分节点性能的特 点，将c h o r d 环上的节点根据实际地理位置映射到不同的自治域内， 并且在自治域中选出性能较高的节点作为超级节点。超级节点可以 缓存更多有价值的资源索引，并且可以在自治域之间转发请求，扩 大查询范围，帮助节点进行资源定位。缩短路由长度。 其次t l c h o r d 依据空间局部性对c h o r d 选择指针的方法进行改 进，在保证c h o r d 原有的路由正确性的前提下，选择与查询节点在 同一个自治域中的节点作为指针。由于节点所属的自治域基本不发 生变化，因此增加了指针表的稳定性，减小了系统和节点的开销， 避免了由于经过不同自治域而造成的高延迟，从而缩短了搜索的逐 跳延迟。 本文最后在p 2 p s i m 平台上对t h c h o r d 进行了模拟试验。模拟实 验结果表明，t l c h o r d 与c h o r d 相比，缩小了搜索延迟，缩短了搜索 路径长度，从而提高了搜索效率。 关键词：对等网络，资源定位，结构化网络，t l c h o r d a bs t r a c t t h i s p a p e r d e a l sw i t ht h ec o r e p r o b l e m i nt h ep 2 p n e t w o r k s - - r e s o u r c e l o c a t i o n a c c o r d i n g t od i f f e r e n t t y p e s o f p 2 p n e t w o r k s ，t h i sp a p e rd i s c u s st h r e e k i n d so fm o s tp o p u l a r p e e r r e s o u r c el o c a t i o na l g o r i t h m - - f l o o d i n g ，i n d e xa n dd y n a m i ch a s h i n g f u r t h e r m o r e ，i tm a k e sac l o s ec o m p a r i s o na n da n a l y z e so ft h e s e a l g o r i t h m sb yc a s eb a s e ds t u d i e so fg n u t t e l l a ，n a p s t e r , c h o r d ，c a na n d e t c t h ep a p e rp r o p o s ea np 2 ps t r u c t r eo ft l c h o r d ，w h i c hi sb a s e d o nc h o r d t h et l c h o r dm a k e si m p r o v e m e n ti nt h e f o l l o w i n g t w o a s p e c t s ： f i r s t l y , t l c h o r dc o n s i d e r st h ef e a t u r eo fe a c hn o d ei nu n s t r u c t u r e d n e t w o r ka n dm a k e sc h o r d sn o d e sm a pi n t od i f f e r e n ta u t o n o m o u ss y s t e m a c c o r d i n gt or e a l l o c a t i o no fe a c hn o d e ，a n ds e l e c t ss u p e rn o d e sf r o m h i g hp e r f o r m a n c e n o d e si nd i f f e r e n ta u t o n o m o u ss y s t e m s u p e rn o d e s m a ys t o r ei n d e xo fv a l u a b l er e s o u r c e si nb u f f e r , a n dm a yt r a n s m i t r e q u e s tf o r ma na u t o m o u ss y s t e mt oa n o t h e r , a n dm a ye x t e n dt h es c o p e o fi n q u i r y ，a n dm a ym a k en o d e sl o c a t er e s o u r c e se f f e c t i v e l ya n dr e d u c e r o u t e sl e n g t h 。 s e c o n d l y , t l c h o r di m p r o v e st h ef i n g e rs e l e c t i o na c c o r d i n gt ot h e s p a t i a ll o c a l i t y , a n de a c hn o d es e l e c t st h eo n ew h i c hi si nt h es a m e a u t o n o m ys y s t e m ( a s ) a si t sf i n g e ri nt h ec o n d i t i o no fk e e p i n gr o u t i n g c o r r e c t n e s s a st h ea sh a ss e l d o mb e e nc h a n g e d ，s oi te n h a n c e st h e s t a b i l i t yo ft h ef i n g e rl i s ta n dt h u sr e d u c e ss y s t e mc o s t s ，a n da v o i d sh i g h d e l a ya n dr e d u c e ss e a r c h sd e l a y i nt h ee n do ft h e p a p e r , t l c h o r d i ss i m u l a t e d b y p 2 p s i m s i m u l a t i o nr e s u l t si n d i c a t et h a tt l c h o r dh a sal o w e rl a t e n c y a n ds h o r t e rs e a r c hp a t ht h a nc h o r ds oa st oi m p r o v es e a r c he f f i c i e n c e k e yw o r d s ：p e e r - t o - p e e rn e t w o r k ，r e s o u r c el o c a t i o n ，s t r u c t u r e d n e t w o r k ，t l c h o r d i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另, j j h 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：垄垦主亟日期：2 竺丛年月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 碰j 学位论r第一章缔论 11 研究背景 第一章绪论 计算机对等网络( p e e r t o p e e r ，简称p 2 p ) ”技术是e l 前流行于计算机网 络技术研究领域的一个热点，但p 2 p 并不是一个新的概念。互连网在早期阶段， 即a r p a n 盯阶段，采用的就是p 2 p 模式。但是以前因为计算机的处理能力、存 储空l 盲l 以及网络带宽等方面的限制，采用的是客户机服务器( c s ) 模式。在 这种模式下，客户端主机只能处于被动接受服务器提供服务的状态，而不具有 主动提供服务的能力，网络的数据处理能力将受到中央服务器的性能以及客户 机和服务器之问带宽性能的限制，当大量用户同时访问某一应用服务器时，网 络带宽大量占用，应用服务器负载过重，网络带宽和应用服务器的性能问题将 成为网络传输能力的瓶颈。c s 的工作方式如图卜1 所示。而p 2 p 模式由于其 本身所具有的分布式控制与协同工作的特点。p 2 p 的工作方式如图卜2 所示。 使得学术界和企业界开始重新关注p 2 p 技术。 里磐发篁州；息 勐j 鼬 赢 b【= 图1 1c l s 模式的工作方式图卜2p 2 p 模式的工作方式 尽管对p 2 p 存在很多表述，比方说惠普p a l oa 1 t o 实验室提出p 2 p 是指以 无中心的方式利用分布的资源完成关键任务的系统”3 。而i n t e lp 2 p 工作组给 出的定义是通过直接交换完成计算机资源和服务共享的系统9 1 。但是我们可以 看到p 2 p 网络的核心特征就是结点之问的分布性、对等性和自治性。 近几年来对p 2 p 的研究迅速升温，各方面的应用层出不穷。特别是它提供 无穷的存储空间咀及不受限制的传输容量，这是传统中央服务器所无可企及的。 p 2 p 是一种分布式技术，不同于c 1 i e n t s e r v e r 、b r o w s e f s e r v e r 等传统模式， 它抛开了应用服务器的束缚，使得网络中的节点以一种对等的方式共享这些节 点的存储空间、处理器计算能力、网络带宽等资源。一方面节点阃可以直接进 行交互，不再需要服务器来作为媒介来进行中转，从而使交流更直接，效率更 高：另一方面不再依赖中央服务器，从而解决了因服务器能力不足而引起的性能 硕l ：学化论文第一章绪论 瓶颈i 口j 题，增强了系统的可伸缩性，同时也避免了因中央服务器的失败而导致 整个系统无法工作的可能性，使得系统的可靠性更强。从c s 模式到p 2 p 模式 的发展，i n t e r n e t 上的共享行为被提升到了一个更高的层次。 1 2p 2 p 的现状 1 9 9 9 年1 月，j 下在读大学一年级的s h a w nf a n n i n g 开发了一个叫n a p s t e r 的软件。这个软件能让乐迷之间方便地共享自己硬盘上的m p 3 音乐。这个软件 通过索引服务器找到需要的m p 3 文件后，它会直接连接拥有该文件的其他用户 主机并下载。这避免了原来集中下载服务器的存储空间和带宽瓶颈。这个新的 应用受到用户的极大欢迎，最高峰的时候注册用户数曾达到8 0 0 0 力。以至于同 年1 2 月美国唱片业协会( r i 从) 代表环球音乐、索尼音乐、华纳音乐、百代唱片、 b m g 等七大唱片公司以违反版权保护法为由把n a p s t e r 公司告上法庭。他们称 n a p s t e r 向网民提供m p 3 文件共享软件侵犯了音乐版权，要求法院关闭该公司 并赔偿损失1 亿美元。虽然经过漫长的法律诉讼，n a p s t e r 最终不得不从索引 服务器上删除所有受版权保护的条目。但是p 2 p 的颠覆性力量第一次引起了全 世界的瞩目。就在n a p s t e r 风生水起，却横遭版权诉讼的同时。2 0 0 0 年3 月a o l ( 美国在线) 旗下的n u l l s o f t 在其网站上发布了一款名叫6 n u t e l l a m l 的软件。 这个新软件和n a p s t e r 有着类似的功能，但是不再需要任何中心服务器作资源 索引。可以说，这是第一款完全意义上的p 2 p 软件，推出以后立即受到广泛的 关注。但是a o l 当时正在试图与时代华纳合并，而时代华纳j 下是参与对n a p s t e r 的诉讼人之一。a o l 高层马上就把软件从网站上取了下来，但是这已经太晚了。 很多人喜欢上了它，而黑客们更对它进行逆向工程，并且把源代码放到了开源 社区。这样6 n u t e l l a 变成了一套丌放协议，各种各样的兼容软件由此发展。从 s w a p p e r 到s h a r e a z a ；从l i m e w i r e 到m o r p h e u s ，甚至是r i s c o s 下也有人开发 了c o c o g n u t ，u n i x 下有g t k g n u t e l l a ，苹果的m a co s 下也有a c q u i s i t i o n x 。 g n u t e ll a 家族成为了p 2 p 世界的一颗闪亮新星。 从此以后，p 2 p 软件似乎一发不可收拾。现在大家熟悉的b it t o r r e n t 旧1 ， e m u l e ，f a s t t r a c k ，f r e e n e t 1 们等等都是p 2 p 在文件共享领域的良好范例。而 除了文件共享以外，p 2 p 也有广阔的应用天地。比如g r o o v e 就是一个对等协作 平台。而s e t i h o m e 则是充分利用分布在网络边缘的计算资源的成功范例。 1 3p 2 p 应用前景 根据对等网络工作委员会( p e e r t o p e e rw o r k i n g6 r o u pc o m m i t t e e ) n 幻 2 颀i j 学位论文第一章绪论 的定义，它可以在商业上有以下几种主要应用： 1 协同工作( c o l l a b o r a t i o n ) 对等网络可以让一个工作小组建立和管理同步及非同步的协同工作，并提 高他们的效率。利用对等网络技术，可以增进成员i b j 的合作效率和促进生产力， 减少在多个项目问再评估和协调的时间，每个成员都可以访问最新的数据、充 分分享彼此的资源。 2 边缘服务( e d g es e r v i c e ) 对等网络技术可以帮助跨越不同地域的大型企业在其内部更有效的提供并 传递信息，所谓边缘服务就是指利用大型企业内部存取信息的地域性，让信息 存储在更靠近最终用户的节点上，及网络的边缘。例如一家大型的跨国公司希 望通过i n t e r n e t 向其全球的员工提供统一的培训课程。如果培训课程的录像存 储在中央服务器很可能会造成网络j f j 塞；如果在每个分部所在地增加服务器存 储培训课程录像又会增加成本。利用对等网络，只需将培训课程传至各地的一 个员工的计算机上，其他员工就可以通过对等网络的方式得到培训录像。 3 分布式计算( d i s t r i b u t e dc o m p u t i n g ) 对等网络运算可以帮助企业拥有强大的运算能力。通过网络联结在一起的 包括网络计算机、个人计算机在内的空闲c p u 时间及存储空间皆可充分利用。 据在2 0 0 1 年初的估计n 引，全球通过i n t e r n e t 相联的个人计算机可以提供至少 1 0 0 亿m h z 的c p u 处理能力和1 0 0 0 0t b 的存储空间，可以预计，这些数据已经 远远小于目前的实际数字。利用对等网络技术来充分整合这些闲置的计算机资 源，不但可以为公司节省大项目的运算成本，也不需只是为此大项目而额外添 置机器设备，节省在硬件上的支出。以i n t e l 公司为例，该公司美国总部的员 工就曾利用时差的影响，在i n t e l 公司设在以色列的分部的工程师们下班的时 间，通过基于对等网络的分布式处理程序n e t b a t c h ，利用他们以色列同行空闲 的计算机在八周内完成一个芯片的设计。没有对等网络，这个项目至少需要两 倍的时间才能完成。i n t e l 估计利用对等网路节省的包括购买设备和缩短项目 周期的费用至少为5 亿美元。 4 智能代理( i n t e l l i g e n ta g e n t ) 智能代理可以运用对等网络技术，动态的在网络上一起进行协同工作，运 行于不同节点计算机( 如不同操作系统或不同的程序语言) 间的代理可以进行 信息的传递和格式转换，代理还可以在对等网络的环境下按事情的优先级来执 行它被安排的工作。 除了上面介绍的这些对等网络常见的应用之外，随着对等网络技术的逐渐 成熟，还产生了一些新的应用。例如可以通过对等网络改变i n t e r n e t 现有的层 硕i j 学位论义第一章绪论 次化的d n s 结构，建立分布式的基于对等网络的域名服务系统；利用新出现的 基于分布式哈希表的对等网络结构，可以建立可靠的网络文件系统；利用对等 网络技术，建立分布式的电子邮件系统，在邮件发送者和接受者之间建立直接 的链接，不必通过邮件服务器；利用对等网络技术进行负载均衡，例如用来缓 解某些热门网络的w e b 服务器上的负载等。 1 4 关键问题 对等网络系统最大的特点就是用户之间直接共享资源，其核心技术就是分 布式资源定位机制，即查询对象存储位置的请求在对等网络中的路由问题，这 也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。 目前对等网络系统的资源定位技术基本上可以分为三类。第一类基于中央 服务器( 或服务器群) ，如n a p s t e r 系统，中央服务器维护系统中所有共享资源 的位置索引，由中央索引服务器提供查询和定位。该技术的优点是高效、易于 实现，但存在单一故障点、可扩展性差等问题。 另外两种技术将共享资源的索引分散在系统中的节点上，根据资源定位机 制是否依赖特定的系统拓扑结构，分为非结构化和结构化定位技术。非结构化 定位技术，如g n u t e l l a n 钔，以洪泛( f l o o d i n g ) 方式将定位请求发送给自己的邻 居节点，直到满足查询或超时，其优点是没有单一故障点，但存在带宽消耗大、 可扩展性差等问题。 结构化定位技术基于分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t n 5 1 ) ，这 种方法利用哈希函数为搜索空间建立索引，将杂乱的信息有序化，然后将信息 按照一定的规律组织，进而抽象出高效的查询算法完成准确查询定位。由于每 个节点都保存一张拥有其他少数节点的索引信息的路由表，所以这种算法也被 称为分布路由算法。分布路由算法摒弃了上述两种定位机制的弊端，是新一代 规模可扩展的路由算法，现在已经有t a p e s t r y n 制，c h o r d n ”、c a n n 刚等较成功的 范例。 分布路由算法的重点主要集中在提高查询效率、负载平衡、网络的扩展性、 降低带宽占用率等方面。由于分布式哈希的路由算法是网络逻辑层上的算法， 在逻辑网络很难考虑节点在物理网络拓扑上的关系和数据之间的逻辑联系，所 以出现了虽然逻辑上高效，而实际效率极低的问题。而且，在分布式哈希表的 搜索机制中，对共享资源也进行哈希，节点根据哈希标识存储相应的资源，忽 略了节点在能力上的差异，造成了负载分配不均衡，影响路由算法的效率。 4 硕l j 学位论史第二章对等例络的资源定位技术 第二章对等网络的资源定位技术 从最初以n a p s t e r 为代表的有着中央目录服务器的对等网络结构，发展到 后来的以g n u t e l l a 为代表的完全分布式的无结构对等网络和提供节点匿名发 布和获取文档的f r e e n e t ，再到以c a n ，c h o r d ，p a s t r y 和t a p e s t r y 等为代表的 基于分和式哈希表的结构化对等网络，对等网络的发展历经了大致三个阶段， 分别采用了不同的资源定位和路由模型。本章将对这三种最重要的对等网络系 统模型及其搜索机制加以介绍。 2 1 集中式对等网络 对等网络首先引起人们的注意是从n a p s t e r 时代开始的，n a p s t e r 虽然不 是严格意义上最早的对等网络，但却是第一个通过i n t e r n e t 获得大规模应用并 取得巨大成功的对等网络系统。n a p s t e r 的用户注册与文件检索过程类似于传 统的c s 模式，区别在于所有共享数据并非存储在服务器上，而是存贮在各个 节点中。网络中的每个客户机存储共享内容，所有的客户机都连接到一个中央 目录服务器( d i r e c t o r ys e r v e r ) ，该服务器维护的信息主要有注册用户的连接 信息表，如i p 地址、连接带宽等信息；描述网络上所有文件的元数据信息，如 文件名，创建时间等；文件列表，记录每个用户提供共享的文件。 当一个客户机要连接到网络时，它与中央服务器联系，并报告自己共享的 文件列表。客户机提出资源定位请求时，将请求发向目录服务器，服务器在它 的索引中查找匹配的信息，并向客户机返回存储了请求文件的用户信息列表。 客户机根据网络流量和延迟等信息选择合适的节点，直接与一个或多个存储了 请求文件的用户建立连接并下载所需文件，而不必再经过中央服务器。n a p s t e r 的资源定位过程如图2 - 1 所示。 硕l ：学位论义 第二章对等州络的资源定位技术 o ( 1 a 脚焱、 囝 坚i 囝 e n t 。4 弩引沁眦 资源定位过程如下： ( 1 ) 用户利用r e q u e s t 消息向服务器发出查找关键字的请求； ( 2 ) 服务器在索引中查找匹配请求的文件，并向用户返回查找结果； ( 3 ) 用户从服务器响应中得知拥有请求文件的节点列表，选择性能最好的节 点并向该节点发送下载文件的请求； ( 4 ) 从性能最好的节点处获取请求文件。 2 2 非结构化对等网络 非结构的对等网络系统采用完全分布式的拓扑结构。非结构对等网络中的 每个节点之间是比较松散的关系，节点的加入和退出仅需要遵循一些简单的规 则。非结构对等网路中的每个节点保存各自共享的文档，由于不再存在中央目 录服务器，每个节点对本地保存的文档进行索引，并转发或应答其他节点的搜 索请求。在非结构的对等网络中，由于缺乏中央目录服务器且文档并不存储在 特定的节点上，所以资源搜索最基本的方式是泛洪( f l o o d i n g ) 或类似泛洪的 盲目搜索。 泛洪算法( f l o o d i n g ) 的思想非常简单。当节点a 需要查找时，它把查询 请求向它知道的所有节点发送。假设节点b 接收到a 发来的查询请求，b 就会 在本地资源中寻找匹配的资源。如果发现，就把结果传回请求送来的方向；如 果没有发现，则把这个请求向b 自己的所有已知节点( 除节点h 外) 转发。节 点b 在转发查询消息后会记录查询的来路，这样当其他节点向b 返回查询结果 后，b 能正确地把结果转回给a 。 所有节点都按此策略工作，查询消息就能在网络上以可能达到的最快速度 扩散。如果把这个p 2 p 网络的节点看作一个图的顶点，有联系的节点之间认为 存在一条弧。这个f l o o d i n g 查询过程类似在这张图上，从节点a 开始，按广度 6 倾i ：学位论义第二章对等叫络的资源定位技术 优先遍历的过程。 如果不考虑网络拥塞的影响，这科策略能够最快地找到资源，并且具有非 常强的容错能力。并且算法简单，是非常理想的方案。但是现实的网络带宽是 有限的，甚至往往是整个网络中最稀缺的资源。当p 2 p 节点到达相当规模以后， 各个节点查询请求的洪水式扩散将会很快耗尽可用带宽。造成p 2 p 网络的瓦解。 实际系统中都对f l o o d i n g 的扩散作了很多抑制。比如为每个查询产生一个 唯一标志，这样节点发现重复的查询消息到来时就可以直接把这些重复请求丢 弃。比如图2 2 中节点b 把查询转发后可能又收到节点c 的转发。有了唯一标 志b 就可以放心地丢弃c 转束的请求。又比如为这些查询请求设置一个转发计 数器。类似于i p 报文中的t t l ( t i m et ol i v e ) ，最初发出查询时设定好一个计 数，其他节点转发一次就把这个计数减l ，当计数为0 时放弃查询。如此一来， 节点查询时就可以把计数从l 开始试查。如果得到需要的结果，就只会产生一 次扩散。如果没有查到，把计数设为2 再查。这次的查询最多只能被扩散两次。 如果仍然没有找到，节点把计数器加1 再查。直到找到目标或者该计数值达到 网络直径。这个措施也能极大地降低系统中的查询扩散流量n 9 。 图2 - 2f l o o d i n g 算法的消息扩散示意图 下面将对无结构对等网络中的典型系统做一介绍。 2 2 1 采用洪泛算法的实例川n u t ei la g n u t e l l a 是非结构对等网络中的典型系统，它被用于各种文件的共享。 g n u t e ll a 的名字是由g n u ( 实际上g n u t e ll a 并没有根据g n ug p l 发布最新的软 件) 和一种花生酱巧克力的名字n u t e l l a 构成。g n u t e l l a 的作者是 j u s t i n f r a n k e l ( n u l l s o f t 公司的创始人) ，2 0 0 0 年3 月1 4 日，n u l l s o f t 在美 国在线网上发布了最初的g n u t e l l a ，但一天以后即被勒令停止下载，但是此时 7 硕i j 学位论文第一二章对等叫络的资源定位技术 大约已有2 3 k 用户使用g n u t e ll a ，并丌始交换和共享数据。今天，作为p 2 p 文 件共享的始祖，g n u t e l l a 仍然被广泛的使用，著名的g n u t e l l a 客户端包括了 s h a r e a z a 2 0 3 。g n u c l e u s l 2 1 1 ，x o l o x 2 2 1 ，l i m e w i r e 2 ：1 ，b e a r s h a r e 2 4 1 ，m o r p h e u s 2 5 1 。 g n u t e l l a 网络中的每一台节点机，即所谓的一个p e e r 也被称为s e r v e n t 。 这是s e r v e r 和c l i e n t 两个单词的复合，表明每个节点既有服务器的功能又有 客户机的功能。s e r v e n t 一方面提供客户机界面使用者借以提交查询请求、 浏览查询结果，同时接收来自其它s e r v e n t 的查询请求、在本地数据集中查找 匹配信息、给出适当的应答。 g n u t e l l a 协议包括了五种消息，其格式包括了头( h e a d e r ) 和数据荷载 ( p a y l o a d ) 两部分比6 。，如图2 - 3 所示： 头( h e a d e r )数据 0 2 2 b y t e2 3 b y t e 最大 图2 - 3g n u t e f a 的数据格式 数据头描述了消息的类型，g n u t e l l a 共有五种消息的类型心7 1 ，其类型和描 述如表2 - 1 所示。 表2 - 1g n u t e 1l a 协议通信描述符定义 描述符描述 p u s h 用于在g n u t e l l a 网络中主动发现对等点， 一个收到p i n g 描述符的对象点会向发送方响应 一个或多个p o n g 描述符。 用于对p i n g 响应的描述符。他包括一个相 连的g n u t e ll a 对等点的地址和有关该节点能提 供给网络共享的信息。 是搜素g n u t e ll a 分布式网络的主要机制， 一个收到q u e r y 描述符的对等点，如果其本地 共享信息与q u e r y 搜索的内容匹配，将会响应 一个q u e r y h i t 给q u e r y 的发起者。 用于对q u e r y 响应的描述符。他包括匹配 q u e r y 搜索数据的对等点i p 地址及端口号、传 输速度及结果集、对等点标识等。 提供一种机制允许一台处于防火墙后的对 等点向g n u t e ll a 网络提供基于文件的数据。 8 顾l ：学位论义第一二帝对等州络的资源定位技术 g n u t e l l a 采用洪泛算法，其查询机制如下心8 | ： ( 1 ) 节点加入网络，g n u t e l l a 网络中的节点都至少与另外个节点相连， 所以节点加入网络首先要连接到网络中的任意一个节点。 ( 2 ) 加入网络后的节点将通过p in g p o n g 消息获得网络的相关信息，首先新 加入的节点通过p i n g 消息向网络发布自己的身份，然后网络中收到p i n g 消息 的节点回复p o n g 消息，并根据需要继续向其他节点转发，p o n g 消息通过相同 的路径返回源节点。通过这样的方式使得新加入的节点获得网络信息。 ( 3 ) 节点搜索消息，g n u t e n a 网络中的节点以泛洪的方式查询所需信息。节 点通过q u e r y 消息向网络中的其他节点广播所需文档信息，收到q u e r y 消息的 节点检查自身数据是否匹配查询信息，若匹配就回复q u e r y h i t 给q u e r y 的发起 节点，否则将继续向其他节点转发此q u e r y 消息，直到t t l 为零时截止。 ( 4 ) 信息下载，q u e r y 消息的发起者通过q u e r y h i t 回复信息获得目标节点 的地址，便可以通过点到点的方式建立t c p 连接通过h t t p 协议直接从目标节点 处下载所需信息，若目标节点位于防火墙内，可以通过p u s h 信息进行反向连接。 6 n u t e n a 的资源搜索机制如图2 4 所示。 图2 - 4g n u t e ll a 网络搜索机制 9 r - - _ q 埘 l 董； 倾i ：学位论文第_ 二审对等叫络的资源定位技术 2 2 2 算法的改进 非结构化p 2 p 网络采用集中目录式搜索算法和泛洪搜索算法，但是主要以 泛洪搜索算法为主。由于泛洪搜索算法容易产生大量的网络流量，带来很大的 网络负载，据2 0 0 1 年3 月的统计报告啪1 ，g n u t e l l a 网络中大约有5 5 的流量是 由于p i n g 和p o n g 消息包产生的。叫，其中包含了很多不必要的重复包流量，严 重吞噬网络带宽，影响网络性能。所以目前对泛洪搜索算法进行了很多改进， 主要体现在改进查询请求的转发策略和节点拓扑结构的构造两个方面。以下介 绍基于这两个方面改进的泛洪搜索算法。 1 基于查询请求转发策略的改进 基于查询请求转发策略的改进是指它将不同于传统泛洪搜索算法那样把查 询请求转发给所有的邻居节点，而是有选择地转发，这种转发策略的改进可以 减少网络中的消息流量，减少被访问的节点，同时也减轻了节点的处理负担， 这样便节省了带宽，提高了响应速度，达到快速地搜索到所需资源的目的，目 前主要有以下几种改进算法： 迭代泛洪算法口：即逐步加深搜索算法，这种算法的实现过程是进行多次泛 洪搜索，每次搜索的深度限制依次递增，即每次搜索的t t l 值都大于前一次搜 索，当查询结果满足要求或者已经达到最大的深度限制时，就不再继续下一个 深度优先搜索，搜索过程结束。因此，对于能够在较小的范围内找到满意结果 的情况，这种算法就减少了查询的节点数，节省了搜索的时间和资源的消耗， 提高了搜索效率。 启发式泛洪算法b 2 1 ：其搜索思想是把查询请求转发给邻居节点中过去表现 优秀的那些节点，是基于过去表现优秀、能提供很好的搜索请求的节点在将来 的查询中也会表现优秀的假设。与其搜索思想类似的是有向宽度优先搜索算法 口3 。，同样将查询消息仅仅转发给邻居节点集中的一个子集，节点根据其记录的 关于邻居节点的历史信息有选择的把查询消息转发给那些能对消息进行很好回 应的有限个节点，从而使得较短的时间内查询到结果，降低了查询开销，减少 了通信量，保证了查询结果的质量。 随机游走搜索算法1 ：和上述算法一样同是属于盲目搜索算法，但是不同的 是随机游走搜索算法将查询请求转发给邻居节点中的一个，一个随机步定义为 一个搜索进程，n 个随机步进程同时搜索将大大降低了网络带宽的消耗，提高 搜索的效率和系统的可靠性。文献 3 5 证明了泛洪搜索算法并不比随机游走搜 索算法更有效。文献 3 6 进一步对无结构p 2 p 网络的随机步搜索进行了定量分 析，并指出当p 2 p 网络的拓扑结构呈现较强的簇的特征以及同一个节点重复发 1 0 硕i j 学位论文第一二章对等叫络的资源定位技术 出类似的搜索请求时，随机步搜索算法比泛洪搜索算法更有效。 本地索引和路由索引技术口7 1 ：在本地索引中，节点建立r 跳距离内的邻居节 点的数据索引，r 称为索引半径，是一个系统变量，当r = o 时，节点只建立自 己的数据索引。当节点接到查询请求时，可以代替r 跳距离内的邻居节点处理 查询清求。采用这种搜索算法，查询很少一部分节点就相当于查询了很多节点， 这种算法和超级节点的方式有些类似，但不同的是这里节点所负责的其他节点 的数量可以因设定不同的索引半径r 而不同。路由索引技术不同于本地索引是 因为它还具有路由作用，不仅存储文档的地址，还存有其他一些相关的数据， 使得节点可以根据邻居节点对查询的某个方面的优劣程度对它们进行排序，使 得节点能够根据这个排序，将查询请求转发给更可能响应请求的邻居节点。从 而减少不必要的通信量。 2 基于节点拓扑结构构造的改进 基于节点拓扑结构构造的改进主要表现在两个方面： 一个方面就是引入了“超级节点的概念m 棚1 。超级节点将整个网络划分 为多个子网，每个超级节点被视为其所在子网的中央服务器，因为它保存这个 子网内的所有节点的索引信息，负责其搜索和维护等工作，所以查询了一个超 级节点就相当于查询了一部分节点，从而避免了泛洪搜索算法中的大量冗余搜 索包的问题，明显地提高了搜索的效率。在目前流行的p 2 p 软件中，k a z a h 和 m o r p h e u s 就是基于这种思想的代表。 另一个方面是基于节点表现的兴趣组织网络。基于兴趣的定位搜索方法 ( i n t e r e s t e d - b a s e dl o c a l i t ys e a r c h ) h 仉4 的思想是：每个节点所共享的文档都 表现出某种特定的兴趣，兴趣相似的节点保存的内容也相似，通过深度挖掘每 个节点的兴趣，按照节点的兴趣组织网络，使得兴趣相近能够互相满足查询要 求的节点聚集在一起。这样根据g n u t e l l a 网络所具有的小世界特征h 引，节点可 以在自己的临近找到结果，而不需要把查询请求转发到远处。基于兴趣的资源 定位方法在不改变g n u t e l l a 下层机制的条件下，缩小了查询搜索范围，节约了 带宽，节省了节点计算资源的消耗，而且提高了搜索的响应速度和查全率。 2 3 结构化对等网络 泛洪算法的不可扩展性在g n u t e l l a 的实践中得到了证实。虽然仍然有些研 究继续在这类非结构化系统的基础上进行，但是更多的研究焦点转向了结构化 系统。结构化对等网络也是完全分布式的对等网络系统，通常采用的是分布式 哈希表( d i s t r i b u t e dh a s ht a b l e ) 的结构。和非结构对等网络相比，结构化 对等网络对文档在系统中的存放位置有严格的控制并且节点之间的关系比较紧 硕i j 学位论文第一二章对等网络的资源定位技术 凑。结构化对等网络的最大优点在于它可以在0 ( 1 0 9 n ) ( 其中n 是系统中节点 的数目) 的跳数之内完成文档的路由和定位。结构化对等网络的主要特点是自 组织、可扩展、负载均衡、以及较好的容错性。和非结构对等网络主要用于文 件共享领域不同，结构化对等网络的这些优良特性使得它可以应用在对可靠性 和扩展性要求比较高的场合。 简单的理解，结构化对等网络中每个文档对应一个m 比特长的唯一标识符， 可以将文档的这个唯一标识符理解为一个虚拟空间中的地址。整个虚拟空间被 划分为很多个区域，每个区域包含了若干连续的虚拟地址，系统中的每个节点 负责这些区域中的一个或多个。文档被存储在负责它的虚拟地址所在区域的节 点中，对文档的插入和查找操作的路由通过文档的虚拟地址进行。虚拟空问中 区域的划分和负责每个区域节点的选择都是动态的，每次节点加入或者离丌系 统都会导致动态的调整。文档的唯一标识符通过对文档内容或u r l 进行哈希变 换得到，相容哈希变换( c o n s i s t e n th a s h i n g ) n 3 1 是最常用的算法。 采用了分布式哈希表结构的结构化对等网络很好的解决了系统的扩展性问 题，比无结构对等网络更适合大规模的应用。在d h t 基础上，由于采用的哈希 表分片策略不同，节点问消息传播方式不同，节点定位机制不同，产生了很多 变种。下面介绍其中的一些典型系统。 c a n ( c o n t e n ta d d r e s s a b l en e t w o r k ，内容寻址网络) 实质上是一种分布式 的、i n t e r n e t 规模的哈希表，它的基本操作包括插入、查找和删除表中的( k e y ， v a l u e ) 数据对。网络中的每个节点存储哈希表的一部分，称之为区( z o n e ) ，以 及相邻的几个区的信息。插入、查找或删除特定关键字的请求通过相邻的区路 由，到达负责维护请求关键字所在区的节点。 c a n 基于虚拟的d 维笛卡儿坐标空间实现其数据组织和查找功能。整个坐 标空间动态地分配给系统中的所有节点，每个节点都拥有独立的、互不相交的 一块区域。系统使用统一的哈希函数将文件标识符k 映射到笛卡儿坐标空间的 点p ，负责点p 所在区的节点存储数据对( k e yk ，v a l u ev ) 。如图2 - 5 ( a ) 中， 一个关键字映射的坐标( 0 1 ，0 2 ) 位于区b ，它将存储在负责区b 的节点上。c a n 中的节点维护一个与它相邻区的节点信息表，包括节点的i p 地址等信息，以保 证在空间中任意的点之白j 路由。直观上，c a n 的路由沿着源节点到目的节点在 笛卡儿空间中的坐标直线路径。任何节点都可以使用相同的哈希函数得到关键 字k 对应的点p ，当需要查询关键字k 对应的值时，根据相邻区的节点信息表， 找到负责点p 所在区的节点取出相应的值。如果此节点不是发起查询请求的节 1 2 幕一口w 等m 络的话镡定仳挫术 点，c a n 将此查询请求转发到对应的节点。如图2 - 5 ( a ) 中所示节点a 发出请 求，其请求关键字1 i 兜射到点p ，请求沿着箭头所示的直线由区 ，b 到e 。 。1 ) ( b ) 圈2 - 5c a n 的查拽机制和节点加入 新加入的节点利用文献 4 4 中所描述的引导机制找到c a n 中已存在的一个 节点。根据c a n 的路由机制，节点随机地选择坐标空间中的一点p ，然后向负 责点p 所在区域的节点发出j o i n 请求。负责点p 的节点将自己的区域分成两半， 将其中一半分给新加入的节点。如图2 5 ( b ) 中所示，新加入的节点f 随机地选 择点p ，然后向负责点p 的节点e 发出j o i n 请求，请求沿着箭头方向到达节点 e ，节点e 将自己的区分半给节点f 。新加入的节点通过了解自己新邻居的i p 信息以及相邻区的信息建立自己的路由表，并通知新邻居更新它们的路由表使 其包含新加入的节点。 当节点f l 离开c a n 时，n 的一个邻居节点n 负责接管节点n 所负责的区及 哈希表。如果这个区域可以和相邻区域合并形成一个太的区域，那么c a n 将执 行合并操作。如果合并不能进行，那么该区域将交给其邻居节点中区域最小的 节点。 在正常情况下，节点定期地向每个邻居节点茇送更新信息，报告自己的区 坐标、邻居列表和邻居的区坐标。如果多次没有收到某个节点的更新信息，邻 居节点则认为这个节点失效，并启动取代操作。如果一个失效节点的多个邻居 节点也失效了，凌失效节点的一个邻居节点则启动一种扩展环( e x p a n d i n gr i n g ) 搜索机制寻找该失效区外任意的正在运行的节点。 t a p e s t r y “”是用于覆盖网络的定位和路由机制，它可以在分布的环境下将 请求路由到目标( 如果网络中有多于一个拷贝的话，将路由到最近的拷贝) 。通 ，；_l一墨一尉尉。 - - - e p - rr卜。壁 l 了。一 1l， 麓一 一a士m一 硕i j 学位论文第一二章对等m 络的资源定位技术 过忽略失效的路径和节点、快速适应通信拓扑，t a p e s t r y 提供系统范围内的稳 定性，并具有自我管理和容错的特点。 1 、p l a x t o nm e s h t a p e s