（计算机系统结构专业论文）织女星网格路由器的改进设计与实现.pdf

摘要 网格是一个异构，动态的分布式系统，它的两大特征是资源共享和协同工作，信息 服务是其核心部件之一。织女星( v e g a ) 网格提出了网格路由器的概念，它是一种完 全分布式的信息服务部件，以类似i p 路由器的方式进行工作。为了体现该信息服务部件 的特点及提供使用案例，我们设计和实现了一种基于网格的在线游戏服务平台，称为织 女星游戏网格( v e g a g a m e g r i d ) 。针对网格路由器应用中出现的问题，我们对网格路由 器进行了改进设计与实现。本文的创新点主要包含以下几个方面：1 ) 为支持多人游戏， 在游戏网格中设计和实现了全局游戏组。2 ) 基于i p u d p 协议对网格路由器进行了改进： 基于u d p 协议实现资源请求路由转发协议；通过i p 协议测量网格路由器之间的物理网 络距离：资源无需主动注册到网格路由器上。3 ) 基于图的遍历算法，提出和实现了对于 s d r t 算法的几种改进方法。 关键词：网格，信息服务，网格路由器，在线游戏 i m p r o v e dd e s i g n a n d i m p l e m e n t a t i o no f v e g a g r i dr o u t e r e n h u a t a n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yz h i w e ix u g r i di sah e t e r o g e n e o u s ，d y n a m i cd i s t r i b u t e ds y s t e m ，a n di th a st w om a i nc h a r a c t e r s ： r e s o u r c es h a r i n ga n dc o l l a b o r a t i o n t h ei n f o r m a t i o ns e r v i c ei so n eo ft h ec o r ec o m p o n e n t si n t h eg r i d v e g ag r i dg a v et h ec o n c e p to fg r i dr o u t e r ：af u l l yd i s t r i b u t e di n f o r m a t i o ns e r v i c e c o m p o n e n tw h i c hw o r k ss i m i l a rt o i pr o u t e r i no r d e rt od e m o n s t r a t et h eb e n e f i to ft h i s c o m p o n e n ta n dp r o v i d eu s ec a s e ，w ed e s i g n e da n di m p l e m e n t e dag r i d - b a s e do n l i n eg a m e s e r v i c ep l a t f o r m ，c a l l e dv c g ag a m e g r i d c o n s i d e r i n g t h e p r o b l e m so c c u r r e d i nt h e a p p l i c a t i o n o fg r i dr o u t e r , w ei m p r o v e dt h ed e s i g na n di m p l e m e n t a t i o no fg r i dr o u t e r t h i sd i s s e r t a t i o n i n c l u d e st h ef o l l o w i n go r i g i n a l w o r k s ：1 ) t os u p p o r tm u l t i - p l a y e rg a m e ，w ed e s i g n e da n d i m p l e m e n t e dg a m eg r o u p sf o ra l lg a m ep l a y e r so n t h eg a m eg r i d 2 ) i m p r o v e dt h eg r i dr o u t e r b a s e do ni pa n du d p p r o t o c o l s ：i m p l e m e n t e d r e s o u r c e r e q u e s ta n d t r a n s f e rw i t hu d p p r o t o c o l ； e n a b l e dm e a s u r i n gt h ep h y s i c a ln e t w o r kd i s t a n c eb e t w e e ng r i dr o u t e r sw i t hi pp r o t o c o l ； r e s o u r c e sn e e dn o tt om a n u a l l y r e g i s t e ro ng r i dr o u t e r 3 ) p r o p o s e da n di m p l e m e n t e ds e v e r a l m e t h o d st oi m p r o v et h es d r ta l g o r i t h mw i t ht h e g r a p h t r a v e r s ea l g o r i t h m k e y w o r d s ：g r i d ，i n f o r m a t i o ns e r v i c e ，g r i dr o u t e r , o r d i n cg a m e i i 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：万盗 易茅 1 日期：加。乒7 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：砭眵蓐导师签名：7 ：c 2 埘7 7 1 1 网格研究现状 第一章引言 网格( g r i d ) 这个概念最早可以追溯到1 9 6 5 年m i t ，b e l l 实验室和g e 联合开发的 一种分时操作系统m u l t i c s ( m u l t i p l e x e d i n f o r m a t i o na n d c o m p u t i n gs e r v i c e ) 2 6 】，它的设 计目标是“制造一种几乎能满足现在和不远的将来对于大型计算能力的要求的计算机系 统”，“这样的系统必须能够像电话和电力系统一样持续可靠的一周7 天，一天2 4 小时的 运行，而且必须能够满足广泛的服务需求：”【1 0 】。很可惜，这个系统出于商业原因 失败了，但由于它提出了很多先进的概念，例如虚拟内存，在线重配置( o n - l i n e r e c o n f i g u r a t i o n ) 等，其后有很多系统由此而引申出来，比如u n i x ，i b m 3 6 0 等。 最近1 0 年伴随着g l o b u s 3 5 ，l e g i o n 2 2 等项目的研究，网格的概念逐渐变得具体 起来。中国科学院计算技术研究所提出的织女星( v e g a ) 【4 3 】网格也是一个很有特色的 网格系统。 1 1 1g l o b u st o o l k i t , o g s a 和w s r f g 1 0 b u s 项目的主要成果体现为g l o b u st o o l k i t 。在其1 x ，2 x 版本中，g l o b u s 提出了 种沙漏型的网格体系结构【1 5 】，指出网格的意义在于实现了虚拟组织的概念：即“基 于高度可控的的共享规则，由一些个人或者团体形成的集合体”，并认为为了网格的长远 发展，需要定义和广泛部署i n t e r g r i d 协议，如同i p 协议把计算机网络互联起来一样， i n t e w g r i d 协议能使不同的组织互相操作和交互或者共享资源。 随着w e bs e r v i c e 3 3 ，5 1 的发展，g l o b u s 在其3 o 版本中提出了o g s a ( o p e ng r i d s e r v i c e s a r c h i t e c t u r e ) 【1 4 的概念，希望把g r i d 与w e bs e r v i c e 技术相结合，使g r i d 更加 适合于商业运算。其3 0 版本完全用j a v a 实现，并遵循被称为o g s i 2 8 的规范。o g s a 定义了一种统一开放的服务语义：网格服务；定义了创建，命名和发现瞬时网格服务实 例的标准机制；提供了服务实例的位置透明性和多种协议的绑定；并支持对于底层的本 地平台设施的集成。o g s a 还按照w s d l 5 的接口和相关约定定义t g j 建和组织复杂的 分布式系统所需要的机制，包括生命周期的管理，变更管理和通知机制。o g s a 的服务 绑定支持可靠的调用，认证，授权和代理。 g l o b u s 在今年年初又提出了w s r f ( w s r e s o u r c e f r a m e w o r k ) 【3 6 】的概念，对o g s i 做了修改，并把它分离为6 个w e bs e r v i c e 的标准：w s r e s o u r c e p r o p e r t i e s ， w s - r e s o u r c e l i f e t i m e ，w s r e n e w a b l e r e f e r e n c e s ，w s s e r v i c e g r o u p ，w s b a s e f a u l t w s - n o t i f i c a t i o n 。这样做的主要目的是希望w e bs e r v i c e 业界能够更好的接收网格概念， 从而达到两者最终的融合。 织女星州格路由器的改进设计0 实现 1 1 2 织女星网格 织女星网格的研究重点在于网格体系结构和网格操作系统。织女星网格体系结构设 计继承了已有计算机系统的设计方法，即将网格看成是一台虚拟的、具有单一系统映像 的计算机系统。与现有的计算机系统类似，织女星网格也将包括硬件、系统软件和应用 三个组成部分。 在织女星网格的研究中，提出了基于“网格计算协议”( g r i dc o m p u t i n gp r o t o c o l ， g c p ) 的网格互联系统。该协议由基于t c p i p 协议的资源路由协议和应用层次的网格 计算表示协议所组成。 + 资源路由器( 后文中也被称为网格路由器) 是织女星网格体系结构中的重要组成部 分，资源路由器与网格计算协议的关系如下图所示。在i n t e m e t 中，i p 路由器实现了数 据报文的路由和转发，并最终将数据可传递到目的地。而在织女星网格中，资源路由器 将完成计算请求的路由和转发，并将计算请求传递给能够满足此请求的计算资源。资源 路由器主要完成以下功能： 资源注册注销。资源路由器是网格计算资源的接入设备，计算资源在资源路由 器上注册之后，相当于在网格中分配了一个“地址”，可以被全网格共享。 资源路由信息收集便新。资源路由信息是有关资源所在位置的信息，作为对资 源请求进行路由和转发的依据。由于资源的动态变化，资源路由器之间、资源 路由器和资源之间需要定时进行路由信息的更新。 资源请求的路由转发。当资源路由器收到一个资源请求后，它需要根据资源路 由信息为这个请求选择一条路径并将其转发给对应的资源路由器。 1 2 在线游戏研究现状 图1 1 织女星网格g c p 协议层次结构 随着互联网的网络带宽的持续增长，在线游戏日益成为网络上的热门应用。我们可 以简单的把热门在线游戏分为三类：小型的休闲类游戏，例如棋牌类、益智类游戏；动 作类游戏，例如反恐精英：大型多人在线游戏，包括e v e r q u e s t ，网络创世纪( u l t i m a 2 第一章弓l 吉 o n l i n e ) 等。在【1 9 】中对于多人在线游戏的研究做了很好的综述。 1 2 1 联众游戏 联众游戏( w w w o u r g a m e c o m ) 是一个棋牌类游戏网站。截至2 0 0 4 年3 月，联众共 捌有近一亿三千万注册用户，一周上下线人数1 0 0 0 多万，每月活跃人群达1 5 0 0 万，最 高同时在线人数已超过5 8 万，声称是目前世界最大的游戏娱乐网站。 联众游戏主要的游戏框架采用c l i e n t - s e r v e r 结构：用户通过连接到同一个游戏服务 器进行游戏通信。采用这种游戏结构，联众可以有效的防止用户的作弊，并方便的进行 用户的管理。但是这种方式往往会使服务器成为网络瓶颈和单一故障点，而且游戏消息 的延迟也会e l 较大。 1 2 2 p 2 p 游戏 纯p 2 p ( p e e r - t o - p e e r ) 的游戏一般采用单播或者多播的方式更新游戏消息。使用单 播方式意味着n 个结点之间需要o ( n 2 ) i 拘更新消息，系统很难扩展到支持大量的用户。 m i m a z e 3 是一个完全分布式的基于i p 多播的多人游戏，它使用m b o n e 1 3 作为其实验 网络。由于i n t e m e t 对于多播的支持还不完善，所以该工作目前还只具有实验意义。 3 9 】 中提出了一种用于网络虚拟环境的p 2 p 的通信结构，结点之间可以基于虚拟环境中的几 何距离远近建立连接，距离最近的邻居结点之间交换消息，消息延迟相对c l i e n t ，s e r v e r 方式比较低。 1 2 3 多服务器结构 f 9 】中提出了一种镜像服务器( m i r r o r e d $ e l - v c r ) 的游戏结构。它是一种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 相比，它又 能允许集中的用户管理。每一种游戏部署有多个分布的镜像服务器，客户端以传统的 c l i e n t - s e r v e r 方式连接到距离最近的服务器。这些服务器之间通过一个游戏专用的、低 延迟的多播网络互联，形成了一个p 2 p 结构，每个服务器维护一份游戏的状态。但是这 一游戏结构需要在各个镜像服务器之间同步游戏的状态，限制了某些同步算法的使用， 不利于在镜像服务器之间用兴趣管理技术 1 9 1 优化通信。 【6 】提出了一个被称为b o o s t e rb o x 的计算装置，它被部署到边缘路由器上，能够知道 附近网络的状态。b o o s t e rb o x 通过如下方式减轻了服务器的负载：能缓存一些非实时的 信息，替服务器做应答：能汇集多个客户端发送的相关消息包，组合起来发送给服务器； 可以过滤一些多余的消息；还可以进行应用层路由，即只把消息发送给负责处理它的服 务器。 【8 】在g l o b u st o o l k i t2 2 的基础上开发了游戏运行平台所需要的中间件：包括针对游 戏用户。提供商和系统的服务。系统服务主要包括：服务器资源管理，发现游戏用户和 游戏提供商的目录服务以及可用性监控。服务器资源的分配会随着游戏用户数量和分布 织女星网格路由器的改进设计j 实现 情况而变化。 1 3 姿源发现研究现状 信息系统，尤其是分布式信息系统，需要解决的一个核心问题是资源发现：帮助用 户或者程序找到他们需要的各种资源。p 2 p ( p e e r - t o - p e e r ) ，网格都是典型的分布式信息 系统，它们资源发现机制各具特点，可以相互借鉴。 1 3 1p 2 p 系统的资源发现机制 p 2 p 系统按照其组织方式可以划分为无结构和有结构( s t r u c t u r e d ) 的p 2 p 系统。前 者主要以g n u t c l l a 1 2 为代表，后者包括c a n 3 i ，c h o r d 1 6 等系统。 g n u t e l l a 使用一种泛洪( f l o o d i n g ) 的方式进行资源发现，每个s e r v e n t ( 即每个p e e r ) 在不能满足查询请求时会转发查询包给所有的邻居s e r v e n t ( 除了发送者) 。g n u t e l l a 通过 查询包中的r r l 字段控制查找的范围，通过一个全局唯一的d 标识查询请求，防止环 路导致的请求被重复转发。g n u t e l l a 的这种查询方式原理非常简单，但是扩展性较差， 当用户数量变多的时候，g n u t e l l a 的通信会占据大量网络带宽。 c a n 等有结构的p 2 p 系统的核心思想是把资源的关键字( 伴随对应的资源信息) 按 照某种映射算法分布到网络中的不同结点，这种分布是有规律的，可以是按照d 维的笛 卡尔空间分割关键字空间，也可以是按照类似相容h a s h 7 的办法。在有结构的p 2 p 系 统中，资源请求的路由是确定的，系统的可扩展性很好。但是它们也有缺点：经过这种 映射之后，p 2 p 网络结点之间相邻关系与实际网络并没有联系，这样会导致查询的性能 得不到优化。 1 3 2g l o b u s 中的m d s 及其改进版本 m d s 2 1 是g l o b u s 中的信息服务部件。它采用了l d a p 3 4 的树状资源组织结构， 支持按照资源的属性进行资源的查询。 为了适应网格中资源动态变化的特征，有效的组织m d s 的目录服务器，在 1 l q 6 使 用了一种类似p 2 p 的方式进行资源的查找，希望能够对于m d s 进行有益的补充。主要 的改进方法包括对于请求进行随机，基于经验，基于最佳邻居等算法的转发。 1 3 3 其他改进方法 【2 5 】提出了一种对于无结构的p 2 p 网络基于数字签名的改进查询算法。它通过把查 找内容的数字签名作为索引，在有邻居关系的结点之间进行交换，从而改善查找的方向 准确性。它提出了三种构造邻居结点查找内容的签名的方法：完全重叠的，部分重叠的， 部分附加的。它限定了签名传播的半径，当一个查询在这个半径范围内得不到满足时， 它将把这个查询以随机或者泛洪的方式扩展到传播的半径之外，继续进行查询。 4 第一章0 l 苦 2 4 则提出了一种对于资源状态信息的传播算法。它提出了g r i dp o t e n t i a l 的概念： 计算能力和网络带宽高的主机，g r i dp o t e n t i a l 相应的就高。同时每个结点还将通过收到 的资源状态信息计算网络中所有结点的平均g r i dp o t e n t i a l 。g r i dp o t e n t i a l 高于平均g r i d p o t e n t i a l 的结点将把资源的状态信息传播到所有的邻居结点，或者以一定的概率进行传 播；低的则不传播。这种传播方式减少了重复的信息传播，提高了性能。 1 4 论文的组织 本文的组织如下：第一章主要阐述了网格研究现状，在线游戏研究现状，资源发现 研究现状。 第二章介绍了网格路由器在织女星游戏网格中的应用。 第三章对网格路由器改进后的的协议和路由转发算法做了详细的描述。 第四章主要是网格路由器改进后的实现和实际评测。 最后，对整个论文进行了总结，并给出了将来的研究方向。 2 1 概述 第二章织女星游戏网格介绍 在介绍织女星游戏网格之前，我们先来看看目前的在线游戏存在的问题。 2 1 1 目前在线游戏存在的问题 首先考虑性能方面：c l i e n t s e r v e r 结构，服务器是网络瓶颈，也是计算瓶颈。p 2 p 结构虽然通信延迟较小，但是如果使用单播，扩展性不够好，无法支持大规模的结点间 通信，使用多播则很理想，不过目前i n t e m e t 对于多播尚不广泛支持。对于多服务器结 构来说，服务器间应当尽量避免不必要的通信，而且应当负载均衡。 其次考虑功能方面：c l i e n t - s e r v e r 结构比较适合用户的发现，p 2 p 结构往往需要一个 b o o t s l t a 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 结构都有用户作弊的问题，前 者一般需要比较好的延迟补偿算法【19 】，后者则需要对游戏的状态进行同步 2 7 】。 2 1 2 织女星游戏网格的特点 织女星游戏网格试图通过引入网格路由器解决目前在线游戏存在的一些问题。 织女星游戏网格的系统结构是一种多服务器结构和p 2 p 结构的混合体。对于小型游 戏，服务器用于在线用户的发现和管理，客户端通过服务器找到合适的游戏组之后，建 立p 2 p 通信。对于大型游戏，服务器还可用于中转游戏消息以及计算游戏的状态，客户 端之间不直接进行通信。 性能上：对于小型游戏来说，由于客户端采用p 2 p 方式通信，服务器的负载比较轻， 避免服务器的瓶颈效应。此外，由于服务器之间可以有效的通过网格路由器进行资源发 现，因此，可以很好的进行负载平衡，而且可以很方便的实现全局范围用户查询，无需 像镜像服务器一样同步所有的服务器存放的游戏信息，整个系统的可扩展性较好。 功能上：由于采用了多服务器结构，方便了游戏用户之间的发现和用户管理。对于 作弊问题来说，如果游戏的瓶颈是网络带宽而不是计算，可以方便的使用服务器作为p 2 p 游戏过程的仲裁者【2 0 】，避免了纯p 2 p 结构游戏状态复杂的同步【2 7 】。 2 1 3 总体结构 织女星游戏网格( v e g a g a m e g r i d ) 主要由游戏服务平台( g a m e s e r v i c e p i a t f o 珊， g s p ) ，网格路由器( g r i dr o u t e r ) ，全局用户数据库( g l o b a lu s e rd a t a b a s e ) 和客户端四 大部分所组成。其中每个g s p 依赖于一个本地在线用户数据库，客户端也可以被分为游 6 第二二章织女星游戏嘲格介绍 一一 戏大厅和各个游戏模块。总体结构如下图所示： 图2 1 织女星游戏网格系统结构图 可以用一句话概括织女星游戏网格的系统结构：游戏服务器( 即g s p ) 通过网格路 由器提供游戏用户和游戏组的发现服务，游戏客户端一般采用p 2 p 通信的方式交互游戏 消息。由于n a t 的存在，同时处于不同n a t 之后的游戏客户端之间无法直接进行p 2 p 通信( 使用u d p 协议时，某些情况下可以，参见【2 】) ，这时需要游戏服务器中转游戏消 息。 2 2 网格路由器的原理和功能 下面我们对于网格路由器的原理和功能做一个简单的介绍【4 2 】。 2 _ 2 1 资源信息路由转发模型 资源信息路由转发模型是织女星网格资源发现机制的核心内容。为区别不同种类的 资源和其状态，在模型中，每个资源都被赋予一个全局唯一的类型码r e s o u r c ei d ( 这个 i d 在资源的全生命周期中是不变的) 和一个属性值l e s o u r c ev a l u e ( 一个实际的资源可能 有多个属性，这里用一个属性简化表述) 。一个资源的描述包括该资源r e s a u r c ei d 和 7 织女星删格路由器的改进设计与实现 r c s o u r c ev a l u e 。这个组合并不能在网格中唯一的确定一个资源，有可能存在多个类型和 属性完全相同的资源，在这种情况下，哪些资源是对用户可见的，是由路由器根据一定 的策略来决定的。 2 2 2 模型框架 织女星网格的资源发现机制中有三个基本角色：资源请求者( 网格用户) 、资源路由 器和资源提供者( 有时，为了简便，资源提供者和资源本身不加区别) 。它们三者之间有 以下关系：每个资源提供者必须连接到一个资源路由器上：每个资源路由器与一个或多 个路由器或资源相连，直接相连的路由器互为邻居；每一个网格用户可以连接到一个或 多个路由器上。它们的工作过程如下： 用户将自己的资源请求发给直接与自己相连的资源路由器。该请求包含了所需资源 的类型和属性值。路由器维护着记录邻居们( 包括路由器和资源) 的资源状态的路由表。 它总在等待用户请求的到来。当收到一个来自用户的请求时，路由器检查本地的路由表， 找出一个邻居( 或者多个，取决于路由策略) ，并将该请求转发给它( 们) 。一个请求在 到达一个可以满足它的资源或生存期( t t l ) 到期前，可能被多次转发。如果路由器发 现一个请求的t r l 已经过期，就将该请求丢弃，不再做进一步处理。 资源路由器必须尽量保持其路由表中资源信息的正确性和实时性。一个路由器将定 期地收到它的邻居路由器向其发送的更新报文，并以此为根据更新本地路由表中的相关 内容。相应地，该路由器也应该周期性的将本地的资源信息报告给它的邻居路由器。如 果个路由器在某一段时间内没有收到来自某一邻居的更新，则认为该邻居发生了故障， 路由器不再将请求报文和更新发送给该邻居，并根据特定策略更新拓扑。 资源提供者必须首先注册到一个路由器，并周期性地向其发送自己最近的状态。当 一个资源提供者收到一个资源请求时，如果本地资源可以满足请求，则向请求者发送相 应消息，否则将该请求丢弃。 哑。 懋忿 一 f |i 、t 。万? 匝态苗、心瓷型 j 万锄 万) 。一j r e q u e s t o r ( 、p r o v i d e r r o u t e r 图2 2 路由表转发模型的结构和资源发现的过程 上图给出了路由模型和资源发现的过程。资源提供者，提供了一个资源，而请求 肼是来自请求者砺的，的请求。开始时m ，被发送至路由器勘，而根据路由表勘 知道如果将该请求转发至r j ，那么请求将最终到达资源r ，于是r o 将请求转发至 月，。类似地，路由器r j 和r 2 也将为怫选择一条可以到达p ，的路径。 8 第二章织女星游戏网格介绍 2 2 3 协议 在织女星网格的原型中，路由器网络是一个静念配置的非结构化的平铺结构，也可 以根据需要配置成诸如树状的层次结构。管理员在路由器的配黄文件中指定了该路出器 可以直接建立连接的路由器，即该路由器的邻居路由器。为适应网格中结点、资源自主 控制和动态变化的特点，资源路由器在运行时，需要有动态改变拓扑的能力，如隔离故 障结点等。为此，资源路由器上运行了一个包含注册、定时更新、超时探测、注销及相 应的应答报文的协议。该协议用于解决路由器网络的生成、扩展和运行时维护的问题， 并且保证资源信息在路由器网络中近似实时的传播( 信息的实时性由路由更新的周期和 更新路径的拓扑结构决定) ，从而较好地适应了网格资源动态变化的特点。 2 2 4 路由表 在路由表中，每一个资源类型都有且只有一个入口指明在这个子网格中是否存在该 类资源。在模型中，选择记录特定资源类型的“方向”和“距离”，而非这一资源的物理 位置( 例如p 地址) 。这就是说，资源路由器知道有一个特定长度的路径，通过它，可 以到达要求的资源类型。在模型中，路径的长度被抽象成请求通过本路径时经过的路由 器结点数( 跳数) 。如果我们将每个资源的位置信息记录下来，空间开销十分巨大，因为 尽管资源类型是有限的，但资源数量却是无限的。 模型采用一种类似r i p 算法的距离向量算法进行路由表的更新，并采用了水平分裂 算法的简单形式( 即不向邻居路由器更新从它获得的路由信息) 来防止无穷计算问题 【1 l 】。 路由转发模型中的另一个问题是如何决定收到的资源请求的转发方向，这被称为路 由策略问题。这个问题将直接影响到资源发现的效率。模型中，资源路由器能使用几种 不同的路由转发策略来处理资源请求，如随机路由转发( r - r t ) ，最短距离路由转发 ( s d r t ) 【3 7 ，和多点路由转发( m - r t ) 。当资源路由器接收到一个资源请求，s d - r t 算法将选择出一个路由器转发请求，通过它，请求将经过最少的跳数到达能满足请求的 资源。m r t 算法则将向每一个可以满足这一请求的相关路由器转发请求。 2 3 网格路由器在游戏网格中的应用 最初对织女星游戏网格进行设计时，并没有g s p 的概念。原始设想是让每个客户端 作为一个资源提供者直接注册到网格路由器，通过网格路由器进行全网格范围用户发现。 但这样做复杂了网格路由器的功能：它必须提供各种形式的查询功能。而实际上网格路 由器比较适合对于资源按类型查询，不适合按照属性查询。而且直接使用网格路由器无 法满足对于用户管理的需要。 因此我们提出了g s p 的概念，希望能够提供更加详细的查询功能，而且能对用户进 9 织女星网格路由器的改进设计j ，实现 行有效管理。g s p 还提供了另外一个非常重要的功能：对于游戏组的支持，这对于游戏 的运行来说是必不可少的。 g s p 主要的功能如下所述： 对于客户端：用户注册，登录，选择游戏，刷新用户列表。刷新游戏组列表， 查询游戏用户( 组) ，创建，力日入游戏组，获得游戏组成员地址，开始游戏，离 r 丌游戏组，退出。 g s p 之间：进行游戏用户( 组) 的查询，实现游戏组的同步协议。 作为资源提供者注册到网格路由器，定期更新，向网格路由器发出查询请求。 客户端在登录之后会与g s p 保持t c p 连接，g s p 对于每一个t c p 连接新建一个线 程进行消息处理。这样做简化了对于游戏用户的认证过程，也很容易判断用户是否在线。 2 3 1 游戏服务平台启动和运行流程 图2 3g s p 启动与运行流程 图2 3 示意了g s p 的启动与运行流程。其中的运行流程并不完全，主要展示了对于 查询请求的处理。 0 第1 二章织女星游戏阿格介绍 2 3 2 全局用户数据厍 为了能够提供有效的用户管理，我们使用了一个全局用户数据库进行注册用户信息 的管理。该数据库为所有的g s p 所使用，在用户注册、登录和退出时g s p 会访i 司该数 据库。全局用户数据库包含用户的注册信息：用户名、密码、昵称、性别等：用户在各 种游戏中的信息，包括等级、积分和信用；此外还有一个字段表示用户是否已经登录， 防止用户在多个g s p 上同时登录，造成游戏世界中用户名不唯一。 2 3 3 本地在线用户数据库 为了能向游戏用户提供各种形式的查询功能，每个g s p 都使用了个本地的数据 库，记录登录到该g s p 用户的信息。本地的数据库主要包括用户登录时从全局用户数据 库获得的用户的注册信息，游戏信息，此外还有动态的在线信息。在线信息主要由用户 的状态、所在游戏i d ，所在游戏组信息及用户的源地址端口信息所组成。用户的源地 址，端口信息用于客户端之间的p 2 p 通信。由于该数据库一般不会很大，所以采用了内存 表的形式加快访问速度。 2 3 4 全局范围用户查询 对于网格路由器来说，g s p 既是一个资源提供者。也是一个资源请求者。每个g s p 都注册到网格路由器上，定时更新本地的用户信息，提供给其他的g s p 查询自己本地登 录用户的服务；同时它们也会在满足不了用户发出的查询请求时向网格路由器发出资源 请求，要求得到符合查询要求的g s p 的地址，并向该g s p 发出详细的查询请求，得到 查询结果。可以看出，由于使用了网格路由器，g s p 可以很方便的实现全局范围内的用 户查询。 在设计g s p 向网格路由器的资源更新方式时，我们想到了两种方法，各有优缺点： 1 ) 把游戏用户的m 作为r e s o u r c ei d 。 _ 优点：可以直接按用户的i d 进行全局范围用户查找。 _ 缺点：路由表会很大，路由更新频繁；无法按用户的属性进行查找。 2 ) 把游戏用户的属性值的所有组合( 例如， 性别、等级、积分等级、速度等级、 信用、游戏i d 的笛卡儿积) 作为r e s o u r c ei d 。 _ 优点：可以实现按属性的用户查找，而且路由表的表项可以合并( 前一种 方式无法合并) ，路由表的大小固定，路由更新只需定期完成，不必很频繁 ( 因为更新的只是关于属性的信息，略微的出入关系不是很大) 。 _ 缺点：无法实现按用户的i d 进行查找，只能用遍历一遍g s p 的方法；或 者搜索到指定深度就不找了( 这时不保证能够找到) ：当然如果在全局用户 数据库上面作些标记，也可以实现这种查找，但这时会给全局用户数据库 带来负载。 织女星嘲格路由器的改进设计0 实现 目前的实现采用第二种方式的简化版本，称之为粗粒度的更新：即只把游戏i d 作 为r e s o u r c ei d 进行更新，只有某游戏有人玩，而且有人状态为空闲的时候，才响资源 路由器更新该游戏i d 资源。这样做实际上让网格路由器只进行粗粒度的查找：即返回 一个可能符合资源要求的g s p 地址；然后再让资源请求者连接该g s p 进行更详细的查 找。这种方法也有优缺点： 优点：对于路由器来说，按照r e s o u r c ei d 进行查找是最适合的，资源的具体属 性可以在资源提供者处进行查询。这样，路由器无需存储大量资源的属性信息， 较少了空间存储，加快了查询速度。 缺点：资源请求者可能需要经过多次查询才能找到合适的g s p 。 2 3 5 全局游戏组 为了支持多人游戏，应当提供一个游戏组，支持游戏用户的加入和离开。对于 c l i e n t - s e r v e r 结构来说，这一点比较容易实现；对于多服务器结构来说一般有两种实现 方法：1 ) 把一个游戏组放在个游戏服务器上进行维护；2 ) 一个游戏组在多个服务器 都有副本，需要对于各个副本之间进行同步工作。第一种方法无疑是最简单的，而且也 是目前大多数采用多服务器结构的游戏的做法，但是这种方法往往需要游戏组所有成员 都与该服务器进行通信，而且会造成该服务器成为单一故障点。为了支持“游戏客户端 只需与离它最近的g s p 进行通信，减少通信延迟，改善用户体验”的想法，我们决定采 用第二种方法实现游戏组。 对于镜像服务器来说( 见1 2 3 多服务器结构) ，每个游戏组在所有的镜像服务器都 存在副本，因此，游戏组的命名、创建、加入、离开问题都很好解决。我们的想法是尽 量减少游戏组的副本个数，最好只在游戏组成员所在的g s p 上存在该副本，其他的g s p 对于该游戏组的存在并不知情。这样可以减少同步通信的代价，也是一种天然的兴趣管 孕t j l , 翻j 1 9 。 这样做首先需要解决的就是游戏组的命名及加入问题：游戏组由于可能会随着组成 员个数的增长而扩展到全部的g s p 上，所以游戏组被创建时必须有一个全局范围的命 名：有了这个名字之后，用户应当如何加入该游戏组呢? 我们采用的游戏组命名方法是 游戏i d ，加上游戏组被创建时所在的g s p 的地址，再加上该g s p 生成的本地唯一的游 戏组i d 号。这种命名方法可以保证游戏组名称的全局唯一性。如果用户发现了该游戏 组( 例如使用全局用户查询功能或者刷新本地游戏组列表) ，那么他可以通过与游戏组 被创建时所在的g s p 进行通信( 一般由用户所在的g s p 代为通信) 来加入该游戏组( 当 然还需要告诉其他组成员所在的g s p ，同步组成员信息) 。用户离开游戏组的过程也与 此类似。游戏组被创建时所在的g s p 需要一直维护游戏组成员的信息，不管其本地用户 在不在该游戏组内。 具体的加入和退出游戏组的算法如下： 算法2 1 游戏组加入算法 第二章织女星游戏网格介绍 参数说明：u s ri d ：欲加入游戏纽的本地在线用户i d ； ( g a m ei d g r _ i d ，g r _ a t ) 构成了游戏纽全局唯一的i d 其中g a m e i d 为游戏i d t g ra t 为游戏纽创建时所在的g s p 的地址，g r i d 为g - a t 生成的本地唯一的组i d a g r j o i n ( u s r i d ，g a m e i d ，g r i d ，g r a t ) i f ( g ra t 为本地g s p ) ( ( 临界区：防j i ：同时加入好几个组成员) ： 检查纽成员个数足否超出最大值； 更新u s ri d 的游戏组信息，表示其已经加入该组了。 le l s ei f ( g ra t 不是本地g s p ) 连接g ra t ，请求把u s ri d 的信息加入到其本地数据库； 更新u s ri d 的游戏组信息。表示其已经加入该组了： i f ( 本地数据库除u s ri d 无其他组员记录) ( 连接g ra t ，请求获取所有组员( 除了u s ri d ) 的信息； 插入结果到本地数据库。 ， ) 对于不在本地和g r a t 的组成员，连接它们所在的g s p ，请求把u s r i d 的信息加入到其本地数 据库： l 算法2 2 游戏组离开算法 g r l e a v e ( u s r i d , g a m e i d , g r _ i d ，g r _ a t ) i f ( g ra t 不是本地g s p ) 连接g r a t 请求把u s r j d 的信息从其本地数据库中删除； 更新u s ri d 的游戏蛆信息，表示其已经离开该组了： 对于不在本地和g ra t 的组成员。连接它们所在的g s p ，请求把u s ri d 的信息从其本地数据库 中删除： i f ( g ra t 不是本地g s p ) 如果本地无其他组成员，从本地数据库中删除组成员信息副本。 1 通过上述的游戏组命名方式以及算法，我们可以很方便的加入一个组，而且能够确 保组成员的个数不超过某个上限值，这对一些需要限定游戏人数的游戏( 比如棋牌类游 戏) 来说很有必要。但是这种方法也存在问题：游戏组被创建时所在的g s p 成为了加入 该游戏组的集中控制点，如果这个g s p 失效了，那么游戏组就无法加入新成员了( 离开 游戏组还是可以的，因为离开时本地已经有了该游戏组其他成员所在的g s p 的信息，即 使游戏组被创建时所在的g s p 失效了，还是可以与其他相关的g s p 进行通信，同步游 戏组信息的) 。如果不使用这种方法，且想控制游戏组成员的个数，则需要一种具有强一 织女星叫格路由 l 的改进设计1 j 实现 致性的分布式游戏组加入算法，一般会带来新的开销。 2 3 ，6 可扩展性与负载平衡 由于游戏网格使用了网格路由器，整个系统具有较好的可扩展性：无论是某个g s p 失效了还是新部署了一个g s p ，对于其他的g s p 的正常运行都没有影响。 当在游戏网格中部署了多个g s p 之后，有可能出现负载不均的情况。我们可以使用 网格路由器来实现全网格范围内g s p 负载的平衡。具体来说，g s p 作为资源提供者可以 向网格路由器定时更新其负载情况。当某个用户登录到一台负载很重的g s p 时，该g s p 会向阿恪路由器发出资源请求，获取附近负载比较轻的g s p 的地址，然后把用户重定向 到该负载比较轻的g s p 进行登录。 3 1 概述 第三章网格路由器的改进设计：协议与算法 3 1 1 网格路由器前期设计与实现存在的问题 通过网格路由器的实际应用，我们发现，网格路由器的前期设计与实现中存在如下 一些问题，希望能对其进行改进： 性能方面： 1 ) 网格路由器使用的各种协议的早期实现是基于t c p 协议或者s o a p 3 3 】协议 ( 把网格路由器作为一个网格服务实现) 。对于需要频繁路由转发和路由更新的 网格路由器来说，这种实现性能并不高。因此，我们想基于口层协议( 包括m ， u d p ，i c m p 3 0 等协议) 来实现网格路由器的协议，提高处理速度，改善性能。 2 ) 在t c p 层实现网格路由器的时候，我们对于网格路由器之间的物理网络距离并 不关心，简单的定为1 。这样做导致网格路由器设计目标“能找到最近的资源” 并不太符合实际情况：网格路由器之间形成的o v e r l a y 网络上的最近往往并不 是物理网络上的最近。而且由于o v e r l a y 网络的拓扑与底层物理网络可能并不 重合，网络通信的开销也没有得到优化。在p e e x - t o - p e e r 网络中也存在这个问题， 被称之为m i s m a t c h 问题【2 3 】。 4 1 ，4 0 通过动态调整o v e r l a y 的拓扑结构来解决 这个问题。基于网格路由器与口路由器的相似性，我们想把网格路由器做到底 层去，最好是部署到真正的m 路由器上，这样就天然的不会有m i s m a t c h 问题， “建立和维护路由表时。以及请求转发时，消息在路由器层上的逻辑传递路径 与底层口报文的物理传递路径是一致的”【4 2 】。 3 ) 网格路由器存储资源属性开销较大。这个我们希望用分层处理的办法加以解决： 网格路由器不存储资源属性，而是由资源提供者维护，网格路由器只负责找到 同一类型的资源，具体的属性匹配可以基于这个功能实现：例如只让属性匹配 的资源提供者返回应答给资源请求者，或者让资源提供者返回资源的详细信