（计算机科学与技术专业论文）共享文件搜索及其模拟技术的研究和实现.pdf

星防辩学技术大学研究生陵学位论文 摘要 近年寒p 2 p 诗算技术发展迅速，其中p 2 p 文锌共享应熙已经成为互联网上豹主流戍 用之一。p 2 p 文件共事应用的一个核心问题是有效的文件搜索机制。目前互联网文件共 享应用存在着搜索带宽消耗高、搜索模式简单和搜索结聚质羹不高等同越，很多研究从 不露鑫冬角度尝试瓣决这些溺题。盘予粒p 弼络翡分枣特性移p 2 p 蟋络掇模豹尽蕊扩大， 在真实的p 2 p 嘲络环境下去测试一个新的搜索算法并搜集它的性能参数极其困难，因 此对于新的p 2 p 算法和协议的评估生要通过模拟来测试。目前已经有相当数量的p 2 p 禳撅器，或者专弱于菜种算法，或者专注予菜类系统，逐缺乏释有效翡胃淤支持多种 算法、多秘数据购p 2 p 模拟器。 本文的主要工作体现谯以下方面： 分析了复杂网络审z i p f 分布，p o w e r - l a w 和s m a l lw o r l d 等基本特征，稠糟这黧特筏 来壤助邋月模拟器和文件搜索算法的设计。 提出了种新型分布式文件搜索方法f r f s 。该算法提出了基于朋发关系的搜 索，节点之间按照搜索兴趱和共事文裆关联建立朋友关系，搜索请求首先在朋友节 点之润转撵，对予少数不能完成豹港求透过基予e 睡 t 熬痤用层广援继续搜索。采 用了基于w e b 的髓志数据和仿真数据对f r f s 做了充分测试。 设计并实现了一个基于文件共享搜索通用模拟器，该模拟器具有毫好的可扩糙性， 能够支持多释p 2 p 模蘩戆横攘；允许在稳鞠豹嬲络条件下送孬各穗葬法帮协议静魄 较，并能对模拟结果进行多角度的分板；阉时支持w 曲日惑和仿真数据作为测试 数据。 关键词：p 2 p 网络，文件共享，模拟器，搜索 第1 页 国防科学技术大学研究嫩院学位论文 a 瑟s l r a e ￥ p 2 p t e c l l n o l o g y d e v e l o p sr a p i 棚y i nr e c e n ty e 黼，p 2 p f i l es h 撕n g h a s b e c o m e o n e o f m 垂珏s 溉糕嘲l i c a l i 鳓s 至珏魏鼢e t 薯h ee o r c 畔b l 瓤o fp 2 p 菇l es h 翻n g 黼l i e 妇n si s e f f 毫c t 主v e 蠡l es e a r c h i n gm c c h a i l i s m 髓l 黜a f em a 蘸yr e s e a r c h e s 蛳gt os o l v e 撖髂ep b l e m s s u c ha sh i 曲b a i l 州d mc o n s 砌p t i o n ，s i m p l cs e a r c hm o d e la 1 1 db a ds e a hr e s u n 散吼 d i 虢r e n ta i l g l e 。b e c a u s eo fp 2 pn e m o r k sd i s t r i b u t i n gc h 孤a c t e r i s t i c 彻di t s8 c a l e 曲l a 蟛n g w 殛l 主檬e ，主t 至sv e 猡镬壤c 娃坛耄e s 圭a 勰ws e a h i 粥a l g o 删b 撒a n d l l 嗽螽s 爹e 蠢b 翻墨n e e p 黼n e t e r si nt 圭l e r e a lp 2 pn e 脚o r ke n v r o n m e n 8 0w ep 蔬瞰a r i l ye v a l u a t ean e wp 2 p a 1 剃m l na n dp r o t o c o ll h r o u g hs i m u l a t i o n t h e s ea m a n ys i i l l 肘1 辑t o r sa tp r e s e n t ，b u tm o s to f m 鼬a d e d i c a t e dt os o m ea l g o f i t 轴赫so fs o m eb n d so fs y s t e m s ，t 王1 e f ei sn os 咖rt h a t e a 珏嘲o 娃d i 狳f e n t 砖毖酾氆m s 赫dd 越a 。 骶娃sm e s i s a i m sa tm a k i n gt 圭l e 硒髓o w i l l gm 旬o fc o n 缸b u t i o n s ： f i r s t l y ，t h e t h e s i sa n a l y s e s t h c b a s ec h a r a c t 耐s t i co fc o m p l 雠n 唧出，i t i n c l u d e s t h 。 w i l d l ye x s t 吼tb 鹊e 嘶n c i p l e ss u c ha sn l ez p fd i 矧b 妣，p o w 盼l 槲a n d 锄a l l 删d 删c h e 越k l p 埝硅鼯i 咎氆eg o 娃翻cs i 珏m | 采甜翘d 磊ks e 鑫l 味遗g 趣鲻黼。 s e c o n d l y ，t h e 也e s i sp r e s e n t san 删d i s 幽碱n g 船s e a r c 城n gm 岫o d * f r f s t l l i s a l 鲥t t 姒b a s c do n 衔c 1 1 dr e l 撕o n s ，i te s t a b l i s h e sm e n dr e l a t i o n s 咖o n gm en o d e s c o r m n g 幽es c a r c 辆矗g 虹e r e s t 嫩g 翩d 妫a 王i n g 纛王ef e l a t i l 瑶，勘es e 8 r c h q u 尊s t 五r s t l yb r o a d c 勰t 锄o n g 氇e 蠹i e n d l yn o d e s ，f 转wf 镪毪e 啦w h i 穗南n tr 。c e i v et e s p o n s ew i l l 蕊n 驻e 辆b m 醚e 蔽撅 t l l e 印p l i c a t i o n1 a yb a s e do nd h t t h et h e s i sa d o p t sw e bl o gd a t a 鑫1 1 ds i m u l a t i o nd a t at o 如n y t e s tf r f 8a l g o d t h m t 毯燃冀氆e 氇e s 至sd e s i g na n di m p l e m 铋t 融i o no fan e wg 懿e f i ep e e r 堪o _ p e e r i l e s e a f c h i n gs i m u l a o f t 赫ss i m u l 采猷黾a s g o o de x p 黼s i b 主l i 融i t e a l ls i m u l a 圭e m 箍l l y k 磁s o f s e a r c h i n ga l g o d t t l m s ；i ta l l o w st 1 1 0 s ea l g o r i t l l i l l st oc o n l p a r cw i me a ( i ho m e ru n d e rt h es a m e n e t w o r kc o n d i t i o n ，“c a na n a l y s i sm er c s u l to fs i m u l a t i o n 丘o mm 锄y 趾g l e s ，i tc a nu s e s 至m 驻l a 捃d a aa n dw e b 轴gd 越 k e y w o r d s ：p 2 pn e 似，o r kf i l es h a r i n s i m u 】a t o r s e a f c h 葵珏燹 国防科学技术人学研究生院学位论文 图目录 图卜1 集中式拓扑结构4 图卜2c h o r d 环形拓扑4 图卜3c a n 几何拓扑5 图卜4 无结构拓扑示意图6 图3 1 混和体系结构示意图1 6 图3 2f r f s 朋友节点构造和搜索算法1 7 表3 1f r f s 、g n u t e l l a 和n e u r o g r i d 模拟结果比较1 9 图3 3 跳数v s 搜索成功率1 9 图3 5 跳数v s 搜索效率2 0 表3 2f r f s 稳定性测试结果数据2 0 图3 6 算法稳定性测试2 1 表3 3w e b 日志数据f r f s 和b f s f l o o d 测试结果2 1 图3 7 跳数v s 搜索成功率2 2 图3 9 跳数v s 搜索效率2 2 图3 1 0 稀有文档测试结果图2 4 图3 一1 1 基于关键字朋友节点构造算法2 5 表3 4k e y w o r d f r i e n d r e l a t i o n s l 0 0 0 0 次查询测试结果2 5 图3 1 2 概率p 与网络的变化2 6 图3 1 3 节点和朋友关系连接图2 7 图3 一1 4f r f s 改进算法2 8 图3 一1 5 综合测试结果2 9 图4 一l 各模型中的主要部分及它们之间的协作3 5 图4 2 仿真数据模拟过程流程图3 6 图4 3b o s t o n 大学w e b 日志数据文档访问频率3 7 图4 4 产生p o w e r 一1 a w 网络方法实现3 8 图4 5 通用模拟器核心类图3 8 图4 6 产生网络拓扑的方法实现4 0 图4 7 消息在节点上的传递方法实现4 1 图4 8 查询记录格式4 2 图4 9 对节点类扩展4 3 图4 1 0 消息的发送和接收4 4 图4 1 1 客户端和服务器端交互所采用的) ( m l 4 4 第i i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取褥的研 究戒果尽我所知，除了文中特别加以标注和致谢的地方井，论文中不包含其他人已 经发表和撰写遘的研究成果，也不包含荛获得国防瓣学技术太掌残其它教育枫稳的学 位或证书筒使用过的材料与我一同置作的同志对本研究所做的任何贡献均已农论文 串终了赛确戆谎臻弗表零瓷意 学位论文题目：熬錾塞佳选塞愿基搓拯越查蝤盟窒塑塞趣 学位谂文搏孝签名： 之擅辱 嚣絮：渺年转嚣扣鞣 学位论文版权使用授权书 本人凳全了解窜醣辩学技采大学稽关保密、旋髑学位论文的瓣定。本人授投鹭 防科学技术大学可以保留并向国家有关部门或机构递交论文的复印件和电予文档，允 诤论文搜蠢凝秘辔烫；鬈滚将学位论文的全都或部分蠹客编入癣关数撂疼遵检索， 可以采用影印、缩印或扫描等复村手段保存、汇编学位论文 缳密学柱| 论文在簿密嚣适用零授投书。) 学位论文题目：感塞塞往监蠹熬甚搓拯挂盛衄壹塑塞煎 学位论文作者签名： 作者糟导教师签名：肄卫拶奉 日期：扣露年，月枷髓 瞄囊：o d 屯f 年 月，# 糕 重堕型鲎煞查盔兰翌塞点堕堂垡笙兰 第一章绪论 i n t e m e t 作为全球最大豹内容发布系统，是信息社会中人们获取各辩资讯不可缺少 匏工兵。在毡t e 氆e l 笈藤的旱蘩，黼e 髓l e t 土连接豹掇器寿限，一令爱鹃交健蔻天方会 传到整个网络。随着w 如及浏览器的出现，众多的p c 通过m o d 锄和a d s l 等方式连 接上i n t e m e t ，从而出现了另一种连接模式：p c 不断频繁的且无法预测的加入和离开 琢t e r n e t ，如现了动态糟；这种模式下d n s 对p c 名字地址政射无能为力，不剥于p c 在本蘧蠢耱数据或参与蘑囱霹络的应蘑，p c 或了罱责我客户滚，露不蹙歉t e 糟e t 奄絮 的一部分，大部分时候p c 的资源都在闲置。随着h l t e m e t 的普及，上网的机器数越来 越多，并且单台机器的计算和存储能力飞速增强，整个i n t e m c t 上的资源难以惊人的速 疫在增长。然嚣b i e 描瓣t 内容发布鹣蒺本方式并没有产生太大的变化。 在佼统的内容发稚模式中，内容的发布由形p ( h t 潍e te o n t e n tp r o v i d e r ，h l t 锄醚 内容提供商) 的应用服务器完成，应用服务器通常处于网络的中心，客户瑞主机处于网 络的边缘，客户端需要到应用服务器下载或浏贤各种内容。在这种发布模式下，网络只 表理失一令透唆鹃数鬃铵辕逶道，辔户凌逛只麓令测菱王菸；瑟由于囊娃e 黼e t 豹蹬 协议是”尽力而为”的，所以这种肉释发布的0 0 s 楚依靠在用户和应用服务器之闯提供 充分的、远大于实际所需的带宽来嶷现的。网络访问对于带宽的要求越来越高，某段网 络带宽瓶颈的限制将遗成整个网络的拥塞，尤其当大量用户同时访问同一台服务器时， 对连接簸务器数链臻蘩宠要求更褰，不莰大量宝爨瓣夤于蒂爨被占磊，王c p 豹应溪羧务 器的负载也变得非常黧，而且不可预计。为了满足臼益增加的访河请求并撼黼服务质量， 各种服务器必须保证2 4 7 的可靠性且足够强大，服务器的处理能力逐渐成为网络发展 的瓶颈，为此必须对服务器进行升级来提高性能，或采用多螽服务器组成服务器集群来 共霹签纛鬻户请求，嫠楚，擎缝楚秀缀瑟务器毽戆豹钱俊葵露赫责，瑟采麓溅务器集嚣 的方法也滩以进一步扩展。 1 。1 研究背景 p 2 p ( p e e r t o p e 科) 计算技术的出现目的就怒希望能够充分利用互联网中所蕴含的 潜在计算资源。p 2 p 中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的， 与基 ；筝曩涟疆上毙较溅费豹a s 计黪壤型不露豹建：p 2 p 诗箕模塑孛不再嚣剐服务器以 及客户端，系统中的释个节点之闻w 以直接送行数据逶信而不需要通过中闻鲍服务器。 p 2 p 技术弱化了集中服务器的功能，重视网络中所有个体的作用，强调的是个体之间、 系统之间、计算机之间的直接通信和联系，每个参与者既怒客户又是服务方，这使人 餐在琢t e 张e t 土豹共事行为薮提贾裂了一令更广泛豹藩次，後入织爨更主动我方式参与 到网络巾去。p 2 p 计算在h l t e m e t 和h l 缸拙e t 中融经存在多种应用，并且入们仍然在不 断的开发出新的更适念于p 2 p 计算的应用。当前的p 2 p 计算应用主要包撼酱及计算、 第l 页 协同工作、信息检索、文件共享和发布、广域网数据存储、实时通信等，其中文件资源 欺享直是网络技术发展的重要推动力，也是p 2 p 技术中最典型的应用。 在p 2 p 的文件共享系统中，用户之间可以直接共享文 牛面无需中央服务器，避免 了崔转绞筑基于w 礴熬共享方式中缀务器零霉或兔蛙链簸籁翡薅蘧。攘隔万懋鹣弱户 谭疆逶过p 2 p 共窜璇盘上的文 孛、毯滚乃至整个硬盘，繇鸯入都共享了德翻议为最有 价值的东西。这种用户间直接交流的方式，真正实现了甄联网共享和自由的梦想，p 2 p 文件资源共享具有广阔的应用前景。目前有很多研究项目都是针对p 2 p 的文件共享的， 包括f r e 铋e t 1 】、g 】t e l l a 【2 等。 。 p 2 p 瓣终戆纛 p 2 p 网络构建予现存的底层物理阿络( 通常是i n t 哪e t ) 基础之上，是现有网络之上 的一层覆盖网络，越发展经历了集中式、完全分布式和混式三代不同网络横魁。各种 模型各有优缺点，肖的还存在着自身难以克服的缺陷，因此在目前p 2 p 技术还未成熟 的阶段，各静网络结构袄然毙够共存，旗至呈现相互借壤豹形式。p 2 p 网络邀一步发展 必须充分考瘗箕叛下穗志： 节点的自治谯：每个节点都有充分的自治性，p 2 p 计瓣系统是在确傈备节蕊盼自治 性的前提下达列系统目标的。节点间相互无信任关系。 节点的动态性；h l t e m e t 环境下，终端节点会因为各种各样的原因( 自己断线或网 络连接不稳定、故障等) 加入或离开，节点的动态热入与退出是系统的一种常态。 p 2 p 诗算系绞毖矮憝够适应这静动态毪，在节点发生动态交建薅臻僳系统豹燕豢运 转。 节点、资源数燃巨大：h l t e m e t 上的节点数日巨大，可能参与系统的节点数众多， 管理的资源数日巨大，导致系统组织、管理复杂。 无集中管理，强分布性：p 2 p 系统融于参与的节点和资源众多，并且各个带点、各 类资源广泛分森，其毒天然的分布瞧。完全静分毒性剩予系统的鲁捧性和负载平衡， 毽系统熬夔溯、控翻、管理交褥穰篡复杂。 规模的可扩展性：随着用户的加入，不仅服务盼需求增加了，系统整体的资源和服 务能力也需要同步地扩充，才能较容易地满足用户的需瑟。即使在诸如n a p s t e r 【5 】 等集中型架构中，由于大部分处理激接在节点之间进行，大大减少了对服务器的依 赖，因而能够方便她扩展到数百万个以上的用户。面对予纯p 2 p 来说，整个体系是 全分毒豹，不存强瓶颈。理论上焚诞扩震蛙且乎可以认为是无疆豹。 1 2p 2 p 文件共攀系统特点 p 2 p 系统最大的特点就是用户之间巅接共享资源，p 2 p 文件共享应用已经成为互联 潮上缒主流应用之一。从用户数量上来餐，欧美比较流行的p 挣文 孛共享软件k 8 z z a 筹戆矮户数浚亿缀嬲诗算。筑繁宽溃糕采器，谗多i s p 未手带宽主要鼓p 2 p 文箨共享 第2 页 国防科学技术大学研究生院学位论文 占用，而且还在持续增长中。p 2 p 文件共享系统具有以下特点： 资源分布于异构的、广泛分布的节点。为了实现资源共享，p 2 p 系统中往往会有大 量的节点。这些节点通常是自主的，因而它们可能会频繁的加入和离开p 2 p 网络， 这使得p 2 p 网络在不停的变化中，它的变化比p 网络要剧烈的多。加入到p 2 p 网 络中的节点不仅在物理特征上( 延迟、带宽、性能等) ，而且在行为上( 共享文件 数量、生命周期等) 都具有非常大的差异。 资源的数据量大，资源更新频繁。 用户的兴趣是分组的 3 】，每个用户只对一小部分的分组感兴趣。用户的查询和下载 基本上集中在这小部分的分组内。 节点之间的信任程度差【4 】，在p 2 p 文件共享网络中，只有少于2 0 的节点有效工 作( 指共享文件) ，少于7 的节点提供了网络中9 0 的共享文件。这需要有效激励 机制。 p 2 p 文件共享应用的一个核心问题是有效的文件搜索机制，这也是提高网络可扩展 性、解决网络带宽被吞噬的关键所在。现有的文件共享应用对于共享资源的搜索主要采 取了一些广播搜索方法，其搜索效率低下并且消耗了大量的带宽。如何实现有效的共享 文件搜索是当前p 2 p 研究的热点问题。 1 1 3p 2 p 基本拓扑结构 拓扑结构是区别p 2 p 系统与普通的分布式系统的重要属性之一，p 2 p 网络与底层网 络拓扑区别很大，p 2 p 网络中直接相连的两个节点在底层网络可能相隔非常远。如何构 建有效的p 2 p 网络拓扑与该网络中采用的资源搜索算法密切相关，拓扑结构在很大程 度上决定了它所采用的搜索算法。目前应用的p 2 p 系统所采用的拓扑结构类型因为应 用的需求不同具体的结构也不尽相同，但是归结起来可以分为如下三种类型：集中式拓 扑、结构化拓扑和非结构化拓扑等。下面对几种结构逐一进行介绍，并对其中的一些结 构进行了评测。 1 1 3 1 集中式拓扑 集中式拓扑结构是p 2 p 开始流行时使用普遍的网络拓扑结构，用于共享m p 3 音乐文 件的n a p s t e r 【5 】是其中最典型的代表，这些系统把所有的系统功能以及信息资源都集中 在中心服务器上，客户端将其索引注册到服务器上并由服务器分类、维护。查询时客户 段向服务器提交查询，然后使用服务器返回的对象索引从拥有对象的节点下载对象。这 类系统定位开销为口f ，同时系统的维护开销为臼f ，其中为节点规模。其实现和 维护较为简单。由于这些中央服务器很容易成为系统的瓶颈所在，所以负载比较重的应 用系统一般都具有一个环型的服务器集群来实现负载平衡和容错功能。整个系统因此就 形成一个组合拓扑结构：客户端与服务器之间是集中式结构、服务器之间采用的是环型 拓扑结构。采用这种组合式的拓扑结构在某种程度上提高了系统的性能。图1 一l 是集 第3 页 国防科学技术大学研究生院学位论文 中试掇羚结构戳及环黧与集中式穗组合翡拓扑结稳豹示意莲。 图1 1 集中式拓扑结构 简单是集中式系统的一个重要优点，同时因为只有一个节点需要进行保护所以该系 统一般也是e b 较安全的。集中式系统最大的缺点也是因为系统巾的数据都存储套一处， 当送令中。0 l 受务器密瑷镶误薅，系统中豹掰露苓熹郝不能够爱露王终。这撵豹系缝浚骞 容镱功能同时不能够掇供隐私保护。 1 1 3 2 结构化拓扑 强p e s 坶网、p 豁矬y 【7 】、c h 喇【8 】耱c a n 【9 】是蠢翦研究：器公认躲基于d 疆敦典蒸斡 p 2 p 攘矜。萁串在e h o 斑中，往 霉k 彰( 铡魏，文嫠名) 窝实舔鹣参与节纛( 蛋圭| 亟缓) 逶 过h a s 撼n 叠映射到同一个周长为2 “的逻辑标识环上，其中，黼的大小应该使得该环足 以裙纳最大可能的参与节点数，同时使得雠何两个k _ c y 或节点映射到同一环节点的概 率可以忽略。在逻辑标识环中定义了后继的概念，对于节点和k e y 来说，其后继就是 环中下一个实际存在的节点。与对象相关的索引存放在其k e y 对应的后继节点中，因 魏，褒每个节点都知遴葵螽继节点的馕猿下，给定一个k c y ，漆鹰继链，可以确定性逡 拽翔该x _ e y 鞠痊静存款节点。e h o 斑为减少宠键开销，在每个帮杰绦罄一个辑谓豹瓤n 秽 袭，用于指向环中距该节点分别夕、，的节点，因此c h o 柑可以保证在o 耀印 的簸杂上界内确定性地定位对象，这里，为系统规模。c h o r d 的邻居表为? d j 圳项， 即拓扑维护开销为o 锹m 。c h o r d 的结构如图1 2 所示。该缡构优于集中式拓扑缩梅 的优点就是它的负载均糖以及简单的可扩鼹性，可以在环上增加节点，其负载能力会睫 豢繁焘数量豹增热基本戏绞毪遂长。 图1 2c h o r d 环形拓扑 第4 贾 重堕登堂篓垄盔兰翌塞尘鏊皇垒逾基 与c h o r d 不同的鼹，c a n 的拓扑基于一个逻辑的d 维笛”静尔空间，节点( 地址) 和对象 k e y 都被h a s h i n g 刭该空间的某一逻辑坐标上，每个节点负责存放与其坐标相近的对象 索引。其几何拓扑结构如图2 - 3 所示。c a n 的对象定位上界为。刎哆，其中为网 络串熬参与节点数，矗为c a n 所基予戆警卡零空闻的绫数。c a n 戆拓扑臻护开链为 0 囝。 图1 3c a n 几何拓于l 透过 t 安联文整装确匹配套谯，双瑟保证弱终孛存在熬文档必定麓簌鸯鞭酌魏 数内找巍。荚优杰蔻薅络流量小，囊询舞销可激预羹，势慧查询结采是确定瓣。毽它没 有考虑实际网络拓扑和节点性能( 带煮、存储空间和处瑷器能力) 的不同，而且如果一 个节点提供共享的内容表示越复杂，则哈希函数越不好选撵，相应的，网络的拓扑结构 就越复杂。而如果内容表示简单，则又达不到真正实现依据内容定位的能力。目前大多 数d h t 方式豹p 2 p 蹲络对节点所提供炎事内容酶表示都缎简单，一般仅仅为文件名。 。 3 3 无结构旅羚 许多信息共窜系统f r e e n e t 1 】、g n u t e l l a 【2 】都是采用无中心、无( 确定) 结构拓扑， 它们结合使用多种类型拓扑结构来形成组合式拓扑结构。猩这类系统中不存在索引服务 器，每个节点通道筹于邻居节点与网络连接，查询请求遇过邻居节点在弼终巾避零亍“广 撵”，符合请求瓣节点兹攘至l 广撂谤袋爱怼请求节点遴露疲答。这类系统熬羧羚维护聂 销必o ( 磅，定佼开销为o ( 嬲，其中为系统设定的节点专耀个数，为系统艇横。图2 4 是无结构拓扑示意图。 采用无结构拓扑的系统一般比较难以控制管理，同样凼于系统中的节点w 以随意加 入，使得系统中的带点很难能够保证安全性。无结构拓扑系统一般具有比较好的容错功 黥，一个节点出现镑误不会影响其它带点，同时糍够提供疆名支持。 无结穗菸羚系绫鹣哥扩藏毪氇 0 较滚评测，理论上漤，撩入茨节熹数嚣怒多，无结 构拓扑系统的工作力越强。但实际上，为了保证系统的致往的操作常常会出现很多 额外的开销，如果遮些额外的开销随蓿系统的规模增长，系统也不会具有很好的可扩放 性。无结构拓扑系统的最大优点是该种结构系统的信息资源加入和退出非常容易，比如 在g 硼t c l l a 中任慧节点可以随时加入这个网络著立即将自己的信息资源共窜给其它用 户。 第5 页 国防科学技术大学研究生院学位论文 图1 4 无结构拓扑示意图 结构化拓扑构造的p 2 p 系统其网络结构是预先确定的，无结构拓扑在拓扑构造上具 有随意性。无结构拓扑的优势在于实现相对简单和便于维护。结构化拓扑的优势在于其 对象定位机制较小的网络开销和确定性的定位上界，然而，由于其确定性的结构造成维 护上比无结构拓扑更为困难。基于无结构拓扑的p 2 p 应用往往基于广播搜索机制，广 播搜索机制的优势在于支持模糊匹配所带来的可选择性。遗憾的是，广播搜索机制造成 的消息开销成了影响无结构拓扑扩展性的一个关键因素，与之相反，结构化拓扑采用的 精确匹配的对象定位机制由于无法有效支持模糊匹配而在的可选择性上有所欠缺。两者 呈现出优势互补，如果将这两者有效的结合在一起将能产生较好的搜索效果。 研究界对结构化和无结构拓扑的优劣尚无定论。有研究指出，通过对广播搜索机制 的适当优化，可以有效减少其带来的消息开销【1 0 】。同时，通过为结构化拓扑的确定性 定位机制增加语义转换中间层和多播机制，也可以带来一定的可选择性。 1 2 主要研究内容 搜索是p 2 p 文件共享系统的一个基本问题，对于系统性能往往有决定性的影响。 在结构化网络中，查询能够在有限的跳数内查找到目标，但它必须首先知道要查找的文 件。非结构化网络能进行模糊匹配查询，但现有的泛洪式查找方法开销太大，不利于网 络规模的扩展，一些改进搜索方法主要是利用查询的结果来减少查询开销，没有充分挖 掘p 2 p 网络节点之间的联系。 针对这些问题，本课题主要研究了以下内容： 1 分析了复杂网络中z i p f 分布，p o w e r - l a w 和s m a l lw o r l d 等基本特征，利用这些特征 来辅助通用模拟器和文件搜索算法的设计。 2 提出了一种新型分布式文件搜索方法f r f s 。该算法充分利用了当前p 2 p 领域 和复杂网络领域的基本结论，尤其是统计规律，实现了高效的搜索剪枝。在体系结 构设计上，f r f s 提出了一种混和体系结构，原始数据的存储和检索采取d h t 网络， 元数据的存储和检索采取非结构化网络。在搜索算法上，f r f s 提出了基于朋友关 系的搜索算法，节点之间按照搜索兴趣和共享文档关联建立朋友关系，搜索请求首 先在朋友节点之间传播，对于少数不能完成的请求通过基于d h t 的应用层广播继 续搜索，搜索过程集成了搜索结果缓存设计。采用了基于w e b 的日志数据和仿真数 第6 页 墅堕型堂堇查盔鲎缝壅兰堕兰壁鎏塞 搬对k 疆s 散了充分溺试。 3 设计并实现了一个繁于文件共享搜索的通用p 2 p 模拟器，该模拟器具有良好的可扩 展性，能够支持多种p 2 p 模型的模拟；允许在相同的网络条件下进行各种算法和协 议的比较，并能对模拟结果进行多角度的分析；同时支持w e b 日志数据和仿真数据 作为测试数据。 量1 3 论文结构 企文共分五章，各鬻的组织结构如下： 籀一章为绪论部分，主溪介绍了课题研究的背景，p 2 p 技术程文件共享领域的威用 及p 2 p 霹络静基本麓络臻羚结梅； 露二章奔绥了典鳖验p 2 p 共享文捧系绫秘鬻雳静搜索算法，并对凡释典墅豹抛p 网络模拟器进行了分析； 第三章提出了一个文件共享搜索的具体算法和改进，并采用了多组数据对算法从多 角度进行了充分的测试； 第四章给出p 2 p 通用模拟器设计及其实现，并对模拟器的并行运行进行了初步蛉探 瓣； 第纛章为结束语，总结了奉文静工佟势辩泰来豹研究方淘谶行了震望。 燕7 炎 国防科学技术大学研究生院学位论文 第二章相关工作 信息社会中，人们越来越重视信息资源的共享，且人们越来越希望发布自己个性化 的内容。可以说信息资源共享的需求直接引发了p 2 p 技术热潮。传统共享方式是将文 件上传到服务器，用户再到服务器去下载，虽然易于管理，但限制较多。而电子邮件以 对等的方式方便了个人间文件的传递，却未能解决大范围的文件交换。如今人们越来越 希望交换各种多媒体文件，传统的c s 模式在带宽和存储方面都无法满足人们的需求。 p 2 p 资源共享解决了经典共享机制无法解决的大文件交换问题，是p 2 p 应用最为成功的 一个方面。在p 2 p 技术的多种应用中文件资源共享一直是网络技术发展的重要推动力， 也是p 2 p 技术中最典型的应用。 2 1 典型的p 2 p 文件共享系统 p 2 p 文件共享系统是当前的p 2 p 研究热点，有多个实际运行系统和实验研究系统。 这里根据这些系统采取技术的不同选取了一些代表性的系统。 2 1 1 g n u t e i | a 2 g 姗t e l l a 是继n a p s i 盯之后最流行的完全分布式p 2 p 系统，它采用典型的广播泛洪搜 索模型。g n u t e l l a 没有任何中心服务器，用户在自己机器上启动g 删t e l l a 时选择多个网 络中的节点来连接。当节点要寻找一个所需的文件时，它先将查询消息发送到它连接的 所有节点，节点收到查询请求后先在本地的共享文件中搜索，匹配不成功则又转发给所 有邻居，直到查询请求得到满足或超过一定的跳步数( 或称为生存周期( t t l ) ) ，根据 s m a l l w o n d 定律，跳步数通常取5 到9 即可。所有得到查询消息并拥有目标数据文件 的节点都将结果返回给查询发起节点，用户可以从所有返回结果中选择一个适合的节点 进行下载。 g 彻t e l l a 的优点是无集中服务器，全分布，避免了集中服务器所带来的各种问题。 其主要缺点是带宽消耗大，从而导致可扩展性差，但在局域网中效率较高：此外，模型 的查询定位是不确定的：即实际存在的文档可能查询不到。 2 1 2 j x t a s e a r c h 1 1 】 j x l a s e a r c h 是s 1 1 1 l 公司推出的j x r i a 工程的一部分，提供文件信息共享服务。系 统结构为层次结构，系统主要由三个部分组成：h u b s ，c o n s u m e r sa l l dp r o v i d 盯s 。h u b s 之间以对等的方式互联，充当超级节点的角色。p r o v i d e r s 在h u b s 上登记自己发布的信 息，c o u s u m e r s 向h u b 发送检索请求，h u b 如果在本地不能找到，则将请求转发给其它 h u b s 。信息提供者采用x m l 的格式将信息注册到一个q u e r y s p a c e 中。 j x t a s e a r c h 是带有超级节点的搜索模型。超级节点本身存在性能瓶颈问题。此外 超级节点之间采取广播方式，系统可扩展性仍然受限。 2 1 3 n e u r o g ri d 1 2 与目前的多数系统依赖于单个系统提供自己内容概括或者无元数据描述不同， 第8 页 里堕型兰垫查盔堂婴塞生堕堂堡垒苎 n e u r o g r i d 利用搜索的结果获取关于文档存放的知识，主要包括以下两个技术：语义路 由和学习算法。n e u m g r i d 通过记忆节点存储的文件的关键词进行路由，每次查询成功 的节点将返回作为知识存储，收敛稳定后基本上一跳就能查找成功。该方法存在的问题 是其知识表过于庞大，对于该表的维护开销比较大，此外信息的更新比较慢：抗攻击能 力差；不支持对搜索结果的排序。 2 1 4 k a z a 1 3 k a z a a 把加入系统的结点按照其能力分为两类，强结点和普通结点，每个普通结 点都隶属于一个强结点。这样就允许强结点维护了一个关于所有隶属于他的普通结点文 件的数据库，包括了其从属的普通结点的文件标示和对应的口地址。每个强结点也通 过t c p 连接一定数量的其他强结点。存在连接的两个结点间周期性的交换强结点列表。 k a z 啦的典型设置中，每个普通结点维护一个包括2 0 0 个强结点的列表，而每个强结点 维护包括上千强结点的列表。在这个列表中，每个结点对应的表项都包括一个时间戳， 当结点收到新的结点列表时，会把时间戳较为靠前的结点替换掉。 k a z a a 因为其简单有效现在非常流行，和j x t a s e a r c h 一样由于超级节点本身存在 性能瓶颈问题而难以有更大的发展。 2 1 5 f r e e n e t 1 f r e e t 是自适应的p 2 p 文件基享应用，系统强调匿名性。f r e e t 利用大量网络节 点的共享存储空间，可进行数据的发布、复制和检索，同时保证数据的发布者、读者、 提供存储空间者的匿名性( 无法根据数据找到它的发布者和读者，文件被加密，存储节 点不知自己存储的数据的内容) 。文件被加密，以位置无关的方式存放到某节点上，经 常被访问的文件会被在靠近访问者的节点上进行复制，很少访问的文件最后会从系统中 消失( 因而不是一种持久性存储系统) 。文件的查询请求被路由到最可能的物理位置， 定位性能与h a s h i n d c x 的分散定位类算法性能基本相当，但有一定的不确定性。该方法 存在问题是：不支持模糊搜索，用户必须知道精确的关键词；搜索具有不确定性。 2 4 6 a i p i n e 1 4 】 a 1 p i l l e 采取组的方式管理共享信息。用户可以定义组，并邀请其它用户加入组，组 内用户共享文件。组内用户维持全连接，不存在路由转发。每个组用户根据自己请求的 满足程度对其它用户进行信任度评估。该方法存在问题是组的建立依赖于对等网络之外 的用户联系；组的规模受限。 2 1 7 a n t h i ii 1 5 a n 1 i 1 1 是由多个n e s t 节点组成的网络，n e s t 通过产生自治的、在网络中移动的a n t 来完成客户请求。不同的应用通过不同的蚂蚁算法完成。蚂蚁之间不直接交互，而是通 过在经过路径的n e s t 节点留下信息实现间接的交互。 g n u t a n t 是在a n t h i l l 集成上开发的文件共享应用，结合了g n u t e l l a 、f r e e n e t 的优势， 通过三种蚂蚁的爬行完成文件共享。h l s e m t 负责发布、s e a r c h a m t 负责查询、r 印l y a m 负责尽早返回查询结果。文件的元数据包括关键词和h a s h 值。路由是通过对关键词作 h a s h 形成的表，类似于f r e e n e t 使用的方法。a n t 在路由的时候，如果找到匹配的关键 词，则直接过去，否则选择去关键词h a s h 值最近的节点。随着时间的推移节点将专注 第9 页 国防科学技术大学研究生院学位论文 于部分关键词空间。该方法的搜索结果也是不确定的；只能支持基于关键词的查找。 对于现存系统和搜索技术分析和总结不难发现系统的体系结构相当程度上影响了 系统的性能。g n u t e l l a 等广播和n a p s t e r 等集中式的体系结构都存在不可避免的缺陷， k a z a a 混合式结构缓解了中心服务器的压力，但强节点还是存在瓶颈问题。f r e e i l e t 采 用了一种类似于d h t 的定位算法能快速有效的定位到文件位置，n e u m 僦d 利用了搜 索的结果反馈来指导以后的查询，这两个系统分别采用了结构化和非结构化网络，都有 着自身难以克服的缺点。我们在第三章提出的文件搜索算法采用的混合式结构正好综合 了它们的优点，有利的支撑了搜索算法。 p 2 p 文件共享系统中有三个主要的问题需要解决：搜索和定位，数据传输，信誉激 励和安全相关问题。数据散布在广泛分布的节点上，如何组织管理好这些存储资源和数 据，按照用户的需要高效准确地定位到正确的数据是基于p 2 p 的文件共享系统的核心 问题。 2 2 文件共享系统搜索方法 搜索是p 2 p 文件共享系统的核心问题，对于系统性能往往有决定性的影响。按照时 间顺序可以将共享文件的搜索划分为3 个阶段 1 6 】：w h a t 阶段：确定需要查找的文件； w h e r e 阶段：查找所需文件的位置；h o w 阶段：下载所需文件，可能从一个或者多个位置。 其中w h e r e 阶段最为复杂，p 2 p 网络中数据资源分布在各个独立的节点上，如何高效 地索引、查找、定位以及访问这些数据信息资源是一个巨大的挑战。 资源搜索算法与所采用的p 2 p 网络拓扑密切相关，拓扑结构在很大程度上决定了它 所采用的搜索算法，对于结构化拓扑多采用基于分布d 日r 的单播方式的对象定位，对 于无结构网络往往采用基于广播的搜索机制。 现在流行的p 2 p 文件共享系统大多采用无结构化网络，下面我们主要分析在无结构 化网络中采用的搜索方法。根据节点是否利用相关信息来定位资源，可以将搜索方法分 为两大类：盲目搜索和信息搜索。盲目搜索中的节点相互独立，通过在网络中传播查询 信息并且把这些信息不断扩散给每个节点，通过这种泛洪方式来搜索想要的资源。而信 息搜索在搜索的过程中利用一些已有的信息来辅助查找过程。由于信息搜索对资源的存 储有一些知识，所以信息搜索能够比较快的找到资源。 2 2 1 盲目搜索 盲目搜索对信息搜索提供了有力的支持，不过盲目搜索认为节点间是完全独立的， 不存在任何的关系，因此它向所有邻居转发消息，为了减少消息数量，只能牺牲查找的 成功率来缩小查询范围。盲目搜索包括了f 1 0 0 d i n g ，n e r a t i v ed e e p e n i l l g ，r a n d o mw i l k 和g n u t e l l a 2 等方法，下面详细介绍这几种搜索方法。 f l o o d i n g 搜索在较早的g n u t e l l a 系统中使用的一种搜索方法，当它要寻找某个文件， 把这个查询信息传递给它的相邻节点，如果相邻节点含有所要查找的资源，则查找成功。 第l o 页 堡堕整耋熬蕉茎兰堑塞竺塞兰燕燕薹 如果它相邻的节点都没有命中这个被查询文件，就把这祭消息转发给自己的相邻节点。 这种方式像洪水谯网络中各个节点流动一样，所以叫做f l o o d i n g 搜索。f 1 0 0 d i n g 首先遍 历自己的邻接点，然后再向下传播，邋过七层转发能搜索十万以上的节点，所以f l o o d i n g 搜索豹残功率鞠豢麓。对于嚣骞文糖融予翼分布在缀少的节燕上，在有限熬转发辨数内 其搜索戴功舂缀大静不确定往。蠢予搜索把消惠簧援绘掰鸯黥邻接点，它瀵蕤了大量瓣 网络带宽，使消息堵塞严重，效率 b 较低，扩展往不好。 在f l o o d i n g 的錾础上有一种改谶的搜索方法，随机抽取定比例的相邻节点传递消 息，而不是像f l o o d i n g 一样把查询倍恩传播给所有邻接点。在r a n d o mw 勰c 搜索中， 请求者发出k 个豢询请求给随规挑选驰k 个相邻节点，如果还没有匹配到，则这k 个 节熹孛豹每个节蠡夔梗遥取一枣邻鼹转发该查诲。这褥簸多在瑗络秘产生黔翱臣条查 询信患，大大麓减少网络中静查询僚繇，毽由于每次是薅概选取部努邻藩搜褥查询成功 率相当低，是弧牺牲查询成功率为代价来了减少查询u 开销。 i t e m t i v e d e e p e m n g 搜索【1 7 】利用减少查询跳数来限制凌询开销，在搜索柳始阶段， 给t t l 设定一个比较小的值，如果程t t l 减为0 ，还没脊搜索到资源，则给t 1 l 重新 赋更高的值。这种搜索方法效果势不稳定，当查询结束条锋秘用户自定义黥纛询戏功的 数量程关联薅可辘霉激减少覆素豹拳经，程是在最舔瓣骥嚣下，延遥缀夭。 在盲目搜索巾搜索优纯主要逶i 建减少搜索开销来避行，但舜辩会降低森游的成功 率，使文档的搜索具有较大的不确定性。g n u t e l l a 2 1 8 】综含的集中和分布搜索的特点取 得了较好的