（计算机应用技术专业论文）无结构p2p文件共享系统稀缺文件索引机制研究.pdf

摘要 摘要 近年来以g n u t e l l a 和k a z a a 为代表的无结构p 2 p 文件共享系统已经成为当 前i n t e r n e t 中最重要的应用之一。在无结构p 2 p 文件共享系统中，当用户对流行 文件进行查询时，系统能够以较短的响应时间搜索到大量的结果，但对数量较 少的非流行文件( 稀缺文件) 的查询，系统在经过较长的响应时间后仍难以搜 索到足够的结果来满足用户需求，查询失败的可能性很高。由于对稀缺文件的 查询占系统总查询量的3 - - 一1 5 左右，因此如何在无结构p 2 p 中提高稀缺文件 搜索的成功率已成为迫切需要解决的问题。本文主要研究针对稀缺文件的索引 机制，通过建立索引系统来协助提高稀缺文件搜索的成功率。 索引机制是提高p 2 p 文件共享系统搜索性能最常用的策略之一。已有的局部 索引( l o c a li n d i c e s ) 和路由索引( r o u t i n gi n d i c e s ) 等策略通过在本地记录其它结点 的相关信息来辅助提高查询效率，但这些策略都很少或几乎没有提及对稀缺文 件查询成功率的提高。本文从建立稀缺文件索引要解决的问题出发，系统地讨 论了稀缺文件索引的形成、发布的方式、发布终止的条件、索引的分布和索引 的维护，构成了稀缺文件索引策略的基本框架，并在此基础提出了局部索引策 略，总结了全局索引策略。在局部索引中，稀缺文件索引向部分或全部邻居一 次或多次迭代发布，分布在以稀缺文件拥有者为圆心的一定半径的范围内；在 全局索引中，稀缺文件的索引按照一定的交换原则在全网范围内随着交换而“移 动”，使得索引被稀疏的分散到更为广阔的领域。 本文通过仿真实验对比了采用两种索引机制的搜索方案和无索引搜索方案 在文件查询方面的延迟、命中数、成功率、消息数等衡量指标。结果显示，局 部索引和全局索引在各种网络状况下都降低了延迟并且将稀缺文件的命中数增 加了至少一倍以上，提高了稀缺文件搜索的成功率，同时在流行文件的查询过 程中也起到了一定的优化作用，提高了p 2 p 系统的可用性。 关键词：无结构p 2 p 稀缺文件索引机制局部索引 全局索引 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，u n s t r u c t u r e dp 2 pf i l e - s h a r i n g s y s t e m ss u c ha sg n u t e l l aa n d k a z a ah a v eb e c o m et h em o s ti m p o r t a n ta p p l i c a t i o n si ni n t e m e t t h eu n s t r u c t u r e d p 2 p f i l e s h a r i n gs y s t e m sc a r lr e t r i e v eag r e a tn u m b e ro fr e s u l t sw i t h i ns h o r tt i m ew h e n q u e r yap o p u l a rf i l e ，b u tc a no n l yg e tf e wr e s u l t st om e e tu s e r s d e m a n df o ra n u n p o p u l a ro n e ( i e r a r ef i l e ) aq u e r yf o rar a r ef i l eh a sah i g hr i s ko ff a i l u r e t h u s h o wt oi m p r o v et h ee f f i c i e n c yo fr a r ef i l es e a r c h i n gh a sb e c o m eah o tr e s e a r c ha r e a a n dn e e dt oh a n d l eu r g e n t l y i no r d e rt os o l v et h i sp r o b l e m ，t h i st h e s i ss t u d i e st h e i n d e xs c h e m ef o rr a l ef i l e s ，e s t a b l i s h i n ga ni n d e xs y s t e mt oh e l pi m p r o v et h es u c c e s s r a t eo fs e a r c hf o rr a r ef i l e s i n d e xs c h e m ei so n eo ft h em o s tc o m m o n l yu s e ds t r a t e g i e st oi m p r o v et h es e a r c h p e r f o r m a n c eo fp 2 pf i l e - s h a r i n gs y s t e m t h ee x i s t i n gi n d e xs c h e m e ，s u c ha sl o c a l i n d e xa n dr o u t i n gi n d e xw h i c hl e tn o d e sr e c o r do t h e rn o d e sr e l e v a n ti n f o r m a t i o n l o c a l l yt oh e l pi m p r o v et h eq u e r ye f f i c i e n c y , h a v el i t t l eo rn om e n t i o no ft h er a r ef i l e s t l l i st h e s i sf o c u s e so nt h ei n d e xs c h e m eu s e di ns e a r c hf o rr a r ef i l e si nu n s t r u c t u r e d p 2 pf i l e s h a r i n gs y s t e m s w ee s t a b l i s h e dab a s i cf r a m ef o ri n d e xs c h e m ei n c l u d i n g t h ef o r m a t i o n , t h ei s s u em e t h o d ，t h ed i s t r i b u t i o na n dt h em a i n t e n a n c eo ft h er a r ef i l e s i n d e x b a s e do nt h ef r a m ew ep r o p o s e dap a r t i c u l a ri n d e xs c h e m ec a l l e dl o c a l i n d e x s c h e m e ，i nw h i c ht h er a r ef i l e s i n d i c e sa r ed i s t r i b u t e dw i t h i na na r e aa r o u n dt h ef i l e s o w n e r w ea l s on a m e dt h ei n d e xs c h e m eu s e di ni b f sg l o b a ls c h e m e i nw h i c h i n d i c e sa r ed i s t i l b u t e da l lo v e rt h ew h o l en e t w o r k w ev a l i d a t et h ep e r f o r m a n c eo ft h el o c a li n d e xs c h e m ea n dt h eg l o b a li n d e x s c h e m eu n d e rv a r i o u sn e t w o r ke n v i r o n m e n t s ，a n df i n do u tt h a tt h ei n d e xs c h e m e s i m p r o v e dt h es e a r c hd e l a ya n ds u c c e s sr a t ef o rr a r ef i l e st oal a r g ee x t e n t k e yw b r d s ：u n s t r u c t u r e dp 2 p i n d e xs c h e m er a r ef i l el o c a li n d e xg l o b a l i n d e x i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系所专业 联系电话 e m a i l 通信地址( t h l j 编) ： 备注：是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 第一节p 2 p 简介 1 1 1p 2 p 的特点 在p 2 p 网络中，每个节点都拥有对等的功能与责任，即每个节点既充当服 务器向其它的节点提供数据或服务，又作为客户机享用其它节点提供的数据或 服务。一种常见的p 2 p 的定义是：p 2 p 是一种分布式网络，网络的参与者共享他 们所拥有的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ， 这些共享资源需要由网络来提供服务和内容，能被其它对等节点直接访问而无 需经过中间实体。在此网络中的参与者既是资源提供者，又是资源获取者。 p 2 p 模式和目前流行的c s 模式有着本质上的区别。在c s 模式中，当用户 间要进行信息资源的传输活动时，首先要构建一个有一定资源的服务器，然后 在其它地方( 大多数为在个人计算机上) 创建信息并“发布”到服务器上。这 些信息在服务器上等待请求。接收到请求之后，服务器将信息传递给请求者。 整个过程需要三步，即创建信息一发布信息一查看信息。图1 1 是一个典型的 c s 模式的体系结构。 图1 1c s 模式的体系结构 c s 模式具有以下特点网。 1 ) 采用集中计算方式，存在客户端和服务器之分。信息和数据都保存在服 务器端，每台服务器所能提供的信息数量受到自身存储空间的限制。客户端基 本上只是一个高性能的i 0 设备，上面大量的资源和服务被闲置。 2 ) 服务器及网络的带宽决定了整个网络的性能，任意时刻它所能支持的客 户端访问数量受到自身处理能力以及网络吞吐能力的限制。随着客户端的增加， 第一章引言 服务器的负载就越来越重，成为系统的瓶颈。 3 ) 一旦中央服务器崩溃，整个网络也随之瘫痪。 4 ) 信息的分布与生存期十分稳定。通常，发布的信息将会在服务器上稳定 的保存较长的一段时间，并且该服务器也不间断地运行在网络上。 5 ) 存储与管理比较集中，服务器根据适当的算法和规则管理本地信息，应 答客户端的访问请求。 同样是进行信息资源的传输，在p 2 p 模式下则有很大不同。处于对等地位 的节点可以直接向存储信息的对等节点发送请求。而接收到请求的节点可以直 接将需要的信息发送给对方。整个过程只需两步，即创建信息一查看信息。图 1 2 是一个典型的p 2 p 模式的体系结构。p 2 p 模式具有以下特征【6 ，7 】。 1 ) 节点对等性：每个节点具有相同的地位，既可以请求服务也可以提供服 务，同时扮演c s 模式中的服务器和客户端两个角色。这是和传统的c s 模式 最大的差别。 2 ) 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和服务 的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可 能的瓶颈。非中心化的特点给p 2 p 带来了在可扩展性、健壮性等方面的优势。 3 ) 可扩展性：p 2 p 网络的规模随着加入节点的数量的增长而增长，新节点 的加入会给系统增加新的资源。整个体系是全分布的，不存在瓶颈。从理论上 讲，p 2 p 网络的可扩展性几乎是无限的，可以达到现有的i n t e m e t 规模。 图1 2p 2 p 模式的体系结构 4 ) 节点的自治性：p 2 p 网络中的节点具有高度的自治性，它们的行为不受 任何第三方的限制。系统中的任意一个节点主要关注本地的事务；可以独立自 主地决定哪些本地资源可以被共享以及共享权限等；并且当节点离开p 2 p 系统 2 第一章引言 时仍然是一个功能完备的计算机系统。 5 ) 节点的异构性和动态性：p 2 p 系统中各个节点的c p u 处理能力、存储 能力、带宽以及他们在系统中的滞留时间均有很大的不同。系统中的任意一个 节点可以随时加入网络，也可以随时离开网络。 6 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在 各个节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网 络一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 7 ) 负载均衡：每个节点既是服务器又是客户机，减少了对传统c s 模式服 务器计算能力、存储能力的要求，同时因为资源分布在多个节点，所以可以更 好地实现整个网络的负载均衡。 8 ) 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定律高速 增长。p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存 储资料分布到所有节点上。通过利用网络中的大量空闲资源，可以用更低的成 本提供更高的计算和存储能力。 9 ) 缺乏集中管理：p 2 p 系统是彻底的分布式系统，每一个节点都可以随意 的发布信息，缺乏集中管理，因此信息的获取比较困难。此外，缺乏集中管理 还造成系统整体信息的缺失：每个节点都通过有限的局部信息做出决定。这样 造成的后果是系统不能以全局最优的策略完成某个特定任务。 1 0 ) 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无 需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大减小。在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活 性和可靠性，能够为用户提供更好的隐私保护。 1 1 2p 2 p 网络的分类 了解了p 2 p 网络的特点，我们来看p 2 p 网络的分类。p 2 p 网络按拓扑结构 可分为两大类：结构化p 2 p ( s t r u r t e u r t e dt o p o l o g y ) 和无结构化p 2 p ( u n s t r u r t e u r t e d t o p o l o g y ) 。 结构化拓扑中系统对p 2 p 网络拓扑和文件放置都精确地加以控制，仔细地 将文件索引分布在参与的节点中。这种系统支持分布式哈希表( d i s t r t i b u t e dh a s h t a b l e ，d h t ) 功能，如c h o r d t 引，c a n 9 1 ，p a s t r y t l o 】和t a p e s t r y 0 1 l 等。 3 第一章引言 这种拓扑的优点是搜索机制只需要较小的通讯开销，因而在理论上有更好 的可扩展性；缺点是不能有效地支持模糊匹配和文本匹配等复杂的多样化查询 方式。另外对节点的不断加入和离开需要频繁地做些额外的工作，基于d h t 的 拓扑维护和修复算法比无结构系统要复杂得多。 目前，结构型p 2 p 的文件共享系统缺乏在i n t e m e t 中大规模真实部署的实例， 鲜有成功应用的案例。即使是c h o r d 、c a n 、p a s t r y 等项目也更多的用于动态性 更低的大规模网络存储应用上。事实上，目前已投入实际应用的p 2 p 文件共享 服务大都是基于无结构型的p 2 p 网络的，许多学者指出无结构型的p 2 p 网络更 适合于文件共享系统 1 2 , 1 3 , 1 4 】。 无结构化p 2 p 网络根据是否有中央服务器进行集中管理，又可划分为集中 式( c e n t r a l i z e dp 2 p ) 、分布式( d e c e n t r a l i z e dp 2 p ) 和混合式( h y b r i dp 2 p ) 三 种不同模式。 1 集中式p 2 p 集中式p 2 p 在交换数据或文件时一般是通过中央服务器进行目录管理的。 由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查 询。最大的问题与传统客户机服务器结构类似，容易造成单点故障，访问的“热 点现象和法律等相关问题，这是第一代p 2 p 网络采用的结构模式，拓扑结构 如图1 3 所示，经典案例就是著名的m p 3 共享软件n a p s t e r t l 5 】。它是最早出现的 p 2 p 系统之一，并在短期内迅速成长起来。n a p s t e r 实质上并非是纯粹的p 2 p 系 统，它通过一个中央服务器保存所有n a p s t e r 用户上传的音乐文件索引和存放位 置的信息。当某个用户需要某个音乐文件时，首先连接到n a p s t e r 目录服务器， 在服务器进行检索，并由服务器返回存有该文件的用户信息，再由请求者直接 连到文件的所有者传输文件。 集中式p 2 p 模式的优点是：结构简单，便于维护；资源检索响应比较快；管 理维护整个网络消耗的网络带宽较低。但是集中目录式p 2 p 模式还存在很多问 题，主要表现为：服务器承担所有的检索工作，负载过重不完全符合p 2 p 的原 则；中央服务器的瘫痪容易导致整个网络的崩溃，可靠性和安全性较低；中央 服务器的存在引起共享资源在版权问题上的纠纷，这也是直接导致n a p s t e r 破产 的原因。集中式p 2 p 对小型网络而言在管理和控制方面占有一定的优势，但对 大型网络并不适合【l 6 1 。 4 第一章引言 查询 下囊 图1 3 集中式p 2 p 拓扑结构 2 分布式p 2 p 在分布式p 2 p 网络中，没有中央目录。当一个新的节点加入到网络中时， 它自由地连接其他节点( 例如，随机选择某些节点作为邻居) 。如果节点要发布 某些资源，通常是它局部地存储这些资源。分散的无结构化拓扑非常适合由高 度自治的节点组成的环境，来自许多不同组织的用户互相之间共享资源， c m u t e l l a 、f r e e n e t 1 7 】是典型的分布式无结构化p 2 p 网络。分布式p 2 p 的拓扑结构 如图1 4 所示。 查询 下载 图1 4 分布式p 2 p 拓扑结构 分布式无结构化p 2 p 网络因其简单和可用性，在互联网上广泛配置，并占 据主导地位。如果发生节点或者网络失效，这类系统容错性好。当随机失效经 常发生时，网络具有较好的可恢复性，对整体网络的性能影响较小。无结构化 p 2 p 网络适合节点的动态性，也支持复杂的搜索条件，如规则表达的关键字搜索， 范围搜索( r a n g es e a r c h ) 等。但是无结构化p 2 p 网络只能提供资源发现的不可 靠的保证。某些搜索会失败，即使请求的资源事实上是存在的，搜索效率也不 能保证。在这样的网络中，资源发现常常采用洪泛、随机行走或者选择性转发 5 第一章引言 技术，但随着网络规模的扩大，通过洪泛方式定位对等节点及查询信息的方法 将会造成网络开销成指数级增加，因此目前这些搜索技术通常是效率较低的。 3 混合式p 2 p 混合式p 2 p 是集中式拓扑和分散式拓扑的综合。拓扑中存在一些超级节点 ( s u p e rp e e r ) ，即比普通节点拥有更强的能力( 处理能力，存储能力、带宽等) 。 每个超级节点和连接到它的所有普通节点构成一个簇，超级节点作为簇内部分 普通节点的中央资源，维持这些普通节点共享数据的索引。各个超级节点之间 组成纯分散式p 2 p 网络，如图1 5 【6 l 】所示。超级节点为它负责的普通节点执行搜 索。如果一个普通节点p 要找某个资源，它首先向它的超级节点s 提交搜索请 求，然后搜索请求由s 发给各超级节点处理。超级节点s 获得搜索结果以后， 返回给p 。但是在文件下载时，所有的节点仍旧是同等的。k a z a a 模型是p 2 p 混合模型的典型代表。 o o 超级节点 普通节点 图i 5 混合式p 2 p 拓扑结构 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充分 的时候，再通过搜索节点之间进行有限的泛洪。这样就极为有效地消除分布式 p 2 p 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时，由于每 个簇中的搜索节点监控着所有普通节点的行为，这也能确保一些恶意的攻击行 为能在网络局部得到控制，并且超级节点的存在也能在一定程度上提高整个网 络的负载平衡。但是，部分分散式拓扑也要面对集中式拓扑和分散式拓扑的类 似问题。网络中的超级节点很重要，如果接近顶层的少数超级节点失效，也会 给整个系统带来严重的影响。同时各超级节点间形成一个纯分散式拓扑，所以 也要面对分散式拓扑类似的问题。 6 第一章引言 第二节p 2 p 系统的广泛应用 近年来，p 2 p 系统以其各方面的特点和多样化的结构得到学术界与工业界的 共同推动，取得了快速的发展。到目前为止，主要有以下几个研究和应用方向： 1 ) 文件共享服务：这是p 2 p 最为成功的用途之一，也是本文的研究领域。 用户利用基于p 2 p 的网络协议，直接从含有所需文件的对等结点下载该文件， 从而摆脱了对特定服务器的依赖。应用实例包括第一代的n a p s t e r ”】，以及第二 代g n u t e l l a 【1 】和k a z a a 2 等p 2 p 文件共享系统。 2 ) 分布式计算：把网络中众多计算机暂时不用的计算能力连接起来，使用 积累的能力执行超级计算机的任务。任何需要大量数据处理的行业都可从分布 式计算中获利，如天气预报、动画制作、基因组的研究等。应用实例包括 s e t i h o m e 1 8 】和x e n o s e r v e r s 1 9 1 等。 3 ) 网络存储：随着网络规模的扩大，一些研究项目开始采用p 2 p 技术来组 织和存储数据，将传统的局域存储技术向基于互联网的数据存储系统发展。这 些项目的目标是提供面向全球的数据存储服务。应用实例包括o c e a n s t o r e 2 0 1 ， p a s t 2 1 】和c f s 2 2 1 等。 4 ) 即时通讯：在基于p 2 p 技术的通信中，中心服务器仅仅是连接初始化时 用来控制用户的认证信息等基本信息：尔后通讯双方的交流完全是点对点进行， 不依赖服务器的性能和带宽。这种应用实例很多，包括i c q 【2 3 1 ，m s n 2 4 1 和s k y p e 2 5 】 也蟹 守o 5 ) 应用层组播：利用p 2 p 技术可以在应用层实现组播功能而不需要i p 层 的支持。这样就可以避免出现由于i p 层迟迟不能部署对组播的支持而使组播应 用难以进行的情况。应用实例包括n a r a d a t 2 6 1 ，a l m l l 2 7 和s c r i b e 2 8 1 等。 6 ) 协同工作：p 2 p 技术可以帮助企业和关键客户以及合作伙伴之间建立一 种安全的网上协同工作方式，避免了传统的w e b 方式的协同工作给服务器带来 的极大负担。应用实例包括g r o o v e 2 9 】等。 7 ) w r e b 缓存：基于p 2 p 的w e b 缓存系统可利用对等计算的技术优势，很 好地解决传统的w e b 缓存系统不能避免的硬件开销，缓存有限以及维护和运营 成本指数级递增等问题。应用实例包括s q u i r r e l 3 0 】等。 8 ) p 2 p 搜索引擎：与传统搜索方式相比，利用p 2 p 可以充分检索网络上的 所有结点，并且可以通过检测网站的变化，提高搜索引擎的可达范围和数据的 刷新率。应用实例包括i i l f 蕊e a r c h 【3 1 1 ，p a n d a n g o 3 2 1 和g o o g l e l 3 3 1 等。 7 第一章引言 9 ) 其他应用：提供从多点持续测试网站性能的诊断工具；用散布在i n t e r n e t 上的计算机来创建一个精确和实时的网络交通图；用网络上不同地点的多个结 点来检测、监测和鉴别恶意行为；利用p 2 p 技术进行安全路由等。 第三节p 2 p 文件共享系统的现状 本文主要研究p 2 p 文件共享系统，它具有分散化、自主性强、容错性好、 信息量大等优势，以k a z a a 、g n u t e l l a 、b i t t o r r e n t 等为代表的一批无结构型p 2 p 文件共享系统已经成为当前i n t e m e t 中最重要的应用之一。但这些文件共享系统 存在着明显的弊端，在这些文件共享系统中，各种文件的流行度截然不同。如 果以整个系统中某个文件的拷贝数作为判断该文件流行度的依据，就会发现文 件的流行度呈现出幂律分布【3 4 3 5 】：约5 0 的文件拥有不到2 0 个拷贝，而最流行 的文件却拥有上千个拷贝。 文件分布的不均衡会损伤系统的可用性。对于流行文件的查询，系统能够 以较短的响应时间搜索到大量的结果；对于稀缺文件的查询，系统在经过较长 的响应时间后仍难以搜索到足够多的结果来满足用户的需求。以g n u t e l l a 为例 【3 6 】，有4 1 的查询消息最终得到l o 个或更少的结果，其中1 8 的查询没有得 到任何结果。对于那些只获得一个结果的查询消息，它们的平均响应时间为7 3 秒。对于结果数量小于1 0 的查询消息，它们的平均响应时间为5 0 秒。对于查 询结果的数量大于1 5 0 的查询消息，它们的平均响应时间小于6 秒。可见，现 有的文件共享系统在搜索稀缺文件时失败的可能性很大。 p 2 p 文件共享系统中由文件分布的不均衡性所引发的查询失败是能够得到 改善的。b t l o o 等所提供的方法【3 l3 8 】证明了这一点：对于某一个查询，由 g n u t e l l a 中的3 0 个u l t r a p e e r 同时进行洪泛，则只有2 7 的查询消息获得了1 0 个 或更少的结果，其中只有6 的查询消息没有获得任何结果。尽管这种方法给网 络带来了巨大的开销，但仍证明了由文件分布的不均衡性所引发的查询失败可 以通过新的方法予以改善。 目前针对提高查询成功率的研究大致可以归为以下几类：第一，搜索机制。 区别对待流行文件和稀缺文件。对于稀缺文件采用较大的t t l ，并且以广播的 方式转发给所有邻居( 采用较大1 v r l 值的f l o o d i n g 算法) ；对于流行文件，只采 用较小的1 v r l ，并且只选取一个或几个邻居节点给予转发( 采用较小t t l 值的 8 第一章引言 m b f s ( m o d i f i e db r e a d t hf i r s ts e a r c h ) 算法) 。尽管增大1 几能够提高查询的命中 率，但也给网络带来了大量的冗余查询消息。而选择性转发导致响应时间变长， 用户会因此浪费大量时间。第二，拓扑结构。将具有相似文件的节点聚类，这 样寻找某个文件时就可以减少查询对象，从而提高查询的成功率并且减少了查 询消息转发的数量。但是，在节点分类的过程中可能出现大量的错误，并且分 类信息的维护也需要大量的网络开销。也有人提出将网络中的超级节点组织成 d h t 的形式，将稀缺文件映射到d h t 中，这样查找稀缺文件就会很容易。但引 入d h t 会导致网络结构复杂化，从而丧失无结构p 2 p 自身的优点，因此采用这 种方法的意义并不大。第三，文件备份。节点退出前通过将自己的文件复制至 其他节点来避免因节点失效而导致的文件丢失和查询失败。这种方法固然能够 延长文件在网络中的存在时间，但仍难以克服稀缺文件的查询失败率高这一难 题。第四，索引机制。节点缓存流经的查询结果或者索引其他节点的文件信息。 当自身进行查询或其他节点的查询消息流经该节点时，直接将缓存和索引中的 信息反馈给查询的源节点。这样能够缩短查询的响应时间并且获得更多结果。 这种方法值得借鉴，但目前并没有专门针对稀缺文件的索引机制。 第四节本文研究内容 本文所依托的项目无结构p 2 p 文件共享系统中稀缺文件查询机制研究， 旨在提高稀缺文件查询成功率，从稀缺文件判定、查询机制改进以及稀缺文件 索引三个方面展开研究。 本文主要研究稀缺文件的索引机制，构建了稀缺文件索引系统的基本框架， 在此基础上提出了局部索引策略，并通过仿真实验分析了它和前续工作中采用 的全局索引策略在不同网络状况下的性能表现。 本文的主体由两部分组成，第一部分主要研究稀缺文件索引机制。从需要 解决的问题出发，研究了稀缺文件索引的形成、稀缺文件索引发布的方式、稀 缺文件索引发布的终止条件、稀缺文件索引的分布以及稀缺文件索引的维护， 构建了稀缺文件索引系统的基本框架，并在该框架的基础上引入具体的解决方 案提出了局部索引策略。 第二部分主要通过仿真实验对第一部分中提出的索引机制进行多角度、多 层次的对比。通过选取不同的网络参数，在仿真实验中客观、具体的对比采用 9 第一章引言 索引方案后系统的各项性能表现，为不同网络环境下索引机制的选取提供有力 的实验依据。 第五节论文结构 本文在结构上分为五个组成部分： 第一章引言。介绍了p 2 p 系统的特点、结构及其应用领域；阐述了p 2 p 文 件共享系统的现状及本文要研究的主要内容。 第二章介绍无结构p 2 p 文件共享系统中的文件定位机制，包括搜索算法和 索引策略。 第三章本文的核心，详细阐述稀缺文件索引机制需要解决的问题，提出了 局部索引策略，并归纳概括了全局索引。 第四章仿真实验，对第四章中提出的两种索引发布策略进行多方面多角度 的验证分析，对比其在不同网络状况下的性能表现。 第五章总结和展望。对系统的特点进行总结，并指出需要继续完善的地方。 1 0 第二章无结构p 2 p 文件共享系统中的文件定位机制 第二章无结构p 2 p 文件共享系统中的文件定位机制 本文旨在研究无结构p 2 p 文件共享系统中能够提高稀缺文件查询成功率的 稀缺文件索引机制，因此需要对已有的无结构p 2 p 文件共享系统中的文件定位 机制和索引机制有较为全面的认识。本章将分别从文件定位机制和索引机制两 个方面对现有的工作做一概括。 第一节文件定位搜索算法 g n u t e l l a 是p 2 p 文件共享系统中最经典、也具有最多开发支持的应用系统之 一。本文的后续工作都将在类c m u t e l l a 网络的基础上完成，因此本节首先阐述 g n u t e l l a 中采用的洪泛搜索机制，然后介绍当前学术界提出的能够提高c m u t e l l a 网络基本洪泛算法效率的众多改进机制。 2 1 1洪泛机制 在c m u t e l l a 网络中，搜索方式采用洪泛机制。为了查找某个共享文件，首先 向与之相邻的所有活动节点发送一个查询消息。所有这些节点在接收到该查询 消息后，检查本地是否有符合查询请求的共享文件内容。如果有，则按查询消 息的发送路径返回一个查询响应消息。无论本地是否存在符合查询请求的文件 内容，这些节点都会将该查询包通过“洪泛”方式继续在相邻网络节点中传递， 直至查询包中附带的生存时间值( t t l ) 递减为0 时才停止继续转发。另外，每 条查询消息都带有全局唯一的标识符。当结点接收到一条查询消息时，取出消 息头中的标识符字段，同本地记录的标识符列表相比较。如果该查询消息的标 识符己经在列表中，说明结点己经处理过这条查询消息，它将直接把这条消息 丢弃。这样做的目的是防止一个结点对同样的查询消息进行多次转发。当发出 查找消息的节点定位到了响应查询共享文件的节点后，就与该节点建立连接， 从响应节点中下载自己查询的文件。查询过程中对节点的访问如图2 1 所示。 洪泛机制具有以下特点： 1 ) 结点覆盖率高。研究表明【3 9 1 ，在大约五万个结点( 或超级结点) 的p 2 p 网络中，采用洪泛方式，设置1 v r l 初始值设为7 ，能够搜索到9 5 的结点。这 是因为在洪泛中随着跳数的增加，搜索到的结点个数是按指数增长的。 1 1 第二章无结构p 2 p 文件共享系统中的文件定位机制 图2 1c m u t e l l a 中的查询消息洪泛 2 ) 健壮性好。一个结点出现故障或是退出对其余结点几乎没有影响，因为 在洪泛中，每个结点要向所有邻居结点发送消息，查询消息能够通过结点之间 所有可能的路径被转发。 3 ) 响应时间快。因为洪泛中，结点是以并行的方式向邻居结点发送查询消 息的。 但是，洪泛有个很严重的问题，就是会产生大量冗余消息，特别是当网络规 模比较大，节点之间连通度比较高的时候。论文 4 0 】中指出，尽管当t ，r l 初始 值较小时基本上不会出现冗余消息，但是当t t l 初始值较大的时候，冗余消息 的数目将剧增。冗余消息从第5 跳开始急剧增加，第4 、5 、6 、7 跳的冗余消息 分别达到了消息总数的2 、8 、3 0 和6 1 。在实际的p 2 p 网络中，冗余消 息增加了节点处理负担，也会占用大量网络带宽。 目前针对无结构p 2 p 网络洪泛搜索方法的缺点，有各种新颖的算法和技术 被提出以控制和减少泛洪方法带来大量不必要流量，这大致可归为四类：基于 改进转发机制的方法、基于拓扑结构的优化方法、基于索引和缓存的方法和基 于兴趣分组的方法。结合本文的研究方向和结构安排，3 1 2 重点介绍基于改进 转发机制的方法，基于索引和缓存的方法将在索引缓存策略一节中详细介绍。 2 1 2 基于改进转发的方法 在基于改进转发机制的方法中，按照消息转发的策略，又可以分为两大类： 盲目转发策略和基于信息的转发策略。 1 盲目转发策略 1 2 第二章无结构p 2 p 文件共享系统中的文件定位机制 1 ) m b f s ( m o d i f i e d b f s ) 方法【4 l j ：m b f s 方法是在洪泛( f l o o d i n g ) 算法 上面作了一定修改。跟洪泛搜索方法不同，m b f s 搜索过程只是随机的选取一定 比例的相邻节点作为查询消息的发送目标，而不是发送给所有相邻节点。相比 于f l o o d i n g 方法来说，由于仅选择了一部分结点来进行搜索，必然节省了网络 流量，但查询成功率也会因此而降低。 2 ) i t e r a t i v ed e e p e n i n g 方法 3 1 ：i t e r a t i v ed e e p e n i n g 的迭代递增策略循环递增 t t l ( t i m et ol i v e ) 值，这个值用来控制f l o o d i n g 的搜索深度。跟f l o o d i n g 搜 索方法给t t l 赋一个较大的值不同，这种方法在初始阶段，给t t l 一个很小的 值，如果在1 v r l 减为0 时还没有搜索到资源，则给1 吃重新赋更大的值。这种 策略可以减少搜索的半径，如果p 2 p 网络内重复资源丰富，这种方法在不影响 搜索质量的基础上将减少网络内的查询流量，但是在最坏的情况下( 如查询稀 缺文件时) ，网络流量和延迟将变的更加严重。在有的文献中该方法亦称为 e x p a n d i n gr i n g ( 扩展环搜索) 1 4 z j 。 3 ) r a n d o mw a l k s 方法【4 3 】：查询节点同时生成k 个查询消息给随机挑选的 k 个相邻节点，然后每个消息在节点之间依次随机转发传递，每路消息称为一个 w a l k e r 。r a n d o mw a l k s 方法能够显著减少搜索产生的查询消息数，但是搜索延 迟较高，并且其盲目的随机转发特性使得搜索性能得不到保证。 2 基于信息的转发策略 基于信息的转发是在搜索中采用某些启发式策略和统计信息，如选择最近 返回结果最多的邻居，或者最有可能到达目标节点的邻居等等，算法只选择部 分邻居节点进行转发，目的是减少网络中查询消息的流量。 1 ) d b f s ( d i r e c t e d b f s ) 方法p j ：d b f s 方法将查询消息转发给可能提供 更多结果或更快结果的一部分邻居，它假定历史查询好坏能够预示将来查询的 好坏。为了能够有方向的选择邻居，每个节点都维护了其邻居的一些简单统计 数据，比如该邻居以前返回的结果数，或到该邻居的延迟。从这些统计数据中， 可以启发式的选择最好的邻居来发送查询。但如果稀缺资源恰恰存放在过去表 现不好的结点上，采用d b f s 方法就会搜索不到这类文件。 2 ) i s m ( i n t e l l i g e n ts e a r c hm e c h a n i s m ) 方法 4 1 l ：i s m 方法是对m b f s 的改 进，它将查询发送到最可能得到返回结果的邻居。每个节点在收到消息后将当 前的查询和以前的查询进行比较，按相似度对邻居节点进行排名，然后把查询 转发到最可能获得成功的节点。本质上该方法是基于相似性的邻居选择策略， 1 3 第二章无结构p 2 p 文件共享系统中的文件定位机制 根据邻居节点的历史信息来预测未来的查询。它同样对查询频率低的稀缺文件 表现不佳。 3 ) a p s ( a d a p t i v ep r o b a b i l i s t i cs e a r c h ) 方法1 4 4 ：a p s 是一种改进的基于信 息的r a n d o mw a l k s 算法，它在转发时不是随机选择邻居，而是根据邻居的历史 概率性的选择下一个转发节点。a p s 方法增加或者减少某个邻居的选中概率是 利用反馈机制，根据乐观或悲观策略，对经常返回结果的邻居结点增大选中的 概率，反之减小其概率。a p s 方法在查询成功率和响应时间方面都要优于r a n d o m w a l k s 方法，在一定程度上保证了查询效果，但它对于稀缺资源的查询仍不如传 统的洪泛或部分洪泛方法，因为a p s 方法搜索的结点数目依然很少。 4 ) m s f ( m u l t i p l es m a l l s c a l ef l o o d s ) 方法1 4 5 j ：m s f 方法提出使用代理节 点进行多次小规模洪泛的机制，其主要思想是将查询请求尽量分散到可以返回 尽可能多结果的区域中去，并利用小范围洪泛来控制查询消息的数量。m s f 机 制中使用最多返回结果的方法排列代理结点，并采用同步、顺序和并行三种策 略来控制小洪泛的发起顺序，使得用户可以在最小化响应时间和尽量减少网络 流量二者中作出选择。 5 ) p o p u l a r i t y b i a s e dr a n d o mw a l k s 方法【4 6 】： 该方法将平方根原则 ( s q u a r e r o o tp r i n c i p l e ) h 7 】应用于r a n d o mw a l k s 搜索算法中，通过应用马尔可夫 随机过程使随机漫步算法对下一搜寻节点的选择符合平方根原则，从而提高搜 索的效率。平方根原则要求被查询文件的复本数应与该文件查询频率的平方根 成正比，以使搜索代价达到最小值。该原则通常应用在复本复制和拓扑重组策 略中，p b r w 方法给出了平方根原则在搜索算法中实现的理论依据。 6 ) d q ( d y n a m i cq u e r y ) 方法j ：动态查询是一种新的受控的洪泛技术， 它通过两阶段洪泛来控制搜索范围减少消息数量。第一个阶段称为探测阶段， 使用一个小的t t l 值进行部分洪泛，然后根据返回结果数量估计被搜索文件的 流行度