（信号与信息处理专业论文）bittorrent类网络的位置知晓性研究.pdf

fd l ；： l j l ! 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名： 碴罐 本人承担一切相关责任。 日期：坦参犟i a 挫旦一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在玉年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：迎垒垒丑挫旦 日期：冱竺6 ：1 ：巡 基熏飞 毒 l 乍p 一 国 j + 每 一 摘要 b i t t o r r e n t 类型网络的位置知晓性研究 摘要 近年来，大量的研究结果表明现今的互联网网络流量己不仅仅由 h t t p 、f t p 、p o p 3 、s m t p 等传统业务流量所占据，对等( p e e r - t o p e e r ) 网络产生的流量占据了网络流量的大部分。p 2 p 以其相对于c s 模式 的巨大优势，不仅激发了信息技术领域科研人员的研究热情，而且也 调动了普通人对p 2 p 的使用和期望。这些因素使p 2 p 成为一个热门 的前沿研究领域。p 2 p 技术的迅速发展和投入应用，给现今的互联网 带来了流量类型的冲击，大量的网络带宽被p 2 p 应用占用。由于对等 网络较松散的组织方式，导致大量的网络流量的重复，浪费了带宽。 根据p e e r - t o p e e rw o r k i n gg r o u pc o m m i t t e e 的定义，p 2 p 在商业上的 应用主要有文件共享、边界服务、分布式计算，但文件共享是目前最 重要的一个应用。 b i t t o r r e n t 文件共享系统作为典型的p 2 p 技术的应用，采用了多源 下载机制，下载速度快，资源享用免费，得到了用户的广泛青睐，成 为我国最热门的下载方式之一，同时，也给网络带来了沉重的流量负 担。 通常p 2 p 网络很少考虑底层物理网络，随机选择逻辑邻居节点， 导致p 2 p 网络和底层物理网络问拓扑结构的不匹配，p 2 p 网络性能因 此受到严重制约，大量浪费了底层物理网络的资源。本文讨论p 2 p 网络的位置知晓性问题，分析造成底层网络重复消息的理论原因，研 究b i t t o r r e n t 类型的对等网络( p 2 p ) 的位置知晓性问题。首先，以校园 网环境为实验平台，测试b i t t o r r e n t 应用的位置知晓性，通过测量试 验的数据论证了b t 网络也存在一定的位置知晓性问题。第二，对该 问题的优化，研究现有的改善位置知晓性的解决方案。第三，根据网 摘要 络环境的实际情况，提出缓存服务器系统，采用基于内容缓存的方式 改善b i t t o r r e n t 型对等网络的位置知晓性问题，并且通过在校园网中 部署缓存服务系统，进行实验测试，以验证该系统可以减少p 2 p 下载 过程中的网络间流量，减轻网络运营商的负担。 关键字对等网络位置知晓性拓扑匹配b i t t o r r e n t r e s e a r c ho nt h el o c a t i o n a w a r e n e s s i nb t - l i k e p e e r t o p e e rn e t w o r k a bs t r a c t r e c e n t l y , l o t so fr e s e a r c hr e v e a lt h a tt h et r a f f i co nt h en e t w o r ki s n o to n l yc o m p o s e do ft h et r a d i t i o n a lt y p e so ft r a f f i cs u c ha sf e p o p 3 ， s m t pa n ds oo n p e e r - t o - p e e rn e t w o r ki sf ln e w t y p en e t w o r kt h a tu s e r s t a k ea d v a n t a g ei nr e s o u r c es h a r e p 2 p , a san e wn e t w o r ks c h e m e p r i o r t o t h ee x i s t i n gc ss c h e m e ，h a si n s p i r e dn o to n l ym a n yr e s e a r c h e r sw o r k e d i nt h ei n f o r m a t i o nt e c h n o l o g yf i e l d ，b u ta l s ob e e na t t r a c t i v et om a n yo t h e r p e o p l e a n dn o w , p 2 pt e c h n o l o g y 。h a sb e e no n eo ft h em o s th o tr e s e a r c h f i e l d sw h i c hl e a d i n gt h es c i e n c e p 2 pt e c h n o l o g ys i g n i f i c a n ti n f l u e n c e s t r a f f i cb e c a u s ei tc o n s u m em u c ho fb a n d w i t h ab i gp o r t i o no fp 2 p t r a f f i ci s r e p e a t e da n du n n e c e s s a r yb e c a u s eo fi t s l o o s em a n a g e m e n t a r c h i t e c h t u r e a c c o r d i n gt ot h ed e f i n i t i o no fp e e r - t o p e e rw o r k i n gg r o u p c o m m i t t e e ，p 2 pc a nb eu s e di nt h ef i l es h a r i n g ，d i s t r i b u t e dc o m p u t i n g a n ds oo n b u tf i l es h a r i n gi st h ed o m i n a n tp 2 p a p p l i c a t i o n b i t t o r r e n ti sa np o p u l a rp 2 pa p p l i c a t i o nw h i c hi sf o c u so nf i l e s h a r i n g i tu s e sm u t i s o u r c e sd o w n l o a dm e c h a n i s m t og e tg r e a td o w n l o a d p e r f o r m a c e i na d d i t i o n ，u s e rd o w n l o a dr e s o u r c e st o t a l l yf o rf r e e t h e r e f o r e ，i tb e c o m e so n eo ft h em o s tp o p u l a rd o w n l o a da p p l i c a t i o n 3 一t文 ，一一 m e a n w h i l e ，t r a f f i cg e n a r a t e db yb tm a k e st h en e t w o r ko v e rb u r d e n e d p 2 pn e t w o r k sa r eo f t e nc o n s t r u c t e dw i t h o u t c o n s i d e r i n g t h e u n d e r l y i n gp h y s i c a ln e t w o r ka n dt h el o g i c a ln e i g h b o rp e e r sa r ec h o s e n r a n d o m l y s ot h ep 2 po v e r l a yn e t w o r km i s m a t c ht h ep h y s i c a ln e t w o r k t h em i s m a t c h i n gp r o b l e ml i m i t sg r e a t l yt h ep e r f o r m a n c eg a i nf r o mp 2 p a n da b u s e st h er e s o u r c eo ft h ep h y s i c a ln e t w o r ki n f r a s t r u c t u r e t h i sp a p e r d i s c u s s e st h el o c a t i o n - a w a r e n e s s p r o b l e m i nb i t t o r r e n t - l i k ep 2 p n e t w o r k s f i r s t ，w eb u i l ds i m u l a t i o ne n v i o r o n m e n tb a s e do nc a m p u s n e t w o r ka n dt h el o c a t i o n - a w a r ep r o b l e mi nb tn e t w o r ki sp r o v e db ya m e a s u r e m e n ts t u d y s e n c o n d ，w es t u d yo t h e rw o r ka b o u tl o c a t i o n a w a r e p r o b l e m t h i r d ，w ep r o p o s eam e t h o dn a m e dc a c h es e r v e rs y s t e m ，w h i c h i sb a s e do nc a c h i n g ，i m p r o v en e t w o r kp e r f o r m a n c e t h ec a c h es e r v e r s y s t e mc a nr e d u c et h et r a f f i cb e t w e e nn e t w o r k sa n dt h ec o s to fn e t w o r k o p e r a t o r s k e y w o r d s ：p e e r - t o - - p e e rl o c a t i o n - a w a r et o p o l o g y - m a t c h i n gb i t t o r r e n t 4 一 ，- i l f1 1 人 f 叠 目录 第一章绪论1 1 1p 2 p 网络概述1 1 2p 2 p 叠加网的第一种分类2 1 2 1 非结构化p 2 p 叠加网j 2 1 2 2 结构化p 2 p 叠加网5 1 3p 2 p 叠加网的第二种分类1 1 1 3 1集中式p 2 p 叠加网1 1 1 3 2 分布式p 2 p 叠加网1 2 1 3 3 混合型p 2 p 叠加网1 2 第二章p 2 p 网络的位置知晓性1 4 2 1叠加层上的重复消息1 4 2 2 拓扑不匹配造成的重复消息1 5 2 3 改善位置知晓性相关工作1 6 第三章非结构化p 2 p 应用b jt t o r r e n t ( b t ) 2 1 3 1b i t t o r r e n t 工作原理2 1 3 1 1b t 网络概述2 1 3 1 2b t 下载流程2 3 3 2b t 位置知晓性测量实验2 6 3 2 1 实验目的2 6 3 2 2 实验原理2 7 3 2 3 实验设备2 8 3 2 4 测量工具2 8 3 2 5 实验步骤2 8 3 2 6 实验结果2 9 第四章b t 位置知晓性改进方案3 1 4 1 缓存服务器系统原理3 1 4 1 1t m a 功能概述3 1 4 1 2 内容缓存服务器概述3 2 4 2 提取识别热门资源原理分析3 2 4 3 缓存服务器系统部署3 4 4 4 实验结果3 6 4 5 部分源码3 8 参考文献、5 3 致谢5 8 h i 、l 、。 卜 令 声 北京邮电大学硕士学术论文 第一章绪论 1 9 9 9 年，n a p s t e r 首次提出了对等( p e e r - t o p e e r ) 网络的概念，构建了包括 一个集中目录服务器的对等文件共享网络。它是首个可从多个节点而非一个服务 器上下载热门文件的系统。这种p 2 p 系统完全是自组织的：并且加入的人越多， 其下载能力就越强。n a p s t e r 是集中式系统，存在一个仅仅存储拥有资源的各个 节点的地址目录的集中目录服务器。这对服务器端的带宽要求就非常低，大大减 轻了服务器的流量负担。但是，该系统有一个不可恢复的点，如果目录服务器端 出现问题，整个系统将无法工作，尽管资源仍然存在于网络，用户由于无法访问 目录服务器则不能定位资源。不过，由于n a p s t e r 网络中存在的资源是流行音乐， 因此，由于版权问题，美国唱片联合会( r i a a ) 迫使n a p s t e r 关门歇业。但是， n a p s t e r 打开了对等网络的大门，促使了后来各种p 2 p 系统的发展。 b t 是目前最热门的下载方式之一，它的全称为“b i t t o r r e n t ”简称“b t ，中文 全称“比特流”。b t ( b i t t o r r e n t ) 是第三代混合式p 2 p 网络的典型代表，它采用 了“多源文件传输协议”( m f a v ，t h em u l t i s o u r c ef i l e t r a n s f e rp r o t o c 0 1 ) ，可以通过 检索分段从多个用户那里同时下载文件，最终将下载的文件片断拼成整个文件， 实现了多源文件的高速下载。协议定义了传输、压缩和打包的标准。每个文件都 7 使用m d 5 h a s h 算法所获得串标识，这使得文件可以使用较短的一串数据标识其 唯一性。 据研究机构c a c h e l o g i c 调查，b t 占了全球网络流量的三分之一。而当b t 用 户选择p e e r 下载资源时并不对其位置信息进行过滤。以校园网为例，当校内主 机拥有资源，而当其他用户下载该资源时，并不会优先下载校内资源，而是以同 样的概率从校内和校外的资源下载，这样，事实上浪费了校园网的出口带宽。类 似的情况也发生在运营商的角度，由于b t 不具有位置知晓性，其网络流量不仅 占用大量出口带宽，运营商还需要为网间流量付出高额的费用。因此，如果将位 置知晓功能加入b t ，不仅能节省带宽，还能降低运营商的费用，提高网络利用 率，同时，不影响b t 使用者的用户感受。 1 1p 2 p 网络概述 对等叠加网络的结构是分布式的，并且没有任何分层次的结构或中央控制机 制；加入对等网络的节点完全是自主组织的，并构架在i p ( i n t e r n e tp r o t o c 0 1 ) 网 络之上。对等网络具有许多优点，如健壮的大区域路由体系结构，数据搜索的高 第1 页 第一章绪论 效性，附近节点的发现和选择，冗余存储，良好的可扩展性以及容错性等。与传 统的c s ( c l i e n t s e r v e r ) 模式不同，加入对等网络的节点既从网络获取资源， 又提供资源，同时具备客户端和服务器的功能。 p 2 p 叠加网络可以看做是在现有的通信网络架构上的网络模型，是一个完全 分布式的，具有互操作性的自组织系统。图1 - 1 所示，为p 2 p 叠加网络的基本架 构图。网络通信层描述了桌面系统连接到因特网的网络性质，本文所研究的p 2 p 网络构架在i p 网络上。叠加网节点管理层涵盖节点的管理，包括节点发现以及 最优路由算法选择等。功能管理层包括网络安全性、可靠性、容错性以及资源有 效性等。服务层为底层p 2 p 结构提供支持，通过并发任务、内容以及文件管理提 供服务级的组件。数据内容管理描述p 2 p 节点存储的数据内容以及位置信息。应 用层描述在p 2 p 叠加网络结构之上所实现特定功能的工具、应用和服务。 应用层 服务层 功能管理层 叠加网节点管 理层 网络通信层 图1 - 1p 2 p 叠加网络架构示意图 1 2p 2 p 叠加网的第一种分类 p 2 p 叠加网络按照搜索定位资源的方式可分为两种：结构化的( s t r u c t u r e d ) 和非结构化的( u n s t r u c t u r e d ) 。 1 2 1 非结构化p 2 p 叠加网 非结构化的p 2 p 网络是以a d h o c 的方式来组织的。叠加网以平面的或分层 的( 例如，超级节点层) 方式组织节点，采用洪泛、随机步进等方式进行资源的 搜索定位。每个收到查询的节点将查询与自己拥有的资源进行比照，支持复杂的 第2 页 一 j j 北京邮电大学硕士学术论文 查询。这是一种低效的查询方式，由于数据位置和拓扑之间没有联系，所以查询 不得不将发送给较多的节点。本节将介绍几种常见的非结构化的p 2 p 叠加网： g n u t e l l a 8 】，f a s t t r a c k 9 k a z a a 1 0 】，b i t t o r r c n t 1 1 】，e d o n k e y 2 0 0 0 1 2 1 3 ，本 节介绍g n u t e l l a ，f a s t t r a c k k a z a a ，e d o n k e y 2 0 0 0 ，b i t t o r r e n t 将在后文详细介绍。 a g n u t e l l a g n u t e l l a 是非集中式分布查询协议，是平面型的拓扑。g n u t c l l a 使用非常广 泛。虽然g n u t e l l a 协议支持传统的客户集中式服务器搜索机制，但其最成功的 是其点对点、非集中式的文件存储和查询模式，如图1 - 6 所示。在这种模式下， 每个节点既是客户又是服务器。该系统既没有集中目录也不对网络拓扑或者文件 存储做硬性规定和强制管理。节点以某种很松散的机制加入网络，并组织网络， 因此数据的存储与网络拓扑完全没有关系，这是与结构化的系统最大的不同。当 需要定位数据时，节点以洪泛的方式向自己的邻居发起查询，该查询又将洪泛的 发送给其它邻居节点。这种机制对节点的加入和离开并不敏感，当一部分节点离 开网络时，网络并不会因此中断不能工作。但是可扩展性差，而且在网络中产生 了大量的流量。 ，廖：馈 ：节点。 鼍节点 ；节 图1 - 6 g n e t e l l a 网络 当新节点加入网络时，它首先连接一个长期在线的节点，在 h t t p ：g n u t e l l a h o s t s c o m 有这样的长期在线的节点列表。一旦连接到网络，节点发 送消息联系其它节点。这种消息或者是广播，或者是简单反向转发( 例如，只向 收到广播的路径的反方向发送消息) 。首先，每条消息有一个随机生成的i d ；第 二，每个节点保存一些最近转发的消息，以避免重复广播和支持反向转发；第三， 第3 页 ，1一 第一章绪论 消息有两个标志( f l a g ) ：t t l 和跳数。消息有以下几种： 组关系消息( g r o u pm e m b e r s h i pm e s s a g e s ) p i n g 和p o n g 。新加入的节点 发送p i n g 消息报告自己的加入。p i n g 消息转发给邻居并发起一个反向转 发p o n g 消息，包含其i p 地址、数据数量和大小： 查询消息( s e a r c hm e s s a g e s ) q u e r y 和q u e r yr e s p o n s e 。q u e r y 包含 用户指定的查询关键字，收到查询的节点将关键字与自己存储的文件名进行 匹配，并将消息广播。q u e r yr e s p o n s e 是反向转发消息，用以响应q u e r y 消息，包含下载文件所需的所有信息； 文件传输消息( f i l et r a n s f e rm e s s a g e s ) g e t 和p u s h 。文件下载和上传的两 个节点通过这两个消息完成下载过程中的通信。 b f a s t t r a c k k a z a a f a s t t r a c k 是非集中式的文件共享系统，并支持元数据( m e t a d a t a ，文件摘要) 搜索。网络中存在超级节点，这样可提高搜索效果，如图1 7 所示。超级节点拥 有较大的带宽、磁盘空间和较高的处理能力，并缓存元素据信息，以提供搜索功 能。普通节点将其共享的数据文件的元数据发送给超级节点，所有的查询信息都 转发给超级节点。类似g n u t e l l a ，f a s t t r a c k 节点也发送广播查询消息，但是仅仅 在超级节点之间洪泛发送。该p 2 p 系统在没有超级节点的情况下也可以运行，但 查询延迟将大大增大。超级节点采用广播协议来进行查询，查询消息被转发给与 查询相关的节点和超级节点。k a z a a 1 0 是f a s t t r a c k 协议的应用。 节点2 ：对象2 节点3 ：对象3 超级节点 超级节点 对象2 节点2 ：对象2 节点 节点3 ：对象3 图卜7f a s t t r a c k 协议网络结构图 k a z a a 采用f a s t t r a c k 协议，网络中有较大带宽连接的超级节点。节点数据 第4 页 苎童竺皇垄兰堡主兰查堡查 - ， 的指针存在与其连接的超级节点中，所有的查询消息都转发给超级节点。k a z a a 文件传输流量包括未加密的h 1 r r r p 传输：所有的传输包含能够标识k a z a a 的 h t i p 头，如x k a z a a i p 。该头可以使得k a z a a 流量很容易的从其他h t i p 流 量中区分出来。k a z a a 应用具有自动更新的特点，当k a z a a 运行时，它定期检 查是否存在更高的软件版本，如果找到，就从k a z a a 网络直接下载高版本。 节点每次启动时先到服务器上注册，从服务器上得到2 0 0 个超级节点的列表 ( 服务器中有s u p e m o d el i s tc a c h e ) 。本机上的k a z a a 程序会自动检查是否为超 级节点，如果是，就连到其它超级节点，如果不是就选择一个超级节点作为父节 点进行连接。与节点连接时，先用u d p 包来探察在s u p e m o d el i s tc a c h e 中所有 可用的连接，然后跟探察成功超级节点建立t c p 连接，再根据策略选择其中的 一个作为父节点，断掉其它的连接，然后向父节点上传其共享文件的信息。 选择父节点的策略通常是超级节点的负荷和超级节点的位置。位置的判断可 以依据i p 地址的前缀，r 订等。 用户搜索时，发送搜索请求到所父节点，然后父节点向其连接的超级节点广 播这个搜索请求，直到丌l 为0 。最终父节点在给用户的应答中会提供一个可用 的文件列表，以及文件所在节点的位置。用户从列表中选择一个地址，进行t c p 连接，发出文件请求( h t t p ) 。文件所有者进行响应( h t t p ) ，然后用此t c p 连接 传输文件。 c e d o n k e y 2 0 0 0 e d o n k e y 是混合的两层p 2 p 信息存储网络，由客户和服务器组成，创建一个 文件共享网络，可发布和查询小数据片。该体系结构具有以下功能： 1 节点可从多个节点同时下载文件； 2 使用哈希来验证文件的完整性和正确性； 3 下载的同时可共享已有部分的文件； 4 文件搜索的快速查询。 当节点( 客户) 加入网络时，需要知道另一个节点( 服务器) 的l p 地址和 端口号。然后节点连接服务器，并将自己共享的对象文件在服务器上进行注册， 这是通过传输文件的元数据实现的。注册之后，节点可通过两种方式来查询对象 文件：一是通过元数据查询，二是通过文件的唯一网络i d 。当客户查询时，服 务器提供对象文件的地址信息，客户根据地址信息连接响应的节点并下载文件。 1 2 2 结构化p 2 p 叠加网 结构化指的是p 2 p 叠加网的拓扑结构是可严格控制的，资源并不是随机分散 第5 页 第一章绪论 存储在节点上，而是以一种能使得查询更加有效的方式来存储的。这样的结构化 系统使用分布式哈希表( d i s t r i b u t e dh a s h t a b l e ，d h t ) ，将数据实体位置信息以 一种确定的方式分布在p 2 p 网络之上，节点的标识符( n o d e l d ) 对应数据实体 的唯一索引( k e y ) 。这种基于d h t 系统随机的将n o d e l d 分配给节点，n o d e l d 从一个较大空间的标识符库中选取，另外，分配给数据实体的标识符叫做索引 ( k e y ) ，同样也从相同的标识符库中选取。通过叠加网协议，将索引唯一的映射 到叠加网中的唯一节点。p 2 p 叠加网通过 索7 1 ，值) ( k e y ，v a l u e ) 这样的映射 对，支持可扩展的存储和检索，如图1 - 2 所示。给定一个索引，存储操作( p u t ( k e y , v a l u e ) ) 可将对应于该索引的数据对象进行存储操作，同样查找检索操作 ( v a l u e = g e t ( k e y ) ) 则可实现通过索引对数据对象的路由请求。 分布式结构化的p 2 p 叠加应用 |ll t 时i 煮叭 一a p i ： 妾1 2 1 ：p u t ( k e yv a l u e ) r e m o v e ( k e y ) v a 舯l u e l 接= g e 匝t ( k e y ) v 量i u e 一 专专 1 分布式哈希表( d i s t r i b u t e dh a s ht a b l e ) j ，1 。，1 、，j 、 j节点，；：节点 j 。节点)节点 。、， j ：j、，、j 。，7 _ ，! 、，j ： 每个节点维护一个很小的路由表，只存储邻居节点的n o d e l d 和i p 地址。查 询消息步进式的在叠加网上转发给n o d e l d 与索引接近的相应的节点。不同的基 于d h t 的系统有不同的数据对象组织形式，索引空间和路由策略。理论上，基 于d h t 系统可将任何数据对象的查找跳数平均限制在o ( 1 0 9 n ) 条之内，n 表示 整个系统中的节点数。底层网络的两节点之间的路径可能跟叠加网的路径大大不 同，即叠加层与物理层的网络不匹配。这样，查询延迟会非常大，会严重影响运 行的应用程序的效率。 典型的结构化p 2 p 应用有以下几种：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 ) j 1 1 ， c h o r d 2 ，t a p e s t r y 3 ，p a s t r y 4 。 a c a n ( 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 【1 】基于虚拟的多维笛卡儿坐标空间实现其数据组织和查找功能。整个d 第6 页 苎童竺皇垄兰堡主兰查笙查 。， 维坐标空间是完全逻辑性的。整个坐标空间动态地分配给系统中的所有节点( 假 设节点数为n ) ，每个节点都拥有独立的互不相交的一块区域。这就类似于一张 大哈希表，每个节点保存哈希表的一部分。此外，每个节点还保存少量的邻接区 的信息。对每个特定关键字的插入( 或者查找、删除) 请求，由中间的c a n 节 点进行路由直到到达包括该关键字的c a n 节点所在的区。如图1 3 所示，虚拟 空间用来存储 k e y ，v a l u e 对。存储一对数值 k ，v ，键k 通过标准的哈希函 数映射到一个坐标空间的一个点p 上。当节点需要查找时，首先查询相应的键值 k ，再使用相同的哈希函数将k 映射到点p ，最后通过点p 查询所需的值v 。如 果查询节点或者其直连的邻居没有点p ，该查询将被路由到c a n 空间其它点， 直到到达p 所在的点。节点维护的是与之相邻的区域的节点的球地址，直连邻 居节点的i p 地址信息表称为并列路由表，该路由表可提高点与点之间的路由效 率。 a 卜_ bxc v d 、i 。 i _ - e 点x 到节点 路由路径 节点x 的并列节点集= ab dz 新节点z 的并列节点集= ac dx 图1 3c a n2 维空间节点z 加入之前与之后示意图 当新节点加入该系统，必须有用自己的坐标空间。这可以通过将已有的区域 对半分开来实现，如图1 2 所示，留一半给原来的节点，将另一半分给新的节点。 c a nj 爿j 有一个d n s 域名，该域名可以解析为一个或多个c a n 引导节点( 维护 一部分c a n 节点的列表) 的i p 地址。当新节点加入c a n 时，节点在d n s 中查 询c a n 域名来检索引导节点地址。引导节点随机的向其提供系统中的一些节点 的i p 地址。新节点随机选择一个点p 向其发送j o i n 请求。每一个c a n 节点使 用c a n 路由机制转发消息，直到其到达p 所在的区域。之后现在在p 区域的节 点将该区域对半分，一半分给新的节点。 当节点离开c a n 网络时，接管算法保证了当节点发现邻居节点失败时，马 上接管那部分区域，并启动接管计时器。节点更新期邻居集来消除已不是它邻居 的节点。系统中的每个节点发送s o f t s t a t e 更新以保证邻居节点知道所发生的变 化并及时更新他们的邻居集。一个节点维护的邻居数目取决于，也仅仅取决于坐 标空间的维数，与系统中的节点总数目无关。 第7 页 第一章绪论 b c o r d c h o r d 使用连续的哈希给节点分配键值。连续哈希可以使得节点可以几乎不 影响网络结构自由的加入或者退出。这种分布式的架构更有利于流量在系统中的 均衡，因为每个节点收到的键值大致相同，并且当节电加入或离开系统时键值的 移动也是相当少的。在一种稳定状态，系统中有n 个节点，每一个节点维护的 路由状态信息复杂度仅仅为0 ( 1 0 9 n ) 。这是非常高效的，但当信息过期时系统 性能将严重下降。 连续哈希方程使用s h a 一1 1 5 1 作为基础哈希方程，为节点和数据键分配一个 m b i t 的i d 。节点i d 由哈希该节点的口地址获得，而键i d 由哈希数据键得到。 l d 的长度m 必须足够长，使得哈希出来的i d 不出现重复。i d 组织成一个模2 m 的圆环。键k 分配给第一个节点，该节点i d 等于k 或者紧跟k 之后。该节点被 称为键k 的后继，由s u c c e s s o r ( k ) 标示。如果i d 代表圆环数字0 到2 m 1 ，则 s u c c e s s o r ( k ) 是k 顺时针第一个节点。i d 圆环称为c h o r d 环。当一个节点n 要加 入网络，为了保持连续哈希映射关系，原来分配给i 1 的后继的键需要分配给n 。 当节点n 离开c h o r d 系统时，分配给它的所有键需要重新分配给n 的后继。如图 1 4 ，c h o r d 环的m 值为6 。该环有1 0 个节点和5 个键。i d l 0 的后继节点是节点 1 4 ，所以键1 0 应存放在n o d e i d1 4 上。类似的，如果一个l d 为2 6 的节点加入 系统，它将存储本来存在节点3 2 的键2 4 。 ? | 5 4 t n n 4 国 图1 - 4 新加入i d 2 6 节点的c h o r d 环 在c h o r d 环上的每一个节点都必须知道怎样与其后继节点进行通信。查询消 息需要匹配键值和n o d e l d 。给定一个i d ，查询信息会顺着圆环后继传递下去， 第8 页 北京邮电大学硕士学术论文 直到找到存储了所需i d 的节点。如图1 2 ，节点8 需要查询键值5 4 。节点8 发起 f m ds u c c e s s o r 操作，将返回该键值的后继，节点5 6 。查询信息访问c h o r d 环上 所有节点，响应信息将顺着圆环相反的路径传回给节点8 。 c t a p e s t r y t a p e s t r y 与p a s t r v 相似，它采用非集中式的随机机制来获得流量均衡和路由定 位。两者所不同的是它们处理网络位置和数据对象复制的方式，在下一小节介绍 p 雒t y 中，这种差异将会更明显。t a p e s t r y 的架构采用不同的p l a x t o ne t 口正【6 】分布搜 索技术以及其它技术已提高可用性、扩展性和适应性，来抗击网络中出现的错误 和攻击。p l a x t o ne ta 1 提出了一种分布式的数据结构p l 积t o n 网，所有的命名 数据对象都连接到一个根节点上。另一方面，t a p e s t r y 网络中，每一个数据对象 都连接到多个根节点，以避免单点失败。在p l a x t o n 网中，节点可以充当以下角色： 服务器( 存储数据对象) 、路由器( 转发消息) 以及客户( 查询实体) 。在每一个 节点采用本地路由映射，将路由消息进位增加的方式传给目标i d ，例如：掌，- 掌7 = ) 枣木9 7 = ) 2 9 7 = ) 3 2 9 7 ，事是通配符。而数字解析可以从左到右也可以从 右到左。节点本地路由匹配有多个等级，每个等级代表匹配i d 空间中字后缀匹配 ( s u f f i xm a t c h i n g ) 的程度。当消息到达第n 个节点，该节点至少匹配目标l d 的n 位 后缀。要定位下一条路由，第n + l 级映射将计算出下一位应该匹配的后缀的数字。 这种路由机制保证任何存在于系统的唯一的节点在删逻辑跳就能定位( n 为节 点数，b 为n o d e l d 长度) 。由于节点本地路由映射假定前面的数字匹配完全匹配 当前的节点后缀，因此节点在每一级映射只需要保存一个常量( b ) 大小的映射 表，整个路由映射表的大小是：( e n t r i e s m a p ) * n o o f m a p s = b * l o g 刖v 。 t a p e s t r y 的查询和路由机制根p l a x t o n 相似，就是基于n o d e l d 的后缀匹配实 现的。将路由映射分级，每一级包含一定后缀匹配的与之最近的节点集合。同样， 每个节点维护与之相邻的节点。t a p e s t r y 存储所有数据对象的地址，这样可以在 应用层方便的选择数据对象，例如按照时l 、日j 选择。除了距离向量，数据对象可能 包含一些可选的向量，例如o c e n s t o r c 【7 】全局存储系统查找的是最近缓存的文件， 同时也满足最近的距离向量。这些查询不完全遵循“寻找第一”的语义原则， t a p e s t r y 将这种消息第k 个近的数据对象。新节点加入时，先向系统预设的网关 节点( g a t e w a yn o d e ) 取得其路由表，然后将本身节点i d 与路由表中节点i d 做字 尾匹配，递归逼近，直到找到最相近的节点i d 的节点。然后从此节点取得其所 负责管理的文件地址信息。 d p a s t r y p a s t r y 与t a p e s t r y 类似，采用p l a x t o n - i 自i f 缀路由，建立自组织的非集中式的叠加 网，每一个节点都可路由客户查询，并能和本地一个或多个应用实例进行交互。 第9 页 第一章绪论 p a s t r y 网络中的节点被分配一个1 2 8 b i t 的节点i d ( n o d e l d ) 。n o d e l d 用来标示节点 在环状n o d e l d 空间的位置，大小从0 ( 2 e x p l 2 8 1 ) 。当节点加入网络时，随机为 其分酉? , n o d e l d 。在一个有n 个节点的网络中，给定一个键值，通常情况下在l o g b n 跳之内就能到达，其中n o d e l d 和键值是以b 为底的数字序列( b = 2 e x p b ) 。p a s t r y 将消息路由传递给n o d e l d 在数字上与查询键值最接近的节点。通常，节点将消 息转发给n o d e l d 与键值前缀匹配至少比当前n o d e l d 匹配多一位( 或b 位) 的节点； 如图1 5 ，每个p a s t r y 节点维护一个路由表，一个邻居集合一个叶子集。路由表有 i o g b n , ；f t 每行有b 1 个条目，第n 行的b 1 个条目代表匹配当前n o d e l d 前n 个数字的 节点，同时第n + 1 个数字不匹配当前节点n o d e l d 的第n + 1 个数字。路由表的每个 条目包含适当的前缀匹配的节点的i p 地址。b 的选择必须在两方面做出权衡：一 是路由表的大小( 约为 伊2 、7 ：) 木0 3 1 ) 个条目) ，二是任何两个节点问路由跳数 ( 1 0 9 b n ) 。 0 xl x2 x3 x4 xd xe xf x 3 0 x3 1 x3 2 x3 7 x3 8 x3 e x3 f x 3 7 0 x3 7 1 x3 7 2 x3 7 a x3 7 b x3 7 e x3 7 f x 3 7 a 0 x3 7 a l x 3 7 a 2 x3 m x3 7 a c x 3 7 a d x3 7 a e x3 乃虹x n o d e l d 为3 7 a o x 的路由表，b = 4 ，1 6 进制表示，x 是任意后缀 n o d e i d 3 7 a o f l 叶子集合( 较小的) 3 7 a 0 0 13 7 a 0 1 13 7 a 0 2 23 7 a 0 3 3 3 7 a 0 4 43 7 a 0 5 53 7 a 0 6 63 7 a 0 7 7 叶子集合( 较大的) 3 7 a o f 23 7 a o f 4 3 7 a o f 6 3 7 a o f 8 3 7 a o e a 3 7 a o f b 3 7 a o f c3 7 a o f e 邻居集合 1 a 2 2 3 bl b 3 4 6 72 4 5 a d o2 6 7 蝴 3 6 1 2 a b3 7 8 9 0 a3 9 0 a f 03 9 1 2 c d 4 6 7 1 0 a 4 7 7 8 1 0 4 8 8 1 a b4 9 0 c d e 2 7 9 d e 02 9 0 a o b5 1 0 a o c 5 2 1 3 e a 1 1 3 4 5 b1 2 2 1 6 71 6 2 2 8 a1 9 9 0 2 d 2 2 1 1 4 52 6 7 2 2 12 8 9 8 9 c1 9 9 a b c n o d e l d 为3 7 a o f l 的路由状态表，b = 4 ，l = 1 6 ，m = 3 2 第1 0 页 北京邮电大学硕士学术论文 广j b 5 7 8 2 d b 5 7 b 3 7 a o f l b 5 7 3 a bb 5 3 2 4 f 从节点3 7 a o f l 路由查找键值b 5 7 8 2 d 图l - 5p a s t r y 节点路由表，叶子集合表和