（计算机科学与技术专业论文）基于p2p的mmog中负载均衡算法的研究.pdf

t 、_ t t h er e s e a r c ho fl o a db a l a n c i n gi np 2 p b a s e dm m o g at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g b y d o n g z h i f u ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y ) t h e s i ss u p e r v i s o r ：z h a og u a n g l i j u n e2 0 1 1 ，fk0： 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文竺基主p 2 的丛丛q 鱼虫鱼夔塑堑箕洼的婴究= ：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：童苤。宣 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全 文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发 行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密口( 请在以上方框内打“刀) 撇散雷名：越f 衲、 日期7 oi1 年7 月劬日 中文摘要 摘要 基于d h t 的p 2 p 网络中，虽然已经提出了很多算法解决负载均衡问题，但这 些算法或者忽略了网络中节点的异构性、扰动性，或者在节点间转移负载的时候 没有考虑其临近关系，从而影响负载均衡代价和速度，或者采用集中式的基于协 调者的动态负载均衡算法，但此算法可能存在单点失效的问题，没有实现完全的 分布式。而大型多人在线网络游戏( m a s s i v e l ym u l t i p l a y e ro n l i n e g a m e s ，m m o g ) 系统 对上述问题要求比较高，故针对上述缺点本文要完成以下工作： 1 ) 针对目前负载均衡算法没有考虑节点临近关系，从而影响负载均衡代价和 速度，所以本文设计了一种考虑节点临近关系的负载均衡算法，该算法采用基于 虚拟服务器策略，同时改进t r a n s f e r 策略的一对一模式为多对多模式。当某个节点 重载的时候，按贪婪算法找到距离最近的合适的轻载节点分担它的负载，使得节 点间负载的转移消耗减少。 2 ) 具体实现了一种考虑了节点临近关系的负载均衡算法，通过建立全分布式 k 叉树，调用l i b 模块沿着k 叉树从叶子节点到根节点收集系统信息，调用n t s 模块找出重载节点，调用v s a 模块产生负载转移调配信息，最后调用v s t 模块依 据v s a 信息实现负载的转移。 3 ) 针对本文提出的负载均衡算法设计了一种仿真算法方案，该方案中结构化 的覆盖网络是由p e e r s i m 产生的，实现了继承于p e e r s i m 的n o d e 接口的k t n o d e 类， 通过k t n o d e 类实现了考虑了节点临近关系的负载均衡算法，同时编写仿真配置文 件、统计分析类和协议类实现仿真方案。 仿真实验中，本文改进的负载均衡算法与未考虑临近关系的p r o p o r t i o n 算法分 别在设定拓扑l 和拓扑2 下运行，并分析对比了两种算法的仿真结果。实验表明， 本文提出的算法在很大程度上减少了负载均衡代价并能够加快负载均衡速度。 关键词：p 2 p ；d h t ；m m o g ；负载均衡；k 叉树 英文摘要 a b s t r a c t m a n ya l g o r i t h m sh a v eb e e np r o p o s e dt os o l v et h el o a db a l a n c i n gp r o b l e mi np 2 p d h t - b a s e dn e t w o r k h o w e v e r , t h e s ea l g o r i t h m si g n o r et h eh e t e r o g e n e i t ya n dc h u ro f n e t w o r kn o d e s ，o ra f f e c tt h ec o s ta n ds p e e do fl o a db a l a n c i n gw h e nt h el o a di s t r a n s f e r r e db e t w e e nn o d e sw i t h o u tc o n s i d e r i n gt h 6 _ rc l o s e r e l a t i o n s h i p ，o ru s ea c e n t r a l i z e dc o o r d i n a t o r - b a s e dd y n a m i cl o a db a l a n c i n ga l g o r i t h m s ，b u tt h i sa l g o r i t h m m a yi s s u eas i n g l ep o i n to ff a i l u r e f o rt h ea b o v ei s s u e s ，t h em a s s i v e l ym u l t i p l a y e r o n l i n eg a m e ss y s t e mr e q u i r ear e l a t i v e l yh i g h ，s ow ed ot h ef o l l o w i n gw o r kt os l o v et h e a b o v es h o r t c o m i n g so ft h i sa r t i c l e 1 ) t h ec u r r e n tl o a db a l a n c i n ga l g o r i t h mn o tc o n s i d e r i n gt h er e l a t i o n s h i pb e t w e e n n e i g h b o r i n gn o d e sa f f e c tt h e l o a db a l a n c i n gc o s ta n ds p e e d s oal o a db a l a n c i n g a l g o r i t h mc o n s i d e r i n gt h er e l a t i o n s h i pb e t w e e nn e i g h b o r i n gn o d e si sp r o p o s e d t h e a l g o r i t h mb a s eo nv i r t u a ls e l v e ra n di m p r o v et h et r a n s f e rs t r a t e g yt om a n y t o - m a n y m o d e w h e nan o d ei so v e r l o a d e d ，w eu s et h eg r e e d ya l g o r i t h mt of i n dt h en e a r e s tn o d e w h i c hi sa b l et os h a r ei t sl o a di no d e rt om a k et h et r a n s f e ro fl o a db e t w e e nn o d e st o r e d u c ec o n s u m p t i o n 2 ) r a l i z i n gt h el o a db a l a n c i n ga l g o r i t h mc o n s i d e r i n gt h er e l a t i o n s h i pb e t w e e n n e i g h b o r i n gn o d e s ，w ed e s i g nag l o b a ld i s t r i b u t i o no fk - a r y t r e eb a s e do nd h t , c a l lt h e l i bm o d u l et oc o l l e c tt h es y s t e mi n f o r m a t i o na l o n gt h ek - t r e ef r o mt h el e a fn o d et ot h e r o o t , c a l ln t sm o d u l et oi d e n t i f yo v e r l o a d e dn o d e s ，c a l lv s a m o d u l et og e n e r a t et h e d e p l o yi n f o r m a t i o n ，a n dc a l lv s t m o d u l e sb a s e do nv s ai n f o r m a t i o nt ot r a n s f e rl o a d 3 ) w ed e s i g nas i m u l a t i o np r o g r a m t os i m u l a t et h ep r o p o s e dl o a db a l a n c i n g a l g o r i t h m i nt h ep r o g r a m ，t h es t r u c t u r e do v e r l a yn e t w o r ki sc r e a t e db yt h ep c e r s i m w e r a l i z et h ek t n o d ec l a s si n h e r i t e df r o mt h en o d ei n t e r f a c et os i m u l a t et h ep r o p o s e dl o a d b a l a n c i n ga l g o r i t h ma n dp r e p a r et h ec o n f i g u r a t i o nf i l e ，s t a t i s t i c a la n a l y s i sc l a s sa n d p r o t o c o lc l a s st oa s s i s t et h ee m u l a t i o np r o g r a m t h ei m p r o v e da l g o r i t h ma n dp r o p o r t i o na l g o r i t h m sn o tc o n s i d e r i n gt h er e l a t i o n s h i p b e t w e e nn e i g h b o r i n gn o d e sa r en m n i n gi nt h et o p o l o g y la n dt o p o l o g y 2r e s p e c t l y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o do fl o a db a l a n c i n gi sl a r g e l yt o r e d u c ec o s t sa n da b l et os p e e du pt h el o a db a l a n c i n gs p e e d k e yw o r d s ：p 2 p ；d h t ；m m o g ；l o a db a l a n c i n g tk - a r yt r e e 目录 目录 第1 章绪论1 1 1 课题研究背景及意义1 1 2 国内外研究现状l 1 3 本文的主要研究工作3 1 4 论文结构3 1 5 本章小结4 第2 章对等网络概述及常见负载均衡算法5 2 1 对等网络的定义5 2 2 对等网络的特点和分类5 2 2 1 对等网络的特点5 2 2 2 对等网络的分类7 2 3 对等网络的关键技术9 2 4 结构化对等网络l l 2 5 负载均衡技术简介1 4 2 5 1 负载均衡技术1 4 2 5 2 负载均衡的作用1 5 2 6 结构化对等网络中负载均衡问题1 6 2 7 结构化对等网络中常用的负载均衡技术1 6 2 7 1 基于复制技术策略1 6 2 7 2 基于流言传播策略17 2 7 3 基于虚拟节点策略1 8 2 7 4 三种策略优缺点比较1 9 2 8 基于d h t 的结构化对等网络负载均衡技术简介1 9 2 9 基于d h t 的结构化对等网络负载均衡算法2 0 2 9 1 基于p r o p o r t i o n 的算法2 0 2 9 2 基于t r a n s f e r 的算法2 1 2 1 0 基于d h t 的对等网络负载均衡算法存在的问题。2 2 2 1 l 本章小结2 2 第3 章考虑临近关系的负载均衡算法的设计与实现2 3 3 1 算法的设计目标2 3 3 2 算法的设计结构2 4 3 3 算法的设计与实现2 4 3 3 1k 叉树创建模块。2 5 目录 3 3 2 负载均衡信息收集模块2 7 3 3 3 节点类型判断模块2 9 3 3 4 节点临近关系产生模块2 9 3 3 5 虚拟服务器调配信息模块3 0 3 3 6 虚拟服务器负载转移模块3 2 3 4 各成员模块之间的关系3 3 3 5 考虑临近关系的负载均衡算法的优点3 4 3 6 本章小结3 5 第4 章负载均衡算法仿真的实现与结果分析3 7 4 1p 2 p 仿真工具3 7 4 1 1p 2 p 仿真工具分类3 7 4 1 2p e e r s i m 仿真工具概述3 7 4 2 负载均衡算法仿真的实现一3 9 4 2 1 配置文件4 l 4 2 2 节点类的实现4 2 4 2 3 统计分析类的实现4 5 4 2 4 协议类的实现4 6 4 3 模拟实验4 8 4 3 1 实验环境4 8 4 3 2p c e r s i m 仿真环境的配置4 9 4 3 3p e e r s i m 模拟仿真实验5 0 4 4 仿真结果分析5 1 4 4 1 算法改进前与改进后对比分析。5 1 4 5d 、结5 4 第5 章总结与展望5 5 参考文献。5 7 致 射6 1 基于p 2 p 的m m o g 中负载均衡算法的研究 第1 章绪论 1 1 课题研究背景及意义 如今大型多人在线网络游戏( m a s s i v e l ym u l t i p l a y e ro n l i n e g a m e s ，m m o g ) 的产品 中，一般都是采用c s 模式，整个游戏以集中的方式进行处理，这种模式在安全 和系统实现复杂度方面占有优势，但它的主要缺点是集中化的服务器会成为整个 网络的瓶颈，从而使得系统的稳定性大大减低，并且整个系统的伸缩性不高，因 而在玩家数量伸缩性和管理方面代价很高。通过使用服务器集群技术，虽然可以 获得适当的伸缩性，但是这种方案的代价是很昂贵的。然而p 2 p 技术很好的解决 了构造m m o g 系统时遇到的伸缩性问题。与传统的基于客户机服务器( c s ) 计 算模式相比，p 2 p 模式大大削弱甚至消除了中央服务器的功能。它能够最大限度地 利用散落在网络中的边缘资源，并通过灵活的协同策略将覆盖网络中各个节点有 效的组织起来。因此基于分布式散列表( d h t ) 的p 2 p 技术能够很好的解决大规模网一 络应用的伸缩性问题【l 】。 一 在分布式计算领域，结构化对等网络与d h t 技术的结合为用户提供了一种全 新的方式，覆盖网中每个计算机贡献自己所拥有的资源的同时又能获取网络中其 它对等计算机的资源。通过这种思想，构建一个在p 2 p 网络上运行游戏应用的模 型，根据玩家的兴趣域( a r e ao f i n t e r e s t ，a o i ) 将虚拟世界地图分成不同的小区域，每1 一个小区域找一个带宽和计算能力较强的节点充当该区域的协调者。 由于p 2 p 覆盖网络中不同节点的计算能力和带宽等方面的差异性很大，网络 游戏系统必须具有一定的负载均衡能力，即能够动态地将负载从超载节点迁移到 轻载节点中【2 捌。因此，在设计m m o g 系统之前，必须认真的考虑如何使用非集 中式的、可伸缩的负载均衡算法来构建系统。 1 2 国内外研究现状 目前负载均衡算法大都基于分布式网络，而这些负载均衡技术无法适应网络 游戏的需求，因此国内外的一些科研机构开展了相关技术的研究。 香港城市大学b e a t r i c e n g 等人提出了一种应用于c y b e r w a l k 虚拟系统中的负 载均衡算法【4 】。该算法依据虚拟系统中v t r t u a lo b j e c t 的分布情况来分割地图，然 第1 章绪论 后每个子地图有一个服务器负责管理。当某个服务器负载超过某一阈值的时候， 它就会寻找一个临近服务器中负载最轻的一个作为目标服务器，把自己的负载按 算法转移过去。这种算法比较适合规模小的m m o g 系统。 台湾羲守大学c h i c h a n gc h e n 和c h e n g - j o n gl e e 利用v o r o n o i 算法以游戏中 的n p c ( 非玩家控制角色) 为中心分割地图，然后分给各个服务器，每个服务器管理 地图中的几个区域【5 】。当某些服务器负载超过预先设定的阈值时，系统将把过载服 务器中一块地图区域转移到负载较轻的服务器。经过大量的实验调查发现，游戏 中大量的玩家都聚集在n p c 的周围，利用上述算法把地图分成多边形而不是三角 形、正方形、六边形等规则图形，更能避免玩家在不同区域间来回移动，减少了 服务器切换的频率，提高了系统的吞吐量。 芬兰的s a m u l ip e k k o l a 等人提出，在v i v a 中先把虚拟环境区域分成六边形， 每个区域由一个服务器负责管理，当有服务器超过预定设置的阈值时，相邻的三个 服务器彼此协调找到一个最佳点来重新分割区域【6 】。系统中没有中央控制器，服务 器的负载状态以及负载转移都由他们协商来完成。在这种算法中，一些相邻服务 器出现超载时，该系统的性能急剧下降。 香港大学的j o h nc s l u i 提出了一种应用于多服务器虚拟现实系统中的负载均 衡算法【刀。该算法依据无向图理论建立一个代表虚拟现实系统的无向图，其中每个 结点代表一个玩家，结点的权值表示所在服务器需要付出的计算代价。无向图中 的每一个边表示两端的结点需要彼此进行交流，边上的权值表示通信代价。这样 把虚拟现实系统分成几个不相交的子无向图，每个子图由一个服务器管理，使得 每个服务器的计算代价几乎均等，服务器间的通信代价也变的最小。 西班牙p m o r i l l o 等人提出了利用蚁群寻径方法( a c s ) ，对初次分配好的各个区 域的“边界玩家 重新分配【8 ，9 1 。首先建立一个“边界玩家 的侯选服务器列表， 列表中的每个服务器都赋予相同的蚂蚁信息素。每次启动a c s 方法时，都要对n 个蚂蚁的寻径结果进行评价，如果某个寻径的结果系统最终的代价最小，那么就 把“边界玩家 分给这个服务器，并增加这个服务器的信息素值。不过，该方法 更适合于大型的网络虚拟环境。 韩国i n f o r m a t i o na n dc o m m u n i c a t i o n su n i v e r s i t y 的k y u n g m i nl e e 等人提出了一 种“邻近侯选服务器”的算法 1 0 , n 】。把游戏的虚拟世界地图分成多个正方形小区域， 基于p 2 p 的m m o g 中负载均衡算法的研究 一个服务器管理预先设定数目的小正方形区域，当某个服务器的负载超过预先设 定的阈值时，它根据列表来选择负载较轻的目标服务器，然后把负载转移过去。 该算法避免了局部和全局失衡的弊端。 1 3 本文的主要研究工作 基于d h t 的p 2 p 网络中，虽然已经提出了很多算法解决负载均衡问题，但这 些算法或者忽略了网络中节点的异构性、扰动性，或者在节点间转移负载的时候 没有考虑其临近关系，从而影响负载均衡代价和速度，或者采用集中式的基于协 调者的动态负载均衡算法，但此算法可能存在单点失效的问题，没有实现完全的 分布式。而m m o g 系统对上述问题要求比较高，故针对上述缺点本文要完成以下 工作： 1 ) 设计了一个考虑临近关系的负载均衡算法，该算法采用基于虚拟服务器策 略，改进基于p r o p o r t i o n 策略仅仅解决了p 2 p 系统异构性问题，但负载转移的时候 没有考虑临近关系的缺点，同时借鉴改进t r a n s f e r 的策略的一对一模式为多对多模 式。该算法着重考虑当一个节点重载的时候，首先考虑它附近的轻载节点，如果 没有，则由近到远，按贪婪算法找到距离最近的合适的轻载节点分担它的负载， 使得负载的转移消耗减少。 2 ) 实现了考虑临近关系的负载均衡算法，该算法一共有六个模块组成，分别 为k 叉树创建模块( k t b ) 、负载均衡信息收集模块( l b i ) 、节点类型判断模块 ( n t s ) 、节点临近关系产生模块q 眦p ) 、虚拟服务器调配信息模块( v s a ) 和虚拟 服务器负载转移模块s t ) 。初始阶段，启动k t b 模块创建一个全分布式的k 叉 树，然后调用l i b 模块沿着k 叉树从叶子节点到根节点收集系统信息，接着调用 n t s 模块找出重载节点，调用v s a 模块产生负载调配信息，最后调用v s t 模块 依据v s a 信息指导重载结点和轻载结点间v s 的转移。 3 ) 设计了仿真算法的方案，该方案中结构化覆盖网络是有p e e r s i m 生产的，实 现了继承于p e e r s i m 的n o d e 的k t n o d e 类，通过k t n o d e 类实现临近关系的负载均 衡算法，同时编写仿真配置文件、统计分析类和协议类辅助仿真方案的实现。 1 4 论文结构 本论文结构的具体安排如下： 第1 章绪论 第1 章是绪论，介绍课题的研究背景和意义，通过对国内外研究现状的比较分 析，提出论文课题具体的研究内容与目标，以及论文的具体结构。 第2 章为论文的基础理论部分，介绍了对等网络的定义、特点与发展，以及基 于分布式哈希表的p 2 p 系统，接着分析了目前对等网络中的负载均衡技术( 基于 复制节点策略、基于流言传播策略、基于虚拟节点策略) ，并对它们的优缺点进 行了归纳总结，最后分析了基于d h t 对等网络常见负载均衡算法。结合m m o g 的特性，分析现存的算法的优缺点，方便以后算法设计，这些背景知识为后续章 节的研究打下铺垫。 第3 章是本文的核心部分，详细分析了基于d h t 的对等网络负载均衡算法存在 的问题，并深入分析了各个问题的原因，结合m m o g 的特性以及p r o p o r t i o n 策略仅 仅解决了p 2 p 系统异构性问题，但负载转移的时候没有考虑临近关系的缺点，设计 并实现了一个考虑临近关系的负载均衡算法，并对该算法进行了详细的描述与分 析。 第4 章是本文的重点，设计了仿真算法的方案并对仿真结果进行了分析。实现 了继承于p c c r s i m 的n o d e 的k t n o d e 类，通过k t n o d c 类实现临近关系的负载均衡算 法，同时编写仿真配置文件、统计分析类和协议类辅助仿真方案的实现。对比分 析了本文改进的考虑临近关系的负载均衡算法与未考虑临近关系的p r o p o r t i o n 算 法。 第5 章总结了本文的研究工作，并指出了需要进一步改进的地方，对下一步研 究工作的方向进行了展望。 1 5 本章小结 介绍课题的研究背景和意义，通过对国内外研究现状的比较分析，提出论文 课题具体的研究内容与目标，以及论文的具体结构。 基于p 2 p 的m m o g 中负载均衡算法的研究 第2 章对等网络概述及常见负载均衡算法 2 1 对等网络的定义 p 2 p 系统产生到现在，关于p 2 p 系统始终没有统一的定义。 英特尔公司的p 2 p i 作组( p 2 pw o r k i n gg r o u p ) 将p 2 p 系统定义为系统中每个 节点之间对等地交换服务或共享资源的系绀1 2 1 。 s c h o l l m 酬p 2 p 系统的定义【1 3 1 如下：当一个系统中的节点共享了它的硬盘资 源的时候，这些共享的资源是系统提供服务必不可少的，并且这些共享资源可以 被同一个覆盖网中节点不用通过中介服务器而直接访问，系统中的节点即是资源 的请求者也是资源的提供者，这个系统被定义为p 2 p 系统。 g r a h a m 认为p 2 p 系统中的节点具有三个必备条件【1 4 】：1 ) 具有处理可变的连接 的能力；2 ) 具有独立于d n s 的寻址能力；3 ) 具有服务器的能力。 m i l e r 认为p 2 p 系统应该具有的五个关键特性【1 5 】：1 ) 系统应该提供结点之间实 时的信息传递或数据传输；2 ) 结点充当客户端的同时又是服务器；3 ) 分布的结 点提供网络的内容；4 ) 系统中的结点应该具备自治权和网络控制权；5 ) 可能没 有永久口地址的结点和不总是连接的结点能够参与到系统中。 惠普实验室m n o j i c i c 认为p 2 p 系统定义为【1 6 】：以分布式的方式使用分布式资源 完成特定功能的系统。 上面的定义从不同的方面对p 2 p 系统进行了描述，故p 2 p 系统可以理解为是采 用了分布控制的方式，利用大量散落在覆盖网络中的节点来完成特定功能的一种 新型网络应用系统。p 2 p 系统可以利用的资源包括c p u 、存储、信息和网络带宽等， 完成的特定功能包括广域分布计算、数据共享、通信协议以及公共服务等各种应 用或服务。p 2 p 系统中的结点或资源通常具有较强的动态性，可能会随时加入或退 出系统。 2 2 对等网络的特点和分类 2 2 1 对等网络的特点 与其它传统的应用模式如c s 模式相比，p 2 p 应用模式具有以下特点【1 7 】： 1 ) 可扩展性 第2 章对等网络概述及常见负载均衡策略 由于受服务器的资源( 包括计算能力、存储能力等) 的限制，基于传统的c s 架构的系统所能容纳的用户数量以及所能提供服务的能力受到很大的约束，为了 支持互联网上大量用户并发地对系统的访问，服务器端往往需要配置大量的性能 较高的计算机，而且需要铺设高带宽的网络链路。但在基于p 2 p 架构的系统中， 当用户加入的时候，虽然服务的请求逐渐增加，但是整个系统的服务以及资源也 在同时地稳步增加，故能够长时间地满足用户的需求。对于纯全分布p 2 p 来说， 理论上其可扩展性几乎可以认为是无限的。 2 ) 健壮性 在传统c s 模式中，集中式服务器成为整个系统的薄弱之处，而采用p 2 p 架 构的系统在对待攻击和容错方面具有很好的表现。由于应用是在各个节点直接相 互作用实现的，某一小部分网络或节点的实效不会对整个网络造成很大的影响。 p 2 p 网络在部分节点失效的情况下，改变其网络拓扑结构，维持与其它的节点联系。 p 2 p 网络现实中都是以自发的方式组建的，节点的加入与离开都是不可预知的。p 2 p 网络还能够根据带宽、节点的数量以及网络的负载做出相应的调节。 3 ) 隐私性 在p 2 p 覆盖网络中，信息的传输不像c s 模式一样，需要通过一个集中的服 务器，而是在某两个节点直接进行的，故用户所要传送的信息被泄露的可能性大 大降低。在p 2 p 系统中，所有用户节点都能够充当中继转发设备，故而大大提高 了信息传递的可靠性与灵活性。 4 ) 高性能 p 2 p 网络的性能优势是其被广泛关注的原因之一。基于传统c s 方式搭建的网 络中，普通用户拥有的节点以客户端的身份接入网络，仅仅以信息和服务的消费 者身份出现，因而这些客户端的计算机能力等资源不能得到充分的利用。而采用 p 2 p 架构的覆盖网络可以充分利用散落在网络中的各个节点，将计算或存储任务按 合适的算法分发到指定的各个节点上，充分利用网络中闲置的大量资源，实现高 性能计算。 5 ) 非集中式 覆盖网络中的服务和资源按一定的策略分散于网络中的节点，信息的服务和 传输的实现都是之间在节点间进行的，这样就避免了可能存在的瓶颈，使得系统 基于p 2 p 的m m o g 中负载均衡算法的研究 的稳定性大大提升。 6 ) 负载均衡 p 2 p 覆盖网络环境下，每个节点担当的角色是服务器的同时又是客户端，使得 基于传统c s 结构服务器的存储能力、计算能力的要求大大降低，再加上资源分 布在网络中多个节点上，能更好地使网络负载均衡得以实现。 p 2 p 架构的系统带来便利的同时也存在很多的问题，诸如由于没有中心监管以 及自由平等的动态性，自组织的p 2 p 网络在技术层面面临的主要问题【1 8 j 如下： 1 ) 知识产权保护问题 p 2 p 共享软件的发展加快了盗版产业的繁荣，对知识产权保护的难度大大提 高。 2 ) 病毒的传播 p 2 p 覆盖网下，其在共享和选路机制方面占优势的同时，也为某些网络病毒的 广泛传播提供了方便。p 2 p 覆盖网络中逻辑相近的节点在物理位置上可能相距甚 远，再加上p 2 p 覆盖网络中参与的节点数量一般很大，因此p 2 p 网络传播的病毒一 般涉及范围大，同时造成的损失也是十分巨大的。 3 ) 安全问题 p 2 p 系统中文件复制传播异常迅速，一些机密文件一旦丢失，在p 2 p 系统中只 要有一份拷贝，就可能迅速扩张，造成大面积的影响，与此同时谍软件已成为p 2 p 软件的硬伤等等一系列安全问题。 4 ) 异构性问题 p 2 p 架构的系统往往有许多能力相差较大的节点构成，没有考虑其网络带宽和 能力，就给网络中每一个节点都被赋予了相同的职责，整个系统的网络性能将会 因能力较差的节点而恶化，这种情况下实现优质的资源管理是很难的。 2 2 2 对等网络的分类 目前已有的p 2 p 系统种类很多，很多研究人员从不同的角度对它进行了分类， 本文给出了一种分类结果，如图2 1 所示。 具 1 ) 根据资源放置位置与p 2 p 结点位置的关系 根据资源放置的位置与p 2 p 结点位置的关系，p 2 p 系统可以分为结构化和非结 构化两种【1 9 】： 结构化p 2 p 系统由于提供了资源标识d 到资源所在结点位置的映射关系，每个 资源能够精确放置在确定的结点上，从而确保在有限的步数内能够定位到资源。 结构化p 2 p 系统以基于分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，简称d h t ) 的p 2 p 系 统为代表如：c h o r d ，t a p e s t r y ，c a n 等。 非结构化p 2 p 系统中没有提供资源标识d 到资源所在位置的映射关系，每个资 源的放置位置即为共享此资源的结点，因而不能再确定的步数内定位到资源。非 结构化的代表有- n a p s t e r 、基于g n u t e l l a 协议的系统如f r e e n e t 、k a z a a 、m o r p h e u s 等。 结构化p 2 p 系统与非结构化p 2 p 系统的优缺点如表2 1 所示。 表2 1 结构化p 2 p 系统与非结构化p 2 p 系统的优缺点比较 t a b 2 1t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fs t r u c t u r e dp 2 ps y s t e m sa n du n s t r u c t u r e dp 2 ps y s t e m 岳 基于p 2 p 的m m o g 中负载均衡算法的研究 2 ) 根据p 2 p 系统拓扑化集中程度 根据p 2 p 系统拓扑集中化程度，p 2 p 系统可以分为集中式、全分布式和混合分 布式三种1 9 1 ，具体如下： 集中式p 2 p 系统中集中式的服务器上储存p 2 p 结点共享资源的信息，网络中的 结点通过查询集中服务器上的信息，找到存放所需资源的p 2 p 结点位置信息，再直 接至u p 2 p 结点上去获取。集中式p 2 p 系统虽然具有效率高的优点，但也继承了 c l i e n t s e r v i c e 方式所有的缺点，诸如单点失效、带宽瓶颈、容错性低、负载不平衡 及可伸缩性差等，n a s t e r 就属于这种类型。 全分布式p 2 p 系统没有集中的服务器存放结点共享资源的信息，覆盖网络中的 每个节点的地位是相当的，不需要集中服务器的协调，结点寻找资源的方式是通 过约定的资源定位请求处理方式相互协作找到的。全分布式p 2 p 系统无单点失效， 鲁棒性强，可扩展性好，但存在定位效率低的问题。基于g - n u t e l l a 协议的非结构化 p 2 p 系统和基于d h t 的结构化p 2 p 系统就属于这种类型。 。 混合分布式p 2 p 系统选择一定数量的p 2 p 结点作为局部的集中式服务器，以保 存部分p 2 p 结点的共享资源信息。这些地位更重要的p 2 p 结点称为超级结点 ( s u p e r - p e e r ) ，不同系统选择超级结点的方式不同。k a z a a 系统就属于这种类型。 2 3 对等网络的关键技术 目前p 2 p 的研究主要包括文件共享、分布式计算、协同工作、即时通讯、数 据搜索、网络游戏、基于i n t e m e t 的分布式存储系统、基于i n t e r n e t 的操作系统等。 除此之外，还有对p 2 p 安全框架的构建和p 2 p 开发平台的研究等2 0 1 ，详细介绍如 下： 1 ) 文件共享 文件共享是p 2 p 最成功应用的领域，也是直接导致p 2 p 研究热潮的根本原因。 在传统的c s 模式中，用户之间要实现共享文件，用户需要把需要共享的文件上传 到指定的服务器，假如某个用户需要这个共享文件，则这用户到这个服务器搜索， 然后下载，这种方式带来十分的不便。n a p s t e r 正是抓住人们希望通过i n t e m e t 共享 m p 3 音乐文件的需求，开发了基于p 2 p 模式的自由的文件交换体系，从而引发了网 络时代的p 2 p 技术革命。与传统的c s 模式相比，通过p 2 p 模式搜索和下载的用户不 第2 章对等网络概述及常见负载均衡策略 再用从其它网站的服务器搜索和下载，而是直接从对等的在线网友的计算机里面 下载即可，这样真正实现了p 2 p 网络中所有的节点都是对等的。 2 ) 分布式计算 分布式计算即利用p 2 p 方式，充分利用分布在互联网上的闲散资源来完成大规 模计算的一种技术。在分布式计算方面，p 2 p 技术之所以占有优势，是因为p 2 p 系 统中每个对等点不只是单一地接收计算任务，而是它还可以根据自己负载的情况 再搜索其它空闲的节点把收到的任务分发下去，然后中间计算的结果逐层地上传， 最后汇总于任务分发点，这时计算任务完成，在计算过程中，对等的节点之间还 可以交换中间结果，完成协同计算。分布式计算，合理地利用散落于网络中的闲 散资源，使得很多需要超大规模计算的研究得以实现，诸如基于分布式计算的搜 索外星文明s e t i h o m c x 【2 1 】科学实验等。 3 ) 协同工作 基于传统c s 模式的协同工作需依赖于服务器，随着现代组织规模的增大和分 支机构的分散，其代价昂贵，并且大规模的实时协作困难。通过p 2 p 技术，可在网 络上任意两台计算机之间进行实时的联系，构建一个安全、共享的虚拟空间，并 通过这一虚拟空间进行各种协作活动，高效地共同完成某项任务。 4 ) 即时通信 即使通讯系统为大量的互联网用户提供了实时交流的虚拟平台。目前的即时 通讯系统通常采用一个( 或多个) 中心服务器来维护用户的身份认证等基本的信 息，而结点之间的即时语音或数据通信一般是以p 2 p 的方式直接进行的。典型的即 时通信系统包括i c q 、o l c q 、a i m 、m s n 、s k y p e 和j a b b e r 等。 5 ) 数据搜索 采用集中式的体系结构的传统的数据引擎存在数据不能动态跟踪、难以访问 数据库和动态w e b 页的信息、单点失效、可扩展性差以及资源浪费等缺点。而基 于p 2 p 的分布式搜索引擎很好地解决了这些缺点，它通过采用分布式结构，避免了 单点失效问题，通过对动态页面的访问使搜索范围更广更深更准确。 6 ) 基于i n t e m e t 的分布式存储系统 传统分布式文件系统虽然能够支持用户在一定范围内对一定数量的分布式文 件进行透明的访问，但面对i n t e r n e t 上大量的用户对海量数据的存储和访问需求， 基于p 2 p 的m m o g 中负载均衡算法的研究 它在可扩展性、鲁棒性、易用性等诸多方面难以满足。p 2 p 分布式存储系统采用新 的p 2 p 结构，通过分布在i n t e r n e t 上大量节点的协作，使得分布式存储系统的可扩展 性和自组织性大大增强，可以适应i n t e r n e t 的动态环境，支持大量用户的海量数据 的存储需求。 2 4 结构化对等网络 前面介绍了根据资源放置位置与p 2 p 结点的关系可分为结构化p 2 p 系统、非结 构化p 2 p 系统两类。本小节将详细地介绍结构化对等网络以及常见的基于分布式哈 希表的p 2 p 系统。 与非结构化对等网络不同的是，结构化p 2 p 网络中资源的位置和网络拓扑结构 有着紧密的关联性。构建这种网络的主要思想是在口网络的基础上建立一个p 2 p 覆 盖网络，通过分布式路由表将资源i d 映射到资源存储位置。目前，结构化对等网 络大部分都是通过分布式哈希表( d h t ) 来映射。哈希表作为一种数据结构，可以在 资源的存储位置和他的关键字之间建立一种确定的一对一映射关系。而所谓