基于SDN和改进CSA算法的多作业集群的负载均衡算法.pdf
《基于SDN和改进CSA算法的多作业集群的负载均衡算法.pdf》由会员分享,可在线阅读,更多相关《基于SDN和改进CSA算法的多作业集群的负载均衡算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、计算机与现代化JISUANJI YU XIANDAIHUA2023年第11期总第339期收稿日期:2022-12-12;修回日期:2023-01-12基金项目:国家自然科学基金资助项目(61572253)作者简介:王重阳(1996),男,湖北黄冈人,硕士研究生,研究方向:分布式计算,软件定义系统,E-mail:;庄毅(1956),女,江苏南京人,教授,博士生导师,研究方向:网络安全,可信计算,分布式计算,E-mail:。文章编号:1006-2475(2023)11-0028-080引言随着多作业集群系统的服务数量与日俱增,实现负载均衡是集群系统的一个重要目标,它降低了一些节点因过载而导致故障的
2、概率同时也避免了一些节点因为空闲而造成资源的浪费,为了实现这一点,系统将多个任务分配给一个或多个同时运行的虚拟机(Virtual Machine,VM),确保在 VM上正确分配工作负载,使得 VM较少受到过载/欠载的影响。负载均衡可以提高QoS(Quality of Service)指标,包括响应时间、成本、吞吐量、性能和资源利用率,工作负载的有效平衡有助于更高的用户满意度和更好的资源分配,同时在集群系统中,应用负载平衡策略可减少发送和接收数据的延迟1-2,如果系统一直处于过载的状态,会影响系统的服务性能,导致无法为用户提供高质量的服务。因此,高效的负载均衡策略对于集群系统的高可用性以及良好的
3、服务性能有着至关重要的作用。由于虚拟机的分配资源不同,在处理用户请求的不同任务并使集群系统保持负载均衡时仍然具有挑战性,尤其是在异构环境下,系统中节点配置、资源类型以及任务的多样性,使得负载均衡变得更加困难。造成这种情况的原因之一是现有策略考虑的任务因素有限,大多数研究人员不考虑任务优先级,这是任务调度中的一个关键因素,考虑不周将导致诸如任务总完成时间增加或者任务拒绝和延迟的数量增加等问题3-7。另外大多数研究人员只关注少数方面。例如,为了增强负载均衡但考虑很少的任务调度参数,只考虑几个指标来提高系统整体性能,因为不正确的任务调度会导致主机中的负载不均衡5-6,8-9,还有虽然采用了新方法5,
4、10来改进系统的负载均衡,但是却没有考虑到违反SLA(Service Level Agreement)的后基于SDN和改进CSA算法的多作业集群的负载均衡算法王重阳,庄毅(南京航空航天大学计算机科学与技术学院,江苏 南京 211106)摘要:为了实现更加高效的任务调度,减少系统的任务总完成时间以及保证可靠的服务性能,提高多作业集群系统的稳定性、灵活性以及高可用性,本文提出基于SDN和SOS-ICSA(Symbiotic Organisms Search and Improved Crow SearchAlgorithm)的负载均衡算法来改善多作业集群管理系统的调度问题。为了提高CSA算法收敛速
5、度和解决方案的质量,对CSA算法加入局部优化策略,还利用SOS算法对CSA的2个控制参数进行自适应优化,帮助CSA找到最佳或者接近最优的解决方案。该算法还评估虚拟机的可靠性并且结合SDN,进一步提升系统性能和灵活性;对比仿真实验结果表明,本文提出的算法降低了系统的不平衡度,减少了任务的总执行时间,提高了资源利用率。关键词:软件定义网络;改进的乌鸦搜索算法;多作业集群;负载均衡中图分类号:TP311文献标志码:ADOI:10.3969/j.issn.1006-2475.2023.11.005Load Balancing Algorithm of Multi-job Cluster Based o
6、n SDN and Improved CSA AlgorithmWANG Chong-yang,ZHUANG Yi(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)Abstract:In order to achieve more efficient task scheduling,reduce the total task completion time of the system,ensure reliable
7、service performance,and improve the stability,flexibility,and high availability of multi-job cluster systems,this paper proposes a method based on SDN and SOS-ICSA(symbiotic organisms search and improved crow search algorithm)load balancingstrategy to improve the scheduling problem of the multi-job
8、cluster management system.In order to improve the convergencespeed of the CSA algorithm and the quality of the solution,a local optimization strategy is added to the CSA algorithm,and theSOS algorithm is used to solve the two problems of CSA.Adaptive optimization of each control parameter helps CSA
9、find the bestor near-optimal solution.The algorithm also takes into account the reliability of the virtual machine and combines with SDN tofurther improve the system performance and flexibility.The experimental results show that the algorithm proposed in this paper reduces the imbalance of the syste
10、m,reduces the total execution time of tasks,and improves resource utilization.Key words:software defined network;SOS-ICSA;multi-job cluster;load balancing2023年第11期果,任务仍然分配给该VM,即使VM无法在任务截止时间内完成该任务,随着任务请求数量的增加,如果任务没有及时分配给合适的VM,或者CPU没有充分利用或不足以处理请求,系统可能会出现更多问题,导致系统负载不均衡进而影响系统性能以及用户体验。为了解决这些问题,有必要考虑QoS因素
11、并提供一种有效的负载均衡策略来提高系统的服务性能。鉴于此,本文提出一种基于软件定义网络(Software-Defined Network,SDN)11和 SOS-ICSA 的负载均衡策略,可以减少任务拒绝率,提高系统吞吐量和资源利用率,进而提高系统的可靠性、稳定性以及灵活性。本文的主要研究工作如下:1)任务调度过程中考虑虚拟机的可靠性,降低了任务执行失败的概率,减少任务迁移的次数,同时结合SDN的优点,提高系统的可扩展性和灵活性。2)对 乌 鸦 搜 索 算 法(Crow Search Algorithm,CSA)12进行优化,通过组合突变策略(CombinedMutation Strategy
12、,CMS)13和精英方法,对局部搜索进行优化,加快算法收敛速度,避免陷入局部最优的问题,降低了任务选择不合适虚拟机的概率,同时引入个体上限策略(Personal Upper Bound Strategy,PUBS)14,对任务调度约束问题进行评估,减少了任务拒绝率,提高了系统服务性能和用户满意度。3)利 用 共 生 生 物 算 法(Symbiotic OrganismsSearch,SOS)15与CSA的控制参数进行自适应优化来提高算法性能,加快任务搜索速率,与其他CSA混合算法相比,由于SOS算法没有任何控制参数,极大降低了算法复杂性。1相关工作目前主要的负载均衡策略分为3种:静态负载均衡策
13、略、动态负载均衡策略以及与群体智能算法相结合的负载均衡策略。Shanthan等人7提出了一种基于资源的负载平衡 Min-Min(RBLMM)算法,旨在减少任务总完成时间并且平衡 VM 上的工作负载。与传统 MM 算法相比,任务总完成时间更少,但是它没有考虑任务的优先级和任何QoS相关的重要参数,例如任务的截止时间。Ali 等人16提出了一种资源感知的 Min-Min 方法,该算法提供了一个矩阵来存储任务,同时考虑到任务的完成时间和执行时间,但是这个方法在任务分配过程中没有考虑VM的实时负载。静态负载均衡策略执行任务分配时很少或根本不考虑虚拟机的计算能力以及可用空间大小,一台服务器可能同时处理大
14、量任务。然而,该算法开销小,易于实现,适用于同构服务器但不足以适应负载的动态变化。Chen等人17提出了一种支持服务器运行状态的负载均衡算法,该算法计算与网络流量、CPU利用率和内存利用率、服务一致的综合负载,结果表明,该算法在分配用户和均衡CPU利用率方面优于随机或轮询算法。Saifullah等人18提出了一种基于EHLBO的负载分配策略,该策略考虑到服务器健康状况。EHLBO使用每个服务器的CPU占用率和可用内存空间来选择目标服务器。Du等人19提出了一种动态负载平衡(DLB)算法,该算法利用当前负载状态和每个服务器的处理能力来选择目标服务器来处理请求,但是定期收集每台服务器上的实时负载会
15、导致大量开销,影响系统性能。动态负载均衡策略考虑到当前节点的负载状态和网络带宽的变化,可以更好地实现集群的负载均衡。但随着任务调度的约束越来越多,调度问题变得越来越复杂,因此需要结合群体智能算法实现任务更高效的分配,在保证系统有较好的服务性能的同时使系统具有高可用性,但群体智能算法由于存在容易陷入局部最优、收敛速度太快等问题,导致出现任务分配不合理、任务总完成时间增加等情况,最终影响系统的负载均衡。Nair等人20提出了LBA-HB负载均衡策略,结合蜜蜂算法对负载均衡策略进行改进,分配任务时虚拟机负载将更新,并通知其他任务。基于先到先服务(FCFS)算法将任务放入等待队列,任务将分配给负载最小
16、的虚拟机,该算法提高了任务的响应时间,但是并没有考虑任务的优先级。Wang等人21提出了IMPSO算法,优化了任务完成时间和执行任务的成本之间的权衡,该算法最大限度地减少了陷入局部优化的概率,提高了 PSO 算法的收敛速度。Kousalya 等人22提出了一种新的虚拟机任务分配模型,与FCFS和PSO方法相比,所提出的ICSA算法减少了任务总完成时间、等待时间及响应时间。Abualigah等人23通过基于精英的差分进化引入了新的混合蚁狮优化算法,用于解决数据中心中的多目标任务调度问题。该方法通过采用基于精英的差分进化作为局部搜索方法进行了改进,以增强探索能力并避免提供陷入受限最优解。Srich
17、andan等人24通过利用混合方法进行任务调度,该方法结合了遗传算法(GA)和细菌觅食(BF)算法的所需特征。所提出的混合算法减少了任务完成时间和能源消耗。这种方法的缺点是任务评估需要更多时间并且性能较差。综上所述,现有的针对数据中心的负载均衡策略存在以下几个问题:1)对任务优先级、截止时间以及实时负载状态等没有考虑全面,导致任务拒绝率的提高以及任务需要重新分配和迁移的概率的提高,降低了系统资源利用率以及增加了任务的总完成时间;2)群体智能算法进行混合时,虽然增强了任务调度时的搜索能力以及避免了陷入局部最优解,但是混合之后导致控制参数增加,提高了算法的复杂性;3)几乎没有考虑调度过程中虚拟机的
18、可靠性,导致作业无法按时执行等问题,最终影响集群系统的服务性能以及用户满意度。2任务调度系统模型与问题建模多作业集群系统中任务调度问题定义为:将各种优先级不同和大小不同的任务根据某些合适的策略分配给VM,使得所有的任务可以在规定的执行周期内完成,减少SLA违规次数,避免由于调度不当引起王重阳,等:基于SDN和改进CSA算法的多作业集群的负载均衡算法29计算机与现代化2023年第11期的资源利用不足(underloaded)或者过度利用(overloaded)的问题,保证资源的不浪费以及较高的服务性能,尽量减少任务迁移次数和降低因过载而导致VM故障的概率,最终提高系统的可靠性、稳定性以及高可用性
19、。2.1系统模型如图1所示,用户提交作业后,作业调度器将会根据作业的优先级和截止时间为任务排序,高优先级和较早截止时间的作业将会先插入到任务队列中,然后根据任务顺序优先出队进行任务调度和分配。任务调度过程中,将利用SOS-ICSA调度策略为任务选择最优的VM,SDN控制器在此期间,将会实时监控网络带宽,使网络带宽得到更有效的利用,任务的中间执行数据将会保存到共享存储中。图1系统模型图2.2任务调度问题建模系统由n台VM组成,C=vm1,vm2,.,vmn,其中vmj表示第j台虚拟机,待处理的任务(Task)有m个,T=task1,task2,.,taskm,其中taski表示第i个任务,每个任
20、务有一组参数,表示为 taski=tLeni,tDli,其中tLeni表示taski的大小,tDli表示taski的截止时间。1)任务执行时间。vmj的计算速率vmsrj计算方法为:nj=1vmsrj=nj=1vmmipsjnj=1vmcpunumj(1)其中,vmmipsj表示 vmj的单个 CPU每秒可运行百万条指令,vmcpunumj表示vmj的CPU数量。taski在vmj上预期执行时间EETi,j计算方法如式(2)所示:EETi,j=mi=1tLeninj=1vmsrj(2)当vmj出现过载的情况,需要对该节点上的任务taski进行迁移,这个过程需要一些任务传输时间。为了减少任务的完
21、成时间,就要提高任务的传输速度TSi,j,进而减少任务传输时间,TSi,j的计算方法如式(3)所示:TSi,j=mi=1tLeninj=1vmbwj(3)其中,vmbwj表示vmj的网络带宽大小。任务传输时间TTi,j是在虚拟机之间传输任务所消耗的时间,计算方法如式(4)所示:TTi,j=mi=1tLenitasktsi,j(4)因此taski在vmj的执行时间ETi,j为预期任务执行时间和任务转移时间的总和,计算方法如式(5)所示:ETi,j=(EETi,j+TTi,j)nj=1DVi,j(5)其中,DVi,j计算方法如式(6)所示:DVi,j=1,如果taski分配给vmj0,otherw
22、ise(6)2)任务总完成时间。MSi,j表示一系列任务taski在vmj上完成的时间,计算方法如式(7)所示:MSi,j=maxETi,j(7)从式(7)可以推断出MSi,j越小,任务的总完成时间就越短,说明系统在一定时间内处理的任务量更多,系统吞吐量更大。3)资源利用率。该系统的另一个优化目标则是提高vmj的资源利用率Ruj,Ruj的计算方法如式(8)所示,平均资源利用率Ravguj的计算方法如式(9)所示:Ruj=ETi,jMSi,j(8)Ravguj=nj=1Rujn(9)vmj的负载vmloadj取决于当前正在执行的任务数量,计算方法如式(10)所示:vmloadj=xi=1tLen
23、ivmsrj,i=1,2,x,1xm(10)4)系统的不平衡度。DI表示系统的不平衡度,计算方法如式(11)所示:DI=nMSi,j-minETi,jnj=1ETi,j(11)5)任务拒绝率。每个任务 taski在 vmj上的任务结束时间表示为FTi,j,初始化为0,如式(12)所示,FTi,j由vmj上前一个任务taski-1的结束时间和taski的预期执行时间决定,计算方法如式(13)所示,FTi,j必须满足式(14)条件,即结束时间不能超过tDli:FT0,j=0(12)FTi,j=FTi-1,j+mi=1DVi,jEETi,j(13)FTi,jtDli(14)对于每个要被分配的task
24、i,如果选定的vmj不满足式(15),则该任务会被拒绝在其上执行,系统会根据负载均衡策略继续选择其余较优的 vmj+1,任务拒绝率越低,在特定时间段内完成的任务数量、用户满意度以及系统的 QoS越高,taskreject_rate计算方法如式(15)所示:taskreject_rate=taskrejectedtasktotal(15)其中,taskrejected表示被拒绝的任务数量,tasktotal表示任务总数。SOS-ICSA调度策略Open vSwitchSDN控制器共享存储用户作业调度器任务队列服务器1服务器nvm1vm2vm3vmj-2vmj-1vmj302023年第11期2.3
25、VM的可靠性评估可靠性是保证多作业集群系统可以提供可靠服务的必要条件,vmj由多种资源组成,因此vmj的可靠性vmrej取决于每类资源的可靠性,本文主要考虑磁盘和RAM的可靠性以及可靠性因子tasksc_fci,j,tasksc_fci,j表示 taski在 vmj成功执行的次数越多,vmj的可靠性越大,据文献 25,磁盘和RAM的可靠性分别为0.93和0.997,用vmre_diskj和vmre_RAMj来表示,本文将用以下评估策略实现vmrej的动态更新,具体步骤如下:步 骤 1 初 始 化 vmj的 vmre_diskj=0.93,vmre_RAMj=0.997,tasksc_fci,j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 SDN 改进 CSA 算法 作业 集群 负载 均衡
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。