SDN中基于动态迁移优化的控制器负载均衡算法

朱国晖，史思潮，翟鹏宇

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

软件定义网络(Software Defined Network,SDN)作为一种新型的网络架构[1]，实现了控制平面和转发平面分离，通过控制器管理整个网络，解决了传统网络僵化的问题。随着大数据、云计算等网络技术的发展，现有的单控制器部署架构不能满足网络的扩展性和灵活性[2-3]。针对此问题，研究者提出了将SDN网络划分成多个独立的子域，并且每个子域中都由一个主控制器控制，通过控制器多域解决网络的扩展性和灵活性问题。但随着网络规模不断扩大，对流量的需求也急剧增加，流量的分布在时间和空间上存在极大的不确定性。当网络中某一时刻或者某一块区域的流量出现激增或骤减的情况时，易导致控制器的负载不均衡问题。

国内外研究者针对控制器的负载不均衡问题使用不同的策略、算法进行了研究。文献[4]中首次提出迁移交换机解决控制器负载不均衡问题。在选择迁入域时将交换机与控制器之间的时延作为选择标准，分析了控制器部署在不同的位置对迁移交换机产生的影响。文献[5]中提出多控制器负载均衡策略，主要研究了控制器之间通信产生的时延对网络的影响，最终实现控制器负载均衡的效果。但是，没有提前计算出迁移的交换机数量，当发生多个交换机迁移可能会产生交换机冲突等问题。文献[6]在分布式SDN架构中提出安全交换机迁移策略，在部署网络之前提前计算出过载概率较大的控制器。当网络流量出现激增时，通过快速卸载过载概率较大的控制器实现控制器负载均衡，但在预测控制器负载时，增加了网络通信的开销。文献[7-8]提出的算法都是通过周期性的采集控制器和链路的流量情况，计算控制器的负载，降低了通信成本。文献[9]中提出一种两阶段式的策略。将控制器的负载最大为迁出域，通过遗传算法选出负载最小的控制器的子域作为迁入域，并给迁移的交换机规定合理的数量，避免了多个交换机在迁移过程中产生的冲突问题。文献[10]提出动态交换机迁移策略。通过动态信息采集(Dynamic Information Acquisition，DIA)算法动态地采取控制器之间的信息，并判断是否过载。再通过对迁入域和交换机选取算法的优化，实现交换机的迁移，达到负载均衡的效果。文献[11]中交换机迁移通过设置博弈论实现控制器负载均衡。博弈论是由过载控制器子域的邻域组成，并综合交换机迁移成本和时延问题，通过粒子群算法选出目标控制器，实现交换机迁移。

综合分析以上研究，针对多个控制器负载不均衡问题主要是通过迁移交换机解决，但当网络需要迁移多个交换机时，在迁移时又会产生冲突问题，导致迁移交换机效率较低。为了解决控制器负载不均衡问题，拟提出基于动态迁移优化(Dynamic Migration-Optimized Load Balancing，DMOLB)的控制器负载均衡算法。该算法针对多个控制器负载不均衡问题，先计算出控制器的负载，并判断出是否过载；再将过载的控制器所在的子域作为迁出域，选择出负载较低且与迁移交换机最近的控制器所在的子域为迁入域；最后，设置子域的迁移度和交换机有效期，完成交换机迁移。同时，通过与负载通告(Load Informing based Load Balancing，LILB)算法和阶段式控制器负载均衡(Stage Controller Load Balancing，SCLB)算法相比，验证该算法的性能。

1 相关研究

在SDN网络中，将网络划分为多个子域，每个子域中由一个控制器控制，并且各个子域之间通过物理链路进行互联。具体的SDN多域网络拓扑图如图1所示。

图1 SDN多域网络拓扑图

利用图论理论，将整个网络可以表示为有向图图G=(V,E)，V为所有节点的集合，E为所有链路的集合。将SDN网络分成M个子域，每个子域都有一个控制器和多个交换机相连，当M个子域中有M个控制器，表示为C={c1,c2,…,cM}，交换机的个数为N个，表示为S={s1,s2,…,sN}，交换机和控制器连接的方式为

(1)

在SDN网络的模型中，控制器分为最高控制器和常规控制器，具体分层式SDN控制器负载均衡架构如图2所示。

图2 分层式SDN控制器负载均衡架构

最高控制器包括负载计算模块、负载信息收集模块即负载分析和决策模块。负载信息收集模块主要负责收集常规控制器的负载情况，并且将负载信息传递为分析和决策模块，由此模块分析并决定是否迁移交换机，并将最终决策下发给常规控制，由常规控制器执行交换机迁移策略。

常规控制器主要负责计算控制器的负载，并将负载信息传递给最高控制器，通过最高控制下发决策实现交换机迁移。

分层式SDN控制器负载均衡算法具体过程包括以下4个步骤。

步骤1常规控制器通过固定的周期收集自身的负载情况，并判断负载是否超过设定的阈值。如果超过，立即将过载信息传递给最高控制。

步骤2最高控制器收集到常规控制器的超载信息，并且会收集整个SDN网络的常规控制器的负载信息，并计算整个网络控制器的负载均值。通过迁移域的策略选出迁入、迁出域和迁移的交换机，并将迁移策略下发给常规控制器。

步骤3常规控制器接收到最高控制器发送的迁移策略，完成交换机的迁移。

步骤4常规控制器完成交换机的迁移任务，至此迁移完成后会出现新的网络拓扑结构。

2 DMOLB算法设计

考虑到迁移通信开销和迁移冲突问题，将基于DMOLB的控制器负载均衡算法分为控制器负载、选择迁移域及设定迁移度和有效期等3个阶段。

2.1 控制器负载阶段

在分层式的SDN网络中，控制器的负载主要包括待处理的Packet-in消息，不同子域之间控制器相互交流的通信开销，维护域内所需要的流量和安装流表代价等4个部分[12]。

1)待处理的Packet-in消息。控制器负载的主要来源为交换机向控制器发送的Packet-in消息数目[13]。SDN网络中子域Gi所接收的Packet-in请求消息的数目、子域中交换机的平均请求度及M个子域中Gi相对于其他子域请求度的表达式分别为

(2)

(3)

(4)

式中：ni为子域中交换机的个数；rsk表示交换机sk向控制器发送请求的数量。

2)不同子域之间控制器相互交流的通信开销。每个子域间的控制器需要交流，控制器之间并不能将子域的请求全部都处理，因此会产生通信开销。控制器ci与控制器ci产生的通信开销的表达式为

(5)

式中：dik表示控制器ci与交换机sk之间的跳数，如果控制器离交换机越远，则需要流量越多；λ为控制器中交换机的平均流量。

3)维护域内所需要的流量。在每个子域中，控制器与交换机之间也产生通信需要定期维护和管理。子域内控制器与交换机产生的通信成本的表达式为

(6)

式中，θ为控制器之间告知对方状况的平均代价，当θ<λ，表示控制器之间不能对子域之间的消息进行处理。

4)安装流表代价。当交换机发送消息产生一个新的流时，发送到控制器，则控制器需要安装一个新的流表项与之匹配。因此，会产生安装代价。安装流表项产生的代价的表达式为

(7)

式中，f表示Pack-in数据包的大小。

每个子域控制器的负载为Lci，表示为在子域Gi中的ci控制器的负载，主要由上面4部分的加权和所得，其表达式为

(8)

式中，ω1～ω4表示对应的权值。

将式(8)中权值和做归一化处理，和为1，表达式为

(9)

并且在SDN网络中每个子域中只能有一个控制器，表示为

(10)

通过式(8)求得加权和就可以计算出常规控制器的负载情况，并根据与设定的阈值作比较，判断控制器是否过载。如果发生过载，则进行迁移域选取阶段。

2.2 选择迁移域阶段

一般对于迁入域的选取只考虑负载情况，负载最小的选为迁入域。一是考虑迁入域控制器的负载是否为最小；二是考虑迁入域中交换机和控制器的距离是否较小，因为距离最近，时延则最小。控制器的负载综合计算公式为

CT=μ1(Lt,maxPavg-Lt)-μ2R

(11)

式中：μ1,μ2参数为权值，权值和为1；Lt表示t时刻的负载；Lci表示控制器的负载值；Lci,max表示控制器负载最大值；pavg表示全网控制的平均负载情况；R为交换机到控制器之间的跳数。

将控制层的所有控制器负载情况计算出并降序排序，依次从高到低选取值高的作为迁入域，当出现需要迁移多个交换机时，及时更新负载状态。按照以上原则依次进行交换机迁移。通过此阶段选出的迁入域，可以减少交换机迁移的开销。

选择迁移域阶段的具体步骤如下。

步骤1计算出各子域的交换机平均请求数，并将平均请求数最大的子域选为迁出域。

步骤2在其他相邻的子域中根据式(11)计算CT。

步骤3将CT值从大到小降次排序。

步骤4选择CT值最大的为迁入域。

2.3 设定迁移度和有效期阶段

通过选择迁移域阶段选出的迁移域，在此基础上设定迁移度和有效期，实现交换机的迁移。

1)交换机的迁移度。计算需要将子域G0中迁移到子域G1中交换机的数量。交换机的迁移度的表达式为

(12)

2)交换机的有效期。交换机在迁移的过程中作为有用迁移交换机的周期数。交换机的有效期的表示式为

Y(sh)=Z(sh)-D(sh)

(13)

式中：Z(sh)表示为交换机在迁移过程中轮询周期总数；D(sh)表示为目前的周期数。

通过此阶段设定的迁移度和有效期，迁移度可以计算出迁移交换机的数量，然后选择有效期内的交换机迁移，控制器负载大于阈值时，重新选择交换机。否则，交换机迁移结束。迁移度和有效期的设置可以避免交换机在迁移过程中产生冲突。

设定迁移度和有效期阶段具体步骤如下。

步骤1计算迁入、迁出域的子域迁移度，确定交换机迁移数目。

步骤2计算迁移交互机的有效期。

步骤3选择有效期内的交换机进行迁移。

步骤4判断控制器是否过载，如果没有过载，交换机迁移结束；如果过载，返回步骤3，重新选择交换机迁移，创建新的SDN网路拓扑。

3 仿真结果分析

3.1 实验环境设置

实验平台为Ubuntu 16.04系统,控制器为Floodlight,在Mininet平台搭建拓扑图，包括1个最高控制器控制5常规控制器和11个交换机。具体的实验的网络拓扑图如图3所示。

图3 网络拓扑图

参数设置类比文献[14]设置的每个子域中控制器的功能全部一样，控制器的容量设为10 MB，每个交换机平均产生流的速率设为150 kB·s-1。控制器中权值系数的比重设置为0.4∶0.2∶0.2∶0.2。控制器4的负载超过设定的阈值。控制器1、控制器2、控制器3和控制器5的负载平稳，在设定的阈值内,并在30 s的情况下加大控制器4的数据流，模拟实际出现负载激增的情况。

3.2 仿真结果分析

为了验证该算法的性能，在相同的实验环境下，通过与文献[15]中LILB的算法和文献[9]中基于迁移优化的SCLB算法做比较，分别从交换机的通信开销、传输时延和控制器资源利用率等3个方面验证算法的性能。

1)控制器负载情况。根据网络拓扑图可以看出，最高控制器控制5个常规控制器，常规控制器的负载时刻发生变化，需要周期的计算常规控制器的负载并判断是否过载。算法主要研究5个常规控制器负载变化情况，具体过程如图4所示。

图4 控制器负载情况

由图4可以看出，在初始阶段给每个控制器产生新的流，使控制器有负载，在30 s时增大控制器4的流，使控制器过载。通过控制器负载阶段计算控制器的负载，再在选择迁移域阶段将控制器4作为迁出域。最后，将选择迁移域阶段选出的控制器1和控制器2作为迁入域。通过设定迁移度和有效期阶段将选定的交换机迁移到该控制器下，实现了控制器的负载均衡。整个负载均衡过程持续了5 s，避免了产生控制器负载震荡或者迁移效率低等问题。

2)交换机迁移通信开销。在网络中控制器与控制器之间和交换机与控制器之间都会产生通信开销，3种算法的通信开销对比具体如图5所示。

图5 交换机迁移通信开销

由图5可以看出，DMOLB算法与LILB、SCLB算法相比，交换机迁移通信开销降低了38%和7.8%。

3)交换机与控制器之间的传输时延。在交换机迁移的过程中，交换机与控制器之间的传输时延随Pack-in消息请求速率改变情况如图6所示。

图6 交换机与控制器之间的传输时延

由图6可以看出，当交换机的请求速率较小时，3个策略产生的传输时延基本一致。当Packet-in消息的请求速率不断增加时，LILB算法需要频繁收集网络信息，使得交换机和控制器的交互增多。因此，时延增加的比较明显。SCLB算法通过给设置迁移交换机的数量，避免流量拥堵，传输时延增加较少。DMOLB算法通过交换机迁移设置有效时间，避免交换机迁移时产生冲突，并可以有序迁移。因此，传输时延效果比以上两种算法较好。

4)控制器资源利用率。控制器资源利用率也是衡量算法性能的重要标准之一，3种算法的控制器资源利用率如图7所示。

图7 控制器资源利用率

由图7可以看出，DMOLB算法和LILB、SCLB两种算法相比，对控制器的资源利用率稍有提高。该算法基于在全网搜索迁移域，并能合理制定迁移交换机的数量，避免在迁移过程中产生冲突。因此，控制器的资源利用率有所提高。

该算法与LILB算法和SCLB算法相比，时延和交换机的开销有所降低，并且也提高了控制器的资源利用率。但是，在算法运行时间方面有所增加，因为在考虑迁入域的过程，不仅考虑了迁入域的负载，也将迁入域的距离考虑进去。因此，增加了算法的时间复杂度。

4 结语

针对SDN网络中多控制器负载不均衡问题，提出了基于动态迁移优化的控制器负载均衡算法。该算法首先提出了具有最高控制器的分层式架构，通过最高控制器控制常规控制器，减少了常规控制器之间的通信，降低了通信开销。然后，优化了迁入域的选取标准，综合考虑迁出交换机与迁入控制器的距离和迁入控制器的负载两种因素，降低了迁移成本。该算法总共分为3个阶段，控制器负载阶段计算出控制器的负载，并将其作为目标函数；选择迁移域阶段对迁移域选取标准进行优化，并选出迁入迁出域；设定迁移度和有效期阶段对迁出域中的交换机设置迁移度和有效期，避免了交换机迁移产生冲突，最终实现多控制器负载均衡。实验仿真结果表明，验证该算法对于LILB算法与SCLB算法，降低了交换机迁移过程的通信开销和时延，提高了控制器的平均负载均衡率。