（计算机应用技术专业论文）基于kademlia协议的网络模型和路由的研究.pdf

西华大学硕士学位论文 基于k a d e m l i a 协议的网络模型和路由研究 计算机应用技术 研究生苏超指导教师刘克剑 近年来，随着计算机网络的发展，网络新技术不断涌现和发展，从最开 始的h m f l 卫s m t p 到后期的h t y p s ，w e b 2 0 ；从最初的客户机端服务 器模型到后来的p 2 p 网络模型。数据共享技术的进步和i n t e r a c t 的广泛使用， 使人们意识到充分合理利用网络数据将是网络发展的前进动力。 p 2 p 技术的主要特点在于充分利用分布在终端电脑上的边缘性网络资 源，包括计算资源、带宽资源、内容资源等，以降低对中央服务器资源的 消耗需求。如今，p 2 p 技术被越来越广泛地应用到网络应用程序中。d h t 是结构化p 2 p 网络广泛使用的技术，如c h o r d ，p a s t r y , c a n ，k a d c m l i a 等。近 年来，k a d c m l i a 协议以其稳定性、高效性和下载速度受到欢迎，很多文件 共享系统都是采用k a d c m l i a 协议实现。 本文首先给出了当前p 2 p 技术的发展背景，对p 2 p 技术和d h t 技术进 行分类介绍，随后对三种广泛应用的结构化p 2 p 协议c h o r d ，p a s t r y , k a d e m l i a ， 尤其是k a d e m l i a 进行了研究，分析了它们的模型结构，路由表结构以及路 由原理。针对k a d e m l i a 的缺点提出了一种带域结构的k a d e m l i a 网络- s c k a d 网络，该网络充分考虑了节点间的物理位置信息，完成了s c k a d 网络的路由 表设计，路由设计，发布资源机制设计等。最后，本文对一些仿真软件以 及当前应用较多的p 2 p 协议仿真软件进行了介绍，重点分析了o v e r s i m 仿 真的原理和框架，并在o v e r s i m 平台上完成了s c k a d 网络的实现和仿真， 最终对s c k a d 网络和k a d e m l i a 网络在o v e r s i m 上的仿真结果进行了比较， 根据仿真结果得出s c k a d 优于k a d e m l i a 的结论。 关键词：p 2 p 、k a d e m l i a 、d h t 、路由、网络模型 i 两华犬学硕+ 学位论文 t h er e s e a r c ho fd h tn e t w o r km o d e la n dr o u t i n g b a s e do nt h ek a d e m l i ap r o t o c o l c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m d c a n d i d a t e ：s u c h a os u p e r v i s o r ：l i uk e j i a n i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fn e t w o r k s ，n e wt e c h n o l o g i e sa r e e m e r g i n ga n da d v a n c i n go na n do n ：f r o mt h eb e g i n n i n go ft h eh 下r ef r 只 s m t pt ot h el a t eh t l v s ，w e b 2 0 ；f r o mt h eb e g i n n i n go ft h ec l i e n t s e r v e r m o d e lt ot h ep 2 ps t r a t e g y d a t a s h a r i n gt e c h n o l o g yi sf a s tc h a n g i n g , a n d i n t e r n e ti ss ow i d e l yu s e dt h a ne v e rb e f o r e ，a l lt h o s ec h a n g e sm a k ew e r e a l i z et h a th o wt oh a r n e s st h ed a t ai nt h en e t w o r ka d e q u a t e l ya n dr e a s o n a b l yi s t h ed r i v i n gf o r c ef o rt h en e t w o r k t h em a i nc h a r a c t e r i s t i c so fp 2 pt e c h n o l o g yi st ou t i l i z et h er e s o u r c e so fa p e r s o n a lc o m p u t e rl o c a t e di nt h ee d g eo f t h en e t w o r ka sf a ra sp o s s i b l e ，i n c l u d i n g c o m p u t i n gr e s o u r c e s ，b a n d w i d t hr e s o u r c e s ，c o n t e n tr e s o u r c e se t c ，a sw e l la st o r e d u c er e s o u r c e c o n s u m p t i o n f o rt h ec e n t r a l s e r v e r s n o w a d a y s ，p 2 p t e c h n o l o g i e sh a sb e e nw i d e l yu s e di nw e ba p p l i c a t i o n d h ti st h em o s tp o p u l a r t e c h n o l o g yi n t r o d u c e dt oc o n s t r u c tp 2 pn e t w o r k ss u c ha sc h o r d ，p a s t r y , c a n ， k a d e m l i aa n dn a m eaf e w m o s tf i l e s h a r i n gp 2 ps y s t e m sa r ei m p l e m e n t e db y t h ek a d e m l i ap r o t o c o lw h i c hh a st h ea d v a n t a g e so fh i g hs t a b i l i t y , e f f i c i e n c ya n d d o w n l o a d i n gs p e e d a tf i r s t ，t h i st h e s i sg i v e sao v e r v i e wo nt h ep 2 pa n dd h t t e c h n o l o g y t h e n ， d i s c u s s e st h r e ew i d e l yu s e dd h t - b a s e dp 2 pp r o t o c o l ：c h o r d ，p a s t r y , k a d e m l i a ， a n a l y z i n gt h e i rs t r u c t u r e s ，r o u t i n gt a b l e sa n dr o u t i n gs t r a t e g i e s b a s e do nt h e k a d e m l i a ，a n df o rt h ep u r p o s eo ft a k i n ga w a yi t ss h o r t c o m i n g s ，ad o m a i n 西华人学硕十学位论文 s t r u c t u r ek a d e m l i an e t w o r km o d e li sb r o u g h tf o r w a r dw h i c hi sn a m e da ss c k a d s c k a di sm o r ee f f i c i e n tb e c a u s ei tt a k ec o n s i d e r a t i o no fp h y s i c a lt o p o l o g yo f n o d e s t h er o u t i n g t a b l e ，r o u t i n gs t r a t e g ya n dr e s o u r c e p u b l i c a t i o n a n d r e t r i e v i n gm e c h a n i s ma r er e d e s i g n e di ns c k a d f i n a l l y , w ei n t r o d u c es o m e p o p u l a rs i m u l a t i o ns o f t w a r ea sw e l la ss o m ep 2 pp r o t o c o le m u l a t i o np l a t f o r m s a n di m p l e m e n ts c k a dp r o t o c o lo v e ro v e r s i m ，af a m o u ss i m u l a t o rp l a t f o r m a b o u tp 2 ps y s t e m s t h e nc o m p a r et h ek a d e m l i an e t w o r km o d e ls i m u l a t i o na n d s c k a dn e t w o r km o d e ls i m u l a t i o no no v e r s i m t h es i m u l a t i o nr e s u l ts h o w st h a t s c k a dd o e sb r i n gb e t t e rp e r f o r m a n c et h a nk a d e m l i a k e yw o r d s ：p 2 p ，k a d e m l i a ，d h t ，r o u t i n g ，n e t w o r km o d e l h i 两华人学硕十学位论文 8 声明 本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及 取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得西华大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确地说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论 文成果归西华大学所有，特此声明。 作者签名：芍，节5 月妒 刷槛轹砻 加 5 8 西华大学硕士学位论文 9 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅，西华大学可以将本论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复印手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书； 2 、不保密斫适用本授权书。 ( 请在以上口内划) 学位论文作者签名：芬、超 日期：q 弘巧 誓签c 7 予, 。s , 俨7 日期： 。 f 两华人学硕士学位论文 1 引言 1 1p 2 p 技术的兴起背景 早在2 0 世纪7 0 年代中期，源于局域网中文件共享的p 2 p 技术就丌始 流行起来，目前大家所关注的p 2 p 并非新技术，而是旧有技术的新应用模 式。8 0 年代及以前的计算机是众多用户共享一个主机，计算资源是集中式 的。随着w w w 网的出现，网络结构中引进了客户机一服务器结构( t i pc s 结构) ，c s 网络结构中，通常是客户机向服务器发送一个请求，服务器获 取这个请求，进行计算，然后返回一个结果来响应这个请求，此过程中以 服务器为中心，服务器与客户机是主从关系。9 0 年代，c s 模式开始流行， 这种模式将应用一分为二，服务器负责数据管理，客户机完成与用户的交 互，c s 模式具有强壮的数据操纵和事务处理能力，以及很好的数据安全性 和完整性约束。 近几年来，计算机网络技术飞速发展，基于t c p i p 协议的开放性特征， 计算机硬件价格的持续下降和人们生活水平的不断提高等因素，连入网络 中的设备、计算单元的数量和种类越来越多，信息资源的获取和发布也变 得非常方便和快捷，i n t e m e t 已经逐渐深入到人们的日常生活中。因为互联 网本身的是分布的、自治的，结点是对等的，计算资源是分布的，基于计算 机网络的各种应用通过对信息资源的采集、存储、传输、处理和利用，在 全球范围内把人类社会更紧密地联系起来，并以不可抗拒之势影响和冲击 着人类社会的各个方面，网络上的信息资源呈爆炸性增长趋势，c s 模型的 缺陷在这种环境下开始突显，与此同时，人们的需求日益增加，c s 很难满 足这些新的需求，这就导致了p 2 p 技术的复兴。 1 2p 2 p 技术的分类 1 2 1 从应用分类 从应用上来分，p 2 p 技术包括文件交换、分布式计算、协同工作、分布 西华大学硕十学位论文 式搜索等。 1 、文件交换 传统的互联网模式中，不论w c b 还是f t p 只要实现文件交换都需要中 央服务器的大力参与，通过将文件上传到某个特定的网站或服务器，用户 再到该网站或登录到服务器上检索需要的文件，然后下载，这就要求中央服 务器能够为大量用户的访问提供有效的服务，因而服务器经常成为这类应 用的瓶颈之一，p 2 p 技术使任意两台相连接的计算机直接共享文档、直接交 互，而不需要使用任一台中央服务器。 2 、分布式计算 有些学者称之为对等计算，是把原来需要超级计算机处理的庞大任务 进行分块，并通过位于系统控制中心的调度软件对分块任务进行调度和管 理，发给许多普通计算机来执行其具体运算操作，操作完成后再将结果返 回给中心，就本质而言，分布式计算是对网络上c p u 等资源的共享，典型 的应有s e t i h o m e 1 l 和f o l d i n g h o m e 2 j 等。 3 、协同工作 协同工作是指多个用户之间利用网络中的协同计算平台来共同完成某 项任务，共享信息资源等。p 2 p 计算系统中的协作分为两个层次：底层为应 用程序之间的协作，高层为用户行为的协作。对于特定应用，共享c p u 时 钟，就可以实现应用程序之间的协作，但高层用户行为之间的协作一般需 借助即时通信来实现，比如流行的软件q q 3 1 ，m s n 4 等。以协作为目标的 p 2 p 计算系统对传统的组件是一个挑战，就应用范围来说，前者足以覆盖后 者的功能。除即时通信外，协作型对等计算机体系也适用于工业系统中， 用于控制生产流水线之间的协调与决策过程。 4 、分布式搜索 p 2 p 技术使用户能够深度搜索文档，而且无需通过w e b 服务器，也可 以不受信息文档格式和宿主设备的限制，相比于传统目录式搜索引擎只能 搜索到2 0 9 6 到3 0 的网络资源，理论上它可以达到无限的深度并包括网络上 所有的资源。 2 西华大学硕士学位论文 1 2 2 从结构分类 根据系统的结构不同大致可以将p 2 p 系统分为以下三种类型：集中式 p 2 p 网络拓扑；非集中式非结构化拓扑；非集中式结构化拓扑( 也称作d h t ，网络) ： l 、集中式p 2 p 网络 这类系统通过中央服务器来进行目录管理，每台普通结点上线时将自 己的共享目录报告给服务器。该结构的特点是，搜索工作是在中央服务器 上进行的，传输是在普通结点之间进行的，n a p s t e r l 5 l 属于此类。由于采用目 录式管理和文件搜索，服务器不可避免地成为整个系统工作效率的瓶颈和 核心故障点，但是这种结构却继承了c l i e n t s e r v e r 模式的易于管理的优点。 2 、非集中式非结构化p 2 p 网络 这类系统没有中心服务器，各个结点之间几乎扮演完全平等相同的角 色。每个结点都会保留一个结点列表，记录着同属于此网络的相邻结点的 地址，需要说明的是，这类系统往往有若干个初始连接结点，保存着一张最 大的结点列表，每个结点上线的时候都会被记录下来，这个最大列表的用 处就在于，随时为网络其他普通结点提供可以访问的结点地址，g n u t e l l a l 6 1 和f r e e n e t l 7 1 是这方面两个的应用。g e n u t e l l a 由于良好的协议开放性得到了 十分广泛的使用，而严格的加密和传输加密则是f r e e n e t 追求的一个重要功 能，其复杂的加密机制使得很难用明文进行搜索，同时也降低了传输效率， 因此用户比g e n u t e l l a 相对较少。 3 、非集中式结构化p 2 p 网络 这类系统没有中心服务器，各个结点之间扮演几乎完全平等相同的角 色。结构化p 2 p 模式是一种采用纯分布式的消息传递机制和根据关键字进 行查找的定位服务，目前的主流方法是采用分布式哈希表( d h t ) 技术，这 也是目前扩展性最好的p 2 p 路由方式之一，由于d h t 各结点并不需要维护 整个网络的信息，只在结点中存储其邻近的后继结点信息，因此较少的路 由信息就可以有效地实现到达目标结点，同时又取消了洪泛算法。该模型 有效地减少了结点信息的发送数量，从而增强了p 2 p 网络的扩展性，同时， 出于冗余度以及延时的考虑，大部分d h t 总是在结点的虚拟标识与关键字 3 两华人学硕十学位论文 最接近的结点上复制备份冗余信息，这样也避免了单一结点失效的问题， 这类网络的代表有c h o r d 8 1 ，p a s t r y 9 1 ，t a p e s t r y i l 0 1 ，勋d e m l i a l l l l 等。 1 2 3 从出现时间分类 根据时间顺序和目的，当前的p 2 p 网络分为三代： 1 、第一代 早期的p 2 p 网络，如n a p s t e r 和g n u t e l l a ，以容易且快速部署为目的。 这代网络结构简单，而且其可展性差或请求效率低。 2 、第二代 第二代p 2 p 网络常利用d h t 技术来实现更好的扩展性和更高的请求效 率，并提供负载平衡和确定性查询保证。尽管如此，弹性或容错性并不是 很好，特别是在恶意攻击的情况下。 3 、第三代 新近提出的p 2 p 网络在假设结点以一定的失效概率离开的前提下，目 的在于提供高弹性。产生弹性的常用方法有：复制，扩展结点之间的连接数 以及一些特别的结构化拓扑。第二代和第三代p 2 p 网络通常是分布的结构 化覆盖网络。 4 西华人学硕+ 学位论文 2 基于d h t 的结构化p 2 p 模型 2 1c h o r d 协议 c h o r d 是麻省理工学院所提出的一种搜寻演算法，它将每一个n o d e ， 和其分享的资源i t e m 做h a s h ，产生出一个独特的i d e n t i f i e r ，用来代表n o d e 或i t e m ，然后将i d e n t i f i e r 建构成一个环( r i n g ) 状的网路架构，如图2 1 ，环 上的每个点代表一个n o d e ( p e e r ) ，而分享的资源h a s h 出来产生的k e y 值( 例 如用文档名做h a s h ) ，会依照大小交由附近的n o d e 管理，也就是n o d e 会 持有资源拥有者的资料而不是文件本身，在取得资源拥有者的资料后再进 行直接点对点的传输。 6 7 o f l n 0 , 射 t a l ) l e s t a r ti n t s u c c 1 【1 2 l 1 2 【2 4 3 4 【4 0 ) o k e y s 圈 53 4 2 f i n g e rt a b l e s a r li n t s u c c 2 f 2 3 ， 3 3 【3 5 ) 3 s 【5 1 ) o f i g u r e2 1c h o r dr i n gw i t hm = 6 图2 1m = 6 的c h o r d 环 b y s z i 慷y s 7 1 2 1 1c h o r d 路由表结构 当一个n o d e 加入环的时候，他会建立一个有关网路资讯f i n g e r t a b l e ， f i n g e r t a b l e 内存放好几笔f i n g e r ，f i n g e r 记录文件的详细定义见表2 1 。 5 两华大学硕十学位论文 f i n g e r t a b l e 的大小为o ( t d g n ) ，也就是t a b l e 内有l o g n 个f i n g e r ，n 为r i n g 的总容量大小。 表2 1f i n g e r t a b l e 定义 t a b l e2 1t h ed e f i n i t i o no ff i n g e r a b l e n o t a t i o nd e f i n i t i o n f i n g e r k s t a r t( n + 2 。1 ) m o d 2 ml = 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 + 1 s t a r t ) n o d ef i r s tn o d e = n f i n g e r k s t a r t s u c c e s s o rt h en e x tn o d eo nt h ei d e n t i f i e rc i r c l e ；f i n g e r 1 n o d e p r e d e c e s s o rt h ep r e v i o u sn o d eo nt h ei d e n t i f i e rc i r c l e f i n g e r t a b l e 中的记录的资讯，代表区间内的i d e n t i f i e r 都由所属的n o d e 负 责。负责该i d e n t i f i e r 的n o d e 就称为s u c c e s s o r ，而每个区间内的那些i d e n t i f i e r 其所属的s u c c e s s o r ，由区间内往下数第一个n o d e 充当，而一个n o d e 的 s u c c e s s o r ，就是第一个f i n g e r 区问的s u c c e s s o r ，也就是f i n g e r 1 n o d e 。区 间大小，依照c h o r d 演算法的设计，从t a b l e 内第一笔资料开始，由n o d e l d 和严1 决定。 2 1 2c h o r d 路由算法伪代码 简单查找c h o r d 中的每个结点仅存储其s u c c e s s o r 结点的地址，查找过 程沿着s u c c e s s o r 进行，每个结点n 要维护一个包含m 个表项的f i n g e r 表， n l 为资源和结点标识的位数，第i 个表项包含的是在节点环中存放 ( n + 2 h ) m o d2 的点s 。即s = s u c c e s s o r ( ( n + 2 ) m o d2 ) ，l = i = m 。称s 是n 的 第i 个f i n g e r ，表示为n f i n g e r i 。 f i n g e r i ：环中存储( n + 2 1 。1 ) m o d2 m 的点。 s u c c e s s o r ：结点在环上的下一个结点，即n f i n g e r 1 。 p r e d e c e s s o r ：结点在环上的前一个结点。 ( 1 ) 每个结点保存部分其他点的信息，并且保存在环路上临近结点的信息量 比远端结点的信息量大。 6 西华人学硕十学位论文 ( 2 ) 每个结点只包含o ( 1 0 9 n ) 个表项，一个结点通常没有足够的信息来直接 找到任何一个关键字。 图2 2 中描述了结点8 查找i d5 4 的过程： 算法如下： f i g u r e2 2s i m p l ef m d i n gp r o c e s s 图2 2 简单查找过程 f i g u r e2 3c h o r d sn o d ef i n d i n gp s e u d o - c o d e 图2 3c h o r d 定位结点算法 7 西华人学硕士学位论文 如果i d 在结点n 与其s u c c e s s o r 之间，则i d 一定存储在n 的s u c c e s s o r 中，否则执行n c l o s e s t _ p r e c e d i n g _ n o d e 过程查找f i n g e r 表，找到与i d 最近 的结点n ，n 再次调用f i n d _ s u c c e s s o r ，这是因为越接近i d 就会了解到更 多的关于i d 的信息，可以尽快地定位i d ，图2 4 显示对于图2 2 中的查找任 务使用升级查找算法以后的查找过程。 5 6 5 lj 4 8 8 l 兰i 娶! ! 嫂3 l 里i 翌坚【13 lf i n e r 【2 】 压五面 、jf i n e r 【4 】 4 叵五面 lf i n e r 0 】1 4 lf i n e r 1 】匪 2 1 阿面两吓； 叫f i n e r 3 】1 5 l lf i n e r 4 】l l 3 8 f i g u r e2 4u p g r a t ef i n d i n gp r o c e s s 图2 4 升级查找过程 结点8 在其f i n g e r 表中找到最接近5 4 的结点4 2 ，将请求发送给结点4 2 ， 同样4 2 在其f i n g e r 表中找到结点5 1 ，结点4 2 将请求发送给5 1 。结点5 1 发现目标5 4 位于它与其s u c c e s s o r ( 即5 6 ) 之间，查找成功，发送请求给 结点5 6 ，结点5 6 响应请求，查找是一个递归的过程，在n 个结点的网络 中，升级算法的查找复杂度为o ( 1 0 9 n ) 。 2 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 ) 。每个 结点都可以路由客户请求并和应用程序( 可以是多个) 的本地实例进行交 8 两华大学硕十学位论文 互。任何一台连接到i n t e r n e t 的计算机只要运行p a s t r y 结点软件就可以称为 p a s t r y 结点，当然，它需要满足应用定义的安全策略。p a s r t y 系统中的每个 结点都被分配一个1 2 8 位的结点号，结点号用于在结点间中标识结点的位置， 结点号是在结点加入系统时随机分配的，分配策略是在点空间中均匀分布， 结点号可以通过计算结点公钥或者i p 地址的哈希函数值获得，由于采用了 均匀分布，因此结点标识相邻的结点处于不同的地理位置的几率很大。 2 2 1p a s t r y , s - d 了表结构 结点需要维护3 种数据结构：如图2 5 l 、路由表 假定网络由n 个结点组成，它有1l 0 9 2 b nl 行，每行有2 b ( b 是一个配 置参数，典型取值是1 ，2 ，3 ，4 ) 个入口的表项组成，行n 的2 b 一1 个入口指向 其n o d e l d 和当前结点的n o d e l d 共享前n 位但第n + 1 位不同的2 b 一1 个表 项，值b 的选择考虑了路由表的长度和路由跳数的权衡，b 越大则路由跳数 越小，但需要维护的路由信息越多，路由表中每行的阴影项表示当前结点号 对应的位。 2 、叶子集( l e a fs e 0 存放的是和当前结点的标识符从数值上看最接近的结点，叶子结点集 合在消息路由时需要用到。它是i l v 2 的下取整( i t 4 是配置参数值为2 b ) 个 其n o d e l d 最接近且大于本地结点n o d e l d 的结点和i l v 2 的下取整个其 n o d e l d 最接近且小于本地结点的n o d e l d 的结点集合。 3 、邻居集( n e i g h b o r h o o ds e 0 它包含同本地结点最接近的l m l i m i 是配置参数，值为2 x 2 b ) 个结点， 用于保证路由表中每个表项指向的结点都是离当前结点最近的结点，保证 的前提是网络距离度量满足欧氏空间的三角不等式【1 2 1 。 9 两华大学硕士学位论文 n o d e l d1 0 2 3 31 0 2 l e a fs e t s m a l l e rl a r g e r 1 0 2 3 3 0 3 31 0 2 3 3 0 2 1 1 0 2 3 3 1 2 01 0 2 3 3 1 2 2 1 0 2 3 3 0 0 11 0 2 3 3 0 0 01 0 2 3 3 2 3 01 0 2 3 3 2 3 2 r o u t i n gt a b l e o 一2 2 1 2 1 0 21- 2 - 2 3 0 1 2 0 3 3 1 2 0 3 2 0 3 0 1 一l 一3 0 1 2 3 3l 一2 2 3 0 2 0 31 3 一0 21 0 2 2 l o 一0 31 2 0 31 0 一1 3 2 1 0 221 0 - 3 2 3 3 0 2 10 2 。0 0 2 3 01 0 2 - 1 - 1 3 0 2 1 0 2 2 2 3 0 23 1 0 2 3 0 3 2 21 0 2 3 1 0 0 01 0 2 3 2 1 2 l3 1 0 2 3 - 0 - 011 1 0 2 3 3 2 - 3 2 0 1 0 2 3 3l 一2 一o 2 l ln e i g h b o r h o o ds e t l 1 3 0 21 0 2 21 0 2 0 0 2 3 0 11 3 0 1 2 3 33 1 3 0 1 2 3 3 l 0 2 2 1 2 1 0 2 2 2 3 0 1 2 0 331 2 0 3 2 0 33 3 2 1 3 3 2 1 l l f i g u r e2 5p a s t r ym u t i n gt a b l es t r u c t u r e s t a t eo fa h y p o t h e t i c a lp a s t r yn o d ew i t hn o d e i d1 0 2 3 3 1 0 2 ，b = 2 ，a n d1 - 8 图2 5p a s t r y 路由表结构( r o u t i n gt a b l e ) 假设结点i d = 1 0 2 3 3 1 0 2 ，b = 2 ，1 = 8 1 0 两华大学硕士学位论文 2 2 2p a s t r y 路由原理 当给定一条消息和一个关键字时，p a s t r y 结点将会把这条消息路由到在 当前所有的p a s t r y 结点中n o d e l d 和关键字最接近的k 个结点的任何一个。 p a s t r y 采用了启发式算法可以使关键字首先路由到在结点空间中和消息产 生的结点距离最近的包括查找关键字的结点，它的目标是使消息传递的距 离最短，结点收到一条消息时，首先检查消息的关键字是否落在叶子结点 集合中，如果是则直接把消息转发给对应的结点，如果不是，则将使用路 由表进行路由，当前结点把消息发送给结点号和关键字直接共同前缀至少 比现在结点长一个数位的结点( 也就是b 个二进制位) ，当然，可能会出现 路由表对应表项为空，或者路由表表项对应的结点不可达的情况，这时候 消息将会被转发给共同前缀一样长的结点，但是该结点和当前结点相比， 其结点号从数值上将更接近关键字，这样的结点一定位于叶子结点集合中， 以图2 5 为例，当结点号为1 0 2 3 3 1 0 2 的结点收到搜索结点请求，其 k e y = 1 0 2 4 1 2 0 1 ，路由过程如下： 1 、检查k e y 值是否在叶子集中，有直接转第4 步； 2 、查询路由表。由于k e y 和当前结点号1 0 2 3 3 1 0 2 的前3 位相同，所以直 接查询第4 行，查找共同前缀至少比现在结点长一个数位的结点，如果找 到符合条件的结点直接转第4 步，本例没有符合条件的结点，因此进行第3 步； 3 、结点在叶子集中查找共同前缀一样长的结点，查找结果为结点号是 1 0 2 3 3 2 3 2 的结点； 4 、向指定结点转发查询请求； p a s t r y 路由算法伪代码如图2 6 ，我们做如下约定： 碍：路由表中的第i 行l 列( o = i 2 b ，0 = 1 m r 糊卜_ a r e a d 玲一一 f i g u r e3 6r e g i s t e rn o d ed o m a i nr o u t i n gt a b l e 图3 6 注册结点域路由表示意图 3 4 3 结点的加入和退出 l 、结点的加入： 结点连接上网络后，首先和注册结点取得联系，如果已经存在该域， 则从注册结点上获取对应域的集合结点，并更新本地的域路由表，然后向 相应的域中的集合结点发送加入消息，如果没有该域，则自身成为域的集 合结点，同时注册结点更新路由表，并将更新后的路由表通知其余集合结 点，由集合结点发送消息通知其余结点更新自身的域路由表。 新结点加入域内时，实际上是遍历二叉树，找到相应的等级和位置的 过程。刚开始只有一个根结点，它也就是叶结点，这时它存储到这个结点 上，这个结点是有意义的，当联系人信息不断得被添加到结点上以后，这个 结点联系人的容量满了，这时要进行的就是一个分裂的操作。这时，会添 加两个结点，左子结点和右子结点，然后把自身的结点中的联系人信息按照 它们的前缀特点分别复制往左结点和右结点，最后把自身的结点废除掉， 西华大学硕十学位论文 这样这个分裂过程就完了。当分裂完成后，就会再次试图添加该联系人信 息，此时会试图按照它的i d ，把它添加到对应的子树中，只有当自身i d 和 当前准备分裂的结点有共同前缀时，这个结点才会分裂，而如果判断到一 个结点不能分裂，而它的联系人又满掉了，那么就会拒绝添加联系人信息。 下面是添加新结点的算法。 f i g u r e3 7p s e u d o - c o d eo fn o d ej o i n 图3 7 结点加入伪代码 2 、结点的离开： 普通结点主动离开网络时，向集合结点发送离开消息，由集合结点负 责将该消息发送到其余结点，被动离开不需要发布任何信息，由更新机制 动态机制自动进行。 集合结点主动离开网络，通知注册结点，同时注册结点通知所有集合 结点，集合结点通知普通结点删除相应的死结点，如果集合结点被动离开 西华人学硕+ 学位论文 网络，则由k a d e m l i a 原有的动态更新机制负责更新集合结点，结点离开， 域内路由表在动态更新中删除了对应的结点信息，如果结点联系人的个数 为0 ，则会发生结点合并。 3 4 4 结点消息类型 l 、路由消息： p i n g s k b o o t s t r a p r e g i s t e r l e a v e f i n d a r e a f i n d s k n