0 引言

随着网络规模的不断扩大，传统的网络架构已经无法满足人类的需求，新的网络架构软件定义网络(Software Defined Network, SDN)^[1]应运而生。

SDN的设计思想主要是将网络的控制功能和转发功能分离，使得控制平面能够更有效地提供统一的网络监控能力。作为数据转发控制的核心，控制平面表现出越来越重要的作用。当网络规模增大，控制器接收的流超出其最大负载时，控制器将无法继续正常工作。目前，解决控制器负载不均衡问题主要有以下两种方法：一是通过为控制器配置多冗余容量来应对大量突发流，但是这种方法会造成资源浪费以及增加系统开销；二是增加控制器数量，但是多控制器可能会存在某一个或者某些控制器发生负载时，其他控制器却处于不工作或轻负载的状态，这种控制器之间负载的不均衡，会导致网络性能的下降。

为了解决多控制器之间负载不均衡、控制器之间通信开销大以及系统吞吐量低等问题，本文提出基于SDN的分层式控制器负载均衡机制，旨在提供一种两层控制器架构，通过顶层超级控制器选择出要迁移的交换机以及将其迁移到目标控制器上，以降低控制器之间的通信开销，提高系统吞吐量，达到更好的负载均衡效果。

1 相关研究

针对多控制器之间的负载不平衡问题，文献[2]提出一种用于控制器负载均衡的动态和自适应算法(Dynamic and Adaptive algorithm for controller Load Balancing, DALB)，文献[3]提出一种基于多个分布式控制器的负载通知策略的负载平衡机制，这两种方案均减少了由网络传输引起的决策延迟；但是该策略周期性收集负载信息增加了控制器之间的通信开销。文献[4]提出用于可扩展SDN的多控制器的负载分配方案，实现了可扩展；但并未考虑相邻控制器也过载的情况。文献[5]提出一种新颖的负载平衡策略, 使用扩展服务器动态分配流量，缓解了负载，提高了吞吐量。文献[6]提出一种用于SDN控制平面的分布式负载平衡算法，其目的是动态平衡SDN控制器集群上的控制流量，从而最大限度地减少延迟、缓解负载，并提高整体集群吞吐量。上述方案都是基于单层控制器的负载均衡方案，虽然可以缓解控制器负载，但是无法高效解决各个控制器之间的负载平衡问题，很难满足大型网络的需求。

针对单层控制器负载平衡时通信开销大、吞吐量低等问题，文献[7]提出了一种控制器协同负载平衡策略(COoperative Load BAlancing Scheme for hierarchical SDN controllers, COLBAS)，文献[8]提出balanceflow概念，两种方案均采用两层控制器架构，通过超级控制器与常规控制器协同完成负载均衡；但是常规控制器群需要周期性向超级控制器发送负载信息，增加了系统开销。类似地，文献[9]提出一种基于集群控制器的交换机迁移机制的动态负载均衡方法，由于协调器节点周期性收集负载消息，同样会增加系统开销。文献[10]提出一种软件定义网络的分布式层次控制器平面，采用三层架构，有效解决了可扩展性和可靠性问题；但其仅仅是描述了一种层次式架构，并没有具体描述如何解决控制器之间的负载问题。文献[11]提出一种SDN的动态负载平衡架构，超级控制器与分割成簇的常规控制器进行通信，当检测到过载簇时，超级控制器将常规控制器分割成新簇，并更新常规控制器的簇矢量；但是，其仅仅是简单描绘了一种负载平衡架构，并没有验证这种架构对于控制器负载平衡的可行性。文献[12-15]的目标均是规划出流传输的最优路径，但负载均衡时，每次可供选择的路径少，且流划分粒度粗，很难达到最优效果。以上方案在大型网络中依然面临着负载均衡过程中控制器之间通信开销大以及控制器吞吐量低等问题。

2 系统模型

本文采用分层式控制平面架构进行负载均衡的研究，如图 1所示，分层式控制平面架构分为三层：物理层、域控制器层、超级控制器层。底层是物理层，包含大量连接的OpenFlow交换机或路由器(本文默认为OpenFlow交换机)，其主要功能是负责数据的转发；中间层是域控制器层，由若干域控制器组成，每个域控制器控制一个域，每个域包含若干交换机，其主要功能包括处理交换机的流转发请求、向底层交换机下发转发规则，并将其发送到超级控制器层等；顶层是超级控制器层，超级控制器层将域控制器视为设备，为域控制器提供全局网络视图，并制定相应的全局策略下发到域控制器。超级控制器层包括两个超级控制器：一个保持活动状态，另一个处于待机状态，两个超级控制器之间采用热备份策略^[16], 使得活动状态下的超级控制器在发生故障或者过载的情况下，保证冗余并保持网络可用于实时处理，因此该程序可以将恢复时间调整为最小的恢复时间。当网络规模较大时，顶层的超级控制器会处理大量信息，容易造成网络过载，此时，应保持待机状态的超级控制器被激活，由于超级控制器之间可以通过分布式协议同步全局抽象网络视图，所以待机状态的超级控制器被激活后，可以很快接收过载超级控制器下的负载较大的域控制器，从而达到负载平衡的效果。而且超级控制器之间采用文献[16]中的热备份策略进行数据同步，该策略大大降低了超级控制器之间的通信开销。

3 分层式控制器负载均衡机制

交换机可以同时连接多个域控制器，但其中只有一个是master控制器，其他都是slave控制器。每个域控制器管理SDN网络的一个域，而且每个域控制器中都包含两个组件：1)负载测量组件，负责收集本控制器的负载信息，判断域控制器的负载是否超过阈值；2)负载通知组件，负责将本控制器的负载信息发送给超级控制器。

超级控制器中包含三个组件：1)负载收集组件，负责汇总所有域控制器的负载信息；2)平衡决策组件，负责进行负载平衡决策；3)交换机迁移组件，负责迁移所选取的交换机来平衡控制器之间的负载。

本文的负载均衡机制的基本思路如下：首先，域控制器周期性测量自身的负载信息，并检查域控制器的负载是否超过预设的负载阈值，如果超过负载阈值，超级控制器向其他域控制器发送负载状态请求，其他域控制器将当前的负载状态发送给超级控制器；然后超级控制器中的平衡决策组件进行迁移决策，完成迁移后，所有的域控制器更新自身的负载信息。更新超级控制器上域控制器负载状态的过程如图 2所示。

接下来详细介绍超级控制器中的负载收集组件、平衡决策组件和交换机迁移组件，以及域控制器中的负载测量组件和负载通知组件。

3.1 负载测量组件

负载测量组件在每个域控制器上运行，用来周期性测量域控制器的负载信息，包括流表条目数(F)、交换机的平均消息到达速率(I)以及每个交换机与域控制器交互的往返时间(R)。SDN控制器的负载由许多因素组成，如处理PACKET_IN事件、安装流条目等。在不同的情况下，这些因素的比例差异很大。但是PACKET_IN事件的处理通常被认为是总体负载中最重要的部分。因此，计算PACKET_IN消息的平均到达速率来表示域控制器的负载。

3.2 负载通知组件

为了作出正确的负载平衡策略，域控制器可以周期性地向超级控制器发送自身的负载信息，这样可以减少决策延迟，但是增加了通信开销。为了解决上述问题，为每个域控制器定义一个负载阈值T，表示消息的到达速率为每秒T个消息，负载阈值根据每个域控制器自身的性能决定。当域控制器的当前负载值L超过负载阈值T时，才会将其负载信息发送给超级控制器, 这样可以避免周期性发送负载信息所带来的高通信开销。

3.3 负载收集组件

负载收集组件运行在超级控制器上，其负责收集域控制器发送的负载信息。负载收集组件收到过载域控制器的负载消息后，向过载域控制器发送确认消息，并向其他域控制器发送负载状态请求，域控制器收到超级控制器的负载状态请求后，向超级控制器发送自身负载状态，然后超级控制器将收集到的所有域控制器的负载信息汇总。

3.4 平衡决策组件

平衡决策组件首先要判断过载域控制器是否是所有域控制器中过载最重的控制器，然后决定选择哪个或哪些交换机进行迁移，并选择哪个或哪些域控制器作为目标域控制器来接收所选择的交换机。

3.4.1 最重过载域控制器的选择

在负载均衡过程中，有一个问题是不可避免的，即如果两个或者多个域控制器的负载同时超过其负载阈值，将导致它们同时进行迁移操作。如果它们同时将交换机迁移到相同的目标域控制器，可能会导致目标域控制器也过载。为了解决上述问题，本文提出了最重过载域控制器的概念，并根据式(1)选择最重过载域控制器:

$ {P_{}} = ({{L_{{\rm{Load}}}} - {T_{{\rm{Load}}}}})/{{{T_{\rm Load}}}} $

(1)

其中：P表示过载域控制器的过载比例；L_Load表示过载域控制器的当前负载值；T_Load表示过载域控制器的负载阈值。如果存在两个或多个域控制器同时过载，则根据P值对过载域控制器进行降序排列，优先选取P值最大的过载域控制器作为最重过载域控制器，并根据P值从大到小依次对过载域控制器进行迁移操作，即优先处理P值最大的过载域控制器，完成迁移操作后，在剩余的过载域控制器中再一次选取P值最大的过载域控制器进行迁移操作，直至负载平衡。如果它们的过载比例相同，采用以下约束公式：

$ \bar L = \frac{1}{n}\sum\limits_{i = 1}^n {L({B_i}} );\;\;i = 1,2, \cdots ,n $

(2)

$ \theta = \left| {1 - {L({B_i})}/{{\bar L}}} \right|;\;\;i \in G $

(3)

其中：L表示系统的平均负载；B_i表示每一个域控制器；n表示域控制器的数量；L(B_i)表示域控制器B_i的当前负载值；G表示过载比例P相同的域控制器集合；θ表示域控制器的负载偏移率。负载偏移率越大，系统的负载平衡越差。因此，当出现多个过载比例P相同的域控制器时，选取负载偏移率θ最大的域控制器进行迁移操作。通过这种方式，可以避免多个域控制器同时迁移交换机。

3.4.2 交换机选择

交换机的平均消息到达速率越大，带给域控制器的负载越大。同时，交换机中的流表条目越多，域控制器所要管理的流表就越大，域控制器的负载也就越大。此外，交换机与域控制器交互的往返时间也是影响负载的重要因素。因此，如果域控制器过载，根据上述三个因素，采用式(4)选择交换机进行迁移:

$ {H_S} = \alpha *F + \beta *I + \lambda *R $

(4)

其中：H_S表示选择迁移交换机的标准；α、β和λ表示权重系数，设置α、β和λ的值分别为0.1、0.8、0.1。如果域控制器过载，根据H_S值对过载域控制器所控制的交换机进行降序排列，并优先选择H_S值最大的交换机进行迁移。如果H_S值最大的交换机可以将过载域控制器的负载降低到负载阈值以下，则只选择该交换机进行迁移；如果不是，则按照H_S值降序排列的顺序从大到小选取多个交换机一起迁移，直到满足下列约束公式：

$ L_{\rm{Migrate}} \le T_{\rm{Target}} - L_{\rm{Target}} $

(5)

$ L_{\rm{Load}} - L_{\rm{Migrate}} < T_{\rm{Load}} $

(6)

其中：L_Migrate表示过载域控制器所要迁移的负载；T_Target表示目标域控制器的负载阈值；L_Target表示目标域控制器的当前负载值。要确保过载域控制器所要迁移的负载不超过目标域控制器的负载阈值与其当前负载值的差，以及过载域控制器的当前负载值与过载域控制器所要迁移的负载的差值要小于过载域控制器的负载阈值。

3.4.3 目标域控制器的选择

所要迁移的交换机与目标域控制器之间交互的往返时间越大，迁移的效率就越低。因此，在选择目标域控制器时，综合考虑域控制器的负载条件以及每个交换机与域控制器交互的往返时间，并根据式(7)来选择目标域控制器：

$ {C_{\rm Target}} = {\mu _1}*({T_{\rm Target}} - {L_{\rm Target}}) - {\mu _2}*R $

(7)

其中：C_Target表示选择目标域控制器的标准；μ₁、μ₂表示权重系数，权重系数总和为1。根据C_Target值对所有的域控制器进行降序排列，并优先选择C_Target值最大的域控制器作为目标域控制器。如果需要迁移的交换机不止一个，则根据C_Target值从大到小依次选取与需要迁移的交换机个数一样的目标域控制器，并将选取的交换机按照H_S值从大到小分别迁移到按照C_Target值从大到小排列的目标域控制器上，保证每个目标域控制器只接收一个迁移交换机，避免多个交换机迁移到一个目标域控制器上的情况。同时，如果存在多个C_Target值一样的域控制器，采用以下约束公式：

$ Q = \min\sum\limits_{i \in s} {({r_i} - {r_0}} {)^2} $

(8)

$ {r_0} = {\sum\limits_{i =1}^n {L({B_i})} }/{{\sum\limits_{i =1}^n {T({B_i})} }} $

(9)

$ {r_i} =({{L_{\rm Migrate}} + L({B_i})})/{{{T_{}}({B_i})}}; \;\;(i \in s) $

(10)

其中：Q表示目标域控制器的负载均衡率；s表示C_Target值相同的域控制器的集合；T(B_i)表示域控制器B_i的负载阈值；r₀表示域控制器的整体负载率；r_i表示目标域控制器接收迁移交换机后的负载率。当存在多个C_Target值一样时，优先选取Q值最小的域控制器作为目标域控制器。因为Q的值越小，系统整体负载平衡越好。

3.5 交换机迁移组件

当超级控制器确定最重过载域控制器，并需要迁移多个交换机时，如果按照H_S值从大到小依次将交换机迁移到同一个目标域控制器上，不仅会大大增加目标域控制器的负载，还会消耗大量时间，降低了整个系统的性能。因此，本文根据C_Target值对所有的域控制器进行降序排列，并根据C_Target值从大到小依次选取与迁移交换机个数对应的多个目标域控制器，然后将选取的交换机按照H_S值从大到小分别迁移到按照C_Target值从大到小排列的目标域控制器上，保证每个目标域控制器只接收一个迁移交换机，避免多个交换机迁移到一个目标域控制器上的情况。

交换机迁移到目标域控制器的过程如下：首先，最重过载域控制器通过controller-controller信道向目标域控制器发送交换机迁移请求消息来触发交换机迁移；然后目标域控制器向所要迁移的交换机发送一个Role-Request消息，通知交换机它的角色更改为equal，目标域控制器收到交换机发送的Role-Reply消息后，通知过载域控制器已经完成角色更改。目标域控制器转变成equal后，也可以从交换机接收异步消息，但是不对其作处理。由于过载域控制器可能有很多即将处理的消息，因此过载域控制器继续与交换机进行通信，完成未完成的工作，直到交换机向目标域控制器发送“终止迁移”。收到“终止迁移”消息后，目标域控制器向交换机发送Role-Request消息使自己变成master域控制器，过载域控制器变成slave控制器，至此交换机迁移完成。

3.6 分层式控制器负载均衡机制描述

分层式控制器负载均衡机制的具体过程如下：

步骤1  测量组件测量F、I以及R的值。

步骤2  如果域控制器的当前负载值L大于负载阈值T，则表示该域控制器为过载域控制器。负载通知组件就会将该过载域控制器的负载信息发送给超级控制器。

步骤3  超级控制器的负载收集组件汇总所有域控制器的负载信息。

步骤4  如果同时存在多个过载域控制器，则根据式(1)选取P值最大的过载域控制器作为要迁移的过载域控制器；如果存在多个P值相同的过载域控制器，则根据式(3)选取θ值最大的过载域控制器进行迁移操作。

步骤5  根据式(4)对H_S值进行降序排列，并从大到小选取一个或多个交换机作为迁移交换机，选取的交换机个数由式(5)~(6)决定，直到选取的交换机个数满足式(5)~(6)的约束条件。

步骤6  根据式(7)，按照C_Target值从大到小依次选取与需要迁移的交换机个数一样的目标域控制器，并将选取的交换机按照H_S值从大到小分别迁移到选取的目标域控制器上；若存在多个C_Target值一样的域控制器，则选取使得式(8)的值最小的域控制器作为目标域控制器。

步骤7  利用交换机迁移组件进行迁移操作。

步骤8  更新相应控制器上的负载状态。

4 仿真实验与分析 4.1 实验环境

在版本为12.04的64位Ubuntu虚拟机下，采用mininet进行仿真实验。超级控制器与域控制器均使用Floodlight控制器，交换机采用OpenFlow交换机。为了评估控制器的性能，使用Cbench软件。Cbench是一款性能测量工具，专为基于OpenFlow控制器而设计，它可以模拟OpenFlow交换机的数据包请求。

4.2 实验评估

本文采用图 1所示的层次式控制器平面架构进行实验，并通过测量三个性能指标(通信开销、负载均衡效果以及吞吐量)进行实验分析。为了验证本文所提机制能够有效地权衡负载均衡度和迁移交换机的通信开销，将其控制器协作负载均衡方案(COLBAS)^[7]、动态和自适应算法(DALB)^[2]进行实验对比。其中，COLBAS是通过底层控制平面周期性向顶层控制器发送负载信息，引起高通信开销，且系统吞吐量低；DALB是控制器之间周期性互相收集负载信息，同样引起高通信开销。

4.2.1 通信开销

为了测量本文所提出的方法在通信开销方面的效率，将提出的方法中交换负载状态所需要的消息数量与COLBAS、DALB进行比较。本文假设域控制器层有n个域控制器，COLBAS和DALB均需要n(n-1)个消息来交换控制器之间的负载状态，因为它们需要互相收集负载状态；而本文所提的方案中，超级控制器与域控制器之间只需要2n个交换消息。基于这种理论评估，在不失一般性的情况下，分别在3至10个域控制器下进行比较。如图 3所示，显然，当域控制器数量增加时，COLABAS和DALB中的域控制器之间需要相互收集负载状态，且消息数量的基数增大，而本文所提方法只有在达到负载阈值时才会收集负载信息，这样使得COLABAS和DALB的消息数量远远高于本文方法。例如，如果采用10个域控制器，本文所提方法的消息数量仅仅是COLBAS和DALB消息数量的21%，所以相比COLBAS和DALB，本文方法的通信开销大大降低。

4.2.2 负载均衡评估

采用5个域控制器进行实验，并设置域控制器1、域控制器3、域控制器4和域控制器5的负载阈值为7 000，域控制器2的负载阈值为8 000，即域控制器1、域控制器3、域控制器4和域控制器5每秒最多可接收7 000个PACKET_IN消息，域控制器2每秒最多可接收8 000个PACKET_IN消息。由图 4可知，从0 s至40 s，5个域控制器的负载都是低于其负载阈值的。在45 s时，突然增加域控制器2的消息到达速率，使其负载超过负载阈值，并触发负载均衡机制。此时，超级控制器将域控制器2中所选择的两个交换机分别迁移到域控制器1和域控制器3上，域控制器2的负载降低，域控制器1和域控制器3的负载上升，而域控制器4和域控制器5上的负载未发生变化，从而达到了负载均衡的效果。而且，从图 4中可以看出，负载均衡在5 s内完成，这个完成时间是可以接受的。

4.2.3 吞吐量比较

吞吐量指控制器每秒可处理的消息数量。采用4个域控制器(A, B, C, D)进行实验，通过Chench工具测得域控制器处理PACKET-IN消息的最大速率为每秒10 154个。先向4个域控制器每秒注入5 000个数据包，运行到20 s时，突然向域控制器A每秒注入15 000个数据包。分别利用COLBAS、DALB以及本文方法进行实验，实验结果如图 5所示。

从图 5可以看出，20 s时控制器的平均吞吐量急剧下降。这是由于域控制器A发生过载，导致PACKET_IN消息因缓冲区溢出而开始丢失，造成吞吐量降低。域控制器过载会触发负载均衡机制，域控制器A将部分负载迁移到其他域控制器上，从而提高了系统吞吐量，并使系统吞吐量趋于稳定。显然，与COLBAS、DALB相比，本文所提方法的系统吞吐量比DALB提高了约8.57%，比COLBAS提高了约52.01%，这是由于本文所提方法可以同时将过载域控制器的多个交换机分别迁移到多个对应的目标域控制器上，大大提高了系统的吞吐量。而DALB可以将交换机迁移到局部最优域控制器上，但是需要收集大量负载信息，并且负载策略较复杂，降低了系统的总吞吐量，使得吞吐量低于本文方法。COLBAS需要周期性收集负载信息，负载策略更为复杂，所以其系统总吞吐量低于COLBAS和本文方法。

5 结语

针对SDN多控制器中存在的负载不均衡等问题，本文提出一种分层式控制器负载均衡机制。该机制以降低通信开销、提高系统吞吐量、达到更好的负载均衡度为目标，采用分层式架构，通过超级控制器与域控制器协作完成负载均衡。仿真结果表明，该机制与COLBAS、DALB相比，能够避免周期性收集负载信息，有效降低了通信开销，同时交换机迁移更合理，提高了系统吞吐量，而且负载均衡完成时间更少，达到了更好的负载均衡效果。下一步工作，将会研究如何降低超级控制器与域控制器之间因信息传输所造成的决策延迟。