（计算机应用技术专业论文）校园网络中自适应负载均衡算法研究.pdf

摘要摘要负载均衡集群技术中的负载均衡算法是整个互联网络应用研究中一个重要问题。本课题针对“需求快速变化这一企业级管理软件开发中呈现的特点，基于网络中的应用集成管理模式已成为管理信息系统发展的主流，而网络上运行的教育教学软件之间的互操作性差、应用集成水平较低，无法实现信息的共享与交流这一问题，将企业应用集成的概念和技术运用到解决网络“信息孤岛 实际问题当中，提出一种新的集群结点负载表示和基于排队理论的负载均衡调度算法以及基于文化算法的负载均衡算法。在研究、构建管理信息系统互操作框架的过程中我们发现，随着服务器数目的增加、系统规模和通信数据的增大，有必要在搭建集成服务器的过程中，利用负载均衡集群技术增强区域集成服务器的处理能力。本文通过对当前主流和常用的负载均衡算法理论的理解和研究，提出了一种新的负载表示方案。它不仅充分考虑到了当前服务器的各种硬指标负载，更考虑到了它的软指标负载，即其输入队列对当前以及随后时间负载的连续性和预见性的判断。并采用仿真程序对其表示方式进行了实验对比和分析。有了更为合理的负载表示后，本文随后提出了基于排队理论的负载均衡调度算法和基于文化算法的负载均衡算法。基于排队理论的负载均衡算法根据当前的负载情况和服务器的剩余处理能力，计算出服务器在随后的固定时间间隔中所需要的平均到达率，进而得到任务分配策略。并对其进行了仿真实验和对比分析。在基于文化算法的负载均衡算法中，充分利用了人类文化进化的思想，应用到了负载均衡算法中。群体本身在产生交叉和变异，而由于长期的活动和繁衍替换，使得群体中好的文化信息得以保存，而相对较差的信息被丢弃。这样也使得群体的文化在不断的被更新，进而影响这群体的不断进化。在经过一定的进化代数后，会得到一些相对优秀的个体，这便是我们的分配策略了。本文在文中对其思想进行了详细的描述和设计，并对其进行了仿真实验和对比分析，证明其比常用的负载均衡算法效果较优。关键词：负载均衡，排队论，文化算法，校园网络a b s t r a c ta b s t r a c tl o a db a l a n c i n ga l g o r i t h mi nl o a db a l a n c et e c h n o l o g yo fc l u s t e ri sa l li m p o r t a n tq u e s t i o ni nt h er e s e a r c ho fc a m p u sn e t w o r ka p p l i c a t i o na n dt h ew h o l en e t w o r ka p p l i c a t i o n a i m i n ga tc h a r a c t e r i s t i co fr e q u i r e m e n tc h a n g i n gr a p i d l yi ne n t e r p r i s em a n a g e m e n ts o f t w a r e ，i nt h i sp a p e r , w ei n t r o d u c e , a p p l i c a t i o ni n t e g r a t i o nt e c h n i q u eb a s e do nc a m p u s en e t w o r ki sb e c o m i n gt h em a i n s t r e a mi nt h ed e v e l o p m e n to fe d u c a t i o na d m i n i s t r a t i o ni n f o r m a t i o nm a n a g e m e n ts y s t e m h o w e v e r , i np r e s e n t ,b e t w e e ne d u c a t i o ns o f t w a r e sl a c ko fi n t e r a c t i v e , a n dt h el e v e lo fa p p l i c a t i o ni n t e g r a t i o ni sl o w , t h o s er e a s o nl e a dt os h a r i n ga n dc o m m u n i c a t i n gi n f o r m a t i o ni nc a m p u s ed i f f i c u l t t os o v l et h i sp r o b l e m , w eu s et h ec o n c e p t i o na n dt e c h n o l o g yo fe n t e r p r i s ea p p l i c a t i o ni n t e g r a t i o nt os o l v et h ep r o b l e mo ft h ei n f o r m a t i o ni s o l a t e di s l a n d a n a l y z i n gc a m p u s en e t w o r k , t h ep a p e ri n t r o d u c e san e wm e t h o do fc l u s t e rn o dl o a d ，a n dd i s c u s s e st w ol o a db a l a n c i n ga l g o r i t h m sb a s eo nq u e u i n gt h e o r ya n db a s e do nc u l t u r ea l g o r i t h m ，i nt h ee n d ，1w r o t et h ep r o g r a mo fc l u s t e r s i m u l a t o rt or e a l i z et h o s ea l g o r i t h m i n t h er e s e a r c ho fi n t e r a c t i v ef r a m e w o r ki ne d u c a t i o ni n f o r m a t i o nm a n a g e m e n ts y s t e m ，w ef o u n da st h en u m b e ro ft h es e r v e r si nf r a m e w o r ki n c r e a s i n ga n dt h es c a l eo fs y s t e ml a r g e n i n ga n dt h ed a t ao fc o m m u c a t i o ne x c e s s i n g t h e r ei sn e c e s s a r yt ou s el o a db a l a n c et e c h n o l o g yo fc l u s t e rt os t r e n g t h e np r o c e s s i n gp r o f o r m a n c ei ns e r v e rc l u s t e r i nt h i sp a p e r , r e s e a r c ht h em a i nl o a db a l a n c ea l g o r i t h m , b e c a u s eo ft h ed e f e c t so fr e p r e s e n tm e t h o di nl o a d ；ip r o p o s ean e wm e t h o do fr e p r e s e n ti nl o a d i tn o to n l yc o n s i d e r st h eh a r di n d e xl o a d ，b u ta l s oc o n s i d e r st h es o f ti n d e xl o a d ，t h ec o n t i n u i t ya n df o r s e e b i l i t yj u g e m e n to fi n p u tq u e u e a n dv a l i d a t et h ei m p r o v e m e n to ft h i sr e p r e s e n tm e t h o d a f t e rt h a t ，t h i sp a p e ri n t r o d u c e st w ol o a db a l a n c ea l g o r i t h m sb a s e do nq u e u i n gt h e o r ya n db a s e do nc l u t u r ea l g o r i t h m i nt h el o a db a l a n c ea l g o r i t h mb a s e do nq u e u i n gt h e o r y , a c c o r d i n gt ot h ep r e s e n tl o a ds i t u a t i o na n dt h er e s tp r o c e s s i n ga b i l i t y , c o m p u t et h en e e da v e r a g ea r r i v a l 丘e q m c yo fs e t v e ri nf i x e dt i m ei n t e r v a l s ，a n dt h e ng e tt h ea b s t r a c tt a s ka l l o c a t i o ns t r a t e g y a l s oas i m u l a t i v ee x p e r i m e n ts y s t e mw a sd e v e l o p e d i nt h el o a db a l a n c ea l g o r i t h mb a s e do nc l u t u r ea l g o r i t h m ，if u l l yu s i n gt h et h et h o u g h to fc l u t u r ee v o l u t i o n a r y , a p p l yi n t ol o a db a l a n c ea l g o r i t h m t h ea l l o c a t i o ns t r a t e g yo ft h i sa l g o r i t h mi st h a tp o p u l a t i o ne v o l u t i o na d o p ta d a p t i v ec r o s s o v e ra n dm u t a t i o no p e r a t o r , b e c a u s eo fa c t i v ei nl o n gt i m ea n dm u t i p l y , s o m ee x c e l l e n tc l u t u r ei n f o r m a t i o ni ss a v e di np o p u l a t i o na n ds o m eb a di n f o r m a t i o ni sd i s c a r d t h ec l u t u r ei si m p r o v e dc o n t i n u o u s l y , a n dt h ep o p u l a t i o ni se v o l u t i o nc o n t i n u o u s l y a f t e rs o m eg e n e r a t i o n ，t h e r ew i l lb es o m ee x c e l l e n ti n d i v i d u a l i nt h i sp a p e r , t h e r ei sd e s c r i p t i o na n dd e s i g n i n gi nd e t a i l so fa l g o r i t h mb a s eo nc l u t u r ea l g o r i t h m ，a n das i m u l a t i v ee x p e r i m e n ts y s t e mw a sd e v e l o p e d w ev a l i d a t et h ei m p r o v e m e n ti nt h el o a db a l a n c ea l g o r i t h m k e yw o r d sl o a d b a l a n c e ，q u e u i n gt h e o r y ，c u l t u r ea l g o r i t h m ，c a m p u sn e t w o r ki i i独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。签名：丝! 垫堡日期：年月日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)签名：丝丝跨导师签名：日期：年月日第一章绪论1 1 课题背景第一章绪论在教育技术研究领域，对教学过程和资源的创造、使用、管理是最受关注的问题，而校园网络应用集成领域则是该问题主要的体现之处，参考校园网络应用集成的解决方案对解决教育技术领域的问题很有借鉴意义。校园网的应用除了用于教学、科研、管理、图书情报资料检索外，还担任着校内外信息交流、电子邮件、公告、新闻发布，以及各种公共网络口的访问等任务。由于在网络上传输的信息不只是数字、文字和图形，还会随应用水平的提高，逐步增加语音、活动图像及视频图像等高带宽的应用。因此，网络的建设，尤其是主干网要求高带宽与高速度，在校园网的服务器中应用负载均衡技术不失为一种廉价的解决方案。当前，基于校园网的全校管理模式己成为教育管理信息系统发展的主流，是通过部门管理系统校园网内应用软件之间的互操作、应用集成，实现校内信息的共享与交流。这就急需制定出一整套互操作的规范，使不同厂商开发的教育管理软件能实现跨系统、跨平台的交流。教育管理信息系统互操作规范就是为解决以上问题而提出来的。遵照教育管理信息系统互操作规范的要求，在校园网的构建的过程中我们发现，随着区域和数目的增加、系统规模和通信数据的增大，对w e b 访问的处理能力最有可能成为系统的瓶颈【1 1 。因此有必要在搭建过程中，增强各节点上的吞吐能力。负载均衡集群技术是目前业界对此类需求所提出的比较成熟的解决方案。随着网络技术的进步以及处理器性能的提高，越来越多的用户开始使用相对廉价的以太网把相对便宜的服务器工作站连接起来组成负载均衡集群【2 】，从而以较少的代价获得较高的处理性能。负载均衡集群技术所带来的低成本、高可用性、良好的扩展性、高利用率，是其脱颖而出的重要原因。利用负载均衡集群技术构建的系统通过中央负载均衡服务器 3 】，依据不同节电子科技大学硕士学位论文点的性能及其网络条件在多节点之间分发网络和计算处理负载。在中央负载均衡服务器集群管理器和集群节点之间、各个集群节点之间都有着一种公共关系，通常，我们使用特定的负载均衡调度算法来反应这一关系。1 2 校园网络现状校园网是指校园范围内通过局域网互联的硬件、软件所构成的为学校管理和教育教学服务的应用集成系统，并可通过与广域网的互联实现远距离信息交流和资源共享。概括地讲，校园网是“校校通工程的基础，是为学校师生提供教学、科研和综合信息服务的宽带多媒体网络。它应为学校教学、科研提供先进的信息化教学环境，这就要求：校园网是一个宽带、具有交互功能和专业性很强的局域网络；多媒体教学软件开发平台、多媒体演示教室、教师备课系统、电子阅览室以及教学、考试资料库、网上图书馆等现代教学手段和软件，都可以通过该网络运行工作。当前校园网已经发展到了校际互联、国际互联、静态资源共享、动态信息发布、远程教学和协作工作的阶段。我国各级教育研究部门、软件开发单位、教学设备供应商和各级学校不断开发各种适合在校园网上使用的教育教学软件，这对校园网的建设提出了越来越高的要求。1 2 1 校园网的功能( 1 ) 教学方面利用现代化的技术设备和多媒体的教学手段形象直观地进行教学讲解，能增强学生的学习兴趣和理解水平，从而提高教学质量和学生素质，促进教育水平提高；提供高速、方便的信息交流和资源共享等手段；提供远比书本知识更为广泛的内容，扩大学生与外界的联系，开阔视野，增进交流；发展远程教育，有效克服地域和学校规模的限制，缩短学校之间师资力量的差距。( 2 ) 管理方面统一管理学校资源，如学籍管理、教学资料、图书管理、资产管理等；实现2第一章绪论办公自动化，增强各部门协调能力，提高工作效率。( 3 ) 除上述两方面外，有条件的学校还可以开展其它多种类型的网络应用，如个人接入( 通常用拨号上网) 、互联网( i n t e n l 哟连通等，更充分地发挥网络的优势。1 2 2 校园网络的组成校园网应该建设成为一个以办公自动化、计算机辅助教学、现代计算机校园文化为核心，以现代网络技术为依托，技术先进、扩展性强、能覆盖全校主要楼字的校园主干网络，将学校的各种p c 机、工作站、终端设备和局域网连接起来，并与有关广域网相连，在网上宣传自己和获取i n t e r n e t 网上的教育资源。形成结构合理、内外沟通的校园计算机网络系统，在此基础土建立能满足教学、科研和管理工作需要的软硬件环境，开发各类信息库和应用系统，为学校各类人员提供充分的网络信息服务。按照教育部初、中等学校校园网建设规范的有关规定，校园网络系统主要包括网络设备、服务器、工作站和软件系统等。网络系统硬件设备的选型、施工、安装应符合i s 0 9 0 0 2 标准。网络布线要符合以下标准：主干网及交换设备：大、中型网的主干网应采用光纤通讯和交换设备，子网采用i o i o o m 交换式以太网星型结构，双绞线布线；校园网服务器：应根据网络功能、信息量及校园网实施计划选择网络服务器。一般网络服务器有文件服务器、数据库服务器、视频服务器、信息服务器和光盘塔光盘库等。网络服务器是网络的核心部分，要选用高可靠性、高稳定性、兼容性好并具有良好性能价格比的优质服务器；网络综合布线系统要兼顾校园网的需求和网络技术的发展，采用结构化布线系统设计；操作系统建议采用w i n d o w s n t 、u n i x 或l i n u x 。1 2 3 校园网的瓶颈随着校园网建设工作的开展和深入，许多校园网建设初期的弊端显露了出来，成为校园网运转的瓶颈：3电子科技大学硕士学位论文( 1 ) 目前各软件厂商提供的教育教学软件还不能够共享信息和交换数据，甚至是一个软件厂商提供的多个软件之间也难以实现数据的共享。各教育教学软件之间缺乏必要的互操作能力，成为“信息孤岛 【4 】。用户需要在多个教育教学软件之间重复录入相同数据，生成报表抽取数据困难、费时费力，提高了用户的维护成本；( 2 ) 校园网上运行的各类教育教学软件间缺乏必要的互操作能力，用户无法通过统一的入口、统一的形式获取其所提供的信息和服务，未能形成“综合的教育门户 5 1 。即使简单地将它们组合在一起，其繁复的用户名与口令、及所部署不同位置，都使用户备添困扰。( 3 ) 目前运行在校园网上的很多教育教学软件开发时间比较早，技术比较落后，特别是其网络安全体系极不完善，导致巨大的安全隐患。( 4 ) 当前，无论在企业网、园区网还是在校园网，其网络访问量的发展都超出了过去最乐观的估计，即使按照过去最优配置建设的网络，也很快会感到吃不消。尤其是作为各个网络核心部分的服务器，单一服务器设备己经无法承担如此巨大的数据访问量。怎样高效、廉价、快速的解决这一问题，负载均衡集群技术应运而生。负载均衡( l o a db a l a n c e ) 建立在现有网络结构之上，它提供了一种廉价、有效、透明的方法，来扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性，有效地解决了校园网建设中存在的“核心h u b 6 1 处理能力瓶颈问题。负载均衡有两方面的含义：首先，大量的并发访问或数据流量分担到多台节点设备上分别处理，减少用户等待响应的时间；其次，单个重负载的运算分担到多台节点设备上做并行处理，每个节点设备处理结束后，将结果汇总，返回给用户，系统处理能力得到大幅度提高。负载均衡集群技术建立在现有网络结构之上，它提供了一种廉价有效的方法扩展服务器带宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。4第一章绪论1 3 负载均衡1 3 1 负载均衡的定义负载均衡是由多台服务器以对称的方式组成一个服务器集合，每台服务器都具有等价的地位，都可以单独对外提供服务而无须其他服务器的辅助。通过某种负载分担技术，将外部发送来的请求均匀分配到对称结构中的某一台服务器上，而接收到请求的服务器独立地回应客户的请求。均衡负载能够平均分配客户请求到服务器列阵，借此提供快速获取重要数据，解决大量并发访问服务问题。这种群集技术可以用最少的投资获得接近于大型主机的性能。1 3 2 网络负载均衡的优点第一，网络负载均衡能将传入的请求传播到多达3 2 台服务器上，即可以使用最多3 2 台服务器共同分担对外的网络请求服务。网络负载均衡技术保证即使是在负载很重的情况下，服务器也能做出快速响应；第二，网络负载均衡对外只需提供一个口地址( 或域名) ；第三，当网络负载均衡中的一台或几台服务器不可用时，服务不会中断。网络负载均衡自动检测到服务器不可用时，能够迅速在剩余的服务器中重新指派客户机通讯。这项保护措施能够帮助你为关键的业务程序提供不中断的服务，并可以根据网络访问量的增加来相应地增加网络负载均衡服务器的数量；第四，网络负载均衡可在普通的计算机上实现。1 3 3 负载均衡策略选择负载均衡系统由多台负责完成服务功能的服务器和一个负责调度的负载均衡器组成。当客户端向代表整个系统的负载均衡器发来服务请求时，负载均衡器要5电子科技大学硕士学位论文做的工作就是按照预定的调度算法，从服务器集群中选出当前最合适的服务器，并把服务请求转发到该服务器或向客户端返回服务器定向结果，从而使该服务器处理新到的客户请求。由此可以看出，负载均衡器中的请求调度算法，其设计实现科学与否，直接关系到负载均衡系统设计实现是否成功。调度算法在分布式操作系统、计算机软硬件群集技术、分布式计算等领域中都扮演着举足轻重的作用，因此，研究该算法的人也特别多，也提出了很多算法的实现方案。从目前的研究情况来看，设计一个成功的调整算法r 7 1 ，设计者必须做出三项抉择：一、采用决定式还是采用启发式策略；二、采用集中式控制策略还是采用分布式控制策略；三、是采用最优策略还是采用次优策略。首先，是采用决定式调度算法还是采用启发式调度算法?决定式算法，是在事先准确地知道已到达系统的所有客户请求给系统增加的负载的情况下，将新到达的客户请求调度到服务器集群中的某一台。例如，如果知道当前负载均衡系统中处理各客户请求的进程所需要的和己完成( 或己得到) 的计算时间、磁盘1 0 量、通信量等信息，那么当新到达一个需要已知计算时间、磁盘i o 量、通信量的客户请求时，就能做一次精确的调度了。理论上，可以穷举所有的调度可能，从中选择最佳方案。事实上，通常不可能事先就了解客户请求对系统要求的负载，但是有时候对它作合理的估计是可能的。这些估计可以通过长时间的观察统计得到。有了对各个客户请求的工作负载预计或统计值，我们也可能实现决定式调度算法。而在很多场合，客户请求所需要的负载是完全不可预测的。请求所需要的负载可能取决于由哪个客户发出，或每小时甚至每分钟都在剧烈变化。这使得我们不能够用数学方法事先决定到底把新到达的客户请求发送到哪台服务器上去处理，只能采用特别的方法来处理。这种处理客户请求的方式就叫做启发式调度算法。我们要设计的是比较通用的负载均衡模型，我们所处的时代是复杂分布多用户网络互联时代，我们面向的是因特网上数目不可预测、需求繁多而各不相同、素质各异的庞大客户群，我们要适用于形形色色、要求条件迥异的场合，它们的客户要求大多没有统计规律、变化剧烈、不可预测，这决定了我们不可能采用数学方法精确地对客户请求进行决定式的调度，只能采取启发式调度策略。第二个选择，是采用集中式控制算法还是采用分布式控制算法?所谓集中式控制策略就是在负载均衡系统中设置一台中央控制服务器，我们把它叫做负载均衡器。所有服务器都把自己的工作情况汇总到负载均衡器上去，使它能准确掌握整个系统的负载分布情况。另外，负载均衡器还作为服务器集群6第一章绪论的一个中心调度器。当远程客户端需要服务时，它向负载均衡器提出服务请求。然后，负载均衡器从服务器集群中挑出负载最轻的一台，由它来完成客户请求的功能。而分布式控制策略是，在负载均衡系统中的所有服务器的地位和功能都是平等的。每台服务器都统计自己的负载情况，并将情况广播到系统中其它服务器上去，同时也收集其它服务器发送过来的负载情况，通过汇总了解整个系统的负载分布情况。另外，整个系统没有一台中央调度器，每台服务器都可以直接接受客户请求，然后根据系统负载分布决定是在本地处理请求还是转发到其它服务器去进行处理。一般来讲，集中式控制方式由于采用负载均衡器来负责收集系统负载情况和调度客户请求，它了解的情况比较全面精确，所以所做的调度比较合理。但是，也正是由于负载均衡器的过度集中，使得系统存在单个故障点，不太健壮。另外，当系统扩充到一定规模时，负责收集整个系统负载信息和调度的负载均衡器的工作负担会很重，会成为整个系统的性能瓶项。而采用分布式控制方式，由于每台服务器自己负责收集负载情况和调度客户请求，系统的健壮性就要强得多了。同样，分布式控制方式也有自己的缺点。分布式控制的工作特点决定了各服务器除了要完成处理客户请求外，还必须完成控制功能，这在系统扩充到一定规模时，会给服务器增加很大的额外计算量，系统内部增加很大的通信量。为此，现在大多数分布式控制系统在实现时不可能要求各服务器像集中式控制方式中的负载控制方式合理。我们注意到，在负载均衡模型中，一是可以采用比较高档的服务器负责负载信息采集和汇总，二是负载均衡器只处理客户请求，而这些客户请求一般数目不多、通信量不大。所以使用集中式控制方式时，我们的负载均衡器不会因负担过重而成为系统的性能瓶颈，影响模型的扩充性。至于集中式控制方式中的单个故障点问题，我们亦可以用备份的方式解决。而分布式控制方式，对服务器集群中的每台服务器的处理能力都要求过高，同时系统内部的通信量也比较大。权衡之下，我们还是选择了集中式控制策略。第三个选择，是采用最优式调度算法还是采用次优式调度算法?采用最优式调度算法还是采用次优式调度算法，这个问题其实可以表述为我们是使用最好的调度算法，还是凑合着使用可以接受的算法。无疑，系统采用最优式算法要比次优式算法花费更高的代价。因为，最优式算法要求收集尽可能多、尽可能准确的各服务器的负载信息，使用更复杂的算法精确地比较所有调度方案，然后才能从中选出最优的结果。这在实现上难度比较大，即使实现了代价也比较7电子科技大学硕士学位论文高。所以我们选择次优式调度算法，即采用相对简单的、收集负载代价较低的算法，来选出相对合理的调度方案。另外，由于静态负载均衡算法缺乏应有的灵活性，不能充分发挥集群的优势，完全的依赖静态负载均衡往往是不够的，因为静态负载均衡依赖的是当时的负载状况，而这些负载状况可能己经是过时的了( 比如在短时间内可能有大量的请求发送到该服务器或应用执行对象，或者当一个请求被分配到某一服务器或应用执行对象，在下一请求分配之前，负载分析器来不及刷新负载信息，就会导致大量请求很短时间内发到同一服务器，从而引起h e r d 效应) ，也有可能因为网络或每台机器正在处理的任务不同等原因，导致初始的负载均衡状态发生变化。为保证整个系统高效运行，采用动态负载均衡算法是必然的选择。此外，算法复杂度也是衡量负载均衡算法优劣的一个重要因素。综合上述分析，本文采用集中控制的、次优的启发式动态负载均衡算法，并尽量采用简单的易于实现的负载调度算法。负载均衡涉及几个方面的问题：( 1 ) 负载评价要素( 2 ) 负载的正确测量估计( 3 ) 任务迁移策略。负载均衡算法设计的好坏直接决定了集群在负载均衡上的表现，设计不好的算法，会导致集群的负载失衡。一般的均衡算法主要任务是决定如何选择下一个集群节点，然后将新的服务请求转发给它。有些简单均衡方法可以独立使用，有些必须和其它简单或高级方法组合使用。而一个好的负载均衡算法也并不是万能的，它一般只在某些特殊的应用环境下才能发挥最大效用。因此在考察负载均衡算法的同时，也要注意算法本身的适用面，并在集群部署的时候根据集群自身的特点进行综合考虑，把不同的算法和技术结合起来使用。在综合几种负载均衡算法的基础上，本文提出了两种基于反馈的自适应负载均衡算法，其基本思想是：根据负反馈的基本原理，结合当前各个服务器的负载情况，作出任务分配策略，并进行任务分配。在进行负载调度时，总是优先把任务分配给负载最轻的服务器，从而动态适应负载的变化。采用自适应负载均衡算法后的系统，既充分利用各节点服务器资源，又保证了对任务的及时响应。在集群内各节点服务器硬件配置不同的情况下，该负载均衡算法更显出其独特的优势。算法基本原理框图如图所示。8第一章绪论新的任务请求- - 图1 - 1 负载均衡算法基本原理框图根据图所示，采集器接收到任务请求，并综合负载服务器反馈回来的负载信息，进行负载决策，以决定当前分配给相应服务器的任务量。1 4 本文的章节安排本论文内容安排如下：第一章，绪论，介绍课题的背景、校园网络现状、负载均衡相关概念以及作者的主要工作。第二章，对常用负载均衡算法相关理论的回顾和分析。第三章，提出一种改进的集群节点负载表示方法。第四章，在自适应负载均衡基础上，提出一种综合性能较好的基于排队理论的负载均衡算法。第五章，在自适应负载均衡基础上，提出一种基于文化算法的负载均衡算法。第六章，全文总结和未来工作预测。9电子科技大学硕士学位论文第二章常用负载均衡算法相关理论和研究典型的动态负载平衡算法可分为三类：1 、发送者启动算法( s e n d e r - i n i t i a t e d ) ，目前这种方法研究得最多【8 , 9 , 1 1 , 1 7 , 1 8 , 2 2 1 。负载分配活动由超载结点( 发送者) 启动，它力图找到一个轻载结点( 接收者) ，并与其均衡负载。其性能在轻负载到中等负载时较优。在系统轻载时，发送者能够较容易地找到接收者，因而该算法比较稳定而有效；但在系统重载，该算法会引起系统的不稳定，因为此时发送者不仅不容易找到接收者，而且大量的查询开销还会增大系统的负载。2 、接收者启动算法( r e c e i v e r - l n i t i a t e d ) ，与发送者启动算法相反，该算法由接收者启动负载的分配【1 0 二5 4 3 1 ，即当一个结点变为接收者时，它主动寻找重载结点，以均衡负载。在系统重载的情况下，由于多数结点处于高载，负载分配活动将趋于微弱，因此不会引起系统的不稳定，优于发送者启动算法。但由于接收者找到发送者时，任务可能已经启动，因此需要支持进程迁移，需要付出一定代价。在轻负载情况下，接收者启动算法的性能将会降低。3 、对称启动算法( s y m m e t r y - i n i t i a t e d ) ，对称启动算法是前两种算法的结合【9 】，发送者发动的适用于系统低负载情况，而接收者发动的适用于系统高负载情况。使用何种策略根据平均负载值，以及相关的阈值进行切换。目前，常用的负载分配算法主要包括轮循算法、最少连接算法、目的地址哈希散列( h a s h i n g s c h c x l u l i n g ) 算法和随机( r a n d o m ) 算法等。2 1 轮循算法轮转调度皿0 1 m dr o b i ns c h e d u l i n g ) 1 1 2 , 1 3 】，是以轮叫的方式依次调度不同的服务器，对所有实际服务器平等对待，一视同仁【1 4 1 。1 0第二章常用负载均衡算法相关理论和研究图2 - 1 轮循算法流程图轮循调度算法属于静态负载分配算法，假设所有服务器处理性能均相同，不管服务器的当前连接数和响应速度。轮循算法把每个来到的请求送给它表中的下一个服务器。这样，在一个有三台服务器的集群中( 服务器a ，b ，c ) ，请求1 发送给服务器a ，请求2 发送给服务器b ，请求3 发送给服务器c ，请求4 发送给服务器a 。如此不断进行着服务器循环。该算法相对简单，不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化比较大时，轮循调度算法容易导致服务器间的负载不平衡。因此，虽然算法简单易行，但是算法的有效性差、并行性低，对系统的性能没有多大的提高。电子科技大学硕士学位论文2 2 最少连接算法最少连接算法将网络连接连向当前建立连接数目最少的服务器上。这是一种动态分配算法，因为这需要每台服务器动态地统计当前被激活的连接。由于一台虚拟服务器管理着一系列具有相同服务的服务器，最少连接算法适于请求消息很多的平滑分配。虚拟服务器会将请求消息分配到具有最少活动连接的服务器上。表面上，最少连接算法在服务器之间具有各种不同的处理能力的情况下也可以工作得很好，因为最快的服务器将获得最多的网络连接。但事实上，由于t c p的t i m e 的r r 状态的存在，该算法并不能尽人意。t c p 的t i m e s 的i t 通常是设为两分钟。在这两分钟之内，一个繁忙的服务器经常会收到数以千计的连接。例如，服务器a 的处理能力是服务器b 的两倍，则服务器a 将处理数以千计的请求并将它们保持在t c p 的t i m e e s 的i t 状态，但服务器b 只能将这数以千计的连接慢慢完成。所以，最少连接算法并不能将具有各种不同处理能力的服务器之间的负载均衡得很好。2 3 目的地址哈希散列算法目标地址散列算法( d e s t i n a t i o n h a s h i n g ，简称d h 算法) 将请求的目标i p 地址，作为散列键( h a s h k y e ) ，通过一单射不可逆的h a s h 函数，从静态分配的散列表中找出对应的集群节点，若该集群节点是可用的且未超载，将请求发送到该集群节点，否则返回空。目标地址散列法在前述几类负载均衡调度算法不是很有效时会显示出特别的威力。例如，在前面提到的u d p 会话的情况下，由于轮转法和前述其他几类算法，无法识别出会话的起止标记，会引起应用混乱。而采取基于数据包目标p 地址的哈希映射可以在一定程度上解决这个问题：将具有相同目标口地址的数据包发给同一集群节点，这使得基于高层会话的事务可以以适当的方式运行。1 2第二章常用负载均衡算法相关理论和研究2 4 随机算法首先需要明确的一点是，计算机系统生成的随机数永远是伪随机。随机算法( r a n d o m ，简称r 算法) 赋给各个集群节点一个由伪随机算法产生的值，具有最小或最大随机数的群节点最有优先权。随机算法实际上相当于“无偏见的给集群节点产生权值，每个机器都有可能获得最大的优先级【1 5 】。因此和前面介绍的轮循算法一样，在集群节点性能相同或近似的环境中，这种算法取得的负载均衡效果比较好。2 5 动态反馈负载均衡算法在上面的几种负载均衡算法中，有的算法属于静态的均衡算法，有的属于动态的均衡算法，虽然有的算法中考虑了服务器的实时负载状态信息，但是，算法中仍然没有考虑到不同类型的请求所耗用的服务器资源和网络带宽不同，比如，单纯的h t m l 请求和大文件的f t p 下载的耗用情况是完全不同的，没有考虑不同类型的请求所要求的服务质量不同，不能实现按不同类型请求优先级进行负载分配。可见，改进的负载均衡算法应区分不同类型的请求和不同请求的q o s ，考虑服务器的实时负载和响应情况，不断调整服务器间处理请求的比例，来避免有些服务器超载时依然收到大量请求，从而提高整个系统的吞吐率。动态反馈负载均衡算法的工作环境如图：电子科技大学硕士学位论文目2 - 2 动态反馈负载均衡算法的工作环境图2 2 显示了该算法的工作环境，在负载调度器上运行监听守护进程来监视和收集各个服务器的负载信息。该进程可根据多个负载信息算出一个综合负载值。该进程将各个服务器的综合负载值和当前权值算出一组新的权值，若新权值和当前权值的差值大于设定的闽值，再将该服务器的权值设置到内核中的分配处理模块中，而在内核中连接调度采用加权最小连接调度算法按请求类别的优先级进行请求分配。通过实时采集各服务器节点的实时负载信息，综合各节点的负载权值和负载闻值，结合请求类别的优先级将当前最需要调度的请求( 优先级最高) 调度到当前最适合负载( 在集群中综合负载最轻) 的服务器。2 6 本章小节在本章中，我们对服务器集群系统中常用的负载均衡算法进行了研究，如：轮循算法，最少连接算法，目的地址哈希散列算法，随机算法以及动态反馈负载均衡算法等。除以上各种算法外，还有基于局部性的晟少链接算法( b 咖l i y - b a s c dl e 捌第二章常用负载均衡算法相关理论和研究c o n n e c t i o n ，简称l b l c 算法) 、带复制的基于局部性最少链接算法( l o e a l i t y - b a s e dl e a s tc o n n e e f i o n 、7 l ，i t l lr e p l i c a t i o n ，简称l b l c r 算法) 、源地址散列算法( s o u r c e h a s h i n g ，简称s h 算法) 、最短期望延迟算法( s h o r t e s te x p e c t e dd d a y ，简称s e d 算法) 、无须队列等待算法( n e v e rq u e u e ，简称n q 算法) 等其它负载均衡调度算法，本文不作详细研究。通过研究，发现他们的思想和算法都很简单，在某些特定的场合下可以获得较好的负载均衡效果。但其共同的特点就是各种表示简单，适用于比较简单的应用场合；对于较为复杂和要求较高的集群系统，他们就会暴露出其致命的缺陷，而导致负载均衡效果不佳。接下来，本文将提出一种改进的集群系统中集群节点的负载表示方法和两种新型的负载均衡算法。1 5电子科技大学硕士学位论文3 1背景第三章一种改进的服务节点负载表示研究随着网络的不断发展和完善，各种计算机应用也随之繁荣。从而用户的网络任务请求也急剧增加，网络和服务器的负荷大幅度增加，在这种情况下，负载均衡在网络中起到的作用将越来越大，且越来越重要。而一种好的集群节点的负载表示是负载均衡系统能发挥更好作用的基本条件。在以往的各种负载均衡算法中，都曾定义过集群系统中集群节点的负载表示方法。而这些方法都主要侧重于对当前时刻的负载值的获取，而缺乏使用该数值对服务器节点将来的一小段时间内的负载做出连续性分析和预测性分析。本章将针对该问题，提出一种改进的负载均衡服务节点的负载表示。3 2影响负载均衡的因素分析在集群系统中，有很对因素都可以影响整个系统负载均衡的效果，其中影响负载均衡的一个关键因素就是节点的资源使用状态。由于系统的最终目标是实现负载均衡，及时、准确地把握节点负载状况，并根据各个节点当前的资源使用状态动态调整负载均衡的流量分布，这样自适应负载均衡算法算是一种比较好的解决方案，而这也正是自适应负载均衡算法考虑的一个关键问题。为了能动态自适应地进行网络请求的负载均衡，必须使用消息机制收集丰富的负载信息。严格地讲，所有的调度算法都要求系统中各服务器能测量自己的负载，并且能够通告其它服务器自己的负载信息。然而，测量负载并不是件简单的工作。在实现负载均衡调度算法时，遇到的第一个问题就是以什么作为衡量负载的标准。最早人们使用系统中的进程数目作为负载的衡量标准。但是，在一个多用户多进程的操作系统( 如u n i x ) 当中，即使它很空闲，仍有许多进程在运行，如u n i x 以中的t d n e t 的后台服务进程、w i n d o w s 管理器等等。所以，进程数基本不1 6第三章一种改进的服务节点负载表示研究能表示系统当前负载状况。作为改良，人们用处于运行状态和就绪状态的进程数目来衡量负载。这在一定程度上是合理的，毕竟处于运行或就绪状态的进程，即使它是后台进程，也会给该服务器增加负担。但即使是处于运行或就绪状态的进程，它耗费的服务器处理能力也是不尽相同的，也就是说它们的执行强度可以不同。例如，在服务器上很多后台服务进程仅仅是周期性地唤醒，查看是否有感兴趣的事情发生，如果没有就继续睡眠。它们实际上不增加系统多少负担。后来，人们又提出使用c p u 的使用率作为衡量标准。使用c p u 使用率的确能比较准确的反映当前系统计算能力的使用情况，但是这仅仅是反映了系统负载情况的一部分。目前比较一致的看法是，衡量系统负载情况应该包括服务器c p u的处理能力、自由内存大小、网络传输能力和磁盘输入输出能力四个方面的使用情况，如果是特殊场合特殊应用，还要测量对系统性能影响很大的外设的使用情况。在校园网络应用中同样存在众多的因素，对自适应负载均衡算法的设计与性能有着非常重要的影响。在负载均衡算法的设计中，周期性地从各个节点中收集以下参数：( 1 ) c p u 使用率c p u n i o ( 2 ) 内存使用率m e m n i ( 3 ) 当前进程数p r o c e s s n i( 4 ) 当前磁盘输入输出能力d i s k n i 随着节点负载变化，系统对各个节点的负载值不断调整。根据节点运行时各方面的参数计算出动态负载值，负载均衡算法依据计算出的动态负载值的大小有策略地调整各节点负载。采用动态负载值的目的是要正确反映节点负载的状况，以预测节点将来可能的负载变化。对于不同的系统应用，上述各个参数的重要程度也有所不同。对于收集动态负载值的周期值设置，虽然较短的周期可以更确切地反映各个节点的，但会给集群各节点带来负担，增加不必要的网络流量，造成各节点负载信息出现剧烈的抖动。因此，一方面要适当调整收集负载信息的周期