（计算机应用技术专业论文）对等网络中搜索算法与资源最优分布策略的研究与应用.pdf

对等网络中搜索算法与资源最优分布策略的研究与应用 摘要 随着i n t e r n e t 与计算机硬件技术的飞速发展，越来越多的人开始通过网络 交换信息、获取服务。截止2 0 0 3 年，全球网站数量超过8 ，7 1 2 ，0 0 0 个，全球 i n t e r n e t 用户超过一亿：但是在这样一个信息、计算和存储资源都异常丰富的 分布式信息系统中却存在着访问延迟、通信错误、服务器过载以及负载不平衡等 一系列急待解决的问题。 造成这些问题的一个重要原因是由于i n t e r n e t 上所广泛采用的集中数据存 储与网络管理模式，即c s 架构。这种访问模式简化了资源搜索过程、网络管理 方式以及安全认证策略，但是对核心网络造成了巨大压力，从而引起了网络局部 应力过大，单一故障点增多以及扩展性降低等一系列弊端。通过w e bc a c h e 、集 群系统( c l u s t e r ) 以及c d n 等技术虽然可以在一定程度上提高服务器的处理能 力和鲁棒性、降低访问延迟以及减少不必要的通信负荷，但是近十年的数据表明， 网络局部饱和，服务质量下降的现象仍十分普遍。 为彻底解决这些问题，一个新的研究领j 葑一对等网络与对等计算，提供了 一个有效的解决思路。对等模式即p 2 p ( p e e r - t o p e e r ) ，它抛弃了c s 模式中 服务器的束缚，网络中的每一个节点既可以成为服务器也可以成为客户端。在 p 2 p 网络中，资源和服务的获取不需要通过服务器，而是“资源在哪里产生就到 哪里获取”。因此p 2 p 对于解决网络延迟，提高系统扩展性，增加数据的持久性 和安全性等方面都具有无可限量的优势。 本文首先针对p 2 p 网络中的核心问题端搜索与发现算法，做了深入的分 析和探讨。针对不同类型的p 2 p 网络，本文综述了三种最典型的端搜索和发现算 法洪泛算法，目录算法和动态h a s h 算法，并结合g u n t e l l a 、n a p s t e r 、c h o r d 和c a n 等实例对这三种算法的实际应用效果进行了比较分析。结果表明洪泛算法 实现简单、收敛快，但是不具有很好的扩展性，并容易导致广播风暴；目录算法 具有简单的协议和较高的查找效率，但是它所采用的目录服务器是网络中的单一 故障点，同时也成为了系统进一步扩展的瓶颈；动态h a s h 算法是p 2 p 研究中的 热点，它具有天然的散列性和动态性，并且具有快速查找的性能，但是尚未实现 实际的应用。 对象的最优分布策略是直接影响到p 2 p 网络可扩展性和稳定性的又一重要问 题，文中对该问题作了系统的建模，并在此基础之上比较了两种著名的对象最优 分布算法h i l 卜c l i m b i n g 算法和启发式算法。基于同样的模型，文中提出了 一种新的对象最优分布算法路由表算法，并重点讨论了该算法的实现。通过 分析表明，该算法具有较好的时间复杂度和信息复杂度，并适用于各种分布式计 算环境。 针对p 2 p 网络的应用p 2 p 计算，文中以消息发布系统一p u b l i s h n e t 为例 介绍了通过j x t a 平台实现p 2 p 应用系统的过程。该系统在j x t a + j 2 s e 环境下丌 发，保证了平台和语言的无关性。p u b l i s h n e t 的工作过程不需要服务器参与， 所有的通信都在对等点之间进行，并且每个节点都可以成为消息的发布者或订阅 者。它最大的优点在于强大的搜索能力和高度的可扩展性，同时数据的本地存储 也保证了用户的隐私。 关键词：对等计算，对等网络，端搜索与发现算法，对象最优分布算法，p 2 p 消 息发布系统 t h er e s e a r c ha n d a p p l i c a t i o n o f s e a r c h i n ga l g o r i t h m a n d r e s o u r c e s o p t i m a l a l l o c a t i o n s t r a t e g y i np 2 pn e t w o r k a b s t r a c t a st 1 1 eq u i c kd e v e l o p m e mo fi n t e m e ta i l dc o m p u t e rh a r d w a r et e c h n o l o g y ，m o f e p e o p l es t a l lt oe x c h a n g ei n f b 瑚a t i o na n dg e ts e r v i c e s 疔o mn e t 、v o r k s b yt h ee n do f 2 0 0 3 ，也e r ei sm o r et h a n8 ，7 1 2 ，0 0 0 、v c b s i t e 孤d 也eu s e r so nt 1 1 ei n t e m e ti se x c e e d i n g 1 b i l l i o n ；h o w e v e r ，、 r i 也i ns u c had i s t r i b u t c dg i o b a li n f b r r l l a t i o ns y s t e mw i t hs u c h 锄p l yi n 佑n n a t i o nr e s o l l r c e s ，c o m p u 诅t i o np o w e ra 1 1 ds t o r a g ec a p a b i l i 咄t h e r eh a s b e e nal o to fp r o b l e ms u c ha sa c c e s sd e l a y c o m m l 】j 1 i c a t i o ne 玎o r sa n d 蚰b a l a l l c e d l o a d r e s e a r c h e r st r yt os o l v et h e s ep r o b l e m so nt h el m e m e tb yu s i n gw e bc a c h e ， c l u s t e ra 1 1 dc d nt oi m p r o v e 也ec 印a b i l i t ya n dr o b u s 协e s so fs e r 、r e r ，d e c r c a s et h e a c c e s sd e l a ya n dr e d u c et l l eu 衄e c e s s a r yc o m m u n i c a t i o nl o a d b u tt h er e c e n td a t e f r o ml a s tt e ny e a r ss t i l ls h o w so v e d o a d e ds e r v e ra n dd e 口a d e ds e n ，i c e s i no r d e r t o s 0 1 v et h e s ep r o b l e m ，m o r ea n dm o r ed e s i g n e rh 舔f o c u s e d l e s er e s e a r c hi n t oo n e a r e a - p e e 卜t o p e e rn c t w o r k sa n dp e e r t o p e e rc o m p u t i n g 1 “o s to tt h es e n ，l c e so nt h ei n t e m e ta r eb a s e do nc sm o d e l c sb a s e ds e i c e s u s ec e n t e r e dd a t as t o m g ea l l dn e t 、v o r km a l l a g e m e n t ，w h i c hs i m p l m e dt 王l er c s o u r c e s s e a r c l l i n gp r o c e s s b u t o nt h eo 也e rh a l l di ta l s ob r i n g s p r o b l e m ss u c h a s1 0 c a lo v e r l o a d ， s i n g l ep o i n to f f a i 】u r ea n dl o w e x t c n s i b i 】i 劬p 2 pm o d e l 疗e ei t s e 】fb ya b a l l d 砌n gt 1 1 e s e r v e ro fc sm o d e l ，w h i c hm e a n se v e r y p o i n ti i lm e n e tc o u l db eas e r v e ro rc l i e n t i n t h ep 2 pn e t w o r k s ，c l i e n t sg e tr e s o l l r c e sa n ds e n r i c e s 谢血o u tm e h e l p 疗o ms e r v e ls o p 2 pi sg o o da td e c r c a s i n gt 1 1 ea c c e s s e sd e l a y ，i m p m v i n g 也ee x t e n s i b i l i t y i n c r c a s i n g t h ed a t ac o n s i s t e n c ya n ds e c u r i t y 1 1 1 i sp a p e rd e a l sw i m m ec o r ep r o b l e mi nt h ep 2 p n e m o r k s p e e rs e a r c h i n ga f l d d i s c o v e r y a c c o r d i n g t od i 虢r e n tt y p e so f p 2 p n e t 、v o r k s ，t l l i sp 印e rd i s c u s st h r e ek i n d s o fm o s t p o p u l a rp e e rs e a r c h i n g a n d d i s c o v e r ya l g o r i m f i 卜一n o o d i n g ， i n d e xa 1 1 d d y n 锄i ch a s h i n g f 皿h e r m o r e ，i tm a k e sac l o s ec o m p a r i s o na n da n a l y z e so ft 1 1 e s e a l g o r i m m sb yc a s eb a s e ds t u d i e s 1 h eo b j e c to p t i m a la l l o c a t i o ni so n eo fm em o s t j f n p o r t a n ts t r a t e g yn l a te 妇套c tt h ee x t e n s i b i l i t ) ，a n ds t a b i l i t yo fp 2 pn e t w o r k s ，t h i s p 印e r h a sp r o p o s e dam a t h e m a t i c m o d e l i n go f t h i sp r o b l e ma r l db a s eo nt h a tm o d e l ，“ c o m p a r e sm of h m o u so b j e c t a 1 1 0 c a t i o n a l g o r i t h i n h i l l - c l i m b i n g a n dh e l l r i s t i c a l g o r i m m f o rm ea p p l i c a t i o no fm u l t i m e d i as y s t e mi np 2 p n e t w o r k s ，t 1 1 i sp a p e rp r o p o s e sa h y b r i dm o d e l 、i t hb o t l lc sa n dp 2 pm o d e l ，w h i c hc o m b i n e st l l ep r i v i l e g e so ft h e s e t w om o d e l si no r d e r t oe i l s u r et l l ee x t e n s i b i l i t yo f 也es y s t c ma n dt h eq u a l i t yo fs e r v i c e 1 1 1 i sp a p e re m p h a s i z e si t sm s c u s s i o no nt l l er c a l i z a t i o no f o b j e c to p t i m a la l l o c a t i o ni n t h i sm o d e l 1 1 1 ea l g o t i l i i lf o r 廿l i sm o d e la c h i e v em es y s t e mo p t i m a la l l o c a t i o nb y t r y i n gt 0n n d a o p t i m a la l l o c a 主i o nf o ro n cc e r “nf i ku s i n gam e c h a n i s mm u c h l i k e m u t i n gt a b l e t h i sa l g o r i t l l m sa i i a l y z es h o w s i th a sg o o d c o m p u t a t i o nc o m p l e x i t y a j l d i n f o r n l a t i o n c o m p l e x i t y ， a n dc a nb eu s e di nv a r i o u sd i s 仃i b u t e d c o m p u t a t i o n e n v i m n m e n t f o rm e a p p l i c a t i o nb a s e do np 2 p n e t w o r k s p 2 pc o m p u t i n g ，m i sp a p e rm a k ea 1 1 i i l i t i a lt 珥i tb u i l d su pap 2 p m e s s a g ed i s 仃i b u t i o ns y s t e m ，t 圭l i ss y s t e md o n tn e e dt 1 1 e n a d i t i o n a ls e r v e ra i l da l lt l l ec o m m 嘣c a t i o na r ep o i n t - t o - p o i n t ，w h i c hm e a n se v e r v h o s tc a nd i s t r i b u 嚏eo rs u b s c r i b et oam e s s a g ew h i c hh e s h ei si n t e r e s t e di n t h e a d v a m a g e s o ft 1 1 i s s y s t c m a r e p o 、v e d u 1s e a r c h m gc a p a b i l i t y a n d e x t e n s i b i l i t y ； n l o 芏_ e o v e r ，t 1 1 e1 0 c a ls t o r a g eo f u s e r sd a t ap m t e c t st h ep r i v a c yo fp 2 pn e t w o r k u s e r s k e yw o r d s ：p e e r _ t o p e e rn e t w o r k s ，p e e “o p e e rc o m p u t i n g ，p e e rs e a 尊c h i n ga n d d i s c o v e o b j e c to p t h a lm l o c a t i o n ，p 2 pm e s s a g ed i s t 曲u t i o n s y s t e m 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 委员： 易) 确彩爱。 、 z 龟屏二以争敞 瓣 谚 粮叫 作 ! = ! ，钐易 轹力翌 弘 口e(、j 委 扎 耀 搐 衡 主 b “3 勘 ( 1 刁 知口 且 、任 抄向 姒 嵌 ，h1 吃呵l ( 一掣 叶争艺 1 、 插图清单 图1 1 内容分发系统( c d n ) 图1 2p 2 p 的发展过程 图1 3c s 计算与p 2 p 计算 图1 4c s 与p 2 p 两种模式下的网络结构 图2 1w 曲站点交换与p 2 p 传输的比较一 图2 2 分布式系统得抽象层次 图2 3 目录式的p 2 p 网络 图2 4 结构化的p 2 p 网络 图2 5 非结构化的p 2 p 网络 图3 1 洪泛算法 图3 。2 t t l = l ，2 ，3 时洪泛算法的效果 图3 3 通过消息i d 解决洪泛中l o o p 问题 图3 4 通过超级节点提高洪泛搜索的效率 图3 5e r 算法 图3 6 r w 算法( k = 1 ，h o p 习) 图3 7r w 算法( k = 3 ，h o p = 2 ) 图3 82 0 0 3 年g n u t e l l a 的用户数量 图3 9g n u t e l l a 的数据格式 图3 1 0 g n u t e l l a 的数据头格式 图3 1 1n a 口s t e r 的工作过程 图3 一1 2 相容h 勰h 图3 1 3 五个节点二维c a n 空间划分 图3 1 4c a n 的二维地址划分 图3 一1 5c a n 的查找过程 图4 1 三种启发式算法的仿真结果 图4 2p 2 p 视频点播系统 图4 3 图2 3 的p 2 p 拓扑结构 图5 1j ) ( t a 的体系结构 图5 2 t a 中的管道通信 图5 3 用x m l 描述的管道通信 图5 _ 4j x t a 中对等点i d 与管道i d 图5 。5j x l a 的查找过程 图5 6 通过j x t a 查找、发布文件 图5 7 p u b l i s h n e t 图5 8p u b l i s h n e t 中对等点的操作流程 2 4 9 p b b bm堪悖拇如姐勉m拍船勰弛h弘甜驼舭耶卯 表格清单 表1 1p 2 p 和w c b 站点之间的要素比较 表4 一l 三种h i l l c 1 i m b i n g 算法比较 表4 2 v 的初始表 表4 3v 2 的初始表 表4 4 v 3 的初始表 表4 5v n 的初始表 表4 6 v 6 的初始表 表4 7 v l 的新表 表4 - 8 v 2 的新表 表4 9 v 3 的新表 表4 1 0 v 4 的新表 表4 1 lv 5 的新表 曙弘拍弱拍拍弘弘弘弘 独创性声明 本人声明所警变的学位论文是本人在导师指导f 进行的研究t 作及取得的研究成枭。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包禽其他 已经发表或撰写过的 研究成果，也不包含为获得盘h 墨些盍堂 或其他教育机构的学位或证书而使用过的材 料。与我一同：i 作的同忠对本研究所做的任何贞献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字：签字日期：年爿日 学位论文版权使用授权书 本学位论文作者完全了解佥世3 ：些盍堂有关保留、使用学位论文的规定，有权保留 井向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阕。本人授权金 自墨工些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师繇粥c 2 芭导师签名：，刍幽c 2 p 勺 签字日期：r 多- 年一铀r q u 电话 邮编 致谢 值此论文完成之际，首先要衷心地感谢我的导师韩江洪教授。本文的研究是 在韩老师两年来悉心指导下完成的。他渊博的知识、敏捷的思维、创新的精神、 严谨的治学风格和开明的科研作风对我产生了深远的影响；他引导我进入了分布 式计算与自动控制领域，并为我提供了良好的学习和1 作环境和机遇，使我能顺 利的完成学业。 感谢实验室的张利和张建军两位老师对我在研究和工作上的指导两位老师 孜孜不倦的学习态度和勤勤恳恳的工作作风是我不断学习的好榜样。同时特别 要感谢实验室里和我朝夕相处的同学魏振春、马学森、王跃e 、石雷、陈海 兵、马克刚、江波、段玲玲、冯玲、毕翔、石小兰、王世福、朱芸，他们在学习 上给了我许多帮助和启发，与他们的讨论总能使我获益非浅。 这里，我要把这篇论文献给我的家人。多年来，我的家人始终是我的精神支 柱，没有他们的关爱和支持二十多年米我对学业的追求是不可能顺利完成的， 正是他们默默奉献习使我的生活变得更加美好。 最后，衷心地感谢所有关心和帮助过我的人们。 作者：王炯 2 0 0 5 年4 月 第一章绪论 1 1 对等计算的历史与现状 对等计算( p e e rt op e e rc o m p u t i n g ，p 2 p ) 2 心【4 j 作为分布式计算的一种新模 式，以其独特的性能在近年来受到人们越来越多的关注。由于采用了分布式控制 的方式，p 2 p 计算显示出了良好的自组织、自适应能力与扩展性，因而被广泛应 用在文件共享，存储系统，即时通信，协同计算，命名系统，搜索引擎，游戏软 件，企业网络等多个领域。 作为一种近年来被广泛关注的研究领域，财富杂志曾把p 2 p 冠以塑造 i m e m e t 未来的四大技术之一。但是对等计算绝非一种新的概念，i n t e r e n t 设计初 期，t c p i p 协议就采用了对等通信原理，即“通信双方不分主从，相互通信”； 此外，i m e m e t 路由协议中路由器之间的通信i ls j 也是对等的，因而同样体现了对 等计算的特征。但是除此之外几乎所有的i n t e m e t 应用如f t p ，w w w 都采用了 c s 的通信模型，使得人们几乎忘记了p 2 p 的存在1 3 j 。 随着i i l t e m e t 上新的服务不断出现以及对传统应用的不断深入，c s 结构的弊 端也逐步显现。首先，关联信息的集中存储，容易导致网络中局部结点( 服务器) 应力过大，最终导致网络瘫痪；其次，基于服务器的集中存储与控制方式容易让 少数节点成为黑客攻击的目标，安全性将无法保证( 例如d o s ) ：再次，c s 结 构的应用模型忽视了网络边缘客户端的巨大存储与计算资源，使得整个网络负载 极度不平衡；最后，多媒体应用的出现对网络提出了更高的带宽和性能要求。 在这样的背景之下，人们首先想到的是对c s 模型进行改进，以适应i n t e m e t 上用户数量与信息量的不断增长。w 曲c a c h e 利用用户访问流中时间和空间上的 一致性，将用户访问过的网页或数据保存在专门的一个或多个c a c h e 服务器中， 以减少客户端对服务器的访问流量，从而缓解了核心网络的压力，降低了用户访 问的网络延时；c l u s t e r 是一种服务器集群系统，它扩展了单一的服务器，提高 了服务器的存储和计算能力，缓解了服务器局部过载的问题，同时也提高了数据 的安全性：c d n ( c o n t e md e i i v e r yn e t 、0 r k ) 综合了w c bc a c h c ，c i u s t e r 等技术， 其目的是提高网络的整体性能，以实现数据快速，安全的传输，如图1 1 所示。 图卜l 内容分发系统( c d n ) ：数据源( s e r v e r ) ：r e v i s 甜c a c h e ：p r o x yc a c h e 亡 ：逐步减少的h t t p 访问流 无论是w 曲c a c h e ，c d n 还是c l u s t e r 技术，它们对原有c s 系统的改进都是 有限的。但是在c a c h e 、c l u s t e r 和c d n 中对分布式控制和管理的研究( 如对象 副本的合理分布，对象的分布式查找) 让人们重新想到了p 2 p 。最早出现的p 2 p 系统是n a p s t e r ，它可以支持1 0 0 万人共同下载音乐，然而n a p s t c r 的风光只是昙 花一现，它的h d c xs e r v e r ( 目录服务器) 很快成为了唱片公司的众矢之的，并 最终被迫关闭。但是n a p s t e r 却为p 2 p 的发展迈出了关键性的一步：在n a p 蝴 之后，出现了g n u t e l l a l l7 1 ，f r c e n e t l 3 耕，0 c e a i l s t o r e l 3 7 1 c h o r d 既p 髂t r y 【3 q 等一大 批p 2 p 网络，它们提高了系统的扩展性，改进了对象查找算法的性能。从c s 计算到p 2 p 计算的发展过程如图1 2 所示。 单纯的c s 应用：例如改进后的c s 应用：倒 搜索引擎和w e b如c d n - 曲c a c h e 图卜2p 2 p 的发展过程 p 2 p 的雏形：日录式p 2 p ，j 除此之外，业界各大公司也都在积极参与对等计算的研究与开发：i n t e i 组织 成立了p 2 p 工作组，并对u p r i z e r 大举注资，试图制定p 2 p 应用的业内标准。微 软在n e t 中加入了p 2 p 应用，此外，还开发了著名的p 2 p 文件存储系统f a r s i t e 2 6 1 。 s l l n 公司推出了j x t a 【2 ，它是一个完整的p 2 p 计算开发平台，可以支持任何网 络设备通过不同传输协议进行点到点的传输。 随着p 2 p 应用的不断深入，人们开始不断提出新的算法以加快p 2 p 网络中对 象的查找以及路由并实现更灵活的p 2 p 通信框架。同时各种基于p 2 p 的新应用， 新系统也在不断的发展之中。根据著名研究机构f o 玎e s t e r 的报道p 2 p 服务将很 快会与a d o b e ，p a l m 和a o l 整合，并占据超过3 0 以上的网络流量【。 1 2 研究的意义 p 2 p 计算抛弃了传统c s 模式下服务器的束缚( 如图1 - 3 所示) ，成为了分布 式计算领域的新范型；由于它本身所具有的分布式控制与协同工作的特性，使其 具有良好的自组织能力及可扩展性，为未来i n t c m e t 多元化网络结构与终端提供 了可持续发展的开放性平台。 随着越来越多的用户加入i n t c m e t ，这些不同的接入设备将为p 2 p 计算提供丰 富的存储与计算资源，它们将不仅仅是信息的消费者；在p 2 p 模型下，不同的 设备在成为消费者的同时也将为网络提供相应的服务，成为信息的生产者，从而 改变了c s 模型下，网络中心与边缘负载不平衡的弊端，保证网络的畅通运行， 如图1 4 所示。 a 图l 一3c s 计算与p 2 p 计算 在传统的文件共享与存储领域，p 2 p 将彻底改变集中数据存储和计算所带来 的种种弊端：系统可以无限扩展，数据保持高度安全性和持续性；在协同计算领 域，i n t e l 在不到两个月内通过p 2 p 方式收集到了超过6 0 万人通过p c 贡献出的 超过1 亿小时的c p u 计算时间，这样的运算能力即使是昂贵的大型机也是无法 比拟的：此外，p 2 p 计算还开创了许多i n t e m e t 上新的服务，例如即时通信系统 ( i n s t a l l tm e s s a 邸) 与交互式网络游戏。 图l - 4 c ，s 与p 2 p 两种模式下的网络结构 但是，p 2 p 计算仍然是一项新技术，在对象的搜索与分布，消息路由，安全 性等方面仍不够完善，现在国外已经开始大量的研究通过改进或发现新的算法来 提高分布式检索的效率，降低检索带来的网路的负荷，优化对象的分布，解决同 一副本的一致性问题以及降低开放个人空间后所带来的各种安全性隐患；同时在 p 2 p 应用领域，各种新的应用也在不断涌现，这些都需要人们进行更深入的研究。 随着近几年来a d s l 等宽带接入技术在中国的普及，接入网环境有了很大的 提高，从而为p 2 p 在国内的发展创造了硬件条件。但是，国内对p 2 p 的研究主 要局限于理论研究【4 1 j 1 4 2 j 【4 孤，少量的p 2 p 应用也大多是基于国外的平台，或者很 少考虑开放的协议与系统的互操作性，因此研究对等网络与对等计算将是一项很 有意义的工作。 1 3 论文的研究工作和创新点 论文是针对p 2 p 网络及其应用系统的研究。主要内容包括： 1 ) 基于实例，对现有p 2 p 网络( 如n 印s t e r ，q m t e l l a ，j x r i a ) 的网络结构、通 信协议、端发现算法、数据存储、信息获取咀及内容搜索策略等主要问题进行深 入研究。在分析归纳的基础上，比较不同p 2 p 系统的优劣，得出客观的结果。 2 ) 与g r i d 与c d n 不同，真正的p 2 p 采用分散控制的方式以获得最大限度的可 扩展性和灵活性，因此对等点加入，离开p 2 p 网络以及获取所需要的资源都依赖 于对等点搜索与发现算法。文中将对不同的端发现算法进行了分析总结。 3 ) 资源的最优分布是w 曲c a c h e ，c d n ，媒体播放系统以及p 2 p 网络所必需解 决的问题，文中对该领域的研究成果作了初步的分析和概括，提出了一种新的问 题模型，并给出了分布式的算法及分析。 4 ) 根据本文提出的p 2 p 网络资源共享模型，借助j x l a 平台实现基于p 2 p 的信 息发布系统p u b l i s h n e t 。 本文的创新点包括两个方面： 4 1 ) 针对基于p 2 p 的多媒体发布系统，提出了一种实现资源最优分布的算法，该 算法具有较好的时间和信息复杂度，易于在分布式环境中应用。 2 1 提出了基于p 2 p 的信息发布系统的模型，并通过j x t a 和j 2 s e 平台实现了该 模型的主要功能，印证了p 2 p 的高效性和可靠性。 1 4 论文的组织结构 各章内容安排如下： 第一章绪论。简要介绍了对等计算的发展背景，在此基础上阐述了本课题研 究的目的和意义，以及完成的主要： 作。 第二章对等计算的概述。本章分别讨论了对等计算的定义和分类，着重分析 了不同类型对等计算模型的特点，揭示了对等计算的核心问题，并比较了对等计 算与分布式计算、网格以及对等网络等相关概念的区别与联系。 第三章端查找与发现算法。作为对等计算分布式控制与存储的核心问题，端 查找与发现算法是对p 2 p 网络分类的基础。本章讨论了三种不同的查找与发现 算法目录式，h a s h 表式以及洪泛式算法，对它们的共性进行了概括总结， 对异性进行了分析比较。 第四章对象的最优分布。本章对对等计算中另一关键问题对象的最优分 布进行了详细的探讨；介绍了几种具有代表性的算法，它们已被广泛应用在多媒 体播放系统，c d n 和分布式文件存储系统之中；最后介绍了由作者提出的对象 分布优化算法和模型。 第五章基于j x t a 的消息发布系统( p u b i i s l 】n e t ) 。本章介绍了s u l l 公司 j x r a + j 2 s e 平台，并在此平台上实现了对等式的消息发布系统p u b l i s h n e t 。 该系统可以有效提高对象的访问效率，实现不同对等点的自主通信，不需要服务 器的参与，并且可以运行于各种不同的平台。 第六章结论。本章总结了本文所探讨的所有问题，并对未来研究的方向做出 了初步的分析。 第二章对等网络概述 2 1 对等网络的基本概念 目前，i n t e r n e t 上的各种应用( 例如w w w ，f t p ) 多是基于c s 模式开发的， 它们虽然功能相异，但是都具有相同的特点即集中数据存储与管理。p 2 p 网 络是一种完全分布式的存储计算系统，它倡导信息和服务在一个个人或对等设备 与另一个个人或对等设备之间流动”1 ；从另一个角度看，p 2 p 将基本的人际关系 协议移植到了计算机世界中，p 2 p 网络中的对等设备代表生产者和消费者之间真 正的交换终点，即“信息在那里产生，就在哪里交换“7 。 p 2 p 的优点在于： 1 ) 只要网络层工作正常，需要的文件总可以找到( 网络的容错性鲁棒性) 。 2 ) p 2 p 支持多个副本存储，当个别主机出现问题不会影响到数据的获取( 数据 的持久性) 。 3 ) 在p 2 p 网络中增加或减少新的信息不会影响系统的性能( 信息的可扩展性) 。 4 ) 在p 2 p 网络中增加或减少节点不会影响系统的性能( 系统的可扩展性) 。 2 。1 1 对等网络的定义 对等计算与对等网络是项新的研究，学术界对其尚未达成一致的定义。下 面是几种对p 2 p 以及p 2 p 网络流行的解释： 对等式( p 2 p ) ，即为了达到既定目标而进行的，生产者和消费者之间直接的 信息和服务双向交换的行为0 3 。 p 2 p 是一种人人平等的通信模型1 。 p 2 p 是一种网络，并且网络中的每一个工作站都具有同等的能力和责任。 p 2 p 是一种类型的应用，它充分利用了i n t e r n e t 边缘的资源例如存储，c p u ， 和信息o ”。 p 2 p 是一种没有固定的客户端和服务器的计算机网络，它的每一个节点都可 以成为客户端和服务器“。 p 2 p 是一种建立分布式应用程序的方式，每一个节点都具有对称的角色，而 不去对客户端或服务器作明确的划分1 。 美国威廉与玛莉学院的张晓东教授对p 2 p 网络做了比较全面的描述性定义： 1 ) 生产者和消费者的双重性。( c l i e n t s e r v e r ) ； 2 )网络的动态性。( h a st h ef r e e d o mt oj o i na 喇l e a v ea n yt i m e ) ； 3 ) 对等点之间巨大的差异性。( h u g ep e e rd i v e r s i t y ) ： 4 ) 广泛而开放的分布式系统。( aw i d e l yd e c e n t r a l i z e ds y s t e m ) 。 通过对各种p 2 p 与p 2 p 网络的定义，可以发现一个p 2 p 系统与传统w e b ( c s 模型) 相比应具有如下特点： 1 ) p 2 p 不是静止，节点动态的交换实时信息和功能；每个节点可以随时加入或 退出网络，而w e b 站点提供的信息往往在一定时间内是相对静止的。 2 ) p 2 p 的价值就在于双向的交换。p 2 p 提供了许多有趣的交换：用歌曲来交换 硬盘空间，用图片来交换录像等等，只要进入p 2 p 网络的人就会受益。而传统 w e b 站点中信息的交换是单向的，即用户向服务器索取资源。 3 ) 大多数有价值的信息，如程序、音乐、文档和演示文稿都是由作为对等体的 个人计算机所创建的，即对等设备代表了信息的根本目的地和数据库，因而p 2 p 可以保证用户可以获得及时有用的信息。而w e b 所采用的“发布”概念延迟了用 户获取信息的时间。 4 ) 对等计算利用了宝贵的资源，提供了诸如文件存储、网络带宽和处理周期： 在传统的w e b 计算中，个人计算机的这些资源利用率是很低的。 5 ) 对等系统不需要中介参与信息的存储与计算，完全是对等点直接交换信息和 服务，因而参与者将获得更高的效率和速度。 6 ) p 2 p 对等的概念就是要求每个参与者( 可能是一台p c ) 在使用这些服务和信 息的同时，也提供别人需要的相应资源，即生产者创建信息和服务的同时允许用 户访问和使用这些内容。 2 1 2p 2 p 模型与c s 模型 c s 是i n t e r n e t 的主要应用模型，它依赖于服务器为用户提供各种服务，如 w w w ，f t p ，t e l n e t 和d n s 。这些服务己在i n t e r n e t 上被广泛使用，并促进了 i n t e r n e t 的高速发展。c s 模型的优点在于： 1 ) 集中的数据存贮与计算有利于网络管理的实现； 2 ) 应用层不需要考虑路由问题； 3 ) 数据管理比较简单； 4 ) 由于一个服务器之上存储的数据往往是相关联的，所以基于服务器的安全性 问题比较好解决。 但是随着i n t e r n e t 上的用户逐渐增大，各种基于c s 模式开发的服务出现了 各种弊端：首先，随着网络上多媒体信息的逐渐丰富( 例如流媒体) ，传统的服 务器无法支持大量的多媒体访问请求( 普通p e g 格式的影片至少需要3 0 0 k 的带 宽) ：其次，根据i e e ei n t e r n e tc o m p u t i n g ( 2 0 0 1 ) 的数据显示，每年i n t e r n e t 上产生大约2 ”字节的数据，但是由于服务器的存储空间有限，只有3 2 字节 的信息可以被其他用户访问到( 大约只占总信息量的0 0 0 0 1 5 ) ；再次，一些热 门的服务器已成为了网络的瓶颈，但是大量高速接入网带宽却被闲置。产生这些 弊端的主要原因是来自c s 模型本身的缺陷： 1 ) 过分依赖服务器，可扩展性差；网络中有限的服务器资源不能满足用户对各 种信息和计算能力的需求。 7 2 ) 数据持久性差，不能保证用户随时获取信息。 3 ) 容易造成网络负载不平衡，大量资源被浪费。 4 ) 服务器往往成为网络中局部应力过大的节点，造成单一的失败点( s i n g l e p o i n to ff a i l u r e ) 。 在c s 网络中，个人计算机和其他移动设备被称为“边缘设备”，这些“边缘 设备”既不是提供h t m l 页面大型w e b 服务器，也不是提供电子商务服务的前端 设备，它们只是信息的消费者：另一方面，这些“边缘设备”中被保存了大量闲 置的数据，存储空间，计算能力和带宽。p 2 p 计算的目的就是充分利用这些资源， 实现边缘设备直接交互，建立全面的全球信息资源共享系统。采用p 2 p 信息交换 和c s 方式信息交换( 以w e b 为例) 的过程如图2 一l 所示，表2 1 分析比较了 p 2 p 和w e b 的主要特点。 表2 一lp 2 p 和w e b 站点之间的要素比较 项目 p 2 ph b 站点 数据交换对称不对称 内容和服务的可用性普通复杂 内容和服务的提供者较多较少 内容和服务的请求者较多较多 升级能力无限有限 隐私保护可以控制脆弱 网络的结构化和控制较低较高 请求分布大量不同的、动态请求大量相似，集中请求 网络范型完全分布式客户端服务器 数据格式不限 h t m l 机器类型任意大型服务器 八、 3 ，发 1 茴夕 i 请求 2 转换、嘴换 、要厂 l 建 竺 自i 口 蓿 j # 霭 r i 产 1 l 2 查看li1 创建 图2 1w 曲站点交换与p 2 p 传输的比较 2 1 3 对等计算与分布式计算 分布计算是指在分布式系 统上进行的计算。其中分布式 系统指的是一些独立、互联的 计算机的集合，它们能够协作 完成既定的任务( 独立的计算 机是指在内存和程序执行空间 相互独立的计算机，通常也被 称为松耦合计算机“1 ) 。 c a l i f o r n i ap 0 1 y t e c h n i c s t a t eu n i v e r s i t y 的m l l i u ”对分布式计算进行了分层 的抽象，如图2 2 所示。可见 对等计算是分布式计算中的一 种独特的模式，随着对p 2 p 研 究的逐步深入，许多采用c s 抽 像 j o c ts p a c e ，o 。1 1 曲t i v ea 印l i c a t i s o s e r v i c e s ，0 田。移动代理 r m 吐em 叼c e d 吡ec a l l 。r e ，d ) t et t h o d h w o 。a i 呻 c s ，p 口 m e s s a 日ef a s s i n g 圈2 2 分布式系统的抽象层次h 模式实现的分布式