（计算机应用技术专业论文）一个p2p资源查找的改进方法.pdf

河海大学硕士研究生论文 摘要 摘要 在过去的几年中，对等网络( p e e r t o p e e rn e t w o r k ，简称p 2 p ) 的迅速发展 引起了计算机界的关注，根据p e e r t o p e e rw o r k i n gg r o u pc o m m i t t e e 的定义， p 2 7 在商业上的应用主要有文件共享、边界服务、分布式计算，但文件共享是目 前最重要的一个应用。如何实现资源的定位是文件共享的关键问题。g n u t e l l a 网络模型被认为是存粹的p 2 p 系统的代表，目前世界上使用用户最多的文件共享 软件都基于g n u t e l l a 网络模型，g n u t e l l a 网络的主要问题是使用“扩散”方式搜 索、发现网络节点及共享信息，随着网络规模的增长，不仅搜索消息的比率在增 长，而且由每一条消息产生的潜在流量也在大幅增长。其中包括了许多不必要的 重复包流量。因此，应该研究和改进g n u t e l l a 网络的资源定位机制。 现有的定向广度优先搜索方法只是从动态变化的网络中寻找某一段时间内 具有某些特定性质的节点，只对这些节点进行资源查找，忽略了大量有用的节点， 而本地索引法中节点建立的索引大小与共享文件的大小成正比，导致索引空间过 大。本文针对这两个问题，借鉴t c p i p 协议中网络路由的思想，提出了路由表查 找法。采用动态路由方法来捕获网络中发生的变化，克服了定向广度优先搜索法 只搜索特征点的缺点，采用路由表指示查找的方向，从而使得路由表的大小与邻 节点的数量成正比，而不是与共享文件数量成正比，减少了网络中的流量。本文 工作如下： 1 根据p 2 p 系统中路径选择和互联网中路由器的路由行为的相似性，将每一 个转发消息的节点都看成一个路由器，因此p 2 p 网络节点的路由问题可看成是路 由器的路由问题，在每个节点建立路由表进行路由选择； 2 网络中某一段时间内具有某些特定性质的节点，作为特征点，把网络中的 特性点信息作为默认值，保存在节点的路由表的默认值项中； 3 根据网络具有动态变化的特性，用两种动态路由方法：集成路由表法和跳 数路由表法，主动捕获网络中发生的变化，并把系统中发生的变化进行更新，存 储到路由表中，为进行动态路由提供信息； 本文先对集成路由表和跳数路由表方法进行了实验比较，然后将路由表查找 方法与定向广度优先搜索方法进行了实验比较，并得出结论：对比开销和查找性 能的提高，可以看出路由表查找方法是一个比较好的查找方法。 关键词：p 2 p 、g n u t e l l a 、路由表查找法 河海大学顾士研究生论文 a b s t r a c t d u r i n gr e c e n ts e v e r a ly e s r s ，p e e r t o p e e rn e t w o r k sh a v eb e e nf o c u s e d o n b yt h ec o m p u t e rr e a l m a c c o r d i n g t ot h ed e f i n i t i o no fp e e r t o p e e r w o r k i n gg r o u pc o m m i t t e e ，p 2 pc a nb eu s e di nt h ef i l es h a r i n g ，d i s t r i b u t e d c o m p u t i n ga n ds oo n b u tf i l es h a r i n gi st h ed o m i n e n tp 2 pa p p l i c a t i o n h o w t ol o c a t ed e s ；i r e df i l e si so n eo ft h ek e yi s s u e s g n u t e l l an e t w o r k sm o d e l ist h er e p r e s e n t a tiv eo fp u r ep 2 ps y s t e m s a tp r e s e n tt h em o s ts o f t w a r e s o ft h ef i l es h a r i n gu s e da r eb u i i to nt h eg n u t e l l a t h ep e e r sa n di t ss h a r e d f i l e sa r es e a r c h e da n df o u n db yf l o o d i n gi ng n u t e l l a w h e nn e wp e e rj o i n i n g t h ep 2 pn e t ，t h en u m b e ro fs e a r c h i n gm e s s a g e sa sw e l1a st h el a t e n c yf l u x g e n e r a t e db ye v e r ym e s s a g e i s i n c r e a s i n g t h o s e i n c l u d em a n yn e e d l e s s r e p e a tm e s s a g e sa n df l u x t h e r e f o r e ，i ti s n e e d e dt or e s e a r c ht h ef il e s e a r c h i n gi n g n u t e l l a e x i s t e n ts e a r c hm e c h a n i s m se i t h e ro n l yf i n ds o m es p e c i a lp e e r sa n d s e a r c hf i l e si nt h o s ep e e r ss ot h a tm a n ya v a i l a b l ep e e r sa r ei g n o r e d ，o r s c a l eo fi n d i c e sp e e r si sp r o p o r t i o no fs c a l eo fs h a r e df i l e ss ot h a t i n d i c e si st o ol a r g e t h et h e s i sr e s e a r c h e st h o s ep o i n t sa n di m p o r t st h e d y n a m i cr o u t ei d e s ，t h e ni n t r o d u c e ss o m em a i na m e n d m e n t s ，t h ek e y sa r ea s f o l l o w s ： 1 a c c o r d i n gt ot h es i m i l a r i t yb e t w e e np a t hs e l e c t i o ni np 2 ps y s t e ma n d i n t e r n e tr o u t ea c t i o n ，e v e r yp e e ri ss e e na sar o u t e ra n db u i i d si t so w n r o u t et a b l e ： 2 t of i n ds p e c i a lp e e r sa n ds t o r et h e i ri n f o r m a t i o ni nd e f a u l tc o l u m n o ft h er o u t et a b l e ： 3 t ou s e m e t h o d s ( i n t e g r a t i o n r o u t e t a b l e ，o r h o p r o u t et a b l e ) t o i n iti a t i v e l yg e tt h en e t w o r kc h a n g e sa n ds t o r et h o s ei nt h er o u t et a b l e ： t h et h e s i sc o m p a r e st h ei n t e g r a t i o nr o u t et a b l em e t h o da n dt h eh o p r o u t et a b l em e t h o d ，t h e ni tc o m p a r e st h er o u t et a b l em e t h o da n dd i r e c t e d b r e a d t hf i r s ts e a r c hm e t h o db a s e do ne x p e r i m e n t s ，a n dd r a w sc o n c l u s i o n s k e y w o r d s ：p 2 p 、g n u t e l l a 、r o u t et a b l es e a r c h i n gm e t h o d 河海大学硕士研究生论文 第一章绪论 1 1 研究动机 第一章绪论 p 2 p 是英文“p e e r t o p e e r ”的缩写，称为对等网或点对点技术。p 2 p 是一 种网络模型，在这种网络中所有的节点是对等的( 称为对等点) ，各节点具有相 同的责任与能力并协同完成任务。对等点之间通过直接互连共享信息资源、处理 器资源、存储资源甚至高速缓存资源等，无需依赖集中式服务器或资源就可完成。 这种模式与当今广泛使用的客户端n 务器( c s ) 的网络模式形成鲜明对比，c s 模式中服务器是网络的控审0 核心，而p 2 p 模式的节点则具有很高的自治性和随 机性。随着像n a p s t e r 、g n u t e l l a 这种信息共享应用程序变得越来越流行，p 2 p 技术 受到人们的广泛关注。 根据p e e r t o p e e rw o r k i n gg r o u pc o m m i t t e e 的定义，p 2 p 在商业上的应用主 要有文件共享、边界服务、分布式计算“1 ，p 2 p 提供了一种新的计算模式，将p 2 p 和现有的网络技术结合起来会带来一些突破。如将p 2 p 和多播结合起来改进流媒 体的播放：将p 2 p 和q o s 结合起来，改善网络的性能：将p 2 p 和a c t i v en e t w o r k 结合， 利用a c t i v e n e t w o r k 中的移动代码主动地改进网络结构，决定最佳路由等。 尽管p 2 p 在很多方面有重要应用，文件共享是目前最重要的一个应用。如何实 现资源的定位是文件共享的关键问题。g n u t e l l a 网络模型被认为是存粹的p 2 p 系统的代表，目前世界上使用用户最多的文件共享软件都基于g n u t e l l a 网络模 型，g n u t e l l a 网络的主要问题是使用“扩散”方式搜索、发现网络节点及共享信 息，随着网络规模的增长，不仅搜索消息的比率在增长，而且由每一条消息产生 的潜在流量也在大幅增长。据最近一个统计。1 ，g n u t e ll a 网络流量有大约5 0 是由 于p i n g 和p o n g 包消息产生的。其中包括了许多不必要的重复包流量! 查询包 ( q u e r y ) 的情况也与之类似。因此，应该研究和改进g n u t e l l a 网络的资源定位 机制 1 2 文件共享方面的研究现状 在最近几年中，基于p 2 p 的网络结构的变革浪潮席卷了整个世界。这种网络 结构和系统不再通过一个中心服务器来获得资料，而是计算机之间直接建立连接 来获得资源。目前文件共享是p 2 p 网络最重要的应用领域，p 2 p 技术使得用户易 于实现资源的共享，搜索和交换。 g n u t e l l a 网络模型被认为是完全分布式p 2 p 系统的代表，现在世界上使用 河海大学硕士研究生论文第一章绪论 用户最多的文件共享软件都基于完全分布式p 2 p 系统网络模型。目前研究和改进 基于g n u t e l l a 网络的资源查找机制的方式有以下4 种： 1 智能化的选择进行查询的节点，只向被选择的节点发送查询消息的方式，如 定向广度优先搜索方法； 2 提高网络的冗余的方式，如预先复制文件法； 3 网络节点建立索引的方式，如本地索引法： 4 利用特有的网络结构的方式，如最大聚集度优先法 这些方式可以单独使用，也可以相互结合使用来提高查询效率 研究表明：大多数的查询结果是由网络中少量的节点提供“”“6 ”。在此基 础上，b e v e r l yy m l g 和h e c t o rg a r c i a - m o l i n a 提出了迭代深入方法、定向广度优 先搜索“，黄道颖等研究了可选择的查询分配方法，使用多路平行查询机制进行 查询“，v a n ak a l o g e r a k i 等提出了一个智能化的搜索机制“e c o h e n 等提出 预先复制其他节点的共享文件，在网络中形成高度的冗余，提高查询效果的方法 。，b y a n g 等研究了将智能化选择网络节点和提高节点冗余这两种机制结合起 来的方法l a d a m i c 等和a c r e s p o 等研究了网络节点建立索引的方法。”。” l a d a m i c 等和黄道颖等研究了利用网络的幂规律和小群体的特点提高查询性 能的方法“” 1 ” 2 “ 1 3 问题的提出 g n u t e l l a 网络中对等机节点利用“广播扩散”方式来搜索网络和发现共享信 息。1 。随着联网节点的不断增多，网络规模不断扩大，通过这种“扩散”方式 定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因 网络资源过载而失效，这样会使得g n u t e l l a 网络被分片、查询访问只能在网络的 很小一部分进行。据最近一个统计0 1 ，g n u t e l l a 网络流量有大约5 0 是由于p i n g 和 p o n g 包消息产生的。显然，其中包括了许多不必要的重复包流量。查询包( q u e r y ) 的情况也与之类似。因此提高资源查找机制有效性和查找速度的关键是降低网络 节点之间的信息交流开销，也就是减少节点之间发送的消息量和对每个查询进行 处理的的节点数量。 在g n u t e l l a 网络中现有的资源查找方法，要么只是从动态变化的网络中寻找 某一段时间内具有某些特定性质的节点，只对这些节点进行资源查找，忽略了大 量有用的节点( 如定向广度优先搜索方法) ，要么节点建立的索引大小与共享文 件的大小成正比，导致索引空间过大( 如本地索引法) 。本文针对这些问题，结合 g n u t e l l a 协议的特点，引入t c p i p 中动态路由的思想，对现有方法进行了改进。 2 河海大学硕士研究生论文 第一章绪论 1 4 本文的工作和组织 本文结合g n u t e l l a 协议的特点，引入t c p i p 协议中动态路由的思想，提出了 路由表查找法，要点如下： 1 根据网络进行动态路由的特点，将每一个转发消息的节点都看成一个路由 器，因此p 2 p 网络节点的路由问题可看成是路由器的路由问题，在每个节点建立 路由表进行路由； 2 将网络中某一段时间内具有某些特定性质的节点，作为特征点，把网络中 的特性点信息作为默认值，保存在节点的路由表的默认值项中； 3 根据网络具有动态变化的特性，用两种动态路由方法：集成路由表法和跳 数路由表法，主动捕获网络中发生的变化，并将这些变化进行更新，存储到路由 表中，为进行动态路由提供信息： 4 利用p 2 p 网络具有的幂规律( p o w e r l a w ，网络中少数节点具有较多的邻居 节点) 的网络结构的特点，将具有较多邻节点的节点信息存放在路由表的默认值 项中，为进行查询提供信息。 本文的其它部分安排如下： 第二章：本章作为技术背景，论述了p 2 p 的概念、特征，对目前p 2 p 网络的 结构分类进行了介绍，对p 2 p 技术的应用领域和关键技术进行了分折，最后对各 种p 2 p 文件共享结构进行了论述，对它们的资源查找机制进行了分析。 第三章：本章对现有的各种典型的基于g n u t e l l a 网络的资源查找的机制按照 资源查找方式不同，分类进行了论述和分析总结。 第四章：本章是本文的核心，在本章中提出了将每一个转发消息的节点都看 成一个路由器，在每个节点建立路由表，将网络中某一段时间内具有某些特定性 质的节点，作为特征点，把特征点信息保存在节点路由表的默认值项中，网络的 动态变化由集成路由表方法或者跳数路由表方法捕获。本文详细论述了集成路由 表方法或者跳数路由表方法的原理和工作过程。 第五章：本章是本文的试验部分。本章首先对试验的评价标准进行分析，提 出了资源查找方法的评价标准，其次对第四章中提出的集成路由表方法或者跳数 路由表方法进行了试验，并进行了分析和比较，第三，对第四章中的路由表查找 法进行了试验分析，并得出结论。 第六章：工作总结和展望。本章对论文的内容进行了总结，并展望了今后需 要进一步完善和开展的工作。 河海人学硕士研究生论文 第二章p 2 p 概述 第二章p 2 p 概述 2 1p 2 p 概述、特征及应用 2 1 1p 2 p 的概念 p 2 p 是p e e r - t o p e e r 的缩写，p 2 p 可以理解为“伙伴对伙伴”的意思，或称 为对等联网。p 2 p 起源于最初的联网通信方式，是一种比较古老的技术，如产生 于1 9 7 9 年的u s e n e t 1 9 8 4 年的f i d o n e t 都是基于p 2 p 技术的，但是目前p 2 p 已被赋予了新的含义，是旧有技术的新的应用模式【l “。 p 2 p 的原意是种通信模式，在这种通信模式中，每一个部分具有相同的能 力，任意一个部分都能开始一次通信。现在，对p 2 p 概念进行了扩展，如m 公司认为：p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特征之一： 系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成 员而不是从服务器的参与中受益；系统中成员同时扮演服务器与客户端的角色； 系统应用的用户能够意识到彼此的存在，构成一个虚拟或实际的群体。【4 7 】【1 1 】 对等网络尚无统一的标准。2 0 0 0 年8 月成立了p 2 p 工作组，成员包括i n t e l 、 m m 和h p 公司等。发展对等网络的其他主要障碍还有版权问题、网络带宽问题、 管理问题和安全问题等。如何连接电话、手机和家电、工业设备婷，也是对等网 络需要解决的问题。“】 2 1 2p 2 p 技术的应用 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心从 中央服务器向网络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以建立p 2 p 对话。 这使人们在i n t e m e t 上的共享行为被提到了一个更高的层次，使人们以更主动深 刻的方式参与到甄络中去，正如1 2 ( 第二代互联网) 之父d o u g v a i - i o u w e l i n g 在 中国之行时说到的：“下一代互联网民们将真正参与到网络中来，每个人都能为 网络的资源和功能扩展作出自己的贡献。” p 2 p 给互联网的分布、共享精神带来了无限的遐想，有观点认为至少有1 0 0 种应用能被开发出来，但从目前的应用来看，p 2 p 的威力还主要体现在大范围的 共享、搜索的优势上。从目前的应用来看，p 2 p 的应用如下： 6 i t 】 4 河海大学硕士研究生论文 第二章p 2 p 概述 ( 1 ) 即时通信软件，如i c q 等。2 个或多个用户可以通过文字、语音或文 件进行交流，甚至还可以与手机通信。 ( 2 ) 实现共享文件资源的软件，如n a p s t e r 和g n u t e l l a 等。用户可以直接从 任意一台安装同类软件的p c 上下载或上载文件，并检索、复制共享的文件。 ( 3 ) 游戏软件。目前的许多网络游戏都是通过对等网络方式实现的。 ( 4 ) 存储软件，如f a r s i t e 。用于在网络上将存储对象分散存储。 ( 5 ) 数据搜索及查询软件，如i n t j a s e a r c h 、p o i n t e r a 。用来在对等网络中完 成信息检索。 ( 6 ) 协同计算软件，如n e t b a t c h 。可连接几千或上万台p c ，利用其空闲时 间进行协同计算。 ( 7 ) 协同处理软件，如g r o o v e 。 2 2p 2 p 系统结构及其关键技术 2 2 1p 2 p 系统结构 p 2 p 系统进行分类通常有两种划分标准：按照集成度来区分，按照网络的结 构来区分。9 】 1 按照集成度来区分：p 2 p 系统可以根据它们的集成度来进行分类，即系统如 何使用服务器在节点之间进行相互交互。通常可分为三类： ( 1 ) 纯分布式p 2 p 结构( 比如最初的g n u t e l l a 结构) 在这种p 2 p 网络中所有的节点都既是服务器，又是客户端。它们在网络中 有着同等的作用，没有中心式的节点对它们之间的交互起协调作用。这些节点被 称为：“s e r v e n t s ”( s e r v e r s + c l i e n t s ) 。 ( 2 ) 部分中心式的系统( 比如k a z a a ，m o u p h e u s 等) 这种系统的结构同纯分布式的系统一样，只是有些节点被认为比其它节点更 重要。这些节点上有其它节点上共享文件的索引。它们被叫做“s u p e m o d e s ( 超 级节点) ”。单个的s u p e r n o d e s 不能组成一个p 2 p 网络，因为它们是被动态任命 的，万一它们被恶意的攻击，网络能够任命其它的节点作为新的s u p e r n o d e s 来 取代原有的s u p e m o d e s 。 ( 3 ) 混合式的分布式结构( 比如n a p s t e r ) 在这种网络中有一个中心服务器，进入网络的节点首先要以元数据的方式在 中心服务器上进行注册，中心服务器通过维护其他节点的元数据来方便节点之间 的交互。端到端的交互就是节点间的交互，这个中心服务器通过进行查找和确定 网络中拥有相关文件的节点来对节点间的交互提供便利。 河海大学硕士研究生论文 第二章p 2 p 概述 显然在这种结构中中心服务器是一个单一的故障点。技术故障和恶意攻击容 易使得服务器出现故障，从而失去使用这种p 2 p 结构的优势。这种系统并不被 认为是真正的p 2 p 系统，而是被认为是标准的客户一服务器结构的范例，只不过 在节点间进行文件传输而已。 2 按照系统是否建立覆盖网络结构来区分：结构化的p 2 p 系统由带有复杂拓扑 结构的高度动态的网络节点组成。这个拓扑结构建立了一个覆盖网络，它与连接 不同节点的物理网络无关，网络中的共享文件可以根据网络的拓扑结构进行定 位。p 2 p 系统根据是否建立了结构化或特殊的覆盖网来区分，可分为两类：非结 构化网络和结构化网络。 ( 1 ) 非结构化网络( 比如g n u t e l l a ) ： 在这种系统中文件的位置和覆盖网完全没有关系。因为节点没有相关文件的 信息进行文件定位，所以需要查询每个节点是否有与查诲条件匹配的文件。 非结构化的p 2 p 系统中不需要建立覆盖网，这种结构的优点是网络臭有很 强的动态性，节点可以随时离开和加入网络，缺点是查找到理想的文件需要进行 大范围的搜索。因为这个原因，非结构的p 2 p 系统被认为是可扩展性不强，可 是现在正在进行许多研究以增加非结构化系统的可扩展性。 ( 2 ) 结构化的网络( 比如c h o r d ，c a n ，p a s t ，t a p e s t r y 等等) 结构化网络的出现主要是解决非结构网络可扩展性差的问题。这些系统建立 覆盖网后，将文件放置在规定好的位置上，在文件标识苻和文件位置之间建立了 一个映射，形成了一个分布式的哈希表，使得查询能够有效的定位到要查找的文 件。 非结构化的系统对于精确查询提供了一个可扩展的方案，因为要查找的资料 的标识苻是明确的。结构化系统的缺点是很难在具有高动态性的网络中( 如 g n u t e l l a 网络中节点加入、离开网络很频繁) 维持网络的结构。 ( 3 ) 松散结构的网络( 比如f m e n e t ) 这种网络结构介于非结构的网络结构和结构化网络结构之间。文件的定位有 一些索引信息麓够进行提示，但是这些索引信息并没有规范，因此搜索的效果并 不理想。 2 2 2p 2 p 系统关键技术 2 _ 2 _ 2 1p 2 p 的优势 p 2 p 是一种基于互联网环境的新的应用型技术，它的优势在于： ( 1 ) 负载均衡。p 2 p 网络环境下可以根据策略灵活分布信息。负载均衡模块 6 河海大学硕士研究生论文 第二章p 2 p 概述 可以监控各种信息的流量和请求率，然后重新分布这些信息以减轻单个节点的负 载。这种负载平衡策略可以提供分布式缓存才能实现的功能，且具备简单和低价 的特点。 ( 2 ) 信息资源丰富。任何p 2 p 网络用户能够扫描活动节点并搜索需要的信息， 然后直接从这个节点上下载信息。用户可以在他们的机器上把下载的信息共享出 来，这样，请求率高的文件能够很快地在许多节点上扩展开来。在一个开放网络 环境下，p 2 p 网络能够很快积累相当丰富的信息。 ( 3 ) 冗余和容错。p 2 p 网络的多个节点间的信息复制导致高度冗余，其直接 结果是提高了信息的可用性，使之为更多的用户提供服务。另外，冗余使得网络 不会产生“单点失效”问题，所以分散式的p 2 p 网络提高了网络的容错和安全。 ( 4 ) 基于内容的寻址。在w e b 上，u r l 地址并不能之间反映它们的内容。但 在p 2 p 网络之，存储特定信息的节点地址对于用户是透明的，用户向网络提交 查询请求时，请求信息中便包括需要查询的信息，p 2 p 软件把请求转换成存放这 些信息的节点地址，所以把信息按照内容分类后再分布在网络上，这更易于信息 资源的查找。 ( 5 ) 有效的搜索。w e b 搜路由表擎存在一些问题，因为这些搜路由表擎依赖 执行程序在i n t e m e t 上进行搜索，得到的信息存储在巨大的、可扩展的数据库找。 这些路由表信息仅包括开放的服务器，并且数据库不会随着网络状态动态更新。 但在p 2 p 网络中，任何节点的信息只有当节点在线的时候才被路由表，因此路 由表信息与网络状态同步。p 2 p 网络不依赖搜索程序重新访问链接来修改数据库 路由表信息，这种动态信息路由表和对信息的有效搜索使得p 2 p 具有显著优势。 5 1 2 2 2 2p 2 p 关键技术 p 2 p 是一种基于互联网环境的新的应用型技术，它的关键技术包括： ( 1 ) 拓扑一致性和资源定位。对于互联网上众多计算机，p 2 p 应用比其他应用 更多考虑那些低端p c 的互连，它们不具备服务器那样强的联网能力，同时对于 以往的p 2 p 应用技术，现在的硬件环境已经更为复杂，这样在通信基础方面， p 2 p 必须提供在现有硬件逻辑和底层通信协议上的端到端定位( 寻址) 和握手技 术，建立稳定的连接。涉及的技术有p 地址解析、n a t 路由及防火墙。 p 2 p 系统需要解决的一个重要问题是：在一个缺少集中化服务器的动态环境 下，各个节点能够维持一致的网络拓扑信息。由于p 2 p 网络中节点的加入和离 开非常频繁，传统路由扩散的方法难以解决这一问题，所以需要一个高效的一致 性信息维护机制实现一些功能。例如，当网络拓扑变化时快速恢复网络的稳定性 7 阿海大学硕士研究生论文 第二章p 2 p 概述 问题更具挑战性。另外，用户从大量分散的节点中找到需要的资源和服务也是一 个挑战。 ( 2 ) 互操作性。数据描述和交换的协议。在应用层面上，如果两个p e e r 分别 代表两家不同的公司，而且它们已经通过互联网建立连接，那么一方的信息就必 须为另外一方所识别，所以当前互联网上关于数据描述和交换的协议，如x m l ， s o a p ，u d d i 等都是一个完善的p 2 p 软件所要考虑的。 ( 3 ) 安全加密。p 2 p 中的安全问题直接决定了p 2 p 能否被大规模进行商用，除 了f r e e n e t 强调p 2 p 系统的秘名问题之外，大多数系统并没有对p 2 p 中的安全问 题做太多工作。p 2 p 中的安全问题包括信息的加密、用户身份的认证、恶意节点 的识别和应对等等。值得注意的是，在p 2 p 的分布式环境下，针对单个服务器 的拒绝服务攻击将不再有效。有通信就要有保障，加密技术是必须要考虑的。 ( 4 ) q o s 问题。p 2 p 网络的q o s 问题包括两个方面：1 信息获得的q o s 问题， 用户需要的信息肯在多个节点同时存放，如何选择一个处理能力强、负载轻、带 宽高的节点需要用户考虑。2 用户肯共享出无用或者违法信息，造成信息垃圾充 斥网络，因此，网络应该控制用户共享的信息，提高用户获得有用信息的效率。 ( 5 ) 其他问题。其他需要考虑的有如何设置中心服务器，如何控制网络规模、 改善查询性能等。 2 1 2 _ 2 3p 2 p 技术特性 ( 1 ) 既是服务器又是客户端，如何表现取决与用户的要求，网络应用由使用者 自由驱动。 ( 2 ) 信息在网络设备闻直接流动，高速及时，降低中转服务开销。 ( 3 ) 构成网络设备互动的基础和应用。 ( 4 ) 在使网络信息分散化的同时，相同特性的p 2 p 设备可以构成存在于互联 网这张大网中的子网，使信息按照新方式又一次集中。 2 3p 2 p 文件共享结构概述 这部分是当前p 2 p 文件共享结构和系统的一个概述【8 】 9 1 。高度动态变化的 p 2 p 网络具有复杂的拓扑结构，这个拓扑结构是一个上层的网络拓扑结构，它在物 理网络之上，物理网络连接不同节点。 表2 i 是p e e r t 0 一p e e r 文件共享系统的分类，从中可看出：有结构和松散 结构的系统都是纯分布式的结构，而非结构的系统可以是纯分布式的结构，也可 以是混合式的分布式结构，还可以是部分中心式的结构。非结构化的系统有：混 翌兰查兰竺圭! 竺竺丝兰塑三皇兰旦塑查一 合分布式的、纯分布式的和部分中心式的三种，松散结构的系统只有纯分布式一 种，结构化的系统也只有纯分布式的一种。 l u n s t m e t u r e d l o o s e l y s t r u c t u r e ds t l u c m r e d n e t w o r k sn e t w o r k sn e t w o r k s l h y b r i dd e c e n t r a l i z e d n a p s t e r l p u r ed e c e n t r a l i z e dg n u t e l l af r e e n e t c h o r d ，c a n ，t a p e s t r y p a r t i a l l yc e n t r a l i z e dk a z a a ，m o r p h e u s 表2 1p 2 p 文件共享系统分类图 上表并没有列出当前所有的p 2 p 系统，但是它们都是某一类型的典型代表， 与它们同类型的系统具有和它们相似的特点。 2 3 1 非结构化的系统 2 3 1 1 n a p s t e r n a p s t e r 是混合分布式的非结构化系统，通过一个中央服务器保存所有 n a p s t e r 用户上传的音乐曲目和存放位置的信息：当某个用户需要某首曲目时， 首先连接蛰 n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该曲目的 用户的信息：再由请求者直接连到曲目的所有者传输文件。这种方式最大的隐患 在中央服务器上，如果该服务器失效，整个系统都会瘫痪。另一个问题在于安全性 上，n a p s t e r 并没有提供有效的安全机制。o ” 2 3 1 2g n u t e l l a g n u t e l l a 是分布式的非结构系统，是一个利用p 2 p 的文件共享系统，它和 n a p s t e r 聂大的区别在：j = g n u t e l l a 是纯粹的p 2 p ，在g n u t e l l a 中没有类 以n a p s t e r 的中央服务器。所有的查询都通过在网络中以有限的f l o o d i n g 的方式进行，这种 方式虽然可以有效地找到需要的信息，但却会在网络中产生大量的流量。另外 g n u t e l l a 也没有提供足够的安全机制。嘲 2 3 1 3 k u i z a a 和m o r p h e u s k a z a a 和m o r p h e u s 都是部分中心式的非结构化系统，在这两个系统中都使用 s u p e r n o d e s ( 超级节点) 的概念。网络中的其它节点在超级节点上登记并建立目 录路由表。单个的超级节点不能组成一个p 2 p 网络，它们是被动态任命为超级节 9 河海大学硕士研究生论文 第二章p 2 p 概述 点的。如果节点具有足够的带宽和很强的处理能力，就会成为超级节点。k a z a a 和m o r d h e u s 都是有知识产权的，没有详细的技术文档，我们不知道它们具体是如 何运作的。 在m o r p h e u s q h ，一个中心式的服务器上有一个或者多个超级节点的列表。超 级节点为连接到它们上的节点的共享文件建立目录路由表，并代理其它节点进行 查询，因此查询被发送到超级节点上，而不是其它节点。 部分中心式系统的优点是它和纯分布式系统的查询相比，查询时间缩短了， 而且由于网络中没有一个唯一的中心服务器，因此不会出现由于中心服务器出现 故障而使得整个网络瘫痪的故障。如果一个或者多个超级节点出现故障，连接到 它们上的节点可以与其它超级节点建立新的连接。网络仍然能够继续运行。即使 大量的超级节点甚至全部超级节点都出现故障，那么现存的节点可以自己充当超 级节点，从而保持网络仍能运行。o “别。” 2 3 2 松散结构的系统 2 3 2 1f r e e n e t f r e e n e t 是一个基于j a v a 的跨平台分布式文件存储系统，其最大的特点就是 匿名。文件的发布者、查询者包括文件的持有者在f r e e n e t 中都是匿名的，为了 实现匿名，f r e e n e t 在路由上降低了效率，路由中的每个节点不能判断前一个节点 是否是文件的请求者、也不能判断后一个节点是否是文件的持有者。” 2 3 3 结构化的系统 2 3 3 1c h o r d 麻省理工学院设计了一种分布式的可扩展的查找和路由协议c h o r d ，c h o r d 通过将( k e y ，v a l u e ) 对中的k e y ( 如文件名) 和网络节点进行哈希计算，并将结果 映射到相同的值空间，将( k e y ，v a l 2 u e ) 对存储在最接近k e y 的哈希值的节点上。由 于逻辑上可以将所有的节点看作一个按照节点的哈希值排列的环，所以路由算法 采用了类似二分查找的方法，每次查找发送的消息数为o ( 1 0 9 ( n ) ) 。嘲。” 2 3 3 2c a n 伯克立和a t t 设计了另外一种基于d h t 的查找和路由算法c a n 。c a n 通过在现 河海大学硕士研究生论文 第二章p 2 p 概述 有的网络之上抽象出一层叠加网，将其中所有节点映射到一个n 维的笛卡尔空间 中，并为每个节点尽可能均匀的分配一块区域。c a n 采用的哈希函数通过对 ( k e y v a l u e ) 对中的k e y 进行哈希运算，得到笛卡尔空间中的一个点，并将 ( k e y ，v a l u e ) 对存储在拥有该点所在区域的节点内。c a n 采用的路由算法相当直 接和简单，知道目标点的坐标后，就将请求传给当前节点四邻中坐标最接近目标 点的节点。c a n 是一个具有良好可扩展性的系统，给定n 个节点，系统维数为d ，则 路由路径长度为0 ( n l p d ) ，每节点状态信息和网络规模无关为0 ( d ) 。”1 2 3 3 3 p a s t r y p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构 建大规模的p 2 p 系统。在p a s t r y 中，每个节点分配一个1 2 8 位的节点标识符号 ( n o d e l d ) ，所有的节点标识符形成了一个环形的n o d e i d 空间，范围从0 多 2 1 2 8 一l 节点加入系统时通过哈希节点i p 地址在1 2 8 位n o d e i d 空间中随机分配。 p a s t r y 中节点的路由状态包括以下三部分： 1 ) 路由表r ；它由l l 0 9 2 b n l 行，每行有2 b 一1 个入口的表项组成。行n 的2 b 1 个入 口指向其n o d e i d 和当前节点的n o d e i d 共享前n 位但第n + l 位不同的2 b - i 个表项。 值b 的选择考虑了路由表的长度和路由跳数的权衡，b 越大则路由跳数越少，但需 维护的路由信息多。 2 ) 邻居集m ；它包含了同本地节点最接近( 根据p r o x i m i t y m e t r i c ) 的f m j 个节点， 不用于路由转发而用于保证l o c a l i t y 特性。 3 ) 叶子集l ；它是l p 2j 个其n o d e i d 最接近且大于本地节点n o d e i d 的节点和f l 2j 个其n o d e i d 最接近且小于本地节点n o d e i d 的节点集合，典型的lll 和 m 值 是2 6 和2 2 “。 给定一k e y ，节点首先检查该k e y 是否落在叶子集范围内，如是，则直接把查 询请求递交到叶子集中n o d e i d 最接近该关键字的节点，查询结束：如在叶子集范 围之外，刚节点把查询请求首先转发到其n o d e i d 和k e y 共享的位数比本地n o d e i d 和k e y 共享的位数至少长一位的节点，如果不存在该节点则转发到共享位数一样 长但n o d e i d 数值比本地n o d e i d 数字更接近k e y 的节点。 给定n 个节点，p a s t r y 叠加网络中，路由一个消息需要o ( i o g n ) 步，每节点需 要维持0 ( 1 0 9 n ) 个入口，而且p a s t r y 路由具有l o c a lit y 特性。9 ” 2 4 小结 本章详细论述了p 2 p 的概念、特征，对目前p 2 p 网络的结构分类进行了介绍， 河海大学硕士研究生论文 第一二章p 2 p 概述 对p 2 p 技术的应用领域和关键技术进行了分析，本章最后对各种p 2 p 文件共享结 构进行了论述，对它们的资源查找机制进行了分析。 1 2 河海大学硕士研究生论文 第三章现有的资源查找方法 第三章现有的资源查找方法 在“非结构化”的系统中搜索需要的数据几乎是随机搜索，搜索从一个节点 开始逐个询问是否有匹配查询请求的数据，造成这样的问题，其根源是没有节点 可能存放哪些文件的信息。g n u t e l l a 采用所有的查询都通过在网络中以有限的 f l o o d i n g 的方式进行，通过t t l 限制f l o o d i n g 的范围。这种方式虽然可以有效地找 到需要的信息，但却会在网络中产生大量的流量，其中包括了许多不必要的重复 包流量。 如果不考虑非结构化系统的网络流量大这一问题，那么它们在文件共享和其 它应用方面仍然是首选的网络结构。所以努力减少非结构化p 2 p 网络的流量大这 一问题还是很有价值的”“”1 。 本章介绍g n u t e l l a 网络下现有的搜索方法。 3 1g n u t e l l a 网络模型 g n u t e l l a 是一种典型的p 2 p 网络模型结构，本节着重论述了g n u t e l l a 网络模型 的体系结构、工作原理和它的拓扑特征。“” 3 1 1g n u t e l l a 网络协议体系结构 描述符描述 p i n g用于在g n u t e l l a 网络中主动发现对等机。一个收到p i n g 描述符的对等 机会向发送方响应一个或多个p o n g 描述符。 p o n g用于对p i n g 响应的描述符。它包括一个相连的g n u t e l l a 对等机的地址 和有关该节点能提供给网络共享的信息。 q u e r y是搜索g n u t e l l a 分布式网络的主要机制，一个收到q u e r y 描述符的对 等机，如果其本地共享信息与q u e r y 搜索的内容匹配，将会响应一个 q u e r y h it 给q u e r y 的发起者。 q u e r y h i t用于对q u e r y 响应的描述符。它包括匹配q u e r y 搜索数据的对等机i p 地址及端口号、传输速度及结果集、对等机标识等。 p u s h 提供一种机制允许一台处于防火墙后的对等机向g n u t e l l a 网络提供 基于文件的数据。 表3 1g n u t e ll a 协议通信描述符 在g n u t e l l a 分布式对等网络模型中，每一个联网计算机既是客户机同时又 河海大学硕士研究生论文第三章现有的资源查找方法 是服务器，因此被称为对等机( s e r v e n t ) ，通过与相邻对等机之间的连接遍历 整个网络。g n u t e t i a 协议定义了网络中这些对等机间通信的方式，是工作于t