（通信与信息系统专业论文）i3网络中的chord环研究及服务融合.pdf

摘要 摘要 i 3 网络作为一种新的网络开始进入到我们的生活中，它有别于传统的i p 通信 网络，通过一种间接通信结构来改变原有的通信方式，从而在网络的移动性，安 全性，多播等方面满足日益增长的网络需求。 而i 3 网络的核心查询部分采用了一种p 2 p 网络叫h o r d 环。p 2 p 网络近几 年来迅速成为研究热点，在各方面的应用层出不穷，特别是它提供无穷的存储空 间以及不受限制的传输容量，这是传统的中央服务器所无可企及的。 目前对p 2 p 网络的研究较为成熟，而i 3 网络还处于初期的研究。本文将对i 3 网络下c h o r d 算法以及服务融合进行研究，所做的工作主要包括以下几个方面： 1 系统分析了对等网络各种查找算法，包括非结构化分布式查找算法 g n u t e l l a ，以及结构化分布式查找算法中的c a n 和c h o r d 。其中，重点分 析了c h o r d 算法，并将它与其它算法做了性能对比，分析出c h o r d 算法的 优点与不足。 2 研究了i 3 网络中c h o r d 算法的应用及实现，对改进路由表结构后的c h o r d 算法进行理论分析并进行仿真。在i 3 网络下，c h o r d 的路由表结构为二阶 形式，本文将其表项改为三阶路由表形式，以增加路由表项的代价来获取 转发次数的降低，经过实验论证可行。对一个网络来说，转发次数的降低 意味着平均时延的降低，从而能对网络性能的改善有所帮助。 3 研究当前的新技术服务融合，系统描述服务融合的概念，以及其在p 2 p 网络下的搜索策略。基于i 3 这个网络平台，提出并分析了三种针对应用 的服务融合方案，完成其中一个方案的服务配置。 4 最后，对i 3 网络下的c h o r d 算法应用进行总结，分析服务融合方案如何 实现，对下一步研究方向作出展望。 关键词：i 3 网络，c h o r d ，三阶，服务融合 a b s t r a c t a b s t r a c t an e ws t y l eo ft h en e t w o r k i 3w h i c hi sd i f f e r e n tf r o mt h et r a d i t i o n a l i p c o m m u n i c a t i o ni sn o w p e n e t r a t i n gi n t oo u rl i f e s i tc h a n g e st h eo r i g i n a lc o m m u n i c a t i o n p r o c e s st h r o u g ha l li n d i r e c tc o m m u n i c a t i o ns t r u c t u r et os a t i s f yt h eg r o w i n gn e t w o r k i n g n e e do fm o b i l i t y , s e c u r i t ya n dm u l t i c a s t i 3i sap 2 pn e t w o r ke s s e n t i a l l yw h i c hi sah o tn e t w o r ks t r u c t u r et h e s ey e a r sa n di t s a p p l i c a t i o n se m e r g ei ne n d l e s s l y e s p e c i a l l yi tp r o v i d e si n f i n i t es t o r a g es p a c ea n d u n l i m i t e dt r a n s m i s s i o nc a p a c i t yw h i c hi sn o tc a p a b l ef o rt h et r a d i t i o n a lc e n t e rs e r v e r s c o m p a r e dw i t ht h em a t u r e dp 2 pn e t w o r k ，i 3i ss t i l lo nr e s e a r c hi n c l u d i n gc h o r d p r o t o c o l ，s e r v i c ec o m p o s i t i o ne t c w ed os o m er e s e a r c ho nt h ec h o r dp r o t o c o la n ds e r v i c e c o m p o s i t i o no fi 3 n e t w o r k ： 1 w es y s t e m a t i c a l l ya n a l y z ee v e r yp 2 ps e a r c h i n ga l g o r i t h m si n c l u d eg n u t e l l a , c a na n dc h o r d w ei n t r o d u c et h ec h o r d p r o t o c o li nd e p t h ，c o m p a r ei tw i mo t h e r sa n d s h o wt h ea d v a n t a g e so fi t 2 d os o m er e s e a r c h e so nt h ec h o r d p r o t o c o li ni 3n e t w o r k w ei m p r o v et h ec h o r d p r o t o c o lf o rt h ei 3a n dd os o m es i m u l a t i o n si ni 3 t h er o u t i n gt a b l eo ft h ec l a s s i cc h o r d i s2 - r a n k w ed e s i g na3 - r a n kc h o r dw h i c hc a ne l i m i n a t et h et r a n s m i t t i n gt i m e si nt h e t h r o u g hi n c r e a s i n gt h ee n t r i e so ft h er o u t i n gt a b l e a c c o r d i n gt oe x p e r i m e n t s ，w ec a l l f i n df o ran e t w o r k ，t h ee l i m i n a t i o no ft h et r a n s m i t t i n gt i m e sm e a n sd e c r e a s i n go ft h e a v e r a g et i m ed e l a y 3 d os o m er e s e a r c h e so nt h es e r v i c ec o m p o s i t i o n ，e x p l a i nt h ec o n c e p to fi ta n d a c h i e v ei ti nt h ep 2 pn e t w o r k b a s e do nt h ei 3p l a t f o r m ，w ep r o v i d ea n da n a l y s et h r e e s e r v i c ec o m p o s i t i o ns c h e m e sf o ra p p l i c a t i o na n dc o m p l e t et h es e r v i c ec o n f i g u r a t i o no f o n es c h e m e 4 f i n a l l y , w em a k eac o n c l u s i o nf o rc h o r da l g o r i t h m su n d e ri 3n e t w o r k ，a n a l y s e h o wt oa c h i e v et h es e r v i c ec o m p o s i t i o ns d a e m e s ，a n dm a k eap r o s p e c tf o rt h ef u t u r e a b s t r a c t r e s e a r c h k e y w o r d s ：p 2 p ，i 3 ，c h o r d ，t h i r do r d e r ，s e r v i c ec o m p o s i t i o n 图目录 图1 - l 集中式p 2 p 结构2 图1 2 分布式p 2 p 结构一3 图1 3 混合式p 2 p 结构4 图1 - 4 互联网的客户机服务器模式4 图l - 5 互联网的p 2 p 模式5 图1 - 6 i 3 网络结构及通信示意6 图1 7i 3 网络对移动性的支持7 图1 - 8i 3 的数据包发送过程8 图1 - 9i 3 的数据包接收过程8 图2 - 1c a n 的逻辑拓扑1 1 图3 - 1 基于i d 通信的i 3 网络1 7 图3 - 2i 3 的通信流程1 8 图3 3i 3 的可移动性1 9 图3 4i 3 的组播特性2 0 图3 5i 3 的任播特性2 1 图3 - 6 路由表容量与路由链路长度关系曲线2 4 图3 - 7 三阶c h o r d 的路由表指针模型2 6 图3 - 8i 3 通信模型2 7 图3 - 9i 3 平台下c h o r d 模块流程3 1 图3 1 0c h o r d 转发次数仿真结果3 3 图4 - 1 服务融合的整体框架3 6 图4 2 服务融合的功能划分3 7 图4 3 服务融合资源的管理抽象模型3 9 图4 - 4 基于内容无关搜索的模型4 0 图4 - 5 最优服务融合的整体流程4 1 图4 - 6 i 3 下的服务融合示例4 3 图4 - 7 i 3 下的服务融合通信流程4 5 图4 - 8 视频服务融合系统4 7 图禾9 电子邮件业务的服务融合4 9 图4 - 1 0o w l s 的本体结构5 1 图4 11 会议方案实施服务流程5 2 睁 表目录 表目录 表卜1p 2 p 结构和c s 结构性能比较5 表2 1c h o r d 环上节点的路由表1 3 表3 1 节点饱和假设下的路由表2 3 表3 2 三阶c h o r d 路由表结构2 5 表3 31 4 个节点的二阶路由表3 2 表3 41 4 个节点的三阶路由表3 2 表3 55 个节点的二阶路由表3 4 表3 - 65 个节点的三阶路由表3 4 - i 缩略词表 英文缩写英文全称 a p i c a n c s d b s d h t d n s d o s h t m l h t t p i 3 i d i p o w l s p 2 p p 2 p w g s h a s o a t c p t t l w 3 c 删l 缩略词表 a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e c o n t e n t a d d r e s s a b l en e t w o r k c l i e n t s e r v e r d i s t r i b u t e db i n n i n gs c h e m e d i s t r i b u t e dh a s ht a b l e d o m a i nn a m es y s t e m d e n i a lo fs e r v i c e h y p e r t e x tm a r k u pl a n g u a g e h y p e r t e x tt r a n s f e rp r o t o c o l i n t e m e ti n d i r e c t i o ni n f r a s t r u c t u r e i d e n t i f i c a t i o n i n t e m e tp r o t o c o l o n t o l o g yw e bl a n g u a g ef o rs e r v i c e s p e e r - t o p e e r p e e r - t o p e e rw r o r kg r o u p s e c u r eh a s ha l g o r i t h m s e r v i c e o r i e n t e da r c h i t e c t u r e t r a n s m i s s i o n c o n t r o lp r o t o c o l 乃脚e t ol i v e w 0 r i dw i d ew e bc o n s o r t i u m e x t e n s i b l em a r k u pl a n g u a g e v 中文释义 应用程序编程接口 内容寻址网络 客户机朋艮务器 分布式围栏算法 分布式哈希表 域名解析系统 拒绝服务攻击 超文本标记语言 超文本传输协议 因特网间接通信结构 身份标识 网际协议 面向服务的网络本体语言 对等网络 对等网络工作组 安全散列算法 面向服务架构 传输控制协议 生存时间 万维网联盟 扩展标记语言 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：张够前 日期：2 0 0 9 年6 月i o 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丞缉整导师签名： 日期：2 _ o o g 年6 月0 日 第一章绪论 第一章绪论 一种有别于传统口通信的网络，称为i 3 网络，正进入到我们的信息生活中。 它使网络构架成一种间接通信结构，然后通过这中间层进行通信，可以在网络的 移动性、安全性、多播等方面有效地满足网络需求。 由于i 3 网络实质上是p 2 p 对等网络，因此，我们将从p 2 p 网络的研究入手， 首先将对p 2 p 网络进行介绍及分析。 1 1p 2 p 网络背景及发展现状 1 1 1p 2 p 网络定义 关于p 2 p 1 】对等网络，人们尚未给出一个统一的定义，但对此都有一些共同的 认识。大家把具有如下特征的分布式网络系统称为p 2 p 网络系统：所有的参与者 共享他们的一部分资源，如存储空间、计算能力、网络连接、外设等，这些共享 的资源对于网络上提供的服务和数据共享是必不可少的，可以被网络上其他节点 不经任何中间节点直接存取，参与这个网络的所有节点既是服务、资源和数据的 提供者，又是数据、资源和服务的需求者。 世界顶级r r 公司i b m 则为p 2 p 做了如下定义【2 l ：p 2 p 系统由若干互联协作的 计算机构成，且至少具有如下特征之一：系统依存于边缘化非中央式服务器设备 的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中成 员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在，构 成一个虚拟或实际的群体。 不管具体的表述有什么不同，我们都可以由此看出： 1 p 2 p 网络是由多个节点组成的一个分布式系统； 2 p 2 p 网络中各个节点完全自治，分别属于不同用户； 3 p 2 p 网络中的资源分布于各个节点； 4 p 2 p 网络中每个节点既提供服务又享受服务【2 1 。 电子科技大学硕士学位论文 1 1 2p 2 p 网络的结构 p 2 p 网络虽然出现的时间不长，但它并不是一种全新的技术，其前身可追溯到 上个世纪。早在1 9 7 9 年就产生了分布式对等网络技术的成功例子u s e n e t t 3 】 【4 】， 1 9 8 4 年又产生了f i d o n “5 1 ，这两个分布式系统就是目前p 2 p 网络的最初雏形。然 而，这种分布式系统长期被忽略。直到上个世纪末，随着n a p s t e r 6 】的广泛使用和 巨大成功，p 2 p 重新被大家重视。由于其固有的优越性，发展非常迅速，主要产生 了以下几种网络结构【2 1 。 1 1 2 1 集中式p 2 p 结构 集中式p 2 p 结构中，由一个中心服务器来负责记录共享信息以及回答对这些 信息的查询，如图1 1 所示。每一个节点对它将要共享的信息以及进行的通信负责， 根据需要下载它所需要的其它节点上的信息。采用这种结构形式的代表性软件为 n a p s t e r 。它的优点是有利于网络资源的快速检索，缺点是要有一个连续运转的高 性能服务器，集中处理用户的查询和返回查询结果。一旦该服务器失效，整个网 络就会停止运行。此外，该服务器必须能够处理大量的用户连接，拥有足够大的 内存和磁盘空间来搜索和维护文件列表。 图1 - 1 集中式p 2 p 结构 2 第一章绪论 1 1 2 2 分布式p 2 p 结构 分布式p 2 p 结构是一种纯p 2 p 模式，如图1 2 所示。这种结构不需要有中心 服务器，网络上的每一个节点都作为对等实体，地位是完全平等的。每一个节点 既可以作为客户机又可以作为服务器，并且它们与相邻的节点有相同的能力。 g n u t e l l a r l ，f r e e n e t 8 】就是这种分布式p 2 p 的代表。这种分布式p 2 p 的优点是：由 于没有中央服务器，一个节点失效并不影响整个网络的正常运行，而且不容易受 到网络攻击。但是它的缺点也很明显：搜索请求要经过整个网络或者至少是一个 很大的范围才能得到结果，所以，这种模式需要占用很多网络带宽，而且需要花 费很长时间才能得到返回结果。 图i - 2 分布式p 2 p 结构 1 1 2 3 混合式p 2 p 结构 混合式p 2 p 结构则结合了集中式和分布式p 2 p 的优点，在分布式模式基础上， 将用户节点按能力进行分类，使某些节点具有搜索和索引等特殊的功能，如图1 3 所示。这种结构的关键是引入了索引节点和搜索节点等特殊节点，索引节点只是 搜索与所需资源相关的地址，搜索节点则管理着所属用户的文件列表，它们称之 为“超级中心”。用户节点通过索引节点获得搜索节点信息，之后用户节点就与获 3 电子科技大学硕士学位论文 得的搜索节点相连，每一次查询都通过该搜索节点进行。采用这种结构的代表软 件是k a z a a ，m o r p h e u s 。 图1 3 混合式p 2 p 结构 客户端客户端客户端 ( c ii e n t ) ( c li e n t ) ( c 1i e n t ) 1 1 3p 2 p 结构和c s 结构 客户端 ( c 1 i e n t ) 图1 _ 4 互联网的客户机朋艮务器模式 当前互联网的主要模式还是客户机j l 民务器( c l i e n t s e r v e r ) 模式，如图1 4 。 4 第一章绪论 它要求有高性能的服务器，配合各种软件来集中处理信息，同时还响应网络中其 它客户端的请求。相对于服务器来说，每个客户端的能力和性能要求非常低，客 户端只需要处理自己的事务。这种结构导致网络中的资源都向少数服务器集中， 服务器成为网络中的主宰。这样的结构安全性好、易于管理。 图1 5 互联网的p 2 p 模式 表1 1p 2 p 结构和c s 结构性能比较 性能p 2 p 结构c s 结构 安全性差好 容错性好差 可扩展性好差 数据及时性好差 数据互动性 好差 数据质量中好 数据覆盖率和数量差好 易管理性差好 抗干扰性 好差 数据发布好差 数据接收中好 成本控制好差 5 电子科技大学硕士学位论文 而p 2 p 网络采用的是分布式结构，如图1 5 。虽然一些具体的结构没有完全抛 弃服务器，但是服务器的功能已经大大被弱化了，各个对等节点之间是平等的主 体，每个节点既是服务器又是客户端，网络资源不再集中于一处，而是分散到每 个节点。这种结构交互性好、及时性好。 所以，p 2 p 结构和c s 结构各有优点和不足。表1 1 是两种结构的性能比较， 从安全性，管理型和对数据的操作性等方面给出了对比。 1 2i 3 网络 i 3 网络实质是一种特殊的对等网络【9 】。就i 3 网络中主要成员i 3 服务器的相互 关系来看，它们也是彼此独立的，扮演角色相似的，实现功能相近的，所以i 3 网 络的结构就是p 2 p 的。只是其采用了独特的通信方式，才称之为因特网间接通信 结构。 ( i d ， 盆 图1 - 6i 3 网络结构及通信示意 在文献 1 0 中，对i 3 的间接通信方式描述有详尽描述。这种通信方式将发送 功能和接收功能独立开来，发送者向i 3 服务器发送数据包，传送的报文包含两个 部分：i d 和d a t a ，分别是m 位的身份认证和数据负载；接收者用一个触发消息( i d ， r ) 向i 3 服务器表示自己想接收的感兴趣的报文，i d 代表触发消息身份认证，r 表 示这个接收者的地址信息。这个触发消息表示任何身份认证为i d 的数据包都可以 在妒层被传送到地址信息为r 的主机终端，基本实现原理如图1 - 6 。在网络中设 置i 3 服务器，由它来决定数据包的转发，发送者不需要知道接收者是谁，也不需 要知道接收者的地址和接收者的个数等信息，通过这种方式我们可以简单的实现 组播通信和主机的移动性。 当一个节点从一个本地域移动到其他地方，它的地址也有可能发生了变化， 6 凰 第一章绪论 从r 变化到尺。但是通过这种基于身份认证的间接通信提取方式，发送者并不需 要知道这种信息的变化，即使是发送者移动也没有什么附加的操作需要被处理。 接收者只需向i 3 服务器发送具有同样身份认证i d 的触发消息就可以方便的取回数 据包。具体实现过程如图1 7 。 0i d 凰 n n 凰 口凸口 图1 7i 3 网络对移动性的支持 不过i 3 服务器自发组建o v e r l a y t l l l 网络模型实现应用层组播或者移动性也存在 着一些问题：如果采用结构化o v e r l a y t l 2 1 网络模型虽然实现简单并且不需要复杂的 路由管理，但是不能完全反映底层网络状况，造成资源利用不合理；如果采用非 结构化o v e r l a y 网络模型则路由算法过于复杂，不适合推广到大规模组播应用。 1 3c h o r d 算法背景 随着i 3 网络的发展，需要高效的数据定位和查找机制，c h o r d 算法不是应运 而生，却恰到好处的对i 3 网络提供了支持。 c h o r d t l 3 】是麻省理工学院提出的一种结构化分布式查找算法。该算法的核心在 于提供查找资源在对等网络中存储位置的服务。算法阐述了怎样找到给定资源的 存储位置，新节点怎样加入系统，现有节点怎样退出系统以及系统怎样从现有节 点的失效中恢复等机制。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 的结构化对等物理路由算法。麻省理工学院一直在进行有关c h o r d 算法的研究，开发了称为“c h o r dp r o j e c t 的项目。“c h o r dp r o j e c t ”项目的目的是： 以对等通信的理念构建可扩展的、健壮的分布式系统【1 4 1 。 7 电子科技大学硕士学位论文 1 4 服务融合背景 i 3 网络能够提供网络资源的服务融合。我们通过分析i 3 网络的数据包发送和 接受过程来说明。图1 8 表明，接收者r 发送数据包传输请求，在它接收到发送 者s 的数据之前，是通过中介服务点( t r a n s c o d e r t ) 进行用户身份识别的。显然， 当发送者传送数据包( i d t ，i d ) 的时候，中介服务点就插入了一个有关接受者身份识 别的数据i d t ，然后中介服务点根据数据i d t 把数据包再转发给相应的接收者。 t r a n s c o r d e r ( t ) 图1 8i 3 的数据包发送过程 图1 - 9i 3 的数据包接收过程 8 第一章绪论 图1 - 9 描述了接收者通过身份信息的转变接受数据包的过程。接受者r 拥有 一个触发器( i d ，( i d t ，r ) ) ，这个触发器中( i d t ，r ) 代表的是他身份识别的信息。当一 个数据包与身份识别的信息相匹配的时候，那么数据包的识别信息也随之转变为 相应的接受者的身份识别信息。然后，数据包被传入中间服务点( t r a n s c o d e rt ) ， 最后数据包由中间服务点传输给接受者。整个流程中的核心部分是数据包的识别 信息与接受者身份信息的匹配，这是数据包能准确传输的关键所在。 以上通信过程说明，在用户之间的数据传输都是基于用户本身身份信息的， 而与用户的使用地址无关，也就说明在i 3 网络上面的服务融合是切实可行的。 1 5本文的研究内容及章节安排 本文的研究内容主要有以下几个方向： 1 对p 2 p 网络下各种查找算法，主要是对c h o r d 算法的研究，包括它的运行 机理，性能和优缺点。 2 研究了i 3 网络的通信方式，分析i 3 网络对现有p 网络的优势。以及对i 3 平台中c h o r d 算法的应用，改进及实现。 3 对服务融合系统研究，并进行p 2 p 网络下的应用探索，以及i 3 网络下的 服务融合方案。 论文的章节安排如下： 第一章介绍了论文研究的背景，包括p 2 p 网络，i 3 网络，c h o r d 算法以及服务 融合的概述。它们对接下来的具体研究提供理论基础。 第二章对网络中各种查找算法进行分析，选取代表性的分布式查找算法c a n 和c h o r d 进行了详细分析，然后将c h o r d 算法与其他相关算法进行比较分析。 第三章对i 3 网络的特点作了分析及通信方式的研究，并将c h o r d 算法在i 3 平 台下实现改进路由表结构后的仿真。实验结果表明了改进路由表结构后的c h o r d 在转发次数和时延上具有一定的优越性。 第四章研究了服务融合的基本理论后，以具体实例说明了i 3 网络下的服务融 合，以及给出三种服务融合的具体方案，完成其中一个方案的服务配置。 最后一章对全文进行了总结，并给出展望与下一步的研究方向。 9 电子科技大学硕士学位论文 第二章网络查找算法研究 国内外对于对等网络查找算法的研究成果可归结为集中式、分布式和混合式 三类查找算法。其中，集中式查找算法因可扩展性差，并且往往有网络中单点失 效问题的存在而使人们更多的研究分布式查找算法。至于混合式查找算法，则是 结合了集中式查找的高效与分布式的强容错性与可扩展性。因此，分布式查找算 法在网络中最重要。 2 1非结构化分布式查找算法 非结构化分布式查找算法中，对等节点连接任意其它节点构成对等网络，数 据放置与对等网络拓扑无关。此类算法的优点是由于逻辑网络拓扑采用随机图的 组织方式，节点度数服从“p o w e r - l a w ”规律，因而能够较快发现目的节点，并具 有较好的容错性。同时可以支持复杂查询，如带有规则表达式的多关键词查询， 模糊查询等。缺点是由于没有确定拓扑结构的支持，非结构化网络无法保证资源 发现的效率和准确性。同时，随着网络规模不断增大，此类算法采用的洪泛发现 机制将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载 而失效。因此，可扩展性能很差同样是此类算法的重大缺陷。此类查找算法最有 代表性的应用是g n u t e l l a t l 3 】。 g n u t e l l a t l 4 】是一种对等网络文件共享系统，它采用非结构化分布式查找算法。 g n u t e l l a 中不存在中央服务器，它采用基于完全随机图的洪泛发现和随机转发机 制，并通过t t l 的减值来控制查找消息的传输。g n u t e l l a 中每个节点维护一些随 机邻居节点的位置信息，用户需要查找某个文件时，首先向邻居节点广播查找消 息，邻居节点收到查找消息后，再中转给自己的邻居节点，直到找到目标文件或 超过1 t l 的限制。通过g n u t e u a 的查找过程，我们可以发现，虽然g n u t e l l a 中完 全分布式的查找方法有效避免了单点失效问题，但它的查找范围被局限在了以查 找起点为半径的特定范围内，无法保证查找的有效性，同时，它采用的广播查找 机制导致了系统可扩展性不佳。 1 0 第二章网络查找算法研究 2 2结构化分布式查找算法 由于非结构化分布式查找算法使用的随机搜索机制造成查找效率和准确性的 不可控制以及系统可扩展性差的重大缺陷，如何构建高度结构化的分布式查找算 法成为了学术界的研究热点。目前最新的研究成果体现在基于d i s t r i b u t e dh a s h t a b l e t l 5 】构建的结构化分布式查找算法。 分布式哈希表实际上是一个由广域范围大量节点共同维护的巨大哈希表。哈 希表被分割成不连续的块，每个节点被分配给一个属于自己的哈希块，并负责管 理这个哈希块。 基于d h t 的结构化分布式查找算法能够自适应节点的动态加入和退出，有着 良好的可扩展性、容错性、负载平衡性和自组织能力。由于采用了确定性逻辑拓 扑结构，查找的准确性和查找效率得到了保证。此类查找算法较有代表性的应用 有p a s t r 3 ，【1 6 1 ，t a p e s t r 3 ，【1 7 1 ，c a n t l 8 】和c h o r d 。下面选取有代表性的c a n 算法和c h o r d 算法进行介绍与分析。 2 2 1c a n 查找算法 c a n t l 8 】是b e r k e l e y 提出的一种结构化分布式查找算法。该算法构造一个虚拟 的d 维笛卡儿坐标空间，每个机器或数据根据其i p 地址或关键字k ，由哈希函数 映射到该d 维空间中的一点。参与网络的物理节点动态划分该d 维空间，拥有某 块虚拟坐标区域的物理节点对由哈希函数映射到该区域中的数据负责。 图2 1c a n 的逻辑拓扑 2 2 1 1 逻辑拓扑结构 图2 - 1 显示了一个2 维的c a n 网络的拓扑结构。这是一个2 维的笛卡儿坐标 空间，整个虚拟坐标空间被划分为许多小的2 维区域，每个物理节点对应一个区 1 1 电子科技大学硕士学位论文 域，维护由哈希函数映射到该区域的数据。比如节点a 对应( o 0 5 ，0 0 5 ) 区域， b 对应( 0 5 1 0 ，0 0 5 ) 区域。在d 维空间中，如果两点有小1 维坐标相同，并且 剩下的维坐标相邻，如在图2 1 中，e 和b ，d 都相邻，则它们互为邻居；e 和 a ，c 不相邻，那么它们就不是邻居。 2 2 1 2 数据结构 c a n 中每个节点需要维护一个协作式的路由表，路由表中包含邻居节点( 每 维有2 个，共2 d 个，d 代表维数) 以及相应的拥有空间。 2 2 1 3 查找步骤 c a n 进行查找操作时，首先将要查询的目标的关键字由哈希函数映射到d 维 空间中的一点( x ，y ) ，每一步从路由表中选取与( x ，y ) 笛卡儿距离最近的邻居节点转发 查找消息，这样一步步的将查找消息路由到目的节点。例如，在图2 1 中，如果从 e 节点开始查找数据k ，假定数据k 属于c 管辖范围内，则可能的查找路由过程为： e 专d 专c 或e 专曰专么专c 等。 2 2 1 4 节点加入和退出过程 节点m 加入c a n 时首先需要知道一个已知节点b ，然后节点m 随机选取一 个空间坐标点( x ，y ) ，通过b 在c a n 中路由到负责( x ，y ) 的节点c ，然后将c 负责的 区域均分，其中的一半给节点m ；与此同时，节点m 加入将导致节点c 及其邻居 节点的路由表发生变化，节点m 通知节点c 并由节点c 通知其邻居节点进行路由 表的更新，此外，每个节点还周期性地通知其邻居节点自己所负责的区域以便路 由表的更新。 c a n 中节点正常退出时会运行接管算法( t a k e o v e ra l g o r i t h m ) ，发送t a k e o v e r 消息给其直接邻居，并由某个邻居接管该节点留下的区域【1 6 1 。 2 2 2c h o r d 查找算法 2 2 2 1 逻辑拓扑结构 c h o r d 通过一致性哈希函数为网络中的所有节点和资源赋予d 位的标识号。其 中，节点的标识号一般是通过对节点口地址的哈希运算得出，资源的标识号一般 是通过对资源名称的哈希运算得出。所有可能的n = 2 。个节点标识根据其数值由 小到大按顺时针方向相连，并且最大值和最小值相连，最终构成一个标识环。对 于一个标识号k ，标识环中顺时针方向第一个物理节点称作k 的后继节点，记做 s u c c e s s o r ( k ) ；逆时针方向第一个物理节点称作k 的前驱节点，记做p r e d e c e s s o r ( k ) 。 1 2 第二章网络查找算法研究 c h o r d 规定标识号为k 的资源存储在k 的后继，即s u c c e s s o r ( k ) 上。一个d = 6 的c h o r d 环，环中最大可能拥有n = 2 6 = 6 4 个节点，现有1 0 个节点。s u c c e s s o r ( 1 0 ) = 1 4 ， s u c c e s s o r ( 2 4 ) = 3 2 ，s u c c e s s o “3 0 ) = 3 2 ，s u c c e s s o r ( 3 8 ) = 3 8 ，s u c c e s s o r ( 5 2 ) = 5 6 ，因此， k 1 0 存储在n 1 4 上，k 2 4 存储在n 3 2 上，k 3 0 存储在n 3 2 上，k 3 8 存储在n 3 8 上， k 5 2 存储在n 5 6 上。 2 2 2 2 数据结构 在标识空间的大小为n ( d = l o g ，n ) 的c h o r d 环中，每个节点维护的内部数据 结构包括：前驱节点，后继节点，拥有d 个表项的路由表( 称为f i n g e r 表) ，连续 d 个后继节点的列表，前d 个节点存储资源备份列表。其中前三项是基本c h o r d 算 法所规定的必备数据结构，后两项是c h o r d 算法考虑系统容错性和数据可靠性而 附加的数据结构。c h o r d 路由表中每一项的结构如表2 一l 所示： 表2 1c h o r d 环上节点的路由表 标记含义 f i n g e r k s t a r t ( 咒+ 2 一1 ) m o d 2 a , 1 k d s u c c e s s o r f i n g e r k s t a r t 的后继节点 从表2 1 可以看出，路由表中存有在当前节点之后，且距离当前节点 2 0 ，2 1 ，2 扣1 的虚拟点的后继节点的位置信息。 2 2 2 3 查找步骤 根据c h o r d 算法的规定，标识号为k 的资源存储在k 的后继上。因此，查找 资源的过程为：首先根据待查资源的名称哈希运算出标识号k ，然后运用查找算法 在标识环中找到k 的后继节点s u c c e s s o r ( k ) ，s u c c e s s o r ( k ) l l j 为资源k 的存储位置。 c h o r d 节点运用后继节点和路由表配合完成查找操作。查找步骤如下： 1 如果待查资源k 在查找节点s 与查找节点后继s u c c e s s o r ( s ) 之间，即k ( s ， s u c c e s s o r ( s ) ) ，则s u c c e s s o r ( k ) = s u c c e s s o r ( s ) ，返回s u c c e s s o r ( s ) ，查找完成。否则， 执行下一步。 2 节点s 查询路由表，找到节点s ，s 7 最接近并且小于k ，然后，将查找消 息路由到s 7 ，以s 为新的查找节点执行第一步。 2 2 2 4 节点加入过程 节点加入c h o r d 网络的过程分为三个步骤完成： 首先，新节点刀必须找到c h o r d 网络中的一个现有节点刀，并利用该节点使 1 3 电子科技大学硕士学位论文 用查找算法，得到咒的后继s 。 然后，n 构造自己的数据结构，包括构造前驱，后继，后继节点列表，路由表。 构造过程如下：填写后继为j ；获取后继s 的前驱作为自己的前驱；向5 请求它的 后继列表，以s 后继列表的前小1 项和s 构成本节点的后继列表：利用聆7 分别查找 ，z + 2 m ( m = 0 ，1 ，d 一1 ) 的后继，填写路由表。 最后，z 通知所有相关的节点更新其数据结构以便反应n 的加入。相关节点包 括n 的前驱，后继，前d 个前驱和那些当n 加入时必须改变其路由表的节点。更 新n 的前驱，后继的过程如下：修改n 的后继的前驱为n ；修改n 的前驱的后继为 刀。更新以的前d 个前驱的过程如下：将刀作为后继列表中的一项，将原后继列表 中的最后一项从后继列表中删除；更新当n 加入时必须改变其路由表的节点的过 程比较复杂( 1 8 】。 2 2 2 5 节点退出过程 节点退出c h o r d 网络的过程分为两个步骤完成： 首先，准备退出的节点n 通知它的前驱，后继，前d 个前驱。更新n 的前驱， 后继的过程如下：修改i v 的后继的前驱为n 的前驱；修改n 的前驱的后继为n 的 后继。更新, 的前d 个前驱的过程如下：将原后继列表中最后一项的后继加入后 继列表，将n 从后继列表中删除。 其次，n 通知所有相关的节点更新其路由表。这一步是节点加入操作的逆向过 程。 。 2 2 3c h o r d 算法与其他算法的比较分析 d n s 提供了主机名对i p 地址的映射，而c h o r d 可以提供同样的服务。域名可 以被换作值，地址可以被换作数据，这样就完成了值专数据( k e y 专v a l u e ) 的映射。c h o r d 不需要请求任何的特殊服务器，而d n s 则依赖于根服务器。d n s 名称这一结构反映了管理的范围，而c h o r d 却没有任何命名结构。d n s 是专门用 来寻找被命名的主机以及服务，而c h o r d 也能用来寻找不固定在特定机器上的数 据目标。 自由网【8 】( f r e e n e t ) 是一种分布式信息存储和搜索系统，像c h o r d 一样，是一 个非集中式的，系统化的而且能够在主机加入或者离开时自动适应的p 2 p 系统。 f r e e n e t 不把文档分配给专门的服务器，取而代之的是，它的搜索是用一种查找 1 4 第二章网络查找算法研究 c a c h e 副本的形式。这就允许f r e e n e t 提供一定程度的匿名。但是这个使得它不能 确保提取已经存在的文档或者可能会导致提取代价很大。c h o r d 不能提供匿名，但 是它的搜索操作可以在一个预期的时间内进行，而且能够成功或者是确定的失败。 p 1 a ) 【t o n 【1 9 1 艮好的发展了分布式的数据位置协议，它提供了比c h o r d 更加强的 保证：像c h o r d 一样它保证了一个查询将产生对数级数量的段以及可以很好的平 衡值的分布，但是p l a x t o n 协议还可以保证，根据网络拓扑的假设，查询距离从来 不会超过存储值的节点在网