（计算机软件与理论专业论文）网络敏感的对等网络覆盖网的若干关键技术研究.pdf

网络敏感的对等网络覆盖网的 若干关键技术研究 摘要 在互联网发展日新月异的今天，对等网络系统扮演了越来越重要的 角色。但是对等网络系统在被广泛应用的同时也占用了大量的互联网带 宽。统计数据说明，目前互联网上的网络流量中有相当大的部分属于对 等网络应用所产生的流量。进一步地研究发现，对等网络系统产生这么 多网络流量的一个原因就是对等网络中有很多信息的传递是没有经过优 化地。而使这些信息以非优化的形式传递的一个主要原因就是对等网络 覆盖网和其下的物理网络之间的不匹配。简单的说就是覆盖网络对物理 网络不敏感。本文对结构化对等网络覆盖网和非结构化对等网络覆盖网 的网络敏感问题，以及与其紧密联系的网络坐标系统进行了研究。本文 的主要贡献和创新点为： 1 针对v i v a l d i 网络坐标系统的平均相对误差较小但是在计算较近节点 之间的距离时误差较大的缺点，提出了通过对计算出的网络节点恣 间的距离进行补偿的方法来减d x v i v a l d i 在计算较近节点之间距离的 误差。减小了这个误差，也就提高了从一系列候选节点当中选择出 最近邻节点的能力。实验证明，补偿后的v i v a l d i 在保持了原来平均 相对误差较小的特点的情况下，提高了选择最近节点的能力。本文 首先研究网络坐标系统的原因是网络坐标系统赋予了具有网络坐标 的节点感知其在网络空间中的相对位置的能力，任意两个节点可以 通过计算它们在网络坐标系统上的距离进一步判断它们在真实的物 理网络上的延迟大小。 2 针对非结构化对等网络覆盖网的网络敏感问题，提出了通过基于网 络坐标系统的随机散步粒子群节点聚类算法来进行覆盖网络优化的 方法。在研究对等网络覆盖网的网络敏感问题时的一个难点是如何 设计一个分布式的算法来优化覆盖网络。本文通过粒子群算法来解 决这个难题。这个算法的特点是使用虚拟的粒子代表节点在网络空 上海交通大学博士学位论文 间中运动，运动的方向通过粒子群算法来确定。通过计算出来的粒 子运动向量来选择粒子在网络空间中的下一个运动目标。粒子在每 访问一个节点时，都会使用适应度函数来计算它所经过的这个节点 作为它代表的节点的邻居的可能性。在经过定时间地运行后大部 分的节点都可以找到合适的邻居。经过实验证明，该算法是有效 的。 3 针对结构化对等网络覆盖网的网络敏感问题，提出了基于网络坐标 系统的网络敏感的路由选择和网络敏感的路由表构建两种技术。对 于结构化对等网络覆盖网具有固定的结构且路由表中的条目需要按 照一定规则指向其它的节点的特点，首先在c h o r d 覆盖网络中通过 设计双向的路由表，在路由时将下一跳候选节点的数量由一变为 二，并从中选取延迟较小者来降低路由延迟。对于网络敏感的路由 表构建技术，本文在以异或距离作为覆盖网络中节点标号距离的异 或网络上进行了研究。利用将下一跳的目标定义为包含目标节点的 更小的子树的方式，使得路由表中的每一个条目可以在一个较大范 围内选择任意一个符合条件的节点。由于路由表中的每个条目都可 在一个更大的范围内选择，因此可以选择更接近的节点加入路由 表。经过理论分析和实验证明，在优化路由表的基础上结构化覆盖 网络可以在保持原有路由时间复杂性的基础上降低路由时间，同时 使得异或覆盖网络上的任意两个节点之间的路由延迟保持在一个较 低的水平。而且这个路由延迟的期望值在一定程度上与覆盖网络的 规模无关。 关键词：对等网络，覆盖网，网络敏感，网络坐标系统 一一 r e s e a r c ho nk e yt e c h n i q u e so fn e t w o r ka w a r ep e e r - t o - p e e r o v e r l a yn e t w o r k a b s t r a c t r e c e n t l y p e e r - t o - p e e rn e t w o r ka p p l i c a t i o n sp l a y 蛳i m p o r t a n tr o l ei nt o d a y si n t e r a c t w h i l et h ep e e r - t o - p e e rt e c h n o l o g i e sm w i d e l yu s e d t h ep e e r - t o - p e e ra p p l i c a t i o n so c c u p i e d a l a r g e p a r t o f t h e i n t o n e t t r a f f i c sa c c o r d i n g t o t h es t a t i s t i c s a f t e r f u r t h e rr e s e a r c h i n g ，i t w a s f o u n dt h a to f l eo ft h er e a s o n st h a tc a u s e dt h o s et r a f f i c si st h en o n o p t i m i z a t i o no fr o u t i n g i np e e r - t o p e e rn e t w o r k a n dt h i si sc a u s e db yt h em i s m a t c h i n go ft h eo v e d a yn e t w o r kt o t h ep h y s i c a ln e t w o r ku n d e r n e a t h t h a ti st os a yt h eo v e r l a yn e t w o r ki sn o tn e t w o r k - a w a r e t h i sd i s s e r t a t i o nf o c u s e do ns o m eo ft h ek e yt e c h n o l o g i e st h a tm a k et h ep n e r - t o - p e e ro v e d a y n e t w o r kn e t w o r k - a w a r e m a i nc o n t r i b u t i o n sa n dc r e a t i v ep o i n t so ft h i sd i s s e r t a t i o na l ea s f o l l o w i n g 1 c o n s i d e r i n g t h e f a c t t h a t t h e r e i s a l l h i g hr e l a t i v e e r r o r i n c o m p u t i n g t h e d i s t a n c e l o n e a r p e e r si nv i v a l d iw h i l et h ea v e r a g e r e l a t i v ee r r o rr e m a i n i n gl o w , ar e p a i r e dv i v a l d iw a s p r o p o s e d i n t h i s d i s s e r t a t i o n i n t h e r e p a i r e d v i v a i d i ，t h e r e l a t i v e e r r o r i n c o m p u t i n g t h e d i s t a n c et on e a rp e e r si sd e c r e a s e d t h ee x p e r i m e n t ss h o wt h a tt h ea b i l i t yo fc h o o s i n g t h en e a r e s tp e e ra m o n gn e i g h b o r si sa l s oi m p r o v e di nr e p a i r e dv i v a l d iw i t ho n l yl i t t l e e x p e n s ei nt h ea v e r a g er e l a t i v ee r r o ra n dr e l a t i v er a n kl o s sr a t e t 1 l er e a s o nw h yw e d i g g e di n t on e t w o r kc o o r d i n a t e ss y s t e mf i r s t l yi st h a tm o s to ft h ea l g o r i t h m si nt h i s d i s s e r t a t i o nw e r em a k ee x t e n s i v e l yu s eo ft h en e t w o r kc o o r d i n a t e ss y s t e m w i t i lt h e h e l po fn e t w o r kc o o r d i n a t e ss y s t e m ，a n yp e e rc a r la w a r eo fi t sr e l a t i v ep o s i t i o ni n i n t e r n e ta n dc a l le s t i m a t et h en e t w o r kl a t e n c yt ot h eo t h e rp e e rw i t h o u tp r o b i n g 2 an e wr a n d o m w a l k i n gp a r t i c l es w a r l i ib a s e dn e t w o r kn o d e sc l u s t e r i n ga l g o r i t h mw a s p r o p o s e di nt h i sd i s s e r t a t i o nt oo p t i m i z et h eu n s t r u c t u r e dp e c r - t o - p e e ro v e r l a yn e t - w o r k o n eo ft h ed i f f i c u l t i e so fc l u s t e r i n gt h en e t w o r kn o d e si sh o wt oc l u s t e rt h e m m 一 上海交通大学博士学位论文 d i s t r i b u t i v e l y t h ep a r t i c l es w a r ma l g o r i t h ms o l v et h ep r o b l e me a s i l ya st h ep a r t i c l e s e x p l o r i n ga n de x p l o i t i n gt h en e t w o r ks p a c ei n d e p e n d e n t l y w h i l ep a n i c l e sf l y i n gt h e y c o m m u n i c a t i n ga n de x c h a n g i n gt h eb e s tf i t n e s st h e yf o u n d ，s ot h ep a r t i c l es w a l t i c a n f i n dab e t t e rf i t n e s sq u i c k l y t h ef l y i n gd i r e c t i o no f p a r t i c l e sa r ed e t e r m i n e db yt h ep a r - t i c l es w a m ia l g o r i t h m t h ep r o p o s e da l g o r i t h mi sb a s e de l lt h ef a c tt h a tt h en e t w o r k c l u s t e r i n ga l g o r i t h mi sa na l g o r i t h mt h a te a c hn o d ef i n dab e t t e rc l u s t e ri tb e l o n g st o s oa p p l y i n gt h e p a r t i c l es w a r ma l g o r i t h mi nn e t w o r kn o d e sc l u s t e r i n gp r o b l e m , w e c a l l c l u s t e rt h en e t w o r kd i s t r i b u t i v e l y 3 i ns t r u c t u r e dp e e r - t o - p e e ro v e f k l yn e t w o r k ，r e o g a n i 比t h ew e l lo r g a n i z e dn o d e si n t o an e t w o r k - a w a r eo v e r l a yi st o od i f f i c u l t i nt h i sd i s s e r t a t i o n ，an e t w o r ka w a r er o u t i n g a l g o r i t h m f o r c h o r da n d a n e t w o r k c o o r d i n a t e s b a s e d n e t w o r k p r o x i m i t y a w a r e r o u t i n g t a b l ec o n s t r u c t i o np r o t o c o lf o rm o r eo p t i m a lr o u t i n gw e i , ep r o p o s e d c o n s i d e r i n gt h e f a c t st h a tt h es t r u c t u r e dp e e r - t o - p e e ro v e r l a yh a sf i x e ds u u c t o r ea n dt h en e i g h b o r so f n o d ec a n n o tb es e l e c t e du n b e n d i n g l y ad u a ld i r e c t i o n a lr o u t i n ga l g o d t h mf o rc h o r d w a sp r o p o s e dt om a k et h er o u t i n gn e t w o r ka w a r e ，t h ed u a ld i r e c t i o nr o u t i n ga l g o r i t h m c a l lr o u t et h em e s s a g ei nc l o c k w i s ed i r e c t i o na n dc o u n t e rc l o c k w i s ed i r e c t i o nt o o t h u st h ea v e r a g ep a t hl e n g t hr e d u c e dt oh a l fo ft h eo r i g i n a l a d d i t i o n a l l y , d u et oe a c h o ft h es t e pc a nb ec h o s e nf r o mt w oc a n d i d a t en o d e s t h ee x p e c t e df o r w a r dl a t e n c y r e d u c e dt o o t h i sp a p e ra l s oi n v e s t i g a t e dt h en e t w o r kp r o x i m i t ya w a r er o u t i n gt a b l e c o n s t r u c t i o ni nax o rm e t r i cb a s e do v e r l a yn e t w o r k i nt h i so v e r l a yn e t w o r k ，n o d e s i nt h eo v e r l a yn e t w o r kc a l lb ev i e w e da sl e a f si nav i r t u a l 忧e n t r i e si na r o u t i n gt a b l e c a n b ev i e w e da st h ep o i n t e r sl ot h e 打e e sn o n - o v e d a p p e d s ot h er o u t i n gt a b l ee n t r i e s c a nb ep o i n t e dt oa n yn o d ei nt h ec o r r e s p o n d i n gt r e e t h u st h e r ea r em o r ec a n d i d a t e f o r e a c h e n t r y o f r o u t i n g t a b l e s o t h e r o u t i n g t a b l e e n t r y c a n b e o p t i m i z e d b y c h o o s i n g o n eo ft h en e a r e s tn o d e i tw a sp r o v e db yt h e o r e t i ca n a l y s i sa n de x p e r i m e n t si nt h i s d i s s e r t a t i o nt h a tt h er o u t i n gl a t e n c yi no v e r l a yn e t w o r kw i t ho p t i m i z e dr o u t i n gt a b l e c a nh er e d u c e dw h i l em a i n t a i n i n gt h es a m et i m ec o m p l e x i t y a n dt h ee x p e c t e dr o u t i n g l a t e n c yi sl o wa n dh a sn or e l a t i o n s h i pw i t ht h es c a l eo fo v e r l a yn e t w o r k k e yw o r d s ：p e e r t o - p e a rn e t w o r k , o v e r l a yn e t w o r k , n e t w o r ka w a r e n e s s ，n e t w o r kc o - o r d i n a t e s 一一 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： e t 期： 姿迂 五正夏 ) 五i 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定。同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于竺竺手年解密后适用本授权书。 不保密6 z ( 请在以上方框内打“ ”) 学位论文作者签名：菱支 日期：2 衄年卫月厶包日 指导教师签名：幽 日期3 泣年卫月止日 第一章绪论 随着n a p s t e r ! 、g n u t e l l a 2 这样的文件共享软件在i n t e m e t 上被成功地应用，对 等网络【3 】引起人们普遍关注，同时也吸引众多研究机构和研究人员投入到这个研究 领域。对等网络之所以会这么引起人们关注是因为对等网络模型改变了原来以客户 端棚务器为特征的分布式计算模型，使得分布式计算能够方便地利用i n t e r n e t 边缘 的资源。随着接入i n t c m e t 的计算机也越来越多，i n t e r n e t 也越来越庞大。原来的客户 端，服务器结构中的服务器不堪重负，成为系统的瓶颈。与此同时，个人计算机的功 能也越来越强大，足以分担服务器的计算任务。而许多时候连接在互联网上的众多 个人计算机的资源却处于赋闲状态。如果能够将这些赋闲的计算机资源有效的利用 起来，将能够很好地解决现存的计算资源、存储资源等不足的情况。对等网络模型 为解决这些问题提供了方法。 在对等网络模型中，网络节点都具有相同的地位，网络资源分布在各个 节点上；每个节点既可以作为服务器也可以作为客户端，不存在集中的服 务器。由于在对等网络的结构中不存在特定的节点充当服务器，因此也不会 出现由于服务器性能不足造成的系统瓶颈；而且对等网络计算模型可以将网 络上闲置的资源组织起来向外提供服务，这样就可以充分利用网络资源，例 如s e t i h o m e 4 和o c e a n s t o r e 5 6 】。s e t i h o m e 是一项旨在利用连入因特网的成 千上万台计算机的闲置能力“搜寻地外文明( s e l l ，s e a r c h i n g f o r e x t r a t e r r e s t r i a l i n t e l l i g e n c e ) ”的巨大试验。该项目用基于对等网络的分布式计算模型将网络上闲置 的计算能力聚合起来，并利用这些聚合起来的巨大的计算能力分析和处理来自天文 望远镜的微弱信号。目前该项目已经成为b o i n c 项即7 的子项目，此项目包含了包 括s e t i h o m e 在内的众多科研项目，例如关于地球科学的科学计算和关于生物医学 的科学计算。s e t i h o m e 的成功经验已经让更多科学研究获益。s e t i h o m e 通过 使用对等网络模型聚合了网络上闲置的计算能力，而o c e a n s t o r e 贝u 将网络上闲置的存 储能力组织起来。o c e a n s t o r e 是加州大学伯克利分校的研究项目，这个项目的目标是 全球一致性数据存储，任何计算机都可以加入此体系贡献其存储资源。 对等网络的基础和核心是对等网络的覆盖网络( o v e r l a yn e t w o r k ) 。发展迅速 的对等网络覆盖网自产生以来出现了许多不同的拓扑结构。主要可以分为两大类： 非结构化对等网络，例如g n u t e u a 2 和f r e e n e t 8 上海交通大学博士学位论文 结构化对等网络，例如c h o r d 9 ，c a n i l 0 ，t a p e s t r y 1 1 、和p a s 仃y 【1 2 】 在这两大类之外，还有一种混合式的对等网络。这种对等网络的主要代表 是n a p s t e r ，它是早期的对等网络。现在随着对等网络的发展，混合式的网络由 于网络中具有中心服务器而逐渐不再是研究的重点。 1 1 对等网络概述 g n u t e l l a 2 是一个纯对等网络，它具有非结构化的拓扑。在这种拓扑结构中没有 集中的服务器，网络中的所有节点地位完全相同。重要的是在g n u t e l l a 节点之间无需 维护拓扑信息，因而在g n u t e l l a 网络中查询一个资源时多使用“f l o o d i n g ”( 泛洪) 算法。一般认为由于使用了泛洪搜索算法，该网络中的通信量会随着网络尺度的增 长而指数增长，因此网络中的流量负载过大，这个特性使得g n u t e l l a 网络可伸缩性受 到限$ 0 1 1 3 1 1 4 1 1 5 。 分布式结构化对等网络的拓扑具有严格的结构，如c h o r d 【9 】。c h o r d 网络中的节 点按照键值的大小排列成一个圆形的拓扑。在查找资源时，首先给定资源的名称， 然后通过哈希函数计算出资源对应的键值，而要查找的资源就存放在这个键值的后 继节点上。这种方法的优点是查询过程中的每一步路由都是可计算的，从而减少了 对路由信息的需要。缺点是每个节点上需要路由表保存网络的拓扑结构信息，当一 个节点加入或者离开网络时需要更新路由信息，维护网络的拓扑结构；另一个缺点 是结构化对等网络只能实现基于键值的查找，这样显得不够灵活。在对等网络中， 基于内容的查询是一个很有意义的查询方式，而在分布式结构化对等网络中实现基 于内容的查询是比较困难的。 混合式对等网络是象n a p s t e r 这样的对等网络，在网络中有一个集中服务器，它 作为索引服务器使用，在这个服务器上存有网络中的节点地址信息以及节点上共享 资源的信息。当网络中的一个节点需要查找某个资源时，首先向索引服务器发送查 询请求，得到存放该资源的目的节点的地址，然后在从该节点上得到资源。实际的 文件传输发生在请求节点和目的节点之问。这种结构的优点是查找资源时很方便， 只需将查询请求发给索引服务器即可。但缺点也比较明显，它仍然存在客户服务器 结构的缺点，当网络规模增大时，集中的服务器会成为系统的瓶颈，也会出现单点 故障。 在这三种结构中，每种结构都各有优缺点。但是对于分布式结构化对等网络和 混合对等网络这两种对等网络，它们的缺点是和它们的结构有关的，要想消除它们 一2 一 第一章绪论 的缺点是不容易的。对于分布式非结构化对等网络，它的缺点在于采用了简单的泛 洪查找算法，使得查找效率较低，通信负载较大，导致网络的可伸缩性受限【1 5 】；对 发出的搜索消息使用1 1 l ( t i m e t o l i v e ) 参数限制搜索范围，致使有些资源可能会 找不到。 1 1 1 非结构化对等同络 非结构化对等网络路由协议中最典型的和影响最大的是g n u t e l l a 1 6 】。c m u t e l l a 路 由协议是一个开放的、分布式的组成员关系管理和搜索协议。它的主要用途是在 互联网上共享和交换文件。在互联网上，所有使用g n u t e l l a 语言( 协议) 的应用程 序可以访问彼此共享出来的资源。每个g - n u t e l l a 节点，称为服务者( s e r v e n t ) ，在 这个文件共享网络中具有两种角色。它是服务提供者( s e r v e r ) ，又是服务使用者 ( c l i e n t ) 。每一个服务者既提供了客户端接口供其它服务者访问共享资源，查询和 返回查询结果；也提供了覆盖网络维护的功能( 如对管理消息的处理) 和维护网络 完整性的功能。 霪。谨 “於“ 亿d o 等o 刊 图l l 非结构化对等网络中的路由和搜索 f i g1 1t h es e a r c h i n ga n d r o u t i n g i nu n s t r u c t u r e d p e e r - t o - p e e r n e t w o r k s 节点为了加入到g - n u t e l l a 网络中去，必须知道至少一个已经在网络中的节点( 服 务者) 。通过这个节点，新节点得到网络中的其它节点的地址，并向其它的节点发 出问候。在g n u t e l l a 中，消息有两种传播方式：一种是广播( b r o a d c a s t ) ，节点向所 有已经建立t c p 连接的节点发送消息；一种是反向传播( b a c k - p r o p a g a t e d ) ，消息沿 着广播消息所经过的路径被发送回去。 g n u t e l l a 中的消息传递和路由可以由图1 1 中的右半部分来表示。在这个图 中，左边的图为以n a p s t c r 为代表的混合式对等网络。右边为以g n u t e l l a 为代表 的非结构化对等网络中的搜索。在更新的g n u t e l l a 协议中，引入y s u p e r p e e r 来增 强g n u t e l l a 网络的性能和伸缩性。总体来看，c _ m u t e l l a 中的消息的传递是以广播或 泛洪为基础的。当一个节点需要找到一个未知的资源时，向洪水般泛滥的消 一3 一 上海交通大学博士学位论文 表i ig n u t e l l a 搜索产生的带宽【1 4 1 t a b l e1 1b a n d w i d t hi n c u r r e db yg n u m l l aq u e r yi nb y t e s 1 4 】 t = 3t = 4t 三5t t 习t = 8 n = 48 ，6 3 22 6 5 6 08 0 3 4 42 4 1 6 9 67 2 5 ，7 5 2 2 ，1 7 7 ，9 2 0 n = 51 7 ，4 3 0 7 0 ，5 5 02 8 3 ，0 3 0 1 ，1 3 2 ，9 5 04 5 3 2 ，6 3 0 1 8 1 3 1 3 5 0 n = 63 0 8 7 6 1 5 5 ，3 7 67 7 7 ，8 7 63 。8 9 0 ，3 7 61 9 ，4 5 2 8 7 69 7 ，2 6 5 3 7 6 n = 74 9 ，9 6 6 3 0 0 ，9 5 8 1 8 0 6 9 1 0 1 0 ，8 4 2 ，6 2 26 5 ，0 5 6 ，8 9 43 9 0 ，3 4 2 ，5 2 6 n = 87 5 ，6 9 65 3 1 2 0 0 3 ，7 1 9 ，7 2 8 2 6 ，0 3 9 ，4 2 4 1 8 2 ，2 7 7 ，2 9 6 l ，2 7 5 ，9 4 2 ，4 0 0 息会占用很大的网络流量。g n u t e l l a 中可以用来控制消息个数的参数就是消息最 大步长盯t l ，t ) 和同时打开的连接数( n e i g h b o r sn u m b e r , n ) 。在b 4 中的研究 中，揭示了t 和与g n u t e l l a 产生的网络流量之间的关系。如表格1 1 所示。从这 ”个表格中可以看出，当和t 增长时，在网络上产生的流量会爆炸式增长。在每 个消息的长度时8 3 字节( i ph e a d e r ( 2 0b y t e s ) ，t c ph e a d e r ( 2 0b y t e s ) ，g n u t e l l a h e a d e r ( 2 3b y t e s ) ，m i n i m u ms p e e d ( 1b y t e ) 和s e a r c hs t r i n g ( 1 8b y t e s + 1b y t e ) 。 共8 3 字节) ，n = 8 ，t = 8 时，一次查询将在有2 0 0 0 + 节点的g n u t e l l a 网络上产 生6 3 7 ，9 7 1 ，2 0 0 - 7 - 节的流量【1 4 】。 显然在对等网络应用程序改变了人们使用互联网的方式同时，也产生了巨大的 网络流量。g n u t e u a 消息传递的存储和转发的结构决定了g n u t e l l a 的覆盖网络拓扑与 物理网络之间差距越大，给物理网络带来的压力也就越大。但是目前很难计算出 任意时刻覆盖网络拓扑与物理网络之间的匹配程度，也很难精确的使覆盖刚络拓 扑与物理网络完全匹配。目前的互联网络拓扑是一种由路由器连接起来的自治系 统( a u t o n o m o u ss y s t e m ) 的集合。而自治系统本身也是由局域网组成的。从互联网服 务提供商的角度来看，跨越自治系统边界的流量比自治系统内部的流量更昂贵。因 为那涉及到复杂和较贵的网间结算。在1 1 7 中提到，只有2 5 的g n u t e l l a 连接是处 在同一个自治系统中的，并且4 0 的节点位于最大的l o 个自治系统中。【1 7 忡的结论 表明，大量的g n u t e l l a 流量没有必要地跨越了自治系统边界，产生了没有必要的带 宽。这也说明如果可以更好地维护无结构化对等网络的拓扑，就可以显著地减少对 等网络运行时需要的网络带宽的数量 1 1 2 结构化对荨网络 1 1 2 1 结构化对等同络的覆盖网络 由于非结构化对等网络采用泛洪之类的随机搜索算法带来了伸缩性差等缺点， 一4 一 5 第一章绪论 结构化的对等网络系统引起了研究者的兴趣。在结构化对等网络系统中，每个节点 只存储特定的信息或特定信息的索引。当用户需要在对等网络系统中获取信息时， 它们必须知道这些信息( 或索引) 可能存在于哪些节点中。由于搜索算法知道应该搜 索哪些节点，避免了非结构化对等网络系统中使用的泛洪式查找，提高了信息搜 索的效率。目前主要的结构化的系统( 如c h o r d 9 】) 都是基于分布式哈希表的分布 式发现和路由算法。这些算法中，既没有如n a p s t e r 那样的中央目录服务器，也没有 像g n u t e l l a 那样通过泛洪进行搜索。通过分布式哈希表，覆盖网络中的每个节点在虚 拟的覆盖网络空间中具有一个特定的位置，每个关键字也被映射到覆盖网络中的某 个特定位置。通过路由算法，关键字的位置与覆盖网络中的节点建立了存储关系。 在结构化的覆盖网络中，存在于物理网络中的计算机被称作节点。存储在节点 中的数据被称作对象。在覆盖网络中的一个对象名称的集合被称为名称空间。在覆 盖网络中，对象通过名称相互区别。同样的，在覆盖网络中，每个节点也具有一个 独立且不重复的名称。在物理网络中，一个节点的标识可以用这个节点的网络地址 来代表，或者用这个节点的网络地址和节点名称的结合来代表。在以分布式哈希表 为基础的结构化对等喇络中，每个节点具有一个唯一的标识符。这个标识符是使用 散列函数在节点的名称上散列后得到的。这个过程可以用p = h a s h ( i p ：p d n ) 来表 示。散列函数的功能是将关键字映射为整数，映射后的整数的分布是均匀的分布。 而且这个映射的过程是不可逆的。在将多个关键字映射到整数空间时，可能会发生 多个关键字映射到同一个整数上的情况，这种情况叫做散列冲突。一个较好的散到 函数是几乎不会发生散列冲突的。在目前地研究中，一致性散列函数s h a l 最为常 用，它将每一个关键字映射到一个1 6 0 位的二进制整数空间中去。 图1 2 为基于分布式哈希表的分布式对等网络覆盖网络的一般结构。从图中可以 看出，隐藏在分布式哈希表后面的是覆盖网络中的节点。通过分布式哈希表的映射 作用，节点分布到虚拟的哈希表中，根据路由协议分别负责一部分数据标识符空间 地存储。而建立在对等刚络覆盖网络之上的应用，则通过简单的哈希表操作来在分 布式存储空问中进行插入、删除、和读取操作 由于c h o r d 和k a d e m l i a 1 8 这样的一维的基于分布式哈希表的结构化对等网络上 的消息路由都在逻辑空间上进行，它们的路由算法具有一定的相似性，路由选择都 是在当前节点上选择下一跳，由下一跳继续选择转发的节点直到日标节点接收到消 息。不同的是，有的实现在使用下一跳的时候使用迭代式的( 如k a d e m l i a ) ，有的 采用递归式的( 如c h o r d ) 。选择下一跳的原则是要求下一跳距离目标节点的距离要 一5 一 上海交通大学博士学位论文 比当前节点距离目标节点的距离缩短l 2 。这样路由策略带给大部分的结构化对等网 络o ( t o g n ) 路由复杂度，也提高了系统适应不同网络规模的伸缩性。但是由于路由 选择仅考虑覆盖网络上的虚拟节点地址，忽略了节点之问在物理网络上的距离。因 此在选择路由时虽然选择了距离目标节点在覆盖网络上近的节点，却无法保证“下 一跳”在物理网络上是否接近目标节点。这带来了结构化对等网络上的拓扑匹配问 题。 回回回回 图1 2 分布式哈希表的结构 f i g1 2s t r u c t u r eo ft h ed i s t r i b u t e dh a s ht a b l e s 图1 3 中的圆代表了一个具有l o 个节点，存储有5 个关键字的c h o r d 环。图中的小 圆点代表了覆盖网络中的节点，而这个大的圆代表了覆盖网络( 分布式哈希表) 。 在这张图上，还有代表着关键字的方形。图中，k 5 4 代表散列值为5 4 的关键字，这 个关键字存储在节点n 5 6 上。 图1 3 一个具有1 0 个节点，存储有5 个关键字的c h o r d 环 9 】 r 9 1 3 a c h o r d r i n g w i t h l o n o d e sa n d 5k e y b 1 1 2 2 结构化对等网络 本节以典型的基于分布式哈希表的分布式对等络c h o r d 9 i g q k a d e m l i a 1 8 例简单介绍结构化对等网络的覆盖网络。如图1 3 ，c h o r d 中的节点以节点i d ( i d = h a s h ( x p ) ) 的顺序顺时针摆放在虚拟的圆环上。这个圆环代表c h o r d 的标识符空间。 一6 l 第一章绪论4 这个空间大小为s = 1 1 妒卜在c h o r d 中的任意一个节点的n o d e a d s ，同样，任 意一个关键字的k e y _ i d s 。 基于分布式哈希表的结构化对等网络的路由的基本思路是：在每次消息转发 到下一跳时，要求转发的日的节点距离目标的距离要比当前节点距离目标节点 的距离减少至少1 2 。这样一来，在一个具有个节点的d h t 环中，至多l 0 9 2 n 次 转发后，消息可以被送达目标节点。在c h o r d 中，每个节点保留有指向其所在 覆盖网络拓扑中前一个节点( p r e d e c e s s o r ) 和后一个节点( s u c c e s s o r ) 的指针。 在c h o r d 中，p r e d e c e s s o r 和s u c c e s s o r 被用来维护整个覆盖网络的可达性，并作为覆盖 网络中消息路由的最后手段来使用。为了更有效地进行消息路由，c h o r d 中使用了一 种被称；为f i n g e r t a b l e 的路由表。节点n 的f i n g e r t a b l e 中的第k 个表项中包含的指针指 向在虚拟环中顺时针方向上距离当前节点距离至少为2 的第一个节点。在图1 4 中， 节点8 的f i n g e rt a b l e 中包含4 个节点，分别是1 4 ，2 l ，3 2 ，和4 2 。 图i 4 节点8 的路由表( f i n g e r t b b l e ) 【9 1 f i g1 4t h er o u t i n gt a b l eo f n o d e8 图1 5c h o r d 的路由过程【9 】 f i g1 5 t h e m u t i n g p r o c e s s o f c h o r d o a o r d 路由算法比较简单。c h o r d 使用f i n g e rh a b l e s c 寸其顺时针方向上的覆盖网 络地址空间进行了划分。每个f i n g e r t a b l e q 的表项都对前一项的月标区域进行了 二分。从图1 5 中地路由过程中可以看出，c h o r d 在路由时选择的节点是：在当前 节点的路由表中距离目标节点最接近的节点。消息被这样转发，直到目标节点就 一1 一 上海交通大学博士学位论文 在当前节的f i n g e r t a b l e 中、或者是当前节点的s u c c e s s o r 、或者当前目标节点并不 存在而目标k e y 处在当前节点和当前节点的s u c c e s s o r 当中。图1 6 描述了这个算法的 执行过程。c h o r d 的路由算法是在环状的逻辑空间中逐渐地逼近目标的1 9 】中证明 了c h o r d 路由算法在具有的节点的c h o r d 覆盖网络中的平均跳数为；f 卵 耐ja ds h n n l ，_ d “ n 州j m t a i _ w “m l i d ( n _ h i ， t 一j t 一 - = d _ 州十删埘n 止) n 一r j 碰n n t 研( 哪 h 耐妇o * , m 幽社舡k 口吲_ - 一 _ - j 叫q j 叫坤 m d 0 _ _ i r u 叩f ( n 邮l ，_ - m j 刊】 图1 6 c h o r d 的路由算法【9 】 f i g1 6 t h e m u t i n ga l g o r i t h m o f c h o r d 1 1 2 3 结构化对等网络k a d e m i i a 的路由 k a d e m l i a 【1 8 】也是一种基于分布式哈希表的结构化对等网络。与c h o r d 相同的 是，k a d e m l i a 使用s h a 1 算法计算节点的i d 和生成关键字