（计算机应用技术专业论文）psp技术研究及应用.pdf

摘要 摘要 i i i i i ii ii ii i ii i i i iiiif 18 8 9 4 6 1 如何有效的管理和利用互联网上快速增长的信息资源是现代网络亟待解决的一个 问题。随着现代加工技术和硬件技术的发展，p 2 p 在现实生活中的大规模应用成为现 实。它通过尽可能利用网络边缘空闲的资源，以提高整个互联网处理能力，消除了传 统客户服务器模式中服务器为中心的网络瓶颈。 m i t 提出的c h o r d 是一种简单、精确、高效率的环形结构化p 2 p 模型，因此对 c h o r d 的研究具有很重要的意义。本文从分析c h o r d 出发，发现当系统频繁有节点加 入、退出、失效等状况时，指取表中的大量连接不可用，从而导致c h o r d 的性能急剧 下降。为了提高c h o r d 对动态网络的适应性，本文提出了一种基于k 桶结构的动态路 径缓存c h o r d 协议，该协议对c h o r d 路由表进行了“k 桶结构的改造，在查询或路 由的过程中用以实时保存网络动态信息，提高连接的可用性，增强c h o r d 对网络动态 性的适应性。同时为了保有c h o r d 的查询效率，保留了c h o r d 中原来的路由表项，在 此称为“基准点 。与c h o r d 相比，“基准点”的更新策略采用按需更新的方式，降低 了系统网络拓扑维护的代价。模拟实验表明，改进后的c h o r d 算法在不影响查询效率 的前提下，提高了对动态网络的适应性。 其次对p 2 p 网络安全策略的研究。由于p 2 p 系统中没有中心组织单元，每个节点 利用内建的机制相互之间互联组成网络，整个网络分布呈现出小世界特性和无标度特 性，这为网络病毒的入侵提供很好的机会。通过对p 2 p 所呈现出的网络特性的研究， 本文提出了局域搜索免疫策略。在已知邻居节点度的前提下，该策略主要通过最大度 搜索策略，搜索并免疫度数大的节点。实验使用s i s 病毒传播模型分别在e r 随机网 络、b a 无标度网络和现实网络中进行测试，该策略比其他免疫策略得到相等或者更 低的感染密度。实验在b a 无标度网络中测试了该策略与聚类系数之间的关系。 最后将p 2 p 思想引入到公交查询系统。与传统以建立邻接矩阵为基础的建模思想 相比，该系统则以站点为建模对象，通过起始站点和目的站点的信息交换，逐步扩大 搜索范围，完成搜索任务。基于p 2 p 思想的公交查询系统不仅提高了查询效率，而且 可以向系统提供诸如实时路况、站点忙闲等动态信息，以满足人们不同的需求。 关键字：c h o r d ；动态网络；免疫策略；e r 随机网络；b a 无标网络；公交查询 a b s t r a c t a b s t r a c t t h e r ei sab u r n i n gp r o b l e mt h a th o wt om a n g ea n du t i l i z et h ei n f o r m a t i o nw h i c h i n c r e a s e sr a p i d l ye v e r y d a yi nm o d e mn e t w o r k w i t ht h ed e v e l o p m e n to fh a r d w a r ea n d m a c h i n i n gt e c h n i q u e ，p 2 pc a nb eu s e di nt h er e a l - l i f e ，w h i c hu s e t h en e t w o r ki d l er e s o u r c e a tt h ee d g eo ft h en e t w o r ka sm u c ha sp o s s i b l et oe n h a n c et h eh a n d l i n gc a p a c i t yo ft h ew h o l e n e t w o r k , e l i m i n a t i n gs e r v e r - c e n t r i cn e t w o r kb o t t l e n e c ko fc l i e n t s e r v e rm o d e c h o r di sa s i m p l ea c c u r a t ea n dh i g h l ye f f i c i e n tr i n gm o d e lo fp 2 p , w h i c hw a sp r o p o s e d b yb r i t t h e r e f o r e ，t h er e s e a r c ho fc h o r dh a sav e r yi m p o r t a n ts i g n i f i c a n c e i nt h i st h e s i s ，w e f o u n dt h a te x i s tc e r t a i na m o u n t so fu n r e a c h a b l el i n k si nt h ef i n g e r t a l b eo fc h o r d ，w h e nt h e s y s t e mo c c u rt h eo p e r a t i o no fj o i n , q u i to r f a i l u r e f r e q u e n t l y , w h i c hm a k ec h o r d s p e r f o r m a n c ef a l l i n gb a d l y i no r d e rt oa d d r e s st h i sp r o b l e m ，t h et h e s i sa d v i c c sak - c a n s t r u c t u r a ld y n a m i cc a c h ep r o t o c o lb a s e do nc h o r d ，w h i c hr e - b u i l d st h ef m g e r t a b l eu s i n gt h e “k - c a n ”s t r u c t u r e ，s t o r a g i n gt h er e a l t i m ed y n a m i cn e t w o r ki n f o r m a t i o nw h e nr o u t i n go r s e a r c h i n g ，w h i c hi n c r e a s e st h e l i n k s a v a i l a b i l i t y f o ru s ea n de n h a n c e st h ec h o r d s a d a p t a b i l i t yf o rd y n a m i cn e t w o r k m e a n w h i l e ，s oa st om a i n t a i n t h ee f f i c i e n c yo f c h o r dq u e r y , e c p ( e n h a n c e dc h o r dp r o t o c 0 1 ) r e t a i n st h ef i n g e r t a l b ee n t r i e sw h i c hw e r ei nt h eo r i g i n a l c h o r d ，w h i c hi sc a l l e d “s t a n d p o i n t a n di su p d a t e db yu s i n go n - d e m a n ds t r a t e g y , d e c r e a s i n g t h ec o s to fm a i n t e n a n c e t h er e s u l t ss h o wt h a te c pc a nb ea p p l i e dt oah i g h l yd y n a m i c e n v i r o n m e n t 、析t l lg o o ds e a r c h i n gp e r f o r m a n c e s e c o n d l y , s t u d yo fs e c u r i t ys t r a t e g ya b o u tp 2 pn e t w o r k e a c hn o d eu s et h eb u i l t - i n m e c h a n i s mt oi n t e r c o n n e c tw i t l le a c ho t h e rw h t h o u tc e n t r a lo r g a n i z a t i o nu n i t , w h i c hf o r ma n e wn e t w o r k , s h o w i n gt h e d i s t r i b u t i o no fs m a l l - w o r l da n df r e e s c a c l ec h a r a c t e r s ，w h i c h p r o v i d eag o o do p p o r t u n i t yf o rt h ev i r u s si n t r u s i o n f o rt h ep u r p o s eo fs o l v i n gt h ep r o b l e m , w ep r e s e n tan e w l yd e v e l o p e dl o c a ls e a r c hi m m u n i z a t i o ns t r a t e g yi ni n h o m o g e n e o u s n e t w o r k s o nc o n d i t i o nt h a tw ek n o wt h en e i g h b o u rn o d ed e g r e e ，o u rp r o p o s e ds t r a t e g yu s e s m a x - d e g r e e s e a r c hw a y t os e a r c ha n di m m u n e s t r o n g e r n o d e w eu s et h e s u s c e p t i b l e - i n f e c t i o u s - s u s c e p t i b l ee p i d e m i cs p r e a d i n gm o d e lt od e m o n s t r a t et h ee f f i c i e n c yo f o u r p r o p o s e ds t r a t e g yo ne r , b a s c a l e f r e ea n dt w or e a ln e t w o r k s ，t h er e s u l ts h o w si tc a n e l i m i n a t et h ev i r u st h r o u g hi m m u n i z i n gt h es a m ed e n s eo fi n f e c t e dn o d e so rr e q u i r e sn om o r e i m m u n i z a t i o nd o s e st h a no t h e rs t r a t e g y w ca l s ot e s tt h er e l a t i o n s h i pb e t w e e nt h es t r a t e g ya n d c l u s t e r i n gc o e f f i c i e n ti nb a s c a l e - f r e en e t w o r k f i n a l l y , p 2 pc o n c e p t i si n t r o d u c e di n t ot h ep u b l i ct l r 伍cq u e r ys y s t e m c o m p a r i n gw i m t h et r a d i t i o n a lw a yw h i c hc r e a t eam o d e lb a s e do na d j a c e n c ym a t r i x ，o u rp r o p o s e ds y s t e m s m o d e l i n go b j e c ti ss i t e ，强es y s t e m s ，so p e r a t i o nm o d ei st h a tt h es o u r c es i t ea n dt h e d e s t i n a t i o ne x c h a n g ei n f o r m a t i o na n dg r a d u a l l ye x p a n dt h es e a r c h i n gd o m a i nt oc o m p l e t et h e a b s t r a c t s e a r c ht a s k p 2 p b a s e dp u b l i ct r a f f i cq u e r ys y s t e mn o to n l yi m p r o v e st h es e a r c he f f i c i e n c y , b u ta l s oc a np r o v i d ed y n a m i ci n f o r m a t i o n ，s u c ha sr e a l t i m et r a f f i c ，s i t e sb u s yo ri d l ee t c ，t o m e e td i f f e r e n tn e e d s k e y w o r d s ：c h o r d ；d y n a m i cn e t w o r k ；i m m u n i z a t i o ns t r a t e g y ；b as c a l ef r e en e t w o r k ；e r r a n d o mn e t w o r k ；p u b l i ct r a f f i cs e a r c h i i i 目录 目录 摘；要一i a b s t r a c t i i 第一章绪论l 1 1 课题的背景1 1 2p 2 p 技术国内外研究现状2 1 2 1国外相关研究2 1 2 2国内研究现状3 1 3p 2 p 存在的问题4 1 4 本文研究内容及文章内容5 第二章p 2 p 网络技术7 2 1 p 2 p 系统7 2 2p 2 p 核心机制7 2 3 结构化经典模型c h o r d 。1 2 2 3 1 c h o r d 简介1 2 2 3 2c h o r d 工作原理1 3 2 3 3c h o r d 对象定位算法1 5 2 3 4c h o r d 节点加入和离开1 6 2 3 5c h o r d 自适应算法17 2 3 6c h o r d 容错性18 第三章基于k 桶结构的动态路径缓存c h o r d 协议1 9 3 1c h o r d 存在的问题19 3 2e c p 基本思想19 3 3e c p 构建过程2 0 3 3 1 “k 桶”结构2 0 3 3 2 “k 桶”的更新策略2 1 3 3 3 “基准点”的更新策略2 1 3 - 3 4 动态节点算法2 3 3 3 5 路由查询机制2 3 3 4 性能分析2 4 3 5 实验2 4 3 5 1 路由效率试验2 5 3 5 2 收敛性2 6 3 5 3 查全率实验2 6 第四章不均匀网络中局域搜索免疫策略2 9 4 1p 2 p 面1 1 6 j 的安全问题2 9 目录 4 1 1p 2 p 网络病毒与蠕虫2 9 4 1 2 结构化p 2 p 网络的隐患2 9 4 1 - 3 p 2 p 安全研究一3 0 4 2 模型3 0 4 2 1s i s 病毒传播模型3 0 4 2 2b a 无标度网络模型3 1 4 2 3 无标度网络中的传播临界值31 4 3p 2 p 网络安全策略局域搜索免疫3 2 4 4实验3 4 4 4 1 经典网络模型的免疫。3 4 4 4 2 模拟现实网络的免疫。3 6 4 4 3 免疫与聚类系数之间的关系一3 7 第五章p 2 p 思想在公交查询系统中的应用3 9 5 1 建模思想一3 9 5 2 建模过程3 9 5 2 1 数据处理3 9 5 2 2 p 2 p 优化查询算法一4 0 5 3 算法实现与应用4 2 第六章总结和展望4 3 6 1 论文小结及其创新点4 3 6 2 论文存在的问题以及未来工作的展望4 3 致谢4 5 参考文献4 7 附录：作者在攻读硕士期间发表的论文。5 1 h 第一章绪论 第一章绪论 1 4 课题的背景 p 2 p 1 ( p e e r - t o p e e r ，对等) 网络是建立在互联网上的覆盖网。它是在现有的新材料 和新技术的基础上发展起来的，该思想的实现改变了传统客户服务器模式集中存储和 处理资源的方法，将网络边界上的资源有效地组织起来，使得资源提供者和资源接收 者之间能够直接相互交互信息。 在p 2 p 应用网络中，相互独立的用户在数据交换之前，关键问题是目标资源的定 位。资源的定位包括获取资源所在物理节点位置信息、资源属性信息以及建立连接所 需的信息。在第一代p 2 p 网络2 中，边缘节点共享网络资源，中心服务器负责记录共 享资源的索引信息并响应信息查询请求。节点加入网络时首先向服务器提交共享的资 源列表和节点的物理位置信息。物理位置往往以节点的i p 地址、端口号等标示。当某 节点需要网络资源时，该节点向服务器提交查询请求，服务器响应该节点的请求信息。 在收到服务器的响应之后，该节点与目标节点建立连接并从目标节点直接下载所需的 资源。随着互联网技术的发展以及人们对网络资源的迫切需求，服务器负载过重以及 版权纠纷问题日益显现，分布式p 2 p 网络取代中心式p 2 p 网络是必然的趋势。 分布式p 2 p 网络分为结构化和非结构化p 2 p 网络。在非结构化p 2 p 网络3 中，网 络中没有中心服务器，所有节点都是对等实体，该系统是纯粹的p 2 p 网络。即节点既 可以向其他对等实体发送查询请求并获取查询结果，又可以接收来自其他对等实体的 查询请求并返回请求的文件信息或者将此请求转发给其他对等实体。当某节点加入非 结构化p 2 p 网络时，该节点随机地从现有网络中选取部分节点做为其邻居。当需要检 索网络资源时，节点向邻近节点发送查询请求，该节点检查本地是否存储查询请求的 文件。如果含有请求的资源，该节点给请求源节点回送响应，发送请求的源节点会与 该节点直接建立连接并获取网络资源。无论中间节点是否存储满足查询请求的资源， 节点都会转发查询请求到自己的邻居节点。查询请求经过中间节点转发一次，请求的 路由跳数减一。当跳数为零时，节点忽略该查询请求。 结构化p 2 p 网络也是纯粹的p 2 p 网络。现实生活中，呈现在网络的资源数不胜数， 而在如此庞大的数据库中搜索所需的资源更是困难。因此对资源和节点的物理信息进 行结构化处理，以此来加快搜索速度是有必要的。在结构化p 2 p 系统中，每个节点按 照即定的规则存储一些其他节点信息。当用户需要在p 2 p 系统中查询网络资源时，他 们利用自身存储的信息，逐步转发向目标节点靠近，最终确定目标资源位置。有结构 的p 2 p 网络在一定跳数内，查询请求可以覆盖整个网络，避免了非结构化p 2 p 系统中 洪泛查找方式，提高了信息搜索的效率。这就是说只要网络中存在需要的资源，节点 总能定位到目标节点。 江南大学硕士学位论文 d h t 技术引入p 2 p 系统之后，结构化p 2 p 得到了快速的发展。目前经典的结构 化路由定位算法有c h o r d 4 、c a n 5 、t a p e s t r y 6 、p a s t r y l ，它们资源定位效率高，网络可 扩展性好，纠错能力强。每个节点只需与网络中的少部分节点保持连接，就能在一定 跳数内定位需要的资源，这极大缩短了节点路由表项长度。结构化p 2 p 网络搜索速度 快，产生的查询消息少，资源消耗少，但结构化网络中存在不少影响查询效率的问题。 如由于节点在加入和离开网络时需要进行修复操作，由此产生大量的消息，使得有结 构的网络不能适应高度动态的网络环境；由于所有有关查找和路由的操作都是基于重 叠网络进行的，而没有考虑网络底层的实现，很可能导致重叠网络上的两个邻居节点 在网络层面相距很远，使得原来在重叠网络上一个h o p 的延迟，反映到网络层上会是 更大的延迟；由于对资源和节点物理信息做了结构化处理，必然使资源丢失很属性， 导致在资源定位方式单一，无法实现复杂查询。以及没有考虑节点实际处理能力的异 质性等问题。而且有结构的路由定位算法没能消除p 2 p 网络的安全问题8 9 1 01 1 。随着 计算机网络应用的深入发展，计算机病毒对信息安全的威胁日益增加。特别是在p 2 p 环境下，方便的共享和快速的选路机制，为某些网络病毒提供了更好的入侵机会。在 不安全的网络环境中，新加入节点面临劫持攻击和路由表等攻击；新加入网络节点被 攻击者隔离出真实的网络；被劫持节点无法共享资源和获取网络资源；被劫持节点成 为攻击者的傀儡节点。 1 2 p 2 p 技术国内外研究现状 1 2 1国外相关研究 当前国外比较知名的p 2 p 研究机构有s u n 公司的j x t a 平台1 2 ，莱期大学的 e p o s t 系统等。 ( 1 ) s u n 公司的t a 平台 s u n 公司推出的j x t a 开发平台，j x t a 是j u x t a p o s e 的简称。它定义了构建p 2 p 应用的一个协议通用集合，用于解决现有p 2 p 系统创建非兼容协议时经常出现的问题。 j x t a 的主要目标是定义一种通用p 2 p 网络的重叠网，可以用来实现大范围不同种类 的p 2 p 应用和服务。 在j x t a 中，并列放置的实体是计算设备和计算机组。此标准就是要在系统间和 组间建立临时性的连接变得更容易。j x t a 项目是在j o y 和m i k ec l a r y 的领导下开始 的，他们指导这项开发本着三个核心原则：他们尽可能选择使用熟悉的技术和标准， 寻求行业专家的意见，以及鼓励开放式的开发。 j x t a 具体来说是一种标准组件平台，s u n 公司希望j x t a 能帮助开发人员开发便 于用户在网上查找资源和信息共享的分布式计算机应用软件。在企业层面，不仅可以 使不同企业的应用互操作，还帮助企业更好的利用计算机资源处理工作。在消费层面， 个人可以利用j x t a 平台更好的与个人移动设备信息共享。j x t a 使得可共同使用的 p 2 p 应用程序拥有了更多能力，其中包括：在能简单地穿越防火墙通讯的不同设备的 2 第一苹绪论 用户间建立对等组；在网络上查找对等体的能力甚至穿越防火墙，简化文件共享， 自动侦测新的网站目录，对对等体的远程监控，访问深层网络的数据，以及提供安全 的通讯。 ( 2 ) e p o s t 系统 e p o s t 是一个基于p 2 p 思想的邮件系统，它除了提供现有基于服务器的电子邮件 相同的功能，还有更新的协作应用，如即时消息、共享日历、会议同步等。信息交换 的方式也从以前的以服务器为中心的交换模式转变了端到端的直接通信模式。这种去 中心化的、协作的方法，使整个邮件系统更安全，数据的鲁棒性更好。 1 2 2 国内研究现状 在国内研究机构中比较知名的相关系统有：华科的a n y s e e 、北大的m a z e 、清大 的g r a n a r y 。详细介绍如下： ( 1 ) 华科的a n y s e e 华科设计的视频直播系统a n y s e e 是一对多的服务模式，它利用近播原则以及分 域调度的策略，并采用l a n d m a r k 路标算法构建应用层上的多播树，这种方法克服了 一对多模式中多播树的构造和维护带来的负载影响。 a n y s e e 的第一个版本基于树状结构，该结构便于节点加入到网络中，而且还可以 根据物理距离相近的原则构建i p 多播树，使得节点加入位置都是和自己物理距离相近 的节点，提高了系统的服务质量。 a n y s e e 的第二个版本结合了树状结构和网状结构的优点，采用“控制数据流走树， 媒体数据流走网”的结构，这既保留了树状结构的优点，又能实现一定程度的负载均衡， 并部分解决了树状结构中底层节点和项层节点之间播放时差大的问题。 ( 2 ) 北大的m a z e 北京大学互联网实验室开发的天网m a z e 系统，它是第一代p 2 p 技术和第二代p 2 p 相融合的系统。系统中即有中心控制单元，亦有对等端的相互操作。网络上的一台计 只要安装运行客户端软件就可以自由的加入和退出m a z e 系统，系统成员既可以将自 己的文件共享给系统的其他成员，也可以获取其他成员已经共享过的文件。天网m a z e 根据用户对搜索的兴趣及偏好，采用自有算法，智能提取其搜索的偏好，将用户所需 的信息内容按照更容易被接受的方式例如r s s ( 简易聚类) 呈现，真正做到按需搜索， 按需呈现。同时，天网将教育、在线学习、娱乐等相关服务整和到体系中去，充分发 挥其平台优势。m a z e 支持好友关系，互为好友的对等端可以通过内部共享机制自己交 换文件。 ( 3 ) 清大g r a n a r y 清大开发的g r a n a r y 对等计算存储服务系统和其他已有类似系统相比，有如下两 3 江南大学硕士学位论文 个特点：一、面向对象的数据管理，支持属性级的数据查询，这一点极大地方便了上 层应用系统的开发。二、对于系统环境的自适应性。系统中嵌入了基于p e e r w i n d o w 算法的路由协议t o u r i s t ，用以收集节点信息。无论在怎样的系统规模下，组成节点的 动态性如何，也无论这些节点的能力分布如何，g r a n a r y 都可以自动调节，取得当前 系统环境下的最优性能 ( 4 ) 企业研发产品 腾讯科技( 深圳) 有限公司q q q q 是腾讯科技( 深圳) 有限公司开发基于混合p 2 p 系统结构的即时通讯工具， 个巨大的便捷沟通平台，在人们生活中实践着各种生活功能、社会服务功能及商务j 用功能；并正以前所未有的速度改变着人们的生活方式，创造着更广阔的互联网应j 前景。 广数联软件公司p o c o 广数联软件公司开发的p o c o 是基于第三代p 2 p 技术的信息资源交换平台。p o c 同时还致力于第三代多媒体p 2 p 网络技术的开发、研究与应用，成功开发出的多媒1 资源分享软件p o c o 连续三年成为中国十大最受欢迎软件，也同时成为国内p 2 p 多； 体分享软件第一品牌。 在线视频直播p p s t r e a m p p l i v e q q l i v e u u s e e p p s t r e a m p p l i v e q q l i v e u u s e e 都是基于互联网的视频直播的共享软件。它们使 不同的方法，在各自系统上解决了网络视频点播服务的带宽有限和负载均衡的问题， 实现了用户越多播放越流畅效果，使视频直播服务质量大大提高。 1 3 p 2 p 存在的问题 基于d h t 的结构化搜索算法和基于s m a l lw o r l d 理论1 3 的搜索算法是目前p 2 pj 术研究的热点。但在实际的应用中，还存在一些影响p 2 p 算法效率的因素，如表1 所列出各项因素。 表1 - 1 影响算法效率的因素 t a b 1 1t h ef a c t o r sw h i c he f f e c tp 2 pa l g o r i t h me f f i c i e n c y 影响因素详细介绍 节点的处理能力 在客户服务器模式中，网络节点的计算能力、存储空间、c p u 空 闲资源等不尽相同。但在p 2 p 系统中，对等端做为独立的个体没 有分别的直接参与到系统通信中来，而没有考虑节点的能力问题。 节点所承担的负载应该与节点的处理能力相关，否则这种不加分 4 第一章绪论 别的处理方式会影响路由算法的效率。 网络物理距离在整个p 2 p 技术的发展过程中，无论中采用随机选择邻居的方法， 亦或是结构化选择的方法，他们都隐藏了节点的物理信息，这将 是影响效率的致命因素。节点在网络中的实际位置以及网络中该 节点与其他节点的物理距离都会影响路由算法的效率。 动态网络p 2 p 技术是基于动态网络提出的，整个系统不断有节点的加入、 退出、失败、迁移、并发加入等动作。中心式和无结构分布式p 2 p 网络，因其结构和查询的简单性，使得他们能够较好的适应网络 动态性需求。而结构化网络因其“结构化”，使其面对动态网络时， 性能不尽人意。 语义复杂查询结构化搜索速度快，前提条件必须对资源和物理信息进行结构化 处理，这必然使其丧失很多属性。而在实际的应用中，支持关键 字、语义模糊查询是必须的。终端用户在应用中很少有明确的查 找内容。而结构化查询方法因其对信息进行了结构化处理，而不 能支持复杂查询类型，阻碍新技术的应用与发展。 从国内外近几年来计算机领域的各大会议、期刊，特别是p 2 p 专业会议发表的论 文上看，p 2 p 的研究重点已经从核心机制逐渐转向增强机制，目前的研究主要集中在 以下几个方面：p 2 p 网络中的语义模糊查询、容错性、拓扑意识与一致性问题、声誉 和安全性问题。除此之外，对于p 2 p 模拟、仿真的重视程度也在日渐增加。 1 4 本文研究内容及文章内容 本文针对p 2 p 系统中的一些基本问题进行了研究和实验，包括结构化网络的拓扑 维护、p 2 p 网络安全免疫策略以及p 2 p 应用。本文的主要研究工作如下： ( 1 ) 结构化网络的拓扑维护。基于d h t 的查找系统具有良好的搜索性能，但 d h t 路由方法面临着如负载均匀不易、网络拓扑维护代价大、k e y 的同步维护困难等 固有问题。本文提出一种基于k 桶结构的改进协议，该协议在原有路由表的基础上进 行了“k 桶 结构的改造，用以保存网络动态信息，从而实现按需更新路由表项。这 提高了连接的可用性，减少了系统网络维护的代价，能够适应p 2 p 网络高度动态性的 需要。 ( 2 ) p 2 p 安全免疫策略。通过对自动演化网络所呈现出的网络特性的研究，提出 了局域搜索免疫。在已知邻居节点度的前提下，该策略的主要是通过最大度搜索策略， 搜索并免疫度数大的节点。 ( 3 ) p 2 p 应用。将p 2 p 思想引入到公交查询系统，以站点为对象建立模型。查询 过程通过源端和目的端的信息交互，从而逐步扩大搜索范围，使系统能够快速完成搜 索任务。 本文结构如下t s 江南大学硕士学位论文 第一章：介绍课题的背景、国内外的研究现状以及论文结构。 第二章：介绍了p 2 p 的系统定义、核心机制以及结构化经典模型c h o r d 。 第三章、第四章和第五章是本文的研究工作。 第三章：介绍了基于k 桶结构的动态路径缓存c h o r d 算法具体实现细节。在 不影响其他性能的前提下，该算法目的是为了降低c h o r d 网络拓扑维护代价。 第四章：根据p 2 p 的所呈现的网络拓扑特性，设计了一种新的免疫策略：局 域搜索免疫。已知邻居节点度的前提下，该策略的主要是通过最大度搜索策略，搜索 并免疫度数大的节点。与其它免疫策略相比，该策略可以通过免疫相等或较少的节点 来消灭病毒。 第五章：设计开发了基于p 2 p 思想的公交查询系统。该系统通过源端和目的 端的信息交换，逐步扩大搜索范围，改善查询系统的性能。 第六章：总结全文并对p 2 p 技术的发展做了前景分析。 第二章p 2 p 网络技术 第二章p 2 p 网络技术 2 1p 2 p 系统 一个p 2 p 系统由计算单元组成1 4 ，且满足以下条件： ( 1 ) 由一个网络连接起来 ( 2 ) 以惟一的方式寻址 ( 3 ) 共享一个常规的通信协议 所有计算单元称为节点或对等端，它们具有不同角色并共享对资源的责任和开销。 p 2 p 系统系统必须提供以下四点： ( 1 ) 去中心化 纯p 2 p 系统中没中心控制单元，而是靠每个节点内建的一些规则并利用这些规则 加入系统、发出请求或将信息路由到其他节点。 ( 2 ) 结构 使用户共享的资源按照一定的方式组织起来，以便于以后的查询，这对提高系统 系统是非常有效的。同时对存储节点的有效组织，也可以加快路由查找过程。 ( 3 ) 任凭动态变化的可靠性 p 2 p 系统是基于动态网络的，整个网络处于不断的变化中。在动态的环境中如何 稳定系统整体属性( 如系统直径和连接性) 成为必然。 ( 4 ) 稳定性 在动态环境中系统应该能够向所有节点提供高效而快速的服务。 这些条件表明它们类似于社会网络的特征：社会网络是自组织的，但仍然是有结 构的。 其他随时间而演化的“真实 网络展示出类似的属性，像i n t e r a c t 、新陈代谢网络 ( m e t a b o l i cn e t w o r k ) 或w w w l 5 1 61 7 。不管其动态性，是什么使演化的、去中心化的 网络具有稳定的结构呢? 这取决于演化网络的两个重要属性：小世界效果和规模无关 度分布( 无标度网络) 。具有小世界效果的网络称为小世界网络，具有规模无关度分布 的网络称为规模无关网络。 2 2p 2 p 核心机制 ( 1 ) p 2 p 网络拓扑结构 p 2 p 网络在互联网应用层的基础上构建的覆盖网1 81 9 2 0 2 1 ，它所呈现出来的拓扑结 构对于p 2 p 系统至关重要，系统中的路由与定位算法、查询和搜索、负载均衡、自适 7 江南大学硕士学位论文 应、自组织等都是基于它的。到目前为止，已出现了几十种不同拓扑结构的p 2 p 网络。 表2 1 列举了几种经典p 2 p 覆盖网拓扑结构的各项参数、优缺点。 2 1 各经典拓扑比较 t a b 2 1t h ec o m p a r i s i o no fd i f f e r e n tc l a s s i ct o p o l o g y 分类p 2 p 网络 拓扑结构路由算法 路由效率路由表项节点加入容错 安全 ( 节点度)离开开销性性 n a p s t e r 星形服务器 o ( 1 )o ( 1 ) d ( 1 ) 服务无 混合器单 式点 p 2 p b i t t 0 r r e n t星形 服务器 d ( 1 )d ( 1 )d ( 1 ) 服务一般 网络 器单 点 g n u t e l l a 随机图洪泛法 t t l 很好低 d ( 1 )d ( 1 ) k a z a a 双层结构超节点、良好低 无结 d ( 1 ) + t t 0 ( 1 )d ( 1 ) ( 随机洪泛法 构 l p 2 p 图、星形) e d o n k e y 双层结构服务器、良好 一般 网络 d ( 1 ) + t to ( 1 )d ( 1 ) e m u l e ( 随机洪泛法 l 图、星形) f r e e n e t 随机图基于对象 h t l ( h o p s d ( 1 )d ( 1 ) 很好匿名 的洪泛法 t o l i v e ) c h o r d带弦环 数值邻近 o ( 1 0 9 n )l o g n l 0 9 2n 一般低 路由 c a n 多维空间位置邻近 o ( d d 4 - e ) 2 d2 d良好一般 路由 t a p e s t r y 超立方体后缀匹配 o ( 1 0 9 。忉b l o g bnl o g 占n 良好一般 路由 p a s t t r y 超立方前缀匹配 o ( 1 0 9 口) b l o g 古 l o g 口n 很好 一般 体、环形路由 + h + m 结构 很好 一般 k a d e m l i a基于异或 数值邻近 o ( 1 0 9 n )0 0 0 9 n )o ( 1 0 9 n ) 化 的带弦环路由 p 2 p 很好局部 s k i p n e t 跳表数值邻近 o ( 1 0 9 n )o ( 1 0 9 n )0 0 0 9 n ) 网络 路由、前可控 缀匹配路 8 第二章p 2 p 网络技术 由 v i c e r o y 蝴蝶网、蝴蝶路 o ( 1 0 9 n ) 7 l o g n 一般低 环形由、环形 路由 k o o r d e d eb r u i j nd eb r u i j n o ( 1 0 9 n ) 4 l o g n 一般低 图、环形 路由、环 形路由 c y c l o i d c c c 、环c c c 路 o ( 1 0 9 n ) 7 一般低 l o g n 形由、环形 路由 ( 2 ) 路由和定位算法 路由是指当某一节点收到来自其他节点的信息时，查看该信息的索引部分，并根 据本地存储的转发列表，将信息从适当的接口转发出去或者将信息转发给按某种规则 相近的某个节点上。 定位则是指根据目标对象确定目标节点的过程。在p 2 p 网络中目标资源的定位过 程是通过中间节点的一步步路由来实现的，即路由是定位的基本步骤2 2 。路由和定位 算法取决p 2 p 系统的两个重要因素：覆盖网拓扑结构和路由表结构。基于结构化的p 2 p 网络采用局部贪心算法，搜索效率高。无结构分布式p 2 p 网络通常采用路由索引、洪 泛法、局部探测或其融合改进方法等进行路由，其效率不高。而且由于这些方法带有 很大的随机和局部性，无法确保资源定位成功。 ( 3 ) 查询和搜索 查询根据指定的内容来定位。可以指定目标对象的确切内容。当目标内容不明确 时，可以指定与其相关的几个关键字，这就是搜索，即模糊查询。结构化p 2 p 仅支持 精确查询，这是结构化方法的优势；但在实际应用中，模糊查询比精确查询更实用， 有更广阔的发展空间。无结构p 2 p 网络支持模糊查询，但却受制于无结构网络的查询 效率。表2 2 列举了现有的p 2 p 网络搜索技术，表2 3 列举了它们之间的性能比较。 表2 - 2 p 2 p 网络搜索技术 t a b 2 - 2p 2 pn e t w o r ks e a r c ht e c h n o l o g y 网络类别技术特点 第一代p 2 p 网络依旧采用传统c s 模式，只是中心服务器的功能发 生了变化。与传统的中心服务即是资源管理存储中心的模式相比，第 一代p 2 p 网络中心服