(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf_第1页
(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf_第2页
(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf_第3页
(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf_第4页
(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf_第5页
已阅读5页,还剩47页未读, 继续免费阅读

(计算机系统结构专业论文)对等网络搜索机制及资源管理的研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 摘要 伴随着计算机的处理能力和网络速度快速发展,人们越米越广的使用计算机。如何有效 利h j 这些大量的计算机资源已成为一个热点问题。当前利用这些地理分布的、闲敞的计算资 源技术有对等网络和网格技术。对等网络在文件共享取得巨人成就,止人们认识到对等网络 是实现信息资源共享的高效方式。与此同时,网格的研究也取得很人的突破。 对等网络按结构的不同可分为结构化对等网络和非结构化对簿网络。与非结构化对等网 络比较,结构化对等网络具有查找效率高和查找确定性等优点。路由算法是结构化对等网络 的核心,它的路由效率、可扩展性和容错性对对等网络有着很重要的意义。如何提高当前结 构化p 2 p 网络的路由性能呢? 还有,如何将非结构化p 2 p 网络应用到搜索引擎上? 如何实 现p 2 p 资源有效管理呢? 如何将p 2 p 和网格两种技术融合起来? 如何将p 2 p 技术应用到电 子邮件系统? 等等。这些问题是当前p 2 p 研究遇到的难点也是热点问题。本文试图解决 上述问题。并做出如下几个方面的贡献: 1 融合p 2 p s u 网格两种技术 网格$ 1 p 2 p 技术有着不同点也有很多相似之处。就目前广受欢迎的应用来看,p 2 p 侧 重于文件存储,而网格侧重于大规模计算。我们在p 2 p 和网格融合的环境下做了不少研究工 作,例如分布式搜索和资源管理等。 2 提出一种拥有高效路由性能的结构化p 2 p 系统 由丁i 缺少考虑实际网络结构,当前结构化p 2 p 系统女n c a n ,c h o r d n p a s t r y 等有着高延迟、 低效率的毛病。在t a c h o r d 系统中,本文提出与实际网络结构相关的路由方法,以及一种基 于c h o r d 的系统。在实验仿真中,用物理跳数、域问的延迟和每个消息占用的带宽米衡鼙 t a c h o r d _ 手f l 其他系统。从实验结果可以看出t a c h o r d 系统在路由性能有着极大的提高。 3 对等对称搜索技术 p 2 p 搜索在信息检索时付出大量劳动并使用了庞大的信息资源。而发布信息和检索信息 是一种对称的信息沟通需求,因此可以削一种对称搜索技术使对称信息匹配的准确度得到很 大提高。 4 基于市场的p 2 p 系统资源管理模型 由于p 2 p 环境下的资源不仅是地理上广域分布的,而且是动态,各个用户共享资源的热 情不一样上线时间也不同。经济模式极可能成为有效的资源管理方法,因为它激励资源所 有者更好的动机来贡献其资源,平衡资源的需求和供给,并且非常适合松散的资源管理。 5 p 2 p 技术在电子邮件系统中的应用 本文提出了g m a i l 系统,它不仅提供了类似网络磁盘的功能,实现用户数据转发米方便 用户间的数据交换,而且能够有效抑止垃圾邮件的传播。 关键词:对等网络,网格,超级节点,搜索引擎,拍卖,电子邮件 ! 堕壁兰塾查叁兰堡! 兰些堕苎 a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fc o m p u t i n ga n dn e t w o r k i n g c o m p u t e r sa r ew i d e l yu s e d h o w t ou s et h e s ec o m p u t e rr e s o u r c e sb e c o m e sah o t s p o t t h e r ea r et w ot e c h n i q u e si nu s i n gt h e s e d i s t r i b u t e dc o m p u t e r s :p e e r - t o - p e e r ( p 2 p ) a n dg r i d p 2 pi sp o p u l a ri ns h a r i n gf i l e s ,w h i c hm a k e s p e o p l er e a l i z et h a ti ti sa ne f f i c i e n tm o d et os h a r ei n f o r m a t i o na n dr e s o u r c e a tt h es a m et i m e , r e s e a r c ho ng r i dh a sm a d eg r e a tp r o c e s s t h ep 2 pn e t w o r k sc a l lb ec l a s s i f i e da ss t r u c t u r e dp 2 pn e t w o r k sa n du n s t r u c t u r e dp 2 p n e t w o r k s c o m p a r e dw i t hu n s t r u c t u r e dp 2 pn e t w o r k s s t r u c t u r e d p 2 pn e t w o r k sh a v et h e a d v a n t a g e so fe f f i c i e n c y n c o r eo fs t r u c t u r e dp 2 pn e t w o r k si st h ep 2 pm u t i n ga l g o r i t h mt h e e f f i c i e n c y ,s c a l a b i l i t y ,a n dt h er e s i l i e n c et of a i l u r eo f t h ep 2 pa l g o r i t h ma r eo f g r e a ts i g n i f i c a n c et o p 2 pa p p l i c a t i o n s h o wc a nw ei m p r o v er o u t i n gp e r f o r m a n c eo fs t r u c t u r e dp 2 pn e t w o r k s ? h o w c a nw eu s et h eu n s t r u c t u r e dp 2 pn e t w o r k si n t os e a r c he n g i n e ? h o wc a r lw ei m p l e m e n tr e s o u r c e m a n a g e m e n ti np 2 pn e t w o r k ? h o w c a r lw ei n t e g r a t et w od i f f e r e n tt e c h n i q u e s :p 2 pa n dg r i d ? h o w c a nw eu s ep 2 pi n t oe m a i ls y s t e m s ? a n ds oo n t h e s ep r o b l e m sa l et i c k l i s h ,a l s oa r eh o t s p o t s n i e a u t h o rt r i e st or e s o l v et h e s ep r o b l e m s a n dm a k ec o n t r i b u t i o n st h ef o l l o w i n g 1 i n t e g r a t i n gt w od i f f e r e n tt e c h n i q u e s p 2 pa n dg r i d h a v em u c hd i f f e r e n c e a sw e l la ss i m i l i t u d e p 2 pa r em o r eu s e di nf i l es h a r i n g b yf a r , w h i l eg r i di nl a r g e - s c a l ec o m p u t i n g w eh a v ed o n er e s e a r c ho nd i s t r i b u t e ds e a r c ha n d r e s o u r c em a n a g e m e n ti np 2 pa n dg r i de n v i r o n m e n t 2 p r o p o s i n ga l ls t r u c t u r e dp 2 ps y s t e m d u et om i n i m u mc o n s i d e r a t i o nt oa na c t u a ln e t w o r kt o p o l o g y , t h ee x i s t i n gp e e r - t o p e e r ( p 2 p ) o v e r l a yn e t w o r k sl i k ec a n ,c h o r d ,p a s t r ya n dt a p e s t r y w i l ll e a dt oh i g hl a t e n c ya n dl o w e f f i c i e n c y i nt a c h o r d ,w ep r e s e n tas t u d yo ft o p o l o g y - a w a r er o u t i n ga p p r o a c h e si np 2 po v e r l a y s , a n dp r e s e n ta ni m p r o v e dd e s i g ni nc h o r d w ee v a l u a t et a c h o r da n do t h e ra l g o r i t l u n sb yp h y s i c a l h o p s ,i n t e r d o m a i n - a d j u s t e dl a t e n c y , a n da g g r e g a t eb a n d w i d t hu s e dp e rm e s s a g e f r o m e x p e r i m e n t a lr e s u l t st a c h o r ds h o w st h ed r a s t i ci m p r o v e m e n ti nr o u t i n gp e r f o r m a n c e 3 p e e r & s y m m e t r i cs e a r c ht e c h n i q u e t h ea u t h o ra r g u e st h a tp e o p l ec a ns e a r c hw i t ho n es y m m e t r yt e c h n o l o g yt om a k e s y m m e t r i c a ld e g r e eo fa c c u r a c yt h a tm a t c hm e s s a g ei m p r o v eg r e a t l y s o ,t h ea u t h o r so ft h i sp a p e r c o m b i n ea d v a n t a g e so fp 2 ps e a r c ht e c h n o l o g ya n ds y m m e t r i c a ls e a r c h i n g ,p u tf o r w a r dt h eg r i d p e e r s y n m a e t r i cs e a r c ht e c h n i q u e 4 p 2 pr e s o u r c em a n a g e m e n tb a s e do nm a r k e t d u et or e s o u r c ei np 2 ps y s t e m sa r el a r g e - s c a l yd i s t r i b u t e d ,d y n a m i c ,u s e r sh a v ed i f f e r e n t a t t i t u d e st o s h a r i n gt h e i rt h i n g s e c o n o m i cm o d ei sb e c o m i n gag o o dr e s o u r c em a n a g e m e n t , b e c a u s ei tn l a k e su s e r ss h a r et h e i rf i l e so rc o m p u t i n gw i t ha i m s 5 p 2 pt e c h n i q u ei ne m a i ls y s t e m s t h eg m a i ls y s t e mi sas i m p l eg i r dm a i ls y s t e mw h i c hi sb a s e do nt h eg 1 0 b u st o o l k i t s i tn o t o n l ya c t s t h ew e bd r i v e r s b u ta l s om a k e si tp o s s i b l et h a tu s e r se a r le x c h a n g et h e i rd a t a k e y w o r d s :p e e r - t o - p e e r , g r i d ,s u p e rp e e ls e a r c he n g i n e ,a u c t i o n ,e - m a i l 第一章绪论 1 1 论文研究背景 第一章绪论 正如摩尔定律所指,“每十八个月处理器性能提高一倍,而价格降低一半”,计算机的低 廉价格让其使用越来越广泛。如何有效利用这些计算机资源也随之成为人们研究的热点。而 且,随着高性能计算应用需求的迅猛发展,人们需要超强计算能力来解决一些超犬规模应用 向题。计算模式随着计算机性能及其网络速度的快速增长经历了三个阶段:主从模式、客户 机月务器模式和s e r v e n t 模式。 在s e r v e n t 模式中,每台机子既可以作服务器,也可以作客户机。每台机子通过相互协 作,从而达到拥有超强计算能力的网络计算环境。当前研究的热点有两种技术:对等网络 ( p e e r - t o - p e e r ,p 2 p ) 和网格计算( g r i d c o m p u t i n g ) 。p 2 p 技术引起人们热切关注起源于 n a p s t e r ,g n u t e l l a 等等p 2 p 产品的应用。这些杀手级应用( k i l l e ra p p l i c a t i o n s ) 满足入们快速 交换大容量数据的需求。而网格的出现是由于人们需要解决一些超大规模应用问题。这些超 大规模应用所需计算能力已不可能在单一的高性能计算机或单一的计算机机群上获得这就 需要将地理分布、系统异构、性能各异的各种高性能计算机、计算机机群、大型服务器、贵 重科研设备、大型通信设备、可视化系统等,通过高速互连网络连接并集成起来,形成对用 户相对透明的、虚拟的、高性能计算环境,即网格计算系统,以此来共同解决大型应用的计 算问题 1 】。“t 本文试图解决如下问题: 庸h 啦押:! 歹1 一 1 如何将p 2 p 和网格两种技术融合起来? o , 当前两者的应用决然分开的。就目前广受欢迎的应用来看,2 倒重王室娃茹储 一而网 格侧重于大规模计算。当然,网格和p 2 p 技术又有很多相似之处。将两者有效结合将对计 算模式的研究有着极大的意义。 2 如何提高当前结构化p 2 p 网络的路由性能呢? s y l v i ar a t n a s a r n y 等人在总结现有的结构化p 2 p 路由算法的基础之上 2 提出了结构化 对等网络面临的“十五个问题”- 其中指出p 2 p 路由算法和安全问题是p 2 p 研疫鞠霉禧。p 2 p 蛐3 堂黑p 椰2 p 裟淼赢塬 种p 静 如何将技术应用到搜索引擎上呢? 。i 、j 盎: 1 p 2 p 将使用户能够深度搜索文档,而且这种搜索无需通过w e b 服务器,也可以不受信 息文档格式和宿主设备的限制,可达到传统目录式搜索引擎无可比拟的深度。这将对搜索技 术的发展产生深远的影响。 4 如何将拍卖市场引入到p 2 p 的资源管理呢? 由于网络中个体如同社会个体也是自私的,我们能否将拍卖市场引入到p 2 p 的资源管 理呢? 借用市场、拍卖等模型描述p 2 p 系统的内部机制和行为,刻画系统与p e e r 、p e e r 与 p e e r 之间的关系,建立新的基于市场的p 2 p 系统资源管理模型。 5 如何将p 2 p 技术应用到电子m 口件系统呢? 己眦: 本文提出一种基于p 2 p 技术的邮件系统,即g 唧c i r 系统。这个系统不但提供了类似网 络磁盘的功能,实现用户数据转发来方便用户间的数据交换,而且能够有效抑止垃圾邮件的 传播。 、这五类问题是当前热点俺短,| 也是急待解决的问题。本文试图解决这些问题,通过一系 鼍私蝶和如孙 、五渺、铀水 y j 中国科学技术人学颂l :学位论文对等时略搜索机制及资源管理的研究 列的仿真实验,并取得良好的效果。 1 2 文章组织 本文的组织结构如r 所示: 第一章绪论 首先介绍我们从事的研究工作的背景和意义,然后介绍本文的主要工作和组织结构。 第二章对等网络研究现状及与网格融合 首先介绍对等网络的含义,以及对等网络的组成、特征、关键技术、分类和应j f _ f ;然 后介绍对等网络的典型应用,分析p 2 p 的研究现状:最后介绍网格的含义与p 2 p 的区别 和联系,及p 2 p 与网格技术的融合。 !第三章结构化对等弼络系统- - t a c h o r d 提出与实际网络结构相关的路由方法,以及一种基于c h o r d 的系统,即t a c h o r d 。然后 进行实验仿真,用物理跳数、延迟和每个消息占用的带宽来衡量t a c h o r d 和其它系统。 第四章非结构化对等网络搜索引擎 首先介绍传统的搜索引擎技术并指出其不足:然后提出一种更为有效地网格搜索引擎 技术一对等对称搜索技术,即在网格资源管理系统基础上实现p 2 p 的搜索引擎,克服原有 技术带来的弊端。 第五章基于市场的对等网络资源管理 首先了解一下p 2 p 系统b i r t o r r e n t 和e d o n k e y 的资源共享机制;然后提出了基于市场的 对等网络资源管理方法;最后做了仿真,比较了集中市场和双向拍卖模型的性能。 第六章对等网络技术应用一g m a i l 系统 本文提出一种基于p 2 p 技术的邮件系统,即g u m i l 系统。首先介绍g m a i l 系统设计的 目标,设计思想和系统结构;最后是g m a i l 系统的初步实现。 第七章结束语 总结目前成果介绍要继续开展的工作;最后是p 2 p 的发展趋势及可能突破的技术。 总的文章结构如图1 - 1 所示。 图1 - 1 本文组织结构图 2 第二章对等铡络研究现状及与阍格融台 第二章对等网络研究现状及与网格融合 p 2 p 是p e e r - t o - p e e r 的简称,也称为对等网络。 p 2 p 技术引起人们热切关注起源于n a p s t e r ,g n u t e l l a k a z a a b i r o r r e n t 等p 2 p 产品的 应用。随着社会和网络的发展,人们对数据存储和传输、高性能计算等有着迫切的需求;而 这些杀手级应用( k i l l e ra p p l i c a t i o n s ) 满足人们快速交换犬容鼙数据的需求。p 2 p 技术避免了 c s 结构带来的单点失效、性能瓶颈和网络拥塞等问题。p 2 p 技术不依赖或尽可能不依赖中 央服务器,使得每个p e e r 既能作为服务器,也可成为客户机。p 2 p 技术的核心思想就是将 网络应用的核心从中央服务器向网络边缘的终端设备扩散;这些终端设备可以是高性能计算 村b 可以是p c 机,可以是手机,也可以是p d a 等等。 2 1 对等网络的特征及分类 随着计算机处理能力的进一步增强,当前市场上任一台新生产的计算机都可作为服务 器。p 2 p 的每个p e e r 既是客户机。又是服务器,还是路由器。p 2 p 的各个p e e r 因互为服务而 共存而不是依赖于特定的集中式机制;而且,各个节点可以直接交互并可能随时离开对等 网络。对等网络的以下特征使之与传统系统相区别: 夺 每个节点既是客户机,又是服务器; 夺 节点之间通过直接建立连接,交互共享资源; 夺 资源分布在各个节点中,而不是集中在一个服务器中进行管理; 夺 节点具有动态性与即席性: 有着极强的扩展性: 夺 纯p 2 p 系统没有任何集中控制机制,系统的各个节点运行的p 2 p 系统软件功能相 同。 p 2 p 根据其不同特性可以有不同的分类方法。本文介绍的是按照其网络拓扑结构和应用 范围两种分类方法。 对等网络按结构的不同可分为结构化对等网络和非结构化对等网络。网络拓扑结构是固 定的,有规律的系统为结构化对等网络。c h o r d 3 、t a p e s t r y 4 、p a s t r y 5 和c a n 6 都属于 结构化对等网络。这类网络提供了文件i d 和文竹存贮位置之间的映射关系,从而保证有效 路由,并保证最终找到目标节点。而在非结构化对等网络中( 如g n u t e l l a 7 1 ,b i t t o r r e n t ) 中, 对等节点连接任意其它对等节点构成对等网络,数据放置与对等网络拓扑无关,网络拓扑是 a d h o c 的。与非结构化对等网络比较,结构化对等网络具有查找效率高和查找确定性等优 点。路由算法是缶与构化对等网络的核心,它的路由效率、可扩展性和容错性对对等网络有 着很重要的意义。h a s h 算法在结构化对等网络和非结构化对等网络系统中都有应用,分别 是文件d 和文件存贮位置之闻的映射关系,以及生成文摘文件( 以保证文件的完整性和下 载安全性) 。m d 5 - h a s h 文件的数字文摘通过h a s h 函数计算得到。不管文件长度如何,它 的h a s h 函数计算结果是一个固定长度的数字。与加密算法不同,h a s h 算法是一个不可逆的 单向函数。采用安全性高的h a s h 算法,如m d 5 、s h a 时,两个不同的文件几乎不可能得到 相同的h a s h 结果。因此一旦文件被修改就可检测出来。在2 2 和2 3 节分别介绍结构化 p 2 p 和非结构化p 2 p 系统的例子。 p 2 p 系统按照应用范围来分类。可以分为:实时消息传递、管理和共享信息、协作和分 3 中国科学技术大学硕士学位论文对等同络搜索机制及资源管理的研究 布式服务。 实时消息传递( i n s t a n tm e s 强g i n g ,i m ) 使得在线用户可以直接的以实时方式进行一对一 的或成组的消息交流。通过使用i m 服务,用户安装系统客户端软件并且登录中心服务器以 后,服务器会将该用户设置为在线状态。这样,该用户才能和其他用户建立直接的连接。i m 产品有腾讯q q 、i c q 1 4 1 a i m 等。由i m 衍生出来有交互式网络游戏,即通过网络仃点进行的交 互式在线游戏。p 2 p 网络游戏有着j 1 + 阔的市场前景,国内人气极旺的有联众、盛大网络等等。 管理和共享信息包含了文件共享、资源共享和分布式搜索引擎。文件共享,比如g n u t e l l a 和k a z a a ,不需要中心化的管理或控制机制就能实现文件共享。资源共享是一种分布式的计 算形式,即通过动态方式利用节点计算能力来处理一些过去只能有超级计算机才能处理的任 务。而分布式搜索引擎是将创建为资源检索结果的信息索引所需的功能扩展到有对等节点存 在的网络边缘。它采刚了分而治之的策略来定位信息并执行信息的实时搜索功能。 p 2 p 分布式服务义分为分布式计算和分布式网络服务。分布式计算例子有s e t i f a o m e 项目【8 】,即利用节点空闲c p u 时间片断来计算寻找外星人程序。分布式网络服务特点在于 将网络流量局部化,这样不仅降低了网络开销还缩短了程序响应时间。c y t a q 公司开发的 d i s t r i b u t e dr e s o u r c en e t w o r k 9 就是一个p 2 p 分布式网络服务的例子。它是一个由连接和集 成了一个企业中的多种不同信息源的资源路由器组成的网络,这些资源包含多种应用程序和 数据库的信息。多个信息源可以连接到一个资源路由器上,或者一个信息源连接到多个资源 路由器上。 2 2 结构化对等网络 对等网络的核心是对等网络路由算法,对等网络算法的可扩展性和容错性真接影响到对 等网络系统的性能,因此对等网络路由算法的研究具有重要的意义。结构化对等网络路由算 法由于查找可确定性、简单性和分布性等优点,正成为研究和应用的焦点。本章介绍了几种 有影响的结构化对等网络路由算法。 2 1 1t a p e s t r y 算法 t a p e s t r y 是z h a o 等人1 4 】等提出的一种新型的对等网络定位和路由算法。该算法是目前 广域环境中非集中式定位和路由的最有影响路由算法之一。每个t a p e s t r y 节点只需维护 l o g n 大小的路由表信息,路由最多在l o g n 的路由跳数内完成。 t a p e s t r y 算法针对p r r 算法进行了改进和扩充,该算法具有可扩展、自适应和鲁棒性 等特点,能够在高负载和动态网络、节点差错时有效地进行路由查询和定位资源。尽管 t a p e s t r y 算法与p r r 算法相类似,但是该算法增加一些新的特点:利用状态信息、提供自 管理功能、强壮性、可扩展性、动态自适应性,在出现节点、网络失败和高负载时实现平滑 降低系统性能,不需要任意节点来维护全局信息等。 2 1 2p a s t r y 算法 p a s t r y 5 是m i c r o s o f t 和r i c e 大学共同发起的对等网络匿名存储系统中的定位和路由 算法- 该算法与t a p e s t r y 有许多相似之处:使用匹配前缀或者后缀地址的路由方法、插入 和删除算法有类似的代价。p a s t r y 与t a p e s t r y 的区别在于:第一p a s t r y 中对象复制无需 4 第二章对等蚓络研究现状及与阿崭融合 由所有者来控制在对象的出版发布过程中,复制对象被放到与对象编号最接近的多个节 点上。第二,t a p e s t r y 在服务器和根节点之间的路由过程中放置对象指针信息:而在p a s t r y 中客户端通过对象编号直接黯由到保存对象复制点附近,这样在实际网络中多个复制对象存 在丁- 实际物理网络的不同节点上。在多个节点存储复制对象带来了存储开销、安全性、保密 性和一致性等问题。第三,与t a p e s t r y 的代理路由算法( s u r r o g a t er o u t i n g ) 相比,p a s t r y 的路 由跳数具有较弱的理论分析性;p a s t r y 的路由距离时具有可证明的理论分析性和概率界限 并保证能够找到已存在的可到达对象。最后,p a s t r y 路由算法不能充分利用本地性提高路由 效率。 2 1 3c a n 算法 ;c a n e 6 j 是a t & t 的a c i r i 部门开展的研究项目。c a n 模型将节点映射到d 维坐标空 间,并根据服务器的密度和负载情况将该坐标空间分成d 维坐标空间区域,其中每个区域 保留邻居信息。查找请求通过邻居节点路由到目标节点。 c a n 与t a p e s t r y 有多处差异,首先,t a p e s t r y 的树形对等网络结构从对等网络的任意 一个位置出发都能迅速收敛到目标节点,使用节点内部的位置信息使t a p e s t r y 的路由更有 效率,而c a n 假定对象不可改变,在对象改变后必须重新插入到c a n 中:最后,t a p e s 姆 网络的构造考虑了网络时延,c a n 在构造网络时并没有完全考虑物理网络拓扑,从而导致 路由效率过低。 2 1 4c h o r d 算法 c h o r d 算法【3 】是m i t 提出的一种分布式查找算法。该算法中每个节点和文件都映射到 1 6 0 位的标识,该标识通过对文件名或节点i p 哈希得到,节点和文件i d 在一维空间上构成 一个环,文件关键字存贮在文件i d 的后继节点上。为减少定位开销,c h o r d 在每个节点建 立一个f i n g e r 表( 路由表) ,用于指向环中距该节点分别2 丰口,2 井,2 m 的节点。因此 c h o r d 可以保证在o ( 1 0 9 n ) 的复杂上界内确定一陛地定位对象( 索引) ,其中为对等网络系 统的节点数。c h o r d 的邻屠表为l o g 项,即拓扑维护开销为0 0 0 9 _ ) 。 与现有的工作相比,c h o r d 算法具有简单性、可验证性和可扩展性等优点。c h o r d 算法 的路由跳数和网络直径优于c a n 算法,节点加入过程和维护开销优于t a p e s t r y 算法和 p a s l l y 算法。在本文第三章,将提出基于c h o r d 算法的新的一种结构化p 2 p 结构。 2 3 非结构化对等网络 本章介绍时f 非常流行的非结构化p 2 p 的应用;b i t t o r r e n t 和e d o n k e y 。g n u t e l l a 也是 非结构化p 2 p 系统,它吸取了n a p s t e r 的失败教训将p 2 p 的理念推进一步:它不存在中 枢目录服务器,用户只要安装了该软件,立即变成一台能够提供完整目录和文件服务的服务 器,并会自动搜寻其它同类服务器,从而联成一台由无数p c 组成的网络超级服务器。 2 3 1e d o n k e y e d o n k e y 1 0 1 是由j e dm c c a l e b 在2 0 0 0 年创立起来的。最重要的是可以同时从许多人 中国科学技术人学颂i 。学位论文对等别络搜索茸l 捌驶资源管理的研究 那里f 载同一个文制:,它采用了“多源文件传输协议”( m f t p ,t h em u l t i s o u r c ef i l et r a n s f e r p r o t o c 0 1 ) 。电驴的索引服务器并不集中在一起的,而是各人私有的,遍布全世界每一个人 都可以运行电驴服务器同时共享的文件索引为被称为“e d 2 k - q u i c k l i n k 的连接,文件前缀为 “e d 2 k :”。同时,在协议中,定义了一系列传输、压缩和打包的标准甚至还定义了一套 积分的标准,你上传的数据量越大,积分越高下载的速度也越快。而且每个文件都有有 m d 5 一h a s h 的超级链接标示这使得该文件独一无二,并且在整个网络上都可以追踪得到。 e d o n k e y 可以通过检索分段从多个用户那里下载文件,最终将下载的文件片断拼成整 个文件。而且只要你得到了一个文件片断,系统就会把这个片断共享给大家,尽管通过选 项的设置你可以对上传速度做一些控制,但你无法关闭它。 当然,e d o n k e y 也存在一些不足之处。比如其分段下载的机制存在一定负面影响,一 个大型文件分割成许多单元米下载,如果f 载的过程中有个单元破损,整个文件就不能够 使_ i j 了。而且更糟糕的是由这种下裁机制,在启动下载任务时e d o n k e y 需要搜索该文件 所商可以使用部分的来源,然后分析每一个来源是拥有整个文件还是文件的一部分,再根据 具体的情况来安排f 载任务,通常从启动下载任务到开始传输第一个字节,需要等待好几分 钟的时间。如果用户中途关闭程序,在下次启动继续下载时,除了得重新搜索和分析文件来 源,还需要分析e d o n k e y 用于存储已下载单元的缓存文件,这通常需要花费更多的时间。 总之g n u t e l l a 和e d o n k e y 以及e m u l e 代表了第二代p 2 p 无中心、纯分布式系统的特 点,它不再是简单的点到点通信,而是更高效、更复杂的网络通信:再加上e d o n k e y 和e m u l e 引入的强制共享机制,在一定程度上避免了第一代p 2 p ( n a p s t e r ) 纯个人服务器管理带来的 随意性和低效率。 2 3 2b i t t o r r e n t b i t t o r r e n t ( 简称b t ) 1 1 z ;i 起人们的关注是在人们下载r e d h a t9 ,0 的时候。通过b t , 在短短的几个小时内,全部3 张光盘镜像的5 0 0 份拷贝被下载,数据总量达到了1 5 t b , 相当于2 0 0 0 多部高质量电影,最高速度达到了仃0 m b ,秒。如此快捷、高效、自发而又有 序的数据传播方式,在b t 出现以前几乎是不可思议的事情。 b t 批判地继承了前辈产品的优点,将中心目录服务器的稳定性同优化的分布式文件管 理结合起来,从而在效率上远远超出了电驴这类产品。它要求提供一个或多个统一的w e b 发布服务器,供网友此发布和搜寻资料。在客户端,它通过一个i e 插件提供下载、上传管 理。b t 把一份大文件切割成碎片给每一个碎片标上特殊标识,用户无需到一个固定地点( 例 如传统网络的中心服务器) 上下载完整的文件,系统会帮助你自动寻找、随机下载具有相同 标识的文件碎片,将其加以整合成为完整的文件。 b t 不需要指定服务器,虽然在b t 里面还是有服务器的概念,但使用b t 的人并不需 要关心服务器在哪里,b t 的服务器称为t r a c k e r 。用b t 下载,需要得到一个扩展名是t o r r e n t 的文件,这个文件很小,可以放在某个w e b 服务器上,或者用f t p 和传统的p 2 p 米得到, 甚至作为附件贴在论坛上。这个文件里面存放了对应的发布文件的描述信息、该使用哪个 t r a c k e r 、文件的校验信息等。b t 用文件关联来对其进行处理。 使用b t 不用担心会抓到死档,b t 把提供文件的人称为种子( s e e d ) ,正在下载的人称 为客户( c l i e n t ) 某一个文件现在有多少种子多少客户是可以看到的,只要有一个种子,就 可以放心的下载,一定能抓完。当然种子越多、客户越多的文件抓起来的速度会越快。如 果传输中间断掉了,也没有关系再次打开t o r r e n t 文件,b t 会自动的续传。 为了方便使用b t 技术,有人还专门开发了b t 的辅助工具,比如p t c 就是一个非常 完整的工具。它不仅可以查询下载信息还可以做下载前的侦察,获得更多准备信息以决定 6 第二章对等网络研究现状及与网格融合 是否f 载。同时它还可以让你随时制作并发布一个t o r r e n t 。p t c 甚至可以使用一个脚本来 读取r s s 的内容并搜索获得更多扩展的共享资源。 我们也搭建8 t 的平台服务器地址为h t t p :l l e b u f f a l o , 3 3 2 z o r q 。癫牛,欢迎大家访问。 2 4 对等网络的应用 本文列出现有的p 2 p 技术和产品。 提供文件交换服务如n a p s t e r 、g n u t e l l a 、b i t t o r r e n t 、e d o n k e y 、e m u l e 。 挖掘p 2 p 分布计算能力的公司和组织如p o p u l a rp o w e r 、s e t l h o m e 、d i s t r i b u t e d n e t , 他们希望使用p 2 p 技术集中那些联接在网络上的电脑的空闲的c p u 时间片断、内存空间、硬 盘空间来替代“超级计算机”。i b m 、微软、h r i b a 也在合作开展一个名为u d d i 的项目以将 b 邵电子商务标准化。e a z e l 止在建立下一代的l i n u x 桌面。 j a b b e r 已经开发了一种基于x m l 、开放的即时信息标准,j a b b e r 被认为是建立了未来 使用p 2 p 数据交换的标准。 l o t u sn o t e s 的开发者创建的g r o o v e 试图“帮助人们以全新的方式沟通”。 英特尔也在推广它的p 2 p 技术以帮助更有效地使用芯片的计算能力。 2 5 对等网络与网格融合 随着p 2 p 技术的发展,p 2 p 系统和网格( g r i d ) 界限越来越模糊。本文第四章、第五章 和第六章的工作都是在基于p 2 p 和网格的混合环境进行的。 2 5 1 网格 网格定义到目前为止仍没有一个明确统一的表述。对网格和网格计算理论做出巨大贡 献的i a n f o s t e r 等人认为网格是“在缺乏中央控制、全局信息和严格信任关系的情况下能够 协同使用地理分布的资源( e u a b | i t x g 山ec o o r d i n a t e dl l s eo fg e o g r a p b t c a t t y d i s t r i b u t e d r e s o u r c e s - i n t h ea b s e n c e o f c e n t m tc o n t r o l ,o m n i s c i e n c e ,s t r o n g t r u s tr e l a t i o n s h i p s ) ”【1 2 - 1 3 。 一般认为:将地理分布、系统异构、性能各异的高性能计算机、计算机机群、大型服 务器、贵重科研设备、大型通信设备、可视化设备等,通过高速互连网络连接并集成起来, 形成一个广域范围的无缝集成和协同计算环境,这个计算环境称为网格计算系统( g r i d c o m p u t i n gs y s t e m ) 一般称为网格。 网格计算系统是一个集成的计算资源环境,或者说是一个计算资源池【4 9 】,它能够集成 各种计算资源,将这些计算资源转化为可靠的、标准的、抽象的计算能力。网格计算系统给 最终使用者提供的是与地理位置无关、与具体的计算设施无关的通用的计算能力。组成网格 计算系统的计算资源不仅包括高性能计算机、计算机机群、大型服务器,而且包括贵重科研 设备( 电子显微镜、雷达阵列、粒子加速器、天文望远镜等) 、大型通信设备、可视化设备, 以及连接这些资源的高速互连网络。 一般而言网格计算系统具有以下几个方面的特征 1 4 】 ( 1 ) 扩展性:网格计算系统初期的规模较小,随着各种高性能计算机、计算机机群、 大型服务器、贵重科研设各、大型通信设备、可视化设备的不断加入,整个系统的规模随之 迅速扩大。 7 中国科学技术大学硕i :学位论立 对等1 5 9 络搜索机制及资源管理的研究 ( 2 ) 系统多层次的异构性;构成网格计算系统的计算资源有不同的类型。即使是高性 能计算机也有多种类型不同类型的高性能计算机在体系结构、操作系统、应用软件等多个 层次上具有不同的结构。 ( 3 ) 结构的不可预测性:网格计算系统由于其地域的分布性和系统的复杂性整体结 构经常发生变化,随着时间的推移会不断地有新的资源加入弼格计算系统,与此同时原有的 资源也会由于出现故障导致不可用。 ( 4 ) 动态和不可预测的系统行为:在传统的高性能计算系统中,计算资源是独占的, 因此系统的行为是可以预测的,在网格计算系统中,由于资源的共享造成系统行为和系统性 能经常发生变化。 ( 5 ) 多级管理域:构成网格计算系统的资源通常属丁不同的机构或组织并且使用不同 的安全机制,资源的拥有者对该资源具有最高级别的管理权限,这些资源同时也接受网格计 算系统的统一管理,多个机构业组织共同参与解决多级管理域的问题。 。 基于网格计算系统的应用可以分为以。f j l 类 1 5 : ( 1 ) 桌面超级计算:这些应用与远程超级计算机和数据库相耦合,并且具有高端图形 处理能力,使用户在获得超级计算能力的同时,与计算资源保持远程距离。 ( 2 ) 远程仪器和设各:这些应用将用户和远程超级计算机上的电子显微镜、雷达阵列、 粒子加速器、天文望远镜以及卫星接收装置相连以获得准实时的数据处理。 ( 3 ) 协同工作环境( t e l e i m m e r s i v e a p p l i c a t i o n s ) :这些应用将不同地点的多个组织连 接在一起形成一个虚拟环境,不同地点的用户在这个虚拟环境中协同工作。有的文献将其翻 译为远程沉浸。 ( 4 ) 分布式超级计算:这些应用将多个高性能计算中心连接在一起,解决一些在单一 的高性能计算机上难以处理的问题。 网格研究项目可简单地分成有代表性的两类。 第一类网格研究项目以g l o b u s 项目为代表。这类项目提供基础的软件,集成分散的异 构资源,形成单一的计算环境。g l o b u s 项目的核心是g l o b u s 软件,它是构筑网格计算系统 的中间件,提供认证授权、资源管理、任务调度、信息查询、用户管理、文件传输等基本的 网格计算功能。g l o b u s 软件是模块化的,允许用户按自己的需要进行定制。目前的g l o b u s 软件可以认为是网格计算技术的典型代表和事实上的规范。 第二类网格研究项目是基于j a v a 的网格项目。这类项目利用j a v a 解决平台性、安全性、 易用性等问题。j a v a 语言和相关技术成功地解决了困扰网格计算的几个关键问题,如异构性

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论