（计算机软件与理论专业论文）对等计算中的若干问题研究.pdf

摘要， 本文着重研究对等( p e e r - t o - p e e r ，简称p 2 p ) 计算。对等网应用在近 几年内己得到突飞猛进的发展。p 2 p 文件共享系统是对等计算最重要的应 用之一。p 2 p 文件共享系统能否成功极大地取决于搜索机制的多样性和扩 展性。 当前支持分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 功能的结构 化系统( 如c a n 【5 】、c h o r d 6 】、p a s t r y 【7 】和t a p e s t r y 【8 】) 易扩展但不能 有效地支持部分匹配的查询；而基于扩散的非结构化系统( 如g n u t e l l a ) 支持多样化查询但不易扩展。本文作者提出了一种新型的对等网体系结 构一语义对等网( s e m a n t i cp e e r t o - p e e rn e t w o r k s ，s p n s ) ，其中语义相关 的结点互相连接在一起。基于内容编址网( c o n t e n ta d d r e s s a b l en e t w o r k s ， c a n ) ，我们分别构造了粗粒度语义对等网p g r o u p 和细粒度语义对等 网f g r o u p 。根据不同的查询情况，我们分别对p g r o u p 和f g r o u p 提出相应的 搜索算法。模拟结果表明，搜索效率比g n u t e l l a 网络大大提高了。 为加速大文件的接收，许多p 2 p 系统如k a z a a 、g r o k s t e r 和m o r p h e u s 等 采用了并行下载机制。为研究多个用户同时使用这一机制时其对整个网络 的影响，本文作者利用非合作博弈论对并行下载问题进行建模。就我们所 知，这是第一次用非合作博弈论方法分析并行下载问题的工作。在这个框 架下，我们给出了纳什均衡在一般网络中的特征：针对特殊的网络分析了 纳什均衡的性质：并对两个特殊的网络建立了纳什均衡的动态收敛性；最 后，分别从用户和系统的角度，即分别从单个用户的下载时延和所有连接 1 本研究受到科学技术部基础研究重大项目前期研究专项第2 0 0 1 c c a 0 3 0 0 号，国家自然 科学基金第6 0 2 7 3 0 4 5 号和上海市科技发展基金第0 2 5 1 1 5 0 3 2 号资助。 籼? f 霄、锄t 8 0 氘 ：船垒文公榴 i i 上总的时延，研究了纳什均衡的效率。结果发现，尽管从用户的角度来 看，纳什均衡是最优的；但从系统的角度来看，纳什均衡却很糟糕。 大多数d h t s 如c a n 、c h o r d 、p a s t r y 和t a p e s t r y 需要o ( 1 0 9 n ) 的邻居 数和o ( 1 0 9 n ) 的路由长度。为维护路由的正确性和效率，当一个结点 加入或离开系统时它们需要对路由表进行o ( 1 0 9 n ) 的修复操作。考虑 至i p 2 p 系统中用户的高度动态性，构造具有o ( 1 ) 邻居数采i l o ( 1 0 9 n ) 路由长 度的d h t s 是很重要的。最近的文献【7 0 ，7 3 ，7 4 1 提出了基于d eb r u i j n 图 的p 2 p 网络，但他们都仅使用了单方向的链路。通过引入双向链路，我们 进一步改进了其中的路由算法，并使用连续离散方法7 5 1 构造了d h t s 。 关键词： 对等网，内容编址网，语义对等网，并行下载，纳什均衡，分布式哈 希表 中图法分类号：t p 3 9 3 ，t p 3 0 1 6 a b s t r a c t z t h i st h e s i sf o c u s e so np e e r t o - p e e r ( p 2 p ) c o m p u t i n g p 2 pn e t w o r k i n g a p p l i c a t i o n sh a v es e e ne x p l o s i v eg r o w t hi nr e c e n ty e a r s o n eo ft h em o s t i m p o r t a n ta p p l i c a t i o n so fp 2 pc o m p u t i n gi sp 2 pf i l es h a r i n gs y s t e m t h e s u c c e s so fp 2 pf i l e s h a r i n gs y s t e mh i 馥l yd e p e n d so nt h es c a l a b i l i t ya n d v e r s a t i l i t yo fi t ss e a r c hm e c h a n i s m e x i s t i n gs t r u c t u r e dp 2 pn e t w o r k s ( s u c ha sc a n 【5 】，c h o r d 【6 1 ，p a s t r y 【7 a n dt a p e s t r y 【8 】) s u p p o r t i n g d i s t r i b u t e dh a s h t a b l e ( d h t ) f u n c t i o n a l i t y a r es c a l a b l e ，b u tt h e yc a nn o ts u p p o r tp a r t i a l m a t c hq u e r i e se f f e c t i v e l y o n t h eo p p o s i t e ，u n s t r u c t u r e dp 2 pn e t w o r k s ( s u c ha sg n u t e h a ) r e l yo nf l o o d - i n g f o rs e a r c h ，t h u ss u p p o r t i n gp a r t i a l m a t c hq u e r i e s ，b u ts u c h f l o o d i n gd o e s n o tm a k et h es y s t e m ss c a l a b l e w ep r o p o s ean o v e la r c h i t e c t u r ec a h e ds e m a n t i cp e e r t o - p e e rn e t w o r k s ( s p n s ) w h e r es e m a n t i c a l l yr e l a t e dn o d e sa r e c o n n e c t e dt oe a c ho t h e r b a s e do nc o n t e n ta d d r e s s a b l en e t w o r k s ( c a n ) ， w ec o n s t r u c tc o a r s e - g r a i n e ds p n s ( p g r o u p ) a n d f i n e - g r a i n e ds p n s ( f g r o u p ) r e s p e c t i v e l y a c c o r d i n gt ot h ed i f f e r e n tq u e r y i n g ，w ep r e s e n tc o r r e s p o n d - i n gs e a r c ha l g o r i t h m si np g r o u pa n df g r o u pr e s p e c t i v e l y a si ss h o w nb y s i m u l a t i o n s ，s e a r c he f f i c i e n c yi si m p r o v e dg r e a t l yc o m p a r e dt og n u t e l l a t oe x p e d i t et h er e c e p t i o no fal a r g e f i l e ，m a n yp 2 ps y s t e m ss u c ha s k a z m u ，g r o k s t e ra n dm o r p h e u sh a v ee m p l o y e dt h es c h e m eo fp a r a l l e ld o w n 一 2 t h i sw o r ki ss u p p o r t e db yag r a n tf r o mt h em i n i s t r yo fs c i e n c ea n dt e c h n o l o g y ( g r a n t 社2 0 0 l c c a 0 3 0 0 0 ) ，n a t i o n a ln a t u r a ls c i e n c er 】n d ( g r a n t # 6 0 2 7 3 0 4 5 ) a n ds h a n g h a is c i e n c ea n dt e c h n o l o g yd e v e l o p m e n tn l r l dr g r a n t # 0 2 5 1 1 5 0 3 2 ) i i i l o a d i n g t oi n v e s t i g a t et h ei m p a c tt h a tt h i ss c h e m em i g h th a v eo nt h en e t w o r ki f m u l t i p l ec l i e n t ss i m u l t a n e o u s l yu s ei t j w ef o r m u l a t ep a r a l l e ld o w n l o a d i n ga s an o n c o o p e r a t i v eg a m e t ot i l eb e s to fo u rk n o w l e d g et h i si s t h ef i r s tw o r kt h a ta n a l y z e st h ep a r a l l e ld o w n l o a d i n gp r o b l e mi nan o n c o - o p e r a t i v eg a m et h e o r e t i c a lf a s h i o n w i t h i nt h i sf r a m e w o r k ，w ep r e s e n t a c h a r a c t e r i z a t i o no ft h et r a f f i cc o n f i g u r a t i o na tn a s he q u i l i b r i u mi nag e n e r a l n e t w o r k ，a n da n a l 3 7 z ei t sp r o p e r t i e si nas p e c i f i cn e t w o r k w ea l s oe s t a b l i s h t h ed y n a m i cc o n v e r g e n c et oe q u i l i b r i u mf o rt w os p e c i f i cn e t w o r k s f i n a l l y , w ei n v e s t i g a t et h ee f f i c i e n c yo fn a s he q u i l i b r i u mf r o mt h ep o i n to fv i e wo f t h ec l i e n t sa n dt h es y s t e mr e s p e c t i v e l y , i e ，d o w n l o a d i n gl a t e n c i e sp e r c e i v e d b yi n d i v i d u a lc l i e n t sa n dt o t a l l a t e n c i e so v e ra 1 1c o n n e c t i o n s w ef i n dt h a t a l t h o u g ht h et r a f f i cc o n f i g u r a t i o na tn a s he q u i l i b r i u mi so p t i m a lf r o mt h e p o i n to fv i e wo ft h ec l i e n t s l i t m a y b eb a df r o mt h ep o i n to fv i e wo ft h e s y s t e m m o s td h t ss u c ha sc a n ，c h o r d ，p a s t r ya n dt a p e s t r yr e q u i r eo ( 1 0 9 n ) n e i g h b o r sa n d h a v eo ( 1 0 9 n ) p a t h l e n g t h s i no r d e rt om a i n t a i nt h ee f f i c i e n c y a n dc o r r e c t n e s so fr o u t i n g ，t h e yr e q u i r eo ( 1 0 9 n ) r e p a i ro p e r a t i o n so ft h e i r r o u t i n gt a b l e sw h e n an o d ej o i n so rl e a v e s g i v e nt h eh i g h l yt r a n s i e n tu s e r p o p u l a t i o n si np 2 ps y s t e m s ，i ti st h e r e f o r eo fg r e a ti m p o r t a n c e t oc o n s t r u c t d h t sw i t ho ( i ) n e i g h b o r sa n do ( 1 0 9 n ) p a t h l e n g t h s s e v e r a lr e c e n tp a p e r s 7 0 ，7 3 ，7 4 h a v ep r o p o s e dd eb r u i j ng r a p h s f o rp e e r t o - p e e rn e t w o r k s b u t t h e ya l l u s el i n k si no n l yo n ed i r e c t i o n b yi n t r o d u c i n gb i d i r e c t i o n a l i t yo f l i n k s ，w ef u r t h e ri m p r o v et h er o u t i n ga l g o r i t h ma n d c o n s t r u c ts u c hd h t s b y u s i n gt h ec o n t i n u o u s d i s c r e t ea p p r o a c h 7 5 k e y w o r d s ： p e e r - t o - p e e r ，c o n t e n ta d d r e s s a b l en e t w o r k s s e m a n t i c p e e r t o - p e e rn e t w o r k s ，p a r a l l e ld o w n l o a d i n g ，n a s he q u i l i b r i u m ，d i s t r i b u t e dh a s h t a b l e c l a s s i f i e a t i o nn u m b e r ：t p 3 9 3 ，t p 3 0 1 6 第1 章 引言 1 1 背景知识 随着计算机处理能力和存储容量的提高以及通信技术的进步，我们可以随 时随地接入网络并通过直接交换共享计算机资源和服务，对等计算( p e e r t op e e rc o m p u t i n g ) 也就应运而生了。对等网( p e e rt op e e r ，简称p 2 p ) 是 没有任何集中控制的分布式系统，系统中每个结点在功能上是等同的，既 是客户机又是服务器，没有主从之分。 其实对等网并不是一个新的概念，在互联网问世的时候它就已经 存在了。早期a r p a n e t 的几台主机就是以对等的方式互联，不存在 主从或客户机服务器关系。随着因特网规模的增大，客户机服务器 应用如w w w 、f t p 、t e l n e t 等流行起来。1 9 9 9 年5 月，美国东北大学的 一年级学生s h a w nf a n n i n g 率先发起了对等计算模式一m p 3 文件共享系 统n a p s t e r 。到2 0 0 0 年1 2 月，n a p s t e r 捐 有的用户已达5 千万。继n a p s t e r 之 后，新的对等网文件共享系统f r e e n e t 、g n u t e l l a 和k a z a a 等也日益流行。 对等网应用突飞猛进的增长已为世人所瞩目，对等计算已成为工业 界和学术界的研究热点。工业上，许多大公司如i n t e l 、h p 、s o n y 等组织 了对等网工作组( p e e r - t o - p e e rw o r k i n gg r o u p ) ，从事对等计算底层标准 研究；s u n 公司的j x t a 项目致力于为大规模的分布式应用提供开发平 台。学术上，有许多专门的对等计算国际会议如i n t e r n a t i o n a lw o r k s h o p c h a p t e r1 引言 2 o np e e r - t o - p e e rs y s t e m s 和i n t e r n a t i o n a lc o n f e r e n c eo np e e r - t o - p e e rc o r n p u t i n g 等；有声望的国际会议如s i g c o m m 、i n f o c o m 和i c d c s 等也增 开了对等计算的专栏。还有许多关于对等网的在研项目如麻省理工 学院的c h o r d 、i c s i 的c a n 、伯克利的t a p e s t r y 及r i c e 大学、微软研究院 等的p a s t r y 。2 0 0 2 年9 月，麻省理工学院、伯克利、i c s i 、纽约大学以 及r i c e 大学等联合获得一千二百万美圆的自然科学基金项目i r i sf i n f r a s - t r u c t u r ef o rr e s i l i e n ti n t e r n e ts y s t e m s ) ，用以开发安全、容错和抗攻击的 分散化因特网基础设施。该项目的最终目的是开发一个由不可靠的、低廉 的结点组成的可靠的、大规模分布式系统。 1 2 对等计算的概念 从不同角度，存在几种对等计算的定义和诠释。对等计算工作组定 义p 2 p 为“通过直接交换共享计算机资源和服务”f 1 】；a l e xw j y t 8 e l 【2 将之 定义为“以非客户的能力使用因特网外围设备”；c l a ys h i r k y 3 则给出了下 面的定义：“对等计算是利用因特网边缘设备资源，如存储、c p u 周期、 内容等的一类应用。因为访问这些分散化的资源意味着在一个连通性不稳 定和不可预测i p 地址的环境中进行，p 2 p 结点必须能够独立于d n s 系统运 行，并且具有独立于集中服务器的大部分的或完全的自治性。” 对等计算和客户机服务器计算都是分布式计算模型，它们的主要区别 为：客户机服务器计算模型( 如图1 1 ( a ) ) 是非对称的，而对等计算( 如 图1 1 ( b ) ) 是对称的。在客户机服务器系统中，一个或少量的服务器为一 定数量的客户机提供存储和计算等方面的服务，客户发出请求而服务器服 务请求；服务器在存储和计算方面比客户机具有更高的性能且在系统中比 客户机滞留更长的时间。而对等计算消除了这种非对称性，系统中每个结 点既可以提供服务也可以享用服务，即每个结点既是客户机又是服务器， 在功能上是等同的。这样，对等计算就能充分利用客户机上存在的存储和 计算方面的空闲资源。 c h a p t e r1 引言 ( a ) 客户机服务器计算模型 ( b ) 对等计算模型 图1 1 ：客户机服务器计算模型与对等计算模型之比较 1 3 对等计算的特点 3 对等网是分散化的、自组织的分布式系统，具有如下特点： 对称的系统：系统中所有或大部分结点在功能上是等同的，既可作客 户机又可作服务器。 分散化( d e c e n t r a l i z a t i o n ) ：分散化是指系统中的数据和资源分散在 参与的结点中。在客户机服务器模型中，数据被放在集中的服务器 上，客户通过执行请求一响应协议来访问服务器上的数据。这种系统 不可避免地存在性能瓶颈和单点故障问题。而在对等计算模型中，每 个结点具有对数据和资源的拥有和控制权，在功能上是等同的。 自治性( a u t o n o m y ) ：许多情况下，分布式系统中的用户希望在本 地处理数据而不情愿依赖于第三方服务供应商。对等计算自然地支持 这种自治性。 动态系统：结点到达和离开系统是即席的( a d h o c ) ，且他们在系统 中的滞留时间长短不一。 c h a p t e r1 引言 p e e r lp c e r 3p e e r 6 瓣订 一：l 一l 一一一1 一 o v e r l a yn e t w o r k p h y s i c a ln e t w o r k 图1 2 ：覆盖网络示意图 4 自组织( s e l f - o r g a a f i z a t i o n ) ：在控制论中，自组织定义为“系统组织 的自发增加过程，即这种增加不受环境或其它外部系统的控制”f 4 1 。 由于需要满足扩展性、容错、动态性以及自治性等要求，对等网系统 应为自组织的。对等网规模的增大增加了系统的故障概率，以及结点 的动态性需要系统具有自维护和自修复能力；同时由于不可能用单一 的全局机构来管理大规模的动态系统，这种管理应该分布在参与的各 个结点上。 异质性( h e t e r o g e n e i t y ) ：系统中各个结点的c p u 处理能力、存储能 力、带宽、以及他们在系统中的滞留时间均有很大的不同。 覆盖网络( o v e r l a yn e t w o r k s ) ：对等网是一种覆盖网络，对等网结 点间的连接关系和路由是应用层意义上的，在对等网上路由一跳 ( o n eh o p ) 往往对应于在i p 层上路由一跳或几跳，如图1 2 所示。 1 4 对等计算的优点 利用对等计算，我们可以： c h a p t e r1 引言 5 汇聚资源，减小成本：由于需要昂贵的服务器提供大量的存储、 计算以及访问带宽等资源，以客户机j j l i 务器架构的大规模分布 式系统的成本很高。而对等网通过汇聚来自因特网边缘的大量 低廉设备的资源，可以减小系统的成本。对等网文件共享系统 ( 如n a p s t e r ，g n u t e l l a ) 通过将文件分散存储在各个结点上，不仅 汇聚了系统中结点的存储空间还汇聚了下载文件所需的通信带宽。 而s e t i h o m e 则将大量的计算任务分散在参与结点上运行，充分利 用结点的空闲c p u 周期，来分析天文望远镜收集的数据以寻找地球 外的生命。 改进扩展性：对等网分散化的特点有助于改进系统的扩展性。n a p s t e r 通过让发出请求的结点直接从拥有所请求文件的结点上下载 文件，改进了系统的扩展性，其规模在高峰期可达到6 百万用 户。s e t i h o m e 则通过让参与的结点并行地执行计算任务，规 模也达到了几百万用户。g n u t e l l a 文件共享系统由于采用盲目的 扩散方式搜索文件，造成很大的资源浪费，扩展性差。支持分 布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 功能的对等网系统 如c a n 【5 卜c h o r d 【6 i 、p a s t r y 7 j 和t a p e s t r y 8 j 中每个结点的邻居数 为o ( 1 0 9 n 1 ( 系统中总的结点数为n ) ，查找文件需要o ( 1 0 9 n ) 剧， 大大改进了系统的扩展性。 提高容错性和可用性：对等计算消除客户机服务器系统仅有单一访 问点造成的瓶颈和单点故障问题。由于对等网是分散化的，单个结点 故障对整个系统的影响很小。同样由于分散性，攻击者难以找到合适 的攻击点，从而提高了系统的抗攻击能力。网络故障或结点故障( 包 括离开系统) 都可造成数据的不可用。对于网络故障，由于对等网中 发出请求的结点和拥有资源的结点之间往往存在多条冗余路径，从而 可以绕过故障区域。对于后者，通过对数据主动或被动地复制来减轻 或消除这种故障。对等网文件共享系统如g n u t e l l a ，流行的文件自动 地复制在多个结点上：f r e e n e t 贝l j 主动地将文件复制在回答查询路径 上的结点：o c e a n s t o r e 维护了两层复制，并通过对管理域的监视，避 c h a p t e r j 引言6 免将文件复制到高故障概率的地方。 提高匿名性和抗审查能力：匿名性( a n o n y m i t y ) 的重要目标是隐藏 用户的身份及保护用户的隐私，进一步的目标是保护文件免受审查 ( c e n s o r s h i pr e s i s t a n c e ) 。利用对等网可构建满足下列性质的抗审 查系统： 一不能识别出在系统中发布文件的发布者身份，使得采用攻击发 布者来审查文件的方法不可行： 一不能识别出检索文件的请求者身份，使得采用攻击请求者来审 查文件的方法不可行； 一难以在系统中引入一个新的结点使该结点负责某一特定的文 件，使得采用新结点自愿地负责某个文件从而来审查该文件的 方法不可行： 一难以根据给定的文件识别出存储该文件的结点，从而使对该结 点进行攻击来审查文件的方法不可行。 对等网文件共享系统f r e e n e t 中，作出回答的结点要么本身拥有所 查询的文件，要么由于路径复制从“上游”结点得到该文件。从攻击 者的角度看，作出回答的结点可能是无辜的( p o s s i b l yi n n o c e n t ) ， 因而f r e e n e t 具有一定程度的匿名性；文献1 1 1 使用信任第三方来 获得相互匿名，即文件请求者和提供者都不知道对方的身份；c a n 5 、c h o r d 【6 】、p a s t r y 7 年i l t a p e s t r yi s 使用哈希技术将文件存储在结 点上，结点的这种存储方式是非自愿的，因而对所存储的文件是不负 责任的( u n a c c o u n t a b l e ) 。文献【1 2 】和文献【1 3 】分别对c h o r d 和c a n 进一步作了改进，提高其抗审查能力。 以上部分内容参考了文献【1 4 卜 1 5对等计算的体系结构 对等网文件共享系统是对等计算最重要的应用之一。当前对等网文件共享 c h a p t e r1 引言 7 系统的体系结构大致有如下三种：集中式( c e n t r a l i z e d ) 、分散式非结构 化( d e c e n t r a l i z e da n du n s t r u c t u r e d ) 和分散式结构化( d e c e n t r a l l z e db u t s t r u c t u r e d ) 。 1 5 1 集中式 n a p s t e r 及其它类似的系统用一个集中目录服务器存储系统中所有文件的 索引。当用户加入系统时，向目录服务器注册可供其他用户下载的文件的 索引：当用户检索文件时，以文件名向服务器提交查询，获得存储所需要 文件的主机的i p 地址，然后文件从这个主机下载给用户；当用户离开系统 时，他所共享的文件索引就从服务器中删除掉。这样，n a p s t e r 以p 2 p 的方 式进行实际的文件传输，而以集中的方式进行文件的定位。 集中式p 2 p 文件共享系统的优点是支持多样化( 部分匹配) 的查询， 支持稀少文件的查询；缺点是系统存在单点故障。 为了避免系统的单点故障，其他两种体系结构均不使用集中的目录服 务器，而将文件索引分散于参与的结点中，这两种体系结构的区别主要在 于文件索引的分布方式及对网络拓扑的控制方式。 1 5 2 分散式非结构化 分散式非结构化系统中既没有集中的目录服务器，又对p 2 p 网络拓扑 ( p 2 p 成员的连接集合) 和文件放置没有任何精确的控制。系统中每个结 点只维护自己存储的文件及其索引。c n u t e l l a 就是这样的一个例子。结点 加入网络时只需遵守一些松散的规则，形成随机的覆盖网络拓扑。查找文 件的典型做法是以一定的半径在网络中扩散( f l o o d i n g ) 查询消息。接收到 消息的结点，将其与所存储的文件进行比较，若存在正的匹配，则向提出 查询的结点回答；若消息的生命期( t i m et ol i v e ，t t l ) 不为0 ，则将查 询消息向邻居结点扩散，否则，将之丢弃。 非结构化设计的优点是非常适应于动态系统，能够灵活地处理结点不 断加入或离开事件并且支持多样化查询；缺点是当前的搜索算法对网络及 参与者产生很大的负载，系统非常不可扩展，并且由于使用限制范围的查 c h a p t e r1 引言 8 找，即使目标文件存在于系统中，仍可能找不到。这样，对稀少文件的定 位非常不利。 1 5 3 分散式结构化 分散式结构化系统也没有集中目录服务器，但为结构化的。这里的 结构指的是系统对p 2 p 网络拓扑和文件放置都精确地加以控制，仔 细地将文件索引分布在参与的结点中。这种系统支持分布式哈希表 ( d i s t r i b u t e dh a s ht a b l e ，d h t ) 功能，如c a n 【5 】、c h o r d 【6 6 、p a s t r y 7 1 和t a p e s t r y 8 1 。d h t 系统中，文件与键( k e y ) 相关联。键为一定长 度( 如1 2 8 位) 的位串，通过哈希文件名而得；结点的标志符通过哈 希i p 地址获得，并与键具有相同的地址空间。每个结点为哈希桶，负 责存储一定范围的键。d h t 系统有一个基本的操作，l o o k u p ( k e y ) 。给 定k e y ，l o o k u p ( k e y ) 返回存储k e y 的结点的i p 地址。该操作允许结点基于键 放置和获得文件，因而支持类似于哈希表的功能。查找文件时，直接将 查询消息逐步地路由到拥有所需文件的结点上。d h t 系统已成为许多大 规模分布式系统的构建基础，如分布式文件系统 1 5 ，1 6 ，l7 、应用层组播 f 1 8 ，1 9 1 和事件通知服务 2 0 ，2 1 】等。 这种系统的优点是易于扩展，查询效率高，支持稀少文件的查询；缺 点是对结点的不断加入和离开需要频繁地做些额外的工作，不能有效地支 持多样化查询。 1 6 本文工作 p 2 p 文件共享系统是对等计算最重要的应用之一。p 2 p 文件共享系统能否 成功极大地取决于搜索机制的多样性和扩展性。当前支持分布式哈希表功 能的结构化系统易扩展但不能有效地支持部分匹配的查询；而基于扩散 的非结构化系统支持多样化查询但不易扩展。分散式非结构化p 2 p 系统的 低效性在于：p 2 p 网络拓扑与数据的位置无关，查询消息在整个网络中盲 目扩散。为改进这种盲目扩散搜索的效率，本文作者提出了语义对等网 c h a p t e r1 引言 9 ( s e m a n t i cp e e r - t o - p e e rn e t w o r k s ，s p n s ) 的新概念。语义对等网是一种 新型的体系结构，介于结构化和非结构化之间：语义相关的结点自组织在 一起形成语义对等网s p n s ：而对象的放置仍保留非结构化系统的特征， 每个结点只存储自己的对象。我们基于c a n 分别研究了粗粒度语义对等 网p g r o u p 和细粒度语义对等f 5 t f g r o u p 的构造、维护及搜索算法。提出的 结点加入算法能够使结点快速地加入到相应的s p n 中，并且构造的s p n 能 够适应结点内容的不断变化。对于p g r o u p ，针对用户不同的查询行为，提 出了直接组扩散算法d g f 、随机组扩散算法r g f 和预测组扩散算法p g f 。 基于b l o o m 过滤器我们通过简单的分布式算法构造y p e e r 组过滤器，利用 增大的背景开销来改进r g f 算法。对于f g r o u p ，不仅语义相关的结点形 成s p n ，而且构造的s p n 之间也是语义相关的，它们在逻辑上组织为一个 层次结构：我们提出的搜索算法使查询消息只在合适的s p n 中扩散，并可 以灵活地在系统性能和查全率之间进行折中。 为加速大文件的接收，许多p 2 p 系统如k a z a a 、g r o k s t e r 和m o r p h e u s 等 采用了并行下载机制。文献4 7 1 针对单个用户使用并行下载的实验表明， 该用户可获得明显的性能改进。为了理解这一技术被广泛采用时其对整个 网络和服务器的影响，最近，文献【4 8 】和【4 9 】用实验和模拟的方法对多个 用户同时使用的情况做了进一步的研究。本文作者利用非合作博弈论对并 行下载问题进行建模。就我们所知，这是第一次用非合作博弈论的方法分 析并行下载问题的工作。在这个框架下，我们给出了纳什均衡在一般网络 中的特征；针对特殊的网络分析了纳什均衡的性质；动态系统并不是一 开始就处于均衡，我们采用文献 5 2 ，5 3 】提出的初等逐步系统( e l e m e n t a r y s t e p w i s es y s t e m ，e s s ) 对两个特殊的网络分析纳什均衡的收敛性；纳什均 衡并不总最优化总的系统性能，为了量化用户自私行为所导致的系统性能 损失，我们分别从用户和系统的角度，即分别从单个用户的下载时延和所 有连接上总的时延，研究了纳什均衡的效率。结果发现，尽管从用户的角 度来看，纳什均衡是最优的；但从系统的角度来看，纳什均衡却很糟糕。 大多数d h t s 如c a n 、c h o r d 、p a s t r y 和t a p e s t r y 需要o ( 1 0 9 n ) 的邻居 数和o ( 1 0 9 n ) 的路由长度。为维护路由的正确性和效率，当一个结点 加入或离开系统时它们需要对路由表进行o ( i o g n ) 的修复操作。考虑 c h a p t e r1 引言 1 0 到p 2 p 系统中用户的高度动态性，构造具有o ( 1 ) 邻居数和o ( f o g ) 路由长 度的d h t s 是很重要的。最近，文献【7 0 ，7 3 ，7 4 提出了基于d eb r u i j n 图 的p 2 p 网络，但他们都仅使用单方向的链路。通过引入双向链路，同时保 持常数的结点连接度，我们进一步优化了其中的路由算法。最后使用连 续一离散方法 7 5 】构造了d h t s 。 1 7 本文结构 第二章简单综述分散式结构化系统和分散式非结构化系统中的资源定位和 路由算法。 第三章提出语义对等网的概念；基于c a n 分别研究粗粒度语义对等 网p g r o u p 和细粒度语义对等网f g r o u p 的构造、维护及搜索算法；并简单 讨论其中的热点问题：最后，给出模拟结果。 第四章利用非合作博弈论对多用户并行下载问题进行建模，研究纳什 均衡的特征、性质、收敛性及效率问题。 第五章研究常数度、对数直径的d h t 路由网络，并基于无向d e b r u i j n 虱使用连续一离散方法构造d h t s 。 第2 章 对等网资源定位和路由算法综述 对等网应用有一系列的功能需要：冗余、匿名、认证、可扩展、负载均 衡、动态、自组织、搜索( 即对象的定位和路由) 等，其中最核心的是数 据对象的定位和路由( 本文中的对象、文档、文件指的是同一概念，以下 不再区分) 。下面分别讨论分散式结构化系统和分散式非结构化系统中的 资源定位和路由算法。 2 1分散式结构化系统 2 1 1p r r p l a x t o n ，r a j a r a m a n 和r i c h af 2 2 1 第一次提出了基于d h t 的可扩展的路由 算法。尽管p r r 算法由于假定静态的结点环境而并不适用于p 2 p 系统， 但p r r 算法的确提供了相当高效的路由机制。算法通过执行前缀路由来 转发查询消息，即每一个路由步“校正”一个前缀位。例如，如果标志符 为2 0 1 4 的结点收到键为3 2 2 4 的查询消息，那么该结点就将查询路由到与 键3 2 2 4 第一位相匹配的结点，如结点3 1 0 3 ，然后结点3 1 0 3 再将查询消息路 由到与键3 2 2 4 第二位也匹配的结点，如结点3 2 1 1 等，如图2 1 ( a ) 所示。为 此，每个结点须将与自己的所有前缀匹配而下一位不同的结点作为邻居， 如图2 ，1 ( b ) 所示。如果系统中有n 个结点，每个结点需要存储o ( 1 0 9 n ) 个邻 c h a p t e r 2 对等网资源定位和路由算法综述 2 0 1 0 2 0 1 0 2 0 0 x 2 0 i x 2 0 x x 2 1 x x o x x x l x x x 剿篙剥罢憔 2 0 1 4 ll2 0 4 x ll2 3 x x i1 4 x x x ( a ) 从结点2 0 1 4 搜索键3 2 2 4 的路( b ) 结点2 0 1 4 的路由表 由过程 图2 1 ：p r r 路由算法 0 0 4 l 1 3 2 1 2 2 l o 3 1 0 3 4 2 4 3 1 2 居。由于每次查询都前进一位，则路由的路径长度最多为o ( f 0 9 ) 应用层 跳( a p p l i c a t i o nl e v e lh o p s ) 。 2 1 2 t a p e s t r y t a p e s t r y 8 对p r r 算法进行修改来适应动态的结点环境。同时保持原来的 性质：每个结点有o ( t o g n ) 个邻居，路由长度最多蔓j o ( 1 0 9 n ) 。 2 1 3 p a s t r y 在p a s t r yf 7 1 系统中，每个结点存储数值上最接近的键( 键空间为环) 。 邻居由叶集( 1 e a fs e t ) l 组成，l 是个数值上最接近的结点的集合。通 过叶集可获得正确但低效的路由。为了获得更高效的路由，p a s t r y 也使用 了p r r 路由机制。为每个结点维护一个邻居集，路由将查询转发到与待查 找的键具有最长公共前缀的结点( 若有多个这样的结点，则转发到与键数 值上最近的结点) 。在p a s t r y 中，每个结点有o ( 1 0 9 n ) 个邻居，路由长度 最多为o ( 1 0 9 n 1 。 a m p t e r2 对等网资源定位和路由算法综述 f i n g l e t a b l e o fn 2 0 n 2 0 + ln 2 4 n 2 0 + 2n 2 4 n 2 0 + 4 n 2 4 n 2 0 + 8n 3 2 n 2 0 + 1 6n 4 3 n 2 0 + 3 2n 5 5 ( a ) 在c h o r d 环中，键( b ) 结点n 2 0 的路由表 存储在后继结点上 2 1 4c h o r d 图2 2 ：c h o r d 环与结点的路由表 1 3 c h o r df 6 1 使用一致哈希技术 2 3 】对结点和键分配标志符。结点的标志符 通过哈希i p 地址，而键的标志符通过哈希键得到。选择足够大的标志 符长度m 使得两个结点或键哈希到相同值的概率是可忽略的。标志符 表示为1 n 2 m 一1 间的数，在一维环空间( 模2 ”) 上由小到大按顺时针 排列。键k 存储在与其相等或顺时针方向第一个跟着k 的结点上，该结 点称为键k 的后继，表示为s u c c e s s o r ( k ) 。如图2 2 ( a ) 所示，图中有8 个结 点，5 个键，m = 6 。标志符为1 1 的键的后继为结点n 2 0 ，故键k l l 存储在 结点n 2 0 上。同样，键k 2 3 存储在结点n 2 8 上，键k 3 6 存储在结点n 4 3 上， 键k 5 8 和k 6 2 存储在结点n 1 上。 每个结点维护两个邻居列表：一个为后继列表，用以存放环空间上 后继于它的结点，路由的正确性可由这种列表获得；为了提高效率，每 个结点还维护一个指针表( f i n g e rt a b l e ) 。若键结点的标志符位数为m ， 每个结点的指针表