（信号与信息处理专业论文）结构化对等网络资源搜索的研究.pdf

- 删i i i i ii ii ii i iii ii i ii ii y 1819 2 2 9 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：一越魁翌 本人承担一切相关责任。 日期：三丝生：墨：2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在2 年解密后适用本授权书。非保密论 文注释：本学 。 本人签名 导师签名。玩l ， l 一 、 适用本授权书。 日期：一趔：至：兰 日期： k z 。：距 第j i 页 辱 一 摘要 结构化对等网络资源搜索的研究 摘要 对等网络( p 2 p ) 的出现是对传统c s 网络架构的一次进化，由于 p 2 p 中的每个节点都能共享大量数据，因此基于p 2 p 架构的网络随着 网络扩展信息量迅速扩大，信息资源十分丰富。 目前，p 2 p 系统一般分为非结构化系统和结构化系统，非结构化 系统由于维持松散的叠加网络使其更能适应高度动态的p 2 p 网络，但 是由于其转发查询时随机选择节点，查询效率不高，使用泛洪的方法 又造成系统可扩展性差，且不能保证查找的成功。结构化系统使用可 扩展的方法能保证查找的成功，但由于要维持严格控制的叠加拓扑， 因此对p 2 p 网络中大量节点的动态变化适应性较差，更重要的是由于 分布式哈希表的使用使其只支持精确查找。大量的共享资源使得p 2 p 系统吸引了大量的用户，但困难的是如何在大量的共享资源中寻找用 户想要的资源。如何有效地获取有用信息，是系统能否大规模应用的 关键之一，对于p 2 p 搜索机制的研究成为一个非常重要的课题。 由于网络资源具有多样性和复杂性，为了准确表述用户对资源的 要求，也为了使系统返回给用户的结果能更好的满足用户需求，需要 用多个属性从不同角度描述资源。本文在分布式哈希表( d h t ) 思想的 基础上，设计并实现了一个多属性发布系统。利用d h t 可以将单个键 映射到网络中的节点的特点，在发布资源时，多属性发布系统将资源 的各个属性分别发布到特定的节点；在搜索资源时，用户根据实际需 要，指定一个或多个资源属性值作为搜索条件，系统根据用户指定的 各个属性搜索条件，将搜索请求路由到存放各个属性的节点，并将多 个属性值对应的索引求交集以使得结果满足用户的所有条件。从而克 服了结构化对等网络只支持精确查找的弊端。 接着，本文详细分析了几个可以对系统进行优化的关键技术：向 量空间模型，t f i d f 文档划分，b l o o mf il t e r 压缩技术。并分析了如 何利用这些技术解决文本文件的搜索问题，从而使系统的应用范围得 到进一步扩展。 最后，作者对前期工作做出了总结并展望了今后可以进一步研究 的方向。 第i i i 页 北京邮电大学硕士毕业论文 摘要 关键词对等网络 结构化系统非结构化系统分布式哈希表 多属性发布向量空间模型 第i v 页 一 广 北京邮电大学硕士毕业论文 英文摘要 s t u d yo ns e a r c hs c h e m ei ns t r u c t u r e d p 2 pn e t w o r k a b s t r a c t p e e rt op e e rn e t w o r k ( p 2 p ) ，i nw h i c he v e r yn o d ec a ns h a r eal a r g e a m o u n to fd a t aw i t ho t h e r s ，i sar e v o l u t i o nt ot h et r a d i t i o n a lc l i e n t s e r v e r n e t w o r ka r c h i t e c t u r e w i t ht h es c a l eo ft h ep 2 pn e t w o r kg r o w i n g ，i tc a n r a p i d l ya c c u m u l a t ei n f l a t e di n f o r m a t i o na n dp r o v i d ear i c hi n f o r m a t i o n w a r e h o u s ef o ru s e r s p r e s e n td i s t r i b u t e ds y s t e mb a s e do np 2 pc a nb ec l a s s i f i e d i n t o u n s t r u c t u r e da n ds t r u c t u r e ds y s t e m s u n s t r u c t u r e ds y s t e m sa r ef i tf o rt h e h i g h l yd y n a m i cn e t w o r ke n v i r o n m e n to fp 2 p , f o rt h e ym a i n t a i nl o o s e n e t w o r ko v e r l a y b u tb e c a u s eo ft h er a n d o mq u e r yf o r w a r d i n gs c h e m e e a c hn o d ea p p l i e s ，i t ss e a r c he f f i c i e n c yi sl o w t h el i m i t e df l o o d i n g m e c h a n i s mi m p r o v e st h es e a r c h e f f i c i e n c y , b u t c a u s e s p o o r s y s t e m s c a l a b i l i t ya n dl o ws e a r c hs u c c e s sg u a r a n t e e s t r u c t u r e ds y s t e me m p l o y s as c a la b l es c h e m et og u a r a n t e es e a r c hs u c c e s s ，b u ti tn e e d st om a i n t a i n s t r i c t l yc o n t r o l l e do v e r l yn e t w o r k ，i ti s d i f f i c u l tt o a d a p t t o h i g h l y d y n a m i cn e t w o r ke n v i r o n m e n to fp 2 em o r ei m p o r t a n t ，t h eu s eo fd h t s l e a d st ot h ef a c tt h a to n l yk e y w o r de x a c t m a t c hi sa v a i l a b l e a b u n d a n t s h a r e dr e s o u r c e so fp 2 ps y s t e m sa t t r a c tl a r g ea m o u n to fu s e r s ，b u ti t s d i f f i c u l tt of i n dd e s i r a b l er e s o u r c e sf r o mt h eh u g ea m o u n to fr e s o u r c e s c o n s e q u e n t l y , a ne f f i c i e n ts e a r c hs c h e m e f o ru s e r st or e t r i e v en e e d e dd a t a q u i c k l ya n da c c u r a t e l yi sr e q u i r e de m e r g e n t l y b e c a u s eo ft h ed i v e r s i t ya n dc o m p l e x i t yo fn e t w o r kr e s o u r c e s ，i ti s n e c e s s a r yt oc h a r a c t e r i z ee a c hr e s o u r c ew i t hs e v e r a lp r o p e r t i e sf r o m v a r i o u s p o i n t s o fv i e ws oa st o e x p r e s su s e r s 。r e q u i r e m e n t sm o r e a c c u r a t e l ya n dt om a k et h es e a r c hr e s u l tm e e tt h eu s e r s r e q u i r e m e n t s b e t t e r b a s e do nd i s t r i b u t e dh a s ht a b l e ( d h t ) i d e a ，am u l t i p l ep r o p e r t i e s p u b l i s hs y s t e mi sd e s i g n e di nt h i sp a p e r u s i n gt h ea b i l i t yo fd h tt h a ti t i sa b l et om a pas i n g l ek e yt oap e e ri nt h en e t w o r k ，t h es y s t e mp u b l i s h e s 第v 页 北京邮电大学硕士毕业论文 英文摘要 t h ei n v e r t e di n d i c e so fe a c hp r o p e r t yt oc e r t a i np e e r sr e s p e c t i v e l yw h i l e p u b l i s h i n gr e s o u r c e s ，a n d r o u t e st h es e a r c h r e q u e s t t ot h e s e p e e r s p o s s e s s i n gt h ei n v e r t e di n d i c e sa c c o r d i n gt og i v e ns e a r c h i n gc o n d i t i o n so f e a c hp r o p e r t yw h i l es e a r c h i n gr e s o u r c e s i t sr e q u i r e df o rt h es y s t e mt o c o l l e c te a c hp r o p e r t ya n dc o m p u t et h ei n t e r s e c t i o no ft h e ma st h er e s u l to f s e a r c h s ot h es y s t e ma v o i d st h ep r o b l e mt h a ts t r u c t u r e dp 2 po n l y s u p p o r t se x a c t l ys e a r c h i n g n e x t ，t h ea u t h o ra n a l y s e ss o m ei m p o r t a n tt e c h n i q u e st oi m p r o v et h e s y s t e m ，s u c ha sv s m ，1 1 f i d fa n db l o o mf i l t e r a n di td i s c u s s e dh o wt o a p p l yt h e mo ns e a r c h i n gt e x tr e s o u r c e a tt h ee n do ft h i sd i s s e r t a t i o n ，i tg i v e so u tas u m m a r yo ft h er e s e a r c h w o r ka n dp r o p o s e st h ef u r t h e rr e s e a r c hi nt h i sf i e l d k e yw o r d sp 2 ps t r u c t u r e ds y s t e mu n s t r u c t u r e ds y s t e md h t m u l t i p l ep r o p e r t i e sp u b l i s h v s m 第v i 页 3 2对等网抽象模型1 2 3 3典型对等网络软件模型研究1 3 j j 2 g n u t e l l a j 4 f ： j 3k a z a a 1 6 i i 4z j 日。j7 ： j - 5f r e e n e t 17 3 3 6 缮构纪系z 密j 8 第四章 基于d h t 的资源查找算法分析 1 9 4 1 p 2 p 网络中的拓扑结构研究1 9 4 2d h t 的概念2 0 第v i i 页 北京邮电大学硕士毕业论文目录 4 2 1 4 2 2 学矛襄毫必2 1 42 3 上) 肼2 1 4 3 基于d m 的资源查找算法研究2 1 4 王j ( 洲刀 t i 5 第游彪裁分析刃 第五章 结构化对等网络查找算法改进 5 1 算法改进的必要性3 4 5 2 系统算法设计3 4 s 2 1 5 2 2 5 2 3 5 3 s 3 1 唐缮4 口 进一步优化算法的几个关键技术4 1 5 3 4 5 3 s j 绔f 6 第六章工作总结和展望 4 7 6 1 工作总结4 7 6 2工作展望4 7 参考文献 致谢 4 3 第v i 订页 北京邮电大学硕士毕业论文第一章绪论 1 1 研究背景 第一章绪论 随着互联网的普及和宽带技术的发展，以对等网络( p 2 p ) 技术为核心的软件产 品正在为越来越多的网民所接受和喜爱。自2 0 0 0 年开始，国内外多家p 2 p 产品纷纷 问世，其中以国外n a p s t e r 、g r o o v e 、o p e n c o l a 等和国内o p e n e x t 、k u g o o 、p o c o 等为代表的p 2 p 产品在短短几年时间，用户的注册量不断增长，已成为许多网民不能 离弃的上网伙伴。就国内p 2 p 软件市场而言，由于目前存在的几家知名p 2 p 产品几乎 都是以即时通信和文件搜索、共享为主要功能，而且多数产品还处于开发和运营的初 期，因此，对p 2 p 多个功能的开发和商业应用，将成为竞争的焦点，而整个p 2 p 领域 正蕴藏着巨大的商机。 p 2 p 所包含的技术就是使联网电脑能够进行数据交换，但数据是存储在每台电脑 里，而不是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数据库里 自由搜索、更新、回答和传送数据。p 2 p 与其说是一场革命倒不如说是一种演变。在 过去的几年中，n a p s t e r 和g n u t e l l a 这样的文件共享软件在i n t e r n e t 上迅速传播，用户 数量急剧增长。 企业对电脑资源的需求是无限的，且p 2 p 网络具有降低成本，并提高生产力的潜 力，所以，p 2 p 运算技术的普及，需要更多的客户端电脑资源及控制管理p 2 p 运算网 络的服务器系统。在如此巨大的需求下，p 2 p 的研究必将成为一个相当热门而又有重 大意义的课题。 1 2p 2 p 发展历史 从网络模型来看，p 2 p 并不是新概念，它可以说是互联网整体架构的基础。互联 网最基本的协议t c p i p 并没有客户机和服务器的概念，所有的设备都是通讯的平等 的一端。在十几年前，所有的互联网上的系统都同时具有服务器和客户机的功能。然 而，由于受早期计算机性能、资源等因素的限制，随着互联网规模的迅速扩大，大多 数连接到互联网上的普通用户并没有能力提供网络服务，从而逐步形成了以少数服务 器为中心的客户机朋艮务器( c l i e n t s e r v e r ) 架构。w w w 的风靡，正是这一应用潮流的 体现。在客户机朋& 务器架构下，对客户机的资源要求非常少，因而可以使用户以非常 低廉的成本方便地连接互联网，推动了互联网的快速普及。 但是，随着互联网对人们生活的联系日益紧密和深入，人们需要更直接、更广泛 的信息交流。普通用户希望能够更全面地参与到互联网的信息交互中，而计算机和网 第1 页 北京邮电大学硕士毕业论文 第一章绪论 络性能的提升也使其具有了现实的可能性。在此背景下，p 2 p 再一次受到了广泛的关 注。 将p 2 p 带入了网络世界的一个著名例子是n a p s t e r 。该公司成立于1 9 9 9 年，它提 供服务允许音乐迷们交流m p 3 文件。它与提供免费音乐下载m p 3 c o m 的不同就是在 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 在短时间里吸引了5 0 0 0 万用户。n a p s t e r 的成功促使人们 认识到把p 2 p 拓展到整个互联网范围的可能性。 另一个采用p 2 p 方式实现计算资源共享的例子是s e t i h o m e 。这是一个寻找外 星球文明的大型科研工程。为了快速处理大规模天文数据，该工程将互联网上3 0 0 万 台以上的计算机通过p 2 p 方式组织起来，充分共享这些节点的空闲计算资源( c p u ) 。 事实上，网络上现有的许多服务可以归入p 2 p 的行列。即时通信系统如i c q 、y a h o o m e s s e n g e r 、m s nm e s s e n g e r 以及o i c q 等是都最流行的p 2 p 应用。它们允许用户互 相沟通和交换信息、交换文件。但这些系统缺少对于大量信息共享非常重要的一些功 能，如搜索。这可能正是为什么即时通讯出现很久但是并没有能够产生如n a p s t e r 这 样的影响的原因之一。 1 3 论文结构 本文分析了p 2 p 技术的特点，并根据所做的工作，以路由查找算法为重点，介绍 了自己所进行结构化对等网络的研究。论文内容的安排具体如下： 第一章绪论：简要介绍了论文的研究背景和对等网络的发展历史，概述本课题 的研究内容以及本文的组织。 第二章p 2 p 网络介绍：对对等网络的定义和分类进行探讨，并指出了对等网络 的应用和优势所在。 第三章对等网络模型：首先，介绍了对等网络抽象模型，接着研究了包括n a p s t e r , g n u t e l l a ，j x t a 等在内的典型对等网络抽象模型。 第四章基于d h t 的资源查找算法分析：本章总结了对等网络的拓扑结构，介绍 了分布式哈希表的定义和应用，最后详细分析了几个典型结构化对等网络的资源查找 算法，并对算法性能进行比较。 第五章结构化对等网络多关键字查找算法改进：本章首先提出了结构化对等网 络查找算法的必要性，接着详细介绍了多属性发布系统的设计，最后研究了可以对系 统优化的几个关键技术，并讨论了其在扩展系统应用上作用。 第六章工作总结和展望：本章总结了所做工作和研究成果，并对今后的进一步 工作方向进行了展望。 第2 页 厂 北京邮电大学硕士毕业论文 第一章绪论 在本文的最后，列出了研究和完成论文阶段的参考文献，并对研究工作中给予作 者大力支持的老师同学致以衷心的感谢。 第3 页 北京邮电大学硕士毕业论文 第二章p 2 p 网络介绍 第二章p 2 p 网络介绍 2 1 对等网络的定义和分类 2 1 1 对等网络的定义 n a p s t e r 的出现引起互联网的一次巨大震动，同时在社会上也引起强烈的反响， p 2 p 概念也就应运而生。可以说，p 2 p 不仅仅是一种软件架构，也是一种社会模式的 体现。 p 2 p 网络是一种分布式的网络结构，其参与者共享部分硬件资源，如处理能力、 存储空间、网络带宽、打印设备等。这些共享资源通过网络来提供服务和内容。对等 点之间直接存取，不需经过中间仲裁实体。网络中的每个参与者既是资源提供者，也 是资源请求者。 目前对于p 2 p 有着不同的定义i n t e l 的p 2 p 工作组定义为“通过在系统之间的直 接交换共享计算机资源和服务”，p 2 p 有三个关键特性： 1 具有服务器的操作能力 2 有独立于d n s 的寻址系统 3 能够处理变化的连接 c l a ys h i r k y 把p 2 p 定义为“一类能够利用在i n t e r a c t 边缘可以获得的存储空间， c p u 周期，信息等资源的应用，由于需要在一个高度动态的环境中访问这些分布式资 源，p 2 p 的节点必须能够独立于d n s 系统且高度自治”。 一般的说，p 2 p 是一个用于资源共享p e e r 群体，其中每个p e e r 向群体提供资源同 时作为回报从中获取所需资源，它的思想是基于世界上的事物是广泛分布且相互联系 的，不可能通过种集中化的方式管理如此庞大的结构。p 2 p 通过分布于世界各地的 个人计算机管理大量的计算能力，存储空间和连接。p 2 p 中的每个p e e r 自治又彼此依 赖，所谓自治是指每个p e e r 独立决定自己的行为而不受其它例如集中式授权机构的 控制，同时每个p e e r 又需要相互协作获得信息资源计算资源，在本文中把每个p e e r 称 为节点。 和p 2 p 相关的术语主要有如下几个： 1 集中式系统 系统中只有一个单元，可能是一个单处理器，多处理器机器，也可能是一个超级 计算机或者大型机。 2 分布式系统 系统中的各个部件分布于网络中，各个部件通过传递消息协同工作 第4 页 北京邮电大学硕士毕业论文第二章p 2 p 网络介绍 3 客户 定义为一个能发起请求但不能提供服务的实体( 节点，程序或者模块等) ，如果 一个客户同时能提供服务，那么它同时也承担服务器的角色。 4 服务器 定义为一个能对其它实体发起的请求提供服务而不发起请求的实体，如果服务器 同时发起请求，那么它同时承担客户端的角色。多数情况下，只有少量的服务器而有 大量客户。 5 客户机n 务器模型 该模型中，每个实体都可以承担服务器和客户的角色，但是对同一个实体而言， 承担的客户和服务器两个角色必须是针对不同目的，也就是说对同一个目的而言，服 务器和客户角色必须由不同的实体承担。 6 p e e r 定义为同系统中其它实体功能相似的实体也称为节点 7 p 2 p 模型 该模型中，实体至多通过和集中式服务器有限的交互共享它们的资源( 信息，处 理器等) ，所有的实体对于同一个目的而言既是客户又是服务器。 8 分布式计算 定义为一个计算机系统，系统中的多个相互连接的计算机共同完成分配给系统的 任务。这些系统包括集群计算，网格计算和从整个i n t e r n e t 上的p c s 上收集计算资源 的全球计算系统。分布式计算具有内在的p 2 p 特性。 。 9 网格计算 定义为“在大规模和复杂虚拟组织中的资源共享和协作方案”，更具体地说，网格 是一个用于共享计算密集型资源( 例如超级计算机和集群计算机) 的系统结构，同具 有内在p 2 p 特性的分布式计算系统最大的不同是网格计算有透明的特点。 1 0a d h o c 通信系统 定义为一个能够在没有预先设计好的结构的系统中实现计算机间通信的系统，这 些计算机形成一个a d h o c 网络。这个网络必须自己解决通信，命名和安全问题。p 2 p 系统可以建立在一个a d h o c 通信系统之上。 2 1 2 对等网络的分类 计算机系统的划分可以用图2 1 表示 第5 页 北京邮电大学硕士毕业论文第二章p 2 p 网络介绍 图2 1 计算机系统划分 从图2 - 1 可以看出任何计算机系统都可以分为集中式系统和分布式系统，分布式 系统分为客户机服务器，出版者订阅者和p 2 p 模型根据有没有一个集中的实体，可 将p 2 p 系统分为混合p 2 p 系统( 有集中的实体) 和纯p 2 p 系统( 无集中的实体) 。相 应地p 2 p 软件分为集中式和分布式的。 集中式p 2 p 利用服务器作为媒介，使各个分散的节点( 用户) 能互相联系，生成各 种服务响应各节点的业务需求，各节点一旦建立联系，便可互相共享对方资源。这种 方式可使各节点定位比较容易，易于搜索、查找，使各节点问容易建立比较固定的关 系，使得在此平台上开发进一步的应用更加易于推广。但这种方式对服务器性能要求 也很高，应用系统功能越强大，对服务器的要求就越高。在这种架构中可以利用技术 手段使得某些大节点分担一些服务器的功能，从而降低服务器的负荷。 在分布式p 2 p 中，每个节点即做服务器又做客户端。这种方式非常灵活，一个孤 立的节点只要连上此p 2 p 网络内的任一节点便可与此网络进行资源互享。事实上，这 种方式宏观来看应属于p e e r - t o n e t ( p t n ) ，任何一个节点只是此网络的一个组成部分， 任何一个节点只是从此网络上获取资源，它可以在一个公司或企业内部无需额外配置 而实现一个企业内部p 2 p 系统。这此方式搜索功能强大而灵活，能够体现出p 2 p 的本 质。由于架构的原因，此方式节点定位能力极差，无法使节点之间产生比较固定的关 系；搜索能力虽然灵活强大，但冗余较大，如果技术手段处理不好很容易产生广播风 暴，引起网路资源的大量消耗，且该架构的技术实现难度极大。 另外，p 2 p 系统从逻辑结构上可以分为结构化系统和非结构化系统，将在第三章 介绍。 2 2 对等网络的应用 根据p 2 p 工作组的定义p 2 p 在商业上主要有以下几种应用： 第6 页 北京邮电大学硕士毕业论文 第二章p 2 p 网络介绍 1 文件共享 p 2 p 允许文档，多媒体和其它文件在不同计算机之间直接共享，用户发布的文件 可以利用网络上任何可用存储空间。据估计，互联网上的p c 至少提供了一百万 t e r a b y t e s 的空闲存储空间，通过这种分布式文件共享，空间利用率大大提高，用户可 得信息资源大大丰富。 2 协同合作 p 2 p 可以让一个工作小组建立和管理同步与非同步的协同合作，并增进他们的效 率。利用p 2 p 技术，可以增进成员间的合作效率和促进生产力，减少在多个项目间再 评估和协调的时间，每个成员都可以访问最新的数据，充分分享彼此的资源。 3 边界服务 p 2 p 运算可以帮助企业更有效地提供并传递跨越不同的地理疆界的服务，而e d g e s e r v i c e 可运用企业存取信息的服务地域性( s e r v i c el o c a l i t y ) ，让资料可以更靠近需要服 务的点。例如一家大型的跨国公司希望通过i n t e m e t 向其全球的员工提供统一的培训 课程。如果培训课程的录像存储在中央服务器则很可能会造成网络拥塞，如果在每个 分部所在地增加服务器存储培训课程录像又会增加成本。利用p 2 p 只需将培训课程传 至各地的一个员工的计算机上，其他员工就可以通过p 2 p 的方式得到培训录像。 4 分布式计算 p 2 p 运算可以帮助企业拥有强大的运算能力。利用网络连结而成的网络计算机， 闲置计算机上的c p u 及储存空间皆可充分利用。利用p 2 p 技术来充分整合闲置的计 算机资源，不但可以为公司节省大项目的运算成本，也不需只为此大项目而额外添置 机器设备，降低硬设备的支出。以i n t e l 公司为例，该公司美国总部的员工就曾利用 时差的影响，在i n t e l 公司设在以色列的分部的工程师们下班的时间，通过n e t b a t c h 在八周内完成了一个芯片的设计。没有p 2 p 这个项目至少需要两倍的时间才能完成， i n t e l 估计它利用p 2 p 节省的包括购买设备和缩短项目周期的费用至少为5 亿美元。 5 智能代理 智能代理可以通过p 2 p 运算模式，动态的在网络上一起进行协同工作。运行于不 同节点计算机( 如不同操作系统或不同的程序语言) 间的代理可以进行信息的传递和格 式转换，代理还可以在p 2 p 的环境之下按事情的优先级来执行它被安排的工作。 6 p 2 p 和主动网络 主动网络的开发者目的是在i p 报文中封装可执行代码，报文在网络上传输的时 候在中间节点的有限环境中执行该代码使得网络可编程。这样就可以通过在口报文 中封装p 2 p 用户的查询请求定位需要的信息位置，同时可以获得其它信息，例如文 件修改时间，文件大小，文件访问率和链路拥挤状况等等，使用这些信息动态调整网 络中文件存放位置，实现负载均衡。 第7 页 北京邮电大学硕士毕业论文第二章p 2 p 网络介绍 p 2 p 和主动网络的结合适合于商业实体应用，这些实体可以对一些节点采取某种 集中控制，配置这些节点能够执行的移动代码类型，由于p 2 p 的查询比分布式数据库 的查询更加轻量级，所以移动代码所产生的计算负载和网络负载都很小，这样二者的 结合将导致一个高效的自组织的p 2 p 网络。 2 3 对等网络的优势和挑战 2 3 1 对等网络的优势 和传统的客户服务器网络相比p 2 p 网络有如下吸引人之处 1 负载均衡 p 2 p 网络环境下可以根据策略灵活分布信息。负载均衡模块可以监控各种信息的 流量和请求率，然后重新分布这些信息以减轻单个节点的负载。通过这种负载平衡策 略可以提供分布式c a c h e 可以实现的功能，但是更简单且代价小。f r e e n e t 已经采用了 自动文件复制和重定向策略。 2 丰富的信息资源 任何p 2 p 网络用户能够扫描活动节点搜索需要的信息，然后直接从这个节点上下 载。用户可以在他们的机器上把下载的信息共享出来，这样，请求率高的文件能够很 快在许多节点上扩散开来。当网络增长的时候共享信息的数量和范围都将随之增长。 在一个开放网络环境下，p 2 p 网络能够很快积累相当丰富的信息。 3 冗余和容错 p 2 p 网络的多个节点间的信息复制导致高度冗余，其直接结果是提高了信息的可 得性，使之服务更多的用户。另外，冗余使得网络不会产生“单点失效”问题。所以分 散式的p 2 p 网络提高了网络的容错和安全。这和开始i n t e r n e t 的设计思想很相似，正 如n a p s t e r 的创始人s h a w nf a n n i n g s 所言：“文件共享网络是向原有i n t e r n e t 的一次回 归”。 4 基于内容的寻址 在w e b 上，u r l 地址并不能直接反映出它们的内容，在p 2 p 网络中，存储特定 信息的节点地址对于用户仍然是透明的，用户向网络提交查询请求，请求信息中包括 需要查询的信息，p 2 p 软件把请求转化成这些存放这些信息的节点地址。这种寻址方 式是在语义的高层，因为用户指定的是信息标识符而不是物理位置。信息标识符等价 于一组存储有该信息的节点地址，所以把信息按照内容分类在网络上分布能够使信息 资源更加易于查找。 5 有效的搜索 w e b 搜索引擎存在一些问题，这些搜索引擎依赖于w e bc r a w l e r 在i n t e r n e t 上漫游 得到信息并把这些信息存储在巨大的，可扩展的数据库中。这些索引信息仅包括开放 第8 页 北京邮电大学硕士毕业论文第二章p 2 p 网络介绍 的服务器，并且数据库不会随着网络状况动态更新。 在p 2 p 网络中，任何节点的信息只有当节点在线的时候才被索引，因此索引信息 与网络状态同步。p 2 p 网络中不依赖于搜索机器人重新访问链接来修改数据库索引信 息，这种动态信息索引和对信息有效搜索使得p 2 p 和其它应用有显著优势。 6 隐私性 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正在变得越来越容 易。隐私的保护作为网络安全性的一个方面越来越被大家所关注。目前的i n t e r n c t 通 用协议不支持隐藏通信端地址的功能。攻击者可以监控用户的流量特征，获得i p 地 址。甚至可以使用一些跟踪软件直接从i p 地址追踪到个人用户。 在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个集中环 节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决i n t e r n e t 隐私 问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体之 中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继服务器节点。而在 p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活性 和可靠性，能够为用户提供更好的隐私保护。 2 3 2 对等网络面临的挑战 同样，如果要广泛应用p 2 p ，技术上还面临很多挑战。 1 安全 由于在p 2 p 网络中节点的硬盘需要被其他节点访问，节点用户安全意识的缺乏以 及p 2 p 协议和p c 操作系统的安全漏洞使得节点很容易受到黑客攻击。节点受到攻击 会造成两种后果：一是用户个人信息被剽窃，文件被病毒感染，其他从该节点下载文 件的用户也会被感染；二是用户站点被黑客控制成为分布式拒绝服务的发起者。在商 业中，使用这种结构共享关键数据可能导致严重的安全问题，因此安全因素是必须首 先要解决的问题。 2 互操作性 p 2 p 系统( 尤其是商务应用) 必须面对各种各样的操作系统、网络技术和平台。 现在的p 2 p 系统执行的是相对简单的任务，例如传输m p 3 音乐文件，它们能够和脚 本翻译、软件打包以及其他互联网上的互操作性技术兼容。将来，p 2 p 系统需要更高 级的互操作性技术以执行复杂的任务。 3 拓扑一致性和资源定位 p 2 p 系统需要解决的一个重要问题是：在一个缺少集中化服务器的动态环境下， 各个节点能够维持一致的网络拓扑信息。由于p 2 p 网络中节点的加入和离开非常频 繁，传统路由扩散的方法难以解决这一问题，所以需要一个高效的一致性信息维护机 制实现一些功能。例如，当网络拓扑变化时快速恢复网络的稳定性问题需要解决，但 第9 页 北京邮电大学硕士毕业论文 第二章p 2 p 网络介绍 多个节点的并发加入和离开使得解决这一问题更具挑战性。另外，用户从大量分散的 节点中找到需要的资源和服务也是一个挑战。 4 q o s 问题 p 2 p 网络的q o s 问题包括两个方面。第一是信息获取的q o s 问题，用户需要的 信息可能在多个节点同时存放，如何选择一个处理能力强、负载轻、带宽高的节点需 要用户考虑。第二个问题是用户可能共享出无用或者违法信息，造成信息垃圾充斥网 络，因此，网络应该控制用户共享的信息，提高用户获得有用信息的效率。 第1 0 页 北京邮电大学硕士毕业论文 第三章对等网络模型 3 1概述 第三章对等网络模型 尽管p 2 p 在很多方面有重要应用，文件共享是最重要的一个应用。随着加入文件 共享网络的用户急剧增加，具有可扩展性是一个p 2 p 系统成功的关键。由于p 2 p 网络 的分布式特性，数据的存储和传输是内在可扩展的，关键的问题是文件定位和查询解 析是否可扩展。最早的p 2 p 文件共享系统如n a p s t e r 和s c o u r 实质上并非是纯粹的p 2 p 系统，它通过一个中央服务器保存所有n a p s t e r 用户上传的音乐曲目和存放位置的信 息，当某个用户需要某首曲目时，首先连接到n a p s t e r 服务器，在服务器进行检索， 并由服务器返回存有该曲目的用户的信息，再由请求者直接连到曲目的所有者传输文 件。这种方式最大的隐患在中央服务器上，如果该服务器失效，整个系统都会瘫痪。 另一个问题在于安全性上，n a p s t e r 并没有提供有效的安全机制。这种结构能够满足 早期少数用户的需求，当网络膨胀以后会产生严重的可扩展性问题。之后产生了不依 赖于中央服务器的p 2 p 系统g n u t e l l a 和k a z a a ，这些系统在网络的物理拓扑之上虚拟 了一层叠加拓扑，拓扑之中每个p 2 p 节点和若干个其它节点相连，由于数据的存放和 叠加拓扑毫无关系，因此这些系统是非结构化系统。在这样的系统中搜索需要的数据 几乎是随机搜索，搜索从一个节点开始逐个询问是否有匹配查询请求的数据。造成这 样的问题其根源是没有节点可能存放哪些文件的信息。p 2 p 系统的不同之处很大程度 上在于如何构造叠加拓扑和如何传播查询请求。例如g n u t e l l a 采用所有的查询都通过 在网络中以有限的h o o d i n g 的方式进行，通过t r l 限制f l o o d i n g 的范围。这种方式 虽然可以有效的找到需要的信息，但却会在网络中产生大量的流量，显然是不可扩展 的。 叠加网络定义：p 2 p 网络中每个节点都在应用层维持一应用层路由表，其中每 个入口都包含其邻居节点的i p 地址，网络中所有节点通过该路由表形成的逻辑网络 称为叠加网络。 由于非结构化系统中的随机搜索造成的不可扩展性，大量的研究集中在如何构造 一个高度结构化的系统。在结构化系统中，叠加拓扑被严格控制，文件( 或者文件指 针) 存放在确定的位置上。系统提供从文件标识符到存放该文件的节点标识的映射服 务然后查询请求路由到该节点通过以上方法系统提供了一个可扩展的方案实现了文 件的“精确匹配”查询。目前人们把研究的重点放在了如何有效的查找信息上，基于 d h t ( d i s t r i b u t e dh a s ht a b l e ) 的分布式查找和路由算法目前是一个研究热点。 由上可知，目前的分布式p 2 p 系统一般分为非结构化系统和结构化系统，非结构 第1 1 页 北京邮电大学硕士毕业论文第三章对等网络模型 化系统由于维持松散的叠加网络使其更能适应高度动态的p 2 p 网络，但是由于其转发 查询时随机选择节点，查询效率不高，g n u t e l l a 使用f l o o d i n g 的方法又造成系统可扩 展性差，且不能保证查找的成功。结构化系统使用可扩展的方法能保证查找的成功但 由于要维持严格控制的叠加拓扑因此对p 2 p 网络中大量节点的动态变化适应性较差， 且由于分布式哈希表的使用使其只支持精确查找。两种类型p 2 p 系统各有优劣，有其 各自的应用范围。 3 2 对等网抽象模型 p 2 p 中所有的节点通过规则或者不规则的方式逻辑上互联成一叠加网络，使得路 由表和路由路径长度大大减少，这样的系统中，路由表的入口作为指向其邻居节点的 逻辑链接可以看成是叠加网络的边。 叠加网络的复杂性决定了可以构造的p 2 p 系统的最大尺寸和性能，因此叠加网络 的选择和构造是p 2 p 系统设计中的关键问题，下图显示了通用的分布式p 2 p 系统模型。 模型中可以看出，p 2 p 系统中的每个节点通过物理网络互联，在应用层形成逻辑 上的叠加网络。每个节点一般由三部分组成： 1 查询和路由算法 当节点产生或接收到查询请求时，使用该算法通过叠加网络选择邻居节点转发查 询。 2 路由表 网络中每个节点都维持一路由表，该表记录了系统中其它节点信息，路由表的每 个入口对应该节点的一个邻居信息，路由表的大小决定了该节点在叠加网络中的出 度。 3 数据存储 每个节点本地存储的数据以及其它节点数据的索引都在此区域中。 第1 2 页 北京邮电大学硕士毕业论文 第三章对等网络模型 节点n 查询和路由算 法 路由表 数据存储 图3 - 1 对等网抽