SDN 中基于时延优化的多控制器部署方案

张联镇，黄传河＋，曾毓珑，张 海，贾永宏

（1.武汉大学 计算机学院，湖北 武汉430072；2.华为技术有限公司，广东 深圳518129）

0 引 言

软件定义网络［1］（software－defined networking，SDN）技术将网络的控制平面与数据平面分离开来，其可编程特性使我们能够动态地配置并管理整个网络。在SDN 中，控制器负责整个网络的集中化控制，对于把握全网资源视图、改善网络数据交付都具有非常重要的作用。随着SDN 在大规模网络中的部署［2］，单一集中式的控制器已无法满足来自全网所有交换机的流处理请求，SDN 在大规模网络中的部署面临着来自控制平面扩展性方面的严峻挑战［3］。目前，解决SDN 面向大规模网络部署的趋势是，通过分布式的方式，将多个控制器部署到多个控制域内，形成一个分布式的管理控制平面，各控制器之间进行协同式工作［4］。然而，这样一来也带来了一些新的问题：对于一个给定的网络拓扑，需要部署多少个控制器，以及如何部署这些控制器才能在优化流表建立时间的同时获得较小的控制器之间的同步时间开销。

1 相关工作

关于多控制器的部署问题，国内外已有相关的研究，文献 ［5］中提出基于平均时延和最坏情况传播时延的控制器部署衡量指标，并在真实的网络环境中分析了其对控制器部署的影响。文献 ［6］提出了一系列的控制器部署算法，以最大化SDN 的可靠性作为控制器部署标准。文献［7］分析了SDN 中，影响多控制器部署的不同类型的弹性衡量指标之间的权衡问题，并提出了一个弹性的基于帕累托分布的控制器优化配置构架方案，以解决多控制器的部署问题。在所有以上提出的解决方案中，并没有直接考虑到控制器与控制器之间的同步时延开销。控制器之间需要定期进行信息同步，以便各控制器维持一个全局的网络状态信息，当网络规模较大，控制器数目较多时，控制器之间的同步开销将是控制器部署过程中需要考虑的重要因素之一。

与上述方案相比本文首先评估对于给定的网络拓扑其所需部署的控制器的个数，在使用基于聚类思想的控制器部署方法，根据最小平均时延的原则将控制器初步部署到网络中之后，向网络中输入动态数据流，通过最小化网络的流表建立时间和控制器间的同步时延开销来进一步优化控制器的部署。我们将这一优化问题看作是整型线性规划问题，并提出了一种元启发式搜索算法来解决这一问题，以便在优化流表建立时间的同时获得较小的同步时延开销，从而实现对两者的权衡，并确定控制器的最终部署位置。

2 控制器部署模型描述

在SDN 中，当一个新的数据包到达交换机时，交换机首先检查其流表，看是否有匹配的流表项，如果查找到匹配的流表项，交换机根据流表项规定的操作进行相应的转发，如果没有查找到匹配项，交换机便会向控制器发送一个packet－in路径请求消息，以获取转发路径。控制器通过其维持的网络拓扑信息，为该数据包计算本域范围内的转发路径，并将转发规则下发安装到与该路径相关的交换机的流表中。此时存在两种情况，当此数据包的目的地 （这里所说的目的地指的是交换机，另外，下文所提到的源目的地址除特别说明之外，都指的是交换机）在本控制域范围内时，与该转发路径相关的各交换机按照指定的转发操作将数据包转发至目的地；而当目的地不在本域范围内时将涉及到跨域通信问题，如图1所示，当控制域D1内的交换机i收到一个新的目的地址为控制域D2内的交换机l的数据包时，如果没有相应的匹配项，交换机i就向控制器c1发送一个路径请求消息。控制器c1为此数据包计算本域内的转发路径，这里我们假定转发路径为i→j，然后将转发规则下发给交换机i和j。此时数据包由交换机i转发至交换机j，最终由交换机j转发至交换机k。交换机k收到此数据包后，检查其流表，如果没有匹配项，交换机k就向控制器c2发送路径请求消息，控制器c2以同样的方式为此数据包计算转发路径，并将转发规则下发给交换机k和l，最终该数据包被转发至目的交换机l。整个转发过程中经历了两次路径请求，4次流表下发的过过程。

定义1 为了便于描述，将网络拓扑等效为一个连通图

图1 跨域数据包转发流程

G （V，E），V＝ ｛1，2……，N｝表示交换机集合，E 为交换机之间的链路集合，N＝｜V｜为交换机个数，m 为所需部署的控制器数，C ＝ ｛c1，c2，…cm｝表示控制器集合，d （i，j）表示交换机i与交换机j之间的最短路径时延。Tv表示交换机流表的生存时间，Pc表示控制器c每秒能够处理的最大路径请求次数，我们假定所用到的各个控制器的处理能力是相同的。

在向G 中部署控制器时，我们假定每一个交换机所在的位置都有可能成为控制器的部署位置，即控制器部署在交换机所处的位置上，但控制器与交换机并不重合放置，且控制器部署位置所对应的交换机在该控制器所管理的交换机范围内，它们之间的时延忽略不计。

定义2 δ表示控制器与交换机之间正常通信所允许的最大通信时延，Mc＝ ［［Miij］］N×N表示T 时间内控制器c收到的平均路径请求矩阵，其中Mij表示T 时间内交换机i与交换机j进行通信时产生的平均路径请求次数。Lij表示交换机i与交换机j通信时所经过的交换机的集合，交换机i与交换机j也包括在内。R ＝ ［Ric］N×k表示交换机分配矩阵，其中Ric＝1表示交换机i被分配给控制器c，否则Ric＝0。

在向网络中部署多控制器时，会产生很多类型的时延开销，本文主要考虑流表建立时间和控制器之间的同步时延开销。我们将流表建立时间分为两个部分：请求路径时延，如图1中①和④所示；流表下发时延，如图1 中②、③、⑤和⑥所示。对于控制器c来说，T 时间内其域内的总的请求路径时延Dcreq为

其中k为第一个满足k∈Lij且Rkc＝1的交换机，则整个网络的路径请求时延Dreq为

T 时间内，控制器c所在域内的流表下发时延Dcdis为

则整个网络的流表下发时延Ddis为

通过式 （2）和式 （4）可以得到总的流表建立时间Df

在多控制器环境下，控制器之间需要进行信息同步，以便各控制器维持一个全局的网络状态信息。我们假定控制器间每隔Ta时间进行一次同步更新，则控制器之间进行同步的时延Dsyn为

通常，在控制器的部署过程中，为了提高整个网络的性能，我们总希望网络的流表建立时间尽可能短，控制器之间的同步时延开销尽可能的小。因此，本方案需要实现流表建立时间与控制器之间的权衡，我们将这一问题看成是一个求最小值的优化问题，待优化的目标函数Fmin为

式中：λ——常量系数，且满足0≤λ≤1，其值可以根据网络对各时延的要求比重不同进行设定。优化过程中必须满足的约束条件如下

其中式 （8）表示每一个交换机都只由一个控制器控制，式（9）表示任意交换机与控制器之间的时延必须在其上界之内，式 （10）表示确保每一个控制器都能够处理来自本域内的所有交换机产生的路径请求数，式 （11）表示交换机k是否分配给控制器c，若是，则为1，否则为0。

3 控制器部署方案

本部分首先评估给定网络拓扑所需部署的控制器的个数，然后通过基于聚类思想的控制器部署方法，根据平均时延最小的原则将控制器初步部署到网络中，再向网络中输入动态数据流，分析各控制域内控制器收到的平均路径请求次数，对请求次数超过控制器所能处理的域进行调整，最后运用蜂群算法思想以最小化Fmin为目标进一步优化控制器的部署，从而确定控制器的最佳部署位置。

3.1 控制器个数的确定

根据式 （12）我们可以近似地得到所需部署的控制器个数m 为

式中：α——一个常量系数，网络管理人员可以根据需求进行相应的设定。

3.2 基于聚类的控制器部署方法

我们将控制器部署问题类比为聚类分析问题，每一个聚类好比一个控制域。本文假定每一个域内有且只有一个控制器。我们使用基于聚类的控制器部署方法将控制器初始的部署到网络中，把每一个聚类的中心作为控制器的部署位置，使用平均时延作为选取聚类中心的评判标准，每一个聚类的平均时延Lavg为

其中j表示聚类的中心位置，Rij＝1，表示交换机i属于以j为聚类中心的聚类，Rij＝0，表示交换机i不属于该聚类。

为最大限度消除初始控制器部署位置对最终聚类结果的影响，加快其收敛速度，将交换机集合V 按照度的大小进行降序排列，选择度较大且距离相对较远的m 个交换机所在位置作为控制器的初始部署位置，执行步骤如下：

步骤1 将选好的m 个交换机所在位置作为集合C 中控制器的初始部署位置；

步骤2 遍历剩下的N－m 个交换机，根据距离最短原则将交换机分配给距其较近的控制器，形成m 个控制域；

步骤3 遍历每个控制域内的所有交换机，根据式（14）计算Lavg的值；

步骤4 选取使得Lavg值最小的交换机所在位置作为域内控制器的新的部署位置，形成新的控制器集合C；

步骤5 不断重复步骤2～步骤4，直到控制器集合C不再发生变化。

3.3 控制器部署优化

在基于聚类的控制器部署方法的基础上，向网络中输入动态数据流，根据蜂群算法［8］思想，以最小化式 （7）为目标，进一步优化控制器的部署。由于使用基于聚类的控制器部署方法得到的结果可能存在某些域，其域内交换机产生的总的路径请求次数超过控制器能够处理的数目，因此在进一步优化前，需要对每一个域进行检测，对超出控制器处理能力的域作出相应的调整。对于路径请求次数超过控制器处理能力的控制域，不断将域内产生路径请求次数最多的交换机分配给其它能够处理这些请求的控制器，直到域内的路径请求总数在控制器的处理能力范围之内，其域内的每一个交换机i所产生的路径请求次数Sireq为

具体的调整策略步骤如下：

步骤1 分析每一个控制器收到的平均路径请求矩阵，将不满足约束条件式 （10）的控制器加入到控制器集合Cu中；

步骤2 初始化链表list为空，从集合Cu中取出一个控制器c，将控制器c所在域内的所有交换机按照式 （15）计算后进行降序排序，并放入list中；

步骤3 从list中依次选择交换机i，将i分配给剩余处理能力与i所产生的路径请求次数相近的且i与其之间的时延小于δ的控制器；

步骤4 重复步骤3，直到控制器c能够满足约束条件式 （10）为止；

步骤5 重复步骤2～步骤4，直到集合Cu为空。

用调整好后的交换机分配信息来初始化交换机分配矩阵R，并重新计算每一个域内的路径请求矩阵，为进一步优化工作做好准备。多控制器部署优化问题与蜜蜂采蜜行为对应关系见表1。

表1 多控制器部署优化问题与蜜蜂采蜜行为对应关系

假 定 初 始 蜂 群 B 的 总 数 为Z， 则 有 B ＝（b1，b2，…，bi，…，bZ），其中bi＝ （ci1，ci2，…cim），称其为第i个可行的控制器部署解，每一个解都是一个m 维向量，m 为所需部署控制器的个数。为加快算法的收敛速度，首先根据基于聚类的控制器部署算法得到的控制器的初始部署位置初始化蜂群B，即将初始控制器部署的位置集来初始化B 中的一个解，并依次从每一个控制器c的初始部署位置附近随机选取一个位置作为B 中的下一个解，直到B中的Z 个解都被初始化。B 中每一个解的收益度函数为

式中：Fimin——第i个解所对应的Fmin的值，收益度越高，Fmin的值越小。我们使用轮盘赌的方式来决定跟随蜂转变为引领蜂的概率，其概率公式为

侦查蜂根据以下3种方式进行蜜源的搜索：

方式1：从 ［1，m／2］中随机选取一个整数作为随机选取解的分量个数，在每一个被选分量对应的控制器所部署位置的h跳范围内随机选取一个控制器部署位置，形成一个新的蜜源位置，计算新的蜜源的收益度，如果大于原来的收益度，则用新的位置代替原来的位置，否则什么也不做。

方式2：从 ［m／2，m］中随机选取一个整数作为随机选取解的分量个数，在每一个被选分量对应的控制器所在的控制域范围内随机选取一个控制器部署位置，形成一个新的蜜源位置，计算新的蜜源的收益度，如果大于原来的收益度，则用新的位置代替原来的位置，否则什么也不做。

方式3：在解的每一个分量对应的控制器所在的控制域范围内随机选取一个控制器部署位置，形成一个新的蜜源位置，用新的位置代替原来的位置。

算法的基本步骤如下：

步骤1 根据式 （16）计算每一个蜜源 （可行多控制器部署位置）所对应的收益度值，并将其降序排列，将前半部分指定为引领蜂，后半部分指定为跟随蜂；

步骤2 对每只引领蜂，按照方式1在其邻域内搜索新的蜜源；

步骤3 对于每一只跟随蜂，以式 （17）得到的概率转变为引领蜂，并根据方式1在其邻域内搜索新的蜜源，而对于剩下的跟随蜂，根据方式2的方式搜索新的蜜源；

步骤4 如果某只引领蜂在连续limit次迭代后都没有任何变化，且其所对应的收益度在整个蜂群B 中不是全局最优的，则根据方式3产生新的蜜源；

步骤5 若当前迭代次数小于规定的最大迭代次数MAX，则转到步骤1，否则停止迭代；

步骤6 输出全局最优的蜜源位置，该蜜源位置即为控制器的部署位置。

4 仿真与结果

为了验证本文所提方案的有效性，我们建立了一个模拟器来模拟交换机与交换机、交换机与控制器和控制器与控制器之间的传播时延。该模拟器是事件驱动的，每当产生一个新的路径请求时，相应的控制器立即响应该请求。通过文献 ［9］提供的NOX 控制器参数来模拟控制器的处理能力。实验中用到的拓扑为ISP 拓扑集中选取的一个节点个数为157链路条数为341的拓扑。我们假定拓扑中的每一个节点都为OpenFlow 交换机。本文采用iperf发包工具产生TCP数据包并输入到网络拓扑中，数据包的源目的地址都是随机的，为了使得模拟更接近于真实，在产生TCP数据包流时，我们根据文献 ［10］中提供的方式来确定数据流的大小，数据流的发送间隔以及并发流的数量。为更好的优化流表建立时间，本文引入文献 ［11］中提出的一个控制器监测工具OFSim，它能够记录各控制器收到的来自各交换机发出的路径请求次数、每一次请求的源目的地址以及控制器为此次请求计算出的路径所包含的交换机集合等信息。在仿真实验中，我们通过计算平均流表建立时间和控制器之间的同步时延开销来评估本文所提控制器部署方案的性能。

我们根据λ的不同取值进行仿真实验，观察平均流表建立时间和控制器间同步时延情况，仿真结果如图2所示，其中图2 （a）表示的是λ的取值与平均流表建立时间之间的关系图，图2 （b）表示的是λ的取值与控制器间进行一次信息同步时的同步时延开销之间的关系图。

图2 λ取不同值对应的平均流表建立时间和控制器间同步时间

从图2中可以看出，在控制器部署优化前，平均流表建立时间和控制器间的同步时延是一个固定值，因为控制器部署位置并不随动态流的输入而进行相应调整，它们是固定的。优化处理后，当λ向0趋近即优先考虑控制器与控制器之间的同步时延时，网络中的流表建立时间逐渐增大，控制器之间的部署位置更加趋近，而当λ向1趋近即优先考虑流表建立时间时，控制器间同步时延开销逐次增加，控制器之间的部署位置更分散一些。两者之间的比重可以根据网络拓扑规模以及对网络各性能指标需求不同来设定，具有较强的灵活性。

图3表示的是当λ＝0.7时，平均流表建立时间与各控制器间进行一次信息同步时的同步时延开销之间的关系图。从图3中可以看出，经过优化后所得到的平均流表建立时间和控制器间同步时延都比基于聚类的控制器部署方法所得到的对应值要小。控制器间同步时延相差较大是因为前者在优化平均流表建立时间的同时将控制器之间的同步时延开销考虑在内。平均流表建立时间比用基于聚类的控制器部署方法所得到的值小，充分体现了基于蜂群算法思想的优越性，它能够有效的跳出局部最优解，而得到全局的最优解，进而在优化平均流表建立时间的同时获得较小的控制器间的同步时延开销。

图3 平均流表建立时间和控制器间同步时延

5 结束语

本文首先使用基于聚类的方法将控制器部署到网络中，然后向网络中输入动态数据流，通过蜂群算法思想来权衡流表建立时间与控制器间同步开销时延，从而进一步优化控制器的部署。研究发现，更注重流表建立时间时，控制器部署的位置相对分散，而优先考虑控制器间同步时延时，控制器之间的部署位置更加集中。在参数λ确定的情况下，本文多控制器方案能够很好地权衡流表建立时间与控制器间同步时延开销，使整个时延开销最小。

［1］McKeown N.Software－defined networking ［J］.INFOCOM Keynote Talk，2009，418 （1）：1－12.

［2］McCauley J，Panda A，Casado M，et al.Extending SDN to large－scale networks［J］.ONS，2013，58 （2）：50－51.

［3］Yeganeh SH，Tootoonchian A，Ganjali Y.On scalability of software－defined networking ［J］.Communications Magazine，IEEE，2013，51 （2）：136－141.

［4］Yazici V，Sunay MO，Ercan AO.Controlling a software－defined network via distributed controllers［C］／／Proceedings of the NEM Summit，2012：16－20.

［5］Heller B，Sherwood R，McKeown N.The controller placement problem ［C］／／Proceedings of the First Workshop on Hot Topics in Software Defined Networks.ACM，2012：7－12.

［6］Hu Y，Wendong W，Gong X，et al.Reliability－aware controller placement for software－defined networks ［C］／／IFIP／IEEE International Symposium on Integrated Network Management.IEEE，2013：672－675.

［7］Hock D，Hartmann M，Gebert S，et al.Pareto－optimal resilient controller placement in SDN－based corenetworks［C］／／25th International Teletraffic Congress.IEEE，2013：1－9.

［8］Karaboga D，Akay B.A comparative study of artificial bee colony algorithm ［J］.Applied Mathematics and Computation，2009，214 （1）：108－132.

［9］Tootoonchian A，Gorbunov S，Ganjali Y，et al.On controller performance in software－defined networks ［C］／／USENIX Workshop on Hot Topics in Management of Internet，Cloud，and Enterprise Networks and Services，2012：8－14.

［10］Gebert S，Pries R，Schlosser D，et al.Internet access traffic measurement and analysis ［M］／／Traffic Monitoring and Analysis.Berlin：Springer Berlin Heidelberg，2012：29－42.

［11］Kong X，Wang Z，Shi X，et al.Performance evaluation of software－defined networking with real－life ISP traffic ［C］／／IEEE Symposium on Computers and Communications.IEEE，2013：541－547.