（计算机科学与技术专业论文）层次式p2p系统中的数据定位与数据复制.pdf

国防科学技术大学研究生院学位论文 摘要 p 2 p 数据定位技术是p 2 p 系统中的基础性关键技术在p 2 p 系统中数据定位 的路由路径是由一系列应用层跳点而不是口层跳点组成，但是已有的p 2 p 系统中 很少考虑逻辑覆盏网与底层网络拓拎匹配的问题，这种不匹配严重影响了p 2 p 系 统数据定位的效率，利用节点的位置信息可以大幅度提高p 2 p 系统数据定位的效 率根据拓扑结构，p 2 p 系统可以分为集中式拓扑、全分布式拓扑和层次式拓扑， 其中全分布式拓扑包括非结构化拓扑和结构化拓扑。集中式p 2 p 系统数据定位效 率很高，但存在系统瓶颈等问题。非结构化f 2 p 系统具有一定的灵活性，但是可 扩展性较差；结构化p 2 p 系统具有较好的可扩展性，但是它的基于d h t 的扁平式 结构引起了节点负载和节点能力不匹配的问题层次式结构可以综合集中式和分 布式拓扑结构的优点，当前采用层次式拓扑结构来提高p 2 p 系统的性能成为研究 的热点。由于节点的不可靠性，p 2 p 系统中主要采用数据复制技术来提高数据的可 用性，传统的全复制算法和分块复制算法空间利用率低，采用基于编码的数据复 制算法可以大幅度提高空间利用率。本文对层次式p 2 p 系统中的位置感知的数据 定位和基于编码的数据复制进行了深入研究 针对逻辑覆盖网与底层物理网不匹配的问题，提出了一个基于底层网络位置 信息建立p 2 p 覆盖网的算法l a n c t ，覆盖网中每个节点都选择和自己物理距离相近 的节点作为自己的邻居，逻辑上相邻的节点也是物理上相近的节点。由于路由路 径中的每跳的延迟都较低，这就使得数据定位具有较低的延迟。该算法不需要网 络中固定的节点充当地标节点，具有很好的分布性和可扩展性。模拟实验结果表 明：利用l a n c t 来构建位置感知的结构化p 2 p 系统和非结构化p 2 p 系统，这些系 统中的数据定位延迟能够得到大幅度的降低 为了利用层次式拓扑结构来提高p 2 p 系统性能，提出了一个动态自适应层次 式p 2 p 系统拓扑结构d a h p 2 p 的构建算法c h p p 与路由算法h r o u t c ，系统中物理 位置相近的节点被组织成群，群中选出能力最强的节点充当超级节点，超级节点 为群中的普通节点提供服务，各层群的超级节点组成上一层覆盖网，系统的层次 数根据节点数目而动态调整，采用层次式的消息路由算法来减少数据定位路由跳 数模拟实验表明：h r o u t c 能够在o ( i ) ( 1 表示系统的层次数) 路由跳数内定位到 数据，不同层超级节点的负载相对平衡。 为了提高层次式p 2 p 系统中数据的可用性，提出了层次式p 2 p 系统中基于 l d p c 编码的数据复制算法d y r e ，数据通过l d p c 编码算法编码成含有冗余信息 数据块，采用动态放置算法把数据块放置到不同的群中，数据块的位置信息根据 数据的关键字和数据块索引直接计算得到；失效节点的数据可以从前驱和后继节 第i 页 国防科学技术大学研究生院学位论文 点中恢复，当数据的有效编码块数目过少并将导致数据不能被还原时，重建该数 据模拟实验表明；在相同的环境下，d y r e 可获得比传统复制算法更高的数据可 用性，该算法可获得比o c e a n s t o r e 中数据复制算法更小的时间开销 主题词：对等计算，覆盖网，位置感知。数据定位。数据复制，数据可用性 第j i 页 国防科学技术大学研究生院学位论文 d a t ai o c a t i o ni sa l li m p o r t a n tb a s i cs e l 啊c ei nl a r g e - s c a l ep e e r - t o - p e e rs y s t e m s a p a t ho f d a t al o c a t i o no nt h ef 2 po v e r l a yn e t w o r kc o n s i s t so f as e r i e so f a p p l i c a t i o n - l e v e l h o p s ，n o ti p - i c v e lh o p s h o w e v e r , i nm o s tp 2 ps y s t e m s ，l i t t l ee f f o r ti sm a d et oe i l s u r e t h a tt h i sa p p l i c a t i o n - l e v e lc o n n e c t i v i t yi sc o n g r u e n tw i t ht h eu n d e r l y i n gi p - i c v e l n e t w o r kt o p o l o g y t h i si nt u r nc a l ll e a dt oi n e f f i c i e n tr o u t i n g b yu s i n gt h el o c a t i o n i n f o r m a t i o no f n o d e s ，t h el a t e n c yo f d a t al o c a t i o nc a l lb er e d u c e dg r e a t l y a c c o r d i n gt o t h et o p o l o g y , p e e r - t o - p e e rs y s t e m sc l a nb ed i v i d e di n t ot h r e ec a t e g o r i e s ：c e n t r a l i z e d t o p o l o g y , p u r e l y d e c e n t r a l i z e dt o p o l o g ya n dh i e r a r c h i c a l t o p o l o g y 1 1 1 ep u r e l y d e c e n t r a l i z e dt o p o l o g yi n c l u d e su n s t r u c t u r e dt o p o l o g ya n ds t r u c t u r e dt o p o l o g y t h o u g h t h ed a t al o c a t i o no fc e n u a l i z o di 2 ps y s t e m si se f f i c i e n t , t h e i rc e n t r a l i z e ds c r v e r sm a y b e c , o m ep e r f o r m a n c eb o t t l e n e c k s t h o u g hu n s l r i k 氨l r e dp 2 ps y s t e m sa r ef l e x i b l e 。t h e f l o o d i n gm e c h a n i s mo fd a t ai o c a f i o ni n d u c e st h a tt h e yc a n ts c a l et ol a r g en e t w o r k s y s t e m s t h o u g hs t r u c t u r e dp 2 ps y s t e m sa r es c a l a b l e ，t h e i rf l a td h td e s i g n sr e s u l ti n m i s m a t c ho f p e e r sb e t w e e nt h e i rc a p a b i l i t i e sa n di o a & 1 1 l eh i e r a r c h i c a lp 2 p s y s t e m sc a l l c o m b i n e sa d v a n t a g e so f b o t hc o n l 珂i z c da n dd e c c n 仃a _ l i z c dp 2 ps y s t e m s r e c e n t l yi th a s b e c o m ear c s e a r c hh o tt h a th i e m r c m c a ls t r u c t u r ei si n t r o d u c e dt oi m p r o v et h e p e r f o r m a n c eo fp 2 ps y s t e m s a st h eu n r e h a b i l i t yo fp e e r si np 2 ps y s t e m s , d a t a r e p l i c a t i o na l g o r i t h m sa r eu s e dt oi m p r o v ed a t aa v a i l a b i l i t y t r a d i t i o n a ld a t ar e p l i c a t i o n a l g o r i t h m sh a v eal o wu t i l i z a t i o nr a t i oo fs t o r a g es p a c e d a t ar e p l i c a t i o na l g o r i t h m b a s e do ne r a s u r ec o d i n gc a l li m p r o v et h ei r i l i 枷o nr a t i oo fs t o r a g es p a c eg r e a t l y i n t h i st h e s i s ，l o c a t i o n - a w a r ed a t al o c a t i o na n dd a mr e p l i c a t i o nb a s e do ne r a s u r ec o d i n gi n h i 盯孤c h i c a lp 2 ps y s t e m sa r ed e e p l ym s e a r c b e d t or e s o l v et h ei n c o n g r u i t yb e t w v e e np 2 p o v e r l a yn e t w o r ka n du n d e r l y i n gn e t w o r k , ad i s t r i b u t e dt o p o l o g y - a w a r eo v e r l a yc o n s t n l c t i o na l g o r i t h ml a n c ti sp r o p o s e d , i nw h i c h t h eo v e r l a yn e t w o r kc o n s t r u c t i o ni sb a s e do nt h el o c a t i o ni n f o r m a t i o no fu n d e r l y i n g t o p o l o g y n o d e st h a ta r ec l o s ei nt h el o g i c a ln e t w o r ka r ea l s oc l o s ei nt e r m so f n e t w o r k l a t e n c y 1 h ee x p e c t e dd c t a yi ne a c hh o po f m e s s a g er o u t i n gi sl o w , w h i c hl e a d st ol o w l a t e n c ys t r e t c ho fd a t ai o c a t i o mt h i sa l g o r i t h mi s s c a l a b l ea n dd i s t r i b m e d t h i s a l g o r i t h mc a nb eu s e dt oc o n s t r u c tl o c a t i o n - a w a r es y s t e m st h a t 躺s t r u c t u r e do r u n s t r u c t u r e d s i m u l a t i o nr e s u l t si n d i c a t et h a tt h el a t e n c yo fd a t al o c a t i o ni nt h e s e s y s t e m sc o n s h - u c t o db yl a n e tc a nb er e d u c e dg r e a t l y t oi m p r o v et h ep e r f o r m a n c eo f p 2 ps y s t e m sb ye x p l o i t i n gh i e r a r c h i c a lt o p o l o g y ，a c o n s t r u c t i o na l g o r i t h mc h p po fh i e r a r c h y - a d a p t i v ep 2 pt o p o l o g yd a h p 2 pa n da h i c ：r a ：r c h i c m r o u t i n ga l g o r i t h mi - i r o u t e a r ep r o p o s e d p e e r sa r eg r o u p e di n t oc l u s t e r s a c c o r d i n gt op r o x i m i t y , a n ds u p e rp e e rt h a ti st h es t r o n g e s tp e e ri ne a c hc l u s t e ri s s e l e c t e dt op r o v i d es e l v e sf o rc l i e n tp e e r s s u p e rp e e r si nt h es a m et i e rf o r mt h eu p - t i e r 第i i i 页 国防科学技术大学研究生院学位论文 o v e r l a yn e t w o r k , a n dt h en u m b e ro fs y s t e mt i e r si sc h a n g e ds e l f - a d a p t i v e l ya c c o r d i n gt o 也en u m b e ro fn o d e si nt h es ) , a e m ah i e r a r c h i c a lr o u t i n ga l g o r i t h mi s d e s i g n e dt o r e d u c et h er o u t i n gh o p sa n dl a t e n c y s i m u l a t i o nr e s u l t ss h o wt h a th r o u t ec a l ll o c a t ed a t a w i t h i n0 0 ) h o p s oi st h en u m b e ro fs y s t e m 矗e r s ) ，a n dl o a d so fs u p o r p c e r si nd i f f c r c m t i e r 勰r e l a t i v e l yb a l a n c e a b l e t oi m p r o v ed a t aa v a i l a b i l i t yi nh i e r a r c h i c a lp 2 ps y s t e m s 。an o v e lr e p l i c a t i o n a l g o r i t h md y r eb a s e do nl d p cc o d i n gi sp r o p o s e & d a t aa r ee n c o d e di n t ob l o c k st h a t c o n t a i nr e d u n d a n ti n f o r m a t i o l aw i t hl d p ce n c o d i n g a l g o r i t h m d y n a m i or e p l i c a p l a c e m e n ti su s e dt 0s t o r eb l o c k s0 1 1d i f f e r e n tc l u s t e r s a n dt h el o c a t i o no f e a c hb l o c ki s d e t e r m i n e db yt h ek e yo f t h a td a t aa n dt h ei n d e xo f t h a tb l o c ld a t ai ni n v a l i dp e e r sc a l l b er e t r i e v e df r o mp r e d e c e s s o fa n ds u c c e s s o rp c e r s w h e nt h en u m b e ro fa v a i l a b l e b l o c k si st o o 锄a u 。w h i c hw i l li n d u c et h a td a t ac a n tb er e c o n s t r u c t e d ，t h ed a t ai s r e s t o r e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mg a i n sh i g h e rd a t aa v a i l a b i l i t yt h a n t r a d i t i o n a lr e p l i c a t i o na l g o r i t h m s ，a n dt h et i m ec o s to f t h i sa l g o r i t h mi sl o w e rt h a nt h a t o f r e p l i c a t i o na l g o r i t h mi no c e a n s t o r e k e yw o r d s ：p e e r - t o p e e rq o m p u t i n g ，o v e r l a yn e t w o r k ，l o c a t i o n a w a r e ，d a t a l o c a t i o n ，d a t ar e p l i c a t i o n ，d a t aa v a i l a b i l i t y 第i v 页 国防科学技术大学研究生院学位论文 表目录 表4 1 本章标识符的含义表 ，4 6 表5 1l d p c ( 3 ，6 ) 编码5 7 表5 2 公式中符号的含义。5 8 第页 国防科学技术大学研究生院学位论文 。 图目录 图1 1p 2 p 模式与c s 模式示意图2 图2 1n a p s t e r 结构 图2 2g n u t e u a 结构 图2 3p a s t r y 中节点的路由表 图2 4c h o r d 方法 1 2 1 3 图2 6c a n 方法 图2 7k a t _ a a 结构示意图 图2 8 ，c o c o 两种拓扑结构。 1 7 1 8 1 9 图2 9 逻辑链路a 2 a 3 和b i b 3 上的不必要流量一。2 2 图2 1 0 拓扑不匹配问题2 2 图3 1i n t e r n e t 的几何空间模型t 。2 9 图3 2 图3 3 确定地标的坐标2 9 普通节点坐标的计算3 0 图3 4 两维空间示意图 图3 5 新节点的加入过程 图3 6l c a n 与c a n 的比较。3 5 图3 7l c a n 的构建。 图3 82 维虚拟空间。 图3 9 位置感知的c m u t e l l a 的构建 图3 1 0 位置感知覆盖两的延迟伸展率分布图 3 5 3 6 3 7 图3 1 1l a n e t 与b i n n i n g 算法延迟伸展率的比较 图3 1 2l c a n 与c a n 中平均数据定位延迟比较图 4 0 图3 1 3l c a n 与c a n 中平均数据定位延迟比值分布图 图3 1 4l c m u t e l l a 与c m u t e u a 数据定位延迟比较图 4 0 4 1 4 l 4 2 4 2 4 5 4 5 图3 1 5l c _ m u t e l l a 与g n u t e l l a 平均数据定位延迟比值分布图 图4 1四层超级节点结构示意图。 图4 2 二维空闻的4 层划分 图4 3 节点的加入 图4 4 基于祖先节点表的层次式路由 图4 5 基于祖先节点的路由路径 图4 6 利用快速通道的路由示意图。 4 7 第页 国防科学技术大学研究生院学位论文 图4 7 基于快速通道的层次式消息路由5 1 图4 8 快速通道表的更新 图4 9d a h p 2 p 与e c a n 平均数据定位路由跳数的比较5 3 图4 1 0d a h p 2 p 与不伺维数的c a n 和c h o r d 平均数据定位跳数比较5 4 图4 1 1d a h p 2 p 与e c a n 的路由延迟伸展率的比较 图4 1 2 快速通道对不同层超级节点负载的影响5 5 图5 1 数据迁移过程 图5 2 数据恢复过程 图5 3 数据重建算法 6 0 图5 4 节点有效性分布。 图5 5 节点有效性相同的数据可用性比较 图5 6 节点有效性不同情况下数据可用性比较 6 1 6 2 6 3 6 4 6 4 图5 7d y r e 与o c e a n s t o r e 复制算法数据可用性比较 图5 。8 复制算法开销比较 6 4 6 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：垦燮聋盎! 叁章塑熟玉童虚丝垒i 盥鱼塑a 学位论文作者签名：拯叠：蜩 日期： 埘6 年1 1 月日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：垦鉴盘翌奎丝宝逊亟垄查塑拯黛壁1 2 学位论文作者签名：i 至：! 蛆日期：w 衫年f f 月阳日 作者指导教师签名：蔓耋造 日期：，一6 年，月】1 日 国防科学技术大学研究生院学位论文 第一章绪论 对等( p e e r - t o - p e e r ，p 2 p ) 计算是近年来兴起的一种重要网络计算技术。与传统 的c s 计算不同，p 2 p 计算中的各节点是地位平等的对等体，通过直接交换来利 尾计算、存储、信息移带宽等资源目前p 2 2 计算在很多镪域都有着大量盼研究 和应用。p 2 p 数据定位技术是p 2 p 计算中的基础性关键技术。目前正在使用或研 究当中的p 2 p 系统都是在物理网络上建立一层逻辑覆盖网，这种结构造成了逻辑 路径与物理路径不一致，且节点的能力相差巨大，造成了节点能力和节点任务的 不匹配，这些向题给p 2 p 数据定位技术带来了很多挑战性问题p 2 p 系统作为大 规模的数据存储介质变得越来越流行，但是系统中节点的可靠性相差巨大，因此 在p 2 p 系统中利用复制技术支持数据的可用性、持久性和完整性成为一个研究热 点解决这些问题，既具有重要韵学术价值，又具有广阔的应用前景。 i ip 2 p 计算概述 自上世纪末以来，p 2 p 计算技术作为一种新的网络计算技术，受到工业界和学 术界的普遍关注，成为计算机领域研究和应用的重要热点。i n t e l 1 i p 和s o n y 等著 名公司联合成立了p 2 p 工作组，s u n 开发了开放源码的p 2 p 计算平台$ x t a l “， m i t 、uc b e r k e l e y 和s t a n f o r d 等众多著名大学以及m i c r o s o f t 研究院、h p 研究院 等著名研究机构都纷纷开展了大量的相关研究。目前f 2 p 计算已在广域分布计算、 文件共享、即时消息、分布式存储、协同工作、应用层组播、数据管理和大规模 联机游戏等多个领域有着广泛的研究与应用基于p 2 p 计算技术的新型分布式系 统( 即p 2 p 系统) 已成为i n t e r n e t 上最流行的应用系统之一。 1 1 1p 2 p 计算的定义 p 2 p 计算技术当前正处于飞速发展中，学术界对p 2 p 计算尚无公认的严格定 义。目前研究者们从不同角度对p 2 p 计算提出了多种定义p 2 p 工作组定义p 2 p 计算为“通过系统问直接交换来共享计算机资源和服务”闭；被引用较多的是c 1 a y s h i r l 哆给出的定义 3 1 ，“p 2 p 计算是指能够利用分布在i n t e m c t 边缘的大量计算、 存储、网络带宽、信息和人力等资源的技术。由于访问这些分数的资源是在不稳 定连接和动态口地址的情况下进行的，p 2 p 节点必须能够独立于d n s 系统之外寻 址并有相当部分乃至全部的自治性”。 这些定义从不同的侧面对p 2 p 计算进行了描述。综合说来，p 2 p 计算是指“采 用分散控翩的方式，利用大量分布的动态自治资源来完成特定功能的一种新型两 第1 页 国防科学技术大学研究生院学位论文 络计算技术”p 2 p 计算利用的资源可以是c p u 、存储、信息和网络带宽等各种 资源；完成的特定功能可以是广域分布计算、数据共享、通信协作以及公共服务 等各种应用或服务；p 2 p 计算中的资源通常具有较强的动态性，可能会随时加入或 退出系统；p 2 p 计算一般采取分散控制方式，其分散控制特性可以体现在系统的组 织结构、交互协议和算法等某一个或多个方面( 例如通常各节点地位平等，可以直 接进行交互或协作等) 随着p 2 p 计算技术的飞速发展和广泛应用，p 2 p 计算模式已成为一种重要的 网络计算模式与传统的c l i e n t s e r v e r ( c s ) 计算模式相比，p 2 p 计算模式中的节 点一般在逻辑上是对等的，没有客户端和服务器之分，各个节点之间可以直接进 行通信和交互，无需通过中间的服务器图1 1 给出了两种模式比较的示意 t 3 1 值得注意的是，p 2 p 计算模式与c $ 计算模式是互补而不是完全对立的两种计算模 式例如，c s 计算模式中的s e r v e r 可以通过p 2 p 计算技术来提供，p 2 p 计算模式 中也可以使用某种形式的服务器( 如n a p s t e l l 4 】中的索引服务器) ，图1 1 ( a ) 中给出 的是理想的纯p 2 p ( p u r e p 2 p ) 模式。 p 2 p 模式 图1 1p 2 p 模式与c s 模式示意图 1 1 2 p 2 p 计算的历史 模式 p 2 p 本身不是一种全新的概念，无中心的对等结构在很久以前就已提出，但 是由于缺乏有力的应用背景一直没有受到广泛重视，因为对于集群或者局域网范 围内的分布式系统，其网络连接良好、节点能力强且稳定，设置一个中心节点对 全局进行管理的确方便而有效 1 9 9 9 年诞生的文件共享系统n a p s t c 4 4 j 逐渐改变了这一形势n a p s t e r 是最早 的p 2 p 应用系统，参与系统的是大量个人计算机用户，每个用户将自己愿意共享 的文件提供出来，同时可以下载其他用户共享的文件。n a p s t c r 需要解决的核心问 第2 页 国防科学技术大学研究生院学位论文 题是必须知道哪些机器上有哪些文件，这样当用户提出文件搜索请求时才可以得 到正确的匹配结果。在n a p s t e r 中使用了一个中心服务器，称为目录服务器，存放 所有文件的元数据信息( 文件的标题和一些简单的描述信息) 以及其存放节点的口 地址。节点加入系统时首先要连接目录服务器并报告自身地址及共享的文件列表 用户需要某个文件时向目录服务器提交搜索请求，目录服务器返回符合搜索要求 的所有文件的存储地址，之后用户根据对应地址直接从共享此文件的节点处进行 文件下载。由于耳录服务器只提供索引服务，而不承担文件存储和下载服务，因 此它支持上万节点同时在线n a p s t c r 在发布后迅速流行起来，很快成为增长最快 的网络应用系统 n a p s t e r 中的节点并非全部对等，目录服务器要承担比其它节点繁重得多的工 作，从这个意义上说，n a s p t e r 并非一个纯粹的对等系统由于n a s p t e r 中的节点 动态性很高( 指节点的加入、退出很频繁) ，目录服务器就处在不断更新之中并 且，目录服务器还要负责响应所有用户的查询请求因此，当系统规模更大时， 目录服务器还是会成为系统瓶颈。此外，目录服务器的存在成为系统的关键点， 也就成为整个系统最易受攻击的要害所在。在n a s p t e r 之后的p 2 p 系统都在这一点 上进行了重点改进，系统基本上都采用无中心结构，鲁棒性和可扩展性都得到大 幅度提高。当前p 2 p 计算技术的发展已远远超越了n a p s t c r 及其代表的p 2 p 文件共 享应用，甚至已经超越了p 2 p 计算技术兴起的初衷，p 2 p 计算技术兴起的最初目 标是充分利用i n t c m e t 边缘的客户端资源，但随后p 2 p 计算技术很快就超越了这一 目标。目前p 2 p 计算中的节点可以是i n t c m e t 边缘的客户机，可以是骨干网上大量 分布的服务器( 如o c e a n s t o r e 系统网) ，也可以同时包括各种类型的节点。p 2 p 计算 技术不仅可用于新兴的p 2 p 文件共享应用，也可作为一种通用网络计算技术广泛 应用于各种领域，包括分布式存储、广域分布计算、协同工作、应用层组播和数 据管理等。 1 1 3p 2 p 应用系统 随着p 2 p 技术的发展，越来越多的p 2 p 系统得到应用，主要的应用包括： ( 1 ) 广域分布计算 采用p 2 p 计算技术，充分利用网络( i n t e r n e t 或局域网等) 上大量闲置的计算资 源，将复杂的计算任务分割成小的子任务包，分配到参与f 2 p 计算的各个节点上， 由各个节点来完成子任务芳将锝到的结果进行综合。通常较适于可高度并行的应 用，如天文数据分析、基因组分析和密码破译等，典型项目如s e l l h 伽e 【6 】、 g e n o m e h o m e 、f o l d m g ( 磊抽o m e 和d i s 仃i b m e d e t 等i n i e l 的n c t b a t c h 【7 l 系统采用 此技术，利用世界上2 5 个分公司的1 0 0 0 0 多台机器用于芯片设计，i n t c l 估计已因 第3 页 国防科学技术大学研究生院学位论文 此节约了5 亿美元目前有一些公司也在从事相关工作，如e n 血 o p i a 和p o p u l a r p o w e r 等。 ( 2 ) 广域网分布式存储系统 分布式存储系统一直是分布式系统的一个重要领域，传统的局域网范围内的 分布式文件系统、分布式对象存储系统、分布式数据库系统都有着良好的研究基 础p 2 p 技术出现后，人们试图把这些分布式存储系统向更大范围拓展，在广域网 中构建分布式文件系统【s 习、对象存储系统 1 0 , 1 1 】和数据库系统0 2 , 1 3 1 ( 3 ) 协同工作 基于传统c s 模式的协同工作需依赖于服务器，随着现代组织规模的增大和 分支机构的分散，其代价昂贵，并且大规模的实时协作匾难。通过p 2 p 计算技术， 可在网络上任意两台计算机之间进行实时联系，构建一个安全、共享的虚拟空间， 并通过这虚拟空间进行各种协作活动，以高效地共同完成某项任务典型的p 2 p 协同工作系统包括g r o o v e 1 4 】和m a g i t l 升等。g r o o v e 公司是由l o t u sn o t e s 系统的开 发者r a yo z z i e 创建，目前已被微软公司以1 2 亿美元并购。 ( 4 ) 视频组播系统 视频组播的带宽要求很高，因此传统的c s 结构的组播系统往往由于服务器 出口带宽的限制而导致系统的可扩展性很差。在基于p 2 p 结构的视频组播系统中， 只有少数节点从服务器直接获取数据，更多的节点一方面从其它节点处获得数据， 一方面也向其它节点提供数据。整个系统的体系结构为树状结构或者网状结构 1 6 , 1 7 , 埘这种以对等方式构建的视频组播系统充分利用了节点之间的可用带宽，使 得系统的可扩展性大为提高。 ( 5 ) 即时通讯 即时通讯是非常流行的一种p 2 p 应用。即时通讯系统为大量的互联网用户提 供了实时交流的虚拟平台目前的即时通讯系统通常采用一个( 或多个) 中心服务 器来维护用户的身份认证等基本信息，而节点之间的即时语音或数据通信一般是 以p 2 p 的方式直接进行的。典型即时通讯系统包括i c q 、o l c q 、a i m 、m s n 、s k y p e 和j a b b e r t l 9 1 等。由于目前各种即时通讯系统之间不具有互操作性，j a b b e r 提供了一 个开放源码的实时通信平台，通过一个基于x m l 的协议在不兼容的各种即时通讯 平台间进行消息交换。 ( 6 ) 应用层组播( a p p l i c a f i o n - l e v d m u l f i c a s o 虽然球层组播技术提出已经有十年之久，但一直没有被广泛使用，主要原因 是它需要改变路由器算法，因此难以被广泛部署并且p 组播需要记录组状态( 组 名与成员地址) ，使得协议十分复杂，也不符合i n t e r a c t 设计中一贯坚持的d 层元 状态的基本原则。鉴于此，人们提出不需要口层支持的应用层组播，也就是在需 第4 页 国防科学技术大学研究生院学位论文 要收到消息的节点之间不断转发消息，保证消息最终能够被该组的所有成员收到 很多应用层组播在节点之间通过树状结构进行组播，不但保证有节点进出时树状 结构能够迅速修复，而且优化这一树状结构，使其与下层i n t c r n c t 结构更为匹配， 以提高组播效率、降低组播通信对i n t e r n e t 链路产生的压力口啦! 捌 ( 7 ) 大规模联机游戏 在很多大规模联机游戏中，有大量的玩家通过网络同时参与游戏，例如l h e a g e 游戏有两百万注册用户，1 8 万用户同时在线传统的联机游戏中，玩家的注册信 息以及游戏状态信息等都是由服务器来维护，给服务器带来了大量的负荷网络 游戏设计中的一个重要趋势是玩家参与游戏设计，传统c s 模式限制了众多玩家 同时对游戏进行扩展的能力。采用p 2 p 计算技术，可以充分利用游戏客户端的资 源，将全局游戏状态等信息分布到客户端上，并根据游戏者在虚拟世界中的位置 等信息在客户端之间建立自组织的连接关系，便于游戏状态等信息的维护和查询。 典型的p 2 p 联机游戏系统如s i m m u d 项目瞄】等 ( 8 ) 域名服务器( d n s ) 当前i n t c r n e t 的d n s 服务器之间的连接使用树状结构。在这种结构中，解析 不常用的域名时需要在树状结构中进行多跳的查询转发，因此效率比较低。尤其 是如果对一个错误域名进行解析，或者负责解析的服务器暂时不可用时，需要很 长时间才能返回用户并显示查询失败。另外，由于现行机制下标识一份文档的u d 和它的存储地是直接相关的，这给文档的迁移带来很多不便。很多工作致力于使 用p 2 p 结构重建d n s 系统，使其更高效讲瑚】，并且剥离文档标识与存储地点的相 关性，取得了很好的效果 另外，还有一些工作试图建立p 2 p 搜索引擎郾捌、利用p 2 p 系统测量i n t e r n e t 链路状况嘲、通过p 2 p 路由消除防火墙与网关的障碍1 2 9 , 3 0 , 3 ”、事件通知框架、p 2 p 电子邮件等。 1 2p 2 p 系统的拓扑结构 p 2 p 系统有很多种分类方法。目前研究者们通常根据p 2 p 系统拓扑结构的分 散度和耦合度来进行分类p 2 _ 3 3 1 分散度是指p 2 p 系统的拓扑结构对中央服务器的 依赖程度。根据分散度，p 2 p 系统可以分为三大类： ( 1 ) 集中式拓扑 。 在集中式拓扑的p 2 p 系统中，存在着一个( 或少数几个) 中央服务器，作为目 录服务器来协调其它各个节点之间的交互，但节点之间的交互与资源共享等行为 仍是直接以p 2 p 模式进行的典型系统如n a p s t e l 工4 】和b i t t o r r e n t p q 等集中式拓扑 的p 2 p 系统也称为是混合p 2 p ( h y b r i dp 2 p ) 模式的 第5 页 国防科学技术大学研究生院学位论文 由于在集中式拓扑结构中存在着中央服务器，所以系统的性能严重受限于中 央服务器这种结构导致了系统瓶颈和单点失效等问题，因此系统的健壮性不好 ( 2 ) 全分布式拓扑 在全分布式拓扑的p 2 p 系统中，所有节点都是完全平等的，每个节点既是服 务器也是客户端，系统中没有任何目录服务器典型系统如g n u t e l l a t 3 7 1 、f l r e e n e t t 3 9 和c h o r d l 3 9 等全分布式拓扑的p 2 p 系统也称为是纯p 2 p ( p u r e p 2 p ) 模式的。耦合 度是用来衡量p 2 p 系统的拓扑构造过程是受某种机制严格控制还是动态、非确定 性的。根据耦合度，全分布式拓扑结构p 2 p 系统可分为两大类： 夺非结构化拓扑( u n s t r u c t u r e dt o p o l o g y ) 在非结构化拓扑的p 2 p 系统中，节点问的逻辑拓扑关系通常较为松散，具有较 大的随意性数据( 或数据元信息) 的放置通常与p 2 p 系统的拓扑结构无关，一般 只放置在本地。非结构化拓扑的实现和维护相对简单；可支持灵活的数据搜索条 件 结构化拓扑( s t r u c t u r e dt o p o l o g y ) 在结构化拓扑的p 2 p 系统中，节点间的逻辑拓扑关系通常由确定性的算法严格 控制，资源( 或资源的元信息) 的放置也是由确定性的算法精确发布到特定的节点 上。结构化拓扑p 2 p 系统通常采用分布哈希表技术( d i s t r i b u t e dh a s hm l e ， ，d m t 2 2 , 2 3 构建。结构化拓扑的优点是资源定位准确并且可保证一定的效率，有着 良好的可扩展性和性能，因而适用于对可用性要求高的系统结构化拓扑的应用 领域广泛，包括分布式存储、应用层组播和名字服务等。结构化拓扑的p 2 p 系统 大都是全分布式的，如c h o r d l 3 9 、t a p e g 缸严田和c a n l 4 i 1 等。 在全分布式拓扑结构中，所有节点都是完全平等的，承担的任务都是一样的， 在非结构化拓扑结构中，所有节点都采用相同的泛洪式技术广播消息在结构化 拓扑结构中，每个节点分配同样大小的m 空间，存储数据m 值包含在本节点d 空间的数据信息，且响应对该数据的访问请求但在实际网络中节点能力存在广 泛的差异性，如c p u 速度、存储能力、网络带宽等在全分布式拓扑结构中没有 考虑节点能力的差异性，系统的性能受其中弱节点的影响比较严重。 ( 3 ) 层次式拓扑 在层次式拓扑结构p 2 p 系统中，存在一些。超级节点”( s u p e r - p e e r ) 超级节 点具有比普通节点更强的能力和更高的地位，通常充当其它一些节点目录服务器 的角色。但这些超级节点都是由p 2 p 系统动态选择和组织的，一般不会给p 2 p 系 统带来单点失效等问题。典型系统如f a s t t r a c k t 3 5 】