（计算机系统结构专业论文）基于kademlia的内容分发网络的研究与实现.pdf

d i s s e r t a t i o nf o rm a s t e rd e g r e ei n2 011 i 燃必 fy 1 斟攀毯崔岁燮l 毒c h o o lc o d 占1 0 2 6 参 n u i l l b e r ：5 1 0 8 1 2 0 1 0 1 4 ea s tch i n an o r m a l u n i v e r s i 锣 i 之es e a r c ha n di m p l e m e n l - 鲴 1 i o n o nco n t e n td i s t l u b u t i o n s t r u ct u r eb a s e do nk a d e m l i a d e p ，岍m e n t ： q 蛩堕p 坠曼s 堡i 曼坠坌曼i 也亟! 受坌! 墅堕q l q g y m a j o r ： s p e c i a l i t y q 堑q 型曼! n 曼盟q 亟 t u t o r ： 0 c t 2 0 l o 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于k a d e m l i a 的内容分发系统的研究与实现， 是在华东师范大学攻读恁为博士( 请勾选) 学位期间，在导师的指导下进行的研究工 作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确 说明并表示谢意。 作者签名：鹕 啉冲年f 月加 华东师范大学学位论文著作权使用声明 基于k a d e m i i a 的内容分发系统的研究与实现系本人在华东师范大学攻读学位 期间在导师指导下完成的移班博士( 请勾选) 学位论文，本论文的研究成果归华东师 范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部 门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许 学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全 国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部 或“涉密学位论文掌， 于年月日解密，解密后适用上述授权。 ( 力2 不保密，适用上述授权。 导师签名 本人签名囱垃固蟊 晰i ，月纠日 “涉密 学位论文应是已经华东师范大学学位评定委员会办公室或保密委员 会审定过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密 审 批表方为有效) ，未经上述部门审定的学位论文均为公开学位论文。此声明栏不 填写的，默认为公开学位论文，均适用上述授权) 。 刘丽娇硕士学位论文答辩委员会成员名单 姓名职称+单位备注 邵时副教授华东师范大学主席 王能教授华东师范大学 张卫教授华东师范大学 华东师范大学硕十学位论文 摘要 摘要 在当今，随着m e n l e t 的高速发展，浩瀚的信息充斥着人们每天的生活，对 i n t 锄e t 的服务品质和访问速度要求越来越高，高效的从网络上获取信息成为人 们更加期待的事情。从技术的角度讲，当前互联网上主要存在的是内容分发网络 技术【1 1 和p 2 p 【6 ，7 1 两种主流技术实现内容传递。 内容分发网络( c 0 n t e l l td e l i v e r yn e t 、) l ，o r k ，c d n ) 的核心是通过在网络边缘 布置服务器，将网站的内容发布到最接近用户的边缘服务器上，使用户可以在最 近的服务节点上获取所需的内容，但究其本质，其核心仍然是基于集中服务器的 架构，通过配置高额硬件设备达到“一步之遥”的效果，与地域化管制紧密相连， 维护和扩展时都需要很高的成本，而且无法利用大量网络中的闲散资源，特别是 对大量的公益站点无法采用该项技术提高站点的分发速度。而p 2 p 技术即对等 网络( p e * t o p e e r ) 技术，突破了传统的c s 模式，每个节点都拥有服务器和客 户端两种身份，在获取其他节点上的资源的同时为其他节点提供服务。在内容传 递方式上，与c d n 相比采用了完全不同的方式，其核心是充分的利用用户资源， 通过对等方式进行文件传输，实现了不依赖服务器而快速的交换文件。p 2 p 技术 广泛的应用在网络应用程序中，特别是k a d e m l i a 协议以其稳定性，高效性应用 更广泛。 本文吸取c d n 提供的“一步之遥 的思想，通过对p 2 p 网络中节点之间 形成的信息区域性的研究，结合k a d e m l i a 协议，提出了一种混合层次的基于p 2 p 的内容分发i 网络结构l i k a d ( 1 0 c a l i t y - a w a r e i l e s s 觚di n t e r e s t - f o c u s i n gk a d e m l i a ) 以 达到该效果。在该结构中，从上至下由源服务器层，索引节点层，自治节点层构 成，不同区域和不同站点的索引节点构成了k a d e i i l l i a 网络结构，通过查找方法 的改进，使节点之间的逻辑结构与物理拓扑相结合，高效的查找和分享资源；自 治节点层由普通客户节点组成，位于相同位置区域和具有相同兴趣的客户节点相 互分享资源，推举出综合能力强的节点作为该区域的索引节点，负责管理和组织 该区域节点；实验表明，在节点查询站点内容，定位资源副本所耗延时方面，本 文提出的基于k a d 锄l i a 的混合层次的网络结构比传统的k a d e m l i a 的结构改进效 果明显。 华东师范人学硕上学位论文摘要 关键词：p 2 pk a d e i i l l i a 内容分发网络兴趣集中 华东师范大学硕士学位论文 a b 盯r a c t a b s t r a c t n o w a d a y s ，v 撕。邯i i l f o 肌a t i o nb o m b a r dp e o p l e sd a i l yl i f e a n de v e r y o n e i s e x p e c t i n gh i 曲e rq u a l 埘o fi n t 朋域s e i c e 肌dn l o r e ：f ；斌i n f 0 1 m a t i o n f e t c h t e c h l l i c a l l ys p e a k i n 舀l et 、7 l ，oc 嗍l tp r e v a l e n tt e c l l l l 0 1 0 百e s a r ec o n t e n td e l i v e r ) r n e t w o r k ( c d n ) 【1 】a n dp 2 p 【6 ，7 1 t h ec o r co fc d ni st ol a y o u ts e e r so nt h en e 觚o r ke d g e ，w l l i c hc 趾r e l e 嬲e c o n t e n tt 0m e e d g c ，w h i c hi sn e 锄o s tp e e rt 0t h eu s 既1 h eu s e rc 眦g e tn e e d e d i n f o m a t i o n 丘o mt h en e a r e s tn o d e s t i l i st e c l l i l o l o g yb r i n g sf 瓠tr e s p o n s e ，d e c r e 弱eo f s e r v e rl o a da i l di n c r e 嬲eo fn e 咐o r kd e v i c e su t i l i z a t i o n t 0m en a t l 鹏m ec o r ei ss t i l l b a s e do nc ss t m c t i l r e ，c o n 6 9 l l r ct h e 蛐出c o s ts e 懿i no r d c rt 0m ee 仃e c to f o n e s t 印a w a y 锄d 嬲s o c i a t e dw i mr e 西o no ft h cc o n t r 0 1 t h ec o s tf o rm a i n t e n a n c e 锄d e x p a n s i o ni s 唧1 l i 曲i tc 锄n o t t a k ef i l na d v 觚t a g eo f al 姆n u m b e rn e t 、7 l ，o r ke d g e r e s o u r c e p 2 pt e c l m o l o 斟b r e a l 【st h e 仃a d i t i o n a lc sm o d e l e v e 叮p e e ri ni ti sb o m c u s t o m e ra n ds e r v 既p e e r sg e tr e s o u r c e s 伍) mo t h e rp e e r s 锄dp r 0 v i d er e s o u r c e sf o r o m e r sa tm es a m et i m e p 2 pp r o p o s e dt o t a l l yd i f f i e r e i l tw a y so fd e l i v e r i n gc o n t e n t s t h ec o r eo fp 2 pi st o 伽1 yu t i l i z eu s e rr e s 叫r c ef o rp e * t 0 - p e e r 咖l s “s s i o n f a s t j e i l e e x c h a i l g ew i t h o u tr e l yo ns e f v e rw 嬲呻1 e m e r l t e db ym em u l t i - p o i n t 觚l s m i s s i o n m e c h a i l i s ma 1 1 dd e s i 皿o fd e c 钮咖l i z e d p 2 pt e c t l i l o l o g ) ，i sa p p l i e d i nn e t 、) i ，o r k a p p l i c a t i o n sw i d e l y ，e s p e c i a l l yk a d e m l i ap r o t o c o l i sm o r ew i d e l yb e c a u s eo fi t s e m c i e n c ya n ds t a b i l i 够 w et l 血l ko fm e o n es t 印m e m o di nm ec d n ，s t i l d yt h el o c a l i t ) ri n f o 姗a t i o no f p 2 pn o d e ，p m p o s e dac r o s sl a y e rl o c a l i t y - a w a r e n e s s 觚di n t e r e s t f o c u s i n gk a d 锄l i a ( l i k a d ) s 仇l c t l l r e t h es t m c t u r ec o n t a i l l ss o u r c es e 盯1 i n d e x - p e c rl a y c r 锄d a u t o n o m o u sp e e r s1 a y 瓯1 1 l el i k a ds 乜u c t l l r ec o n s i s t so fd i 侬嘞ti i l d e ) 【_ j e e r si n d i 伺衙e n tz o n e s w bh n p r o v em es e a r c ha 1 9 0 r i s m 、) i ，：i l i c h c a i lm a t c hn o d e s 1 0 百c a l t i d p o l o g y 趾dp _ h y s i c a lt o p o l o g ya n di 麟e 弱em ee 伍c i e l l c yo fs e 鲫幽n ga n d g r e s o u r c e a - u t o n o m o u sp e e r sc o n s i s to fc o i l l m o nc u s t o m e r s n o d e si nm es 锄ez o n e a 1 1 dh a v i n gs 锄ei n t e r e s ts h a r cr e s o u r c e 丘r s t 1 l l e nm c yv o t ef o rp o w 刊试n o d e t 0b e t l l e i ri n d e x ，w l l i c hi s i i lc h a r g i eo fm a i l a g i i l ga n do 唱a i l i z i n gn o d e si i li t sz o n e e x p 甜m 饥t ss h o w 廿l i ss 仃1 1 c t u r ch 硒l o w1 a t e i l c y ，l 鹕es c a l a b i l i 吼1 l i 班p e r f 0 n 1 1 a i l c e i nq u e 强1 0 a db a l a i l c e n sv e r ) rs u i t a b l ef o rd y i l 锄i cn e t 、o r kw h m es c a l ei sv c 巧 l a r g e l ( e vw b r d s ：p 2 p ；k a d 既【l l i a ；c o n t 铋td i s t r j b u t en e 附o r k ；h l t e f 懿t b 船e dl o c a l i t y 华东师范人学硕上学位论文目录 目录 摘要i a b s t r a c t 目录：；i v 第一章绪论。1 1 1 研究背景1 1 2 研究内容和研究意义2 1 3 论文的组织结构3 1 4 本章小结3 第二章内容分发网络及p 2 p 概述4 2 1c d n 技术核心思想4 2 2p 2 p 网络资源搜索技术概述5 2 2 1p 2 p 网络的概述5 2 2 2p 2 p 的网络结构6 2 2 3 结构化p 2 p 网络的搜索技术9 2 3p 2 p 与c d n 的结合1 7 2 4 本章小结1 8 第三章基于k a d e m l i a 的内容分发网络的系统结构1 9 3 1 总体设计思想1 9 3 1 1k a d 网络的社群性1 9 3 1 2 基于兴趣的局部性原理( i n t e r e s t - b a s e dl o c a i i t y ) 2 1 3 2 基于k a d e m “a 的内容分发网络的系统结构2 3 3 2 1 基本概念2 3 3 2 2 系统结构的总体设计2 4 3 2 3l i k a d 系统节点查找基本工作流程2 5 3 3 索引节点之间资源搜索算法2 6 3 3 1 节点位置信息的获取2 6 3 3 2 索引节点标识符和资源标识符2 7 3 3 3 索引节点间的资源搜索2 8 3 4 自治系统内资源搜索3 0 3 4 1 节点的数据结构3 1 3 4 3 自治系统内部节点之间资源搜索和路由算法3 2 3 5 节点的离开与失效的处理3 3 3 6 本章小结3 3 华东 v 荤 华东师范大学硕 1 1 研究背景 近几年来，随着互联网的高速发展和个人计算机，移动设备的广泛应用，人 们对网络的使用频率越来越高，人们在i n t 锄e t 上查找自己所需的资料，分享自 己拥有的资源，流动在网络中的信息量在呈指数方式上升，与此同时人们迫切希 望能够获得更快的站点访问速度。就目前而言，大多数的站点选择添加c d n 服 务器的方式加速内容分发，以此加快用户访问速度。 c d n 是架构在传统的c s 模式下的一种增值网络，通过在网络边缘部署高 额服务器，将站点内容推送到网络的边缘服务器，从而为用户提供就近性的边缘 服务，保证了服务质量和访问速度。通过c d n 服务器的部署使得站点内容从中 心分散到了边缘，缓解了中心服务器的压力，实现了一定程度上的负载均衡。但 究其本质，c d n 是建立在c s 模式下的应用，并且服务器的布置与地域化管制 紧密联系，随着用户规模指数级的增长，原有的c d n 规模已经不能适应用户需 求，但扩展规模和维护需要耗费大量资金，内容提供商总希望回避该问题，长此 以往，出现了严重的矛盾。特别是针对大多数的公益站点来讲，它可能拥有大量 的用户，但是由于其公益性，没有利润收入，配置不了高昂的c d n 服务器，显 然c d n 方式不能很好的适应这些站点的需要。例如，维基百科是一个纯粹的公 益站点，只是为了实现全球范围内的知识共享，但它确是世界上第五大站点，每 月拥有3 8 亿的用户，占全球互联网使用人数的1 3 左右，但却依然面临没有资 金投入设备更新的窘境，无法使用c d n 的方式为其用户提高访问速度。这样一 个现实的问题该如何解决? 设计怎样的一种结构既能使拥有巨大用户的公益站点拥有较高的内容分发 速度又不会花销太多呢? 如果能够充分利用巨大的边缘资源为站点内容进行分 发内容将能够有效的缓解这些站点面临的问题。此时，p 2 p 技术的发展正是弥补 了这个缺陷。p 2 p 的核心思想是网络中的每一个节点既可以向其他节点请求资源 也可以为其他节点提供自身拥有的资源，即每一个参与的节点既是客户端又是服 务器。突破了传统的c s 模式，形成了无中心化的结构模式，弱化了服务器的角 色，强调了节点之间的对等性。这样，整个系统的性能会随着节点数目的增长而 1 华东师范大学硕七学位论文第一章绪论 增长。 就现阶段的大多数的研究而言，内容承载解决方案基本集中在c d n 和p 2 p 的融合方面。其基本融合方式分为两种：p 2 p o v c r c d n 和c d n o v e r p 2 p 。但无论 哪种方式都摆脱不了对c d n 服务器的依赖，都要面对c d n 服务器高昂的维护 成本，无法解决c d n 面对突发高流量的适应性不足的问题。如果仅是纯粹的p 2 p 结构，节点频繁的加入或是退出，不利于内容管理。 因此，这就需要一种新的结构既要满足用户高效访问站点的要求又不会对内 容提供商造成特别大的维护费用，这一点对非商业公益站点特别的重要。本文根 据这样的构想，提出了新型的基于p 2 p 的内容分发网络。 1 2 研究内容和研究意义 本文针对内容分发网络和p 2 p 技术及k a d e i n l i a 结构的研究，拟建立一种全 新的基于k a d e i l l l i a 架构的内容分发网络模型。 本文从分析内容分发网络c d n 技术的特点和不足以及p 2 p 网络的优势出 发，结合k a d e m l i a 协议，提出了新型的基于k a d e m l i a 的内容分发服务解决方案。 本文研究的主要内容包括以下几个方面：， 1 着重研究了c d n 架构的核心思想，p 2 p 技术和l 【a d e m l i a 协议的原理， 关键技术，分析各自的优缺点；并从社群网络和局部性的角度分析了网络 的特点； 2 在分析研究的基础上，通过吸取c d n 架构的核心思想并利用m 网络 特点，构建一种基于位置感知和兴趣集中的新型混合层次的k a d e m l i a 结构用以 实现站点内容高效分发的目的。 3 基于兴趣的局部性原理，优化自治系统节点结构，建立直接资源列表， 实现区域内资源共享和快速查找。 4 改造k a d 网络结构中节点结构，实现逻辑结构与物理拓扑结构相匹配， 提高查找效率。 本文针对公益站点内容分发的问题，提出了一种新型的基于k a d 锄l i a 的内 容分发网络结构，帮助站点利用对其内容感兴趣的用户帮助其分发内容的目的， 充分利用网络边缘资源加速内容分发，具有高性能性价比，使站点摆脱了c d n 服务器设备的高额成本和维护费用，具有现实意义。 2 华东师范人学硕上学位论文第一章绪论 1 3 论文的组织结构 本文第一章主要介绍了研究背景和意义，以及本文的主要工作； 第二章主要介绍了c d n 架构的核心思想以及其优缺点，并介绍了p 2 p 技术 的相关内容，详细讲解了k a d 锄l i a 的结构和算法； 第三章根据前文的分析和研究，提出了基于l 锄e m l i a 的内容分发网络结构 模型，详细介绍了该网络结构的组成，并介绍了利用s n a 的方法分析网 络的特性和基于兴趣的局部性原理，针对性的改进节点结构和路由算法，提高系 统性能； 第四章对该结构进行相应的仿真实验； 最后第五章给出总结并提出存在的问题，以及下一步工作。 1 4 本章小结 本章主要介绍了研究背景，研究的主要内容和意义，并简要介绍了论文的组 织结构。 3 华东师范大学硕十学位论文第二章内容分发网络及p 2 p 概述 第二章内容分发网络及p 2 p 概述 2 1c d n 技术核心思想 c d n 【3 】即内容分发网络( c o l l t e n td i s t r i b u t i o nn e t 、) l ，o r k ) ，它是在传统的口网 络之上建立的由不同区域的节点服务器群组成的虚拟网络，是一种高性能分发的 应用层上的“增值 网络，是一种为多种应用发布而特别优化的网络系统支撑平 厶 口o c d n 的核心思想是将站点内容从中心服务器推到网络边缘从而更靠近用 户，不仅提高用户访问内容的性能，而且有效减轻了中心设备和骨干网络的压力。 c d n 的关键技术是全局负载均衡( g s l b ) 技术，它为c d n 的多个分布节点， 提供智能d n s 解析、内容就近访问的核心技术，它的作用是根据距离最近、节 点负载最轻等多种策略，将用户的请求导向整个c d n 网络中的最佳节点；在提 供内容最快相应的同时，它也实现了各个分布节点之间互为备份，保障了网络服 务7 x 2 4 的可用性。因此，全局负载均衡( g s l b ) 的准确性和效率直接决定了 整个c d n 的效率、性能和可用性。 c d n 是一个策略性部署的整体系统，如图2 1 所示包括内容分发、负载均 衡、网络请求的重定向和统计管4 个主要组件。内容分发组件由源服务器和一组 缓存服务器组成，缓存服务器位于网络的边缘，是内容提供商源服务器的一个透 明镜像。网络请求的重定向组件负责将用户请求重定向到离用户最近的代理服务 器。负载均衡组件负责将内容从源服务器分发到位于网络边缘的代理服务器，并 保证内容的一致性。统计管理组件维护客户接入日志和c d n 服务器使用情况记 录。 4 华东师范人学硕上学位论文第_ 二章内容分发网络及p 2 p 概述 图2 1c d n 组件 2 2p 2 p 网络资源搜索技术概述 2 2 1p 2 p 网络的概述 1 p 2 p 的定义 7 ，8 】 网络上信息的分享方式实际上是人类社会的一个抽象过程，p 2 p 就模仿了人 类社会的p e r s o n - t o - p e r s o n 的交流方式。在p 2 p 网络中每个节点的地位相同，既 充当服务器，为其他节点提供服务，同时也充当客户端，享用其他节点提供的服 务，打破了传统的c s 模式。如图2 2 所示p 2 p 结构中每个节点直接互联，但 c s 结构中节点通过服务器相连。 p e 雠 幽鞠t 霉 图2 2p 2 p 与c s 模式 5 华东师范人学硕士学位论文 第一二章内容分发网络及p 2 p 概述 c l a ys h i r k y 对p 2 p 做出了如下定义：“p 2 p 是一类利用各种i n t e n l e t 边缘资源 的应用程序，边缘资源包括存储，计算，内容，人力等资源；访问这些分散资源 意味着在不可预测的i p 地址和不稳定的网络连接环境中进行，所以p 2 p 节点必 须独立于d n s 系统和中心服务器，完全或高度的自治和自组织”。 本文将p 2 p 网络定位为是以互联网用户为主体，节点之问进行资源共享， 协同合作的网络应用，它能够有效的组织，定位和利用互联网络( 核心网络或边 缘网络) 中任何可用的存储空间，计算能力以及人力等资源完成特定的任务。 2 p 2 p 网络的特点 p 2 p 网络的广泛应用，关键在它具有良好的特性： ( 1 ) 非中心化：网络中的所有节点都参与资源的存储和信息的传输，每一个 节点既是服务器又是客户端，节点之间直接进行信息交换，提高了网络 的健壮性，避免了服务器瓶颈等问题。 ( 2 ) 可扩展性：由于网络的无中心化，服务的需求增加与系统整体的资源和 服务能力同步地扩充； ( 3 ) 高性能价格比：p 2 p 网络充分利用网络边缘的节点存储资源，利用节点 闲置的计算能力或存储空间，达到高性能计算和海量存储，因此可以以 低成本提供较高的计算和存储能力，实现负载均衡；而且避免了传统模 式下的对服务器设备的高额维护费用； ( 4 ) 负载均衡：p 2 p 网络中的每个节点扮演客户端和服务器端，请求资源时， 是客户端；共享资源时，是服务器，资源分布在多个节点，一个请求有 很多的服务器节点接受请求，避免了传统c s 模式下的单独服务器的弊 端，更好的实现了整个网络的负载均衡。 2 2 2p 2 p 的网络结构 1p 2 p 的覆盖性 p 2 p 网络构建于现有底层物理网络之上，是现有网络之上的一层覆盖网络 o v a d a yi l e t w o r k 。传统c s 结构中，服务器与客户之间的连接通常依赖于底层物 理网络拓扑，两者之间的通信遵循最短路径原则；而p 2 p 节点之间的通信是覆 盖网络中的最短路径，这可能与底层网络的最短路径不同或是相差很大，因为通 常p 2 p 覆盖网络与底层网络的拓扑区别很大。 这也是本文着重改进的一点，解决物理网络和逻辑网络拓扑适配的问题。如 6 华东师范人学硕上学位论文第二章内容分发网络及p 2 p 概述 图2 3 所示，节点的物理拓扑是一个总线型结构，但上层的覆盖网中，节点的联 系方式显然与物理拓扑结构没关系，相邻最远节点的反而直接联系。改进后使覆 盖层网络的节点获取资源时能够尽可能的选取其在物理距离上邻近的节点上的 资源副本。 图2 3p 2 p 覆盖网络 2p 2 p 的网络结构 从p 2 p 最初的发展至今，其结构几经变化，从体系结构，出现时间角度和 应用领域角度进行分类总共分为四类 7 ，3 4 】：集中式结构，完全分布式非结构化 p 2 p 网络，完全分布式结构化p 2 p 网络和混合式p 2 p 网络。 ( 1 ) 集中式结构 集中式p 2 p 网络是指将资源存放在网络中的节点上，设置一个中心服务器 用来记录资源索引信息，且对等节点之间以及服务器与对等实体之间具有直接交 互能力，通过对中心服务器的索引信息的查询，节点之间进行资源的直接交互。 如代表性软件n a p s t c r 。 集中式p 2 p 系统结构图如图2 4 所示：节点通过服务器获得其他节点信息， 然后可以直接与其他节点进行通信。 7 华东师范大学硕士学位论文第- 二章内容分发嘲络及p 2 p 概述 叶盘渤 j ；c + 一- 下披流 图2 4 集中式p 2 p 结构 ( 2 ) 完全分布式非结构化p 2 p 网络 完全分布式非结构化的p 2 p 网络采用随机图的组织方式形成，每个节点具 有相同的功能，既是客户又是服务器。典型代表是g n u t e l l a ，如图2 5 所示： 砼询流 下袭流 图2 5 完全分布式p 2 p 结构 g n u t e l l a 是一个p 2 p 文件共享系统，它和n a p s t e r 的最大区别是它没有中心 服务器，它采用了完全随机图的泛洪式搜索和随机转发机制。 ( 3 ) 完全分布式结构化p 2 p 网络 基于d h t ( d i s t r i b u t e dh 嬲h1 a b l e ) 技术，将网络中的节点按照一定的方式 分配唯一一个节点标识( p e e ri d ) ，资源对象通过散列运算产生一个唯一的资源 标识符( o b j e c t ) ，且该资源将存储在节点i d 与之相等或者相近的节点上。 需要查找该资源是采用同样的方法可定位到存储该资源的节点。这样一种结构称 为完全分布式结构即d h t 结构。 ( 4 ) 混合式p 2 p 网络 混合p 2 p 形式结合了集中式和分布式p 2 p 的优点，使结构的性能得到优化。 混合式p 2 p 在分布式模式的基础上，根据用户节点能力的不同，使节点担当不 8 华东师范大学硕士学位论文第二章内容分发网络及p 2 p 概述 同的角色，负责不同的任务。混合结构中，总共包含了3 种节点，如图2 6 所示： 普通用户节点；能够处理节点请求的搜索节点；具有索引功能的索引节点。 、。_ - ， 图2 6 混合式p 2 p 结构 2 2 3 结构化p 2 p 网络的搜索技术 盎询流 卜一一一一一一一下载流 基于d h t ，p 2 p 网络中发明了很多优秀的路由协议，如c h o r d ，p a s 咄c a n ， t a p e s 时之类。由这些协议构成的网络中，每个节点都有固定的地址，整个网络 具有相对稳定而规则的拓扑结构。依赖拓扑结构，可以给网络的每个节点指定一 个逻辑地址，并把地址和节点的位置对应起来。对于给定的某个地址，拓扑结构 保证只需要o ( 1 0 9 ( n ) ) 跳就能路由到具有相应地址的节点上去。在实际的系统 中，p 2 p 网络的逻辑地址通常是由h a s h 函数得到的，每个节点都将保存一张d h t 进行路由，所以结构化p 2 p 网络也称为d h t 网络。 2 2 - 3 1d h t 路由原理 基于d h t 的p 2 p 系统中，通过对节点i p 地址或是资源名称的散列获得唯一 标识符。例如标识符p = h a s h ( i p ) ，关键字( k e y ) 可以通过对对象名进行散列来 获得，k _ h a s h ( v ) 。系统中的每个节点拥有一部分散列空间，它负责保存某个范 围的k e y 。在对一个k e y 进行查询后，系统将返回一个保存具有k e y 的对象的节 点的标识符p 。 基于d h t 的搜索实现只要包括4 个关键点【_ 7 1 ，如表2 1 所示： 9 华东师范大学硕十学位论文第二章内容分发刚络及p 2 p 概述 表2 1d h t 搜索关键点 关键点细节描述 散列表的建立散列值的产生使用一个基本的散列函数；节点的标 识符采用节点名字的散列值；对象的标识符采用对 象名的散列值；每个节点存储一张散列表，存储节 点标识符与节点物理地址的映射 内容查找内容通过 对来查找，k e y 在这里对应着 对象的标识符，v _ a l u e 在这里对应文件的名称，所 在的节点的地址信息。 定位关键字所在的节点 将各个节点所具有的 对保存在与对象 标识符相近的节点标识符的机器中，使搜索关键字 代表的对象与节点地址关联上。 对的流动 当有新的节点或新的 对出现时， 将对应的 对转移到对应的节点上；当 旧的节点离开时将其存储的 对转移到 相邻的节点上。 2 2 - 3 - 3 结构化p 2 p 网络的经典路由k a d e m h a 目前典型的d h t 网络包括c h o r d ，p 嬲仃y ，c a n ，k a d e m l i a ，1 a p a s t 珂等， 它们基于不同的d h t 路由算法构建了不同的逻辑拓扑结构。其中k a d e i i l l i a 协议 是原理和实现最简洁和实用的一种，因此在网络中应用最广泛，是当前主流p 2 p 软件采用的辅助检索协议的首选，比如e m u l e ，b i t c o m e t ，b i t s p i 订t 和a z u r 即s 等。 下面将详细介绍k a d e m l i a 路由协议。 首先对五种典型的d h t 路由算法进行比较一下，如表2 2 所示： 表2 2 经典d h t 路由比较 路由算法路由查找效率负载均衡策略抗网络波动 性 1 a p e s t r yo ( 1 0 9 n ) 采用较优的根冗余 不好以波动最差 策略，其路由时动态不彻的情况设计 底，路由相对容易失败。的 p a s 仃yo ( 1 0 9 n ) ，考虑网络的物理拓 不好以波动最差 扑，路由线路尽量选择最小的情况设计 的 c h o r d o ( 1 0 9 n ) 采用虚拟服务以波动最差 器技术负载策的情况设计 略较好，但增加 的 路由延迟 c a n o ( d n ) ，不考虑物理距离不好 以波动最差 的情况设计 的 k a d 锄l i a o ( 1 0 9 n ) ，没有考虑物理网络 一般采用冗余策 距离，采用冗余策略，查找略，抗网络波 速度快动性好 由表2 2 可知，k a d 锄l i a 路由算法平均效率最高，故本文选择k a d e i i l l i a 协 议为网络的基础协议，下面将详细的介绍k a d e m l i a 协议。 k a d e m l i a 协议【1 0 】是美国纽约大学的p e t a r p m a y m o o u n k o v 和d a v i dm a z i e r e s 在2 0 0 2 年发布的一项研究结果 0 ； ( 3 ) 对于任意x ，y ，d ( x ，y ) = d ( y ，x ) ； ( 4 ) d ( x ，y ) + d ( y ，z ) d ( x ，z ) 异或运算具有单向性，那么k a d e m l i a 协议的查找将具有较好的收敛性。 k a d 的路由表是通过被称为“k 桶”的列表构造起来的，每个节点将保存 1 6 0 个列表，每个列表中保存k 个到本节点的距离为2 到2 节点序列，其中 晦i 1 6 0 ，节点序列中记录节点的信息包括 。 “k 桶”的更新策略是：新节点访问本地节点时，本地节点首先根据标识符之 间的异或值确定新节点与本地节点的距离，确定在k 桶中的位置后，更新k 桶： ( a ) 访问节点已存在，将调整节点位置到列表尾部；( b ) 不存在且该桶的节点个数 少于k ，插入列表尾部；( c ) 如果该桶节点大于k 个，则测试该桶中最久未联系 的节点是否还在线，如果在线，访问节点被丢弃不保存；如果不在线，删除旧的 节点保存新的节点到桶尾部。 如此发现，k 桶具有高效的更新机制，可以保持在线时间长的节点更久的保 留在k 桶中。如图2 7 所示的k 桶结构： 华东师范大学硕上学位论文第二章内容分发网络及p 2 p 概述 c 一阮c k e o l i c 吣味e 倒l l c 一c k 哦2 l 妯u d 戚1 15 9 l o 戳孙：【1 ，2 l e 戳洛r e c e n 主耘 渺1 的，2 a 1 6 0 t 覆i l e j 叫) 删 臻。纛r e 偿嗍 图2 7k 桶 ( 3 ) k a d e n l l i a 协议操作类型 k a d e m l i a 协议包括四种远程过程调用( r p c ，r e m o t ep r o c e d u r ec a l l ) 操作： p i n gs t o r e ，f i n p n o d e f i n 唧l u e 。如表2 3 所示： 表2 3k a d e m l i a 协议中的r p c r p c功能描述 p i n g探测一个节点，用以判断其是否仍然在线 s t o r e 通知一个节点存储一个o_|也篁3价叱o上ii|【a口一m叱价皇1价叱 华东师范大学硕十学位论文 第三章基于k a d e m i i a 的内容分发网络的系统结构 以上实验可证在p 2 p 网络资源中存在基于内容的局部性原理。 在对w 曲访问领域的研究发现【4 】，基于相似内容即兴趣的节点之问也存在 局部性原理，即基于兴趣内容的局部性定律如下：如果节点a 和b 曾经访问过 许多相同w e b 内容，那么很有可能节点a 和b 即将访问的内容也有很多重合 之处，则也说明，访问过相同网站的两个节点可能代表两个节点的访问兴趣有一 定的相似度。根据该定律，优化自治系统中的节点查找方式，提高查找效率。 3 2 基于l ( a d e m l i a 的内容分发网络的系统结构 3 2 1 基本概念 在第二章中我们了解到c d n 提供了一种内容分发方法，通过在网络边缘添 加c d n 服务器的方式加速客户端访问站点内容，只要选择距离客户“一步之遥 的c d n 服务器即可提高读取的速度；而p 2 p 提供了一种资源快速查询的方法， 其中k a d e m l i a 又是一种基于异或方式的快速高效的确定资源节点的路由方法。 因此本文吸取该思想并结合前文的研究提出基于改进的k a d e i i l l i a 网络结构的内 容分发网络的系统结构模型l i k a d 。 为了简化研究，我们先设定一些假设： 1 假设一段时间内，源服务器内容的信息暂时稳定，我们不考虑源服务器 内容更新的过程； 2 基于l 觚d m a r k m a c l l i n e 的思想【5 1 ，根据网络中的节点到固定的路标的i 岍 的不同，划分为不同的距离等级，进而将网络划分为k 个区域。 下面我们给出描述系统结构所需要的几个定义： 定义1 系统根据l 趾d m a r k 技术划分的区域称为自治系统。每一个区域获得 一个唯一确定的l 0 c a l i d ； 定义2 自治系统中节点分为索引节点( i n d e xp e e r ) 和客户节点( c l i 咖p e c r ) ， 根据能力的不同，节点在结构中担当不同的角色和任务。 定义3 采用该结构的源服务器站点w s ，根据s h a 1 算法将其域名散列得站 点标识s o u r c e d ； 定义4 每个w e b 文件对象都拥有一个文件标识符m e i d ，f i l e i d 是根据s h a 1 算法将文件u 也，文件大小等信息经过散列单向计算生成。 华东师范大学硕l ：学位论义第三章牿于k a d e m 晒的内容分发例络的系统结构 3 2 2 系统结构的总体设计 系统逻辑结构如图3 5 所示，整个网络的逻辑结构分为三个部分： ( 1 ) 源服务站点层：由特定的互联网内容提供商的源服务器所组成，本文较 为针对具有大量文本信息的公益站点，标记加入该结构中的一组站点 w = w l ，w 2 ，w 3 ，w 4 ) ； ( 2 ) 索引节点层：由分布在各个区域中综合能力比较强的节点组成，每个区 域的节点用h l d e x p e e r 妣a l i d 删。i d 标识，该类型节点在整个结构中起着承 上启下的作用，索引节点在自己所在的区域中为其他节点提供索引；而 索引节点之间构成k a d e i i l l i a 网络结构，通过k a d e m l i a 协议查找资源。 ( 3 )自治节点层：由客户节点组成的自治系统，每一个自治系统内包含该地 区的索引节点和客户节点，这些客户节点处于相同的地区以及对同一站 点感兴趣，形成簇