（通信与信息系统专业论文）forces集群路由器资源管理的研究与实现.pdf

f o r g e s 集群路由器资源管理系统的研究和实现 摘要 控制件与转发件分离( f o r c e s ) 的集群路由器架构，能很好地 - 满足下一代网络对路由器所提出的开放性、可扩展性、可编程性以及 高可用性的需求。为了使用户高效的、透明的使用f o r c e s 集群路由 器，本文设计了f o r c e s 集群路由器资源管理系统，并对实现所需的 相关技术进行了深入的研究。 本文首先介绍了f o r c e s 集群路由器的整体架构和集群资源管理 系统的基本概念，在此基础上我们提出了f o r c e s 集群路由器资源管 理系统的体系结构。然后我们对f o r c e s 集群路由器资源管理系统中 需要用到的作业调度算法进行了深入的探讨和研究，针对现有作业调 度算法存在的不足，提出了一种适用于f o r c e s 集群路由器的 ( i m l 腰) 算法，即资源预约策略配合回填策略的最大作业优先调 度算法，并从理论上分析了该算法的优势。接着我们对f o r c e s 集群 路由器资源管理系统中最重要的资源分配问题进行了深入的探讨和 研究，提出了融合面向作业分配处理机和面向处理机选择作业两大经 典模型的双向任务匹配资源分配模型。 最后，我们对自己设计的f o r c e s 集群路由器资源管理系统的相 关性能和功能进行了对比测试，验证了相关实现的合理性和正确性。 j 关键词：f o r c e s ，资源管理，作业调度，资源分配 r e s e a r c ha n di m p l e m e n t a t i o no fr e s o u r c e n 【a n a g e m 匝n ts y s t e mi nf o r c e sc l u s t e rr o u t e r a bs t r a c t t h ec l u s t e rr o u t e rb a s e do nf o r c e s ( f o r w a r d i n ga n dc o n t r o le l e m e n t s e p a r a t i o n ) ，p r o p o s e db y f o r c e sw o r k i n gg r o u pc a ns a t i s f yt h e p r o p o s e d n e x t - g e n e r a t i o no p e n ，f l e x i b l ea n dp r o g r a m m a b l ed e m a n d s t om a k et h eu s e r su s e f o r c e sc l u s t e rr o u t e rm o r ee f f i c i e n t l ya n dt r a n s p a r e n t l y , t h i s p a p e rr e s e a r c ho n b u i l d i n ga r e s o u r c em a n a g e m e n ts y s t e mi nf o r c e sc l u s t e rr o u t e r 一- ， f i r s t l y , w ei n t r o d u c et h eo v e r a l lf r a m e w o r ko ff o r c e sc l u s t e rr o u t e ra n db a s i c c o n c e p to fc l u s t e rr e s o u r c em a n a g e m e n ts y s t e m ，o n t h i sb a s i s ，w ep r o p o s e d a r c h i t e c t u r eo fr e s o u r c em a n a g e m e n ts y s t e mi nf o r c e sc l u s t e rr o u t e r s e c o n d l yw e m a k ear e s e a r c ho nt h es c h e d u l i n ga l g o r i t h mo fr e s o u r c em a n a g e m e n ts y s t e ma n d a n a l y z et h ed i s a d v a n t a g eo fc u r r e n tj o bs c h e d u l i n ga l g o r i t h m ，i no r d e rt or e s o l v e t h o s ep r o b l e m s ，w ep r o p o s e dr e s e r v a t i o nb a c k f i l l i n g l a r g ej o bp r i o r i t y ( r b l j p ) a l g o r i t h m t h e n as e to fr e s o u r c ea l l o c a t i o n s t r a t e g y h a sb e e ns t u d i e da n d i m p l e m e n t e ds u c c e s s f u l l y , w h i c h i sb a s e do nt w oc l a s s i c a lr e s o u r c ea l l o c a t i o n m o d u l e s ”j o b o r i e n t e dr e s o u r c ea l l o c a t i o n ”a n d ”r e s o u r c e o r i e n t e dj o bs e l e c t i o n ” i nt h ee n d ，w et e s t e dt h ef u n c t i o no fr e s o u r c em a n a g e m e n ts y s t e mi nf o r c e s c l u s t e rr o u t e ，a n dp r o v e dt h ec o r r e c t n e s sa n df e a s i b i l i t yo ft h ep r o p o s e dd e s i g n so f j o b s c h e d u l i n ga l g o r i t h ma n dr e s o u r c ea l l o c a t i o ns t r a t e g y k e y w o r d s ：f o r c e s ；r e s o u r c em a n a g e m e n t ；j o bs c h e d u l i n g ；r e s o u r c e a l l o c a t i o n 1 1 课题背景及意义 1 绪论 随着互联网的快速发展，网络需求量不断增大，网络应用也越来越多样化， 现有的互联网架构已远远不能满足未来发展的需求，这就促使了国内外各研究机 构开始研究下一代互联网架构。目前关于下一代互联网将如何发展还尚无定论， 但朝向以“更快、更及时、更方便、更安全和更可控制管理”的新一代互联网发 展已经得n y 大家的共识【l 】。路由器作为互联网中最重要的网络设备，是影响互 联网速度、性能、规模等指标的重要因素，因此新的互联网架构研究过程中离不 开对路由器体系结构的研究，在下一代互联网架构中，路由器除了完成网络通信 中路由选择、转发任务外，还需要完成一些控制、管理以及业务处理功能。现有 路由器体系结构【2 】由于受其自身结构、操作系统及协议方面的固有限制，存可扩 展性上严重欠缺，而集群路由器是分布式的，解决了目前传统路由器所面临的一 些问题，具有非常广阔的发展空间，也成为了现在国内外机构的研究重点。 f o r c e s 是互联网工程任务组i e t f 路由领域中的一个工作组，f o r c e s 工作组 希望将网络设备物理分离，使其内部的控制平面和转发平面之间的信息交换标准 化【3 】。这种在物理上将网络设备分离，在各个分离部件间使用统一的标准和规范 来开发产品的做法，充分发挥了开放网络架构的优势，使得各个组件能够独立发 展，如果能将f o r c e s 技术应用到集群路由器中，这势必将提高集群路由器的可 管理性、可扩展性和灵活性，从而进一步获得更好的故障冗余和管理控制能 力m 】。 目前，国内外关于如何将f o r c e s 技术应用在集群路由器上已经取得了很好 的进展。但是本课题组的前期工作并没有解决用户如何使用f o r c e s 集群路由器 的问题。对f o r c e s 集群路由器用户来说，他没有必要去了解f o r c e s 集群路由 器内部的结构，也不必知道使用的f o r c e s 集群路由器的位置。这就需要一个集 群资源管理系统可以根据用户的需求，统一管理和调度f o r c e s 集群资源，当然 也包括用户提交的业务，然后通过合理分配资源给各个业务来保证用户能够公平 合理地使用f o r c e s 集群路由器资源。 1 2 国内外研究现状 目前国内外对集群资源管理系统和f o r c e s 集群路由器都作了许多的研究。 本小节详细讲述了集群资源管理系统研究现状和f o r c e s 集群路由器研究现状。 1 2 i 集群资源管理系统研究现状 通常，集群系统的组成很复杂，为了能够让用户方便、透明的使用整个集群 系统，也为了方便整个集群系统的管理和调度，就需要一个集群资源管理系统可 以根据用户的需求，统一管理整个系统内的所有资源，当然也包括用户提交的作 业，然后通过合理分配资源给各个作业来保证各个用户能够公平合理地共享集群 系统资源，使整个集群系统达到最优的性能。所以集群资源管理系统的研究已经 成为国内外高性能计算领域的一个热点问题，目前已经出现了几十种类似的集群 资源管理系统，它们在目标、结构、功能和实现上各有所长，适用于不同的集群 系统，也反映了一个好的集群资源管理系统所应具备的特性。国外对这方面的研 究开始的较早，目前已经出现了p b s 、c o n d o r 、l s f 、l o a d l e v e l e r 等当 今颇具代表性的集群资源管理系统。而当前国内集群系统常用于科学计算，往往 结合己有的高性能计算平台的体系结构和相关应用领域对通用作业系统管理软 件进行功能的扩充和加强，开发适合特定需要的资源管理软件。下面我们将介绍 下国内外几种代表性的集群资源管理系统： p b s ( p o r t a b l eb a t c hs y s t e m ) 6 】：p b s 开源项目是i 妇n a s a 的a m e s 研究中心开 发，p b s 具有强大的作业调度功能，这样可以更好满足的异构计算，特别是高性 能计算的需要。在p b s 系统中用户可以非常方便的配置和修改调度策略，从而来 满足特定集群系统的需要。另外如果当前调度策略无法满足集群系统，用户也可 以很方便地添加新的调度策略。此外，由于p b s 是开源项目，所以它支持代码开 放、支持多重任务、支持系统可配置等等。 c o n d o r 刀：威斯康星大学研究团队开发的c o n d o r 是一个可以充分利用 工作站休闲时间的集群作业管理系统。c o n d o r 管理的集群系统由网络中的工 作站组成，它时刻监测网络中所有工作站的状态，一旦有某台计算机处于空闲状 态，便把它纳入到资源池中，在资源池中的所有工作站都可被用来执行作业。如 2 果当前工作站被所有者使用，c o n d o r 便会将运行在该工作站上的作业迁移到 资源池中的其它结点上继续运行，这样不会影响到工作站主人使用该工作站。 l s f ( l o a ds h a r i n gf a c i l i t y ) 【8 】：负载共享软件l s f 是由加拿大p l a t f o r m c o m p u t i n g 公司开发的，它的前身是由t o r o n t o 大学开发的u t o p i a 系统，在此基础 上，它加强了科学计算和企业事务处理方面的功能。相比一般研究产品而言， l s f 具有更强大的功能和更稳定的性能。无论是在负载平衡、系统容错方面，还 是在检查点操作、进程迁移方面，都要做的更好。它为紧急作业提供了抢占式调 度和关键资源保障；同时还提供了强大的任务调度策略，其中包括r e s e r v a t i o n 和 b a c k f i l l i n g 等。 l o a d l e v e r l e 9 】：l o a d l e v e l e r l 9 】是美国i b m 公司开发的商用集群作业管理 系统，目前它已成功运行在i b m 公司的s p 2 集群系统上，允许用户在同构或异构 的集群系统中提交交互对比处理作业。由于它具有灵活高效的特点，因此被广泛 的应用于教育机构、研究所和企业等各个行业。和c o n d o r 类似，l o a d l e v e l e r 也有资源池概念，用户可以向资源池中所有机器提交作业。l o a d l e v e l e r 主要特点 是支持多种作业的运行、支持用户自定义作业类、集群系统集中式控制与n q s 兼容等等。 j o s s 集群管理系统【l o 】：j o s s 作为我国自主开发的一个集群管理系统，尽管 存在一些不足之处，例如系统未提供检查点操作和进程迁移功能，不能支持作业 依赖，不能挂起运行中作业，当运行中作业异常时，不能重新调度，安全性不高； 但是它基本上实现了一个集群资源管理系统所应具备的功能，而且应用于曙光超 级服务器系统后，充分发挥了曙光超级服务器的优势，能很好完成集群资源管理 的工作，提高了曙光服务器系统的使用效率。 多集群作业调度系统m c s s j 1 1 】：m c s s j 是在p b s 基础上实现了的多集群作业 调度系统，它实现了多集群的作业提交接口和基于选择最轻的负载调度转发模 块。作业转发机制有很多，比如将作业负载进行分类来转发等，其效果还有待于 实验。在多集群的调度中，还可以采取更优的策略来收集负载信息，减少信息量 和通信次数，以缩短决策过程，多集群系统在未来实际使用中可能会拓展到广域 网环境，该系统中的作业调度均未考虑网络延迟问题，通常广域网存在严重的数 据传输能力不足的问题。多集群系统中可能存在由于网络故障原因造成远程集群 负载信息失效而引起作业分配失效问题，因此可能需要对分配失败的作业进行改 派的研究，提高算法的可靠性。 基于网格的自强3 0 0 0 集群管理系统【1 2 】：该系统是上海大学以o p e n p b s 为基 础开发的一套网格环境下的集群管理系统，不仅为集群内用户提供计算资源，而 且为网格中的其他用户提供资源，实现完全的资源共享。该系统的主要特点具有： 集群节点的快速部署、集群系统性能监测、可远程进行集群系统管理和作业管理。 而且为了使得方便集群系统的管理，他们还提出了一套能够高效和安全地对于集 群进行管理和监控的集群系统管理的协议。 1 2 2f o r c e s 集群路由器研究现状 在介绍f o 疋e s 集群路由器的研究现状前，我们首先概述一下开放可重构技 术及协议标准的研究。通信网络领域开放可重构技术及协议标准的研究可以追溯 到1 9 9 6 年左右的开放信令( o p e n s i g ) 技术研究，“0 p e n s i g ”学术组织为了实现， 网络设备的模块化和快速更新，提供了交换机和路由器之间的开放接口，但是 o p e n s i g 并没有制定标准化的协议。随后各个研究机构都试图制定出相应的体系 结构和结构标准，到目前为止，主要的研究成果有： 1 9 9 8 年i e e e 主导制定的p 1 5 2 0 参考模型将结构细分为四层：v a l u ea d d e d s e r v i c el a y e r 、n e t w o r kg e n e r i cs e r v i c e sl a y e r 、v i r t u a ln e t w o r kd e v i c el a y e r 和 p h y s i c a le l e m e n t sl a y e r ，v a l u ea d d e ds e r v i c el a y e r 、n e t w o r kg e n e r i cs e r v i c e s l a y e r 隶属于控制面，v i r t u a ln e t w o r kd e v i c el a y e r 、p h y s i c a le l e m e n t sl a y e r 隶属 于数据面。但是进一步的研究表明网络设备中的许多功能并不能单在某个层面的 一个接口上实现，而利用p 1 5 2 0 模型就必须将功能串行分配到各个层上，这使问 题变得更加复杂，有时甚至难以实现，因此这种将控制面和数据面串行细分的方 法既不实用，也不简便，也就是说p 1 5 2 0 的研究被证明是不成功的。 i e t f 组织的g s m p 工作组提出了在交换机上实现主从结构的思想，主就表 示控制件，从就表示交换件。控制件和交换件之间的通信通过g s m p 协议来实 现，目前该工作组已经提交了r f c l 9 8 7 、r f c 2 2 9 7 、r f c 3 2 9 2 三个标准类r f c 。 g s m p 协议相比s n m p 协议来说，提高了对转发件的资源管理功能，但是g s m p 协议并未对交换件内资源作分类管理，导致g s m p 架构应用范围不大。 4 n p f 组织的工作是由i n t e l 公司推动的。由于i n t e l 公司对网络领域的战略调 整，目前n p f 研究进展相当缓慢，但是它在网络设备软件和硬件模块之间的接 口标准化方面还是取得了一定的研究成果。比如在控制面，n p f 定义了针对各类 网络应用服务的a p i 接口集：在转发面，则定义了类饼通用交换接口协定c s i x ” 这样可用于网络处理单元的接口标准。 开放架构及接口研究中，i e 邗f o r c e s t 作组已经针对现有网络设备提出了 一种控制件和转发件相分离的f o r c e s 架构( r f c 3 6 5 4 、i 汪c 3 7 4 6 ) 。在f o r c e s 架 构中，控制件由管理模块、构件代理等组成，转发件由各类标准化的逻辑功能块 ( l f b ) 组成，并可由控制件按用户需要构造动态l f b 拓扑结构【1 3 】，控制件和转 发件的信息交换按照f o 吒e s 协议【1 4 】实现，f o r c e s 协议对转发件的管理是基于 l f b 模块来实现的。在这样的架构中转发件具有很好的灵活性，特别是在l f b 间 的拓扑构造和l f b 的属性控制方面。由此可以看出g s m p 架构相比f o r c e s 架构， g s m p 的交换件只有一个l f b ，即交换l f b ，所以g s m p 架构中交换件的资源可 重构性很差，用户只能设置其资源属性，而无法改动资源的连接拓扑结构等。 在完成对f o r c e s 架构的研究后，目前f o r c e s 工作组主要专注于f o r c e s 协议、f em o d e l 、l f b 定义库、f o r c e st m l 、f o r c e sm i b 等文件的制定。具 体研究成果如下： 1 ) f o r c e s 协议方面，i e t ff o r c e s 工作组已经于2 0 0 4 年成立了f o r c e s 协议设计小组，由i b m 、n o k i a 、i n t e l 、e t r i 、z y n x 和浙江工商大学的 7 名成员构成。这些研究机构分别提交的“g r m p 协议”、“f a c t 协议 和“n e t l i n k 2 协议”成为了候选。f o 疋e s 协议设计小组通过对候选协议 的讨论分析，于2 0 0 4 年9 月提交了“f o r c e s 协议 草案，经过4 年多 的工作，在2 0 0 9 年3 月，i e t f 已经将第2 2 版的f o 疋e s 控制协议批准 成为了标准类r f c ，这是大陆学者作为主要成员参与完成的i e t f 标准 类r f c ，被看做是中国在互联网标准制定上的重大突破。 2 ) f o r c e sf e 模型研究方面，i n t e l 公司在2 0 0 3 年首先提出了第0 版的草案， 到了2 0 0 9 年，经多次修改后的草案已经被批准成为i e t f 标准类r f c l l 3 】。 3 ) l f b 定义方面，j o e l 等人撰写的r f c 5 8 1 2 1 3 】定义了一部分用于实现基本 功能的l f b ；浙江工商大学与国家数字程控交换工程技术研究中心 ( n d s c ) 联合在提交的f o 疋e sl f bl i b 草案中【1 5 】定义了更多实现基本 功能的l f b 。而由美国i b m 公司提交的r f c 5 8 1 3 中主要介绍了f o r c e s m i b t l 6 1 。 4 ) f o r c e st m l 研究方面，浙江工商大学与z y n x 公司联合提交的f o 疋e s t m l 草案【1 刀定义了传输层原语，此外浙江工商大学还单独提交了基于 t c p u d p 协议的t 池方案【1 8 】。而基于t c p 协议和s c t p 协议的n 他方 案【1 9 】则分别有i n t e l 公司和z y l l x 公司提交。 5 ) 在其它方面，i n t e l 公司提交的草案中介绍了f o r c e s 协议和模型相关的应 用例子【2 0 】，朗讯公司提交的草案中阐述了如何发现和管理f e 之间的拓扑 结构【2 。 目前相关的f o r c e s 标准还在进一步的制定中，国内外已有多家研究机构就 f o r c e s 技术开始进行网络件实现的研究。n p f 将基于f o r c e s 协议来实现他们的 新型网络架构。朗讯公司在2 0 0 5 年i t u tn g nf o c u sg r o u p 上提出了 s o f t r o u t e r t 2 2 】的概念，基本思路是将i e t ff o r c e s 体系架构应用至u i t u 。i n t e l 公司 推出的i x a ( i n t e m e te x c h a n g ea r c h i t e c t u r e ，互联网交换架构) 开发计划，也融 入了f o 妃e s 协议和n p f 协议【2 3 l 。 集群路由器是指将多个相互独立运行的路由交换结点，由高速互连网络将它 们连接起来的单映像路由系统。由于集群路由器相比传统路由器在数据包转发能 力、计算能力以及网络设备使用周期等方面均具有更好的性能，因此集群路由器 具有广阔的发展空间，将会成为构建下一代互联网的基础。目前，国内外研究机 构对于集群路由器的研究涉及到多个层面，也取得了一定的成果。近几年来，由 于f o r c e s 架构的灵活性和可扩展性，已有研究人员提出采用f o r c e s 架构来设 计集群路由器。 在国外，wl o u a t i 、ih o u i d i 以及mk h a n a t 等人对如何在f o r c e s 架构基础上 进行集群路由器的动态服务部署( d h c r ) 已经有了一定的研究成果，与传统的 集群路由器架构相比，他们定义了用于各个节点间信息交换的框架和协议。在分 布式f e 拓扑方面，他们采用了分布式组件( c o i m a 模型) 来连接各个f e ，已达 到分布式异构的目的。d h c r l 2 4 上的研究示例可以被认为是f o r c e s 架构应用于 集群路由器上的实例，在集群路由器上应用f o r c e s 架构，由于f o r c e s 架构的灵 6 活性和可扩展性，相比传统集群路由器具有更好的性能。 在国内，为了解决f o r c e s 集群路由器内部分组在集群系统内的路由问题， 清华大学的徐明伟等人在前入已有f o r c e s 路由器拓扑发现研究成果的基础上， 提出了基于标签交换的内部路由机制1 2 5 1 。其它研究方面，国防科学技术大学的 研究人员在基于f o r c e s 架构的基础上，提出了一种开放可扩展的通用路由器体 系结构o p e n r o u t e r 模型。与f o r c e s 架构类似，o p e n r o u t e r 模型将集群路由器划 分为控制实体( c e ) 和转发实体( f e ) ，在多个c e 之间以及多个f e 之间，他们 定义了三个对等层协同机制，基于这三个协议，o p e n r o u t e r , 模型能支持控制协议 在多c e 间的并行处理、多f e 间的协同和冗余备份，以及实现由多个f e 构成的集 群转发功能，此外该模型还支持多维可扩展性。另外，国防科学技术大学的研究 人员还针对小规模的转发集群和大规模的转发集群这两种情况，分别提出了集中 式路径构造算法c p c a 和分布式路径构造算法d p c a ，在解决转发集群内部拓扑 发现与路径构造问题上有一定的成效。在这些研究成果的基础上，他们设计了一 种新型的软件集群路由器s c r ，在s c r 中分布式控制与集群转发有机结合，在系 统功能和性能的可扩展性较传统集群路由器有了提高【2 6 】。 1 3 本文的研究内容和主要贡献 1 3 1 研究内容 为了解决用户如何高效的、透明的使用f c r c e s 集群路由器，本文主要进行 了以下几方面的研究工作： 研究了f q r c e s 集群路由器资源管理系统体系结构 集群资源管理系统可以根据用户的需求，统一管理整个系统内的所有资源， 当然也包括用户提交的作业，然后通过合理分配资源给各个作业来保证各个用户 能够公平合理地共享集群系统资源。本文通过分析几种典型资源管理系统的优缺 点后，结合开源资源管理器t 0 r q u e 【2 刀和作业调度器m a u i 【2 8 1 提出了适用于f o r c e s 集群路由器资源管理系统的体系结构。 研究了f o r c e s 集群路由器资源管理系统作业调度算法 作业调度系统是f o r c e s 集群路由器资源管理系统的核心组成部分，良好的 7 7， 作业调度系统可使集群中所有f e 的处理能力全部汇集起来高效地分配给所有 用，从而影响整个f o r c e s 集群路由器的运行效率，在f o r c e s 集群路由器中作 业调度的关键是选择目前最适应整个集群工作状态并能够产生最高性能和吞吐 率的业务。本文在分析了常用作业调度算法的优缺点后，提出了一种基于预约回 填策略的最大作业优先调度( r b l j p ) 算法。 研究了f o r c e s 集群路由器资源管理系统资源分配策略 资源分配模块的主要职责就是对资源进行管理和分配，它处在整个f o r c e s 集群路由器资源管理系统的中间部位，其上层是作业调度模块，下层是资源监视 模块。良好的资源分配策略可以根据各个业务不同的需求，统一管理和调度 f o r c e s 集群路由器资源，使用户公平合理的使用f e 资源，提高整个f o r c e s 集 群系统的利用率和吞吐率。本文在融合现有资源分配模型的基础上，提出了适用 于f o r c e s 集群路由器的双向任务匹配模型，并对其中的实现细节做了详细的描 述。 1 3 2 主要贡献 本文主要贡献如下： ( 1 ) 在课题组前期研究f o r c e s 集群路由器的基础上，提出了f o r c e s 集群路 由器资源管理系统的体系结构，解决了用户如何高效的、透明的使用 f o r c e s 集群路由器。 ( 2 ) 结合当前主要的作业调度算法，提出了预约回填策略相结合最大作业优 先调度算法，为以后研究作业调度算法提供了新的思路和方向。 ( 3 ) 提供了适用于f o r c e s 集群路由器的资源分配策略，该策略在f o r c e s 架 构的基础上融合了面向作业分配处理机和面向处理机选择作业这两大经 典模型，在一定程度上进行了创新。 1 4 论文组织结构 本文共分为六章，内容安排如下： 第一章首先介绍了本文的研究背景及意义，接着分析了集群资源管理系统研 究现状和f o r c e s 路由器研究现状。然后提出了本文的主要研究内容、贡献和组 8 织结构。 第二章首先介绍了本课题组设计的f o r c e s 集群路由器体系结构，然后对集 群资源管理系统的概念进行了叙述，并介绍了几种典型的资源管理系统，在此基 础上提出了适用于f o r c e s 集群路由器资源管理系统的结构。 第三章对作业调度系统中典型的几种调度算法进行了探讨，在分析了这些算 法的特点和不足后，提出了适用于f o r c e s 集群路由器的预约回填策略相结合最 大作业优先调度算法。 第四章首先对f o r c e s 集群路由器中的f e 资源信息进行离散化处理，然后 融合现有的资源分配模型，提出了适用于f o r c e s 集群路由器的资源分配策略， 并阐述了实现的相关细节。 第五章首先介绍了将本文设计的作业调度算法和资源分配策略在f o r c e s 集 群路由器上进行功能及性能测试的内容，然后又对测试结果进行了分析。 第六章在总结当前研究工作的基础上，对下一步的研究工作做了一些展望。 9 2 f o r c e s 集群路由器资源管理系统 集群资源管理系统可以根据用户的需求，统一管理整个系统内的所有资源， 当然也包括用户提交的作业，然后通过合理分配资源给各个作业来保证各个用户 能够公平合理地共享集群系统资源。 本章首先介绍了f o r c e s 集群路由器的体系结构，然后对集群资源管理系统 的概念进行了叙述，并介绍了几种典型的资源管理系统，在此基础上提出了适用 于f o r c e s 集群路由器资源管理系统的结构。 2 1f o r c e s 集群路由器 本课题组设计的f o r c e s 集群路由器遵循控制平面与数据平面分离的思想， 其模型如图2 1 所示，它可以分成控制件( c e ) 和转发件( f e ) ，它们都是由多 台p c 机集群而成。 控制流 c e 构应用构件 件 控 藏据瘴 _-代 软件构件运行环境 制 理 f o r c e s 协议中问件 皿 o l x i n gs y s t e ms 目扣 面 伞 昌 r 棚撇、 帅酣瞒 夕 转 萨l 铲l尊掣l 发 f e l f l 2 f e n f o r c e s 协议中间件f o r c e s 协议中问件f o r c e s 协议中间件 平实时 l f b 操0l f b 库 实时 l i b 操0l f b 库 实时 l f b 操0l f b 库 面 操作 作接口l ( 构件抽象) 操作 作接口0 ( 构件抽象) 操作 作接口l l ( 构件抽象) 系统系统系统 构件资源构件资源构件资源 降- - - f i - - ll 辈l降- - f i - - l n e 图2 - 1f o r c e s 集群路由器软件体系结构 在f o r c e s 集群路由器中，控制件包括以下几个模块【2 9 】： 管理模块：负责管理c e 和外部网管系统的交互。 构件代理：进行重构的执行体，负责接收用户重构指令。 1 0 应用构件：实现各种应用的构件集合，如i p v 4 转发等。 软件构件运行环境：负责构件问的通信，并传递构件与底层协议栈相互间的 报文。 f o r c e s 协议中间件：为c e 提供f o r c e s 协议支持。 转发件包括以下几个模块： f o r c e s 协议中间件：完成f o r c e s 协议消息的发送与接收等操作。 l f b 库( 构件抽象) ：l f b ( l o g i c a lf u n c t i o nb l o c k ，逻辑功能块) 是构件在 f o r c e s 集群路由器转发件中的抽象名称，主要负责管理所有构件资源。在f e 中，根据数据包处理过程中的不同操作，可将l f b 分为三类： ( 1 ) 完成基本数据包转发的l f b e t h e r p o r t ( i n g r e s s ) l f b - 负责接收以太网数据包。 e t h e r p o r t ( e g r e s s ) l f b ：负责发送以太网数据包。 e t h e r d e c a pl f b ：首先对以太网包头解封装，然后根据数据包的类型将 数据包分别发送到下一个l f b 进行分类处理，另外还需要对刚从外部进 入f o r c e s 集群路由器的i p 数据包进行m a c 地址过滤处理以及校验二 层头的有效性。 e t h e r e n c a pl f b ：负责重新封装数据包以太网头，不同数据包的封装标记 是不同的。 c l a s s i f i e r l f b ：判断i p 数据包类型，将不同的数据包类型分发到对应的 接口。 q u e u es c h e d u l e rl f b - 主要功能是调度已执行完的作业队列。 ( 2 ) 实现业务转发和扩展的l f b s e r v i c e p r o cl f b ：完成业务处理所需的l f b 集，s e r v i c e p r o cl f b 的主要功 能是对业务数据包进行业务处理，然后根据模型从l f b 库中调入相应l f b 即可。最后将处理完的业务数据包传送给s e r v i c e f w dl f b 。综上所述， 可以用图2 2 来表示该l f b 。 a t t r i b u t e s 非业务输出- s e r v i c e f w dl f b ：主要功能是通过查找业务路由表来转发那些经 s e r v i c e p r o el f b 处理后还需要进一步处理的数据包。如图2 3 所示： s e r v i e e f w dl f b a t t r i b u t e s 成功输吐 至多 ( 至 流量控制l f b ：主要功能是控制内部f o r c e s 通道中拓扑、路由的配置等 信息的流量。 负载查询l f b ：主要功能是查询各f e 当前负载状况，并将信息上报给 c e 的业务负载评估模块。 l f b 操作接口：c e 通过该接口控制构件，实现抽象到具体的映射，以此来 支持f e 功能的可重构。 构件资源：用户自定义的构件实体集合。 1 2 2 2 集群资源管理系统概述 集群资源管理系统是一类系统软件，在讲诉f o r c e s 集群路由器资源管理系 统体系结构前，我们将首先阐述集群资源管理系统的基本概念、评价集群资源管 理系统的指标以及介绍几种现有的典型集群资源管理系统。 2 2 1 集群资源管理系统基本概念 通常，集群系统的组成很复杂，为了能够让用户方便、透明的使用整个集群 系统，也为了方便整个集群系统的管理和调度，就需要一个集群资源管理系统可 以根据用户的需求，统一管理整个系统内的所有资源，当然也包括用户提交的作 业，然后通过合理分配资源给各个作业来保证各个用户能够公平合理地共享集群 系统资源，使整个集群系统达到最优的性能。它有以下3 部分组成【捌： 用户服务器：用户通过用户服务器向队列提交作业，并向队列告知每个 作业运行所需的资源，也可以通过用户服务器询问作业或队列的状态信 息。 作业调度器：作业调度器会根据用户提交的作业信息和集群系统中各个 节点的资源信息产生一个作业优先级列表。此列表包含的信息有作业运 行的节点、作业的优先级、定义作业和计算环境的参数等等。 资源管理器：资源管理器可以使用户在不了解底层资源构成的情况下进 行有效的资源管理，以此来提高集群系统的利用率，它也允许用户调整 管理资源的方式。在集群资源管理系统中，资源管理器的主要功能是进 程迁移、计算资源分配和定位等等。 2 2 2 集群资源管理系统评价指标 判断集群资源管理系统是否高效、透明我们可以从它是否能提高集群系统的 吞吐率、资源利用率、平均响应时间来考虑。 系统资源利用率：系统资源利用率的高低是评判一个集群资源管理系统最重 要的指标，系统资源利用率越高，说明系统的可吞吐能力越大，各个资源之间的 共享也做得越好，考察系统资源利用率是充分发挥集群系统中所有资源的功能， 从而能够使集群系统达到最优的性能。 系统吞吐率：表示集群系统在单位时间内所能够处理的作业数量。国内外大 量的研究发现，系统的吞吐率可以通过流水线化或者为所有节点分配可以并行的 作业来提高： 平均响应时间：对于用户来说，作业的平均响应时间是最重要的，表示的就 是作业递交到系统的时间和作业结束运行的时间的差值，求出所有作业响应时间 的平均值即作为平均响应时间。 平均等待时间：表示的就是所有作业提交给系统的时问和作业开始运行的时 间的差的平均值，即作业在等待队列中所呆时间的平均值。 平均减速：作业的减速主要来自于c p u 队列的等待时间、进程通信时间以 及进程迁移的开销等因素。平均减速是作业的t 时间和它使用的c p u 时间的比 值的平均值，t 时间等于作业运行时间、队列等待时间和进程迁移时间的总和。 2 2 3 典型的集群资源管理系统 集群资源管理系统的研究已经成为国内外高性能计算领域的一个热点问题， 目前已经出现了几十种类似的集群资源管理系统，它们在目标、结构、功能和实 现上各有所长，适用于不同的集群系统，也反映了一个好的集群资源管理系统所 应具备的特性。t o r q u e 、l s f 、c o n d o r 、l o a d l e v e l e r 是现有管理系统 中比较典型的集群资源管理系统。其中o p e n p b s 演变来的t o r q u e 、威斯康星 大学开发的c o n d o r 是研究产品，而加拿大p l a t f o r mc o m p u t i n g 公司开发的 l s f 、i b m 开发的l o a d l e v e l e r 则是商用软件。下面，我们将介绍下这几种 资源管理系统： 1 t o r q u e t o r q u e 2 7 】是由开源p b s 项目发展而来的，是一种可以用来控制批处理任务和 分布式计算节点的集群资源管理系统。它在许多方面都较p b s 有了增强，主要特 点是： 可以深入到内核级的节点检测和错误修订。 提供了可扩展查询接口，相比p b s ，它可以提供除t c l 、c 语言外更多 的a p i 接口。 1 4 提供了可扩展控制接口，这样的好处就是可以增强控制用户行为和属 性。 在t o r q u e 中，服务器和各个节点之间具有更强的通信能力。 t o r q u e 支持的集群规模更大、支持的作业处理能力更强大。 2 l s f 负载共享软件l s f 是由加拿大p l a t f o r mc o m p u t i n g 公司开发的，它的前身是由 t o r o n t o 大学开发的u t o p i a 系纠引。在此基础上，它加强了科学计算和企业事务处 理方面的功能。相比一般研究产品而言，l s f 具有更强大的功能和更稳定的性能， 无论是在负载平衡、系统容错方面，还是在检查点操作、进程迁移方面，都要做 的更好。其主要特点是： 支持检查点操作( 核心级、用户级及应用程序级) 和进程迁移。 可以对集群系统内的节点进行动态的负载检测，从而达到动态负载平 衡，它能检测的负载指标包括节点状态、运行队列长度、c p u 利用率等 等。 除提供更多调度策略外，它特别为紧急作业提供了抢占式调度和关键资 源保障，从而可以满足特定用户的需要。 3 c o n d o r 、 威斯康星大学研究团队开发的c o n d o r 刀是一个可以充分利用工作站休闲 时间的集群作业管理系统。c o n d o r 管理的集群系统由网络中的工作站组成， 它时刻监测网络中所有工作站的状态，一旦有某台计算机处于空闲状态，便把它 纳入到资源池中，在资源池中的所有工作站都可被用来执行作业。如果当前工作 站被所有者使用，c o n d o r 便会将运行在该工作站上的作业迁移到资源池中的 其它结点上继续运行，这样不会影响到工作站主人使用该工作站。其主要特点是： 提供了自动寻找空闲节点和分配空闲节点功能，系统监视局域网中所有 节点的负载情况，一旦有某台计算机处于空闲状态，便把它纳入到动态 资源缓冲区中。 对网络资源、数据传送和检查点操作有效监控。 提供了远程系统调用机制，如此可以使远程节点上的文件系统和其它特 性与用户最初提交任务的节点几乎一致。 4 l o a d l e v e l e r i s _ l o a d l e v e l e r 【9 】是美国i b m 公司开发的商用集群作业管理系统。由于它具有灵 活高效的特点，因此被广泛的应用于教育机构、研究所和企业等各个行业，具体 应用内容包括集群系统测试仿真、经济分析、天气预报等等。和c o n d o r 类似， l o a d l e v e l e r 也有资源池概念，用户可以向资源池中所有机器提交作业。除了支持 i b m 公司自己的a i x 操作系统外，它还支持了h p 公司u n i x 、s g i 公司i r i x 和 s o l a r i s 等多种主流u n i x 平台。其主要特点是： 支持多种作业，包括并行、串行和批处理作业等。 支持用户自定义作业类，该类作业可以被系统优化调度。 采用系统中心节点集中控制，相比其它集群作业管理系统有更好的可用 性。 2 3f o r c e s 集群路由器资源管理系统体系结构 对f o r c e s 集群路由器用户来说，他没有必要去了解整个f o r c e s 集群路由 器