（计算机应用技术专业论文）基于时间序列预测的ip控制网关集群的设计与实现.pdf

j 一r 时闸序列预测的i p 控制架群的设汁与实现 r t 文摘要 基于时间序列预测的i p 控制网关集群的设计与实现 中文摘要 为了解决i p 控制网关( i p c g ) 带宽不足的问题，本文提出了基于时间序列预 测的i p c g 集群，实现了基于时间序列预测的负载均衡调度算法以及基于n e t f i l t e r 和策略路由的负载均衡技术。 本文首先介绍了集群、负载均衡集群和影响负载均衡的三要素：调度算法、网 络拓扑结构和调度粒度；接着介绍了服务器负载的衡量指标及计算方法和常用的负 载均衡算法，分析了这些算法的不足；结合i p c g 负载变化规律，提出了基于时间 序列预测的负载均衡凋度算法，详细介绍了利用历史负载数据构建时间序列模型的 过程，并利用构建的a r i v i a ( p ，q ) 模型对i p 控制网关负载进行了预测，取得了较好 的预测效果：然后，介绍了负载均衡集群中常用的三种负载均衡技术：n a t 、i p t u n n e l i n g 和d r ，在分析了n e t f i l t e r 框架和策略路由的基础上，提出了基于半连接 的：状态检! ：! j j 0 方法以及适用于i p c g 集群的基于n e t f i l t e r 和策略路由的负载均衡技术， 并对其进行了实验：最后，把基于时间序列预测的负载均衡调度算法和基于最小连 接数的负载均衡凋度算法在i p c g 集群中进行了实验，对比了两者的负载均衡效果； 而且对比分析了i p c g 和i p c g 集群的网络流量，实验结果表明本文所提出的算法 和实现方法不仅实现了高带宽的i p c g 集群，而且还具有良好的负载均衡效果，能 应用于i n t r a n e t 和i n t e m e t 之间的网络连接处的高速网络防火墙( 入侵检测) 集群和 i p c g 集群等新一代网络系统中。 关键词：i p 控制网关：时间序列：n e t f i l t e r ：策略路由；负载均衡 作者：杨伟 导师：钱培德 t h ed e s i g na n di m p l e m e n t a t i o no fi pc o n t r o lg a t e w a y c l u s t e rb a s e do nt i m es e r i e sp r e d i c t i o n a b s t r a c t i no r d e rt or e s o l v et h ei s s u et h a tt h eb a n d w i d t ho fi pc o n t r o lg a t e w a y ( i p c g ) i s n t e n o u g ht of o r w a r dp a c k e t s ，t h i st h e s i sp r o p o s e st h ei p c gc l u s t e rb a s e do nt i m es e r i e s p r e d i c t i o n ，i m p l e m e n t st h el o a db a l a n c i n ga l g o r i t h mw h i c hi sb a s e do nt i m es e r i e s p r e d i c t i o na n dt h et e c h n i q u eo fl o a db a l a n c i n gw h i c hi sb a s e do nn e t f i l t e ra n dp o l i c y r o u t i n g ， f i r s t l y , t h et h e s i si n t r o d u c e st h ec o n c e p to fc l u s t e r , t h ec o n c e p to fl o a db a l a n c e c l u s t e ra n dt h em o s ti m p o r t a n tf a c t o r si nl o a db a l a n c i n g ，s u c ha ss c h e d u l i n ga l g o r i t h m s ， n e t w o r kt o p o l o g ya n ds c h e d u l i n gg r a n u l a r i t y s e c o n d l y , i ti n t r o d u c e st h ei n d e x e so ft h e s e r v e rl o a d ，t h ec o m p u t i n gm e t h o d sa n da l g o r i t h m s ，a n da n a l y z e st h ed i s a d v a n t a g e so f a l g o r i t h m c o m b i n e dw i t ht h ec h a n g i n gr e g u l a r i t yo ft h ei p c g sl o a d ，i tp r o p o s e st h e p r e d i c t i o na l g o r i t h mo f l o a db a l a n c i n gb a s e do nt i m es e r i e s ，a n de x p o u n d st h ep r o c e s so f b u i l d i n gt h em o d e lo ft i m es e r i e sa c c o r d i n gt ou s i n gt h ei p c g sh i s t o r i c a ll o a dd a t ai n d e t a i l s i ta l s oa p p l i e st h ea r m a ( p ，q ) m o d e lt op r e d i c tt h el o a do fi p c gt h em o d e li s p r o v e dt ob em o r ee f f i c i e n ti nt h ep r o c e s so fp r e d i c t i o n t h i r d l y , i ti n t r o d u c e st h eg e n e r a l t h r e el o a db a l a n c i n gt e c h n i q u e sw h i c ha r en a t , i pt u n n e l i n ga n dd r o nt h eb a s eo f a n a l y z i n gt h ef r a m e w o r ko fn e t f i l t e ra n dp o l i c yr o u t i n g ，i tp r o p o s e st h eh a l f - c o n n e c t i o n s t a t ed e t e c t i o nm e t h o da n dt h el o a db a l a n c i n gt e c h n i q u ew h i c hf i tt oi p c gc l u s t e r f i n a l l y , i tc o m p a r e st h ep e r f o r m a n c eo ft h ea l g o r i t h mb a s e do nt i m es e r i e sp r e d i c t i o n w i t ht h ea l g o r i t h mo fl e a s t c o n n e c t i o ns c h e d u l i n gi nt h ei p c gc l u s t e ra n dc o m p a r e st h e n e t w o r kt h r o u g h p u to fi p c gw i t hi p c gc l u s t e r , t h e nm a k e so u tt h ec o n c l u s i o nt h a tt h e a l g o r i t h ma n dt h ei m p l e m e n t a t i o nm e t h o dp r e s e n t e di nt h et h e s i sc a nn o to n l yg e tah i g h b a n d w i d t h ，b u ta l s og a i nt h ee f f e c to fl o a db a l a n c i n gi ni p c gc l u s t e r t h ea l g o r i t h ma n d t h et e c h n i q u ec a nb eu s e di nt h en e wg e n e r a t i o nn e t w o r ks y s t e m sw h i c hl i n kt h ei n t r a n e t t ot h ei n t e r a c t ，s u c ha st h ef i r e w a l lc l u s t e r , t h ei d sc l u s t e r ，i p c gc l u s t e ra n ds oo n 1 1 t h ed e s i g na n di m p l e m e n t a t i o no f 【pc o n t r o lg a t e w a yc l u s t e rb a s e do nt i m es e r i e sp r e d i c t i o na b s t r a c t k e y w o r d s ：i pc o n t r o lg a t e w a y , t i m es e r i e s ，n e t f i l t e r , p o l i c yr o u t i n g ，l o a db a l a n c e w r i t t e nb yy a n gw e i s u p e r v i s e db yq i a np e i d e h i 工9 5 7 1 6 7 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名： 叠龟日期：塑兰：少 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位沦 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： 期：趔 ： ! 驰fh f 间序列预测的i p 控制网关架群的设计与实现 第1 章引言 1 1 研究背景及意义 第1 章引言 随着网络技术的飞速发展，校园网管理进入了一个崭新的时期。账户管理作为 网络管理的重要组成部分，既要对校园网用户访问的范围进行控制，又要对校园网 用户访问互联网的行为进行记录，同时还不能影响校园网用户访问互联网的速度和 质量。现在，一般高校采用代理服务器作为校园网用户访问互联网的途径，但是代 理服务器工作在应用层，一般是基于某种应用层协议的，比如h t t p 、s o c k s 等等这 样就使校园网用户无法使用采用其他协议的服务，给校园网用户带来了极大的不 便。而基于n e t f i l t e r 框架的i p c g 工作在网络层，与应用层协议无关，而且还具有 转发效率高、数据包状态检测、对用户透明等特点：这样，i p c g 不仅具有了代理 服务器的功能，同时，还可以提供其它的应用层服务，比如：r t s p 、i c q 等等。目前， 这技术在北京大学、中国农业大学、苏州大学等高校得到应用，并且取得了较好 的效果。 但是，随着中国教育与科研网( 教育网) 的c e r n e t 2 的开通，很多院校的教 育网f 1 i1 3 由1 5 5 m b p s 专线变成了2 5 g b p s 。这样就使原来在1 0 0 0 m b p s 带宽环境下 运行的i p c g 成为了校园网出口的瓶颈。在目前没有更好的技术出现的情况下， p c g 集群是一种比较好的解决方法。l i n u x v i r t u a ls e r v e r 项目的负责人章文嵩博士在文 献 1 】中也提到：配置1 0 0 0 m b p s 网卡，采用v s t u n 或v s d r 调度技术，集群系 统的吞吐量可接近1 0 g b p s ，这一点为采用集群提供了保证。集群作为网络时代的产 物，一般是运行在应用层，目前各大门户网站：s o b u 、y a h o o 、1 6 3 等都是采用w e b 服务器集群的方式满足用户需求的。但是，一方面，i p c g 在网络层运行，这样就 使许多在w e b 服务器负载均衡集群中使用的技术无法在i p c g 集群中使用：另一方 面，i p c g 集群面向的用户是相对固定的，而且校园网用户上网的行为在很大程度 上和师生员工的生活规律是相关的，最明显的例子就是1 8 ：0 0 到2 2 ：0 0 之间 p c g 的 负载很重，而这一段时间恰好是师生访问互联网最频繁的时间段，与之相对应的是 在凌晨2 ：0 0 到6 ：0 0 之间i p c g 的负载很轻，这一段时间正是广大师生在休息的时间， 为此对i p c g 的负载变化做了专门的实验。实验结果显示i p c g 负载的变化呈现出 弧l | _ ：tq i 畜牲于时间序列预测的【p 控制网关堤群的设汁与实现 周期性和趋势性。从这一点不难看出i p c g 的负载和时间存在着某种关系。因此， 本文提出了基于时间序列预测的i p c g 集群。 i p c g 集群作为负载均衡集群的一种，不但具有一般负载均衡集群的透明性、 高可用性、可管理性；而且还具有与其他负载均衡集群不同的基于时间序列预测的 负载均衡调度算法及基于n e t f i l t e r 和策略路由的负载均衡技术。 1 2 国内外研究现状 目前，负载均衡集群包括w e b 服务器集群、入侵检测集群和防火墙集群三方面， 现在大部分研究集中在w e b 服务器集群方面。 w e b 服务器集群是由n c s a 提出并实现了一个原型系统“n c s as c a l a b l ew e b s e r v e r c l u s t e r ”后来b e r k e l e y 的n o w 小组、c i s c o 公司和i b m 公司也加入了这个 行列，提出了许多新思想和新方法，使集群的研究得到进一步的发展。目前，有很 多基于前端分配器的w e b 服务器集群，其中基于应用层负载均衡调度的典型代表有 z e u s 负载嗣度器、p w e b 、r e v e r s e p r o x y 和s w e b 等。基于i p 层负载均衡凋皮的典 型代表有b e r k e l e y 的m a g i c r o u t e r 、c i s c o 的l o c a l d i r e c t o r 、a l t e o n 的a c e d i r e c t o r 、 f 5 的b i i p 和章文嵩博士领导的l i n u xv i r t u a ls e r v e r 小组开发的l v s 。 在高带宽环境下，巨大的网络流量促使入侵检测系统和防火墙系统开始采用集 群技术，这样提高了入侵检测和防火墙的效率。文献【2 、文献 3 都是采用负载均衡 集群来提高入侵检测的效率，文献 4 】成功的把负载均衡集群应用于防火墙中。 目前，负载预测的研究可以分为网络流量预测和主机负载预测两个领域，其中 网络流量预测开始于2 0 世纪九十年代初期，目前比较成熟的理论( n e t w o r k w e a t h e r s e r v i c e 5 】等) 和产品( a r r o w p o i n t 、a l r e o n w e b 等) ；主机负载预测的研究相对起步 较晚，系统研究开始于二十世纪九十年代后期，其中最具代表性的人物是美国的 d i n d a 。d i n d a 从1 9 9 7 年开始就收集了大量的负载样本【6 】，并且由此提出了基于时 间序列的负载预测理论 7 】，建立了主机资源预测系统r p s t 8 1 ，并把r p s 应用于许多 系统中。国内关于主机负载预测的系统研究几乎是空白，只有文献 9 提出了基于人 工神经网络的b p 预测算法，文献1 0 1 提出了基于滤波理论的预测算法p a a ，文献 11 设计实现了基于时间序列预测的h l p s ，这些算法都具有一定的理论价值，但是 丛于时问序州颅测的i p 控制网关集群的没计与实现 第1 章引高 还没有形成完整的预测理论。 把主机负载预测应用于负载均衡集群的研究在国内几乎是空白，也只有文献 1 l 】 实现的h l p s 对此进行了一定的研究。 1 3 本文的主要工作和组织结构 本文首先介绍了集群、负载均衡集群和影响负载均衡的三要素：调度算法、调 度粒度和网络拓扑结构；其次介绍了常用的负载均衡算法及其不足，结合i p c g 负 载变化规律，提出了基于时间序列负载预测的负载均衡调度算法，详细介绍了构建 时间序列模型的过程，并利用构建的a r m a ( p ，q ) 模型对i p c g 负载进行了预测，取 得了较好的效果：然后，介绍了负载均衡集群中常用的三种负载均衡技术、n c t f i l t e r 框架和 p r o u t e 2 ，并提出了适用于i p c g 集群的基于n c t f i l t e r 和策略路由的负载均衡 技术，并且对这一机制进行了实验，证明该方法是可行的；最后，把基于时问序列 预测的i p c g 集群和基于最小连接数凋度的i p c g 集群进行了实验对比分析同时 还对比了单台i p c g 和i p c g 集群的网络流量，实验结果表明本文所提出的算法和 实现方法具有良好的负载均衡效果，而且有效的解决了i p c g 带宽不足的问题。 第l 章介绍了i p c g 集群研究的背景、意义，负载均衡集群以及负载预测的研 究现状。 第2 章详细介绍了负载均衡集群，以及影响负载均衡的三要素：凋度算法、网 络拓扑结构、调度粒度。 第3 章介绍了服务器负载的衡量指标、获取方法及特性和现有的负载均衡算法， 并分析了这些算法的不足，根据服务器负载的特性，结合i p c g 负载的变化规律提 出了基于时间序列预测的负载均衡调度算法，接着介绍了时间序列，并根据时间序 列详细介绍了如何实现基于时间序列的负载均衡调度算法，其中主要包括：数据预 处理、数据序列的平稳化处理、时间序列的模型识别、模型定阶、时间序列模型中 的参数估计以及如何进行时间序列模型预测，最后利用构建的时间序列模型 a r m a ( 8 ，7 ) 进行了预测试验，取得了较好的预测效果，并把构建了基于时间序列预 测的负载均衡调度算法。 第4 章主要介绍了基于i p 层的三种负载均衡技术和l i n u x n e t f i l t e r 框架的机制、 基于时问序列预测的i p 控制网关集群的故计与实现 功能、基于半连接的状态检测和连接跟踪等，同时还介绍了l i n u x 高级路由技术 ( i p r o u t e 2 ) ，着重介绍了策略路由技术，在比较n a t 、i pt u n n e l i n g 和d r 三种负载均 衡技术的基础上，提出了一种适用于i p c g 集群的基于n e t f i l t e r 和策略路由的负载 均衡技术。 第5 章在介绍i p c g 集群系统配置的基础上，分别对基于时间序列预测的负载 均衡算法和最小连接数算法进行了一周的实验，在对实验结果分析的基础上，得出 了基于时间序列预测的负载均衡调度算法具有相对较好的负载均衡效果；然后又进 行了网络流量分析实验，证实i p c g 集群的带宽得到极大的提高。 丝。j ：时州序列颅测的【p 控：制尉关架群的设计与实现 第2 章负载均衡! l ! 群 2 1 集群 第2 章负载均衡集群 i n t e m e t 的飞速发展给网络带宽和服务器带来了巨大地挑战，从网络技术的发展 来看，网络带宽的增长速度远远高于处理器和内存的增长速度；其次，随着网络技 术的发展，各大门户网站的访问量快速增氏，导致这些门户网站无法提供高质量、 高效率的服务：另外，大部分网站还需要提供每天2 4 小时、每周7 天的服务，尤 其是电子商务网站，任何服务的中断或关键性的数据丢失都会造成直接的经济损 火：还有，在一个由网络连接的多计算机系统中，某一时刻，会出现一些计算机的 负载较轻，而另外一些计算机的负载较重，即出现t b l - 算机之间的负载严重不均衡 现象。以上四种情况，促使了集群的出现。 集群技术就是采用通用的计算机硬件和常用的( 甚至是免费的) 软件，来构造 高。p _ - i - ：f ：i l 的计算机平台和服务平台，解决大规模科学计算、工程领域和商业应用方面 所遇到的问题。集群技术的飞速发展一方面得益于廉价且性能较高的微处理芯 片、高速网络以及用于高性能分布式计算的标准软件的飞速发展和技术上的突破； 另一方面，则是因为科学计算和商业应用领域对计算能力的迫切要求。 2 1 1 集群的定义 集群( c l u s t e r ) 又称为机群或群集，是由一组完整的计算机按照某种结构连接而 成，每个节点可以是一个工作站、一台较小的个人计算机，甚至一台规模相当大的 对称多处理机系统( s m p ) ，每个节点上都有一套完整的操作系统，节点通过网络互 联，用消息传递方式进行通信，统一调度、协调处理，实现高效并行处理的计算机 系统。 2 1 2 集群的特点 集群是由一组完整的计算机互连而成的，作为一个统一的计算机资源来使用。 郝2 壮负城均衡集群坫于时间序列预测的i p 控制网关地群的设汁与实现 ( 1 ) 组成集群的各个节点可以是一个工作站，或者一台个人计算机，也可以是一 个规模相当大的对称多处理机( s m p ) 。集群中的每个节点都有一套完整的操作系统。 节点之间通过网络( 局域网、互联网等) 相连。 ( 2 ) 集群作为一个统一的计算机资源对外提供服务。对于集群而言，最重要的特 点就是具有单一系统映像，也就是说从用户角度看，整个集群系统就是一个单一的 系统，用户可以在任何地点使用这个集群，而不必关心提供这个服务的计算机在何 处。用户使用集群时，各个节点计算机可以自由的切换，以完成请求的服务，用户 不需要指定使用哪台计算机。也就是说，集群具有对用户透明的特点。 ( 3 ) 集群利用硬件冗余的原理来提高可靠性和可用性。利用心跳测试和故障恢复 技术，尽可能地保讧e 任何集群组件发生故障都不会影响集群的正常运行。 2 1 3 集群的分类 集群一般可以分为高可用性集群、高性能集群和负载均衡集群三类。 ( 1 ) 高可用性集群 商可用性集群的主要功能就是提供不问断的服务。有许多应用程序必须每天2 4 小时、每周7 天地不间断地运转，如所有的w e b 服务器、电子商务网站、a t m 、 远程通讯转接器等。任何应用程序的中断或关键数据的丢失都会造成很大的损失， 尤其是电子商务网站。例如：根据d e l l 的新闻发布【13 1 ，d e l l 现在每天在网上的交易 收入为一千四百万美元，- d , 时的服务中断就会造成平均五十八万美元的损失。这 对应用程序的可靠性提出了越来越高的要求。 ( 2 ) 高性能集群 高性能集群充分利用集群中的每台计算机的资源，实现对大量数据的复杂运算 的并行处理，通常用于科学计算领域，比如基因分析、化学分析、图像处理等，以 及模拟星球附近的磁场、预测龙卷风的出现、定位石油资源的储藏地等。传统的处 理方法是使用超级计算机来完成计算工作，但是超级计算机的价格比较昂贵，而且 可用性和扩展性不够强，因此集群成了高性能计算领域的焦点。 ( 3 ) 负载均衡( l o a db a l a n c e ) 集群 负载均衡集群就是把负载压力根据某种算法合理地分配到集群中的每台计算 j 占j 二州f i j jj ：卜列| ：l ； 洲的l p 控制蚓关集群的设汁与实现第2 章负拔均衡集群 机上，以减轻主服务器的压力，降低对主服务器的硬件和软件要求。负载均衡集群 在w e b 服务器上应用较多，尽管它支持许多应用层的协议：印、t e l n e t 、p o p 3 、s n m p 等，但用处最多的还是h t t p 服务。在负载均衡集群中，表面上是用户访问一个i p 地址，但实际上后台有若干台服务器在提供服务。当服务请求达到饱和时，还可以 很容易地添加新的服务器而不用停止提供服务，即所谓的“热插拔”，这也是集群 的易扩展性。另外，负载均衡集群还可以查询真实服务器的情况，当某台真实服务 器没有响应时，就不再把请求分配到这台真实服务器，直到这台服务器恢复正常( 即 心跳测试) ，而且服务器的切换过程对用户是透明的。 2 2 负载均衡集群 所谓负载均衡就是在由多台服务器以对称的方式组成的一个服务器集合中，每 台服务器都具有等价的地位，都可以单独对外提供服务而无需其他服务器的协助。 通过某种负载分担技术，将外部发送来的请求均匀地分配到对称结构中的某台服务 器一l - ，接收到请求的服务器则独立地响应用户的请求。 负载均衡的作用就是实现各个服务器之间的负载相对均衡，不会出现在相同时 刻，有些服务器负载较重，有些服务器的负载较轻的情况，使用户的请求都能得到 及时地响应。 负载均衡集群是基于负载均衡技术的集群系统，即集群中的服务器具有等价的 地位，既可以对外单独提供相同的服务又可以和其它服务器一起为用户提供服务： 通过某种负载调度算法，将用户发送来的请求均匀地分配到各台服务器上，然后由 接收请求的服务器响应用户的请求。这样，充分发挥了集群并行处理的能力，把请 求分配到剩余处理能力最强的节点，使该请求在最短的时间内得到响应。 2 3 影响负载均衡的因素 对于负载均衡集群来说，如何实现负载均衡是最重要的。而影响负载均衡的因 素是算法、网络拓扑和调度频率。其中，算法是指负载均衡调度算法，调度频率 是指调度粒度。 第2 章负载均撕架群 丛于时间序列预测的i p 控制网关集群的设汁与实现 2 3 1 调度算法 负载均衡调度算法可以分成静态调度算法和动态调度算法。静态调度算法不管 各个服务器运行时刻的负载情况，而只是根据预先设定的分配方案对用户的请求进 行分配。动态负载均衡算法则是根据各个服务器运行时刻的负载情况，按照某种算 法将用户请求分配给当前负载最小的服务器。 动态负载均衡算法又可以分为中心任务调度策略、梯度模型策略、发送者启动 策略和接收者启动策略。这些策略会在下一章中进行详细介绍。文献 1 4 中，介绍 了在不考虑网络拓扑结构、调度粒度的情况下，采用接收者启动策略完成任务所需 要的时间总是比发送者启动策略所需要的时间短，而发送者启动策略又比梯度模型 策略好一些，中心凋度策略需要地时间最多；但是，一般接收者启动策略实现起来 相对比较麻烦，所以现在的负载均衡集群大部分还是采用发送者启动策略。 2 3 2 网络拓扑结构 目前，比较常用的拓扑结构有2 d m e s h 、超立方体、f i b o n a c c i 立方体和线性网 络等。文献 1 5 中对各种算法及网络拓扑机构进行了模拟( 采用4 * 4 m e s h 、4 维超 立方体、1 6 结点f i b o n a c c i 立方体和1 6 结点线形网) ，并给出了模拟结果。 从表2 1 和表2 2 可以看出，在m e s h 、超立方体及f i b o n a c c i 拓扑结构中，算 法起主导作用。如果再进一步分析算法相同的情况下各种拓扑结构的影响，就可以 得到在平均距离小和平均结点度大的网络拓扑结构上运行的时间比较短。在线性网 络中，所有的算法和性能都降到最低。中- t l , 调度策略的效果则超过其他三种算法。 这是因为其他三种算法都将直接相邻的结点作为相关结点域，在平均结点度降低时 受到很大影响，而中心调度策略算法中没有相关结点域的概念，所以虽然效率下降 了，但它受的影响却小得多。因此，在选择拓扑结构时，应尽可能的选择平均结点 度较大的结构。在平均结点度较大的拓扑结构中，可以考虑采用接收者启动策略。 捧于i l f 问序列颅测的i p 控制网关集群的设计与实现 第2 章负戴均衡臻群 表2 1 几种网络拓扑的平均距离和平均结点度 结点度的分布 拓扑平均距离平均结点度 12345 6 4 * 4 网络2 6 7 4 8 4 3 0 0 4 维超立方体 2 131 64 0 0 f i b o n a c c i2 4 l 572l13 1 3 线性网络 5 6 721 41 8 8 表2 2 模拟结果 拓扑中心任务梯度模型 发送者启动 接收者启动 n o l b0 p t 网络3 0 0 8 42 9 6 8 32 9 4 6 02 8 7 8 43 2 5 2 92 8 1 6 2 超立方体 2 9 9 0 02 9 5 4 7 2 8 9 6 02 8 5 0 7 3 2 5 2 9 2 8 1 6 2 f i b o n a c c i2 9 7 8 l 2 9 6 6 62 9 3 7 i2 8 6 “3 2 5 2 92 8 1 6 2 线性网络3 0 1 3 l 3 0 8 9 63 0 4 2 03 0 2 9 73 2 5 2 92 8 1 6 2 2 3 3 调度粒度 从直觉上看，负载均衡的粒度越小，进行的越频繁，系统就能够越快地响应服 务器性能的变化。然而，负载均衡是有开销的，过于频繁的均衡会抵消其带来的好 处。负载均衡的开销主要包括4 j ： 服务器间交互的开销：这个开销在中心凋度算法中尤为明显。服务器交互任务 完成情况所消耗的时间与两次调度之间的时间间隔相比必须很小。 服务器间任务迁移的开销：工作移动的开销决定了在什么情况下移动工作才是 合算的。如果没有必要的限制，甚至有可能导致任务不必要的往复迁移。 如果服务器上运行的是多任务的操作系统，计算任务执行就有可能因为操作系 统的任务凋度而受到影响。如果负载均衡周期与操作系统调度周期相近，在计算任 旃2 啦负拔均衡必群基于时间序列预测的i p 控制网关架群的设计与实现 务被调度到前台时，该节点的运算速度很快；反之，如果计算任务被调度到后台， 则该服务器的运算速度又大幅度地降低，那么这必然导致计算任务的错误移动。只 有在负载均衡频率大于操作系统调度时间数倍时才能够将上下文切换带来的影响 抵消掉。 总之，可以选择这三个下限中最大的一个作为实际应用的负载均衡频率，从而 也就确定了动态负载均衡的适当粒度。 2 4 本章小结 本章首先介绍了集群出现的原因，其次给出了集群的定义和分类，再次对负载 均衡集群进行了详细的介绍，最后对影响负载均衡的三种因素进行了详细的介绍。 肇于时州序州f ! i | 测的i p 控制网荚集群的驶汁与实现第3 章i p c g 架群的负载均衡渊度算法 第3 章i p c g 集群的负载均衡调度算法 3 1 服务器负载 在负载均衡集群中，如何获取服务器负载是实现负载均衡的基础，也是负载均 衡集群研究的热点和难点。而服务器负载又取决于负载指标。负载指标是衡量服务 器负载状态的特征值，用于描述服务器的忙闲程度，记录服务器处理服务的能力， 一般有c p u 处理能力、c p u 利用率、c p u 就绪队列长度、内存、磁盘容量、网络 带宽、当前连接数等。不同用途的服务器负载指标一般是不一样的，对于w e b 服务 器而言，一般用网络流嚣作为唯一的负载指标：有些服务器则把c p u 、内存、磁盘 容嫩、当前进程数作为负载指标。在服务器负载受多个负载指标影响时，每个负载 指标值的变化对服务器负载所产生的影响是不一样的。也就是说，不同的负载指标 有不同的负载权重，权重越大表示这个负载指标的变化对服务器负载产生的影响越 大，反之，权重越小对服务器负载所产生的影响也越小。 3 1 1 服务器负载的定义 定义l ：l o a d = i n d e xf + r f t ；l 其中，l o a d 是服务器负载，i n d e x ，是负载指标，忍是相应负载指标的权重。既 然服务器负载取决于负载指标和相应的权重，如何选取负载指标以及如何确定负载 指标的权重就成为计算服务器负载的关键问题。 负载指标的选择要根据服务器所提供的服务来确定。w e b 服务器的主要功能就 是提供w e b 服务，因此，可以把网络利用率、内存使用率、c p u 利用率作为它的 负载指标：而f t p 服务器，除了这三项要作为负载指标以外，还必须考虑到磁盘， 因为f t p 服务器要进行大量的i o 操作。对于i p c g 来说，它主要的功能就是数据 包的转发，几乎不涉及磁盘的l j o 操作，因此，可以把网络利用率、c p u 利用率、 内存作为负载指标。 第3 带i p c g 集腓的负载均衡调度算法基于时间序列预测的i p 控制网关集群的设计与实现 在负载指标选定后，就要为每个指标确定权重。权重一般是通过大量的实验， 不断修正得到的。当然，在集群一开始运行的时候，可以根据以往的经验为每个负 载指标设定权重。 对于i p c g 来说，可以把网络利用率n e t 、c p u 利用率c p u 和内存使用率m e m o r y 作为负载指标，它们的权重分别为r 、r 。、r 。，那么i p c g 的负载l o a d ： 定义2 ： l o a d = n e t + r m + c p u + 。+ m e m o r y + r 。 其中，r n “+ 尺印“+ r m p 。21 ( 3 1 ) 3 1 2 服务器负载的获取 确定了负载指标，如果要计算服务器负载，还要确定负载指标的值。获取负载 指标的方法一般有以下两种： ( 1 ) 从p r o c 文件中获取 在l i n u x 系统中，目录p r o c 下的文件和子目录记录了系统的一些运行状态，包 括系统进程信息、c p u 使用情况、磁盘1 1 0 情况、内存使用情况等。这些文件和目 录并不存在于磁盘中，而是存储在内存中的虚拟文件系统中。口r o c 文件系统读取内 核的执行情况，从p r o c 文件系统中可以获得所需要的负载信息。 在p r o c l o a d a v g 文件中记录了1 秒钟平均负载、5 秒钟平均负载、1 5 秒钟平均 负载、总作业数、正在运行的作业总数等5 种信息。 在p r o c s t a t 文件中记录了c p u 空闲时间、c p u 系统时间、c p u 用户时间等信 息。 在p r o c m e m i n f o 文件中记录了存储器的信息，主要包括：活动存储器、不活动 存储器、缓冲存储器、高速缓冲存储器、总的自由存储器、共享存储器等信息。 在p r o c n e t d e v 文件中提供了每个网卡接收到的字节、收到的总包数、已传输 的字节、传输的总字节等信息。 ( 2 ) 通过执行l i n u x 命令获取 用f r e e 命令可以获得内存的相关信息。为了直接获取已使用内存，可以执行如 下命令： 些二r 时问序列颅测的i p 控制网关集群的改汁与实现 第3 章i p c g m 胖的负绒均衡训度算浊 r o o t j s j g wp r o c # f l e el g r e pm e ma w k p r i n t $ 2 同样，可以用s a r 命令获得c p u 使用情况，为了直接获取1 0 秒钟内的平均值， 可以使用如下命令： r o o t s j g w 】# s a r u25g r e pa v e r a g ea w k p r i n t $ 7 ) 对于网络使用信息也可以用s a r 命令获取。如果要获取网卡e t h 0 的已使用带宽， 可以直接用如下命令： r o o t j s j g w 】拌s a r nd e v 22g r e pe t h 0f g r 印a v e r a g e a w k p r i n t $ 6 + $ 7 其中，$ 6 是接收带宽，$ 7 是发送带宽。 当然，这些信息也可以直接用内核模块来获取。但是，自己编写的内核模块可 能会和系统内现有的内核模块发生冲突，因此，这种方法这里就不再介绍。 3 1 3 服务器负载的特性 要准确地预测负载，首先就要知道如何准确的衡量负载，即认识清楚服务器负 载的特性。美国的卡内基一梅隆大学的p e t e r a d i n d a 于1 9 9 7 年和1 9 9 8 年分两次 对3 8 台不同的机器，其中包括集群服务器、计算服务器和桌面主机等进行长期的 跟踪抽样，获得了大景的负载图样。通过对这些图样进行统计分析，d i n d a 总结出 了负载的特性，这些研究成果收录于文献 1 3 、【1 6 】中。从这两篇文献中可以得出负 载的七个特性： ( 1 ) 负载的变化是一种随机过程，负载可以看作是一种资源信号，表示为 l o a d ( t ) = l o a d ( 1 ) ，l o a d ( 2 ) ，l o a d ( 3 ) ，l o a d ( t ) ，l o a d ( t + 1 ) 。 ( 2 ) 负载一般处于较低的水平，但具有较强的波动性。低端的桌面型主机平均负 载量远远低于其他类型的。这些高差异性表明进行负载预测来均衡负载是有其现实 意义的。 ( 3 ) 平均负载量高的主机其负载的绝对波动量也大，也就是说其最大负载量和最 小负载量之间的差值较大；但是从相对波动量( 负载波动量与平均值的比) 来说， 平均负载高的主机要低于平均负载低的。这种最大负载量与平均负载量的关联性表 明对负载较重的机器进行预测是有较高价值的。 ( 4 ) 负载值的分布性是比较复杂的，尤其是平均负载量高的，其负载值呈现复合 第3 啦i p c g 集衅的负救均衡调艘算法基于时闻市列预测的i p 控制网关集群的设计与实现 多样性。这种分布复杂性表明对负载进行分析、预测应该是图样驱动，而不能简单 的依据分布曲线。 ( 5 ) 负载随时间变化有很强的关联性，即过去的负载值对将来的负载值有很大的 影响。这表明依据过去的负载值对将来的负载值有很大的影响，那么依据过去的负 载值进行负载预测是可行的，而且利用时间序列模型进行负载预测也是合适的。 ( 6 ) 负载的变化又有高度的自相似性，即在所有的时间尺度下，负载的变化既复 杂，又有长期的依赖性，所以负载的模型化和预测是困难的。 ( 7 ) 负载的变化具有突变性。负载值在某一个时刻会有比较大的波动，然后又趋 于平稳。负载的这种突变性表明负载预测应具有修正和重适应机制。 3 2 负载均衡调度算法 负载均衡调度算法是影响负载均衡的三大因素中最重要的一个因素。在2 2 ：竹 中，简单的提到过影响负载均衡的三方面因素。这里将详细介绍负载均衡调度算法。 目前，人们提出了许多种负载均衡调度算法用于实现负载均衡集群系统的负 载均衡。这些算法大体上可以分为动态调度算法和静态调度算法，静态调度算 法不管各个服务器运行时刻的负载情况，只是根据预先设定的分配方案对用户的请 求进行分配。动态负载均衡算法则是根据各个服务器运行时刻的负载情况，按照某 种算法将用户请求分配给当前负载最小的服务器。 3 2 1 动态负载均衡算法的分类 动态负载均衡算法又可分为发送者启动策略、接收者启动策略和自索取策略三 类。 ( 1 ) 发送者启动策略( s e n d e r - i n i t i a t e dp o l i c y ) 接收请求的服务器来执行服务期间的请求调度分配。至于分配给哪个服务器， 则主要取决于各个服务器的负载状态。因此，该策略需要交换服务器的负载信息。 ( 2 ) 接收者启动策略( r e c e i v e r - i n i t i a t e dp o l i c y ) 由空闲服务器逐个向其它相邻服务器索要请求，如果索要到请求，就终止索要， 否则将继续询问下一个相邻服务器。如果所有相邻服务器都没有满足请求则索要 基于时删序列颅删的i p 控制网关集群的驶计与实现第3 章i p c g 榘群的负载均衡调度算池 服务器等待，过一段时间后再向相邻服务器发出索要请求。 ( 3 ) 自索取策略 若干服务器把其中一台服务器作为信息中心，各结点时刻监听信息中心。其中 任何一台服务器的负载状态发生变化，该服务器都会向信息中心汇报它的负载状态 信息，并从信息中心接收其它服务器负载状态信息。超载的负载消息也被作为请求 由信息中心记录下请求的服务器编号，由空闲服务器根据信息中心的记录主动调入 执行。 3 2 2 动态负载均衡算法的组成 以上提到的所有动态负载均衡算法都是由转移策略、选择策略、定位策略和信 息策略组成的。 ( 1 ) 转移策略 确定一个：点是否参与任务转移，如果参与，是作为发送者，还是接收者。转 移策略一般可分为以下三类： 手动策略：清求转移时，由用户指定请求发送者和接收者： 门限策略：如果某节点负载大于某个设定值t l ，则此节点作为请求发送者，如 果某：似点负载小于某个设定值t 2 ，则此节点作为请求接收者； 相对策略：如果某节点负载高于其他节点一定差值c l