基于SDN和改进CSA算法的多作业集群的负载均衡算法.pdf

计算机与现代化JISUANJI YU XIANDAIHUA2023年第11期总第339期收稿日期：2022-12-12；修回日期：2023-01-12基金项目：国家自然科学基金资助项目（61572253）作者简介：王重阳（1996），男，湖北黄冈人，硕士研究生,研究方向：分布式计算，软件定义系统，E-mail：；庄毅（1956），女，江苏南京人，教授，博士生导师，研究方向：网络安全，可信计算，分布式计算，E-mail：。文章编号：1006-2475（2023）11-0028-080引言随着多作业集群系统的服务数量与日俱增，实现负载均衡是集群系统的一个重要目标，它降低了一些节点因过载而导致故障的概率同时也避免了一些节点因为空闲而造成资源的浪费，为了实现这一点，系统将多个任务分配给一个或多个同时运行的虚拟机（Virtual Machine，VM），确保在 VM上正确分配工作负载，使得 VM较少受到过载/欠载的影响。负载均衡可以提高QoS（Quality of Service）指标，包括响应时间、成本、吞吐量、性能和资源利用率，工作负载的有效平衡有助于更高的用户满意度和更好的资源分配，同时在集群系统中，应用负载平衡策略可减少发送和接收数据的延迟1-2，如果系统一直处于过载的状态，会影响系统的服务性能，导致无法为用户提供高质量的服务。因此，高效的负载均衡策略对于集群系统的高可用性以及良好的服务性能有着至关重要的作用。由于虚拟机的分配资源不同，在处理用户请求的不同任务并使集群系统保持负载均衡时仍然具有挑战性，尤其是在异构环境下，系统中节点配置、资源类型以及任务的多样性，使得负载均衡变得更加困难。造成这种情况的原因之一是现有策略考虑的任务因素有限，大多数研究人员不考虑任务优先级，这是任务调度中的一个关键因素，考虑不周将导致诸如任务总完成时间增加或者任务拒绝和延迟的数量增加等问题3-7。另外大多数研究人员只关注少数方面。例如，为了增强负载均衡但考虑很少的任务调度参数，只考虑几个指标来提高系统整体性能，因为不正确的任务调度会导致主机中的负载不均衡5-6，8-9，还有虽然采用了新方法5，10来改进系统的负载均衡，但是却没有考虑到违反SLA（Service Level Agreement）的后基于SDN和改进CSA算法的多作业集群的负载均衡算法王重阳，庄毅（南京航空航天大学计算机科学与技术学院，江苏 南京 211106）摘要：为了实现更加高效的任务调度，减少系统的任务总完成时间以及保证可靠的服务性能，提高多作业集群系统的稳定性、灵活性以及高可用性，本文提出基于SDN和SOS-ICSA（Symbiotic Organisms Search and Improved Crow SearchAlgorithm）的负载均衡算法来改善多作业集群管理系统的调度问题。为了提高CSA算法收敛速度和解决方案的质量，对CSA算法加入局部优化策略，还利用SOS算法对CSA的2个控制参数进行自适应优化，帮助CSA找到最佳或者接近最优的解决方案。该算法还评估虚拟机的可靠性并且结合SDN，进一步提升系统性能和灵活性；对比仿真实验结果表明，本文提出的算法降低了系统的不平衡度，减少了任务的总执行时间，提高了资源利用率。关键词：软件定义网络；改进的乌鸦搜索算法；多作业集群；负载均衡中图分类号：TP311文献标志码：ADOI：10.3969/j.issn.1006-2475.2023.11.005Load Balancing Algorithm of Multi-job Cluster Based on 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 reliableservice 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 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 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 system，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因素并提供一种有效的负载均衡策略来提高系统的服务性能。鉴于此，本文提出一种基于软件定义网络（Software-Defined Network，SDN）11和 SOS-ICSA 的负载均衡策略，可以减少任务拒绝率，提高系统吞吐量和资源利用率，进而提高系统的可靠性、稳定性以及灵活性。本文的主要研究工作如下：1）任务调度过程中考虑虚拟机的可靠性，降低了任务执行失败的概率，减少任务迁移的次数，同时结合SDN的优点，提高系统的可扩展性和灵活性。2）对 乌 鸦 搜 索 算 法（Crow Search Algorithm，CSA）12进行优化，通过组合突变策略（CombinedMutation Strategy，CMS）13和精英方法，对局部搜索进行优化，加快算法收敛速度，避免陷入局部最优的问题，降低了任务选择不合适虚拟机的概率，同时引入个体上限策略（Personal Upper Bound Strategy，PUBS）14，对任务调度约束问题进行评估，减少了任务拒绝率，提高了系统服务性能和用户满意度。3）利 用 共 生 生 物 算 法（Symbiotic OrganismsSearch，SOS）15与CSA的控制参数进行自适应优化来提高算法性能，加快任务搜索速率，与其他CSA混合算法相比，由于SOS算法没有任何控制参数，极大降低了算法复杂性。1相关工作目前主要的负载均衡策略分为3种：静态负载均衡策略、动态负载均衡策略以及与群体智能算法相结合的负载均衡策略。Shanthan等人7提出了一种基于资源的负载平衡 Min-Min（RBLMM）算法，旨在减少任务总完成时间并且平衡 VM 上的工作负载。与传统 MM 算法相比，任务总完成时间更少，但是它没有考虑任务的优先级和任何QoS相关的重要参数，例如任务的截止时间。Ali 等人16提出了一种资源感知的 Min-Min 方法，该算法提供了一个矩阵来存储任务，同时考虑到任务的完成时间和执行时间，但是这个方法在任务分配过程中没有考虑VM的实时负载。静态负载均衡策略执行任务分配时很少或根本不考虑虚拟机的计算能力以及可用空间大小，一台服务器可能同时处理大量任务。然而，该算法开销小，易于实现，适用于同构服务器但不足以适应负载的动态变化。Chen等人17提出了一种支持服务器运行状态的负载均衡算法，该算法计算与网络流量、CPU利用率和内存利用率、服务一致的综合负载，结果表明，该算法在分配用户和均衡CPU利用率方面优于随机或轮询算法。Saifullah等人18提出了一种基于EHLBO的负载分配策略，该策略考虑到服务器健康状况。EHLBO使用每个服务器的CPU占用率和可用内存空间来选择目标服务器。Du等人19提出了一种动态负载平衡（DLB）算法，该算法利用当前负载状态和每个服务器的处理能力来选择目标服务器来处理请求，但是定期收集每台服务器上的实时负载会导致大量开销，影响系统性能。动态负载均衡策略考虑到当前节点的负载状态和网络带宽的变化，可以更好地实现集群的负载均衡。但随着任务调度的约束越来越多，调度问题变得越来越复杂，因此需要结合群体智能算法实现任务更高效的分配，在保证系统有较好的服务性能的同时使系统具有高可用性，但群体智能算法由于存在容易陷入局部最优、收敛速度太快等问题，导致出现任务分配不合理、任务总完成时间增加等情况，最终影响系统的负载均衡。Nair等人20提出了LBA-HB负载均衡策略，结合蜜蜂算法对负载均衡策略进行改进，分配任务时虚拟机负载将更新，并通知其他任务。基于先到先服务（FCFS）算法将任务放入等待队列，任务将分配给负载最小的虚拟机，该算法提高了任务的响应时间，但是并没有考虑任务的优先级。Wang等人21提出了IMPSO算法，优化了任务完成时间和执行任务的成本之间的权衡，该算法最大限度地减少了陷入局部优化的概率，提高了 PSO 算法的收敛速度。Kousalya 等人22提出了一种新的虚拟机任务分配模型，与FCFS和PSO方法相比，所提出的ICSA算法减少了任务总完成时间、等待时间及响应时间。Abualigah等人23通过基于精英的差分进化引入了新的混合蚁狮优化算法，用于解决数据中心中的多目标任务调度问题。该方法通过采用基于精英的差分进化作为局部搜索方法进行了改进，以增强探索能力并避免提供陷入受限最优解。Srichandan等人24通过利用混合方法进行任务调度，该方法结合了遗传算法（GA）和细菌觅食（BF）算法的所需特征。所提出的混合算法减少了任务完成时间和能源消耗。这种方法的缺点是任务评估需要更多时间并且性能较差。综上所述，现有的针对数据中心的负载均衡策略存在以下几个问题：1）对任务优先级、截止时间以及实时负载状态等没有考虑全面，导致任务拒绝率的提高以及任务需要重新分配和迁移的概率的提高，降低了系统资源利用率以及增加了任务的总完成时间；2）群体智能算法进行混合时，虽然增强了任务调度时的搜索能力以及避免了陷入局部最优解，但是混合之后导致控制参数增加，提高了算法的复杂性；3）几乎没有考虑调度过程中虚拟机的可靠性，导致作业无法按时执行等问题，最终影响集群系统的服务性能以及用户满意度。2任务调度系统模型与问题建模多作业集群系统中任务调度问题定义为：将各种优先级不同和大小不同的任务根据某些合适的策略分配给VM，使得所有的任务可以在规定的执行周期内完成，减少SLA违规次数，避免由于调度不当引起王重阳，等：基于SDN和改进CSA算法的多作业集群的负载均衡算法29计算机与现代化2023年第11期的资源利用不足（underloaded）或者过度利用（overloaded）的问题，保证资源的不浪费以及较高的服务性能，尽量减少任务迁移次数和降低因过载而导致VM故障的概率，最终提高系统的可靠性、稳定性以及高可用性。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个任务，每个任务有一组参数，表示为 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进行迁移，这个过程需要一些任务传输时间。为了减少任务的完成时间，就要提高任务的传输速度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，otherwise（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=1tLenivmsrj，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）对于每个要被分配的taski，如果选定的vmj不满足式（15），则该任务会被拒绝在其上执行，系统会根据负载均衡策略继续选择其余较优的 vmj+1，任务拒绝率越低，在特定时间段内完成的任务数量、用户满意度以及系统的 QoS越高，taskreject_rate计算方法如式（15）所示：taskreject_rate=taskrejectedtasktotal（15）其中，taskrejected表示被拒绝的任务数量，tasktotal表示任务总数。SOS-ICSA调度策略Open vSwitchSDN控制器共享存储用户作业调度器任务队列服务器1服务器nvm1vm2vm3vmj-2vmj-1vmj302023年第11期2.3VM的可靠性评估可靠性是保证多作业集群系统可以提供可靠服务的必要条件，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=1.0，初始化vmrej的计算方法为：vmrej=vmre_diskjvmre_RAMjtaskpri，j（16）步骤 2当 vmj出现故障时，更新 vmrej。首先为vmj设置一个count_re记录磁盘或者RAM出现故障的次数，若 vmj出现故障，vmre_diskj和 vmre_RAMj的值将减半，表示vmrej的可靠性很低，被选中的概率也会更小，若集群中有多余的VM，则将vmj替换掉。步骤3 在vmj没有出现故障的情况下，taski执行出错或者没有在可接受的响应时间内执行任务，视为任务执行失败，更新tasksc_fci，j，计算方法如式（17）所示，taskfail_numi，j为当前周期内，vmj上taski执行出错的数量。tasksc_fci，j=tasksc_fci，j+0.1 tasksc_fci，j，任务执行成功tasksc_fci，j-0.1 tasksc_fci，j taskfail_numi，j，任务执行失败（17）在分配taski时，vmrej和vmrej+1的值相同，但vmj上的任务连续执行失败次数更多，系统就判断vmj的可靠性不高，taski将会被分配给vmj+1。3改进的CSA任务调度算法CSA算法的灵感来自于乌鸦对食物的收集习惯，并且乌鸦会一直盯着它的其他伙伴来寻找比现有食物来源更好的食物来源（位置），通过这种方式，也可以为不同任务找到最优的VM并最小化任务总完成时间。表1乌鸦偷窃食物行为与任务调度的对应关系ICSA算法乌鸦乌鸦位置隐藏的食物选择另一只乌鸦跟随隐藏的食物任务调度问题任务任务调度的当前解决方案个体最佳解决方案选择个体最佳解决方案使用个体最佳解决方案生成新解决方案根据任务调度的特点，CSA算法的表述如下，主要参数的物理含义如表1所示。X=x1，x2，.，xnw（X）=1Ruxa+2vmrexa（18）min(Ruxa)iter+1Ruxia max(Ruxa)，a=1，2，.，n（19）其中，X是决策变量组，表示任务要分配的VM，w（X）是目标函数，当选择xa时，要计算它当前资源利用率和可靠度，根据目标函数值来判断是否将其加入决策变量中，每次更新位置时，会选择 w（X）值更小的位置，说明其负载低且可靠性高，1和2分别为负载因子和可靠性因子的权重值；为了避免因VM空闲而浪费资源，以及因过载而导致系统性能下降，式（19）表示选择的位置应满足的资源利用率的范围，根据文献26，如果vmj的利用率低于其能力的25%，则vmj处于欠载状态，如果vmj的利用率超过其能力的80%，则处于过载状态，否则处于平衡，如式（20）所示：vmstatusj=Ruj|vmcpj 80%|，overload|vmcpj 25%|Ruj|vmcpj 80%|，balanced（20）vmcpj=vmsrj+vmbwj（21）其中，vmstatusj表示vmj的负载状态，vmcpj表示vmj的计算能力，计算方法如式（21）所示。虽然CSA算法有实现简单、参数少、灵活性较高等优点，在解决任务调度问题时也颇受欢迎，但是它也存在一些问题：1）传统的CSA是一种保守的方法，它使用当前解决方案（位置）生成一个新解决方案，即使所选位置的目标函数较差，而不是当前最佳的解决方案；2）不均衡的开发和探索过程以及单调的更新方法，很大程度地限制了算法的搜索能力，导致算法在求解问题时陷入局部最优，最终影响虚拟机的选择。基于以上2个主要问题，下面将对其进行改进。3.1局部优化策略ICSA3.1.1引入精英方法由于CSA采用的是用相同的感知概率来随机选择一个记忆位置，这个位置可能会被接受并生成新的解决方案，即使它比之前记忆的位置还要差，所以需要引入精英方法来选择目标解决方案。在迭代过程中，对于每个违反边界的决策变量，本文将用全局最佳解决方案的决策变量来代替它。执行这个方法之后，新的决策变量对于加速搜索过程中的所有新生成的解决方案都将是可行的，同时基于全局最优解来修改违规变量也增加了围绕全局最优解的搜索和收敛速度。检查决策变量是否可行以及更新违规变量的计算方法如式（22）所示：iter+1xia=iter+1xia，xminaiter+1xia w(iterMi)不需要，w(iter+1Xi)w(iterMi)（26）3.2SOS对CSA的参数进行优化乌鸦搜索算法中，它的飞行长度fl参数控制乌鸦的搜索能力，感知概率CAP参数平衡乌鸦的探索和开发能力，由于这2个控制参数值固定，导致无法实现解的多样化，因此需要进一步增强CSA算法，对每个个体采用不同的控制参数，从而可以根据每个个体的状态适当地调整fl和CAP，提高全局的收敛性。使用SOS算法来自适应优化CSA算法2个参数，既能帮助CSA算法找到最佳或接近最优的解决方案，同时由于SOS不包含任何参数，也大大降低了CSA参数设置的复杂性。在迭代过程中，SOS随机生成一组生物作为生态系统中的初始种群，每个生物都代表着问题的解决方法，同时每个生物还有一个适应度值，代表着对生态系统的适应性，在进化过程中，具有较高适应度值的生物将维持到下一代。在SOS中，生物体=fl，CAP 由CSA算法中2个控制参数组成，适应度值的计算方式如式（27）所示：Fitness()=1Summin(w(X)（27）Summin（w（X）的定义如下：由于乌鸦的种群数量为m，所以每只乌鸦使用fl，CAP利用中的值找到自己的一组最优解w（X），获得m个个体最优解后，利用局部最优策略从中选择出的一组最优解作为当前的全局最优解，Summin（w（X）就是当前最优解的最小目标函数值的总和。SOS优化策略是通过以下3个搜索和更新阶段（即互惠、共生、寄生）来执行的：1）互惠阶段。在互惠阶段，2个生物fl和CAP是基于共同利益考虑的。两者之间的关联是为了使乌鸦既具有解的多样性同时也不会陷入局部最优的问题，得到的2个新的解决方案fl和CAP，计算方法分别如式（28）和式（29）所示：fl=fl+r1（0，1）（Xbest-MV K1）if Fitness（fl）Fitness（fl）（28）CAP=CAP+r2（0，1）（Xbest-MV K2）if Fitness（CAP）Fitness（CAP）（29）MV=fl+CAP2（30）其中，r1和r2表示2个（0，1）范围内均匀分布的随机数，K1和K2表示收益因子，随机确定为1或2，MV表示两者之间表现出来的互惠特征，如式（30）所示，增加两者的生存优势，Xbest表示在当前迭代中具有最高适应度值的生物体。值得注意的是，只有fl和CAP的新适应度函数值优于前一代的fl和CAP的适应度值的时候，才会进行更新。2）共生阶段。2个控制参数之间建立关联，会使其中一个受益但不会对另外一个参数造成不利影响，这种关系就称为共生。该阶段将fl置于优势位置，同样仅当fl优于前一代的适应度值才会作为新的解决方案，计算方法如式（31）所示：fl=fl+r3（-1，1）（Xbest-CAP）if Fitness（fl）Fitness（fl）（31）3）寄生阶段。在该阶段，通过复制fl来创造一个Pvec向量，Pvec的值由随机函数进行修改，CAP将作为Pvec的宿主，如果 Pvec的适应度函数值优于 CAP，则将会取代CAP，否则CAP将对Pvec产生免疫功能，保留下来，而Pvec会被忽略。3.3算法描述本文对 CSA算法提出了局部优化策略，并使用SOS算法对CSA的2个控制参数进行自适应优化，不仅可以提高算法收敛速度和解决方案的质量，同时降低了算法的复杂性，算法的具体步骤如下所示：步骤1初始化算法参数：乌鸦种群数量n且包含n个生物，最大迭代次数itermax，选择当前生态系统中最好的生物best。步骤2随机生成初始解，检查可行性，并且初始化记忆。步骤 3执行 SOS 算法生成新的 CSA 参数 fl、CAP。步骤4通过式（18）计算新参数的目标函数值。322023年第11期步骤5生成新的位置（解决方案）。步骤6执行CMS策略，通过式（23）产生2个新解。步骤 7通过式（18）计算新解决方案的目标函数值。步骤8通过式（26）检查变量的可行性，修改违反约束的变量，并更新解决方案。步骤9根据式（27）计算生物的适应度值，选择当前最好的生物vbest。步骤10重复步骤3步骤9，直到达到最大迭代次数，输出最优解。算法1SOS-ICSA任务调度算法输入：T=task1，task2，.，taskm、C=vm1，vm2，.，vmn输出：The optimal solution/Mapping of tasks1：Initialize fl（flight length），CAP（awareness probability），N（crowspopulation，and organisms），itermax，iter=1；2：Randomly initialize the position of the N crows andselect the current best organism best；3：while iteritermaxdo4：for each crow do5：Randomly select crowi+1to follow；6：Execute SOS to compute a new set of CSA parameter values（fl，CAP）；7：if rand（0，1）CAP then8：iter+1xi=iterxi+rand iterfli(iterMi+1-iterxi)9：else choose a random position10：Generate new positions xic，xioby CMS strategy11：Evaluate fitness function of the three new positions12：Check new positions feasibility and modify violated variables by Eq.（22）13：Updateiter+1xiby Eq.（23）14：Update memory byiter+1xi15：Calculate the fitness value of the organism byEq.（27）to select vbest16：End For17：iter=iter+118：End While19：Return the optimal solution3.4任务分配当用户提交任务时，作业调度器会根据任务的优先级别以及任务的截止时间大小将任务插入待分配队列中，若任务没有设置优先级或者截止时间一样，则根据FCFS策略，先来先服务，然后 SOS-ICSA调度策略将会为任务 taski选择合适的虚拟机 vmj，最后SDN控制器将任务请求taski转发到vmj，vmj开始处理该任务，作业运行结果数据会保存到共享存储中，任务分配策略具体步骤如下：步骤 1利用 SOS-ICSA 调度策略，获取 taski的目标vmj的IP地址vmipj和MAC地址vmMACj。步骤 2SDN 控制器在接收任务请求的交换机流表中添加流表项，流表将请求包的目的IP地址ip和MAC地址mac分别修改为步骤1中获取的vmipj和vmMACj。步骤3SDN交换机按照相应规则，将请求包转发到目标vmj，vmj开始处理taski。步骤4SDN控制器将为处理服务请求的vmj新增一个流，它将响应包的源IP地址和MAC地址分别修改为虚拟MAC（VMAC）和虚拟IP（VIP），并建立vmj和用户端之间的网络连接。4实验与结果分析为了对本文提出的模型和策略进行验证，在CloudSim仿真平台下与其他算法 CSA29、ECSA2的性能进行了比较，主要对比的指标有任务总完成时间、资源利用率、系统不平衡度以及任务拒绝率。4.1实验设计实验的硬件环境为：Intel Core i7-10700 CPU2.90 GHz，16 GB内存。软件环境为：Ubuntu18.04操作系统，Eclipse 4.6和Java 1.8.0语言开发工具，以及CloudSim 3.0.3仿真器。算法参数设置如表 2所示，仿真参数如表3所示。表2算法参数设置算法SOS-ICSACSAECSA参数flCAP任务数虚拟机数itermaxflCAPflCAP参数值1，30，1500，250010，50500.50.11.5，2.50.05表3仿真参数设置类别虚拟机任务仿真参数虚拟机数量处理速度（MIPS）CPU（PEs）Memory/GB带宽/MbpsVMM任务数量任务长度（MI）文件大小/MB参数值10，5050025001，52565125001000XEN5002500300100020010004.2实验结果分析1）任务总完成时间。图2显示了任务总完成时间随着任务数量的增加的变化情况，从图中可以看出随着任务数量的增加，3种算法的总完成时间都在增加，而本文提出的方法优于其他 2 种算法，任务总完成时间都是最少的，这说明对CSA算法引用局部优化策略以及对其2个控制参数fl、CAP进行自适应性优化，增强了任务调度的局部搜索能力和全局搜索能力，因此在任务总完成时间方面具有一定的优势。王重阳，等：基于SDN和改进CSA算法的多作业集群的负载均衡算法33计算机与现代化2023年第11期图2任务总完成时间对比图2）资源利用率。如图3所示，本文将VM资源利用率作为另一个性能参数考虑在内，从图中可以看出，与CSA、ECSA算法相比，本文提出的方法非常高效地利用了VM资源，并且达到了较高的资源利用率，在一定程度上避免了资源的浪费。图3资源利用率对比图3）系统不平衡度。如图4所示，与CSA和ECSA相比，随着任务的数量逐渐增加，SOS-ICSA降低了系统不平衡的程度，因为在VM选择过程中对算法进行了改进，考虑了任务的完成时间、当前的VM资源利用率，从而确保了分配任务的虚拟机具有较低的负载。本文提出的算法实现了系统最小的不平衡程度，跟其他 2 个算法相比，SOS-ICSA能更好地均衡VM的负载。图4系统不平衡度对比图4）任务拒绝率。如图5所示，与CSA和ECSA相比，本文提出的方法的任务拒绝率明显是最低的，因为考虑了虚拟机可靠性约束，对于较低可靠性的虚拟机，本文不会把任务分配给它，还考虑了任务约束问题，即任务在选择的虚拟机上执行不能超过任务截止时间，正是这2个约束极大地降低了任务拒绝率，但是在任务数量很大的情况下，由于虚拟机处理不过来，任务又必须处理，所以本文提出的方法仍然有较低的任务拒绝率，但这是可以接受的范围，对系统性能影响很小。图5任务拒绝率对比图5结束语本文针对现有多作业集群系统中存在任务调度效率不高的问题，提出了基于SDN和SOS-ICSA的负载均衡算法。首先对CSA算法加入了局部优化策略，以提高算法收敛速度和解决方案的质量，然后利用SOS算法对CSA的2个控制算法进行自适应优化，帮助 CSA 找到最佳或者接近最优的解决方案。由于SOS没有控制参数，所以大大降低了优化算法的复杂性。在分配任务时，该策略还会考虑虚拟机的可靠性，进一步提升系统性能。相比较现有的负载均衡算法，本文结合SDN的负载均衡策略使得系统灵活性更高，具有更好的可扩展性。最后搭建仿真实验平台，对本文提出的负载均衡算法进行了验证，同时与2个同类方法进行了对比实验。实验结果表明，本文提出的算法在任务总完成时间、资源利用率、任务拒绝率以及系统不平衡度4个方面，都优于CSA、ECSA算法。本文并没有讨论VM的故障预测以及出现故障后的故障恢复，未来可以在这一方面进行进一步的研究。参考文献：1 KUMAR S，MISHRA A.Application of Min-min and Max-min algorithm for task scheduling in cloud environment under time shared and space shared VM models J.International Journal of Computing Academic Research（IJCAR），2015，4（6）：182-190.2 KUMAR K R P，KOUSALYA K，VISHNUPPRIYA S，et al.Enhanced crow search algorithm for task scheduling incloud computingC/IOP Conference Series：MaterialsScience and Engineering.2021，1055.DOI：10.1088/1757-899X/1055/1/012102.3 KUMAR M，SHARMA S C.Dynamic load balancing algorithm to minimize the makespan time and utilize the resources effectively in cloud environmentJ.InternationalJournalofComputersandApplications，2020，42（1）：108-117.4PATEL G，MEHTA R，BHOI U.Enhanced load balancedSOS-ICSAECSACSA300025002000150010005000Makespan/s5001000150020002500Number of tasksSOS-ICSAECSACSA5001000150020002500Number of tasksResource Utilization0.900.850.800.750.700.650.600.550.505001000150020002500Number of tasksSOS-ICSAECSACSA1.61.41.21.00.80.60.4Degree of Imbalance5001000