（计算机应用技术专业论文）p2p网络资源搜索策略研究及方案改进.pdf

兰州大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 摘要 随着计算机处理能力的不断增强和网络通信技术的迅速发展，越来越多的计 算机连接到了i n t e r n e t 上，在传统的客户机服务器管理模式中，服务器端承受着 巨大的负载，而客户端基本上是闲置的，在这种情况下，大量的网络资源没有得 到充分而有效的利用，为此人们提出了p 2 p 网络模型。 在p 2 p 网络中，数据的传递直接在对等节点之间进行，但随着p 2 p 网络规 模的不断扩大，数据的存储管理和快速搜索成为研究的热点。本文对p 2 p 网络各 种体系结构进行了深入研究，对无结构化和结构化p 2 p 网络资源搜索策略进行了 分析，针对结构化p 2 p 网络搜索技术c h o r d 算法存在的几个不足，提出了相应 的改进方案，并通过仿真实验对方案进行了性能测试和分析。主要创新点是： ( 1 ) 针对c h o r d 算法中存在着大量的路由冗余，通过在f i n g e r 表未覆盖的另 一半区域均匀的选取r ( n ) 多个表项添加到原路由表的尾部，从而去掉冗余。 为减少资源重复查询次数，为每个节点添加了一张记录表，用来记录一段时间内 经常被搜索的资源。 ( 2 ) 运用网络延迟和节点i d 来构建f i n g e r 表，f i n g e r 表中每个表项的后继 节点都是离其较近的节点。每个节点根据和参考点之间的延迟确定所属的分组， 属同一分组的节点构成一般c h o r d 环的形式，组之间由超级节点相连。 ( 3 ) 为实现资源就近查询，每个节点同时维护两个方向的指针，当在单独的 c h o r d 环上进行资源搜索时，源节点按照和目的节点之间的逻辑距离判断查询将 沿那个方向进行。 关键词：p 2 p ，c h o r d ，路由冗余，网络延迟，就近查询 兰州大学硕士毕业论文 p 2 p 网络资源搜索策略研究及方案改进 a b s t r a c t w it ht h ed e v e l o p m e n to ft h ep r o c e s s o rs p e e do fc o m p u t e ra n dn e t w o r k c o m m u n i c a t i o nt e c h n o l o g y ，m o r ea n dm o r ec o m p u t e r sh a v eb e e nc o n n e c t e dt o t h ei n t e r n e t i nt h et r a d i t i o n a lc 1 l e n t s e r v e rn e t w o r ka r c h i t e c t u r e t h e s e r v e rw a su n d e rah u g el o a dw h il et h ec li e n tw a sl e f tu n u s e do nt h e w h o l e a sr e s u l t ，a a r g en u m b e ro fc o m p u t i n gr e s o u r c e si nt h en e t w o r k w e r en o tu s e de f f i c i e n t l y ，s op 2 pn e t w o r km o d e lc a m ei n t ob e i n g i nt h ep 2 pn e t w o r k ，d a t at r a n s f e r e dd i r e c t l yb e t w e e nn o d e s w it ht h e g r o w t ho fp 2 pn e t w o r k ，d a t as t o r a g ea n ds e a r c hh a sb e c o m eah o tr e s e a r c h t h et e x ts t u d i e da l lk i n d so fa r c h i t e c t u r e sb a s e do np 2 pn e t w o r kd e e p l y a n da n a l y s is e dt h es e a r c hs t r a t e g i e sf o ru n s t r u c t u r e da n ds t r u c t u r e dp 2 p n e t w o r k it p r o p o s e dt h ec o r r e s p o n d i n gp r o g r a m so fi m p r o v e m e n tf o rt h e s h o r t a g e so fc h o r ds e a r c h i n ga l g o r i t h mb a s e do ns t r u c t u r e dp 2 pn e t w o r k i t t e s t e da n da n a l y s i s e dt h ep e r f o r m a n c eo ft h ep r o g r a m st h r o u g he x p e r i m e n t a sf o l l o w sw e r et h em a i ni n n o v a t i o n s ： ( 1 ) f o rt h ee x i s t e n c eo fal a r g en u m b e ro fr o u t i n gr e d u n d a n c yi nc h o r d a l g o r i t h m ，t h r o u g hs e l e c t i n gr ( n ) a tt h ef i n g e rt a b l eo fn oc o v e r i n g a n o t h e rh a l fo ft h er e g i o na n da d d e dt h e mt ot h et a i l o ft h eo r i g i n a l r o u ti n gt a bl et or e m o v et h er e d u n d a n c y ，i no r d e rt or e d u c et h en u m b e ro f r e p e a t i n gi n q u i r y i n gr e s o u r c e ，i ta d d e dt oar e c o r df o re a c hn o d et or e c o r d s e a r c h i n gr e s o u r c ei nap e r i o do ft i m e ( 2 ) t h et e x tu s e dn e t w o r kl a t e n c ya n dn o d ei dt ob u ii daf i n g e rt a b l e i t m a d et h es u c c e s s o rn o d eo ft h ef i n g e rt a b l ee n t r yf o re a c hn o d ew a st h e n e a r e s tt ot h ep h y s i c a ld i s t a n c e e a c hn o d ed e t e r m i n e do w nd i v i s i o ni n a c c o r d a n c ew i t ht h er e l a t i v ed e l a yb e t w e e nt h er e f e r e n c en o d e t h en o d e s w i t h i nt h es a m ed i v i s i o nc o n s t r u c t e di n t oc h o r dr i n g ，t h e yw e r ei i n k e db y t h es u p e r n o d eb e t w e e nt h ed i v i s i o n s ( 3 ) e a c hn o d em a i n t a i n e dt w op o i n t e r so fd i f f e r e n td i r e c t i o na tt h e s a m et i m e ，i tw a sd e t e r m i n e dt h ei n q u i r yd i r e c t i o ni na c c o r d a n c ew i t ht h e l o g i cd i s t a n c eb e t w e e nt h es o u r c en o d ea n dd e s t i n a t i o nn o d ew h e ns e a r c h i n g r e s o u r c e si nas e p a r a t ec h o r dr i n g k e y w o r d s ：p 2 p ，c h o r d ，r o u t er e d u n d a n c y ，n e t w o r kd e l a y ，n e a r b yi n q u i r y i l 兰州大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 图表目录 图2 - 1p 2 p 网络在协议栈中的位置7 图2 2c s 模式与p 2 p 网络模式比较9 图2 - 3 中心式p 2 p 网络l o 图2 - 4n a p s t e r 网络拓扑结构及查询机制1 0 图2 5 混合式p 2 p 网络模型1 1 图2 - 6 无结构化p 2 p 网络。1 2 图2 7g n u t e l l a 网络拓扑结构及查询机制1 2 图2 - 8d h t 基本结构示意图1 3 图3 1d h t 抽象层与应用程序的关系。1 6 图3 2 洪泛查询过程1 9 图3 - 3 漫步查询过程( k _ 3 ) 。2 0 图3 - 4 基于超级结点的搜索模型2 1 图3 5 逆向路径缓存2 2 图3 6c a n 坐标空间的区域划分2 4 图3 7c a n 的查找路由算法示意图2 5 图3 8p a s t r y 路由消息转发过程2 6 图3 9c h o r d 中节点加入过程3 0 图3 10c h o r d 中节点离开过程3 0 图3 1 1c h o r d 数据结构图3 1 图3 1 2 度数和直径之间的渐进曲线关系3 3 图4 1 一般c h o r d 查找过程。3 4 图4 2 直线c h o r d 环3 5 图4 3 改进后c h o r d 算法中节点n 存储的资源3 7 图4 - 4 改进后f i n g e r 表。3 8 图4 5 加了记录表的c h o r d 环。3 8 图4 6 网络延迟的分组3 9 图4 7 网络延迟分组的坐标映射4 0 图4 8 一般c h o r d 系统中节点n i 的指针表4 l 图4 - 9c h o r d 就近查询系统中节点n i 的指针表4 l 图5 1b r i t e 用户设置界面4 2 图5 - 2 平均查询延时比较4 4 图5 - 3 平均查询路径长度比较4 4 图5 - 4 随机分布的c h o r d 系统和基于延迟的c h o r d 系统4 5 图5 - 5 传统c h o r d 与基于延迟c h o r d 就近查询4 6 图5 - 6 随机分布的传统c h o r d 与基于延迟c h o r d 就近查询。4 7 v 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下 独立进行研究所取得的成果。学位论文中凡引用他人已经发表或 未发表的成果、数据、观点等，均己明确注明出处。除文中已经 注明引用的内容外，不包含任何其他个人或集体己经发表或撰写 过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：让日 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。保密论文在 解密后应遵守此规定。 论文作者虢驻新虢趣日期：与丛桫 兰州大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 1 1 论文背景 第1 章引言 随着计算机网络技术的飞速发展，互联网成了绝大多数用户获取信息资源的 重要场所，网上的信息内容呈爆炸式增长，获取信息的速度和便捷程度前所未有。 而这些大量用户的眼球和消费能力成了网络商家们想要紧紧抓住的市场。于是， 整合了各种信息资源的公司、企业就迅速出现在互联网上，给普通网络用户提供 各种各样的便捷式服务。这样的公司、企业、少数个人渐渐转化为网络上单一的 信息制造和发布者的角色；而普通用户则逐渐演变成单一的信息消费者的角色。 随之网络中的各种资源随着网络规模的不断扩大为传统网络应用带来了新 一轮的挑战。在一个网络环境中，c p u 、存储能力、带宽、缓存、文件、服务等 都统称为网络环境中的资源。网络资源的组织、寻获、管理、推荐、使用等成为 信息检索新的研究内容，传统网络计算模式因存在如集中控制、集中组织等潜在 的缺陷，己不能满足人们的需要，它们的计算模式发生了翻天覆地的变化，从传 统的客户机月艮务器( c l i e n t s e r v e r ，c s ) 模式向p 2 p 网络( p e e r t o p e e r ，p 2 p ) 模式 迅速转变【1 i 。 近年来，虽然w e b 应用等c s 传统结构的网络服务不断被广泛普及，如原 来的互联网应用，如f t p 、t e l n e t 、e m a i l 等，仍然被广大用户使用，但其流量 限制已成为网络发展的一个主要瓶颈，因此基于p 2 p 的网络技术得到广泛应用， 它是一个非常有潜力且具有广泛应用领域的技术。p 2 p 网络，既是一种信息资源 传递交换的模式，也是一种网络结构的思想，它与c s 结构的一个本质区别是： 在整个p 2 p 网络中，信息资源是在p 2 p 实体之间进行对称的双向传输和交换， 每一个节点( p e e r ，p 2 p 实体) 同时具有资源消费者、资源提供者等两方面的功能， 拥有p 2 p 的权利和义务。与传统的网络服务类型相比，p 2 p 技术弱化了服务器的 作用，甚至取消服务器。它直接带来的好处首先是经济性：不需要功能强大的服 务器进行集中的运算，而是把闲置的运算能力加以利用；另一个好处就是社区性： 可以组建一个专门的环境，在这个环境内不仅可以共享资源、共同合作，而且安 全性好、效率高。 兰州大学硕士毕业论文 p 2 p 网络资源搜索策略研究及方案改进 1 2p 2 p 技术的应用 随着p 2 p 技术的深入发展，p 2 p 技术己被广泛地应用到军事，商业和通信等 诸多领域。目前主要应用在文件共享、协同工作、即时通讯、网络游戏、信息检 索、分布式计算等方面，其中在文件共享应用方面最为广、泛【2 1 1 3 】【4 1 。 1 文件共享 共享文件包括音频、视频、图像等多种文件形式。n a p s t e r ，g n u t e l l a 以及 f r e e n e t 是3 种典型的文件共享系统。在传统的p 2 p 方式中，要实现文件交换需 要服务器的大力参与，通过将文件上传到某个特定的网站，用户再到某个网站搜 索需要的文件，然后下载。通过p 2 p 不是从其它网站的服务器搜索与下载资源， 而是从任何一个在线网友的机器里直接下载，当然其它网站的服务器也可以看作 是一个p 2 p 节点，这样真正让个人电脑实现了与服务器同等的地位。 2 协同工作 在p 2 p 出现之前，协同工作的任务通常由诸如l o t u sn o t e s 或者m s e x c h a n g e 等来实现，但是无论采用哪种服务器软件，都会产生极大的计算负担，造成昂贵 的成本支出，而且并不z 月, 匕- 一z z k e t 好地完成企业与合作伙伴、客户、供应商之间的信息 交流。而p 2 p 技术使互联网一t - 任意两台p c 都可建立直接的通讯联系，不再需要 中心服务器，降低了对服务器存储以及性能的要求，也降低了对网络吞吐量和快 速反应的要求，从而大大节约了成本，使低成本的协同工作成为可能，最终帮助 企业和关键客户以及合作伙伴之间建立起一种安全可靠的网上工作联系方式。 3 即时通讯 即时通讯，其实指的就是诸如i c q 、o l c q 、p o p o 等被称为在线聊天的软 件。从某种意义上说，由于版权的限制，即时通讯应用将超过文件共享应用，成 为p 2 p 的第一大应用。与b b s 聊天室比较，p 2 p 的即时通讯软件不仅可以随时 知晓对方在线与否，而且交流双方的通讯完全是点对点进行，不再依赖服务器的 性能和网络带宽。 4 网络游戏 目前很多网络游戏也是基于p 2 p 技术的，采用p 2 p 技术建立起来的分布式 小组服务模型，配以动态分配的技术，每个服务器的承载人数在数量级上超过传 统的服务器模式，这大大提高了目前多人在线交互游戏的性能；同时每个游戏用 户成为一个p 2 p 节点，各个节点可以进行大量的点对点通讯，从而减少服务器的 2 兰州大学硕士毕业论文 p 2 p 网络资源搜索策略研究及方案改进 通讯任务，明显提高了网络服务性能。 5 信息检索 现在人们在网络中信息检索的主要工具是搜索引擎，目前的搜索引擎如 g o o g l e 、天网等都是集中式的搜索引擎。这种搜索模式往往由一个机群在互联网 上盲目读取信息，然后按照某种算法根据关键字将信息保存在一个海量数据库 内，当用户提交搜索请求的时候，实际上是在海量数据库内部进行搜索。这种机 制虽然能尽快获得搜索结果，但不能保证搜索范围的深度和结果的时效性。即使 是g o o g l e 这个目前最出色的全中文搜索引擎只能搜索到2 0 3 0 的网络资源。 p 2 p 网络模式中节点之间的互联关系使得搜索可以直接地、实时地进行。 6 分布式计算 分布式计算是利用整个网络上的计算机的闲置中央处理器、内存以及磁盘空 间等，进行大规模的运算【5 】。p 2 p 计算的优势在于每个p 2 p 节点不再只是单纯的 接收计算任务，它还可以根据自己的情况再搜索其他空闲节点，把收到的任务分 发下去，然后中间结果层层上传，最后到达任务分发节点。p 2 p 节点之间还可以直 接交换中间结果，协作计算。按照这种方式进行，可以合理整合闲散的计算能力 和资源，大大提升了总体计算能力，获得非常可观的计算性能和价格比。 1 3 国内外研究与应用现状 在过去的几年中，p 2 p 模型由于其高度动态性、分散性、强容错性以及低成 本性【6 1 1 7 1 成为了在i n t e r n e t 规模内进行资源共享的一个极具吸引力的模型。所有 p 2 p 领域的研究都遵循4 条线索：搜索、存储、安全和应用。 国内学术机构主要有少数几所大学负责研发，比较著名的有：( 1 ) 北京大学 网络实验室开发的集搜索、下载、发布、交易为一体的对等计算文件共享系统 m a z e ：( 2 ) 清华大学自主开发的p 2 p 存储服务系统g r a n a r y ，是一个广域网上的 分布式存储系统；( 3 ) 华中科技大学设计研发的对等流媒体直播系统a n y s e e ，是 一个基于对等网络的流媒体直播系统；( 4 ) 上海交通大学设计的p 2 p 片段存储系 统等。 国内企业在p 2 p 的应用领域研究一直与世界同步，开发了众多使用广泛的 p 2 p 产品。这些产品主要集中在文件共享与下载，网络流媒体电视等方面。 国外开展p 2 p 技术研究的组织和机构主要包括大学、1 1 r 公司和国际学术团 3 兰州大学硕士毕业论文 p 2 p 网络资源搜索策略研究及方案改进 体。大学侧重于p 2 p 领域的理论研究，高新技术公司侧重于p 2 p 技术的应用开发 和产品化，而国际学术团体主要从事p 2 p 标准化工作。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u cb e r k e l e y ，m i t 和a t & t 互联网研究中。0 , ( a c i r i ) 。在u cb e r k e l e y 大学，t a p e s t r y 项目和 o c e a n s t o r e 项目与p 2 p 技术直接相关。t a p e s t r y 提供了一个分布式容错查找和路 由基础平台，在此平台基础之上，可开发各种p 2 p 应用，o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的p 2 p 平台。它是一个适合于全球数据存储的p 2 p 应用系 统。在m i t ，开展了多个与p 2 p 相关的研究项目：c h o r d ，g r i d 和r o n 。c h o r d 项目的目标是提供一个适合于p 2 p 环境的分布式资源发现服务，它通过使用分布 式h a s h 路由表技术使查找指定对象只需要维护l o g n 长度的路由表。a t & t a c i r i 中心的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 s ，c a n ) 项目独特之处在于采用多维标 识符空间来实现分布式h a s h 算法。 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p e e r - t o p e e rw o r k i n g g r o u p ，p 2 p w g ) 、全球网格论j ：云：( g l o b a lg r i df o r u m ，g g f ) 。p 2 p 工作组成立的 主要目的是希望加速p 2 p 计算基础设施的建立和推进p 2 p 标准化工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司，s u n 公司和i n t e l 公司投入较大，但目前均无成熟产品和技术方案，其研究也仅处于探索阶段。除 了大学、学术团体和i t 公司积极参与p 2 p 研究之外，许多个人和开源爱好者也 积极开展针对p 2 p 的研究工作，其中较为知名的是f r e e n e t 系统和g n u t e l l a 系统。 随着规模的扩大和应用的增长，p 2 p 系统的流量在网络总流量中所占的比例 也急剧增长。根据威斯康星大学的统计，p 2 p 应用所占的网络流量在2 0 0 1 年就达 到总流量的3 0 ，根据互联网数据分析合作协会的统计，2 0 0 2 年各种p 2 p 系统 所占的总流量己超过美国城市骨干网的4 0 1 8 1 。 1 4 论文主要研究内容 p 2 p 网络技术的核心是资源搜索，搜索策略的优劣直接影响到p 2 p 系统的性 能。目前存在的p 2 p 叠加网络拓扑的构建大多数没有考虑底层物理网络的实际情 况，产生了叠加网络拓扑和底层物理网络不匹配的问题，导致了p 2 p 节点定位资 源的延迟和开销增加，严重影响了系统的效率。如无结构化p 2 p 网络g n u t e l l a ， 4 兰州大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 采用的是洪泛机制，容易造成网络流量增大，导致网络拥塞。而基于分布式哈希 表( d h t ) i 拘结构化p 2 p 覆盖网络，如c h o r d 则即可以保证搜索效率，也可以控制 消息数量。由于它查找的可确定性、简单性和分布性等优点正越来越成为研究和 应用的焦点，但由于关键字的唯一性，仍存在许多问题，诸如路由冗余问题、容 错性问题、状态一效率折衷性问题、异构性问题、不支持模糊查找等，而且在可 扩展性方面仍然存在着严重的不足，需要进一步改进和完善。 本文通过对p 2 p 网络资源搜索策略的深入研究，理论联系实际，综合考虑现 实环境中存在的问题，分别对无结构化和结构化p 2 p 网络搜索技术进行了分析和 讨论，针对基于d h t 的结构化网络资源搜索技术一c h o r d 算法存在的不足，提 出了相应的改进方案，并通过仿真实验验证了改进方案的有效性。该研究有助于 解决当前p 2 p 网络资源定位机制的不足，促进网络资源共享的发展。 1 5 论文结构 本文一共分为六章：第一章为引言，主要介绍论文研究的领域、背景、现状、 目的以及研究的内容和重大意义。 第二章是理论基础，对p 2 p 技术的概念，特征、发展，常见模型和体系结构 等进行了理论介绍和简要分析。 第三章对现有的p 2 p 网络资源搜索算法分别进行了归纳和分析，主要介绍了 无结构化和结构化两大类别的搜索算法。 第四章签于当前各种搜索算法本身所存在的问题，在基于d h t 的结构化p 2 p 网络开放环境下，针对c h o r d 算法存在的几种不足，提出了相应的改进方案。 第五章以网络模拟器b r i t e 作为试验平台，用来生成仿真的拓扑结构。对上述 改进算法进行了仿真实验和性能分析。 第六章结束语。对本文工作的总结，以及对下一步工作的展望。 5 兰州大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 2 1p 2 p 的定义 第2 章p 2 p 网络理论基础 p 2 p 系统从产生到现在，无论在学术界还是在工业界都没有一个统一的定 义，但在其发展过程中，我们可以理解下面几个常用定义： s c h o l l m e i e r 对p 2 p 系统的定义如下【9 】：如果一个系统的参与者共享了自己的 硬件资源，这些共享的资源是系统提供服务必需的，且可以被其他参与者不用通 过中介而直接访问；系统的参与者既是资源的提供者也是资源的请求者，则此系 统可以认为是p 2 p 系统。 g r a h a m 通过描述p 2 p 节点所需的三个必备条件来定义p 2 p 系绀1 0 l ： ( 1 ) 具备服务器的能力；( 2 ) 拥有独立于d n s 的寻址系统；( 3 ) 能够处理可变的 连接。 a b e r e r 通过描述p 2 p 系统的特征来定义p 2 p 系统1 。这些特征如下：( 1 ) 没 有集中的协调中心；( 2 ) 没有集中的数据库；( 3 ) 节点没有整个系统的全局视图； ( 4 ) 全局的行为依靠局部的相互作用；( 5 ) 所有存在的数据和服务都是可访问的； ( 6 ) p 2 p 节点是自治的；( 7 ) p 2 p 节点及其相互之间的连接都是不可靠的。 s h i r k e y 将p 2 p 系统定义为一种利用互联网边缘的各种可用资源( 存储空间、 计算能力、媒体能力、人力资源等) 的应用程序【1 2 1 。因为访问这些分散的边缘资 源意味着要在连接不稳定和i p 地址不可预见的环境下工作，所以p 2 p 节点必须 能够独立于d n s 系统且拥有独立于集中服务器的完全的自治。 惠普实验室( h e w l e t t p a c k a r dl a b ) 的m i l o j i e i e 将p 2 p 系统定义为一类采取 分布式方式利用分布式资源完成关键功能的系统【1 3 】。分布式资源包括计算能力、 存储空间、数据、网络带宽以及各种存在的可用资源。关键功能可以是分布式计 算、数据内容共享、通信与协作或平台服务。分布式的方式可以应用到算法、数 据、元数据或所有方面，但并不排除在系统或应用程序的某些部分保留集中式的 方式。典型的p 2 p 系统主要应用在互联网边缘或a dh o c 网络环境中。 目前的p 2 p 网络常被认为是一种应用，因此，它和别的应用一样，处于协议 栈的应用层，它在网络协议栈中的位置如图2 1 所示。由于p 2 p 网络在原有的网 6 兰卅l 大学硕士毕业论文p 2 p 网络资源搜索策略研究及方案改进 络之上，在节点间再构建了一个新的网络关系，因此，p 2 p 网络可以看作一种覆 盖网，并可以利用p 2 p 网络建立新的应用。 2 2p 2 p 的特征 图2 1p 2 p 网络在协议栈中的位置 p 2 p 网络具有以下特征： 1 以网络用户为主体。绝大多数p 2 p 网络以服务每一个网络用户为目的， 尽力为每一个用户提供相同或近似的服务。每个用户自愿地选择加入p 2 p 网络， 并在其中拥有同等或近似同等重要的地位。 2 p 2 p 的每个用户都可以充当双重角色，既是资源的提供者，又是资源的 消费者。每个用户可以方便地共享自身拥有的资源，也可以快捷地从其他用户那 里获取新的资源。资源在用户之间双向对称地流动，实现交换双方共同获利。 3 p 2 p 用户具有异构性。具有不同资源数量、不同主机性能、甚至不同目 的的网络用户均可以加入p 2 p 网络。由于一些自身的原因，p 2 p 网络中的一些用 户拥有少量、甚至没有可共享的资源，而有些用户则拥有大量的可共享信息；p 2 p 用户所使用的主机也有性能上的差别，可以是手机、p d a 、家用电脑、笔记本、 商用计算机、工作站、小型计算机、甚至中大型计算机，在主机的存储空间、c p u 处理能力等方面均有较大差别；用户接入互联网的带宽也有所差别，可以是拨号 接入、a d s l 、c a b l e m o d e m 、以太网等有线接入，也可以是g p r s 、w l a n 等无 7 - 磁 - 缮 - 钉 - 象， 一 觚 一型 。一i!-生竺型| | | i。o。k 兰州人学硕i ：毕业论文p 2 p 网络资源搜索策略研究及方案改进 线接入；用户加入p 2 p 网络的目的也可能有所不同，由于互联网的开放性，有些 用户倾向于与他人之间的合作，而少数用户可能带有传播病毒、攻击他人等破坏 网络秩序的恶意。 4 p 2 p 用户之间是松耦合关系。用户在p 2 p 网络中行为自由，系统通常不 会强制性要求用户之间进行合作，用户可以根据自己的意愿自由地选择在任意时 刻离开或加入p 2 p 网络。因此，p 2 p 网络需要有很强的容错能力来处理这些随时 可能发生的状况，这就要求p 2 p 用户之间应该是一种松耦合的关系。 5 大多数p 2 p 网络尽量采用去中心化的分布式结构。p 2 p 网络以用户的p 2 p 交换信息和协同合作为特征，当某些用户或某部分网络因为某种不可预知的原因 失效后，其他用户希望仍然能够保持原有的通信和合作。而集中式的中心化结构 当中心节点失效后，整个网络就会无法正常运转。而且中心化结构的可扩展性也 较差，当网络规模较大时，就会遇到中心服务器的性能瓶颈问题。因此，去中心 化的分布式结构被大多数p 2 p 网络所采用。 2 3p 2 p 的发展历史 传统的互联网应用模式是基于c s 的。随着个人计算机数目的增加，服务器 的负载过重，难以满足客户机的服务请求；同时个人计算机的性能增强，已经具 备小型服务器的能力，但在传统的应用模式下只能处于客户机地位，导致可用资 源的闲置。这些空闲资源的潜力是巨大的，假设个人计算机数目为1 亿台，每台 个人计算机只要提供1 0 m b 的空闲存储空间，用于存储的总空闲资源就能达到 1 0 0 0 t b 。一方面，处在网络中心的服务器不堪重负：而另一方面，网络边缘却存 在大量的空闲资源，网络负载极不平衡。 网络带宽的增长使得个人计算机之间具备直接通信的能力，用户也希望能够 不通过服务器直接进行资源的共享和交换。由此，采用新型应用模式的p 2 p 系统 产生了。从网络的角度看，p 2 p 不是一个新鲜的概念，p 2 p 是互联网整体架构的 基础。在十几年之前，所有的互联网上的系统都同时具有服务器和客户机的功能。 然而，由于受早期计算机性能、资源等因素的限制，随着互联网规模的迅速扩大，大 多数连接到互联网上的普通用户并没有能力提供网络服务，从而逐步形成了以少 数服务器为中心的c s 架构。也正是在这种架构下，对客户机的资源要求非常少， 8 兰州人学硕上毕业论文p 2 p 网络资源搜索策略研究及方案改进 因而可以使用户以非常低廉的成本方便地连接互联网，推动了互联网的快速普 及。但是，随着互联网对人们生活的联系日益紧密和深入，人们需要更直接，更广 泛的信息交流。在此背景下，p 2 p 技术再一次受到了广泛的关注。 n a p s t e r 软件的出现正是唤醒了深藏在互联网背后的p 2 p 联网。n a p s t e r 软件 提供服务允许音乐迷们交流文件。后来的g n u t e l l a 软件更是体现了p 2 p 所包含的 “非中心化”的理念，是一个p 2 p 文件共享系统，在g n u t e l l a 分布式p 2 p 网络模型 中，每个联网计算机在功能上既是客户机同时又是服务器，所以被称为p 2 p 机。 目前最热衷于p 2 p 技术的是网络游戏、娱乐信息产品的开发商和实时通信软 件供应商。从这个角度看，p 2 p 将进一步提高网络的娱乐价值和交际价值。 早期的i n t e m e t 的节点之间的关系就是一种p 2 p 网络，一些早期的分布式系 统，如u u c p 和交换网络，其节点间的关系也是平等的。现在的p 2 p 网络主要 是相对于w e b 服务所采用的流行的c s 模式而言，两者结构差别如图2 2 所示。 图2 - 2c $ 模式与p 2 p 网络模式比较 由此可以看到p 2 p 应用模式与c s 应用模式相比优势体现在：第一，p 2 p 利 用空闲资源降低了资源共享的开销；第二，p 2 p 极小化或无需集中控制提高了共 享资源节点的自治性和系统的鲁棒性；第三，p 2 p 可以分散资源，平衡网络负载。 2 4p 2 p 现有的体系结构 从1 9 9 9 年n a p s t e r 出现至今，p 2 p 网络应用经历了长足的发展，期间出现了 很多类型的p 2 p 应用，如g n u t e l l a 、k a z a a 、b i t t o r r e n t 等文件共享系统；i c q 、 q q 、m s n 等即时通讯系统；s e t i h o m e 等协同合作系统。综观现有的体系结 构，主要可分为以下几类： 2 4 1 中心式 9 兰州火学硕一i - 毕业论文 p 2 p 网络资源搜索策略研究及方案改进 中心式p 2 p 网络依靠中心的索引服务器提供对共享资源的索引服务，其基本 结构如图2 3 所示。节点加入p 2 p 网络的时候，先向中心索引服务器注册自己的 共享资源信息( 即索引) 。想要获取共享资源的节点则向中心索引服务器发出请 求，中心索引服务器检索索引数据，并将匹配的索引信息返回给请求节点。请求 节点收到返回的索引信息后，与索引指出的服务节点联系。 图2 - 3 中心式p 2 p 网络 中心式p 2 p 应用以n a p s t e r 为典型代表，包括b i t t r r e n t 文件下载应用、m s n 、 q q 等即时通讯系统。如图2 4 所示，所有加入n a p s t e r 系统的用户必须在中心 服务器上登记提供共享的音乐文件信息：当用户需要寻找某一特定音乐文件时， 登陆中心服务器进行查询，根据中心服务器的查询结果，信息连接相应的p 2 p 用 户进行下载。因此，中心服务器在n a p s t e r 系统充当资源管理和查询服务的角色。 图2 _ 4n a p s t e r 网络拓扑结构及查询机制 可以看出，中心式p 2 p 系统设计简单、易于实现和进行系统管理；但中心服 1 0 兰州人学硕士毕业论文 p 2 p 网络资源搜索策略研究及方案改进 务器成为整个系统的性能瓶颈，而且还存在单节点失效、可扩展性差等问题。 2 4 2 混合式 在混合式p 2 p 网络里面，节点被分成了两类：超级节点和普通节点。如图 2 5 所示，超级节点由具有良好性能及网络带宽的计算机担任，而普通节点与超 级节点相联接。通常超级节点之间形成纯粹的p 2 p 网络，而普通节点就像树叶一 样围绕在作为主干的超级节点周围。普通节点加入p 2 p 网络的时候，将选择一个 超级节点作为h u b 节点，并向超级节点注册自己的共享资源信息，而普通节点 需要查找共享资源时，就向h u b 节点提交请求，由h u b 节点负责查找。 图2 5 混合式p 2 p 网络模型 混合式p 2 p 网络实际上是在纯p 2 p 网络基础上引入了一定程度的中心化处 理，由于引入了局部中心的概念，因此，混合式p 2 p 网络也在一定程度上存在中 心点问题，作为局部中心的超级节点的不稳定将给树叶节点带来影响；另外的问 题是普通节点需要定期更新在h u b 节点上的共享资源信息，而这些更新的开销 也是不可忽视的。 2 4 3 无结构化分布式 无结构化分布式p 2 p 系统的主要特征是采用去中心化的全分布式资源索引 管理结构和通信模式，而且用户和资源在系统中随机分布和组织。因此对共享资 源的查找只能通过邻居转交的方式进行，基本结构如图2 6 所示。每个节点都需 要维护一定数量的邻居节点信息，当需要查找共享资源时，则给邻居发送查询消 息。而每个收到查询消息的节点首先检索自己的共享内容，察看是否有匹配的， 如果存在匹配的资源，则返回结果；如果没有匹配的资源，则将查询消息转发给 自己的邻居，如此重复，直到找到所需的资源。主要的系统应用有g n u t e l l a 、 f r e e n e t 、f a s t t r a e k 、k a z a a 等。 1 1 兰州人学硕： ：毕业论文p 2 p 网络资源搜索策略研究及方案改进 p c e r 图2 - 6 无结构化p 2 p 网络 如在g n u t e l l a 网络中一台用户主机是通过访问某特殊站点提供的主机缓存 服务机制获得已有的活动主机的地址，并与之连接后接入g n u t e l l a 网络。每一个 用户节点只记录与之相邻的节点信息，并且共享资源及其元数据信息只存放在本 地节点上，节点之间无法知道彼此共享资源的信息，只能采用扩散的方式查询资 源。如图2 7 所示，当用户需要查找某种特定资源时，就将查找信息转发给部分 或所有相邻节点，再由相邻节点继续转发，直到查找成功或者到达转发次数上限。 图2 - 7g n u t e l l a 网络拓扑结构及查询机制 无结构化分布式p 2 p 系统由于采用了去中心化结构，增强了系统的可扩展性 和健壮性：但因为资源的组织无序，因此，其查找是无序的，通常开销会很大。 1 2 兰州人学硕j j 毕业论文 p 2 p 网络资源搜索策略研究及方案改迸 2 4 4 结构化分布式 由于无结构化p 2 p 网络存在搜索随机性，在资源定位方面存在严重不足，人 们把研究的重点放在了如何有效的查找信g _ b 。最新的研究成果都是基于d h t 的分布式路由查找算法，这些算法避免了类似n a p s t e r 的中央服务器，也不像 o n u t e l l a 那样基于洪泛进行查找，而是通过分布式哈希函数将输入的关键字唯 一映射到某个节点上，然后通过某些路由算法同该节点建立连接。基于d h t 的 p 2 p 网络称为结构化p 2 p 网络，d h t 基本结构如图2 8 所示。 a p p l l c a t l o e v e n tn e t l f l e c t i o n n e t w o r ks t o r a g eo t h e ra p p l i c a t i o n l a v e r ok d h 。i d h t l a v e r r n e t w o r k t c p f l p l a v e r 图2 - 8d h t 基本结构示意图 在这些结构化的系统中，叠加拓扑被严格控制，文件或者指针存放在确定的 位置上，系统提供从文件标识到存放该文件的节点标识的映射服务，然后查询请 求路由到该节点，通过该方法系统提供了一个可扩展的方案，实现了文件的精确 匹配查询。这种结构化的资源组织方式便于资源查找，减小了开销。同时，出于 冗余度以及延时的考虑，大部分基于d b t 的p 2 p 系统总是在节点的虚拟标识与 关键字最接近的节点上