（计算机系统结构专业论文）p2pvt：一种基于虚拟拓扑的点对点模型的研究.pdf

ab s t r a c t ab s t r a c t t h e r e s e a r c h f o r fr a m e w o r k o f n e t w o r k m o d e l i s o n e o f e m p h a s e s i n p e e r - t o - p e e r r e s e a r c h , in w h i c h , t h e s t r u c t u r e d p 2 p s y s t e m o r g a n i z e s t h e c o m p u t e r s a s a s t r u c t u r e d n e t w o r k w i t h e x c e l l e n t re g u l a r i t y o f c o n n e c t i o n a n d r o u t i n g t o s h a r e a n d q u e ry re s o u r c e s i n n e t w o r k , h o w e v e r , t h e n e t w o r k m a i n ta in e d b y s t r u c t u r e d s y s t e m i s u s u a l l y n o t i n t e g r a t e d f o r t h e d y n a m i c o f n e t w o r k , a n d i t l e a d s t o t h a t t h e r o u t i n g a l g o r i t h m a n d c o n n e c t i o n r e g u l a t i o n o w n e d妙 i n t e g r a t e d s t r u c t u r e d t o p o l o g y c o u l d n t b e a p p l y t o p 2 p s y s t e m , i t s h o u l d b e m o d i f i e d d u r i n g c o n s t r u c t i o n o f n e t w o r k m o d e l . i n t h i s p a p e r , a m e t h o d c o n s t r u c t i n g p 2 p m o d e l i s p r o p o s e d , i t o r g a n i z e s t h e n e t w o r k b y v i r t u a l n o d e s t o f o r m a v i r t u a l s t r u c tu r e d n e t w o r k t o p o l o g y . t h e v i r t u a l s t r u c t u re d n e t w o r k w i t h e x c e l l e n t re g u l a r i ty w o u l d b e k e p t i n t e g r a t e d c a n s h o u l d n t b e c h a n g e d w h e n c o m p u t e r s e n t ry a n d e x i t . i n o r d e r t o v e ri 斤t h e m e t h o d , t h e p 2 p - v t ( p 2 p m o d e l b a s e d o n v i r t u a l t o p o l o g y ) m o d e l b a s e d o n d e b r u ij n t o p o l o g y i s p re s e n t e d a n d i t s c r i t ic a l m e c h a n i s m s a r e s t u d i e d . i t d e f i n e s t h e r o u t i n g b i n a ry t r e e t o s t o re t h e v i rt u a l n o d e s a n d p re s e n t s t h e q u e ry a l g o r i t h m a n d m e c h a n i s m o f c o mp u t e r e n t r y a n d e x i t . a s w e l l a s , a s i mu l a t i o n p a c k a g e i s d e v e l o p e d t o s tu d y t h e q u e ry p a t h l e n g t h , s t o r a g e l o a d a n d c o m p u t e r c o n n e c t i o n d e g r e e . t h e r e s u l t s s h o w t h a t p 2 p - v t m o d e l p e r f o r m s b e tt e r q u e ry s p e e d a n d le s s a v e r a g e s t o r a g e d a t a k e y s t h a n k o o r d e , w h i c h i s a s t r u c t u r e d p 2 p s y s t e m u s i n g d e b r u ij n t o p o l o g y t o o . i t c a n c o n s t r u c t t h e p 2 p n e tw o r k m o d e l b y v i r t u a l n e t w o r k t o p o l o g y b a s e d m e t h o d a n d a c h i e v e a p p r o x i m a t e p e r f o r m a n c e o f q u e ry a n d s t o r a g e l o a d . k e y w o r d : c o n s i s t e n t h a s h , s t ru c t u r e d n e t w o r k , v i r t u a l n e t w o r k t o p o l o g y , r o u t i n g b i n a ry t r e e , p 2 p - v t 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内 容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印 刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供 目 录检索以 及提供 本学位论文全文或者部分的阅览服务: 学校有权按有关规定向国家有 关部门或者机构送交论文的复印 件和电子版; 在不以赢利为目 的的前 提下，学校可以适当复制论文的 部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 杨堂 叫 z () 0 了 年乡 月 习日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最 长保密年限及书写格式规定如下: 内部5年 ( 最长 5 年，可少于 5 年 ) 秘密1 0 年 ( 最长1 0 年， 可少于1 0 年) 机密2 0 年 ( 最长2 0 年， 可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学 位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己 经注明引用的内容外， 本学位论文 的 研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集 体， 均已 在文中以明 确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : 和 i 刚 7年 s月 l 4 日 第一章引言 第一章 引言 第一节 研究背景 随着互 联网 络的 发展 和资 源共享需 求的 增加，p 2 p ( p e e r - t o - p e e r ， 点 对点) 技术被广泛应用于资源共享、实时通信、分布式计算、协同工作、分布式搜索 和电 子商务等领域 1 2 7 . 2 8 1 ， 对互联网络、 通信产生深刻的影响 1 5 ) , p 2 p 技 术也成为 计 算机网 络技术研究领域的一 个热点。 p 2 p 技术研究的核心领域之一 是网 络结构模型的研究 1 7 , 2 3 , 2 4 , 2 6 1 ， 它是p 2 p 系 统的基础架构，决定了系统的可扩展性、查询效率和容错性，直接决定 p 2 p系 统的性能和规模。网络结构模型的研究 目 标是建立具有良好可扩展性的网络架 构， 在此基础上研究相适应的路由 查询算， 解决系统面临的 环境动态性并分析 模型的性能 和负 载。 本文的目 的 是提出 一种利用虚拟拓扑 来建 立 p 2 p网 络结 构 模型的方法，使用该方法建立网络模型并对其性能和负载进行分析，通过对模 型的研究验证基于虚拟拓扑的建立 p 2 p 网络模型的方法的可行性。 第二 节 p 2 p 概念和特点 p 2 p 技术虽然被广泛地应用， 但现在仍然没有统一的定义 【 1 0 1 。 通 过对现有的 不同 定 义 10 , 16 1研 究 发 现， p 2 p 作 为 一 个 分 布 式网 络系 统 具 有以 下 的 特点 : 1 ) p 2 p技术主要用于共享网络的各种资源硬件资源和数据文件，硬件资源 包括处理能力、存储能力、网络连接能力、打印机等。 2 ) p 2 p打破7传统的 c l i e n t / s e r v e r网络模式，系统中各个节点 ( p e e r ) 之间直接进行访问而不需要中心实体的参与。 3 ) p 2 p系统中的节点是对等的， 各节点既是客户端 ( c l i e n t ) 又作为服务 器 ( s e r v e r ) ， 既向别人 提供服务，而自 己 本身也享 用其他 节点 提供的 服务。 图 1 . 1 对传统的 c l i e n t / s e r v e r模式和 p 2 p模式进行了对比。 在传统的 c l i e n t / s e r v e r网络中， 所有的客户端 ( c l i e n t ) 都需要和中心服务器 ( s e r v e r ) 进行交互 ( 如图中箭头所示) ，服务器作为中心注册单元是唯一的内容和服务提 供者，客户端只能从服务器请求内容和获得服务，它们不共享自己的资源;而 图 1 . 1 显示的 p 2 p模式中，所有节点 ( p e e r )地位相同，它们既共享 自己的资 第一章引言 源，同时也获取其他节点共享的资源，节点之间的访问不需要经过任何中心的 实体。 c l i e n t / s e rve r 模式p e e r t o p e e r 模式 图1 . 1 c l i e n t / s e rv e r 和p 2 p 模式对比 与c l i e n t / s e r v e r 模式相比， p 2 p 网 络具有以下的 优点 : 1 ) 非中心化:网络中所有节点功能相同，节点既是服务提供者，又是服务 请求者。服务的完成直接在节点 之间实 现而无需中 心实 体介入， 避免了 单点故 障和中心瓶颈。非中 心化 特点 带给p 2 p 系统在可扩展性和健壮性 方面的 优势。 2 ) 可 扩展性: 用 户的 加入虽然导 致网 络中的 服务需求增 加， 但它也使得系 统整体资 源和服务能力同步 地扩充。网 络结构是全分布的，不 存在中心的瓶颈， 理论上其可扩展性可以认为是无限的。 3 ) 健壮性: p 2 p 架构具有耐 攻击、 高容错的优点。系统中 的服务 分散 在各 个节点之间进行， 部分结点 或网络失 效对其它部分的影响很小， 系统具 有很强 的健壮性。 4 ) 高性能/ 价格比:p 2 p架构可以有效利用互联网中分散的大量普通节点， 充分利用其计算能力或存储能力。 通过聚合大量的空闲资 源提供 低成本的大规 模的计算和存储能力。 5 ) 负载均衡: p 2 p网络中 节点既是 服务提供者又是 服务请求者， 减少了对 传统 c l i e n t / s e r v e r结构中服务器的性能要求，资源分布在多个节点上从而很 好地实现了整个网络的负载均衡。 第一章引言 综上所述，p 2 p 以非中心方式打破了传统的c l i e n t / s e r v e r结构，非中心化 作为 p 2 p最根本的 特点 ，它 可以 应用到网 络组织、系 统结构搭建、数 据存储和 系统工 作方式等方面，甚至 系统所有方面都采用非中 心化结构.同 样也不排除 p 2 p 系 统和应用的某些 部分保留中 心化结构以 满足系统 特定的需求。 第三节 p 2 p系统分类 p 2 p 技术采用中 心方式 打破了 c l i e n t / s e r v e r 结构 模式， 对它的分类可以 从中 心化程度进行，同时也可以按照应用目的和网络拓扑结构等进行。以下从中心 化程度和网络拓扑结构两方面对p 2 p 进行分类，介绍相关的概念并界定本文研究 的重点。 .3 . 1中心化程度分类 非中心化是 p 2 p系统最根本的特点， 按照中心化程度可以把 p 2 p系统划分成 三类网 络111 1: 1 )纯非中心化网 络 ( p u r e l y d e c e n t r a l i z e d n e t w o r k ): 网络中所有节点 功能 相同，节点既是 服务 器又是客 户端， 节点 之间 的交互 无需任何中 心实体的 参与，网络中任意的节点被删除后，系统不会发生服务丢失; 2 )部分中心化网 络 ( p a r t i a l l y c e n t r a l i z e d n e t w o r k ) :网 络中的节点既 作为服务器又作为客户端，但系统中某些超级节点 ( s u p e r n o d e s )比其它节点 具有更重要的角色，担负更多的功能。系统中超级节点是动态指派的，网络不 会由 于 超级节点失 效而 遭遇单点故障，一旦超级节点 失效或者 遭受恶意 攻击， 网络将会采取行动以 其他节点 取代它; 3 )混合中心 化网 络 ( h y b r i d c e n t r a l i z e d n e t w o r k ) :系统使用一个中心 服务器来促使节点之间的交互，服务器管理着各用户共享的文件目录 ( 文件存 储在用户机器上而非服务器上).数据传输和在两个节点之间进行，但传输之 前需 要中 心服务器从 存储的文 件目 录中定 位存储文件的 节点来促使节点间的数 据交互。混合中心网络中心服务器具有单点故障风险，同时容易遭受司法起诉、 技术故障和恶意攻击. 混合中心化网络具 有中 心实体， 容易受到 攻击和具有单点 故障 风险， 因此不 作为本文研究的重点。 第一章引言 3 .2 网络拓扑分类 p 2 p 系统并非按照物理网络的结构和布局组织系统中的节点，而是在物理网 络的 上 层再 建 立 一 个 覆 盖 网 络 ( o v e r l a y n e t w o r k ) 91 0 覆 盖 网 络 中 节 点 间的 连 接表示的是逻辑上的 关系， 而非计算机之间的物理网 络的连 接， 覆盖网络中具 有连接关系的两个节点间的交互实际上仍通过下层的物理网络来完成，逻辑上 相邻节点 之间的访问 实际 上可能需要经过物理网络中 的多次 路由 才能到达。 除非中心化特征以外， p 2 p 系统的另外一个关键属性是覆盖网络的网络拓扑， 它描述了节点与节点之间的逻辑连接关系和布局，并决定了系统的非中心特征 和运行机制。 由于 混合中 心化网络 具有的易受攻击和单点故障 特点， 因 此按照网 络拓扑 对 p 2 p 系统进行分类时没有把该类型网络考虑在内。 依据p 2 p网络拓扑结构特性可 以 把系统分成以 下三类: 1 )非结构化网 络 ( u n s t r u c t u r e d n e t w o r k ) : 非结构 化p 2 p 系统的 覆盖网络 采 用随 机图 【22 1 的 组 织 方 式 ， 节 点 之 间 的 连接 没 有 遵 循 预 先 定 义的 拓 扑 来 构建 ， 同时数据存储位置与网 络拓扑没有联系 8 , 1 3 1 . 非 结构化网 络中 没有任何关于数 据 与存储位置的 映射信息， 因此 搜索算 法通常 采用随 机搜索: 发起查 询的节点 把 查询请求转发到与自己邻近的节点，邻近节点根据自己是否存储查询所需的数 据决定向 查询节点进行回 复或者继续 转发查 询请求到其 邻近节点。 非结构 化系 统 主 要 采 用 洪 泛 ( f l o o d i n g ) 131 , 随 机漫 步 2 1, 25 1和 有 选 择 转 发 2 1, 2 51搜 索 算 法。 2 )结构化p 2 p 网 络 ( s t r u c t u r e d n e t w o r k ) : 为解决 非结构化网 络可扩展性 差的问 题，结构化网 络中的 网络拓扑不再 采用随机图， 而是对系统拓扑结构进 行了严格控制， 采用超立方、 m e s h , d e b r u i n等规律性 较强的拓扑7 l 来组织节 点， 同时通过一致性哈 希14 1 把文件存放在精确指定的 位置。 结构化网 络通过 一个 分布式哈希 ( d h t ) 表 存储着文 件哈 希后的k e y 值与其 存储位置的映射关系1 8 1 由于结构化网络拓扑具有较强的规律性，同时数据的存储位置被精确指定，因 此查询请求可以 通过d h t 高效 地路由 到相应的 存储节点 1 8 1 3 ) 松散结构网 络 ( l o o s e l y s t r u c t u r e d n e t w o r k ) : 松散结构网 络的 拓扑 介于非结构化和结构化拓扑之间，这类网络虽然存储着一些文件和存储位置的 提示信息， 但这些 信息受到访问的 影响而不断改 变，同 时数据和存储位置的 映 射没有被完全指定， 因 此不是 所有的 查找都能 成功1 8 . 由于 数据不能 被精确查 找， 第一章引言 因此本文不对该类网络进行深入探讨。 在非结构化网络中， 洪泛搜索采用广播的方式进行转发，发起查询的节点把 查询 请求转发到所 有与其相邻的节点，然后再由 相邻节点广播出 去; 而随机漫 步搜索查询 发起节点发出k 个查询请求给随机 挑选的k 个相邻节点，每个查询 信息在以后的转发过程中直接与发起查询的节点保持联系，每转发一步就询问 是否还要继续转发，如果发起查询节点同意继续漫步，则又开始随机选择下一 步转发的节点，否则中止搜索; 有选择转发搜索对洪泛搜索进行改进，节点在 转发查询请求时不是向所有相邻节点广播，而只选择部分的相邻节点进行转发， 减少网络流量。非结构化网络虽然具有搜索效率高、对网络动态性具有良好的 容错能力和能够支持规则表达式复杂查询等优点，但是采用的洪泛查找会造成 网络中流量急剧增加，导致网络失效，洪泛 ( f l o o d i n g )、随机漫步或有选择 转发算法虽然采用取 t t l作为参数，但是搜索直径不可控，非结构化网络被认 为是 不可 大规模扩展的t 7 ，因此本文不 对非结 构化网络进行深入 研究。 结构化网络采用规律性较强的拓扑组织节点，数据存储的位置被精确指定， 系统查 询效率高并且 d h t算法能 够精确查 找文件;系统避免了 广播式的 查找方 式，使得结构化网络具有良好的可扩展性。由于结构化网络的这些优点，本文 把结构 化 p 2 p网络作为分析和 研究的 重点， 在后续的相关 研究中 对结构化网 络 中的c h o r d , k o o r d e 和 c a n 进行详细介绍和研究， 在此基础 上提出 利用虚拟拓 扑建立p 2 p网络模型的方法。 第四 节 论文导读 本文 在研究现有的结构化p 2 p 系 统基础上， 提出一种利用虚 拟拓扑 建立p 2 p 网络模型的方法，之后利用该方法建立p 2 p - v t系统并对其核心机制进行研究。 论文的整体结构如下 第一章 介绍了p 2 p 网络的相关概念、 特点以 及分类， 通过对结构化和非结 构 化网络的对比分析引出本文重点进行结构化网络的分析和研究。 第二章主 要研究现有的结构化网 络系统c h o r d , k o o r d e 和c a n ，介绍 它们的 网络组织方 式和路由 算法，并分析结构 化网 络中 计算机和网 络拓的关系。 第三章在c h o r d , k o o r d e 和c a n 结构化网 络研究基础上， 进一步分析计算机 和网络拓扑之间的关系，指出结构化网络不能维护完整拓扑的原因，在此基础 上提出虚拟拓扑的概念和利用虚拟网络拓扑建立 p 2 p网络模型的方法。 第一章引言 在提出利用虚拟拓扑建立p 2 p 网络模型方法后， 为验证该方法的可行性和正 确性，第四章利用该方法建立 p 2 p - v t模型并对模型整体结构进行描述，建立了 模型的虚拟节点存储方式和查询算法。 第五章进一步对 p 2 p - t v网络模型中计算机加入、退出和容错性进行研究， 提出相应的运行机制和解决方法。 在 p 2 p - t v 模型与核心 机制建 立完成 后， 第六章对模型的查 询效率、负载情 况和计算机连接度进行仿真，并把仿真结果与 c h o r d . k o o r d e系统进行比较分 析。 第七章在仿真和分析 基础上对本文 所做的 工作进行总结 和展望。 第二章相关研究及技术 第二章 相关研究及技术 由于非结构化网 络存在不可扩展问题，现有的大规模 p 2 p网络大都是基于 d h t ( d i s t r i b u t e d h a s h t a b l e ，分布式哈希表) 技术构建的结构化网 络。 采用 d h t 技术构建的系统可以精确指定数据存储的 位置， 并且系统具有良 好的可扩展 性和高效的查询速度。本章首先介绍 d h t网络采用的一致性哈希算法，然后详 细描述c h o r d . k o o r d e 和c a n 三个典型的结构化网络。 第一节 一致性暗希 一 致性哈 希 4 1 是以 哈希函 数为核 心而建 立的 分 布 式 存储协议， 它 通过哈 希函 数把存储的数据和计算机节点映射得到数据键值和计算机编号，数据键值和计 算机编号在同一键值空间，数据存储在编号与数据键值接近的节点上。系统采 用特定的拓扑把计算机节点依照其编号组织成能 够进行路由查询、 存储的网 络。 这样的网络精确定义了数据存储的位置，同时覆盖网络采用规律性较强的拓扑 实现， 在查询时 可以 利用拓扑的规律快速到达查询终点，系统具有良 好的查询 效 率一 致 性 哈 希 没 有 定 义 具 体的 哈 希 算 法 14 1 ， 可以 采 用 现有的s h a - 1 iz l , m d 5 等哈希算法。一致性哈希具有以下的特点: 1 ) 哈希函数具有平衡特性，它能够把存储的数据均匀分布到键值空间中。 2 ) 一致性哈希中的每一个哈希桶 ( 即 存储数据的计算机) 不需要知道所有 桶的相关信息，而只存储部分桶的信息。 3 ) 当某个哈希桶发生变化时 ( 即计算机加入或离开系统时) ，不需要对己 经映射的所有数据项进行重新映射，而只需把发生变化的桶中存储的数据进行 映射即可。 c h o r d . c a n 和k o o r d e 都基于一致性哈希构建， 以下对c h o r d . c a n 和k o o r d e 进行详细介绍。 第二节 c h o r d 网络协议 c h o r d 网 络 协议 是为 解决p 2 p 网 络扩展 性问 题 提出 的 n ， 该协议 采用 一 致性 哈希在网络中构建一个分布式哈希表，并通过哈希表把查询请求转发到目 的节 7 第二章相关研究及技术 点。c h o r d 的一致性哈希首先通过基本的哈希函数给节点和数据分别分配一个m 位比特 ( b i t ) 长的i d 和键值 ( k e y ):节点的i p 地址被哈希得到节点i d ， 而 数据的关键字被哈希得到键值。节点i d 和数据键值的长度m 是构建系统前预先 选定的常量，其大小要使得两个节点或者两个关键字被哈希到同一个值的可能 性基本可以 被忽略。 c h o r d 没有定义具体的哈希算法， 而是将其规定为s h a - 1 1 1 . c h o r d 协议的覆盖网络采用了环 ( r i n g )拓扑进行组织，节点被按照i d 大 小组织成为一个环， 其中 每个节点存储着后面一个与自 己i d 最为接近的节点的 信息，所有节点形成一个首尾相连的环 ( 如图2 . 1 所示)。i d 值等于键值k 或 者在环中紧接在k 后的节点称为键值k 的后继节点， 表示为s u c e s s o r ( k ) ，键 值k 被存储在其后继节点上。图2 . 1 所示的c h o r d 网络中，键值7 的后继节点 是0 ， 因此它被存储在节点0 上， 而键值4 的后继节点是6 而被保存在节点6 上。 为了 快速查询键值， 每一个节点需要维护一个。 项的 路由 查找表( f i n g e r t a b l e ) ，每一个表项存储网络中一个键值及其后继节点的信息 ( 如i p 地址)， 查询时可以 直接对后继节点转发请求。功为n 的节点的路由查找表按照以下规 则 进 行组 织 : 表中 第i 项 存 储的 键 值为( n 十 2 - ) m o d 2 m， 对 应的 后 继 节 点 为 s = s u c c e s s o r ( ( n + 2 ) m o d 2 m ) ， 其中1 i m o c h o r d 查 询 利 用节 点 存 储的 路由查找表进行，发起查询的节点首先搜索查找表，找到一个键值与要查询的 键值最为接近的项，然后向其对应的后继节点转发查询请求;收到查询请求的 节点如果发现自己 存储了 被查询的键值，则直接回应查询节点，如果没有存储 被查询的键值，就从查找表中选择键值与查询键值最接近的项，并转发请求到 对应后继节点上:该过程一直持续到找到相应节点为止。从查找表的组织和查 询的过程可以看出， c h o r d 路由转发的过程就是二分搜索的过程， 在二分搜索过 程中 ， 每 一 次 查 询 经 过 的 路由 步 调( h o p s ) 为o ( lo g n ) 阶 ls l ， 其中n 为 网 络中 节点个数。 图2 . 1 中是一个m = 3 的c h o r d 网络，i d 为o , 1 , z , s 的节点加入到系统 中，图中带箭头的虚线代表一次路由转发过程，当节点1 查询键值7 时从在查 找表中找到与7 最接近的键值是z ，把查询请求转发到对应的节点s 上，节点s 再按照相同的规则把请求转发到节点0 ， 节点0 存储键值7 所以直接向节点1 进 行回复。 第二 章 相关研究及技术 图2 . 1 c h o r d 网络和查询 c h o r d 系统具有良 好的负载平衡性和扩展性，同时它是一个完全分布式的系 统， 具 有很好的 抗 攻击的 能力， 但每个节点 需 要维 护o ( l o g n ) 大 小的 路由 查找 表，增加了网络开销.后来的结构化网络大都借鉴了c h o r d 的一致性哈希方法， 但它们都采用其他的网络拓扑来降低节点维护的路由查大小， 减少了网络开销。 第三节 内容寻址网络 内 容 寻 址网 络( c o n t e n t - a d d r e s s a b l e n e t w o r k , 简称c a n ) 16 1 采 用一 致 性哈 希 来构建网络， 但其哈希算法与c h o r d 网络的有所不同。 c h o r d 中， 哈希得到的键 值是一维的， 利用这些一维的键值组成一个环拓扑，而在c a n 中，哈希的结果 用d 维的笛卡尔空间来表示， d 是一个由系统规模决定的常量。 由于采用了d 维 笛卡尔空间，因此节点拓扑的是按照虚拟的d 维空间进行组织的.在任何时候， 整个坐标空间被系统中所有的节点划分，每一个节点拥有其单独的，与其他节 点截然不同的坐标空间区域。 第二章 相 关研究 及技术 虚 拟的坐 标空间 用于存储关键字和数据 值对( k e y , v a l u e ) ， 为了 存储( k e y , v a l u e ). k e y 被哈希算法映射到d 维坐标空间 中的一 个点p 上， 如果节点n 的 坐标空间 区 域包含点p ，则该 ( k e y , v a l u e ) 对被存储在节点n 上。 节点 在查 询 ( k e y , v a l u e )时， 只需通过哈希算法把k e y 映射到点p 上， 然后通过相应的 路由查询找到存储点 p的节点即可. c a n中节点加入时随机选择坐标空间中的一 个点a ， 然后 发送一个加入请求到点a ，当 加入请求被路由 到坐标空间包含点a 的节点上时，该节点把其空间划分成两半，把其中一半分配给新加入的节点。 一 卜路由查询- 叫 卜文件存储 一牛76543n1 2 n1 n21oil 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a ) (b ) 765 n3432 n1 n210一 n5n3. _, f4n2i- 1 1- i i i- 0 1 2 3 4，6 7 0 1 2 3 4 5 6 7 ( ) ( a ) 日口口曰曰巨口口尸口口口口匕口 日口口口口口口口门口口口口口口 口口口口口口口口口口口口口口口 口口口口口口口口口口口日口口口 口口口口口口口口口口口口口口口 口国口口国口口口口国口口口巨口 日口口口口口口口口口口口口口口 日口口门日日口口口口口口口口口 门口口口口口口口口口口口口口 口口口口口园口口门口口门口口口 门口口困习n a日回口口口回口口口口 一 侧 口口口口口口口 口口口口口口口口 口 引 口口口口口口口口口日习口口 门n t口口网口口国口口园口口口 曰 、 囚口网【口口口口口口口口口口 曰口口日日、口口口口口口口口口口 图2 . 2 c a n坐标空间划分和路由查询 第止章相关研究及技术 图2 . 2 中 的c a n 是采用二维的7 0 空间建 立的， 其中图( a ) , ( b ) 和( c ) 显示 了 计算机加 入时c a n 坐标空间划分 过程，图( a ) 中系 统只 有一个节点n 1 加入， n 1占据了整个坐标空间;当图( b ) 中节点n 2 加入时，空间被平均分成两部分， n 1占据左半部分， n 2 拥有右半部分:图( c ) 中节点n 3 加入时， n l 拥有的空间被 分成两部分。当节点n 4 , n 5 加入后，坐标空间划分情况如图( d ) 所，其中文件 f l 的关键字被哈希后的空间坐标为( 2 , 3 ) ，处在节点 n l 拥有坐标空间内，因此 f l由节点 n l 维护，同理 f 2由n 2 维护，f 3 由n l 存储。 c a n 网 络中 节点的 路由 表构建按照d 维笛卡尔空间 进行， 节点存储着所 有邻居 节 点的i p 地址和对 应的 坐标区 域. 在d 维坐标空间中， 如果两个节拥有的坐标 空 间区域在 d -1 维上是交迭的，而在剩下一维上是邻近的，那么这两个节点相互 称 对方为 邻居节点。 在图2 . 2 ( d ) 中， 节点n 5 的 邻居节 点为n 4 和n 2 ， 节点n 5 2 会存储着它们的相关信息。 c a n 进行路由 查询时，发起查 询的 节点从自 己的路由 表中查 找与路由目 的坐 标最为接近的邻居节点，把查询消息转发给该节点;节点在接到其他节点转发 的查询消息时， 首先查看自己 拥有的 坐标空 间是否包含要查找的路由目 的 坐标， 如果包含则直接向 发起节点进行回复，否则 把路由 信息转发到与目 的 坐标最为 接近的邻居节点;该过程重复进行直到查询消息到达路由目的坐标为止.如果 节点发现邻居节点 表中 没有可 用的 下一跳节点，则 使用受控的泛洪算法在网中 搜索合适的下一跳节点。 如果 加入系统的所有节点 把d 维笛卡尔空间划分称为 相同大小的区域， 那么所有节点组成一个 d 维的t o r u s 拓扑。 c a n网络中查询的 平均查 询步跳为研d , n i d ) 阶。图2 . 2 ( d ) 中当节点n 1 查询文件f 4 时，首先 把 f 4的关键字进行哈希得到对应的坐标为 ( 7 , 5 )，n 1 查看自己邻居节点，发现 节点n 2和n 3 距离查询坐标一样近，因此随机选中节点 n 3 进行转发， 0 则把消 息转发到n 4 节点 上， 由 于n 5 与查找坐标最近， n 4 把消息 转发到n 5 , n 5 节点维 护的空间包含了坐标 ( 7 , 5 )，它会直接给节点n l 进行回复。 第四节 k o o r d e 网络协议 k o o r d e 网 络 3 把c h o r d的 环 拓 扑 和d e b r u i j n 图 i 结 合 起 来 组 织 节 点 。 与 c h o r d 一样， k o o r d e 中节点i d 和数据 键值被哈希到( 0 ,2 m ) 的 空间， 数据键值也被 存储在其后继节点 ( s u c c e s s o r )上。d e b r u i j n图中编号为 n的节点指向编号 为( 2 n ) m o d 2 m 和( 2 n + 1 ) m o d 2 的两 个节点，因 此k o o r d e 中 每一 个节点 需要维 第二章 相关研究及 技术 护 两 条 边 ， 节 点 n 维 护 着 指向s u c c e s s o r ( n +1 ) 的 边以 及 指 向 s u c c e s s o r ( ( 2 n ) m o d 2 m ) 的前 驱 节 点 的 边， 之 所 以 只 维 护 s u c c e s s o r ( ( 2 n ) m o d 2 ) 的 前驱 节点而没有维护s u c c e s s o r ( ( 2 n 十 1 ) m o d 2 m ) 的前 驱是因 为网 络中每一个 节点 维护着一个后 继节点， 只要找到了s u c c e s s o r ( ( 2 n ) m o d 2 m ) 就可以根据 其 后继节点找到s u c c e s s o r ( ( 2 n + 1 ) m o d 2 .) 。 k o o r d e 查询键值 k e y 时只需 查找s u c c e s s o r ( k e y )的前 驱节点， 然后 通过 其找到存储k e y 值的s u c c e s s o r ( k e y ) 节点。 如果编号0 到2 m 之间 所有的 节点 都加入到网 络中， 那么系 统中 的 d e b r u i j n 拓扑是 完整的， 因此查 询只需要按 照 d e b r u i j n 图的路由 过程进行就能完 成。 但 k o o r d e 网络中 通常只包含( 0 ,2 勺 空间中的部 分节点， 拓扑 不是一个完 整的d e b r u i j n 图，因 此k o o r d e 需要通过 环拓扑 来模拟在完 全的 d e b r u i j n图中 进行 路由。 k o o r d e中 的 节点 在进行 d e b r u i j n路由时， 总是将查询传 递给该节点的 前驱节 点， 再由 前驱节 点去转发， 如果路由的 下一跳节点 i没有 在网 络中， 则需要前驱节点 模拟 把查 询请求转发 到假想节点 i ，然后再模拟从假想节点 i 路由到其他节点。k o o r d e网络中一次 查询的路由步跳为 0 ( 1 0 酬) 。 台b r u ij n 连接 路由 环拓扑连接 图2 . 3 k o o r d e 网络和路由查询 图 2 . 3 显示了一个 m = 3的k o o r d e 系统，黑色的圆圈代表己经加入系统的节 点，节点 n中 存储了 指向s u c c e s s o r ( ( 2 n ) m o d 2 m ) 的前驱节 点的边的信息，图 第二章 相关研究及 技术 中以 带箭头的虚线表 示， 如图中 节点1 0 0 指向的d e b r u i j n 节点应该是0 0 0 ， 其 前驱节 点为1 1 0 ， 因此节点1 0 0 与节点1 1 0 之间有连接关系。 除了d e b r u i j n边 以 外， 节点还具有环拓扑 连接关系，参与系统的节点会存 储在环中 紧接着自己 的 节点 信息， 如图中0 0 1 节点会 存储着节点0 1 0 的信息， 而0 1 0 会存储节点 1 0 0 的 信息，图中通过环上带箭头的 边表示。当节点 1 0 0 查询 键值 0 0 1 时，首先根 据d e b r u i j n 路由 方法得到 下一 步跳节点编号为0 0 0 ， 把查询 请求转发到它的前 驱 1 1 0 节点，节点 1 1 0接到转发的请求后，发现 0 0 0节点没有参与到系统中， 因 此自己 模拟节点0 0 0 进行路由 转发，根据d e b r u i j n 路由， 下一步跳是0 0 1 , 因此查询请求被转发到 0 0 1 节点并到达查询的终点。 第五节 本章小结 本章详细介绍了c h o r d , c a n和k o o r d e 结构化网络，这些网络基于分布式 哈希表构建， 解决了系统的扩展性问题。 c h o r d网络中节点的度 ( 即单个节点需 要维护的邻居节点个数)为 l o g n ， 节点的维护开销使得系统 扩展性受到一定影 响; c a n采用的 t o r u s 拓扑减少了 节点度， 但网 络的动态性 使得系 统拓扑不可 能 保持 完整 t o r u s 结 构，因 此 c a n的节点 连接方 式和路由 查询 算法是在 t o r u s 基础上修改而成: k o o r d e 采用了 具有良 好特性的d e b r u i j n 图作为网 络拓扑， 但 为解决网络动态性它嵌入了一个环拓扑，由于不是所有的节点都存在网络中， 因 此k o o r d e 中节点 连接 方式和路由 查询在d e b r u ij n 基础上进行了 修改， 通过环 拓扑模 拟完整d e b r u ij n 拓扑的 路由 来完成查询。 c h o r d , c a n和k o o r d e 网 络以 及现在结构化网络在系统运行过程中维护的网络拓扑通常是不完整的规律性较 强的拓扑，这使得在建立模型时不能直接采用结构化拓扑的路由算法和拓扑连 接方式， 而需要对其进行修改， 这增加了模型建立的复 杂度和工作量。 在这类 网络中，计算机通常对应着拓扑中的节点，当计算机加入到系统中时，该节点 出现在拓扑中，而当计算机退出以 后， 拓扑就会缺少 该节点，网 络拓扑是随着 计算机 加入、 退出变 化而变化的。 本文希望在 p 2 p系统中 保持一个完整的、具 有良好规律性的拓扑，使得系统的查询能够直接使用拓扑的路由算法实现，简 化系统实现。 第二章基于虚拟拓扑的 p 2 p模型 第三章 基于虚拟拓扑的p 2 p模型 c a n和k o o r d e 系统希望 通过利用一些规律 性较强的 拓扑来组织网络中的计 算机，并根据拓扑的特点进行数据的存储并完成数据的快速查询和定位。利用 分布式哈希表把节点组织成为规 律性较强的拓扑的方法解决了 系统可扩展性问 题， 但网络动态性使得系统 在实际 运行 过程中维护的拓扑不是一个完整的 具有 较强 规律性的拓扑，它只 是近似于预先定义的如t o r u s 或d e b r u i j n 等规律性较 强的 拓 扑. 其 他 的 结 构 化 系 统 ， 如 建 立 在m e s h 拓 扑 上 的p a s tr y jg j， 采 用 蝶形 网 络 建 立 的v ic e r o y 2 0 1， 同 样由 于 网 络 动 态 性 使 得 实际 运 行 中 它 们 维 护 的 拓扑 只是 近似于m e s h 和蝶形网 络， 这使得在建 立模型时不能 直接采用系统 对应的 规律性 较强拓扑的 路由 算法和拓 扑连接方式， 而需要对其进行修改，这增加了 模型建 立的复杂度和工作量。 本章在研究现有结构化网络中计算机和拓扑关系的基础 上，提出利用虚拟拓扑来建立p 2 p 模型的方法。 第一节 计算机和拓扑的关系 c h o r d , c a n和 k o o r d e 虽 然没对系统中节点概念进行定义， 但这些网络的 相关 研究 3 ,5 ,6 表 明 : 在 这 类 系 统中 覆 盖网 络 拓 扑中 节 点 通 常 对 应 一 个 计 算 机， 即 拓扑节点和对应的 计算机是 “ 捆绑” 在一起的。 加入系 统的计算机通过哈希算 法分配一个唯一的i d ， 如果该