基于模拟退火的容量约束和故障感知控制器布局优化

沙特国王大学学报基于模拟退火的容量约束和故障感知P. Aravinda，G.P.Saradhi Varmab，P.V.G.D.Prasad ReddycaGayatri Vidya Parishad College of Engineering（Autonomous），Visakhapatnam，Andhra Pradesh 530048，IndiabChaitanya Bharathi Institute of Technology（Autonomous），Hyderabad，Telangana 500075，Indiac印度安得拉邦维萨卡帕特南安得拉邦大学计算机科学与系统工程系，邮编530003阿提奇莱因福奥文章历史记录：收到2020年2021年3月25日修订2021年4月26日接受在线预订2021年保留字：软件定义网络延迟控制器布局模拟退火优化A B S T R A C T软件定义网络是一种不断发展的网络模型，其中控制平面与数据平面解耦。如何确定控制器的数量和位置，并为它们分配开关，已成为一个令人着迷的问题。每个交换机必须被分配到一个备用控制器，这样，如果一个控制器遇到故障，然后分配给它的交换机可以立即连接到他们的备用控制器。现有的方法试图通过采用混合整数线性规划来解决这个问题，但是对于较大的网络，它的执行时间会大幅增加。为了减少执行时间，本文提出了一种基于模拟退火的启发式算法，其目标是最大限度地减少从所有交换机到各自的备份控制器的最大延迟。在Internet Topology Zoo的7个不同规模的真实网络上对该算法进行了评估，并将其性能与现有模型进行了比较。结果表明，该模型比现有模型（最小网络）平均加速2.5倍，比现有模型（最大网络）平均加速280倍.同时，该模型产生了近似最优解。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍软件定义网络（SDN）是一种不断发展的网络架构，它将控制平面和数据平面分开。控制平面建立了关于数据包如何在网络上传输的指导方针，数据平面实际上将数据包从一个点转发到另一个点。因此，整个网络智能被结合到可编程控制平面中，该可编程控制平面作为软件在服务器上运行，从而实现自动化网络管理、快速且容易地实现网络中的创新虽然SDN技术显然是新的，但其背后的概念在过去25年中已经*通讯作者。电子邮件地址：aravind53735@gvpce.ac.in（P.Aravind）。沙特国王大学负责同行审查制作和主办：Elsevier目前，软件定义网络领域正在进行大量的研究，涉及不同的领域，如网络虚拟化，控制器放置，多控制器SDN中的负载平衡，能源效率，SDN在物联网中的作用，无线SDN，SDN中的安全性等。从理论上讲，一个控制器就足以管理整个网络。但是，这种布置可能导致位于与控制器相距一定距离的位置处的开关的一部分上的传播延迟增加。因此，通常的做法是安装多个控制器，特别是在较大的网络中。现在的问题是需要使用多少控制器以及在哪里使用在网络中部署它们。这个普遍存在的问题在文献中被称为控制器配置问题（CPP），它引起了许多研究人员的注意，在最近的时间。 例如，作者（Singh和Srivastava，2018; Lu等人，2019; Killi和Rao，2019; Das等人，2020年; Kumari和Sairam，2021年）对CPP 进行了出色而全面的调查。作者在（Heller等人，2012）开始了CPP的研究，并提出了一种解决方案，该解决方案独立地最小化两个目标，即平均和最坏情况节点到控制器的延迟。但是他们没有考虑到https://doi.org/10.1016/j.jksuci.2021.04.0121319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comP. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5722的控制器。 作者在（Yao等人， 2014）提出了CPP的解决方案，该解决方案通过考虑控制器的容量而不是控制器的故障来最小化最坏情况的延迟。这个问题简称为CCPP。作者（Killi和Rao，2016）开发了一个线性规划模型，简称为FFCCPP，该模型可以预测控制器的故障，并最大限度地减少最坏情况下切换到备用控制器的延迟。但他们的方法中使用的线性规划模型涉及大量的决策变量和约束条件。决策变量的数量与网络的大小成二次方地增加约束的数量也随着网络的大小成二次方地增加，从而导致程序的执行时间 这种关注导致了以下的研究问题：是否有一种方法，可以解决CPP更快地考虑容量和故障的控制器？启发式算法已被证明是快速解决上述组合优化问题并提供接近最优解的良好研究团体正在使用各种启发式算法，模拟退火、群智能（粒子群优化、蚁群优化和人工蜂群算法）、禁忌搜索、遗传算法等，来解决各个领域的问题。例如，在（Ahmed等人，2015 g，2016 h，2016 i，2017 j，2017 k，2018 l; Basha等人， 2018年）应用各种类别的群优化算法来解决社会，工业和医疗领域的问题本文提出了一种模拟退火算法，考虑了控制器容量和失效情况，快速得到控制器配置问题的最优解。该算法旨在最大限度地减少最坏情况下切换到备份控制器的延迟。这种方法是缩写的作为SA-FFCCPP。本文的主要贡献如下：1. 控制器配置问题的数学表述是一个混合整数线性规划模型。2. 针对控制器配置问题，提出了模拟退火算法以及其他支持算法。3. 对所有算法进行了复杂性分析4. 两类性能指标，即，为了比较所提出的模型与现有模型的性能，定义了主要和5. 在Internet Topology Zoo的实际网络上对所提出的模型和现有的模型进行了评估，结果表明，所提出的方法比现有的方法更快，而且产生了接近最优的解。本文的其余部分组织如下。第2节给出了相关的工作，以及在SDN中解决控制器放置的不同问题的各种方法的应用。在第三节中，给出了现有方法的数学公式和所提出方法的模拟退火算法。在第4节中，给出了实验结果，并对结果进行了讨论。第五部分对全文进行了总结，并对今后的工作进行了展望.2. 相关工作作者在（Heller等人， 2012）发起了CPP的调查，并提供了一种解决方案，该解决方案独立地最小化两个度量，即平均和最坏情况节点到控制器延迟。他们还分析了如何通过最小化另一个度量来影响一个度量。然而，控制器的可靠性和容量的关键方面没有考虑。作者在（Yao等人， 2014年）提出了一种CPP解决方案，该解决方案最大限度地减少了最坏情况下的延迟，而同时con-itrollers被考虑在内。但他们没有考虑控制器的故障。Killi和Rao，2016年）的作者通过将一组K个参考控制器（其中，K > 1 ） 与 每 个 开 关 相 关 联 ， 开 发 了 一 种 混 合 整 数 线 性 规 划（MILP）模型，简称为FFCCPP。例如，如果K = 2，则两个参考控制器与每个开关相关联，即，第一和第二参考控制器（或者分别是主控制器和备用控制器）。控制器被安装在网络中的适当位置处，使得如果任何控制器遇到故障，则其被委派为主要控制器的交换机将被重新分配给它们的第二参考控制器。此模型旨在最大限度地减少最坏情况下切换到备份控制器的延迟。并且，使用这种方法不可能断开连接，因为通过考虑所有开关的需求来安装足够因此，即使一个控制器发生故障，其他控制器仍然可以支持所有交换机。但实现该模型的程序执行时间很长。作者在（Killi和Rao，2020）中试图通过应用多稳定匹配算法来最小化控制器之间的最大负载不平衡。该算法可以在控制器之间均匀地分配开关的子集，而其余的开关被分配给它们最近的控制器。此外，一些开关从它们的控制器转移，以便减少从开关到控制器的延迟。近年来，各种启发式算法被提出来用于解决控制器配置问题.例如，（Schütz和Martins，2020）的作者提出了一种启发式方法来解决CPP，同时确保控制器之间的负载平衡。与此同时，以及每对控制器之间的延迟保持在规定的范围内。作者在（Torkamani-Azar和Jahanshahi，2020）中提出了一种名为Garter Snake Optimization的Meta启发式算法，用于解决容量限制控制器放置问题，以最小化端到端延迟。作者在（Gao等人，2015; Sahoo等人，2017; Kumar Singh等人，2019）应用了萤火虫优化、粒子群优化等启发式算法，以解决控制布局问题的不同方面。在下面的段落中，详细讨论了使用模拟退火启发式算法来解决SDN中的作者在（Hu等人，2014）提出了求解CPP的l-w-贪婪和模拟退火算法。作者旨在通过最小化一个称为控制路径中的期望损耗分数的度量来最大化SDN的可靠性。并证明了模拟退火算法产生的解接近于最优解。控制路径损耗可能由于网络元件（如交换机和链路）的故障而发生。因此，作者考虑了这些网络元件的故障概率。然而，他们没有考虑到控制器的容量和故障。作者在（Lange等人，2015）开发了一种Pareto模拟退火算法，用于解决大规模SDN的CPP。他们的解决方案确定了部署控制器的合适位置，以便在发生故障时最大限度地减少延迟。但是他们没有考虑备用控制器和控制器的容量。作者在（Killi和Rao，2017）中提出了一种模拟退火算法，通过考虑备份控制器并考虑控制器的容量来解决大规模SDN上的CPP其目标是使从交换机到主控制器以及从主控制器到其最近的控制器（假定为交换机的备用控制器）的时延之和最大化。但他们放宽了开关有能力检测控制器故障的假设。P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5723Xx ¼1;8i2V±2Vð ÞIJIJIJIJXXx - 是的x-αx-α···αxα≥wj;作者在（Mohanty等人，2020）提出了模拟退火和贪婪算法来解决控制器的可靠放置问题，其目的是最小化传播延迟和路由成本。他们声称模拟退火预成形比贪婪和随机算法更好但是他们没有关注最坏情况下的传播延迟。表1按拟议模式的主要特点，即：管制员意识用于放置q个控制器的大小为q的位置R1，然后为每个交换机分配第一和第二参考控制器，使得最坏情况下的交换机到第K参考控制器的等待时间最小化。MILP-FFCCPP的数学公式如下：最小值fyg ¼ min。max dKi; j1控制器故障的能力和预见性据我们所知，到目前为止，R1- RjR1j¼ qR1- RjR1j¼qi2V模拟退火启发式算法，用于解决SDN中控制器的放置问题，具有控制器故障预见，并具有对控制器容量的约束，假设交换机可以识别控制器的故障为此，使用模拟退火，重点是最大限度地减少最坏情况下切换到备份控制器的延迟。3. 问题公式化3.1. 初步概念设网络由图G =（V，E）表示，其中V = {s1，s2，. . ，sn}表示网络中n个交换机的集合，E表示交换机之间的物理链路的集合。每个链路的长度基于其源和目标节点的纬度和经度细节来确定，然后将其转换为传播延迟。接下来，确定每对节点之间的最短路径。设G的成本邻接矩阵表示为其中，dKi;j表示与交换机i和其位于交换机j处的第K参考控制器之间的最短路径相关联的等待时间。受以下限制：Xwj<$q2jsR其中，Wj是决策变量。上述约束限制了控制器的数量。如果控制器位于第j个开关所在的位置，则wj= 1;否则wj= 0。它保证安装了q控制器以下两个约束确保每个开关仅由一个第 g个参考控制器管理，其中g= 1，2，.. . 、K.1IJjsR其中，x1是决策变量。如果位于开关j位置的控制器是开关i的第一参考控制器，则x1= 1;否则x1= 0。假设控制器位于D = [d ij]（对于1≤i≤n和1≤j≤n），其中dij表示延迟ij ij对应于交换机S1和Sj之间的最短路径。让q指定需要定位在网络内适当位置的控制器的数量开关i的位置用作该开关的第一参考控制器。Xxg¼1;8i2V;g¼ 2; 3;···;K令R表示用于定位控制器的可能位置的集合。假设每个交换机都具有OpenFlow能力，因此控制器可以位于任何交换机的位置IJjsRjð4Þ因此，R = V。设开关si的需求用Li表示。让电容-其中，xg是决策变量。如果控制器位于开关处，j是开关i的第g个参考控制器，则xg= 1;否则xg= 0。控制器j的性质由Uj表示。假设最多K-1个控制器在K的任意点失效伊季时间，其中K的值可以由网络管理员固定。还假设控制器的故障可以由开关检测到。3.2. 现有方法：最小化最坏情况延迟到第K个参考控制器的MILP模型（MILP FFCCPP）MILP-FFCCPP将一组K个参考控制器（其中，K > 1）与每个开关相关联。例如，如果K = 2，则每个开关与两个参考控制器相关联，即，第一和第二参考控制器（或者，分别是主和备用控制器，x g≤w j;8i2V; 8j2R200g¼1上述约束确保了，如果存在位于第j个开关的位置处的控制器，则对于g = 1，2，.. . ，K且i = 1，2，.. . ，n.如果在开关j处不存在控制器，则对于g = 1，2，.. . 、K.此约束还保证不会将交换机分配给非活动控制器。Xx1≥wj;8i2V;8j2R（当然）。控制器位于网络中的适当位置，使得如果一个控制器发生故障，b2Rdib≤dijð6Þ将被重新分配给它们的第二参考控制器。这种重新分配以这样的方式完成，即最坏情况下切换到第二参考控制器的延迟将被最小化。3.2.1. 现有方法的问题陈述给定控制器数量q和大小为n的可能控制器位置集合R，从R中选取它确保了在q个控制器中，最接近开关i的控制器，i = 1，2，.. . ，n，可以用作其第一参考控制器。g g1g21伊卜伊吉伊吉b2Rdib≤dij8i2V;8j2R;g¼2; 3;···;K=7VIBP. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5724X XL x ≤ U w; 8j2R8ijjxy≥dx;8i2V100 V×IJ1≥≤上述约束确保在q个控制器中，第g个最接近开关i的控制器，对于i= 1，2，.. . ，n，可以用作其第g个参考控制器，其中g> 1。KGIJg¼1i2V上述等式对控制器的容量施加了约束它保证了交换机的需求的集合，对于该集合，位于交换机j处的控制器用作第g个参考控制器（对于g = 1，2，.. . ，K），将不会大于该控制器基季j2R上述约束确保y是从所有交换机到其第K个参考控制器的最大wj2 f 0; 1 g;8j2R1000x g2 f0; 1 g; 8i2V; 8j2R;g¼1; 2;·· ·;K=11以上两个约束称为域约束。它们保证所有决策变量都是二进制的。3.3. 建议的方法：模拟退火启发式最小化最坏情况延迟到第K个参考控制器（SA-FFCCPP）模拟退火是一种概率优化方法，它模仿了冶金学中的退火过程，即缓慢冷却热金属以使其变得坚固。模拟退火算法的主要特点是在搜索最优解时不会陷入局部最优，而是以一定的概率将劣解作为候选解，从而得到全局最优解。SA-FFCCPP假设在任何时间点最多有一个控制器可能发生故障，因此将两个参考控制器与每个交换机关联。3.3.1. 建议方法的问题陈述给定控制器的数量q和大小为N的可能控制器位置R的集合，开发模拟退火算法，以便确定给定控制器的适当位置，并为每个交换机分配主参考控制器和第二参考控制器，使得从交换机到第二参考（备份）控制器的最大延迟最小化。最优控制器放置的模拟退火算法在Ataint m1中给出，它调用了在Ataint m2中给出的Assign_Controllers，在Ataint m3中给出的Is-Feasible，在Ataint m4中给出的Find_Objective和在Ataint m5中给出的Select_NeighborSelect_Neighbor算法依次调用Assign_Controllers和Is-Feasible算法请注意，算法中的某些行号用“*”标记算法1：模拟退火输入：N：-网络中交换机/节点的数量，D：-由每对节点之间的最短路径组成的Nq：-要部署的控制器数量，U：-由控制器的容量组成的大小为q的阵列，L：-由开关的需求组成的大小为N的阵列，Ti：-初始温度，Tf：-最终温度，MaxIter：-每个温度下的迭代次数，Alpha：-温度递减系数。输出量：OCL：-由控制器的最终位置组成的大小为q的数组，OA 1：-大小为N的阵列，由所有交换机的第一参考控制器的最终分配组成，OA 2：-大小为N的阵列，由所有开关的第二参考控制器的最终分配组成，Optimal_Obj：-第二参考控制器的最大值。1Optimal_Obj= ;2whileTRUE do3CCL=在[1，N]中选择q个随机整数; 4* = Assign_Controllers（N，D，q，CCL）; 5*if（Is_Feasible（N，q，U，L，A1，A2，CCL））6然后打破;7end if8 end while9*Obj= Find_Objective（A2）;11 而T Tf12return 1;13而迭代次数MaxIter14如果Ob j Optimal_Obj，则15Optimal_Obj = Obj;16OA2 = A2;17OA1 = A1;18OCL = CCL;19end if20*=Select_Neighbor（N，D，q，U，L，A1，A2，CCL）; 21*New_Obj= Find_Objective（NA2）;22Delta = New_Obj -Obj;23M=得到一个0到1之间的随机数;24如果（Exp（-Delta/T）> M），则25Object = New_Object;26CCL = NCL;27A1 = NA1;28A2 = NA2;29end if30迭代次数=迭代次数+1;31end while32T = T * Alpha;33结束时，P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5725算法2：分配控制器输入：N：-网络中的节点数，每对节点，D：-一个N× N的矩阵，由最短路径组成，q：-要部署的控制器数量，CCL：-由控制器的当前位置组成的大小为q的数组。输出量：A1：-由所有开关的第一参考控制器的当前分配组成的大小的阵列，A2：-大小为N的数组，由所有开关的第二参考控制器的当前分配组成。1 对于i = 1到N，2如果（D[i，CCL1] D[i; CCL2]），则3min = CCL1;4return 1;5smin = CCL2;6return 2;7其他8min = CCL2;9return 2;10smin = CCL1;11return 1;12end if13对于j = 3到q，14如果（D[i，CCLj] min），则15int max = min;16smin_index = min_index;17int [i，j];18int max = j;19else if（D[i，CCLj] smin） then20int [i，j];21return j;22end if23端24A1[i] = CCLmin_index;25A2 [i] = CCLsmin_index;26结束，算法4：Find_Objective输入：N：-网络中的节点数，每对节点，D：-一个N×N的矩阵，由最短路径组成，A2：-长度为N的数组，由所有开关的第二参考控制器的当前分配组成。输出量：目标：-最大的第二参考控制器的负载。1return 0;2对于i = 1到N，3如果（D[i，A2[i]] > Obj），则4Obj = D[i，A2[i]];5end if6端算法3：Is_Feasible输入：N：-网络中的节点数，q：-要部署的控制器数量，U：-长度为q的数组，由控制器的容量组成，L：-由开关的需求组成的长度为NCCL：-由控制器的当前位置组成的大小为q的数组，A1：-长度为N的阵列，由所有开关的第一参考控制器的当前分配组成，A2：-长度为N的数组，由所有开关的第二参考控制器的当前分配组成。输出：布尔值TRUE/TRUE。1对于i = 1到q，2对于j = 1到N，3如果（A1[j]==CCL[i]或A2[j]==CCL[i]）4则U [CCL[i]] = U [CCL[i]] - L[i];5end if6端7如果（U[CCL[i]] 0），则8returna;9end if10端P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5726×算法5：Select_Neighbor输入：N：-网络中的节点数，D：-由每对节点的N N矩阵，q：-要部署的控制器数量，U：-长度为q的数组，由控制器的容量组成，A1：-长度N的阵列，其包括用于所有开关的第一参考控制器的当前分配，A2：-长度为N的数组，由所有开关的第二参考控制器的当前分配组成。CCL：-由控制器的当前位置组成的大小为q的数组。输出量：PCL：-由控制器的修改（扰动）位置组成的大小为qPA 1：-大小为N的阵列，由所有交换机的第一参考控制器的修改分配PA 2：-大小为N的数组，由所有交换机的第二参考控制器的修改分配1choice=在0和1之间随机生成一个整数; 2switchchoice3情况1：//改变一个随机数//控制器与其他随机//push4而TRUE5i1=在1和q之间随机生成整数;6PCL = CCL;7PCL [i1] =随机生成CCL;8* = Assign_Controllers（PCL）;9*if（Is_Feasible（N，q，U，L，PA1，PA2，PCL）），则10破碎;11end if12end while13结束病例14情况2：//改变两个随机数//控制器与其他两个随机//pages15而TRUE16i1 =在[1，q]中随机生成一个整数;17i2=在[1，q]它不等于i1;18PCL = CCL;19i3=在[1，N]中生成CCL中不存在的随机整数;20PCL [i1]= i3;21i4 =生成一个随机整数[1，N]，其不存在于CCL中并且不等于i3;22PCL[i2] = i4;23*=Assign_Controllers（PCL）;24*if（Is_Feasible（N，q，U，L，PA1，PA2，PCL））25然后打破;26end if27end while28结束病例29结束开关3.3.2. 算法描述3.3.2.1. 模拟退火：. 该算法的主要输入是由四个参数组成的冷却计划，Ti（初始温度）、Tf（最终温度）、MaxIter（每个温度下的迭代次数）和Alpha（温度下降因子）。表2中显示了本工作实施中这些参数所用的值。在步骤1中，Optmal_Obj变量被初始化为无穷大，最终给出目标函数的最优值。在步骤3中，q个控制器的位置从N个可能的位置随机生成在步骤4中，将主参考控制器和第二参考控制器分配给所有开关。在步骤5中，对该分配进行可行性检查。如果可行，则执行第9步，否则执行第2步，重复第3步至第5步，直到找到可行解在步骤9中，评估目标函数，并将其值存储在Obj变量中。在步骤10中，Ti（初始温度）存储在变量T中，该变量T保持当前温度。执行步骤11至33，直到T大于或等于Tf。在步骤12中，可变迭代被初始化为1，并且执行步骤13-31，步骤14至19记录了迄今为止在变量OA2、OA1和OCL中发现的最佳可行解。并且，解决方案的目标值记录在变量Optimal_Obj中。在步骤20中，通过改变一个或两个控制器的位置并通过将q个控制器作为主参考控制器和第二参考控制器分配给所有开关来找到当前可行解的可行相邻解在步骤21中，对新的可行解评估目标函数，并将其值存储在New_Obj变量中。在步骤22中，计算新目标值和当前目标值之间的差并将其存储在Delta变量中。步骤23在0到1的范围内随机生成一个数，并将其放入M变量中。步骤24-新的解以一定的概率被接受，定义为Pr（Delta，T）=e-Delta/T.如果Delta为负（即，在最小化问题的情况下，新的解优于当前解），则Pr（Delta，T）>1（与T值无关）并且也明显大于随机数M，因此在这种情况下总是接受新的解另一方面，如果Delta为正（即，在最小化问题的情况下，新的解不优于当前解），则Pr（Delta，T）<1（与T值无关）。在这种情况下，如果Pr（Delta，T）大于随机数M，则接受新的解，尽管它劣于当前解;否则它将不被接受。此外，可以观察到，接受劣解的概率在高温下更高，而在低温下更低，导致解的收敛。这是模拟退火算法的一个重要特征，它使算法有机会从更广的角度探索问题的解，从而得到全局最优解，而不是满足于局部最优解。在步骤30中，递增Iterations变量。在当前温度T下执行了所有预定义的迭代之后，在步骤32中，将温度值减小存储在Alpha变量中的恒定分数。Alpha的典型值为P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5727表1相关工作总结。参考年相关特性目标所用方法容量故障有意识的预见（Heller等人， 2012年）2012X X最小化平均和最坏情况节点到控制器的时延穷举搜索（Yao等人， 2014年度）2014UX最大限度地减少最坏情况下的延迟整数规划（Killi和Rao，2016）2016U U最大限度地减少最坏情况下的延迟混合整数线性规划（Killi和Rao，2020）2020UX最大限度地减少控制器多稳定匹配（Schütz和Martins，2020）2020UX尽量减少控制器启发式（Torkamani-Azar和2020UX最大限度地减少端到端延迟启发式Jahanshahi，2020年）（Gao等人，（2015年）2015UX最小化平均传播延迟粒子群优化算法（Sahoo等人，（2017年）2017X X最小化平均延迟。PSO和Firefly算法（Kumar Singh等人， 2019年度）2019X X最小化总平均延迟PSO与教师学习（Singh等人， 2019年度）2019X X最小化总平均延迟最优化（TLBO）算法基于Varna的优化（VBO）（Hu等人， 2014年度）2014X X最大限度地提高可靠性l-w-greedy算法及其仿真退火（Lange等人，（2015年）（Killi和Rao，2017）20152017X XU U最小化延迟最小化从交换机到Pareto最优控制器配置（POCO）和Pareto模拟退火混合整数线性规划（Mohanty等人， 2020年）2020U U主控制器和从主控制器到备用控制器最小化传播延迟和路由成本和模拟退火模拟退火与贪婪算法表2算法中使用的冷却计划参数值参数值Ti10Tf0.00001MaxIter 100阿尔法0.9范围从0.8到0.99。对于较小的α值，算法运行较快，但可能得不到满意的解。另一方面，当Alpha值较大时，算法运行较慢，但产生接近最优解。3.3.2.2. 分配控制器（_A）：给定所有对最短路径矩阵D和q个控制器的当前位置，该算法找到第一和第二最近控制器（即，分别是第一和第二参考控制器），从而保证满足约束（6）和（7）。3.3.2.3. 是否可行（_F）：给定q个控制器的当前位置和切换到控制器的分配，该算法检查该分配是否可行。它通过确定每个控制器的容量是否足以满足所有开关的需求来检查可行性，对于所有开关，它用作主要或第二参考控制器。该算法确保满足约束（8）。剩余的约束由Simulated_Annealing算法隐式满足。3.3.2.4. 查找目标（_O）：该算法以所有N个开关的最短路径矩阵D和第二参考控制器的分配为输入，以开关到第二参考控制器的最大距离为输出，即可行解的目标值。3.3.2.5. 选择邻居（_N）：该算法在模拟退火算法中起着重要的作用它以所有对最短路径矩阵D和q个控制器的当前位置作为输入，并通过改变一个或两个控制器的位置来产生控制器的修改位置作为输出邻居选择过程完全取决于要解决的问题的类型。邻解一般是通过对当前解稍作改变而得到的。在这项工作中，假设两种情况下选择相邻的解决方案。第一种情况是，用另一个新的随机控制器替换一个随机选择的控制器，该控制器不同于当前存在的控制器。第二种情况是，用一对新的随机控制器替换两个随机选择的控制器，这对新的随机控制器不同于当前现有的控制器。在步骤1中，随机选择两种情况之一。情况1跨越步骤3-13，其中更换一个控制器。在步骤5-7中更换一个控制器之后在步骤9- 11中，修改的解由扰动的控制器位置和扰动的开关到控制器分配组成，检查其可行性。重复步骤4-12，直到获得可行的解决方案。案例2跨越步骤14-28，其中替换了两个控制器。在步骤16-22中更换两个控制器之后，将主参考控制器和第二参考控制器分配给N在步骤23中切换。在步骤24-26中，针对可行性检查修改的解决方案。重复步骤15-3.3.3. 算法的复杂性分析设N是网络中节点的数量，q是要放置在网络中的控制器的数量。3.3.3.1. 分配控制器（_A）：由于q是恒定的，所以从步骤13到23的内部for循环花费恒定的时间。因此，从步骤1到26的外部for循环因此，该算法的时间复杂度为O（N）。P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5728X1¼d;122Q¼ ð Þqq-13.3.3.2. 是否可行（_F）：由于q是恒定的，因此从步骤1到10的外部for循环花费恒定的时间。因此，从第2步到第6步的内部for循环需要O（N）时间。因此，该算法的时间复杂度为O（N）。3.3.3.3. 查找目标（_O）：从第2步到第6步的for循环需要O（N）时间。因此，该算法的时间复杂度为O（N）。3.3.3.4. 选择邻居（_N）：在切换情况1中，while循环的搜索空间的大小是q*（N-q）。因此，时间复杂度为O（N）。在开关情况2中，while循环的搜索空间的大小为. qω。N-q= 0。所以，开关情况2的时间复杂度是，T2=O（N2）.因此，该算法的时间复杂度为max（T1，T2）=O（N2）.3.3.3.5. 模拟退火：从第2步到第8步的while循环的搜索空间的大小为。（2）时间复杂度：O（N）时间复杂度：while循环的范围从步骤11到33迭代了一个常数的次数，其时间复杂度是O（N2），主要是由步骤20贡献。因此，该算法的时间复杂度为O（Nq +1）。3.4. 性能度量为了比较现有方法和提出的方法的性能，定义了以下度量：控制器故障情况（WCL_F）：WCL F¼maxdKi;j12这将使所有交换机的最大延迟达到其第K参考控制器。控制器无故障场景下的最差情况延迟（WCL_FF）：WCLFF最大值1mm;最大值13mm这将使所有交换机的最大延迟达到其第一参考控制器。控制器无故障场景下的平均延迟（AL_FF）：nAL FF ij14ni¼1这给出了从所有交换机到其第一个交换机的平均时延参考控制器。最差情况控制器间延迟（WC_ICL）：设C是由分配给控制器的数组成的大小为q的集合。然后，WC ICL max dij15i;j2C这给出了每个控制器对之间的最大延迟。平均控制器间延迟（A_ICL）实现模型的程序的执行时间（ET）：记录实现该模型的程序所花费的执行时间实现模型的程序的平均执行时间（A_ET）：对不同q值获得的执行时间进行平均。可以注意到，现有的和提出的模型都是为了最小化WCL_F度量而开发的，并且提出的模型是专门为了减少执行时间（ET）而开发的。因此，这三个指标，即，WCL_F、ET和A_ET在这项工作中被视为主要指标，其余指标即，WCL_FF、AL_FF、WC_ICL和A_ICL被视为次要指标。4. 结果和讨论4.1. 实验装置MILP-FFCCPP和SA-FFCCPP都是在不同的网络上评估的，这些网络的信息在互联网拓扑动物园（Knight等人，2011年）。在实验中，三个小网络（即，AARNET：19个节点，FCCN：23个节点，AT T：25个节点），三个中型网络（即，OS 3E：34 个节点，BT 北美（BTNA）：36个节点，GEANT：40个节点），以及两个更大的网络（即，IRIS：51个节点，GARR：61个节点）考虑了给定每个网络中存在的链路以及网络中每个节点的纬度和经度，确定每个链路的长度，并随后将其转换为传播延迟。然后，确定所有节点对之间的最短路径。设网络图G的代价邻接矩阵表示为D =[di j]（1≤i≤n和1≤j≤n），其中dij表示交换机si和sj之间最短路径对应的延迟。例如，AARNET网络图的成本邻接矩阵在表3中呈现，其中，时间以毫秒为单位。每个交换机的需求是在100千请求/秒到400千请求/秒的范围内随机生成的例如，AARNET交换机的需求如表4所示。假设每个控制器都可以作为软件在具有10 Gbps接入带宽的服务器上运行。根据OpenFlow v1.2规范，PACKET_IN消息的大小为了评估MILP-FFCCPP，使用MATLAB生成MILP文件，该文件作为CPLEX优化器的输入这两个模块- els MILP_FFCCPP和SA-FFCCPP都是在英特尔至强E5-2630处理器上实现的，时钟速度为2.4GHz，内存为32 GB。4.2. 实验结果假设至多一个控制器可能遇到故障（即，K= 2）。MILP-FFCCPP和SA-FFCCPP两个模型在三种网络上进行小型、中型和大型网络通过采用不同的Q值（即，控制器数量）。A ICL¼1Xdi;j2Cð16Þ4.2.1. 对拟议和现有模式的评价，主要度量这两种模型在执行时间方面进行了比较，这给出了每个控制器对之间的平均延迟。图中所示图1至图3中所示的WCL_F度量。四比六。i2Vi2VIJP. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5729表3AARNET网络图的代价邻接矩阵。表4为AARNET交换机生成的需求。开关12345678910需求155.04323.26263.45180.21138.35108.07195.03352.58264.74166.28开关111213141516171819需求179.14388.19123.83208.6148.28174.37154.12232.57147.19图1.一、MILP-FFCCPP和SA-FFCCPP在较小网络（a）AARNET（b）FCCN（c）AT T上的执行时间比较从图1、图2和图3中可以观察到，SA-FFCCPP的执行速度比MILP-FFCCPP快得多同时，SA-FFCCPP产生接近最优的解，这意味着由 SA-FFCCPP 获 得 的 WCL_F 度 量 等 于 或 更 接 近 MILP-FFCCPP 的WCL_F度量，这可以从图4、图5和图6中看出。 六、P. Aravind，G. P.Saradhi Varma和PVGD普拉萨德·雷迪沙特国王大学学报5730图二、MILP-FFCCPP和SA-FFCCPP在中型网络（a）OS 3E（b）BTNA（c）GEANT上的执行时间比较图3.第三章。MILP-FFCCPP和SA-FFCCPP在较大网络（a）IRIS（