（通信与信息系统专业论文）对等网络中路由机制及关键技术研究.pdf

摘要 摘要 随着计算机技术以及通信技术的不断发展，以及用户自身存储了越来越多的大量丰富的 具有很高使用价值的内容，整个互联网内容存储的中心渐渐从网络核心移向靠近终端接入用 户的边缘。内容存储方式的转变趋势使得互联网上的内容交换模式也相应发生了巨大的转 变，从传统的基于客户机i n 务器( e l l e n t s e r v e r ，简称c s ) 的内容交换模式演变到如今 的基于对等模式( p e e r t o - p e e r ，简称p 2 p ) 的内容交换模式。 对p 2 p 技术的研究是当前网络界研究的焦点也是工业界关注的热点应用。一般来说，p 2 p 指覆盖在i n t e r n e t 之上的重叠网( o v e r l a yn e t w o r k ) ，系统中的每个节点既是内容的提供 者也是内容的消费者，同时还负责路由、转发来自其它节点的消息请求。按照系统中节点拓 扑结构组织方式的不同，p 2 p 系统可以分为对拓扑结构没有强制要求的非结构化 ( u n s t r u c t u r e d ) p 2 p 网络和对拓扑结构有着较强组织要求的结构化( s t r u c t u r e d ) 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 s ，d h t ) 技术，比 如著名的c h o r d 、c a n 、p a s t r y 、t a p e s t r y 等。由于d h t 技术在扩展性和容错性等方面表现 出来的优点，结构化p 2 p 网络在构建大规模的i n t e m e t 网络应用时得到较为广泛的应用和研 究。但是，如同i p v 4 协议最初提出时未能考虑到地址不够用的这一设计缺陷，p 2 p 技术发 展到现在也暴露出最初设计时忽略的一些问题，其中比较重要的问题包括由于物理网络和重 叠网络不匹配而带来的长寻路延时、：节点负载不均衡以及语义检索时存在的安全性问题，如 何有效的解决这些问题是本论文的研究重点。此外，作为下一代网络标准的i p v 6 协议已经 在国内外得到较为广泛的部署，如何将i p v 6 和p 2 p 这两种新一代网络技术进行有效的融合 也是本论文的研究重点。基于以上的研究背景和研究问题，本论文从d h t 技术的基本工作 原理出发，通过仿真和分析等手段，创新性的做了如下研究： 文中第三章分析了d h t 系统的寻路延时，也即大部分d h t 系统中，k e y 的查找请求都 能够在o ( 1 0 9 n ) 的应用层跳数内得到响应，其中n 是系统中= 常点个数。但是这个跳数只是应 用层上的逻辑跳数，实际它经历的每一跳可能都跨越了多个自治域，从而造成实际寻路延时 过大，寻路效率异常低下。这种寻路低效产生的原因在于这些d h t 系统在最初的设计时忽 略了参与节点在地理上的邻近性，逻辑上邻近的节点在地理上可能相隔多个自治域。我们首 先提出了利用i p v 6 地址前缀进行节点位置聚类的方法。我们注意到不同于i p v 4 地址，i p v 6 地址的格式以及其分配策略都具有很强的层次性，同一自治域内的主机通常具有一定长度的 相同的网络前缀，因而d h t 系统中的= 宵点可以从自己的i p v 6 地址前缀中获取位置信息。接 着提出了一种构建层次化= 竹点标识符的方案c h o r d 6 。我们创造性的提出节点标识符可以 分段构造，标识符的前缀可以通过哈希同一个域中：协点共同的位置信息得到，从而使得物理 网络上临近的：肖点在重叠网络上也互为近邻。最后，从负载均衡的角度出发，提出把：1 ，点的 中国科学技术大学博士学位论文 位置信息存储到d h t 系统中，新加入的节点可以通过d h t 查询到具有相同位置信息的全部节 点列表，从而在物理网络上临近的节点之间构造内嵌于全局d h t 中的本地d h t 。这样，路由 可以先在本地d h t 中进行，必要时经由全局d h t ，从而避免多次跨域路由带来的过长寻路延 时。作为示例，本文利用这种思想对c h o r d 进行了改进，构造了e c h o r d 系统。 文中第四章考察了内容寻址网络( c o n t e n ta d d r e s s a b l en e t w o r k ，简称c a n ) 的负载均 衡特性。我们从实验仿真中发现，对于c a n 而言，若采用其原有的节点加入网络划分负载 区间的策略，会出现网络负载不均衡的现象。由此，我们提出一种新的基于对角线划分：市点 负载区域空间的方案以及一种新的按照文件存储密码进行负载均衡的方案。从实验仿真中可 以看出，这两种方案都能得到比原方案要好的均衡效果。 文中第五章研究了目前p 2 p 网络中语义检索模型的安全问题，提出了一种支持语义检索 的安全模型。现有的基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 模型的p 2 p 网络并不能很好支持语 义查询( 多关键字查询) ，只提供针对某个关键字单一的准确查询，为了实现语义搜索，人 们提出若干基于矢量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 的改进方案，而这些模型 存在各种问题。为此，我们首次分析了p 2 p 中语义网络可能存在的安全问题，阐述了哈希算 法和语义网络之间的固有矛盾；构建一个支持语义搜索的安全内容寻址网络s s c a n ( s e c u r e a n ds e m a n t i cc a n ) ，设计了一种在s s c a n 中进行语义搜索的算法，并对搜索性能进行评估。 该模型具有安全性高，搜索高效的特点。 文中第六章给出了我们和中国科学院声学所共同申请和承担的c n g i ( c h i n an e x t g e n e r a t i o n ：i n t e r n e t ，中国下一代互联网示范二 ：程) 项目中基于i p v 6 的p 2 p 弹性重叠网 络智能节点的研制分项的一个原型系统i n f o s t o r e 6 ，该系统的设计、实现对于本论文以 及其它研究者都有着较高的研究价值。 论文阐述的这些方法和思想都经过了实验( i n f o s t o r e 6 系统的实现) 和l 仿真的验证， 证明了其可行性。这些思想和结论可以应用到未来更多相关p 2 p 产品的开发中，提高p 2 p 产品的性能。 关键词：对等网络，分布式哈希表，c h o r d ，内容寻址网络、查找，寻路，i p v 6 ，寻路延时， 层次化，文件共享 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e ra n dc o m m u n i c a t i o nt e c h n o l o g i e s u s e r s s t o r em o r ea n dm o r ep l e n t yo fv a l u a b l ec o n t e n ti nt h e r eo w nc o m p u t e r ，t h e s er e s u l t s t ot h ec h a n g eo fc o n t e n ts t o r a g ec e n t e rf r o mt h ec o r eo fi n t e r n e tt ot h ea c c e s se n d u s e r t h u st h em o d e lo fi n t e r n e tc o n t e n tt r a n s f e rh a sb e e nc h a n g e df r o mc sm o d e l t op e e r t o p e e rm o d el r e s e a r c ho np 2 pt e c h n o l o g i e sa r et h ef o c u so fn e t w o r ka r e aa n dt h eh o tt o p i c s o fi n d u s t r y g e n e r a ls p e a k i n g ，p 2 pm e a n st h eo v e r l a y n e t w o r ka b o v ec u r r e n ti n t e r n e t ， e a c h n o d ei ns y s t e ma r eb o t ht h ec o n t e n tp r o v i d e ra n dc o n t e n tc o n s u m e r ，a n di s r e s p o n s i b l ef o rt h er o u t i n ga n dd e li v e r yt h em e s s a g e sc o m i n gf r o mo t h e rn o d e s b a s e d o nt h ed i f f e r e n c eo ft o p o l o g yo r g a n i z a t i o n ，p 2 ps y s t e mc a nb ec l a s s i f i e dt o u n s t r u c t u r e da n ds t r u c t u r e dp 2 ps y s t e m t h i st h e s i sf o c u s e so ns t r u c t u r e dp 2 p s v s t e m m o s ts t r u c t u r e dp 2 pn e t w o r k sa r eb a s e do nd i s t r i b u t e dh a s ht a b l e s ( d h t ) ，f o r e x a m p l e ，c h o r d ，c a n ，p a s t r ya n dt a p e s t r y r e l i e do nt h ea d v a n t a g e si ns c a l a b l ea n d f a u l tt o l e r a n c ef e a t u r e so fd h tt e c h n o l o g y ，s t r u c t u r e dp 2 pn e t w o r k sh a v eb e e nu s e d w i d e l yi nd e v e l o p i n gi n t e r n e ts c a l en e t w o r ka p p l i c a t i o n s b u t d u et ot h e s h o r t c o m i n g si ne a r l yd e s i g n ，d h ts y s t e m ss u f f e rs o m ep r o b l e m si n c l u d i n gl o n g r o u t i n gl a t e n c y ，l o a du n b a l a n c ea n ds e c u r i t yi s s u e sw h e nc o n s t r u c t i n gs e m a n t i c s e a r c h h o wt os o l v et h e s ep r o b l e m si so u rc o n c e r ni nt h i st h e s i s a st h es a m et i m e ， i p v 6p r o t o c o li sw i d e l yd e p l o y e di nt h ew o r l d ，h o wt om e r g et h o s et w ot e c h n o l o g i e s i sa l s oo u rc o n c e r ni nt h i st h e s i s w eh a v e d o n es o m en o v e l w o r k si nt h i s t h e s i s ，i n c l u d i n g c h a p t e r3p r o p o s e san o v e lm e t h o dt oe x t r a c tt o p o l o g yi n f o r m a t i o nf r o m i p v 6 a d d r e s sp r e f i x e s w en o t i c et h a ti p v 6a d d r e s s e sa r ea s s i g n e di nah i e r a r c h i c a lw a y s ot h a tn o d e sw it ht h es a m ep r e f i xa r ei nt h es a m ea u t o n o m o u sd o m a i n t h e r e f o r ep e e r s i nad h ts y s t e mc a nl e a r nt h e i rl o c a t i o ni n f o r m a t i o nf r o mt h e i ro w ni p v 6a d d r e s s e s d e v is eas m a r ts c h e m et oe x p l o i tt h e i p v 6a d d r e s sh i e r a r c h i c a lf e a t u r e ，s oa st o c o n s t r u c ta ne f f i c i e n tv e r s i o no fc h o r dd u b b e dc h o r d 6 w ep r o p o s et h a tn o d e i d e n t i f i e r sc a nb ed i v i d e di n t os e v e r a lp a r t sa n dt h u sb ep r o d u c e ds e p a r a t e l y f o r an o d ei d e n t i f i e rd i v i d e di n t ot w op a r t s ，t h eh i g h e rb i t sc a nb eo b t a i n e db yh a s h i n g t h es h a r e da d d r e s sp r e f i xa m o n ga 1 1n o d e sw i t h i nt h es a m ea s a n dt h el o w e rb i t s a r et h eh a s hr e s u l to ft h er e s to ft h ei p v 6a d d r e s s a sar e s u l t ，t o p o l o g i c a l l yc l o s e 中国科学技术大学博士学位论文 p e e r ss h a lla l s ob ea d j a c e n ti nt h eo v e r l a y a ni m p o r t a n ta d v a n t a g eo fo u rs c h e m e ist h a ti t i sv e r ys i m p l ea n db a r e l ym o d i f i e st h eo r i g i n a lc h o r d s i m u l a t i o nr e s u l t s h a v es h o w nt h a to u rm e t h o dc a ns i g n i f i c a n t l yr e d u c ei n t e r d o m a i nt r a f f i ct h a tc a u s e s t h el o n gr o u t i n gl a t e n c y d e v i s ean o v e ls c h e m et oc o n s t r u c te m b e d d e dd h t ，w h i c h c a nn o to n l yi m p r o v et h er o u t i n ge f f i c i e n c y ，b u ta l s oi n h e r i tt h el o a d b a l a n c i n g f e a t u r eo f t h eo r i g i n a ld h t f i r s t ，n o d e si n d e p e n d e n t l yi n s e r tt h e i rl o c a t i o n i n f o r m a t i o ni n t od h ts y s t e m sa st h e yd ow i t hf i l ei n d e x e s t h e n ，an e w l yj o i n e dn o d e c a nu t i l i z ed h tt og e tac o m p l e t el i s t o f a l ln o d e st h a ta r ec l o s et oi ti nt h e u n d e r l y i n gp h y s i c a ln e t w o r k s f i n a l l y ，n o d e sw i t h i nt h es a m ed o m a i n sa r eo r g a n i z e d i n t om a n yl o c a ld h t sw h i c ha r et h e ne m b e d d e di n t oag l o b a ld h tc o m p r i s e do fa lln o d e s t h u s ，r o u t i n gc a nb ec o n d u c t e di nl o c a ld h t sf i r s t ，a n dp a s st h r o u g he a c ho t h e r ( i f n e c e s s a r y ) w i t ht h e a i do f t h eg l o b a ld h t ，w h i c hm e a n st h a t i n t e r d o m a i nt r a f f i c c a nb em i n i m i z e dt ot h ee x t r e m e t oi l l u s t r a t et h ef e a s i b i l i t ya n de f f e c t i v e n e s s o f t h es c h e m e ，w ec o n s t r u c te c h o r du p o nt h eo r i g i n a lc h o r ds y s t e m a n a l y s i sa n d s i m u l a t i o nd e m o n s t r a t et h a to u rs c h e m ei sv e r ye f f e c t i v e c h a p t e r4r e v i e w st h el o a db a l a n c ei s s u ei nc a n w eh a v ef o u n df r o mo u re x p e r i m e n t t h a tt h en e t w o r kw i l ls u f f e rl o a db a l a n c ei s s u ei fk e e p i n gt h eo r i g i ns p a c ed i v i d i n g s c h e m e s o ，w ep r o p o s et w on o v e ls c h e m e s ：1 ) d i v i d et h es p a c eb a s e do nd i a g o n a l 2 ) d i v i d et h es p a c eb a s e do nf i l es t o r a g ed e n s i t y f r o mt h es i m u l a t i o nr e s u l t s ，w e c a nt e l lt h a t ：t h o s et w os c h e m e sw i l lh a v eb e t t e rp e r f o r m a n c et h a tt h eo r i g i no n e c h a p t e r5f i r s tr e v i e w st h es e m a n t i cs e a r c hm o d e li np 2 pn e t w o r k ，a n dt h e ng i v e o u tas e c u r e a n ds e m a n t i cc a n ( s s c a n ) c h a p t e r6d e s c r i b e st h ep r o j e c tt h a tw ed e v e l o p e df o r t h ec n g i ( c h i n an e x t g e n e r a t i o ni n t e r n e t ) p r o j e c t t h ei d e a sa n dp r o t o c o l sp r e s e n t e di nt h i st h e s i sa r ev e r i f i e di ne x p e r i m e n to r r e a ls y s t e m w ee x p e c tt h o s ei d e a sa n dp r o t o c o l sc a nb ew i d e l ya c c e p t e db ym o s to f c u r r e n tp 2 ps y s t e m k e y w o r d s ：p 2 p ，d h t ，c h o r d ，l o o ku p ，r o u t i n gl a t e n c y ，i p v 6 ，t o p o l o g y ，h i e r a r c h i c a l ，f i l es h a r i n g l v 中国科学技术大学博士学位论文 v i i i 图表索引 图1 11 9 9 2 年到2 0 0 5 年全球i n t e r n e t 主机数增长统计( 万) 1 图1 - 2 中国互联网用户人数的增长2 图1 3 中国宽带用户的增长2 图1 4 接入方式趋向于宽带化2 图1 - 5c s 模式，客户和服务器有明确分工4 图1 - 6 对等模型，每个：常点既是客户又是服务提供者5 图1 7 抽象的对等网络功能模型一6 图1 8 典型的非结构化查找方式7 图1 - 9p 2 p 网络的逻辑结构1 1 图2 - 1 标准哈希表结构1 5 图2 2 从哈希表到分布式哈希表：1 6 图2 - 3c h o r d 环1 8 图2 - 4 简单查询过程1 9 图2 5 指针表示例2 0 图2 - 6 扩展查询示例21 图2 ，7 五个节点维护的c a n 虚平面2 2 图2 8c a n 的查找示例2 3 图2 - 9 统一d h t s 的体系模型2 5 图2 1 0 节点的软件体系结构2 8 图2 1 1 通用a p i 接口2 8 图3 1 逻辑号与物理位置之间的失配3 2 图3 - 2 “b i n n i n g ”机制示意3 3 图3 3 层次化的节点分布3 4 图3 4i p v 6 层次化结构以及层次化分配3 6 图3 5i n t e m e t 结构和i p v 6 地址分配的对应3 7 图3 - 6i p v 6 地址格式3 8 图。3 ，7 层次化节点标识符3 8 图3 - 8c h o r d 环中节点分布3 9 图3 - 9c h o r d 6 环中：肖点分布3 9 图3 ，1 0 逻辑层的跳数概率分布4 1 图3 。1l 域从1 到4 0 9 6 时的端到端时延4 2 图3 1 2 节点个数从6 4 增长到4 0 9 6 的端到端时延4 3 图3 1 3e c h o r d 示意4 4 图3 1 4 逻辑层的跳数概率分布4 7 图3 1 5 域从1 到4 0 9 6 时的寻路时延对比4 7 图3 1 6 ：仃点个数增大的情况下寻路时延对比4 8 图4 1c a n 模型中的负载5 1 图4 2 邻居：仃点示意图5 3 图4 3c a n 中k e y 的分布( o k e y l 一5 4 图4 4 仿真平台运行界面5 5 第1 章绪论 图4 5 仿真平台基本结构 图4 6 均衡划分与非均衡划分的比较 图4 。7 初始空间划分和文件分布 图4 8 非均衡划分和文件存储密度均衡的对比 图5 1s s c a n 中的索引搜索过程 图6 1 基于i p v 6 的智能节点弹性重叠网络系统架构 图6 2 智能节点组成弹性重叠网 图6 3自动组网图 图6 4 智能节点功能模块关系 图6 - 5 智能节点( i n ) 模块划分一 图6 - 6 客户节点( c n ) 模块划分 图6 7r o n 节点部署示意图 图6 8r o n 路由优化相关模块一 图6 - 9 智能节点j o i nd h t 流程1 ( 更新自己的路由表项) 图6 1 0 智能节点j o i nd h t 流程2 ( 更新其它节点的路由表& 转移索引) 图6 1 1 智能节点j o i nr o n 流程 图6 1 2 策略数据库结构 图6 。1 3r o n 节点维护的物理路由表_ 图6 1 4 物理路由表的更新一 图6 1 5o v e r l a y 路由表的更新一 图6 1 6 性能数据库内容的定时分发步骤- 图6 1 7 物理路由表内容的分发步骤 图6 - 1 8 动态获取性能数据库内容步骤 图6 1 9 r o n 路由优化报文转发流程 表2 1 各种d h t 网络到统一模型的映射3 0 表3 - 1 不同网络链路的时延4 0 表3 - 2e c h o r d 中的寻路算法4 5 表5 1 查询的基本步骤6 4 表5 - 2 我们设计的泛洪搜索算法6 4 表6 - 1 消息通用格式7 5 表6 2 消息类型汇总7 6 表6 3r o n 路由算法伪代码8 2 i x 弱弱跖甜卯加刀记乃弭乃他力踟趾踞辨辨踮跖髂 第1 章绪论 1 1 论文研究背景 1 1 1 互联网模式的演变 第1 章绪论 近年来，随着计算机技术与通信技术的飞速发展，基于t c p i p 互联网络协议族的i n t e m e t 规模获得了前所未有的扩张，全球i n t e r n e t 入网的主机数、上网的人数都在迅速增长。2 0 0 5 年8 月意大利非盈利机构g a n d a l f 公布的统计数据 1 】显示了i n t e m e t 主机数目持续增长，图 卜l 给出了从1 9 9 2 年到2 0 0 5 年i n t e r n e t 入网主机数的增长曲线。按照平稳的增长方式，可 以预计到2 0 0 7 年间，z n 主机总数将达到5 0 0 ，0 0 0 ，0 0 0 台 4 。 5 0 0 4 0 0 3 0 0 2 0 0 1 0 0 0 掣i；誊至 譬 差善耋三謦 茎三 答 oo3z33z0ooooo 一一一一一一一一n nnn + i n t e r n e t 主机数目( 百万) 图1 11 9 9 2 年到2 0 0 5 年全球i n t e r n e t 主机数增长统计( 万) 中国互联网信息中一l 二, 2 1 2 0 0 6 年1 月1 7 日公布的第十七次中国互联网络发展状况统计报 告 3 显示，截至2 0 0 5 年1 2 月3 1 日，我国上网用户总数突破l 亿，为1 1 1 亿人，其中宽带 上网人数达到6 4 3 0 万人。目前，我国网民数和宽带上网人数均位居世界第二。图卜2 给出 了中国互联网川户从2 0 0 1 年起的增长趋势。从中可见我国网民总数的增长是迅速，但1 1 1 0 0 万网民在我国将近1 3 亿的总人口中还仅占8 5 ( 与0 4 年同期的7 2 相比，有所提高) 。 这说明尽管我国的i n t e m e t 用户总数很火，增长速度较快，但i n t e r n e t 的普及程度和对社会 方方面面的渗透的程度目前还很低，但其发展空间仍非常大。同0 4 年的调查相比，宽带上 网用户人数半年增加了1 0 2 0 万人，增长率为2 3 8 ，和上年同期相比增长7 1 0 ( 如图卜3 所示) 。宽带上网用户首次超过了拨号上网用户人数，并首次超过了网民的一半。可以看出， 虽然我国上网川户总数在快速增长，但是拨号上网用户人数、专线上网用户人数、i s d n 上 网用户人数首次出现了负增长，只有宽带上网用户人数还保持着非常快的增长趋势( 如图 卜4 所示) ，这说明中国网民正在加速向宽带的迁移 3 。 中国科学技术大学博士学位论文 3 0 0 0 0 2 5 0 0 0 2 0 0 0 0 1 5 0 0 0 i 0 0 0 0 5 0 0 0 o 4 0 0 0 0 3 5 0 0 0 3 0 0 0 0 2 5 0 0 0 2 0 0 0 0 1 5 0 0 0 1 0 0 0 0 5 0 0 0 o 2 0 0 l2 0 0 22 0 0 32 0 0 12 0 0 5 2 0 0 6 p2 0 0 7 p 州叭2 0 此0 0 32 0 0 d2 i 】0 5 。2 0 0 铀2 t 1 0 7 9 e 卫中国互联网用户数量( 万) 辫一增长率匠l 中国宽带用户数量( 万) 舜一增长率 图1 2 中国互联网用户人数的增长 图1 3 中国宽带用户的增长 图1 4 接入方式趋向于宽带化 2 0 0 4 年我国正式启动了中国下一代互联网专项( c n g i ：c h i n a n e x t g e n e r a t i o n i n t e m e t ) 6 ，该专项由中国发展改革委员会牵头，联合各大部委，汇集了运营商、设备制造商，将 建成全球最大的i p v 6 7 f f 。联网，中国互联网的发展成为了全球下一代互联网协议发展的巨 大引擎。从中可以看到，互联网建设和研究的浪潮正在逐步的迁移到基于i p v 6 协议的下一 代网络。这正是本论文研究的一大背景。 随着计算机存储技术的发展，磁盘单碟存储容量越来越高的同时价格越来越低，这使得 人们能够以很低的价格获得超大容量的存储空间。如今，不从文件备份和商业的角度考虑， 人们完全可以不依赖于i d c ( 互联网数据中心) 服务器，而将自己感兴趣的所有的影像、音 乐、软件和文档等内容存储在本机上。这种存储模式的转变改变了互联网“内容”所在的位 置。内容正在从“中心”走向“边缘”，也就是说内容将不是存在于儿个主要的服务器上， 而将存在于每个用户的电脑上。即互联网的存储模式，将由现在的“内容位于中心”模式转 变为“内容位于边缘”模式。在这种模式卜，边缘数据如何有效的共享利高效的检索就成为 本论文的一人研究内容。 2 第1 章绪论 位于网络接入端的计算机除了具有大容量的存储空间外，其c p u 的处理能力也非常的 可观。但是，从中国互联网络信息中心 3 历年来的统计调查结果可以看出用户计算机的使 用效率极低，c p u 大部分时间处于空闲的状态，这无疑是计算资源的巨大浪费，如何有效 利用这些计算资源成为一个热点问题。与此同时，计算速度每1 8 个月翻一番，网络速度每 9 个月翻一番，差不多每5 年差一个数量级 7 。利用快速发展的网络技术将各种计算资源 整合到一起，从而实现高性能的分布计算和资源的高效利用，其可行性及迫切性已经被广泛 认同。伴随着存储模式、计算机性能及其网络速度的快速增长，互联网的计算模式演变经历 了三个阶段，也即从早期的大型机模式发展到目前使用普遍的客户n 务器模式，以及被看 作是下一代网络模型的对等模式( p e e r t o p e e rm o d e l ) 。下面分别对这三种模式做简要的背 景介绍。 1 1 1 1 大型机模式 从1 9 6 9 年计算机网络的诞生到上个世纪8 0 年代个人台式机产生以及大量普及之前， 大型计算机占据主导地位。这些大型机的数目有限且价格昂贵，人们通过终端连接并且使用 这些大型机。我们称以大型机作为标志的计算模型为大型机模式。在这种模式下，终端没有 处理能力，只能用于输入数据和显示信息。用户为了对数据进行处理必须和大型机相互交互。 为了尽可能地使用这种昂贵的计算机，一般采用多个作业集中到一台计算机上的集中处理方 式，从而使主机系统资源得到最大的利用。 该模式的缺点是： 主机负载太重，系统可靠性、可用性主要依赖主机； 主机价格过于昂贵； 功能扩展因难； 潜在单点故障等。 1 1 1 2 客户n 务器模式 由于大中型计算机价格昂贵，而微型计算机的性能逐步提高和价格的进一步下降，人们 越来越希望用廉价的微型计算机代替火中型计算机系统，让用户的任务在不同的计算机上分 布进行并统一管理。上世纪七八十年代，客户机j e 务器模式( c l i e n ts e r v e r ，c s ) 8 开始发 展。在这种模式中，系统分成两大部分服务器和客户机。c s 的基本： 作方式是客户机 发出请求，服务器接收请求并进行分析处理，然后将处理结果返回给客户机( 见图卜5 ) 。 从上世纪9 0 年代开始，客户机朋艮务器模式开始流行。目前，这种计算模式已经是市场上的 主流。该模式包括客户机文件服务器、两层c s 、多层c s 以及浏览器n 务器等儿种类别。 3 中国科学技术大学博士学位论文 客户机 图1 - 5c s 模式，客户和服务器有嘲确分工 在该模式中，客户机具备一定的计算能力，但主要工作还是依赖于服务器来完成。由于 客户机n 务器模式将任务分布在多台机器上并行执行，因此系统有更好的性能。 虽然客户机服务器模式克服了主从模式的设备成本高等缺点，但仍存在以下缺点： ( 1 ) 由于在c s 模式下，客户机提交请求，服务器同时为多台客户机提供服务并处理 客户机的请求，因此服务器仍是性能瓶颈。 ( 2 ) 可伸缩性差：服务器的处理能力决定了系统的最大工作负载，而服务器的处理能 力很难有效伸缩。 ( 3 ) 容错性差：服务器易成为单点故障点。 ( 4 ) 缺乏灵活性：用于客户机和服务器通信的协议是硬编码的；客户和服务器之间的 角色分配在设计时就已经决定；系统的功能很难扩展和升级。 1 1 1 3 对等网络模式 随着计算机处理能力的进一步增强，当前市场上任一台新生产的计算机都可作为服务 器。在这样的背景下，计算模式从客户机服务器模式逐步演变到对等计算模式 8 1 1 4 1 。对 等( p e e r - t o p e e r ，p 2 p ) 网络目前还没有一个明确的定义，其中的每个节点不是严格的划分为客 户机或服务器。对等网络的每个节点既是客户机，义是服务器，还是路由器( 见图1 - 6 ) 。 p 2 p 系统中的各个节点因为互为服务而共存，而不是依赖与特定的集中式机制。而且，各个 节点可以直接交互并可能随时离开对等网络。 4 第1 章绪论 对等体 图1 - 6 对等模型，每个节点既是客户又是服务提供者 对等网络的以下特征使之与传统系统相区别： 节点之间通过直接交互共享资源； 资源分布在各个节点中，而不是集中在一个服务器中进行管理； 节点具有动态性与自组织性( a d h o c 模式) ；： 纯粹的p 2 p 系统没有任何集中控制机制。系统的各：肖点运行的p 2 p 系统软件功能 相同，各节点之间交互对称。 1 1 2 对等网络概念及其分类 p 2 p 对等网络本质上是一种分布式的系统，它没有任何层次化结构或集中式控制点。节 点之间形成了在i n t e r n e t 网络之上的自组织重叠( a d h o co v e r l a y ) 网络，提供了各式各 样的特性，比如鲁棒性的全局路由结构，高效的数据条目搜索，近邻：市点的选择，冗余性存 储，持久性，层次化域名，信任和认证，匿名性，巨大的伸缩性汞i 容错性。如前所述，对等 系统中二悼点具有服务使用者、服务提供者以及路由提供者这三重角色，从而超越了客户n 务器系统提供的服务。它允许其它系统对其资源的访问并且支持容错性，自组织以及巨大可 伸缩性等特性的资源共享需求。不同于g r i d 系统 1 5 ，p 2 p 对等网络并不是在已建立的互 联组系统之间进行协作并且并没有稳定可靠资源进行共享。 5 中国科学技术大学博士学位论文 图1 7 抽象的对等网络功能模型 我们可以把p 2 p 对等网络模型看成一个扩展到多个层的通信框架，这描述了一个完全分 布式的，协作式的网络设计，其中节点之间构成了一个自组织的系统。图卜7 描述了一个 抽象p 2 p 对等网络体系结构，给出了对等网络的组件通信框架。网络通信层描述了网络层特 征。节点的动态性给通信方式增加了很多难度。o v e r l a y 层上的节点管理层负责对节点的管 理，这包括节点发现，优化的路由算法。特征管理层包括安全管理、可靠性和容错性管理以 及对可用资源的聚集管理，以此维护p 2 p 系统的鲁棒性。服务特定层对下层的p 2 p 体系结构 以及和应用层相关的组件提供支持，这通过对计算敏感的并行任务、内容和关键管理进行调 度实现。元数据描述了存储在p 2 p 节点上的内容以及位置信息。应削层和上层提供的工具、 应用以及服务依赖于p 2 po v e r l a y 层具体的功能实现。目前有两类p 2 p 对等网络：非结构化 ( u n s t r u c t r u e d ) p 2 p 网络以及结构化( s t r u c t u r e d ) p 2 p 网络 3 6 卜 4 0 。 1 1 2 1 非结构化对等网络( u n s t r u c t r u e dp 2 pn e t w o r k ) 非结构化对等网络中：常点的放置不受控制。目前使用得较为广泛的非