（计算机应用技术专业论文）基于多局域、聚态的p2p搜索与拥塞控制模型研究.pdf

摘要 摘要 p 2 p ( p e e r - t o p e e r ) 技术的大量应用对目前的网络应用提出了巨大挑战，它的p e e r 端 平等性，正在带来因特网的革命，而基于p 2 p 网络的搜索效率研究是推动p 2 p 网络进 一步发展的关键问题，i n t e l 公司和i b m 公司每年都花费巨大的资金进行研究，因为它 在商业上的应用有很大的空间，很多领域尚未探索，像企业资源的优化配置，企业管 理的高效等。在软件发展上，带来了协同软件技术发展的快速进步，这所有的一切都 要基于p 2 p 网对资源的高效搜索和高效利用，而目前像g o o g l e 搜索引擎对资源的召回 率不到1 3 。随着越来越多的数据存储到p 2 p 系统中，上层应用就需要底层构架来提供 关键的数据定位和搜索能力。 本文旨在研究一种新的p 2 p 搜索和拥塞控制模型，论文阐述了p 2 p 搜索技术目前 的研究背景和发展状况，并且对一些典型的模型和算法进行了详细分析，指出了它们 的优点及存在的不足。通过对m l w ( 多局域世界) 模型、w s 小世界模型、n w 小世 界模型的研究，提出了一种搜索控制模型：基于多局域、聚态的p 2 p 搜索模型。研究 了产生的拥塞现象，对p 2 p 搜索模型进行优化，提出了一种拥塞控制解决方案。 目前的p 2 p 搜索根据其拓补结构主要分为泛洪和随机漫步两种，本文提出的 m r w 模型在逻辑上是一种半结构化拓补结构，其给所有p 2 p 资源节点按照资源特 性、物理路径进行分类，建立一种聚态的、多局域世界。论文给出组内搜索、组间搜 索具体的算法，通过组关系的建立解决动态网络环境问题，对在搜索过程中的拥塞现 象给出了控制算法。在资源传输过程中产生的拥塞问题，根据最少优先片段选择原则 确立了一种具体的拥塞控制算法。通过网络特性的公式推导，从最短路径、聚类特性 分析了模型的可行性，优越性。其中在动态网络环境下对系统的状态更新方法是本文 的重要创新，对搜索和拥塞控制的综合考虑，也是论文研究的难点区域。最后，通过 一些实验数据对模型的网络特性进行了比较，并对模型的应用进行了介绍。 最后，通过一些实验数据对模型的网络特性进行了比较，对模型的应用进行了介 绍。 关键词：p 2 p 搜索、m l w 模型、小世界、m r w 模型、聚态、拥塞控制、泛洪、 动态网络、分布式哈希表 a b s t r a c t a b s t r a c t p 2 pt e c h n o l o g y sm a s s i v ea p p l i c a t i o np r o p o s e dt h eh u g ec h a l l e n g et ot h ep r e s e n t n e t w o r ka p p l i c a t i o n i t se q u i v a l e n to ft h ep e e re x t r e n i t yi sb r i n g i n gt h ei n t e m e tr e v o l u t i o n a n dt h er e s e a r c ho fn e t w o r ks e a r c h i n ge 伍c i e n c yb a s e do np 2 pt e c h n o l o g yp r o m o t e dt h em o r e d e v e l o p m e n to fp 2 pn e t w o r k b e c a u s eo fi t sw i d e s p r e a da p p l i c a t i o ni nc o m m e r c ea n dt h e b l a n ke x p l o r a t i o ni nm a n yd o m a i n s 1 i k eo p t i m i z ec o l l o c a t i o no fe n t e r p r i s er e s o u r c ea n dh i g h e f f e c to fb u s i n e s sm a n a g e m e n t ，t h ei n t e ra n di b mc o r p o r a t i o n ss p e n tv a s tc a p i t a lt or e s e a r c h e v e r yy e a r i ta l s ob r i n e dt h ef a s tp r o g r e s so fc o o p e r a t i o ns o f t w a r et e c h n o l o g y , a n dp 2 p n e t w o r ks e a r c h i n ga n du s i n gt h er e s o u r c ee f f i c i e n t l yh i g h l yi sa ni m p o r t a n tf a c t o r , b u tt h er a t e o fr e s o u r c er e c a l l i n gi sv e r y1 0 w , l i k et h eg o o g l eo n l y1 3 n o wm o r ea n dm o r ed a t ew i l lb e s t o r a g e di n t op 2 p t h es u p e ra p p l i c a t i o n sn e e dt h eb o t t o mt u r s st op r o v i d et h ea b i l i t yo fp i v o t a l d a t eo r i e n t a t i o na n ds e a r c h i n g t h i sd i s s e r t a t i o ni sm a i n l yf o c u s e do nan e wm o d e lo fp 2 ps e a r c h i n ga n dc o n g e s t i o n c o n t r o l l i n g a tf i r s t ，t h ep a p e rb r i e f l yi n t r o d u c e st h eb a c k g r o u n da n dt h ed e v e l o p m e n t c o n d i t i o n so ft h ep 2 ps e a r c h i n gt e c h n o l o g y , t h e np a r t i c u l a r l yd e p i c t ss e v e r a lt y p i c a lm o d e l a n da r i t h m e t i c s a n dd i s c u s s e st h e i rm e r i t sa n ds h o r t a g e s c o m b i n i n gw i t ht h em l wm o d e l w ss m a l lw o r l dm o d e l n ws m a l lw o r l dm o d e l i ti n t r o d u c e sas e a r c h i n gc o n t r o lm o d e l 一 p 2 ps e a r c h i n gm o d e lb a s e do nm u l t il i m i t sg a t h e r i td e p i c t sa n da n a l y s e st h ep h e n o m e n ao f c o n g e s t i o n , o p t i m i z e st h ep 2 ps e a r c h i n gm o d e l ，a l s op r o v i d e sas o l v ep r o j e c tt oc o n g e s t i o n c o n t r o l l i n g c u r r e n t l y , t h ep 2 ps e a r c h i n gm a i n l yi n c l u d ef l o o da n dr a n d o mw a n d e rb a s e do n t o p o l o g i c a l t h es t r u c t u r eo fm r wm o d e li sh a l ft o p o l o g i c a l a 1 lp 2 pr e s o u r c en o d e sa r e c l a s s e da c c o r d i n gt ot h er e s o u r c ec h a r a c t e r i s t i ca n dp h y s i c sr o u t e s a n di tb u i l d sag a t h e r e d m u l t il i m i t sw o r l d p r o v i d e sm a t e r i a ls e a r c h i n ga r i t h m e t i cf o rs e a r c h i n gi ng r o u pa n da m o n g g r o u p ，r e s o l v e st h eq u e s t i o no fd y n a m i cn e t w o r ke n v i r o n m e n tb yt h eb u i l d i n go fg r o u p c o n n e c t i o n i n t r o d u c e st h ec o n g e s t i o nc o n t r o l l i n ga r i t h m e t i c a n dam a t e r i a la r i t h m e t i ct ot h e q u e s t i o nw h i c hi sp r o d u c e di nt h ep r o c e s so fr e s o u r c et r a n s m i s s i o n w h i c hi sf o u n db yt h e f u n d a m e n t a lo fl e a s tp r i o r i t ys e g m e n tc h o o s i n g t h e ni td e d u c e st h en e t w o r kc h a r a c t e r i s t i c f o r m u l a s ，a n a l y s e st h ef e a s i b i l i t ya n da d v a n t a g ea b o u tt h es h o r t e s tp a t ha n dg a t h e r c h a r a c t e r i s t i c t h er e n o v a t i n gm e t h o do ft h es y s t e ms t a t ei nt h ed y n a m i cn e t w o r k e n v i r o n m e n ta n di n t e g r a t ec o n s i d e r i n gf o rs e a r c h i n ga n dc o n g e s t i o nc o n t r o l l i n ga r et h es p o to f i n n o v a t i o n ，a n da l s oan o d u s f i n a l l y , av a r i e t yo fe x p e r i m e n t a t i o n sa r eg i v e nt oc o m p a r ea n dd e m o n s t r a t et h e e f f e c t i v e n e s so ft h em e t h o d ，i n t r o d u c e st h ea p p l i c a t i o no ft h em o d e l k e y w o r d s ：p 2 ps e a r c h ；m l wm o d e l ；s m a l lw o r l d ；m r wm o d e l ；c l u s t e r i n g ；c o n g e s t i o n c o n t r o l l i n g ；f l o o d i n g ；d y n a m i cn e t w o r k ；d i s t r i b u t e dh a s ht a b l e ( d h t l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含本人为获得江南大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 期：纱莎。 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的 规定：江南大学有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的 内容相一致。 保密的学位论文在解密后也遵守此规定 签名： 导师签名： 日 期： z 一，哥l盎 第一章绪论 第一章绪论弟一早珀下匕 1 1 概述 随着互联网应用的爆炸增长，c s 与b s 构架给服务器带来了瓶颈，虽然i b m 等服 务器生产厂商在不断地提高服务器的性能、运算速度，但是和网络应用的增长比起 来，仍然显得相形见绌。其实这主要是由其构架的星型结构所导致，资源全部集中在 服务器端，经常性发生网络拥塞，网络响应速度也随之变慢，但是在客户端之间的数 据流几乎为0 ，造成网络流量的严重不均衡。对等( p e e r - t o - p e e r ，p 2 p ) 模型就是在 这种背景下逐渐走向网络应用的舞台。 1 9 9 9 年n a p s t e r n 3 问世以来，p 2 p 模型已经在诸如文件共享、广域网存储、视频播 放和分布式目录服务器等因特网应用中被广泛采用。在p 2 p 网络中，节点既是服务和 资源的使用者，也是提供者，给服务器带来了革命性的“解放 ，网络流不再集中在服 务器端，而开始在各节点端分布，通过在各个节点之间建立多个t c p 连接来实现分布 式的数据传输，提高了吞吐量和网络利用率，优化了业务流量性能，实现了流量的分 布化。节点在使用网络中的共享服务与资源之前，首先需要定位所需服务或资源在网 络中的位置，因此搜索技术成为p 2 p 技术研究与发展中的关键技术之一。同时随着b t 等一系列p 2 p 应用的兴起，网络流量犹如洪水到来，各营运商正在面临巨大的网络压 力。大量带宽的占用，使网络拥塞变的越来越频繁，但是如果封杀p 2 p ，不仅仅有违反 电信法的嫌疑，而且就是在路由器中大量加载p 2 p 应用封堵模块，也将会极大地降低 路由器的性能，最终会导致网络不可用。因此如何有效地实行拥塞控制，平衡p 2 p 流 量就成为必须解决的难题。目前对于p 2 p 的搜索主要还是以d h t ( 有结构) 和泛洪 ( 无结构) 为基础，但是仍然很难解决网络带宽巨大消耗的问题。在大量p e e r 端动态 更新的时候，就很容易造成网络拥塞。 p 2 p 搜索技术的发展从最初w a t t s 和k l e i n b e r g 的广播搜索堙1 ；到y a n g 和g a r c i a m o l i n a 的迭代加深( i t e r a t i v ed e e p e n i n g ) 方法口3 与有向广度优先搜索( d i r e c t b f s ) 方法旺1 ，及本地索引搜索方法口3 ；到a d a m i c 等人提出的基于节点度分布的改进搜 索算法和利用节点度的幂率分布特性来搜索的算法嘲h 3 ，目标都是为了得到更短的平均 路径长度和良好的度分布。 例如利用最大度搜索应用如图i - i ，其中方格的实线为利用邻居及邻居的邻居来进 行搜索，x 为只利用直接邻居的信息进行搜索，这是在一个大约7 0 0 个节点的实际 g n u t e l l a 网络上实现这一搜索算法的。假设每个文件都只存放在一个节点上。那么 5 0 的节点能够在8 步或者更少的步数内寻找到，如果某个节点所需的文件在多个不同 的节点上都存在，那么搜索会更迅速。 江南大学硕士学位论文 貉 却i 靼 墨 列 匠 侣 ：b 碥 图1 - 1g n u t e ll a 网络上查询过的节点数h 1 f i g 1 16 n u t e ll an e t w o r kh a ss e l e c t e dp e e r s 这些算法局部改善了搜索的效率，但是没有考虑网络的动态结构与后续应用保 持，及如何同时建立拥塞控制机制。在实际的网络应用中还是会产生大量的拥塞流 量，不能进行很好的o o s 保障。 1 2 研究背景和意义 p 2 p 技术是在个人计算机之间直接进行资源和服务的共享，而不像传统的客户端 服务器( c s ) 结构那样需要经过服务器的介入和服务。在p 2 p 结构中，每台计算机同 时充当服务器和客户端的角色，当需要其他计算机的文件或者服务时，两台计算机直 接建立联系，本机是客户端，而响应其他计算机的资源要求时，本机又成为提供资源 与服务的服务器。通常这些资源和服务包括：文件的共享与交换、计算资源如c p u 的 共享使用等。在过去的几年及未来的几年，p 2 p 技术会一直是计算机界关注的热门话题 之一，财富杂志更将p 2 p 列为影响i n t e r n e t 未来的4 项科技之一，p 2 p 技术能广泛应 用的关键在于用户能获得较高质量的服务。 目前，p 2 p 网络中存在着三种不同的基本结构：l 、集中式的p 2 p 系统嫡1 ，每一个 节点将自身能够提供共享的内容注册到一个或几个集中式的目录服务器中，查找资源 时首先通过服务器定位，然后两个节点之间再直接通信，代表系统有早期的n a p s t e e r 系统，显然，即使是在一个很大的网络中，通过中心服务器来寻找有用的信息也是非 常方便快捷的，但显而易见，设置一个中心服务器成本是相当高的，并且还可能涉及 版权、隐私等问题，同时也比较脆弱。2 、分散式的结构化p 2 p 系统畸1 ，结构化系统意 味着文件的分布和网络拓补紧密相关。文件并不是分布在随机的节点上，而是按照确 切的地址分布在网络中。在松散结构化p 2 p 系统中，每个节点都分配有虚拟的逻辑地 址，但整个系统仍然是松散的网络结构。文件的分布根据文件的索引分配到相近地址 的节点上，代表系统有f r e e n e t 。在高度结构化的p 2 p 系统中，每个节点都具有虚拟的 逻辑地址，并根据地址使所有节点构成一个相对稳定而紧致的拓补结构。在此拓补上 2 第一章绪论 构造一个存储文件的分布式哈希表d h t ，而文件根据自身的索引存储到哈希表中，每次 检索也是根据文件的索引在d h t 中搜索相应的文件。3 、分散式的非结构化p 2 p 系统 瞄1 ，这类系统文件的分布和网络拓补松散相关，典型的有g n u t e ll a 系统，节点通过简 单的规则加入网络，整个网络的拓补结构服从一定的特性，但是节点的分布与拓补结 构无关，这类系统一般通过广播或者受限广播来进行资源定位，具有较好的自组织性 和扩展性，适用于互联网个人信息共享，缺点是稀疏资源的召回率低。由于分散式的 非结构化p 2 p 系统有着很大的i n t e r n e t 用户群，所以这里研究的主要是分散式的非结 构化p 2 p 系统。 在非集中式的p 2 p 系统中，如何更快更高效的获得资源成为目前p 2 p 研究的重 点，同时网络节点的快速动态更新及视频资源的大量应用，使网络基础变得越束越脆 弱不堪，如何建立一高效疏导的“交通 机制也显的尤为紧迫。作为从完全规则网络 向完全随机图的过渡，n e w m a n 和w a t t s 提出的n w 小世界模型，这个模型对于非集 中式p 2 p 网络特性的研究具有很重要的意义，当一个新的节点加入到一个区域网络 时，它对于其他区域网络的影响很小，但反过来它要受本区域网中节点的影响，p 2 p 网络具有这样的特性，我们可以利用n w 模型来构建p 2 p 网络哺1 。如果我们引入语义 的概念，将相应的资源根据语义进行分类，那么区域网将变成一个个“局域世界，现 在我们可以构造一个m r w ( m u l t i r e s o u r c e - w o r l d ) 模型，这样整个p 2 p 网络就由一个 个小世界组成，对p 2 p 的聚态生成有很好的帮助。 在大量流量产生时，网络会变的非常脆弱，在p 2 p 所产生的拥塞控制方面。目前 还没有很好的模型和算法，而p 2 p 网络所产生的拥塞主要是由于负载不稳定所造成 的，如果我们加入邻居节点负载信息与依赖系统整体负载信息这两种信息，可以构造 一种局部调度算法，可以估计它能快速的使网络达到负载平衡，并提供较好的服务质 量。 1 3p 2 p 搜索技术的特点与发展 基于p 2 p 的搜索方法与目前其他各种传统搜索方法相比，其最大优势在于应用了 先进的对等搜索理念，可不通过给定的中央服务器，也可不受信息文档格式和宿主设 备的限制，对互联网络进行全方位的搜索。p 2 p 网络模式中节点之间动态而又对等的 互联关系，使得搜索可以在对等点之间直接地、实时地进行。 在分布式环境中网络资源的发布通常有两种途径：一种是由资源提供者发布所提 供资源的描述，然后由资源需求者在需要时从众多资源描述中选取所需资源；另一种 途径是由资源需求者发布对所需资源的描述，然后由资源提供者来匹配需求并响应需 求者。而具体实现方法可根据搜索与资源内容的相关性分为内容无关搜索和基于内容 的搜索。在内容无关搜索中，资源的存放和搜索与资源的内容无关。如中央搜索模 型、泛洪请求模型等。 在如g n u t e l l a 这类非结构化p 2 p 网络中，起初采用的用广播形式进行的广度优先 搜索算法，指定一个生存时间t t l ( t i m et ol i v e ) ，当t t l 为0 时，搜索自动停止，这 种方法十分的高效，用户可以在很短的时间内找到所需的目标文件，但是这样的处理 江南大学硕十学位论文 方式会在网络中产生大量查询数据流量，很容易形成网络流量阻塞，特别是一些使用 慢速m o d e m 的计算机和过时的计算机会在网络中形成网络瓶颈，大大降低软件的可实 用性。后来y a n g 和g a r c i a m o l i n a 借用了人工智能里的迭代加深( i t e r a t i v ed e e p e n i n g ) 方法并将之应用在p 2 p 网络中，这种方法也叫扩展环( e x p a n d i n gr i n g ) 方法，这种方 法的缺点是不能减少消息的复制，并且查询的过程也比较慢，后来两个人又提出了有 向广度优先搜索( d i r e c tb f s ) ，基本思想是源节点选择一些能够快速返回高质量结果 的邻居并将查询消息发给他们，这些邻居接下去进行广度优先搜索，这样使查询的成 本大大的降低。但是这种搜索方法查询结果的质量并没有下降，查询消息的流量仍然 很大。为了减少搜索的流量提出了k 遍历器随机游走算法，但是搜索速度却大大的降 低了。 接着又提出了混合式搜索算法，知名资源通过泛洪方式，稀有资源借助于d h t 的 有结构搜索算法，g a b 混合式搜索算法是一种更加智能的设计，但是对于混合式搜索 算法，搜索效率和质量主要取决于其搜索决策的正确性。查询不恰当地被发送到d h t 或被泛洪都会导致系统效率和搜索质量的下降。一个稀有资源的查询被泛洪后，不仅 会导致带宽浪费、响应时间增加，还可能产生不能命中的后果，而一个知名资源的查 询被不恰当地采用d h t 搜索时，可能产生响应时间增加和有效应答数减少的后果。 1 4 主要工作与论文结构 1 4 1 本文的主要工作 我国由信产部电信研究院主办的“中国宽带应用发展论坛暨中国t r i p l e p l a y i p t v 论坛”上，中国科学院声学研究所研究员侯自强为首的一些科学家提出 i p t v 未来必会被p 2 p 所替代，p 2 p 将在2 1 世纪成为最重要的网络应用技术的论断。目 前国内的p 2 p 搜索引擎如百度公司仍然是以中心索引服务器为中心的构造方法，具有 很弱的健壮性，稳定性，和高成本，p 2 p 的视频应用仍然会造成严重的网络拥塞。在理 论研究上提出了如语义网搜索模型，混合式搜索模型，但是在解决网络拥塞问题上都 没有很好的表现，网络的可扩展性不能很好的解决。现有的p 2 p 搜索主要是以d h t 和 泛洪两种结构，仍然很难适应动态网络的环境，大量的搜索和状态更新流量产生仍然 给网络带宽带来了压力，q o s 服务质量仍然还不能达到满意的效果。s e m a n t i c p 2 p 模型 能够获得满意的资源定位性能，有较好的鲁棒性和可扩展性，但是对于动态的p 2 p 网 络还是不能很好的解决网络拥塞问题。也有人提出在p 2 p 的资源搜索上综合利用d h t 和泛洪的特性来研究，但是它不能适应动态性较强的p 2 p 应用，而且资源的召回度不 - - l 一 两。 我们所构造的m r w 模型可以这样构造：在组建网络方面，假设有m 个孤立的 r e s o u r c ew o r l d ，这个孤立的世界有m o 个节点，e 0 条边，可以有如下操作( 1 ) 增加 一个有m 1 个节点，e 1 条边的r e s o u r c ew o r l d ；( 2 ) 增加一个新的节点到存在的 r e s o u r c ew o r l d ，它与同一个r e s o u r c ew o r l d 建立i i l 2 条边；( 3 ) 增加m 3 条边到一个 选定的r e s o u r c ew o r l d ；( 4 ) 在一个选定的r e s o u r c ew o r l d 中与其他已存在的 r e s o u r c ew o r l d 建立m 4 条长程边。( 5 ) 在一个选定的r e s o u r c ew o r l d 中去掉m 5 条 4 第一章绪论 边。在构造时满足如下要求：( 1 ) 不是每一个节点都需要连接到其他的r e s o u r c e w o r l d ；( 2 ) 每一个节点需要知道或者很容易知道连接到其他r e s o u r c ew o r l d 的节点； ( 3 ) 连接到其他r e s o u r c ew o r l d 的节点不能集中在一个或少数几个上，要在w o r l d 中平均分配。搜索资源时，采用查询邻居最大度的机制搜索。传送资源时只在一个 r e s o u r c ew o r l d 中调用相应资源，使用分片传送，对资源采用按路径长度依次调度。 本文提出一完整的资源搜索、拥塞控制模型，即基于分布式哈希表搜索的多局域 聚念系统模型( m u l t i - r e s o u c e - w o r l dm r w ) ，采用小世界网络模型的特性对其资源聚 态特性、搜索效率、平均路径长度进行分析比较，对在动态资源环境下的表现状态、 稳定性、网络流量进行综合分析，最后对其拥塞控制进行论述分析。 1 4 2 本文结构 第一章绪论，主要对p 2 p 构架进行归类，及目前的p 2 p 搜索及拥塞问题做一些简 单的描述，最后对目前的一些搜索技术及发展做一些分析和介绍。 第二章p 2 p 网络理论及现存搜索算法分析，详细介绍p 2 p 网络的应用机制，及研 究分析现有的一些搜索算法，了解它们的优点和缺点。 第三章相关网络模型理论，主要介绍了复杂网络中多局域世界模型的机理和应用 和小世界网络模型，根据本章的模型分析，介绍了几种有代表性的小世界模型，。包括 w s 和n w 小世界模型，及在小世界模型中的统计性质，主要有聚类系数、平均路径长 度、度分布。 第四章多局域聚态系统模型( m u l t i r e s o u c e w o r l dm r w ) ，主要介绍m r w 模型的 理论基础、模型构架、具体策略。 第五章m r w 模型分析比较与应用，与其他的一些正在研究的模型，搜索策略进行 分析比较，并对其未来的具体应用进行研究，特别是在资源共享，协同工作上的应用 进行探讨。 第六章总结及未来工作展望，总结所做的工作、研究重点，可能存在的不足，及 建议改进策略，特别是在动态资源环境下的进一步优化，及拥塞控制的进一步研究思 路和设想。 5 江南大学硕士学位论文 第二章p 2 p 网络搜索技术及目前搜索算法分析 p 2 p 系统本质上也是一个分布式系统，同时它也具备着一些区别于传统分布式系统 的特色，更强调自组织、对等、动态的特性。其按搜索技术的应用主要有非结构化 p 2 p 网络、结构化p 2 p 网络、集中式的p 2 p 网络，根据其结构特点在各种结构下的搜 索技术都有各自的优点，也有各自的缺陷与不足。搜索按功能一般又可以分为数据定 位和关键词搜索，按照不同的功能，在不同的网络逻辑构架上，p 2 p 搜索的效率又有 所不同，在消息路由方面来说，结构化网络中一般基于d h t 来构造的各种路由方法， 在非结构化网络中，一般使用的是泛洪或者随机漫步盯3 ，集中式的依靠中心索引就可以 了。 2 1p 2 p 业务流量分析 p 2 p 技术采用分布式对等网络体系，通过在各个节点之间建立多个t c p 连接来实 现分布式的数据传输，提高了吞吐量和网络利用率，优化了业务流量性能，实现了流 量的分布化，本节将分别从p 2 p 流数量、服务器负载、网络瓶颈点分布、往返时间 ( i 册) 的异构分布来分析p 2 p 业务流量特性。 1 、从流量数来看 p 2 p 业务为了提高数据获取速率，通常并发启用多个t c p 连接同时从多个p 2 p 节 点进行双向数据传输。当p 2 p 应用和传统基于单t c p 应用( 大部分基于c s 、b s 架 构的应用) 竞争时，p 2 p 应用将占据绝对优势。因此当p 2 p 应用建立的t c p 连接愈 多，其占用的网络资源也愈多。当网络瓶颈点发生拥塞时，由于t c p 拥塞控制机制使 得各t c p 流之间能够较为公平的共享瓶颈带宽，但采用多t c p 连接的p 2 p 流量会使采 用单个t c p 连接的传统的i n t e r n e t 应用退避更多，从而相对单个t c p 连接得到的吞吐 量高得多，使其具有非常强大的带宽资源侵略性。 2 、从服务器负载来看 在p 2 p 网络中，p 2 p 节点之间直接进行数据和服务交换，从而打破了传统的c s 模式，弱化了服务器的作用，甚至取消服务器。在p 2 p 网络中，每个节点的地位是对 等的，具备客户端和服务器双重特性，可以同时作为使用者和服务提供者。使得数据 存储模式由“内容位于中心 模式转变为“内容位于边缘 模式，改变i n t e m e t 现在的 以大网站为中心的资源集中状态，重返“非中心化 ，使信息数量、成本资源都向互联 网各端点均匀分布。消除了c s 模式的网络中因负载繁重的服务器引起的服务瓶颈问 题。 3 、从网络瓶颈点分布来看 在传统的c s 架构中，客户端和服务器之间仅存在一条路径，因此具有共同的网 络瓶颈点。对于多连接c s 应用，这些连接将在共有的网络瓶颈点相互影响，相互干 扰，其总吞吐量受到网络瓶颈点剩余带宽的限制。瓶颈路由器会将这些同源同目的的 流作为同质的流聚合为一条流进行转发，因此其吞吐量受到严重限制。 6 第二章p 2 p 网络搜索技术及目前搜索算法分析 p 2 p 用户同时和多个节点进行数据交换和传输，每个节点之间存在不同的路径， 因此网络瓶颈点的单一性转变为分布性，消除了p 2 p 流之间的相互干扰，提高了p 2 p 流的总吞吐量，从而能够更好地利用网络资源，提高网络利用率。 4 、从i m 的异构分布来看 t c p 机制对于不同l 册流存在不公平性，l 册较小的连接将得到更高的吞吐量。 在传统的c s 架构中，客户端和服务器之间仅存在一条路径，即使有多个连接，其传 播时延也是确定的，当网络拥塞时，流将在网络瓶颈点排队，导致r 1 广r 增大，从而降 低了流的吞吐量。而p 2 p 用户和节点之间存在多条路径，每条路径存在不同的传播时 延。r 广r 小的流会尽其最大能力传输数据，从而提高p 2 p 流的总吞吐量。如果某个网 络瓶颈点发生拥塞，导致r 1 r t 增大，p 2 p 用户可以去选择从性能更好的节点取得数 据。因此p 2 p 机制将具有更大的灵活性和高效性。 2 2 搜索算法介绍及分析 在集中式搜索算法中，建立一中心服务器保存索引信息，所以节点通过中心服务 器进行搜索，这种方法不能很好的表现p 2 p 网络的特性，这里主要介绍结构化p 2 p 网 络和非结构化p 2 p 网络的搜索算法。 2 2 1 结构化搜索算法 在结构化的p 2 p 网络模型中，使用d h t 方式阳h 1 1 1 覆盖全网，确保每一个查询都是 有限步，这种方式基于一种假设，那就是节点和资源都是可用的，因此它们在频繁有 节点加入和退出的环境下工作的并不能让人满意。但是其较高的搜索效率还是很有借 鉴意义的，在使用d t t t 方法的系统中，每个节点都有一个唯一的标示，这个标示是根 据资源对象的关键字( 通常是资源对象的某项属性值，如文件名等等) 通过某种哈希 函数的值标示。一般资源对象标示和节点标示属于相同或相似的名字空间，每个节点 负责资源对象标示的名字空间中的一部分。p 2 p 系统网络拓补是根据节点标示构造的， 并且每个节点都维护一个“路由表 ，保存相关邻居节点的标示信息。d h t 消息路由过 程与i p 路由的过程相似，每个节点根据其“路由表 将消息转发到相应的邻居节点上 直到消息最终到达目标节点。d h t 方法还提供了与哈希表类似的两个抽象操作：发布和 查找。资源发布时，根据资源对象的k e y 通过哈希函数得到一个o b j e c t i d ，然后根据 名字空间中的某种度量准则，通过d h t 消息路由将资源发布到标示与o b j e c t i d 最接近 的节点上。当资源搜索时，d h t 方法根据关键字得到其目标o b j e c t i d ，然后通过d h t 消息路由，到达其标示在名字空间中与目标o b j e c t i d 最近的相关节点，返回搜索结 果。 如c h o r d 搜索策略，其基本操作就是发布关键字k e y ，把k e y 和存储这种相关资源 的节点关联起来，例如：文件或者是节点提供的服务等等。根据这里的应用特性，可 以知道系统中的每个k e y 就代表相应节点提供的资源或者是服务。为了将这些k e y 映射到节点上，其使用o n s i s t e n th a s h i n g ( 一致性哈希) 睛1 。这种哈希方法可以警示的 给每个节点分配相等数量的k e y ，一致性哈希函数根据节点的i p 地址和k e y 值分别给 每个节点和k e y 一个m 位的2 进制标示，这些标示都属于一个能够被2 m 整除的环形标 7 江南大学硕士学何论文 示空间，叫做c h o r d 环咖。对于k e y 的分配原则是将它分配给标示等于或者是接下来的 第一个标示小于k e y 的标示的节点，这样的节点叫做这个k e y 的后继节点。 c h o r d 中每个节点和它的后继节点都具有邻居关系。在c h o r d 环上只要沿着后继节 点总可以正确的到达任何目标，这种方法的效率特别低下。因而c h o r d 中的每个节点 都可以维护一个f i n g e r 表，f i n g e r 表最多可以维护m 项信息，节点n 的f i n g e r 表第 i 项是存储的值为珂+ 2 卜1 节点标示。资源搜索的时候，每个节点都通过查询f i n g e r 表，将搜索请求转发到离k e y 最近的节点上。 c h o r d 方法的节点度数为o ( 1 0 9 n ) ，路由延迟和路由消息开销是o ( 1 0 9 多) ，平均路 由延迟为1 2 * l o g 多，动态维护开销0 0 0 9 d ，具有良好的特性。 2 2 2 非结构化算法 非结构化p 2 p 系统中的资源定位技术口2 3 不需要任何关于节点和节点上资源的可用 性假设，也不像结构化的p 2 p 系统那样，严格的约束资源在系统中的存放位置，对于 非结构化的p 2 p 系统中的资源定位技术，主要就是两大类：泛洪和随机漫步。 对于泛洪资源搜索技术来说，就是依靠节点广播查询消息来搜索资源，而且在每 个节点中这种消息的路由并不是有计划的，而是盲目的泛洪，这样虽然可以很快找到 要搜索的目标，但是会带来大量的搜索流量。 迭代加深方法就是初始时，源节点以一个小的t t l 进行广度优先搜索，然后等待 搜索是否成功，如果成功，则停止搜索，否则节点增加t t l ，并重新开始广度优先搜 索，重复这个过程一直到目标文件找到或者t t l 达到一个上限d 为止。在后面这种情 况，搜索不一定能够成功。为了实现迭代加深技术，每个节点都使用同样的t t l 序 列，称为策略p ，其中周期w 为两次广度优先搜索之间的间隔时间。 例如，假设p = 3 ，5 ，8 ) ，w = 6 s 。源节点s 首先进行t t l = 3 的广度优先搜索，与s 的距离在3 步之内的节点，即深度在3 之内的节点都会收到查询消息，并且会临时将 消息存储起来。这些节点中存有s 所需的那些节点会将文件返回给s 。如果在w = 6 s 内 s 收到了所需的文件，则中止搜索；否则，如果距s 的深度在3 之内的节点中没有它所 需的文件，或者文件没能在6 s 之内传递至s ，则s 将开始下一步的迭代，进行深度为 5 的广度优先搜索，并且发送重发消息。距s 的深度在2 之内的节点，在收到这个重发 消息时不作任何处理，而直接向前传给它们的邻居。而与s 的深度为3 的节点将重发 消息丢弃，并将与重发消息对应的查询消息激活，进行深度为2 的广度优先搜索。如 果搜索仍未成功，那么由于8 是策略p 的最高迭代级别，因此与s 的距离在8 步之间 的邻居不再存储查询消息。并且不管搜索是否成功，s 都将不再进行进一步的迭代。迭 代加深方法的缺点是不能减少消息的复制，并且查询的过程也比较慢。 另一种方法是有向广度优先搜索，其搜索策略是源节点选择一些能够快速返回高 质量结果的邻居并将查询消息发给它们，这些邻居接下去进行广度优先搜索，为了更 有效地选择邻居，每个节点存储了它的邻居的一些简单的统计信息，如以前查询通过 每个邻居得到所需结果的数量，或者邻居的连接延时等。通过这些统计信息，可以通 过以下的方法有效地选择最好的邻居节点： 8 第二章p 2 p 网络搜索技术及目前搜索算法分析 1 、选择在以前的查询中返回结果数量最多的邻居。 2 、选择返回的消息的平均步数最少的邻居，也就是选择与存储着有用的文件或数 据的节点最近的邻居。 3 、选择传递查询消息最多的邻居节点，因为传递查询消息越多意味着邻居越稳 定，并且能够处理大的消息流量。 4 、选择消息队列最短的邻居，因为邻居的消息队列较长意味着邻居的处理消息的 能力已经饱和，或者邻居已经离线了。 在实验中发现源节点只选择一个最好的邻居节点并将查询消息传递过去，查询结 果的效率较高，然而，源节点选择好邻居之后，接下来的搜索仍然是广度优先搜索， 查询消息的流量仍然很大。 为了减少搜索流量，提出一种改进的搜索算法一本地索引搜索，在这个算法中，每 个节点n 存储了与自己的距离在r 步之内的所有节点上的文件目录。变量r 定义了目 录的半径。当r = o 时，每个节点只对自己存储的文件作了索引，因此此时搜索退化为 一般的广度优先搜索。当某个节点收到一个查询消息后，它能够代表距它r 步之内的 每个节点来处理这个查询。这样查询很少的节点就可以寻找到许多节点上存储的文 件，因此搜索成本很低，而搜索的效果很好。当r 较小时，节点需要索引的文件数量 也较小，从而索引的大小只有5 0 k b 的数量级，因此r 较小的本地索引搜索容易被结构 松散的系统所接受。在应用本地索引方法时，所有节点使用同一个策略p 。p 中规定了 处理查询消息饿节点与源节点的距离。例如，假设p ： 0 ，3 ，6 ) ，则源节点必须首先查 询与自己距离为0 的节点，即它本身，因为p 中列出了0 。随后，源节点将查询消息传 递给所有距离为1 的邻居。但由于1 并没有被p 列出，因此这些邻居不会对查询进行 处理，而仅仅将查询消息传递给深度为2 的节点。同样，深度为2 的这些节点直接将 会对查询传递给深度为3 的节点。由于3 在策略p 被列出，因此深度为3 的这些节点 将会对查询进行处理，即会检查它们所存储的索引来寻找所需的文件：如果找到，则 将之返回给源节点；如果没有找到，则将查询消息直接传递给深度为4 的节点。当查 询传递到深度为6 的所有节点后，这些节点同样要检查它们所存储的文件索引。由于6 为p 中最大的深度，因此无论查询是否成功，查询都将结束。 本地索引搜索与迭代加深搜索类似，两者都是基于一个深度列表进行广度优先搜 索。不同的是，在迭代加深搜索时，深度小于上限的那些节点都必须对查询进行处 理，而在本地索引搜索中，只有那些深度在策略p 中列出的节点需要对查询消息进行 处理。另外，迭代加深搜索随着t t l 的增加重复广播查询消息，而本地索引搜索只会 广播查询消息一次。 在标准的随机游走算法中，源节点将查询消息传给随机选择的一个，然后这个邻 居再随机选择一个邻居将查询消息传递过去，并重复这个过程一直到文件寻找到为 止。因此查