（计算机软件与理论专业论文）基于kademlia的p2p分层资源定位模型.pdf

摘要 摘要 近年浓p 2 p 研究升温，而资源定位是p 2 p 网络研究中的热点问题。目前，最 受磅变卷们关注戆是鏊予d i t t ( 分蠢式啥希裘) 黪缭构化定位模型。d h t 鼹逢 簿 法茨蔼分布式赊蘩委荻逶覃亍姿滚是燕，捷速、爵扩鬣瞧葑。纛是d h t 方法只支持 关键字的精确查找，而不考虑节点的物理位置，数据没有进行本地化，效率受到 限制。舆型的d h t 模型瓴括：c h o r d 、p a s t r y 、c a n 积k a d e m l i a 簿。 零文在k a d e m l a 模型斡菱磷上，提出了一嵇麓次 皂的p 2 p 模壅。该系统分 为三层：服务提供层、越缀节点层釉注册服务器麟，其中搬务掇供层和超级节点 层都用k a d e m l i a 协议进行资源定位。越级节点层由超级节点构成，超级节点怒山 注臻e 匿务嚣搬摆繁点瓣熊力谭售撂建产生魏。服务提供层 墼饕避节点掏或，罄干 个蓄遂节点被巅分袋一个蠛。骜逶节患哭爱在蠛海豢诲资灏，当藩运节点囊询资 源失败时，内超级节点帮助，在整个越级节点层中焱找相关资源。使用这个模型， 充分和闷丁焱询和数掇的时间空间局部性，资源定位速度快，数据传输效率离。 曩绫篌露p t a n e t s i m 平台稻j a v a 避 亍蕊囊，设计篱攀，可扩曩注好。并绘 出了和k a d e m i i a 模型的仿真比较。 关键词：p 2 p ，d h t ，k a d e m l i a ，分层模型、资源定位 a b s l 姒( 了 a 8 s t r a c t p 2 pn e t w o r kh a sb e e nb e c o m i n gah e a t e dt o p i cd r a m a t i c a l l yi nr e c e n ty e a r s r e s o u r c e sl o c a t i n gi so n eo ft h ek e yi s s u eo fp 2 pn e t w o r ka n dr e s e a r c h d h t - b a s e d d e c e n t r a l i z e ds t r u c t r u em o d l eh a sb e c o m eaf o c u si nt h er e s e a r c ha r e a + d h t - b a s e d m e t h o d se n j o yg r e a ta d v a n t a g e so fs i m p l i c i t ya n de x t e n s i b i l i t y h o w e v e r , s i n c et h ek e y w o r ds p a c ei si s o l a t e df r o mt h er e a lp h y s i c a ln e t w o r k ，t h em e t h o dw i l ld i s t u r bt h ed a t a l o c a l i t y a sar e s u l t ，w h i l et h eq u e r yl a t e n c yi sh i 曲，t h ed a t ad o w n l o a d i n gs p e e di st o w 。 t y p i c a ld h t - b a s e ds y s t e m si n c l u d ec h o r d ，p a s t r y , c a na n d k a d e m l i a t h i sp a p e rp r e s e n t sah i e r a r c h i c a lp 2 pl o c a t i n gm o d eb a s e do nk a d e m l i a t h i ss y s t e mc o n s i s t s r e s o u r c e s p r o v i d e l a y e r , s u p e r - n o d e l a y e r a n dr e g i s t e r - s e r v e r - l a y e r r e s o u r c e s p r o v i d e l a y e ra n d s u p e r - n o d e - l a y e rb o t h u s ek a d e m l i at ol o c a t er e s o u r c e s + t h es u p e r - n o d e - l a y e rc o n s i s t s o f s u p e r - n o d e s w h i c h a r ee v a l u a t e d b yr e g e s t e r s e r v e r a c c o r d i n g t ot h e i r c a p a b i l i t i e s t h e r e s o u r c e s p r o v i d e l a y e ri sc o n s t i t u t e do fb yh e m a l n o d e s s e v e r a ln o m a r l n o d e sc o n s t i t u t ead o m a i n - n o r m a l n o d e sc a no n l yl o c a t er e s o u r c e si ni t so w nd o m a i n + w h e nt h ec o n i co fan o r m a l - n o d e l o c a t i n gr e s o u r c e si ni t sd o m a i nf a i l e d ，i tc a nb eh e l p e db yt h es u m p e r - n o d et ol o o ku pr e s o u r c e si n s u p e v n o d e - l a y e f f o rt h eb e n e f i to fh i g he f f i c i e n yi nd a t al o c a t i n ga n dt r a n s p o r t i n g ，p h y s i c a l l yc l o s e n o d e sa r ed i s t r i b u t e di n t ot h es a m ed o m a i na n do u t s i d er e s o u r c e sa r er e - d i s c h a r g e di nt h el o c a l d o m a i na f t e rb e i n gd o w n l o a d e df r o mo t h e rd o m a i n t h es i m u l a t o ro ft h es y s t e mi nt h i sp a p e ri sb a s e do np l a n e t s i mp l a t f o r ma n dj a v a i nt h ee n do f t h ep a p e rw ep r o v i d et h ec o m p a r i s o no fc a p a c i t i e sb e t w e e nt h em o d e lo ft h i sp a p e ra n dk a d e m l i a k e y w o r d ：p 2 p , d h t , k a d e m l i a ，h i e r a r c h y - b a s e dm o d e l ，r e s o u r c e sl o c a t i n g l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名- _ 凌缝日期：2 d o i 年f 月f 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：凌缱 导师签名丝 日期：聊年参月彳日 1 1课题背景和研究意义 第一章引言 p 2 p 9 5 技术起源予互联网应爱爨旱嬲。虽然p 2 p 这个术语是瑷在方发爨憋，讴 p 2 p 本身的蒸本技术豹存在时闻却至少和u s e n e t 、f i d o n e t 这两种非常成功豹分布 式对等网络技术一样长。 u s e n e t 产生于1 9 7 9 年，是一种分靠式系统，能够为各个地方提供新闻鳃。 u s e n e t 最早蘸形是宙薄窝綦暑究生t o mt r u s c o t t 帮j i me l l i s 实戮豹。当时著没有 互联网上“随选”信息的概念，文件只能通过电话线路批量传送，且常常选在长 途费用比较低的夜间进行。因此，当时的u s e n e t 若聚用集中式管理方法，效率将 晓较低下，囊然瑟然弱辘提出了一静分数、分毒式瓣管理方法。遮秘分布豹缀稳 一直沿用刘今天。早期p 2 p 应用另一个杰出的代表靛是f i d o n e t ，它和u s e n e t 类 似，也是一个分散、分布的信息交换系统。t o mj e n n i n g s 于1 9 8 4 年创建了f i d o n e t 系统，来让不同b b s 系统中的用户互榍交换信息。这种符合人们濡要的技术，迅 速成长莛来，并一壹治曩j 到今天。 2 0 0 0 年，p 2 p 又一次成为业界的焦点。p 2 p 是网络计算的一种新技术，这种技 术的目的是将网络中不同计算机连接在一起，并充分利用互联网和w e b 站点中任 德阕置资澈。p 2 p 号穆羹鸯裁等弱予爨终，蓑零语s e r v e n t s ( s e r v e r + e l i e n t ) 羹三 伴随着网络计算领域的新机遇出现在我们面前，网络计算领域内某些因素的演变 正成为促使p 2 p 技术发展的源动力，p 2 p 正在改变互联网中各成爨问的能力平街。 p 2 p 技术馒棱成互联网的大多数计算机瓣能力锝到发震。只有在今天，我们强调的 才不是个浚，两是各种诗算设备之阍静平等。 所谓p 2 p 模型，是指个网络系统，在其中每个节点都具有同等的能力和贵任， 所有的通讯都是对称的。p 2 p 模型将计辣均衡分布在每个节点，使得一个任务怒由 多夺节点共溺完残熬，苓患可戮垂篷黪燕入或遥窭溺终系统，熬蟀谤筹戆力黢逶 应网络规模的变化。 p 2 p 系统的负载均衡策略让系统中的节点均衡地承担系统负载；它的自组织的 系统维护缀曝，能够及时准确地探测列动态瘸络中麴变讫，著进行媚应踌由镰爨 的调整和上鼷应用程序鞫关数据瀚调熬。因此，p 2 p 系统是一种可扩展、自组织的 电子科技大学预二k 学位论文 分布式系统。最重要的是p 2 p 系统通过科学的组织路由信息，使节点在掌握局部 路由信息的情况下就能够取得高效的全局路由的功能。这一点对p 2 p 系统的可扩 展性做出了决定性的影响。 p 2 p 在互联网中的应用已非一朝一夕，经过最早的p 2 p 系统雏形u s e n e t 、 f i d o n e t 等分布式信息共享软件到以n a p s t e r “、g n u t e l l a 1 和f r e e n e t 为代表的 无结构p 2 p 文件存储系统，再到现在主流的以d h t 为基础的结构化p 2 p 。文件存储 系统c f s i t t l 、p a s t 和o c e a n s t o r e ，以及目前最流行的k a z a a 、b i t t o r r e n t 、s k y p e 等p 2 p 系统。p 2 p 系统己经在不同的应用范围逐渐发展侧重点不同的分布式技术， 将给信息社会带来不可估量的信息财富。 在过去的一年时间里，p 2 p 系统正迅速成为计算机业界关注的热门话题，i n t e l 公司还发起成立了包括微软、s l l n 和h p 等大公司在内的p 2 p 工作组，以推动p 2 p 进一步发展，财富杂志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一。 1 2 国内外研究动态 1 2 1p 2 p 对等网络的定义 p 2 p 。3 即是p e e rt op e e r 的缩写，称为对等连接或对等网络。p 2 p 是一种分布 式网络，其中的参与者共享他们所拥有的一部分硬件资源( 处理能力、存储能力、 网络连接能力、打印机) ，这些共享资源需要由网络提供服务和内容，能被其 他p e e r 直接访问而无需经过中间实体。在次网络中参与者既是资源( 服务和内容) 提供着，又是资源( 服务和内容) 获取者。 目前，业界对p 2 p 的定义还没有一个标准的说法。 i n t e l 将p 2 p 计算定义为“通过系统间的直接交换所达成的计算机资源与信息 的共享”，这些资源与服务包括信息交换、处理器时钟、缓存和磁盘空间等。 r o k ut e c h n o l o g i e s 公司将p 2 p 定义成“使个人与个人之间直接通信成为可能 且更便捷的网络结构”。 为了更好的理解p 2 p 网络，i b m 为p 2 p 做了如下定义：p 2 p 系统由若干互联协 作的计算机构成。且至少具有如下特征之一：系统依存于边缘化( 非中央式服务 器) 设备的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益； 系统中成员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的 2 塑二至! ! 童 存在，构戏一个虚叛躐实际的群 零。p 2 p 网络愁互联网整体絮梅的基础，互联网最 基率的t c p i p 协议并没有客户端和服务器的概念，在通信过程中，所有豹设备都 是平等的一端。 。2 。2p 2 p 弱终戆努樊 1 2 2 1 按网络结构分类 擞援是否有中央交务器嘲，可将p 2 p 羁络分为混合式、分数式帮畜怒缀节点豹 p 2 p 网络。 混合式p 2 p 网络的中央服务嚣只是索引服务器，与c s 模式中的服务器不同， p 2 p 嬲终中懿素善| 黢务器灵遗录内容戆索弓l 翥节点懿必要售慧，辘韵节点之瓣建立 连接，而内容本身存储在节点中，内容的传送只在节点之间进行，不通过服务器。 如n a p s t e r 、b t 、e d o n k e y 、e i u l e 、q q 等。混合式p 2 p 网络的拓扑结构如图1 1 所示。 p e e x 2 圈l 。l ：濑会式p 2 p 匏潮络李五羚结鞠 分散式p 2 p 网络没有服务器，通过基于p 2 p 仂- 议的客户端软件搜索网络中存 在的对等节点，节点之间可直接建立连接，每个节点都是完全平等的，如 g n u e l l 0 瑚。分觳式p 2 p 夔弱终臻癸结稳魏舀l + 2 襞示。 l b 子科技大学硕一i 二学位论文 p e e r 图l 2 ：分散式p 2 p 的网络拓扑结构 有超级节点的p 2 p 网络中，有着高网速( 特别是很高的上行速率) 和高性能的 计算机被自动设置为超级节点。超级节点作为其它用户的索引服务器。随着节点 的频繁加入和退出，超级节点有着很大的动态性，如f a s t t r a c k 。有超级节点的 p 2 p 的网络拓扑结构如图1 3 所示。 s n ：超级节点 图1 3 ：带超级节点p 2 p 的网络拓扑结构 1 2 2 2 按照内容与网络拓扑结构的关系分类 根据网络中存储的内容与网络拓扑结构是否相关，可将p 2 p 网络分为结构化、 4 剃缛嚣 图2 1 ：d h t 技术的基本概念 基于d h t 分布式h a s h 表技术是与应用无关的技术；因为d h t 层单独加入在 应用层和下层通信层之间，可以不考虑具体的应用，只利用d h t 层负责上层数据 和下层通信节点之间查询和插k 1 8 。利用h a s h 函数得到的关键字并不能反映数据 的含义，具体关键字的产生，又完全取决于应用层的开发者。 d h t 作为应用层的接口如图2 2 。d h t 系统基本的操作就是l o o k u p ( k e y l 。 由于系统中的每一个节点负责存储一定范围的关键字，通过l o o k u p ( k e y ) 操作返回 一个存储该关键字节点的节点标识符( n o d e l d ) ，这个操作允许节点根据关键字进 行存储( p u t ) 和读取( g e t ) 。通过d h t 层的l o o k u p ( k e y ) 操作，可以把应用层的 数据均匀分布在网络的各个节点内，这种方法使下层网络完全不中心控制。 应用层 ；e r t ( k e y , d a t a ) ll o o k u p ( k e y ) fl p 盯层 图2 2 ：d h t 层的操作 d h t 作为应用层接口不仅简单，而且与传统的应用层接口相比还具有更多的 优点如表2 1 。传统应用曾接口u d p i p 是以通信为中心的接口，一定要具体指出 要查找和发送数据的节点i p 地址。由于现在的i n t e m e t 过分依赖d n s 是网关，只 要其中有一个服务出现“问题”，相应的其他任何服务就无法获得。d h t 是以数据 l b 予科投火学硕士学位论文 为中心的犊日，只要给出与数据礁一对应翡k e y 辘可以送苻资源查找，著不需要 关心数据恩体存放在哪个节点上和熟有数据来自哪个应用。 d h t 应掰磊接叠u d p i p 痊稻瑶接墨 l o o k u p ( k e 灿d a t a s e n d ( pa d d r e s s ，d a t a ) i n s e r t ( k e y , d a t a ) r e c e l v e ( i pa d d r e s s ) + d a t a 表2 1 ：d h t 应用层按口和u d p i p 应用层接口的比较 d h t 是一个好的共享下层设施，由于d h t 使用资源名字不必再编码成位置 或鼹出链鼹，这撑形裁一个统一懿鏊予蓖骞鲍命名层，堪热了寻技对象的灵灞性。 由于d h t 是一个均衡的体系结构，可以提供多种选择用语考虑在哪些节点空间存 放对象( 和副本) 和用哪一条路径哿找存放对象( 副本) 来确保应用层的安全。 基于d h t 基础结构是翻缓和自治的，所阻不需人们事先预见额外操作，这样就降 低了藏符，维护和管遴豹代徐。使阕d h t 接零镶一个实薅并不躲道它要缳存纾么 样的数据，因此所有实体必须能够志愿的提供p c 资源，网络带宽并且能够按受任 何类型的数据。 2 2几种通用的d h t 资源定位的路由模烈 2 2 。1 c h o r d 路由摸数 2 , 2 1 1c h o r d 简介 c h o r d f a l 是由i o ns t o i c a 等人设计的一稃较麓薄豹结秘讫p 2 p 搜索策暗。它静 设计目标是提供一个分布式、负载均衡的、可扩展的p 2 p 搜索策略，解决瞬前由 中心控制的搜索策略带来的扩展性能差、负载均襁差等限制问题。 c h o r d 系襞蠹，餐一令节点逶避菜啥幕函数( 运鬻是s h a - 1 ) 诗雾窭漆戆 m 位的标示符( n o d ei d ) ，标识该节点在c h o r d 系统中的位置。当c h o r d 需要路 由某一消息时，该消息也用哈希函数计算出消息k e y 值。消息的目标节点就是n o d e l d 大于或磐等于港息k e y 焦鲍节点中n o d et d 最小熬一个，梵警点称为这个瀵怠 的后继节点( s u c c e s s o r ) 。 螭二章纂于d h tt l , o 资源定位方法 在d h t 技术中，两络结点按照一定静方式分配个难一n o d ei d ，资源对象 通过敝列运算产生一个唯一的资源标识符( o b j e c t1 d ) ，且浚资源将存储在结点l d 与之相等或者相j 黩的结点上。濡要查找浚资源时，采用同样的方法可定位到存储 该资源豹结点。瓣诧，c h o r d 瓣主要贡敷是撬壅了一令分布式查我蛰议，浚协议可 将指定的关键字( k e y ) 映射到对应的结点。从算法来髫，c h o r d 是捆容散列算法 的变体。 2 2 。 + 2 稆窑哈莽 c h o r d 实现了这样一种操作，给定一个关键字( k e y ) ，将k e y 映射到某个结 点。如果给对等劂络应用的每个数据都分配一个k e y ，那么对等网络中的数据查找 蠡题簸可戮矮c h o r d 缀容荔蠢绥凌了。 c h o r d 采用了相容哈希的一种变体为结点分配关键字。相容哈希c 1 7 1 有几个很 好的特点，首先魁哈希函数可以做到负载平衡，也就是蜕所有的结点可以接收到 基本楣霹数量的关键字。另羚，当第n 令终点热入或者襄开网络时，只套1 n 蛉 关键字需要移动剿另外的位置。 c h o r d 进一步改善了相容哈希的可扩展性。在c h o r d 中，结点并不需要知道 所有其他结点的信息。每个c h o r d 结点只需要知道关于其他结点的少羹的路由信 惑。焱鑫n 令缮点缝戒熬弼终中，每令结煮哭嚣要维护葵纯o ( 1 0 9 n ) 令结点熬 信息，同样，每次查找只需要0 ( 1 0 9 n ) 馨消息。当结点加入或者离开网络时， c h o r d 需要更新路内信息，每次加入或者离开需要传递0 ( 1 0 9 2 n ) 条消息。 耀容啥希邈数为每个结感稻关键字分聚1 2 ：1 位豁舔识笱，此栋谈雩李可戳爆 s h a - 1 等晗希函数产生。结点的标识符可班通过哈希结点酌i p 地址产生，丽关键 字的标识符可以盥接哈希此关键字。比如1 p 地址为1 9 8 1 0 1 0 1 的结点缀过s h a 1 哈希之后得到的标识符为1 2 3 ，而关键字“l e t l t b e ”哈希之籍的关键字为6 0 。标识 瓮长波m 毖须是够长，这样才麓镶证两令缭点或者关键字啥希到蠢一个标识幸奇上 的概率小到可以忽略不计。从圈2 3 中可以赣出相容哈希的特点。 乜干科技大学1 4 - i ：学位论文 图2 3 相容哈希示例 在相容哈希中，每个关键字都保存在它的s u c c e s s o r 结点中，s u c c e s s o r 结点 是结点标识符大于等于关键字k 标识符的第一个结点，我们将其记为s u c c e s s o r ( k ) 。 由于关键字“l e t l t b e ”的标识符为6 0 ，因此它被保存在9 0 结点中。如果标识符采用 m 位二进制数表示，并且将从0 到2 ”1 的数排列成一个圆圈，那么s u c c e s s o r ( 1 【) 就 是从k 丌始顺时针方向距离最近的结点。这一点，可以从图2 3 中很清楚地得出。 相容哈希的一个特点就是当结点加入或者离开网络时对网络带来的冲击可以 达到最小。当结点n 加入网络时，为了保持相容哈希映射，某些原来分配给n 的 后继结点的关键字将分配给n 。当结点n 离开网络时，所有分配给它的关键字将重 新分配给n 的后继结点。除此之外，网络中不会发生其他的变化。以图2 3 为例， 当结点n 9 0 离开网络时，关键字“l e t l t b e ”将被分配给结点n 1 2 3 。 2 2 1 3 路由查找策略 在c h o r d 中，每个结点维护少量的路由信息，通过这些路由信息，可以提高 查询的效率。如果m 是关键字和结点标识符的位数( 采用二进制表示) ，那么每个 结点只需要维护一张最多m 个表项的路由表，我们称之为指针表( f i n g e rt a b l e ) 。 结点n 的查找表的第i 个表项包括的是s = s u c c e s s f n + 2 i 一1 ) ，这里1 = i ( = m 并且所有 的计算都要进行m o d2 m ，s 称为结点n 的第i 个指针，我们用n f i n g e r i n o d e 表示， 指针表中的其他项的含义如表2 2 所示。 1 4 第二章基于d h t 的资源定位方法 符号定义 f i n g e r k s t a r t ( n + 2 k 。1 ) m o d 2 m ，1 = k = m i n t e r v a l f i n g e r k s t a r t ，f i n g e r k + s t a r t 】 n o d e 第一个大于等于i 1 f i n g e r k s t a r t 的节点 s u c c e s s o r 标示符环中的下一个节点：f i n g e r i n o d e p r e d e c e s s o r 标示环中的前一个节点 表2 2c h o r d 中指针表项含义 以图2 3 为例，结点1 的指针表的表项应该分别指向标识符f l + 2 0 ) r n o d2 3 = 2 ，f 1 + 2 1 ) m o d2 3 = 3 ，f 1 + 2 2 ) r o o d2 3 = 5 。而标识符2 的后继是结点3 ，因为它 是2 之后的第一个结点，标识符3 的后继是结点3 ，而标识符5 的后继是结点0 。 这一方案有两个重要的特性：首先，每个结点都只需要知道一部分结点的信 息，而且离它越近的结点，它就知道越多的信息。其次，每个结点的指针表通常 并不包括足够的信息可以确定任意一个关键字的位置。例如，图2 3 中的结点3 就 不知道关键字1 的位置，因为1 的后继结点信息并没有包含在结点3 的指针表中。 当结点1 1 不知道关键字k 的后继结点时怎么办? 如果n 能够找到一个结点， 这个结点的标识符更接近k ，那么这个结点将会知道该关键字的更多信息。根据这 一特性，n 将查找它的指针表，找到结点标识符大于k 的第一个结点j ，并询问结 点j ，看j 是否知道哪个结点更靠近k 。通过重复这个过程，n 最终将会知道k 的后 继结点。 仍然考虑图2 3 中的例子，结点3 需要查找关键字1 的后继结点。由于1 属 于循环区间【7 ，3 ，它属于3 f i n g e r 3 i n t e r v a l ，因此结点3 查找其指针表的第3 项， 返回o 。由于0 在1 之前，因此结点3 将要求0 去寻找关键字1 的后继结点。依此 类推，结点0 将查找它的指针表并发现1 的后继结点是1 本身，于是结点o 将告 诉结点3 结点1 是它要找的结点。 b 予科技火学硕士学位论文 图2 4 c h o r d 数据组织实例 节点的加入 结点n 豹翔入分为三个除段。 初始化新结点的指针液。假设结点n 在加入网络之前通过菜种机制知道网络 中的某个绪点n t 。这时，为了初始化n 的指针表，n 将要求结点n 为它查找指针衷 中懿葜缝表项。 更新现有其他结点| 询指针表。结点加入网络后将调用其他结点的更新函数， 让其他结点魇新其指针袭。 从后继镰点把关键字使递到结点n 。这一步是撅藏有后继缝点是n 的关键字 转移到n 上。整个加入操作的时阕复杂度是0 ( 1 0 醇n ) ，如果采潮疆复杂匏算法嘲， 可以把复杂艘降低到0 ( 1 0 9 n ) 。 2 , 2 。1 4 节纛的退出 在对等网络中，菜个对等结点随时可能退出系统或者发生失效，因此处理结 点失效是一个重要的问题。在c h o r d 中，当结点i 失效h , j ，所以在指针表中包括n 豹结点都必须把n 替换成n 的后继结点。另井，结点i 蛉失效不能影响系统中正 在进彳亍的鲞询过程。 第二章幕于d h t 的资源定位方法 在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点，每个 c h o r d 结点都维护一张包括r 个最近后继的后继列表。如果结点n 注意到它的后继 结点失效了，它就用后继列表中第一个正常结点替换失效结点。 2 2 2c a n 路由模型 2 9 2 1c a n 的简介 c a n 可以在 n t e r n e t 规模的大型对等网络上提供类似哈希表的功能。c a n 具 有可扩展、容错和完全自组织等特点。c a n 6 】类似于一张大哈希表，基本操作包括 插入、查找和删除。c a n 由大量自治的结点组成，每个结点保存哈希表的一部分， 称为一个区。c a n 的设计完全是分布式的，不需要任何形式的中央控制点。c a n 具有很好的可扩展性，结点只需要维护少量的控制状态而且状态数量独立于系统 中的结点数量。c a n 支持容错特性，结点可以绕过错误结点进行路由。 2 2 2 2c a n 的路由策略 c a n 使用了一个d 维直角坐标系空间来执行d h t 抽象。这个坐标空间被超 矩形划分，成为区域( z o n e ) 。每个在坐标系统的节点负责一个区域( z o n e ) ，每个 节点由它区域( z o n e ) 边界来标识。一个关键字映射到指教坐标系上的一点，坐标 系点对应一个区域，将关键字存储在负责这个区域的节点内。如图2 5 表示了2 维 0 ，1 1 * f 0 ，1 1 的c a n ，其中该系统有6 个节点。每个节点维持它在坐标系中所有 邻居的一个路由表。如果两个节点的区域共享d - 1 维超平面，则这两个节点是邻居。 ( 0 ，1 ) ( 0 ，0 5 ，0 5 ，1 ) ( 0 5 ，0 5 ，1 ，1 ) ( 叭2 5 咒7 5 ，0 5 ) ( 0 ，0 ，0 5 ，0 5 ) r 0 7 5 ，0 ， ( 05 o ，o7 5 ，02 5 ) 1 ，0 5 ) 0 ) 图2 5 ：c a n 系统巾的节点 查询操作通过在d 维直角坐标系空间中转发查询消息被执行，转发是从查询 u 予科技人学砸= l 学位论文 初始化点沿着坐标系上最接近直线的路径到达存储关键字的节点。当收到一个查 询请求，一个节点转发请求到与存储关键字节点在坐标系中最接近的节点上，图 2 6 表明找寻关键字( o 8 ，o 9 ) 的路径。每个节点维护o ( d ) 个状态，查询代价 是o ( d n l d ) 。如果d = o ( 1 c - g n ) ，c a n 查询次数和存储可以和在本文所介绍的其 他协议相匹配。 k e y = ( 0 8 ，0 9 、 ( 0 ，1 ) n o d e ( 0 ，7 5 ，0 7 5 ，1 ，1 ) ( 1 ，1 ) j 一 l ( 0 ，o ) 初始于n o d e ( 0 ，0 ，0 5 ，0 5 ) 查找( 0 8 ，o 9 ) 的路径 ( 1 ，0 ) 图2 6 ：c a n 路由模型的路由过程 c a n 系统中，一个减少查询时延的技术是多实现技术。用户位于多哥坐标空 间同时参与查询来减少时延和提高c a n 的健壮性。每个节点在每个坐标空间被分 配一个不同的区域。关键字在每个坐标空间被复制，提高节点失效时系统的强壮 性。为了转发消息，节点检验在每个空间实际存在的邻居节点并且转发消息到离 本节点最近的邻居节点。 2 223c a n 网络中新节点的加入和退出 为了加入c a n 网络，一个新的节点首先在坐标空间中选择一个随机点p ，找 到包含随机点新加入节点，如图2 7 。新加入节点可以很容易的初始化其路由表， 因为和它相邻的所有节点除了n 节点之外，都在1 1 节点的邻居表中。这也允许邻 居用新节点更新路由表。 第二章赫于d h t 的资源定位方法 ( 0 ，1 )( 1 ，1 )( 0 1 )( 0 ，1 ) 刚弘点。 随机点p 节点n 新氛 图2 ，7 ：新= 苘点加入c a n 系统 当一个节点离开时，这个节点上交它的区域给它的邻居。如果两个区域能合 并成一个大的区域，则产生一个新的有效区域。如果两个区域不能合并，那么邻 居节点就会暂时处理两个区域。当一个节点失效时，c a n 会执行一个协议允许拥 有最小区域的邻居来接管这个区域。c a n 系统潜在的问题就是多点失效会导致一 个坐标空间的分裂，由多个节点处理多个区域，区域越分越多，越分越小。为了 解决这个问题，c a n 执行一个特别的重分配节点( n o d e r e a s s i g n m e n t ) 算法。该算 法能够尽量将多个可以合并的区域分配到c a n 系统中一个合法的节点上，来联合 使用这些区域。 2 2 3 p a s t r y 路由模型 2 2 3 1 p a s t r y 简介 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构 建大规模的p 2 p 系统。在p a s t r y 中，每个结点分配一个1 2 8 位的n o d ei d ，所有的 结点标识符形成了一个环形的n o d ei d 空间，范围从0 到2 1 2 8 1 ，结点加入系统 时通过散列结点i p 地址在1 2 8 位n o d ei d 空间中随机分配。 p a s t r y 4 】提供了下面的功能。p a s t r y 网络中的每个结点都有一个唯一的n o d e i d 。当给定一条消息和一个关键字时，p a s t r y 结点将会把这条消息路由到在当前所 有的p a s t r y 结点中n o d ei d 和关键字最接近的那个结点。路由过程的复杂度是o ( 1 0 9 n ) ，这里n 表示网络中p a s t r y 结点的总数。p a s t r y 考虑了网络的位置信息， 它的目标是使消息传递的距离最短。距离采用类似于i p 路由的跳数的标量距离度 量。每个p a s t r y 结点记录在结点空间中和它直接相邻的邻居结点，当新结点加入、 1 9 电子科按大学颀l ：学短途文 原有结点失效和恢复时通知上层应用。幽于结点号怒随机分配的，那么在结点空 间中相邻的结点很可能在地理位置上是分散的，或者根本就属于不同的组织。应 用可以剥用这点，因为p a s t r y 可以把关键字路出到秘它最接近赡k 个结点中鑫毫 任何一个，p a s t r y 采嗣了稿发式算法可以键关键字首先潞出至l 在结点空闼中署消息 产生的结点距离最近的包括查找关键字的结点。 2 2 3 ，2p a s t r y 系统的组成 p a s t r y 系统是由独立的p a s t r y 结点缀成的自组织的o v e r l a yn e t w o r k ，每个结点 都可以路由客户请求并和成用程序( 可以是多个) 的本地实例进行交互。任何 台连接到i n t e r n e t 的计算枫只要运行p a s t r y 结点软件就可以称为p a s t r y 结点，当然， 它需要满是应用定义静安全策略。 p a s t r y 系统中的每个络点都被分配一个1 2 8 位的绪点号。结点号用于在结点 空间中标识绪点豹位置。结点号是在结点加入系统时髓机分配的。分配策略是在 维点空阕中秘匀分蠢。缝点号霹戮逶遵诗纂结点公钥残誊l p 建缝懿泠豢丞鼗蕊寒 获得。由于采用了均匀分布，因此结点标识相邻的结点处于不同的地理位置的概 察很大。 缓定嗣终幽n 个结点缀成，p a s t r y 可以把一个绘定的关键字路由到扶标识符 来看最接近静缩点，在正鬻绦作条件下，路由豹步数小于l 0 9 2 b n 的上取整，这麓 b 是一个配置参数，典型取德是4 ，即使同时发生结点失效的情况，也可以保证关 键字送达目标缭点。 为了遴纾鼹由，我们撼缮点号蠢关键字表示为一率以弱为鏊懿数。p a s t r y 把 消息路由到结点号从数值上最接近关键字的结点。具体过程如下：在每个路由步 骤中，当前结点将把消息路由给结点号和消息关键字的共同前缀长度至少比当附 镶长一个数经( 也就是b 个二进铡位) 躲结点。如鬃不存在这样黪结点，消息褥 传递给前缀长度相嗣毽是缩点号数值燹接近关键字的绣点。为了支持这样的路囱 过程，每个结点必须维护一定的路由状态。 每个p a s t r y 结点都需鼹维护一张路出表，一个邻羼结点集合和一个叶子结点 集会。路耄袋爨l 0 9 2 b n 豹上酝整孑缝残，每行包菇2 b ，1 令表顼。第n 李亍熬2 b 1 个表项分别指向前n 个数位和当前结点的前n 个数位相同，而第n + 1 个数位取趟 2 b 一1 的可能的假( 要除掉当前结点第n + 1 的值) 。当b 取4 ，而网络中有1 0 6 个 戆点时，每个终点豹路由表乎均雹括7 5 个表项曩l i 预矮豹路由步数懋5 。纛鲡暴瓣 络中有1 0 9 个缩点，路由表的平均表项将为1 0 5 项，丽预期韵路由步数将增加到7 。 韬二章堆- j id h t 的资源定位订沾 邻居结点集合龟括距离当露结点最近昀结t i 魄撂淤雩弩硼1 p 遗址。邻詹鲮点集翕在 正常的路出操作对是用不到的，它的主要作用是维护路幽弱位霞属性。竹子结意 褒合中存放的是和当前结点的标u 符从数随上看最接近的结点，姒：巾一半足结点 号大予当l 狐络点的，另半是结点弓小于当锄。结点的。叶予结点集合在消息路由 时需要雳劐。般束浣，这两个集合的大j 、为2 b 或者2 b + i 。 n o d ed1 u z 3 3 1 0 z r 叶子节点羹岱 s m a l l e r l a r g e r 0 2 3 3 0 3 31 0 2 3 3 0 2 1 0 2 3 3 1 2 0 0 2 3 3 2 2 0 2 3 3 0 0 11 0 2 3 3 0 0 0 10 2 3 3 2 3 01 0 2 3 3 2 3 2 路由表 一0 - 2 2 1 2 1 0 2 溪瓣翘瓣蒸溺 一2 2 3 0 12 0 3- 3 - i2 0 3 2 0 3 燧躐卜1 3 0 1 2 3 3 一2 2 3 0 2 0 3t - 3 0 2 t 0 2 2 0 - 0 - 3 t2 0 31 0 - 1 - 3 2 1 0 2；i 寰蔓囊毒未墓? 翻1 0 一3 2 3 3 0 2 0 2 - 0 0 2 3 01 0 2 - t - 1 3 0 2 10 2 - 2 - 2 3 0 2一。j 痞j 3 嚣jj l 0 2 3 - 0 - 3 2 21 0 2 3 - 1 - 0 0 0 1 0 2 3 2 1 2 1 麟雩琴国霉薯鞠 1 0 2 3 3 - 0 - 0 1 鼷释鬻l 瓣勰1 0 2 3 3 2 3 2 鬻鬻矮冀窝 t 0 2 3 3 t 一2 0 ； 誉辫i 鬻蘧 邻居节点繁合 1 3 0 2 1 0 2 21 0 2 0 0 2 3 01t 3 0 1 2 3 33 2 3 0 1 2 3 3 8 2 2 谨 8 22 2 3 0 1 2 0 33 i 2 0 3 2 0 33 3 2 3 3 2 嗣2 8p a s t r y ：仃点数据结构示惑陶 图2 8 怒p a s t r y 一个结点的数据结构示意幽】。结点号为1 0 2 3 3 1 0 2 ，b 取值为 2 ，所有的数均是4 进潮瓣。其中路由表数最上瑟一纷是第0 幸亍。这囱表；p 每约：拣 阴影项表示当前结点号对应的位。路幽表中每顶表示为“和1 0 2 3 3 1 0 2 的共同前缀 一f 数位一结点号的剩余位”。为了嗣r 起见，图中没有列出相关的i p 地址。 2 2 3 3p a s t r y 款路走篆戆 p a s t r y 的路由过程如下。当l j 父到一条消息明，结点首先检查消息、的关键字是 酉落在叶子结点集合中。如果是，则直接把消息转发给对应的结点，也就是叶子 结蕊集合中绪点号帮荚键字最接近熬绪点。魏栗关键字没有落尧n + 予慈，董集禽中， 那么就将使用路由表进行路由。当前结点将会把消息发送给结点弓和1 关键字赢接 的共同前缀至少比现在结点氐个数位的结点。肖然，在某些情况下，会出现路 由表对应表项为空，或营路由表表项对应的续点不可达。这网候消息将会被转发 l u 了科批火学砸。i 擘位论。逝 给共同嚣缀一样睦躲终点，但是该终点秘当懿缝点稳比，其终点号鼓数值上将更 接近关键字。这样的绪点一定位子时子结点集合中。因跣，只要叶予结点集合中 不会出现一半以上的结点同时失效，路由过程就可以继续。从上述过程中可以看 出，路出的每一步和上一步相比都向目标结点前潍了一步，因此这个过程怒收敛 豹。蚕2 9 是p a s t r y 查找鼯由钧一个示嬲。 銎2 9 ：节点2 5 副节点4 5 9 8 熬路出过稳如匿中耀线掰示。 2 2 3 4 带点的加入和遐出 缓定赣竞瑟入结点蕊结点号为x ( 缝点号懿分囊0 过程是由盛瑗程序凌定黪，臣 如可以对结点的i p 地蚍或者公钥进行s h a 一1 哈希得到结点号) ，x 在加入p a s t r v 之前，需羧知道一个相邻结点a 的位置信息。x 的加入过程主要包括初始化自己 蛉结点数摄维构并通知蒺他结点自己已经加入系统。 x 首先要求a 路函一条“龆入”消息，淆息静关键字就是x 的结点号。和其他 的消息一午芊，这条消息最终会到达具有和x 最接邋的结点号的结点z 。 作为响应，结点a 耜结点z ，以及从a 到z 的路径上的所有其他结点都会把 鸯己静数攥缭翰传绘x 。x 零j 嗣这登穰惫初稔纯鏊已豁鼗莛结构，初始纯完成螽， x 将通知藏他结点它已经加入了系统。x 的数据结构的具体构造过程不再详细描 述。按照消息数量来衡鬣，结点加入操作的复杂艘为o (