（通信与信息系统专业论文）结构化对等网络中基于访问热点的负载均衡策略研究.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处 本人签名：毒潍一一 本人签名：毒婪弛窿卜 ，本人承担一切相关责任。 日期：塑! ! ：至：! ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 e 1 期：趔乜：立：! ! 日期：筮丑里：三：! ! 辱 蠡 ： r p 2 结构化 的访问 中，对 数据资 的性能，导致出现请求消息丢失的情况。 本文对国内外现有结构化对等网络的负载均衡技术进行了分析 和研究。在全面细致分析访问热点问题的产生及已有解决策略的基础 上，提出了一种利用多哈希函数把访问热点复制到一组其它节点上的 策略，将热点产生的高负载平均的分布出去，并且可以动态的增加或 减少副本数量。即使在严重的负载不均情况下，该策略可以保持低的 访问时延和良好的负载均衡。 本文首先介绍了对等网络和现有结构化对等网络的负载均衡技 术，接着通过理论分析详细介绍了本文提出策略的执行和算法设计， 初步分析了该策略所需要的开销问题。最后仿真实验的结果证明了该 策略的有效性，并提出了策略的进一步改进。 关键词：结构化对等网络，访问热点，负载均衡，多哈希函数 e n v i r o n m e n t ，r e q u e s t sd i s t r i b u t i o n sa r eo f t e ns k e w e da n df o l l o waz i p f l a w , s o m eo b j e c t sw i l lb e c o m eh o t s p o t s ，i n d i v i d u a ln o d e sa r ee a s i l y o v e r l o a d e d ，r e s u l t i n gi np o o rg l o b a lp e r f o r m a n c ea n dl o s tm e s s a g e s t h i sp a p e rr e v i e w so nt h et e c h n o l o g yo ft h ec u r r e n tl o a db a l a n d i n g f o rt h ea n a l y s i sa n dr e s e a r c h i nac o m p r e h e n s i v ea n dd e t a i l e da n a l y s i so f t h ec a u s eo fq u e r yh o t s p o t sp r o b l e m sa n dt h em a i ns o l u t i o n ，t h i sp a p e r p r o p o s e dan o v e la p p r o a c hw i t hm u l t i p l eh a s hf u n c t i o n st or e p l i c a t et h e h o t s p o t si nas e r i e so fd i f f e r e n tn o d e st od i s t r i b u t et h eh i g hl o a de v e n l y , a n di tc a ni n c r e a s eo rd e c r e a s et h er e p l i c a sd y n a m i c a l l y a tt h es a m et i m e i tm a i n t a i n sl o wa c c e s sl a t e n c i e sa n dg o o dl o a db a l a n c i n ge v e nu n d e r h i g h l ys k e w e d d e m a n d f i r s t l y , t h ep e e r - t o - p e e rn e t w o r k sa n dt h et e c h n o l o g yo ft h ec u r r e n t l o a d b a l a n c i n gf o rs t r u c t u r e d p e e r - t o p e e rn e t w o r k sa r ei n t r o d u c e d s e c o n d l y ，t h ei m p l e m e n ta n da l g o r i t h mo ft h ea p p r o a c hp r o p o s e di nt h i s - ，p a p e ra r ei n t r o d u c e db yt h e o r ya n a l y s i s ，a n dt h ec o s tp r o b l e m n e e d e db y t h i sa p p r o a c hi sa n a l y z e d a tl a s t ，r e s u l t sf r o mp e r f o r m a n c ee v a l u a t i o n d e m o n s t r a t et h ee f f e c t i v e n e s so ft h i sa p p r o a c h ，a n da ni m p r o v e m e n to f t h i sa p p r o a c hi sg i v e n k e yw o r d s ：s t r u c t u r e dp e e r - t o - p e e rn e t w o r k s ，h o t s p o t ，l o a db a l a n c i n g ， m u l t i p l eh a s hf u n c t i o n s 北京邮电大学硕士学位论文 目 第一章绪论 1 1 研究背景 1 2 国内外对等网络技术的研究现状 1 2 1 国外相关研究。 1 2 2 国内研究现状。 1 3 论文选题与研究意义 1 4 本文的主要研究内容 1 5 论文章节安排5 1 6 本章小结5 第二章对等网络概述6 2 1 对等网络的定义6 2 2 对等网络的特点和发展7 2 3 对等网络的关键技术。9 2 4 两种对等网络。1 2 2 4 1 非结构化对等网络1 2 2 4 2 结构化对等网络1 3 2 5 本章小结1 6 第三章结构化对等网络的负载均衡技术。1 7 3 1 负载均衡技术1 7 3 2 负载均衡的分类1 7 3 3 结构化对等网络中的负载均衡问题1 8 3 4 对等网络中的访问热点问题1 8 3 5 访问热点问题现有的解决策略1 9 3 5 1 基于复制技术解决访问热点的策略1 9 3 5 2 基于留言传播解决访问热点问题的策略2 2 3 5 3 基于虚拟节点解决访问热点问题的策略2 3 3 5 4 三种策略优缺点比较2 3 3 6 本章小结2 4 第四章多哈希函数复制负载均衡的策略2 5 4 1 热点问题访问资源的特点详细分析2 5 4 2 利用多哈希函数进行负载均衡2 6 4 2 1 复制技术策略的设计考虑重点2 6 4 2 2 多哈希函数在已有负载均衡策略中的运用2 6 4 2 3 一种改进的利用多哈希函数复制的负载均衡策略2 7 4 3 利用多哈希函数复制的负载均衡策略详细设计2 7 4 3 1 策略的相关定义2 7 4 3 2 策略分析3 0 4 3 3 策略设计3 0 4 3 4 策略设计的补充说明3 5 4 4 利用多哈希函数复制的负载均衡策略的丌销初步分析3 6 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 4 5 本章小结一k 3 7 第五章策略的仿真分析及进一步改进3 8 5 1 解决访问热点及副本数的变化情况。3 8 5 2 资源请求节点的访问时延情况。4 0 5 3 策略的进一步改进4 1 5 4 本章小结4 3 第六章总结与展望4 4 参考文献4 5 致谢j 。4 8 攻读学位期间发表的学术论文目录4 9 它处在网络协议的应用层。在p 2 p 网络环境中，成千上万台彼此连接的计算机 都处于对等的地位，整个网络一般来讲不依赖于专用的集中服务器，打破了传统 的c s ( c l i e n t s e l n c t ) 客户机朋艮务器模式。网络中的每一台计算机既能充当网 络服务的请求者，又能对其它计算机的请求做出响应，提供资源和服务。通常这 些资源和服务包括：信息的共享与交换、计算资源( 如c p u 的共享) 、存储资源 ( 如缓存和磁盘空间的使用) 等。虽然对等网络从产生到现在并没有多长的历史， 但是它在应用领域和学术界获得了极大的重视与成功，并占据了当前i n t e m e t 一 半以上的流量资源【l l ，被称为“改变i n t e m e t 的新一代网络技术，【2 1 。因此，对等网 络在今天的网络中扮演了一个主导地位的角色，并且也快速进入了许多新的应用 领域。 随着网络技术的持续进步，如今d h t 已日益递增地用于广泛的分布式应用 中【3 l 【4 1 。和非结构化对等网络相比，它们具有高效的、可扩展的和自组织的特点， 为用于数据检索和管理的算法提供了关键优势。 但是，与其关键优势一起，d h t 仍然显示出在协作对等端集合中数据分布 的一个主要缺陷。所有系统常常依赖于这个基本假定，即在对等节点上数据是近 乎均匀地分布的。在大多数d h t 方法中，这种假设基于散列函数的使用，其将 数据映射到d h t 地址空间中。一般而言，人们假定散列函数在d h t 地址空问 上提供关键字和其对应数据的均匀分布。如果就每个对等端所管理的数据而言， 如果在节点负载中存在显著差异，那么系统的分布式自组织丌销可能增加甚快。 然而，如果简单地使用相容哈希的方法，则会导致节点负载不均衡。以c h o r d i 习 为例，相容哈希理论证明了当系统中有n 个节点和k 个键值的情况下，若在每 个节点上运行o ( 1 0 9 州v ) 个虚拟节点时，每个节点所负责的键值范围可以无限 趋近k n 。但是，即使每个节点在键值空间中负载的区域大小完全均等，各节点 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 的实际负载也不一定均衡。虚拟节点机制是解决这类问题的二种方法，但是虚拟 节点的引入也增加了节点路由表的大小，从而加重了网络拓扑的维护负担。最后， 具体的应用通常会和键值关联一定的语义，导致负载的分布不再均匀。例如，在 基于结构化对等网络流媒体应用中，资源的查找者对各节点上存储的索引信息的 访问往往是不均匀的，某些节点的负载很有可能因此而过大，成为“热点”。在资 源信息变化频繁的情况下，如果采取对索引信息进行复制的方法来分散负载，由 于副本一致性问题，对“热点”的访问量依然很大【6 1 。因此，为了将d h t 搜索算 法的复杂度保持在0 ( 1 0 9 ) 的预期范围内或更小( 其中n 是d h t 中的节点数 量) ，就需要适当的负载均衡机制。 1 2 国内外对等网络技术的研究现状 1 2 1 国外相关研究 当前，国外比较知名的对等网络研究，有麻省理工的i r i s 计划，s u n 公司 的j x t a 平台以及斯坦福大学的p 2 p 计划。 ( 1 ) i r i s 计划 为了解决r 益严重的因特网安全缺陷，美国国家科学基金会资助5 所大学和 研究机构合作开发一项安全的分布式数据存储系统，该计划名为i r i s ( i n f r a s t r u c t u r ef o rr e s i l i e n ti n t e m e ts y s t e m s ) 。从本质上讲，i r i s 将是最终的对 等网络，但是其研究人员感兴趣的不是路由器、交换机和骨干网络，而是资源定 位。瓜i s 不仅仅是一个文件共享系统，还是独立于应用的平台，基于该平台可 以方便地丌发其他分布式应用。 i r i s 计划的核心技术，足分布式敖列表d h t ( d i s t r i b u t e dh a s ht a b l e s ) 技术。 资助i r i s 计划的目的，是深入研究d h t 技术在对等i 删络r 1 ，的j 、审用，大规模地验 证已有的研究成果，最终建立安全的健壮的分布式网络。 ( 2 ) 斯坦福大学的研究 斯坦福大学主要是对对等网络系统的搜索、资源分配和聚集以及安全问题进 行了研究探讨，特别总结归纳了仍需要进一步研究的搜索和安全方面的丌放性问 题。搜索机制的关键性研究问题是要确保网络的有效性、可靠性、匿名性和访问 2 北京邮电大学硕士学位论文 控制。 1 2 2 国内研究现状 一雀国内 ，。目前北京大学j 清华大学与华中科技大学都开发出了相应的对等网 络系统，详细的介绍如下： ( 1 ) 北京大学m 钇e m a z e 是北京大学网络实验室开发的一个中心控制与对等连接相融合的对等 计算文件共享系统。在结构上类似n a p s t e r 7 1 ，对等计算搜索方法类似于 g n u t c l l a 剐。网络上的一台计算机，不论是在内网还是外网，可以通过安装运行 m a z e 的客户端软件自由加入和退出m a z e 系统。每个节点可以将自己的一个或 多个目录下的文件共享给系统的其他成员，也可以分享其他成员的资源【们。m a z e 支持基于关键字的资源检索，也可以通过好友关系直接获得。 ( 2 ) 清华大学g r a n a 巧 g r a n a r y 是清华大学自主开发的对等计算存储服务系统。它以对象格式存储 数据。另外，g r a n a r y 设计了专门的节点信息收集算法p e e r w i n d o w 的结构化覆 盖网络路由协议t o u r i s t 。 ( 3 ) 华中科技大学一a n y s e e a n y s e e 是华中科技大学设计研发的视频直播系统。它采用了一对多的服务 模式，支持部分n a t 和防火墙的穿越，提高了视频直播系统的可扩展性；同时， 它利用近播原则、分域调度的思想，使用l a n d m a r k 路标算法直接建树的方式构 建应用层上的多播树，克服了e m s 等一对多模式系统由联接图的构造和维护带 来的负载影响。 对等网络技术在国内的应用还刚刚丌始，多数人对对等网络的认识还不完 整，甚至还有很多的误解。例如盗版问题、管理性差等很容易与对等网络联系起 来。实际上，每个具有划时代意义的创新在刚出现的时候往往可能被人们误解。 对等网络这次也不例外，但这是技术创新的力量，我们不能因为现有的某些习惯、 体制而扼杀技术创新带来的进步。 1 3 论文选题与研究意义 3 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 人们在享受对等网络带来的方便快捷的同时，也面对诸多的问题。比方说， 对等网络系统中的节点的性能差别很大，主要体现在它们的c p u ，存储空间和 带宽等方面的差异。这些差异导致节点负载不均的问题比较严重。即一部分的节 点负载超出了该节点的处理能力，而另二部分节点负载却远远低于其处理能力。 在一个拥有海量节点的对等网络系统中，它们很容易因为节点的负担过重而延缓 了处理速度，使得向其请求服务的节点无法在可接受的时间内得到服务，导致内 容资源没有高效地被利用；另外，某些节点由于访问量小，其处理能力被闲置， 导致其处理能力资源没有被充分地利用。正是由于这些节点的异质性，大大地影 响了对等网络的性能。现实中各种各样的问题使得在对等网络中的潜在资源并没 有被充分、高效地利用。因而，为了使对等网络能够更直接、更充分、更高效地 利用互联网中所蕴含的潜在资源，必须研究网络中的负载均衡。因为，负载均衡 是实现资源有效共享，提高系统资源有效使用率的必然要求，是影响网络系统服 务质量的重要因素之一。所以如何资源调配显得格外重要，负载均衡的研究对提 高对等网络的性能也有着至关重要的意义。 结构化的对等网络中的负载均衡是当前对等网络研究领域中的一个热点。 一个负载均衡算法要达到的目标是：最小化节点的负载不均衡性。为了保证网络 的性能，每个节点的负载应该根据其自身能力维持在一个低于节点最大能力的可 接受的范围内，同时还要保证系统整体服务能力，并且还要最小化负载均衡算法 引起的额外开销。 资源查找者对各节点上存储的索引信息的需求往往是不均匀的，某些节点 可能是经常需要访问的节点，因而会造成某些节点的负载很有可能因此而过大， 成为“访问热点”( q u e r yh o t s p o t ) 。如何动念调整对等网络节点的负载大小，使 节点负载增大时可以将负载分担到负载较小的节点上，是亟待研究的问题。 1 4 本文的主要研究内容 本文在研究了国内外关于结构化对等网络负载均衡技术的基础上，对结构化 对等网络中的访问热点问题做了详细的分析和研究，发现解决访问热点问题的众 多方法中都涉及到负载转移这个步骤。本文正是在这个基础上，侧重如何解决负 载均衡中的负载分担问题。提出了一种利用多哈希函数对热点资源进行备份的负 4 本文的章节安排下： 第一章：介绍论文研究背景、国内外研究现状、论文选题及研究意义、论文 的主要研究内容和论文的组织结构。 第二章：介绍对等网络的概念、特点与发展，以及对等网络的关键技术。然 后介绍了非结构化对等网络和结构化对等网络这两种拓扑结构，以及这两者的区 别。最后研究了结构化对等网络中存在的负载均衡问题。为后面的章节提供了研 究的理论基础。 第三章：详细的介绍了当前处理负载不均衡的主要策略，为后面研究多哈希 函数对热点资源进行备份的动态负载均衡方案提供了技术支持。 第四章：本文的重点，在前面的分析研究的基础上，提出了一种利用多哈希 函数对热点资源进行备份的动态负载均衡方案来解决负载均衡问题。理论上详细 地分析了该方案的实施过程及算法设计。 第五章：对该方案进行了仿真实验的性能评估，验证该方案可以动态的调整 节点的负载的正确性和有效性，并可保证较小的访问时延。 第六章：总结本文的主要工作，并对下一步的研究方向进行了展望。 1 6 本章小结 本章简要介绍了论文的研究背景和对等网络现今的发展状况，以及论文选 题、研究意义及论文的主要研究内容结构化对等网络中的负载均衡问题。最 后总结了论文的章节安排。 5 图2 - 1c s 模式 6 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 2 2 对等网络的特点和发展 图2 - 2 p 2 p 模式 p 2 p 网络中的节点都是对等的，因此也被称为对等体或对等点。这些对等节 点具有相同的责任和能力，并且一起协同完成某一项任务。对等节点之间无需依 赖集中式服务器或者资源就可以相互连接，并且互相共享信息资源、处理器资源、 存储资源甚至是高速缓存资源等。p 2 p 的这种模式与c s 模式形成了鲜明的对比， p 2 p 网络中的节点具有很高的自治性和随意性。 具体来说主要有以下几个优点1 1 0 l ： ( 1 ) 非集中式。网络中的资源和服务分散在所有节点上，信息的传输和服 务的实现都直接在节点之间进行，避免了可能的瓶颈。 ( 2 ) 可扩展性。在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 理论上，整个体系是全分布的，不存在瓶颈。 ( 3 ) 健壮性。p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散 在各个节点之问进行的，部分节点或网络遭到破坏对其他部分的影响很小。p 2 p 网络一般在部分节点失效时能够自动调整整体拓扑，保持其他节点的连通性。 7 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 p 2 p 网络通常都是以自组织的方式建立起来的，允许节点自由地加入和离开。p 2 p 网络还能够根据网络带宽、节点数、负载等变化不断地做自适应式的调整。 ( 4 ) 高性能价格比。性能优势是p 2 p 被广泛关注的一个重要原因。采用 一p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料 分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海 量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的 计算和存储能力。 ( 5 ) 隐私保护。在p 2 p 网络中，由于信息的传输分散在各节点之间进行而 无需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。 ( 6 ) 负载均衡。p 2 p 网络环境下由于每个节点既是服务器又是客户机，减 少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多 个节点，更好地实现了整个网络的负载均衡。 简单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使 得网络上的沟通变得容易、更直接，共享和交互真正地消除了中间层。p 2 p 就是 计算机可以直接连接到其他用户的计算机、交换文件，而不是像过去那样连接到 服务器去浏览与下载p 2 p 。近来在文件共享的实现方面得到了广泛的应用，通过 这种基于p 2 p 的方式，用户可以很自由地更广泛地获得所需要的文件资源。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态，重返“非中心化”， 把权力交给用户。 根据p 2 p 系统对象分布规则和节点“邻居”关系的不同，可以将p 2 p 覆盖网 分为非结构化、结构化和松散结构化三类f 1 1 】： ( 1 ) 在非结构化p 2 p 覆盖网中，对象的存储没有规则，并且节点之问的邻 居关系足任意的。g n u t e l l a ( 老版本) 的覆盖网就足非结构化p 2 p 覆盖网。g n u t e l l a 系统的路由算法为每个节点在收到查询消息后，向其所有邻居节点转发该查询消 息。由于g n u t e l l a 节点的邻居关系是任意的，所以，g n u t e u a 覆盖网不需要拓扑 维护算法。 ( 2 ) 在结构化p 2 p 覆盖网中，对象的位置分布和覆盖网的结构都是完全确 定的。即在节点的邻居集合由路由机制规则指定的同时，p 2 p 系统中的对象也必 须按照对象分布规则存储在指定的位置。t a p e s t r y 1 2 1 ，p a s t r y 1 3 1 ，c a n l l 4 1 和c h o r d 1 5 】 8 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 等实现分布式哈希表的p 2 p 覆盖网，都是典型的结构化p 2 p 覆盖网。其路由算 法均是确定的，并且均运行覆盖网拓扑维护算法。 ( 3 ) 在松散结构化p 2 p 覆盖网中，对象的存储和覆盖网的结构都不是严格 确定的，但又依照一定的规则。一。 一一 。” 2 3 对等网络的关键技术 到目前为止，业界对于“p 2 p 技术”还未形成统一的权威定义，但近年来己有 很多研究者对p 2 p 技术的基本内涵进行了概括【1 6 1 ： ( 1 ) 一类利用位于i n t e n e t 边缘的资源( 包括存储、计算周期、内容、人) 的应用【1 7 1 。该定义是在2 0 0 0 年的o p e n p 2 p 组织年会上提出的，是p 2 p 系统最早 的定义。该定义指出了p 2 p 技术的目的是利用位于网络边缘的用户端资源。 ( 2 ) 在分布式方式下，利用分散资源开展重要任务的应用或系统f 1 s l 。该定 义是由h p 研究院提出的，说明了工业界对p 2 p 系统功能的设想。 ( 3 ) 分散的、自组织的分式布系统。系统中的主要通信是对称的【1 9 】。该定 义是由有“网格之父”之称的i a nf o s t e r 教授提出的。该定义从体系结构的角度概 括了对等网络的特征，反映了对等网络作为一种新的分布式应用的主要特点。 ( 4 ) 所有参与系统的节点( 指i n t e r n e t 上的计算机) 处于完全对等的地位， 没有客户机和服务器之分，也可以说每个节点既是客户机，也是服务器；既向别 人提供服务，也享受来自别人的服务【刎。该定义是由清华大学郑纬民教授的研 究组提出的，描述了p 2 p 系统基本构成单元，即节点的特性，也是对p 2 p 基本 组织形式的概括。 由于p 2 p 模式所具有的技术特点，很多计算机公司、研究部门都认为该技 术蕴含着巨大的商业和技术潜在价值，并从不同的角度应用和研究该技术。目前 主要的研究角度有：文件交换、对等计算、协同工作、即时通讯、搜索引擎、网 络游戏、基于i n t e r n e t 的文件存储系统、基于i n t e r n e t 的操作系统等。另外，还 有对p 2 p 开发平台的研究和p 2 p 安全框架的构建等。 先详细介绍如下： ( 1 ) 文件交换 这是p 2 p 最初的应用和基本功能之一，可以说文件交换的需求直接引发了 9 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 p 2 p 技术热潮：在传统的w e b 方式中，要实现文件交换需要服务器的大力参与， 通过将文件上传到某个特定的网站，用户再到某个网站搜索需要的文件，然后下 载，这种方式的不便之处不言而喻。在这种情况下，n a p s t e r 抓住人们希望通过 互联网共享m p 3 音乐文件的需求j 以p 2 p 模式实现了自由的文件交换体系，从 而引发了网络的p 2 p 技术革命。通过p 2 p 来搜索和下载与传统的方式最大的区 别就是你不是从其他网站的服务器搜索与下载资源，而是从任何一个在线网友的 机器罩直接下载，当然其他网站的服务器也可以看作是一个对等点，这样真正让 个人电脑实现了与服务器平起平坐。文件交换的需求也很自然地延伸到了信息的 交换。 ( 2 ) 对等计算 人们一直在尝试通过并行技术、分布式技术将多个网络节点联合起来，利用 闲散计算资源来完成大规模的计算任务。现在，p 2 p 的网络结构组织方式为这种 计算技术提供了新的契机。p 2 p 用于对等计算的优势在于每个对等点不再只是单 纯的接收计算任务，它还可以根据自己的情况( 比如分到的任务太多) 再搜索其 他空闲节点把收到的任务分发下去。然后中间结果层层上传，最后到达任务分发 节点。对等点之间还可以直接交换中间结果，协作计算。按照这种方式进行，可 以合理整合闲散的计算能力和资源，使得总体计算能力得到大规模提升，获得非 常可观的计算性能价格比。基于c s 模式的分布式计算技术是无法达到这样的 灵活性和高效性的。在所有的p 2 p 应用中，对等计算可能是短期内收益最大的， 任何需要大量数据处理的行业都可从对等计算中获利，如天气预报、动画制作、 基因组的研究等。 i n t e l 也利用对等计算技术来设计其c p u ，并为其节省极大的费用，同时由 于对等计算的发展是以p c 机资源的有效利用为根本出发点的，它也受到i n t e l 的极力推崇。就本质1 1 i 吉。，对等计算【! | j 是网络lc p u 资源的共享。 ( 3 ) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成计算任务，共享各种各样的信息资源等。协同工作使得在不同地点的参与者可 以在一起工作。在p 2 p 出现之前，协同工作的任务通常由诸如l o t u sn o t e s 或者 m se x c h a n g e 等来实现，但是无论是采用哪种服务器软件，都会产生极大的计算 1 0 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 负担，造成昂贵的成本支出，而且并不能很好地完成企业与合作伙伴、客户、供 应商之间的交流。而p 2 p 技术使得互联网上任意两台p c 都可建立直接的通讯联 系，不再需要中心服务器，降低了对服务器存储以及性能的要求，也降低了对网 络吞吐量和快速反应的要求，从而大大节约了成本，使低成本的协同工作成为可 能，最终帮助企业和关键客户，以及合作伙伴之间建立起一种安全的网上工作联 系方式。因此基于p 2 p 技术的协同工作目前受到了极大的重视。 ( 4 ) 即时通讯 所谓即时通讯，其实指的就是诸如o i c q 、i c q 等被称为在线聊天的软件。 从某种意义上说，由于版权的限制，即时通讯应用将超过文件共享应用，成为 p 2 p 的第一大应用。在即时通讯领域，a o l 和微软、y a h o o 一直有比较激烈的争 斗，当然国内还是t e n c e n t 一家的天下。与i r c ( i n t e r n e tr e l a yc h a t t i n g _ 越线 聊天系统) 、b b s 或w e b 聊天室比较，p 2 p 的即时通讯软件不仅可以随时知晓 对方在线与否，而且交流双方的通讯完全是点对点进行，不依赖服务器的性能和 网络带宽。尽管目前的即时通讯技术一般都具有中心服务器，但中心服务器仅是 用来控制着用户的认证信息等基本信息，并且帮助完成节点之间的初始互联工 作。 ( 5 ) 搜索引擎 p 2 p 网络模式中节点之间的动态而又对等的互联关系使得搜索可以在对等 点之间直接地、实时地进行，既可以保证搜索的实时性，又可以达到传统目录式 搜索引擎无可比拟的深度( 理论上将包括网络上所有开放的信息资源) 。以p 2 p 技术发展的先锋g n u t e u a 进行的搜索为例：一台p c 上的g n u t e l l a 软件可将用户 的搜索请求同时发给网络上另外1 0 台p c ，如果搜索请求未得到满足，这1 0 台 p c 中的每一台都会把该搜索请求转发给另外1 0 台p c ，这样，搜索范围将在几 秒钟内以几何级数增长，几分钟内就可搜遍几百万台p c 上的信息资源。可以说， p 2 p 为互联网的信息搜索提供了全新的解决之道。 ( 6 ) 基于i n t e m e t 的文件存储系统 存储技术一直是人们所关注的一项技术。由于网络规模的扩大，人们开始将 传统的分布式操作系统、局域存储技术向基于i n t e m e t 的文件存储系统发展。一 些研究项目开始使用p 2 p 技术来组织和存储文件，这些项目的目标都是提供面 1 1 中基于访问热点的负载均衡策略研究 p 2 p 还有很多种应用等待人 术在日益改善的网络环境下 前面已经介绍了p 2 p 覆盖网分为非结构化、结构化和松散结构化3 类。本 文将详细地研究下非结构化对等网络和结构化对等网络这两种网络结构的对等 网络。 2 4 1 非结构化对等网络 所谓非结构化对等网络【1 1 】，是指一种资源位置和网络拓扑结构松散相关的对 等网络。非结构化对等网络的主要思想是在网络中进行洪泛，也成为受限洪泛。 非结构化对等网络的资源位置不再需要按照网络结构进行精确的定位，每个节点 只需要维护局部相邻节点路由表即可。在非结构化对等网中，每个节点存储自身 的信息或信息的索引。当用户需要在p 2 p 系统中获取信息时，他们预先并不知 道这些信息( 如，某个文件) 会存储在哪个节点上。最典型的非结构化对等网络 是g n u t e l l a 。该网络的自组织性和扩展性都很好，但是唯一的缺点是【2 1 1 ：重复消 息过大，占用带宽，造成网络负载过大，并且网络的安全性较低。 综上所述，非结构化网络的优缺点可以总结如下： 1 、非结构化对等网络的缺点： ( 1 ) 没有确定拓扑结构的支持，因此无法保证资源查找搜索的效率。搜索 请求要经过整个网络或者至少足一个很人的范围j 能够得到结果，因此查询效率 低。 ( 2 ) 采用泛洪( f l o o d i n g ) 的方式进行搜索。随着网络规模的扩大，网络 流量将增加，从而导致网络拥塞，使得g n u t e l l a 网络被分片，从而查询只能够在 很小的范围内进行，因此g n u t e l l a 系统的可扩展性不好。 ( 3 ) 搜索方式带有一定的盲目性，存在查找不到网络中存在的资源的问题， 即存在搜索的不完全性。 北京邮电大学硕士学位论文 2 、非结构化对等网络的优点：由于节点之间的链路不遵循某些预定义的拓 扑结构，使得节点之间无需维护拓扑信息，网络结构简单，容错性好，支持复杂 查询。 + j +，j 一 2 4 2 结构化对等网络 相对于非结构化对等网络，结构化p 2 p 网络是一种资源位置和网络拓扑结 构紧密相关的对等网络。这类网络的主要思想是在口网络的基础上建立一个覆 盖网络。资源的定位指针位于一个指定的固定位置。资源d 与资源存储位置的 映射是通过分布式路由表来进行的。目前，结构化对等网络大部分都是通过分布 式哈希表( d m ) 来映射。哈希表作为一种数据结构，可以在资源的存储位置和 他的关键字之间建立一种确定的一对一映射关系。而所谓的分布式哈希表就是把 哈希表分散到p 2 p 网络的各个节点上。即使用一致性的哈希函数来实现映射， 将资源和节点均匀地映射到一个标识空间中。网络中的每个节点只需要维护有限 的邻居信息和路由信息来完成资源的定位。 分布式哈希表具有很多优点，尤其是在节点失效、遭受攻击和突发性高负载 面前都能表现出很好的健壮性；其次它具有很好的可扩展性，获得较大的系统规 模，而只需要较低的系统开销；最后，分布式哈希表可以进行自我配置，不需要 手工干预就可以自动地加入一个新的节点到系统中，并且为之提供简单灵活的接 口，可以被多个p 2 p 系统同时使用。 结构化p 2 p 网络通过每个节点维护较少的路由信息即可有效地实现查找， 取消了洪泛机制，大大减少了网络中的信息量。但由于覆盖网络结构维护、节点 异构性及逻辑网络与物理网络匹配等问题使得系统更为复杂，故还有很多方面需 进一步研究，使其更有利于实际应用。近年来，人们提出了基于分布式哈希表的 p 2 p 系统，例如：t a p e s t r y ，p a s t r y ，c a n 和c h o r d 。他们的基本思想都是将节点 和共享的资源之间通过相容哈希映射到一个特定的键值来索引。节点根据键值存 储部分资源的索引信息，每个节点维护一张局部路由表，通过这些路由表之间的 协作来完成资源的查找定位。下面将详细地介绍提到的这4 种网络的特点。 ( 1 ) t a p e s t r y 1 2 】 t a p e s t r y 提供了一个分布式容错查找和路由基础平台，在此平台基础之上， 1 3 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 可以开发各种p 2 p 应m ( o c e a n s t o r e t 2 2 1 即是此平台上的一个应用) 。t a p e s t r y 的思 想来源于p l a x t o n 。在p l a x t o n 中，节点使用自己所知道的邻近节点表，按照目的 i d 来逐步传递消息。t a p e s t r y 基于p l a x t o n 的思想，加入了容错机制，从而可适 应p 2 p 的动态变化的特点。o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的 p 2 p 平台。它是一个适合于全球数据存储的p 2 p 应用系统。任何用户均可以加入 o c e a n s t o r e 系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使 用复制和缓存技术，o c e a n s t o r e 可提高查找的效率。最近，t a p e s t r y 为适应p 2 p 网络的动态特性，作了很多改进，增加了额外的机制实现了网络的软状态( s o f t s t a t e ) ，并提供了自组织、鲁棒性、可扩展性和动态适应性，当网络高负载且有 失效节点时候性能有限降低，消除了对全局信息的依赖、根节点易失效和弹性差 的问题。 ( 2 ) p a s t r y 1 3 】 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于 构建大规模的p 2 p 系统。如图2 3 所示，在p a s t r y 中，每个节点分配一个1 2 8 位的节点标识符号( n o d e l d ) ，所有的节点标识符形成了一个环形的n o d e l d 空 间，范围从o 到2 1 2 8 1 ，节点加入系统时通过散列节点i p 地址在1 2 8 位n o d e i d 空间中随机分配。网络节点的加入与退出，资源查询的过程可以参考文献【矧。 ( 3 ) c a n 1 4 1 图2 - 3p a s t r y 的路由消息 1 4 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 c a n ( c o n i e n ta d d r e s s a b l en e t w o r k s ) 项目采用多维的标识符空间来实现分 布式散列算法。c a n 将所有节点映射到一个n 维的笛卡尔空间中，并为每个节 点尽可能均匀的分配一块区域。c a n 采用的散列函数通过对( k e y , v a l u e ) 对中 的k e y 进行散列运算，得到笛卡尔空间中的一个点，并将( k e y , v a l u e ) 对存储在 拥有该点所在区域的节点内。c a n 采用的路由算法相当直接和简单，知道目标 点的坐标后，就将请求传给当前节点四邻中坐标最接近目标点的节点。c a n 是 一个具有良好可扩展性的系统，给定n 个节点，系统维数为d ，则路由路径长度 为o ( n l d ) ，每节点维护的路由表信息和网络规模无关为o ( d ) 。 ( 4 ) c h o r d 【1 5 】 c h o r d 项目诞生于美国的麻省理工学院。它的目标是提供一个适合于p 2 p 环 境的分布式资源发现服务，它通过使用d h t 技术使得发现指定对象只需要维护 o ( 1 0 9 2 j v ) 长度的路由表。在d h t 技术中，网络节点按照一定的方式分配一个 唯一节点标识符( n o d ei d ) ，资源对象通过散列运算产生一个唯一的资源标识 符( o b j e c ti d ) ，且该资源将存储在节点m 与之相等或者相近的节点上。需要 查找该资源时，采用同样的方法可定位到存储该资源的节点。因此，c h o r d 的主 要贡献是提出了一个分布式查找协议，该协议可将指定的关键字( k e y ) 映射 到对应的节点( n o d e )。从算法来看，c h o r d 是相容散列算法的变体。c h o r d 的拓扑形状见图2 4 图2 4 c h o r d 的拓扑形状 结构化对等网络中基于访问热点的负载均衡策略研究 础，这些背景知识为后续章节的研究做一些铺垫。本章主要 念，特点与发展，以及对等网络关键技术的概述；接着介绍 非结构化对等网络的特点以及区别。 北京邮电大学硕士学位论文结构化对等网络中基于访问热点的负载均衡策略研究 第三章结构化对等网络的负载均衡技术 一一。3 1 负载均衡技术一_ 在计算机网络中，由于节点之间的差异很大，主要表现在存储能力、处理能 力、网络传输能力、磁盘输入输出能力等等，这些差异将导致节点处理能力的差 异。而且，由于查询请求的不均衡性，因此，网络中存在某些节点的负载过重， 而另外一些节点的负载相对较轻，出现负载不均衡，重载节点无法正常提供服务， 而轻载节点则造成处理能力的浪费，致使整