（通信与信息系统专业论文）基于chord的服务标识解析系统的仿真与性能分析.pdf

中文摘要 中文摘要 摘要：随着当今互联网中服务资源数量的急剧膨胀，日益多样化的网络服务缺乏 统一的管理模式，新型服务发展受到旧体系架构的制约，d n s 更新速度慢，系统 配置复杂，不支持移动性，传统的服务资源管理模式已经逐渐不能满足用户的需 求。 “一体化可信网络与普适服务体系基础研究 项目提出了一个标识网络的概 念，把网络分为“网通层 和“服务层 两层。其中“服务层”中的服务标识解 析系统很好的解决了传统互联网中存在的一些问题。在一体化网络中，服务标识 解析系统负责分配、管理服务标识，并为每种服务都分配一个唯一的服务标识， 统一由服务标识解析系统管理。服务标识解析系统采用分布式结构，这种结构对 服务的描述和表达能力强，支持数据移动性，鲁棒性好，支持负载均衡，配置方 便。服务标识解析系统路由采用c h o r d 算法，每台服务器之间形成了一种对等关 系，这种管理方式在当前小规模应用中已经发挥了一定优势。 本文首先分析了当前服务标识解析系统一次查询中产生的三种不同时延，随 后通过仿真将三种时延叠加确定了影响系统查询效率的主要时延。针对这种时延， 本文提出了在基于c h o r d 的服务标识解析系统中加入缓存机制的改进方案。增加 缓存机制的核心思想是牺牲一部分系统容量来提升服务查询效率。在现有系统设 计中，用户的查询请求都要通过路由算法经过n 个中间服务器到达服务标识存储 服务器。经过改进，每次用户的查询结果通过递归回复消息存储在经过的每台服 务器的缓存文件中，下次同样的请求只要经过其中的任何一个服务器，就可以直 接得到结果，无需最终路由到服务标识存储服务器。本文针对当前网络服务资源 访问分布的实际情况，在仿真环境中实现了相应的查询请求模块，模拟了数百台 服务标识映射服务器，设计了获取统计数据的方法，并且根据不同资源访问量逐 步改进缓存机制，最后对加入缓存前后的服务标识解析系统性能进行了对比分析。 仿真结果表明，服务标识解析系统的查询效率有所提升。 关键词：一体化网络；服务标识；名字解析；缓存机制 分类号：t p 3 9 3 0 4 a b s t r a ( 玎 a bs t r a c t a b s t r a c t ：a st h er a p i de x p a n s i o no ft h eq u a n t i t yo fr e s o u r c e si nt h ec u r r e n ti n t e m e t ， e v e r yk i n do fs e r v i c e sh a si t so w ns t y l eo fm a n a g e m e n t ，s ot h e r ei sn ou n i v e r s a ls o l u t i o n n e wk i n d so fs e r v i c e sa r er e s t r i c t e db yt h eo l dn e t w o r ka r c h i t e c t u r e d n sh a saf e w s h o r t c o m i n g sa su p d a t i n gi ss l o w , s y s t e mc o n f i g u r a t i o ni sc o m p l i c a t e d ，a n dm o b i l i t yi s u n s u s t a i n a b l e t h ep r o j e c t “af u n d a m e n t a lr e s e a r c ho nu n i v e r s a lt r u s t w o r t h yn e t w o r ka n d p e r v a s i v es e r v i c e p u t sf o r w a r dan e wc o n c e p to fi d e n t i f i e rn e t w o r k i td i v i d e st h e i n t e r n e ti n t ot w ol a y e r sn a m e d “s e r v i c el a y e r a n d n e t w o r kl a y e r s e r v i c ei d e n t i f i e r ( s l d ) r e s o l v i n gs y s t e mi nt h e “s e r v i c el a y e r s o l v e ss o m ep r o b l e m so ft r a d i t i o n a l n e t w o r kw e l l i nt h eu n i v e r s a ln e t w o r k , s i dr e s o l v i n gs y s t e mt a k e sc h a r g ei n d i s t r i b u t i n ga n da d m i n i s t e r i n gs i d ，a n de a c hs e r v i c eh a so n eu n i q u es i da n dt h es i d r e s o l v i n gs y s t e mi si nc h a r g eo ft h a t t h es i dr e s o l v i n gs y s t e ma d o p t sd i s t r i b u t e d s t r u c t u r e t h es i dr e s o l v i n gs y s t e ma d o p t sd i s t r i b u t e ds t r u c t u r e i th a saf e wb e n e f i t sa s f o l l o w s ：g o o dp e r f o r m a n c eo nd e s c r i b i n ga n de x p l a i n i n gs e r v i c e s ，s u s t a i n a b l em o b i l i t y , r o b u s t n e s s ，s u s t a i n a b l el o a db a l a n c e ，e a s yt oc o n f i g u r e s i dr e s o l v i n gs y s t e ma d o p t s c h o r da l g o r i t h m ，s ot h es g r v e r sa r ep e e rt op e e r t h em a n a g e m e n tm o d e lh a sp e r f o r m e d w e l li nt h ec u r r e n tl i m i t e de n v i r o n m e n t f i r s t l y , t h i sp a p e ra n a l y z e st h r e ek i n d so fd e l a y so ft h es i dr e s o l v i n gs y s t e m ，a n d t h e ni tf i n d so u tt h ek e yd e l a yw h i c ha f f e c t st h ee f f i c i e n c yo fq u e r yv i as i m u l a t i o n t o w a r dt h i s 虹n do fd e l a y , t h i sp a p e rp u t sf o r w a r dap l a no fa d d i n gc a c h em e c h a n i s mi n t h es i dr e s o l v i n gs y s t e m t h ec o r ei d e ao fa d d i n gc a c h em e c h a n i s mi st oi m p r o v et h e e f f i c i e n c yo fq u e r yb ys a c r i f i c i n gp a r to ft h es y s t e mc a p a c i t y i nt h ed e s i g no ft h e c u r r e n ts y s t e m ，w ea s s u m et h a ti th a st op a s s1 1h o p sb e f o r et h eu s e r sr e q u e s tg e t st ot h e o b j e c ts e r v e ra c c o r d i n gt ot h ea l g o r i t h m t h ei m p r o v e dm e t h o di s ：s a v i n gt h eq u e r y r e s u l ti nt h ec a c h ef i l eo fe v e r yp a s s e ds e r v e rb yt h er e c u r s i v er e s p o n s em e s s a g e s oi f t h es a m er e q u e s ta r r i v e sa ta n ys e r v e ra b o v e , i tw i l lo b t a i nt h er e s u l td i r e c t l y , a n dd o e s n o th a v et og e tt ot h eo b j e c ts e r v e r c o u n t e r i n gt h ep r a c t i c a ls i t u a t i o no fr e s o u r c e sa n d s e r v i c e sr e q u i r e m e n td i s t r i b u t i o n , t h i sp a p e ra c h i e v e st h eq u e r yr e q u e s tm o d u l e ， s i m u l a t e sh u n d r e d so fs l dr e s o l v i n gs e r v e r s ，d e s i g n sam e t h o dt og a i ns t a t i s t i c ，a n dt h e n g r a d u a l l yi m p r o v et h ec a c h em e c h a n i s mb a s e do nd i f f e r e n ta m o u n to fv i s i t i n go f s e r v i c e s a tl a s t ，w ea n a l y z et h ep e r f o r m a n c eo fs i dr e s o l v i n gs y s t e mi nc o n t r a s to f v 北京交通大学硕士论文 a d d i n gc a c h em e c h a n i s mb e f o r ea n da f t e r t h er e s u l to fs i m u l a t i o ns h o w st h a tt h e e f f i c i e n c yo fq u e r yo f s i dr e s o l v i n gs y s t e mi si m p r o v e do n a l a r g es c a l e k e y w o r d s ：u n i v e r s a ln e t w o r k ；s e r v i c ei d e n t i f i e r ；n a m er e s o l v i n g ；c a c h em e c h a n i s m c l a s s n o ：t p 3 9 3 0 4 北京交通大学硕士论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：习l l 遥 签字日期：少队7 年 钥2 。日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 警翮挺 签字日期：7 1 年6 月2 一日 导师签名： 冬1 以 l 签字日期：少尸年石月矽e l 致谢 本论文的工作是在我的导师秦雅娟副教授的悉心指导下完成的，秦雅娟副 教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢 两年来秦雅娟老师对我的关心和指导。 罗洪斌副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向罗洪斌老师表示衷心的谢意。 张宏科教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。同时，感谢张思东老师、周华春老师、杨冬老师、董平老师在我的科 研和生活中给予我的无私帮助和诚挚的关怀。 在实验室工作及撰写论文期间，吴恒奎、林福宏、张莹、黄道超、王士博、 梁听等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之 情。 另外也感谢家人和我生活中的朋友，他们的理解和支持使我能够在学校专心 完成我的学业。 引言 1 引言 本文以一体化网络为背景，进一步研究在原型系统中的服务标识解析系统的 性能问题。本文通过理论分析以及仿真，逐步挖掘出真正影响服务标识解析系统 性能的主要因素，从而增加新的机制来提高系统性能，并给出了仿真结果分析。 1 1 研究背景与意义 i n t e r n e t 历史邮件列表显示，i n t e r n e t 的设计问题最先出现在7 0 年代，并于9 0 年代再次出现，现在i n t e m e t 的设计问题重新出现在i e t f 的邮件列表中成为讨论 热点。原始互联网基于端到端原理和尽力发送模型设计，取得了巨大的成功，但 是随着互联网的发展，各种新业务不断涌现，n a t 、防火墙等网络中间件【1 】逐渐普 遍，互联网本身隐藏着的弊端逐渐显现出来。 当前的d n s 域名解析方式不支持数据的移动和复制。数据的获得和服务的接 入是当前互联网最主要的应用。随着互联网的发展，数据的移动和复制越发频繁， 这就给当前以主机为中心的域名解析方式提出了新的挑战。用户关心的是数据本 身而不是数据或者网络服务所在的位置。基于当前的d n s 域名解析方式，当一个 网页从一个主机移动到另外一个主机时，将会出现断链现象【2 j 。h t t p 重定向或者 动态d n s 可以部分解决这一问题，但是并不彻底和高效。 当前i n t e r n e t 架构设计不支持服务移动性。d n s 的出现晚于i n t e r a c t 的设计， 一次t c p 3 】连接绑定的是妒地址而不是服务名称，d n s 更像是互联网设计的一次 事故而不是互联网架构的一部分。同时随着互联网络的不断发展，用户对服务性 能的要求越来越高，用户希望从同一服务的不同提供者中选择位置近、负载轻、 性能好的服务器提供服务，并且当服务发生移动时，用户体验不中断。这在动态 和移动网络环境下尤为重要。但是当前负载过重、服务模式单一、更新速度慢、 资源描述能力不强的d n s 不能胜任这一任务。 日益普遍的网络中间件破坏了互联网的层级结构。最初的互联网是基于端到 端原理设计的，核心网络只负责数据包的转发，不侦查、过滤或者改变数据包的 内容，服务目的将在网络边缘实现。这种开放性、透明性的设计理念，使得不需 要改变核心网络就可以容易地部署一项新的应用，是互联网取得今天巨大成功的 最重要因素。但是随着发展，i n t e r n e t 已经成为一个巨大的产业。在商业和安全的 双重压力下，互联网结构正在发生变化，中间件和各种接入策略开始变得越来越 普遍。这是用户、网络服务提供商和社会斗争的结果，任何精巧的网络设计都不 北京交通大学硕士论文 可避免三者之间的斗争。中间件的出现，一方面解决了商业和安全方面的问题， 同时也破坏了互联网的层级结构，破坏了互联网的开放性和透明性。 为了适应互联网的变化，以及下一代互联网设计的要求，“一体化可信网络与 普适服务体系基础研究 项目提出了平面服务标识以及服务标识映射机制，构建 以数据为中心的一体化网络架构。通过平面服务标识，统一标识了数据和网络服 务，解决了数据的移动和复制问题；通过服务标识映射机制，建立新的服务信息 到连接信息的映射规则，解决了服务的移动性问题，并融合网络中间件。设计包 括分层的名字空间，分别是用户描述、服务标识( s i n ) 、连接标识( c i d ) 、接入标 识( a i d ) 和交换路由标识( r i d ) 4 1 1 5 1 。用户描述包括关键字、e - m a i l 地址、s i p 用 户名等，由用户级处理；服务标识为1 6 0 位哈希值，用于区分不同的数据或者网 络服务，由应用程序处理【6 】。原型系统包括3 级映射，服务标识到连接标识映射、 连接标识到接入标识映射以及接入标识到交换路由标识的映射。 本文的后面章节主要任务在于介绍一体化网络中的服务标识解析系统的重要 性以及如何改进其性能。 1 2 国内外研究现状 对于一体化网络中的服务标识解析系统的研究是基于传统互联网中的名字解 析机制。本小节的主要任务是介绍下一代互联网体系架构研究方面的发展以及当 前网络的域名解析机制和一体化网络中的标识解析方案。 1 2 1下一代互联网体系架构的发展 近年来，随着通信技术的不断发展和计算机的普及，电信业务发展迅猛，以 互联网为代表的新技术革命正在深刻地冲击着传统电信业的概念和体系。现有信 息网络的一种网络支持一种主要服务的原创模式及其演进方案，严重阻碍着信息 网络技术的高速发展。为了解决这些严重弊端，新的网络体系结构成为目前研究 的热点。美国国家科学基金委( n a t i o n a ls c i e n c ef o u n d a t i o n ，n s f ) 在2 0 0 5 年提出了 著名的全球网络调研环境( g l o b a le n v i r o n m e n tf o rn e t w o r ki n v e s t i g a t i o n , g e n i ) 7 1 ， 其主要研究目标是要重新思考网络的功能，设计新的网络体系结构和服务。未来互 联网设计项目( f u t u r ei n t e m e tn e t w o r kd e s i g n ，f i n d ) 是n s f 于2 0 0 5 年底推出的 一个新的长期计划，认为未来互联网在服务方面应该重新设计，网络服务应更加 接近人们的生活，实现普适化。一体化网络与普适服务体系就是新网络体系结构 的一个研究项目，其对现有网络改进的重点在于支持多种服务，解决现有信息网 2 引言 络在服务扩展、安全性和移动性等方面存在的问题。 国家9 7 3 项目“一体化可信网络与普适服务体系基础研究定义了一个新的 标识网络。一体化网络与普适服务体系是一种不同于开放式系统互联参考模型 ( o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l ，o s i r m ) 七层网络体系和互联网 四层网络体系的新型网络体系结构。它包括“网通层 和“服务层”两大部分， 如图1 1 所示。 应用层 卜 应用层 表示层 会话层服务层传输层 、 传输层网通层网络层 网络层 数据链路层 、 数据链路层 物理层 f n、 图1 1 一体化网络与普适服务体系结构模型 f i g 1 - 1a r c h i t e c t u r em o d e lo fu n i v e r s a ln e t w o r ka n dp e r v a s i v es e r v i c e s 服务层的位置处于整个一体化网络体系结构中的上层，因此它的主要研究内 容是针对网络中各种各样的服务。在这层中有两个标识，两次映射。 图1 2 一体化网络“服务层”标识映射模型 f i g 1 - 2i d e n t i f i e rm a p p i n gm o d e lo f t h e8 e l w i c el a y e ro fu n i v e r s a ln e t w o r k 新网络体系结构中服务层的新模型如图1 2 所示，新模型引入虚拟服务模块和 虚拟连接模块，以及服务标识解析映射和连接标识解析映射。 一体化网络普适服务体系，引入统一的服务标识( s i d ) 。s i d 是一体化网络 中资源( 包括服务和数据) 的统一标识，为1 6 0 比特的哈希值。s i d 本身不含语义。 ( 将具有语义的描述信息映射到s 1 d 是架构之外的内容，属于一体化搜索引擎的 范围。所谓一体化搜索引擎，是指切实考虑服务和数据的相互联系，进行一体化 北京交通大学硕士论文 搜索，所得结果包括服务和数据两种类型的s i d 。) 如上所述的s i d 采用哈希算法扁平名字的实现方式对应于传统d n s 模式有几 个优点，主要表现在：存储标识的系统结构可采用更多的网络体系，增强了网络 名字的可扩展性和健壮性；消除了由于域名的归属权问题产生的纠纷；增强了网 络安全性，消除了地址篡改欺骗，d o s 8 j ( d e n i a lo f s e r v i c e ) 攻击等问题。 s l d ：0 x 4 5 d 4 f 6 5 4 d 6 5 f 4 6 5 8 d 4 f 6 5 d 4 6 5 f 4 6 5 d f 6 a d ( 1 6 0 b i t ) 映射条目：( a i d1 ，p o r t ，t y p e o f t r a n s m i s s i o n ) ； ( a i d 2 ，p o r t ，t y p e o f t r a n s m i s s i o n ) ； 映射 ( a i d n ，p o r t ，t y p e o f t r a n s m i s s i o n ) ； ( s i d i ，s i d 2 ，s i d n ) ； 附加信息：元数据，q o s 信息等 t t l ：注册缓存信息的有效时间 图1 - 3 服务标识映射结构 f i g 1 - 3s e r v i c ei d e n t i f i e rm a p p i n gs t r u c t u r e 服务标识和连接标识的映射表如图1 3 所示。其中，服务标识s i d 是个1 6 0 比 特的哈希值。服务标识到连接标识的映射可以包括服务标识到接入标识( a i d ) 信息 的映射，服务标识到服务u r l 的映射，以及将复杂服务映射成多个原子服务类型 等。映射的内容也包括相应服务的q o s 信息，注册信息的有效时间t t l ( t i m e t ol i v e ) 等。除了提供简单的一对一映射，服务映射系统还提供一对多映射，包括并行和 串行两种，其中并行一对多映射是指从一个服务标识到多个独立连接标识的映射， 串行一对多映射是指从一个服务标识到完成一次服务而关联的多个服务标识的映 射。服务映射系统很好地支持了数据的复制，经过复制的数据，其本身的s i d 并 不发生变化。服务提供商可以重新注册数据的信息提供服务。由于s i d 标识相同， 服务映射系统只需在连接信息中添加新的连接信息即可。用户查询s i d 标识时， 将得到多个连接信息。用户可以选择其一进行连接，也可以同时获取多个信息进 行连接，这将取决于具体的服务，比如说p 2 p 文件下载，将可以选择多个信息进 行连接。 1 2 2 域名解析及一体化网络中的标识解析机制 我们知道，当前的互联网中有两种标识主机的方式，即通过主机名或者i p 地 4 引言 址进行识别。人们喜欢便于记忆的主机名，而路由器则喜欢定长的、有着层次结 构的口地址。为了折中这些不同的偏好，域名系统( d o m a i nn a m es y s t e m ，d n s ) 应运而生。d n s 是一个由等级制分层的名字服务器实现的分布式数据库，同时也 是个应用层协议，为了提供主机名到m 地址转换的服务而允许主机与名字服务 器进行通信。d n s 的结构如同一棵倒挂着的树，它允许整个数据库的各个部分进 行本地控制。同时整个网络也能通过客户服务器方式访问每个部分的数据，借助 备份和缓存机制，d n s 系统将变得更强壮和拥有足够的性能。名字服务器通常是 运行b i n d ( b e r k e l e yi n t e r n o tn a m ed o m a i n ) 软件的u n i x 机器。 虽然d n s 在i n t e m o t 普及上有着重要的贡献，随着网络技术的发展d n s 自身 也在不断完善【9 】【1 0 1 【1 1 1 ，但d n s 系统架构有一些先天无法克服的缺点。d n s 使用相 对集中的管理方式，极大地限制了服务的灵活性。d n s 本身采用树形的结构层次， 使得其在数据的更新上有很大的延时。d n s 域名都是由d n s 区域层的网络管理员 来管理，不支持针对每个域名的管理结构，除网络管理员之外的个人不能创建或 者管理d n s 域名。随着信息技术飞速发展，各种服务如雨后春笋般涌现出来【12 1 ， 其中的一些服务无法再应用d n s 来很好地为服务需求者提供服务，如p 2 p s i p 服 务。可以说d n s 制约了新服务的应用。域名带有语义f 1 3 】，不可避免涉及到所有权 归属问题，从而带来不必要的法律纠纷，如w w w 1 i u x i a n g t o m 是否可以被刘翔以 外的人注册。d n s 是面向主机的，当主机的数据移动或复制后，d n s 无法再次为 该数据提供服务【1 4 】。由于业务需要，负责t o m 域名的d n s 服务器相对于负责o r g 等d n s 服务器负载重很多，服务器之间没有相互协调充分利用网络资源【l 5 】蛙 鉴于d n s 的这些无法克服的困难，国家“9 7 3 ”项目一体化可信网络与普适服务 体系基础研究将传统互联网分为两个部分，一部分是服务层，另一部分是网通层。 在原型系统中服务层的核心设备就是服务标识解析系统，也叫服务标识映射服务 器。这种解析系统在新的标识网络中与d n s 在传统网络中起到的作用相似。它用 来存储服务标识到接入标识之间的映射关系，它解决了传统d n s 集中化的固有缺 点。 我们利用分布式网络来构建服务标识解析系统模型。前文中提到d n s 系统存 在资源描述能力不足、更新速度慢、配置复杂等方面的弱点，与其网络结构有很 大的关系。利用分布式网络保存服务信息从根本上改变了现有网络名字解析系统 层次的树状结构。分布式网络中保存的关于服务的描述信息可以不受现有d n s 协 议的限制，特别是在一体化网络体系中，我们将名字解析的对象变为服务标识， 不需要经过主机这一环。用分布式来设计名字解析服务器网络可以为系统设计带 来以下优点： 1 对数据和服务的描述和表达能力强，这个特点继承了服务标识的固有优 北京交通大学硕士论文 点。用户可以将资源和服务的很多属性与服务标识一起注册在名字解析系 统中，如服务的类型属性、服务q o s 和服务简单描述。这使得用户可以直 接关注它们需要的数据和服务的位置变化和性能变化，而不是仅仅按d n s 的域名到口的查找，以及其它简单服务信息的扩展查找 2 支持数据移动性，也就是可以很好的支持动态数据和服务的查找。由于每 项数据和服务都有其唯一的服务标识，名字解析系统是以数据为中心而不 是以主机为中心。当数据或服务发生移动时，用户通过定位服务标识可以 迅速地查找到资源。名字解析的过程不需先由u r l 解析到主机，再由主 机找到资源 3 系统鲁棒性好，这是分布式网络本身的优点。在系统中，通过上层软件和 下层特殊算法路由层的交互，可以发现解析成功与否，从而及时发现解析 中可能存在的错误 4 支持负载均衡，这也是分布式网络本身的优点。因为服务标识在网络中的 分布是基本均匀的，所以不会出现热点问题 5 配置方便，这是相对于现有d n s 系统的一个特点。第二章曾经提到过， 现有d n s 系统存在的很多问题都起源于配置问题。因为分布式网络的自 组织特点，系统需要的人工配置过程极少，提高了系统的可用性 以上都是利用分布式网络来设计名字解析系统的一些优点。另一方面，这种 名字解析系统也存在一些缺点，随着网络规模的扩大查找效率会降低。在本文中， 整个名字解析系统以分布式网络为基础。系统的查找速度随着网络规模的扩大将 受到越来越大的局限。同时，动态网络的维护需要周期性的网络维护包，当网络 规模比较大时，网络的负载会加重。在下一章我们会通过理论分析确定了影响整 个服务标识解析机制查询效率的主要因素，并提出改进方案。 1 3 论文的主要工作及结构 本文研究的核心问题就是分析一体化网络原型系统中的服务标识解析系统的 性能并提出改进其性能的解决方案，最后用仿真结果来说明改进方案的有效性。 整篇文章的主要工作及贡献如下t 1 介绍了国家9 7 3 项目“一体化可信网络与普适服务体系基础研究 中提出 的标识网络的概念以及其中的服务标识解析机制。 2 用理论分析结合仿真的方法研究影响当前服务标识解析系统查询效率的 关键问题 6 引言 3 提出提高服务标识解析系统查询性能的解决方案 4 设计并实现具有缓存机制的服务标识解析系统 5 通过仿真结果来说明具有缓存机制的服务标识解析系统在大规模应用中 具备良好的性能。 本文一共分为六章，下面介绍一下本文的组织形式： 第一章引言，主要介绍本文研究的课题的背景以及当前国内外相关研究 的发展现状。 第二章服务标识解析系统及其性能分析，本章的主要工作是对服务标识 解析系统及其应用的相关技术做一个简单的介绍，然后通过比较 仿真分析来确定影响映射服务器查询性能的主要因素 第三章具有缓存机制的服务标识解析系统仿真方案，设计方案，通过仿 真来研究标识映射服务器在大规模应用中的性能改进 第四章增加缓存的服务标识解析系统的仿真实验，本章主要是在特定仿 真平台上将缓存机制应用到服务标识解析系统中，给出了具体的 模块功能实现 第五章仿真结果及性能分析，本章主要是通过仿真结果输出将不同方案 对比，进而分析服务标识解析系统的性能。 第六章总结，本章主要是对全文的工作概括，并且对结果进行评论 7 北京交通大学硕士论文 2 服务标识解析系统及其性能分析 一体化网络中服务标识解析系统最主要的任务是负责管理一体化网络中的 s i d 到a i d 的映射关系。如果系统要在现实网络中大规模的应用，就要对系统的 性能做一个全面详细的分析，尤其是针对用户查找方面。传统的互联网每天对网 站的访问量是非常大的，如果把服务标识的概念引入进来，那么这个信息量会进 一步膨胀。设法提升服务标识解析系统的性能首先需要分析系统的瓶颈。本章首 先介绍了服务标识解析系统的整体设计以及应用到的相关技术，然后通过理论分 析确定了影响服务标识解析系统查询性能的主要因素。 2 1 服务标识解析系统和分布式网络 2 1 1 p 2 p 网络 最近几年，随着b i t t o r r e n t 、s k y p e 和p p l i v e 等众多p 2 p 应用的飞速发展，p 2 p 技术成为一个热门话题。目前，对于p 2 p 并没有一个统一的定义。但p 2 p 的名字 基本上表达了它的特点：它是一种节点到节点的网络，这里的节点主要指用户。 这与传统网络的客户端服务器模式有很大区别。在传统网络中，众多服务器可以 给用户提供各种数据和服务，服务器在互联网中扮演着极其重要的角色。而在p 2 p 网络中，网络中节点的地位都是对等的，每个节点既享受资源也提供资源，在网 络中不存在服务器。这种思路在观念上是对传统网络的重大变革，它的优点和缺 点也相当明显。 与传统的网络比，p 2 p 网络具有以下优点【1 6 1 ： 1 、去中心化。将网络资源和服务分布在网络的各个节点上，无需集中的服务 器来管理资源，可以有效地避免网络瓶颈。 2 、鲁棒性。资源和服务分散在各个节点上，部分节点失效对网络的影响比较 小，通常的p 2 p 算法都会实现自组织性。 3 、可扩展性。不会出现资源和服务的瓶颈问题，随着节点的加入，资源的分 布将更广，在整个网络上能提供的资源也更多。在很多p 2 p 应用中，这个特点体 现得很明显。 4 、负载均衡。无传统网络中的服务器，不会出现一个节点的资源和服务特别 集中的现象。 服务标识解析系统及其性能分析 5 、网络安全。p 2 p 网络中无需经过某个集中节点，用户信息泄露的可能性也 大大降低。 另一方面，p 2 p 技术也存在一些明显的缺点【1 7 1 ，在应用p 2 p 时我们必须避免 这些缺点。主要缺点有：节点加入、退出网络的维护工作开销比较大，这在结构 化的p 2 p 网络中体现得更加明显；节点的异构性可能会造成部分节点的瓶颈；许 多用户可能不愿意共享资源，而只愿意获取；节点间的不信任感等。 网络中的很多应用充分发挥了p 2 p 技术的优点，使其性能取得了以往不可想 象的突破，p 2 p 技术正在迅速发展。 2 1 2d h t 网络概述 根据拓扑结构可以将p 2 p 产生以来所有出现过的p 2 p 形态分为四类：集中式 非结构化p 2 p 、分布式非结构化p 2 p 、混合式非结构化p 2 p 和分布式结构化p 2 p ， 分布式结构化p 2 p 网络也称为d h t 网络。下面依次介绍这几种形态以引出对d h t 网络的介绍。 1 、集中式非结构化p 2 p 。 以n a p s t e r 【1 8 】为代表的集中式非结构化p 2 p 是最早出现的p 2 p 系统之一。 n a p s t e r 采用一个中央服务器保存所有用户上传的音乐文件索引和其i p 地址映射集 合的信息，这个中央服务器也称为目录服务器。当某个用户需要某个音乐文件时， 首先连接到n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该文件的用 户信息；再由请求者直接连接到文件的所有者传输文件。同时目录服务器通过周 期性地向用户发送报文以确认用户是否在线，来维持检索信息的更新。n a p s t e r 系 统的创新在于中心服务器只存放索引，而不存放具体的资源，提高了查询效率。 但它与其他p 2 p 网络类型相比，存在一个信息集中的节点，容易造成单点故障。 2 、分布式非结构化p 2 p 分布式非结构化p 2 p 的典型代表是g n u t e l l a t ”1 。g n u t e l l a 是一个p 2 p 文件共享 系统，解决了n a p s t e r 的一些问题，它没有索引服务器。每个节点维护着到邻居节 点的路由信息，它采用了基于完全随机图的泛洪发现和随机转发机制，并采用生 存时间( t i m et ol i v e ，t t l ) 值的递减变化来控制搜索消息的传输。整个系统具有较 高的容错性，节点频繁地加入和退出对系统的影响不大。但是随着联网节点的不 断增多，网络规模不断扩大，通过这种泛洪方式定位对等点的方法将造成网络流 量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初 期的g n u t e u a 网络中，存在比较严重的分区，断链现象，因此网络的可扩展性不 好，不适合大型的网络。 9 北京交通大学硕士论文 3 、混合式非结构化p 2 p 混合式非结构化p 2 p 的典型代表是k a z a a 2 0 1 。它在分布式拓扑的基础上引入了 超级节点的概念，超级节点成为地理上相邻的其他节点的索引服务器，一个超级 节点的域形成一个簇，簇内的普通节点使用类似于n a p s t e r 的集中式查找算法。而 超级节点之间采用随机图的方式形成类似于g n u t e l l a 的非结构化网络，它们之间 使用泛洪查找算法。这种结构也是一个层次式结构，超级点之间构成一个高速转 发层，超级点和所负责的普通结点构成若干层次。k a z a a 结合了n a p s t e r 和g n u t e l l a 的共同优点，其查找性能和可扩展行都比较好，缺点在于网络中的超级节点易成 为瓶颈。 4 、分布式结构化p 2 p 为了解决非结构化p 2 p 中的扩展性不好、查找范围有限的缺点，p 2 p 的研究 者们把目光聚集在了构建一个结构化的网络上，因此利用分布式哈希表( d i s t r i b u t e d h a s ht a b l e ，d h t ) 构建系统的想法以不同的形式产生出来。d h t 实际上是一个由整 个网络上大量结点共同维护的哈希表。哈希表被分割成不连续的块，每个节点并 不需要知道整个网络的每一点的情况，只需要知道特点的块的情况，通过与其他 节点的通信可以进而了解整个网络的情况。d h t 类结构能够自适应结点的动态加 入退出，有着良好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织能力。由 于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的结点存 在于网络中d h t 总能发现它，发现的准确性得到了保证。在目前的研究中，有几 种比较成熟的系统p a s t d a 2 1 1 ，c h o r d t 2 2 1 ，t a p e s t r y 2 3 】和c a n 2 4 1 。 集中式非结构化p 2 p 存在单点瓶颈问题，基于洪泛的非结构化p 2 p 可扩展性 差，基于d h t 的结构化p 2 p 解决了大规模对等网络问题，采用了相容哈希函数获 得标识符并采取特定的机制组成确定的重叠网拓扑结构，并通过路由表进行高效 的p 2 p 路由。所以d h t 网络是目前的研究热点，也是p 2 p 进一步向前发展的基础。 2 1 3c h o r d 算法介绍 c h o r d 算法是d h t 中的一个典型代表，它是为了解决有效地定位p 2 p 网络中 的资源而提出的一种方法。c h o r d 本身只提供一种操作，给定一个关键字，它把这 个关键字映射到系统中的一个节点上。在c h o r d 的实际应用中，这个节点负责存 储与这个关键字相关的一个值。c h o r d 使用一致哈希的方法来给c h o r d 节点分配关 键字。这种一致哈希方法能起到负载平衡的作用，因为每一个节点接收到的关键 字的数量大致相同而且当节点加入或离开系统的时候，关键字的移动次数也较少， 即使当节点频繁地加入或退出系统时，c h o r d 也能进行很准确的定位和查找。 l o 服务标识解析系统及其性能分析 由于c h o r d 算法和后面将要介绍的服务标识解析系统有着非常密切的关系， 本小结将对c h o r d 算法做一个全面的介绍【2 8 】： 1 系统模型 c h o r d 算法本身只提供一种操作：给定一个关键字，它把这个关键字映射到系 统中的一个节点上。但为了高效地实现这个操做，算法需要完成很多工作以保证 映射的准备性和高效性。c h o r d 算法阐述了下面的一些问题：怎样将给定的关键字 映射到某个节点，构造一维环形的拓扑结构；怎样构造每个节点上的f i n g e r 表，使 节点存贮空间和算法的时间复杂度得到一个很好的折衷；怎样定位资源的存储位 置；节点如何加入系统，如何退出系统，节点失效如何处理等方面的问题。与其 它结构化p 2 p 协议相比，c h o r d 协议具有更加好的综合性能。 c h o r d 作为p 2 p 系统中的一种，很多特点都是p 2 p 网络本身带有的特点。但 在作为一种结构化的p 2 p 系统，c h o r d 也有很多自身的特点。c h o r d 在整体性能方 面比较好的解决了下面这几个难度比较大的问题，从而简化了p 2 p 系统的设计和 基于c h o r d 的应用：。 负载均衡：c h o r d 起到了一个分布式的哈希函数的作用，将关键字均匀地分布 在各个节点上，这提供了某种程度的自然负载均衡。 去中心化：c h o r d 是完全分布式的，所有节点的地位都是平等的。这带来了网 络的健壮性，使得c h o r d 适合那些组织比较松散的p 2 p 应用。 可扩展性：c h o r d 查询的开销随着节点数目的增长而呈对数级增长，这对于非 常大的系统也是可行的。而且提供这种可扩展性并不需要参数的调节。 工 稳定性：当新节点加入或者节点失效时，c h o r d 能自动的调整内部的f i n g e r 表 来反映这种变化，这就使得c h o r d 能忍受下层网络的失效，可以使得负责给定关 键字的节点总能找到。在系统处于持续的变化状态时，这也是能保证的。 灵活的命名：c h o r d 对于它所查询的关键字的结构没有限制，c h o r d 的关键字 空间是扁平的。这就给c h o r d 应用如何在名字和关键字之间建立映射提供了很大 的灵活性。 2 拓扑结构 c h o r d 的一致哈希函数使用一个基本的哈希函数给每个节点和关键字一个m 位长的标识符。标识符长度m 的值应该足够长，使得两个节点或者关键字哈希成 同一个标识符几乎不可能。如在c h o r d 中，采用s h a 1 算法可以将需要哈希的内 容哈希成一个1 6 0 位的标识符。节点的标识符通过对节点的m 地址或再加上端口 号进行哈希运算而得