0 引言

软件定义网络(Software Defined Network,SDN)^[1]的出现很大程度上改变了以往网络的设计和管理方式，其控制逻辑和数据转发分离的特点能够实现对网络更细粒化的管理和资源调度。随着相关技术的不断发展，SDN技术的应用不再仅仅局限于校园网、数据中心网络等小型网络，更大规模的SDN组网已经成为当前的研究热点。谷歌将SDN应用于其连接全球数据中心的骨干网链路，以提高网络资源利用率；电信运营商利用SDN实现城域网与互联网数据中心(Internet Data Center,IDC)专网之间广域网流量的灵活调度，以提升网络的运维效率等。

典型的大规模SDN中往往采用扁平的控制架构实现网络的分布式控制^[2]。布置在不同域内的控制器虽然在地理位置上相对分散，但通过信息交互实现逻辑上的向上集中。如何通过控制器部署更方便地维护全网的逻辑视图、保证控制平面的可靠性、提升节点信息交互的连通性已经成为SDN控制层面设计的一大挑战。

近年来，针对多控制器部署问题的研究成为热点。如文献^[3]中将此问题建模成设备选址问题，在考虑控制链路传输时延的情况下，针对控制器所需的数量和部署位置进行了讨论。文献^[4]提出了控制器综合部署开销的模型，考虑了控制器布置开销、控制器与交换机之间通信开销和控制器之间连通性开销等三个指标，通过线性规划对模型进行优化求解。文献^[5]提出了容量受限的控制器部署(Capacitated Controller Placement,CCP)模型，将负载状况纳入控制器部署的考虑因素，在保证控制器负载均衡的前提下降低控制链路传输时延，并设计了相应的两阶段优化算法。文献^[6]针对SDN弹性控制面临的问题，提出基于k-center的启发式算法，实现了控制器动态部署的快速计算。文献^[7]通过对比故障前后网络中的时延和负载情况，分析了控制节点故障对网络性能的影响，并提出了基于帕累托优化的控制器部署方法。

以上方法之间的差别只局限于探讨与网络服务质量相关的几种不同指标，而本质上都采用了同一种解决问题的思路，即先建立控制器与交换机之间的联系，把实际问题转化成整数规划问题，再利用穷举法或者启发式算法对这一NP难问题求解，最后将归属于同一控制器的节点自然地划分至同一子域。这一思路将子域划分和域内控制器部署这两个步骤的计算融合在一起，分析时把整个网络看作一个整体，而未单独考虑划分子域的问题。对于实际网络，其拓扑一般都具有社团结构，因此可利用社团发现算法先将网络划分成若干个子域，使得同一子域内部的节点相互连接紧密，而不同子域之间的节点相互连接稀疏^[8]。这样在保证控制器与子域内交换机之间控制链路连通性的同时，将子域划分和控制器部署的计算分离，降低了模型计算的复杂度。

本文基于标签传播算法(Label Propagation Algorithm,LPA)^[9]，提出包含两个步骤的针对大规模SDN的子域划分及控制器部署(Domain Partition and Controller Placement for large-scale SDN,DPCPS)算法：1)在LPA的基础上进行改进，限制标号传播的最大跳数和子域间节点数量的最大差值，从而将网络划分成多个负载均衡和可靠性均满足要求的子域；2)根据控制链路平均时延，分别在每个子域中部署控制器。通过把多控制器部署的问题转化成多个单控制器部署的问题，将模型的运算复杂度由指数型简化至倍数型。基于公共拓扑Internet2^[10]和topology zoo^[11]的仿真可发现，与原始的LPA相比，控制器的负载均衡性得到明显的改善；与CCP算法相比，模型计算复杂度大大降低，控制链路平均时延有所减小，控制链路的可靠性得到一定的加强。

1 模型的描述和建立

将网络建模成一个无向图G=(V,E)，其中V=(v₁,v₂,…,v_n)是无向图中节点的集合，n=|V|代表网络中节点的个数；E是边的集合，m=|E|代表网络中边的个数。将网络划分成p个子域，表示为C=(C₁,C₂,…,C_p)，每个子域中包含任意k(1≤k≤n)个节点和一个控制器s_i，表示为C_i=(v_t1,v_t2,…,v_tk,s_i)，网络中控制器的集合为S=(s₁,s₂,…,s_p)。所有的子域之间互不重叠，并且网络中的任意节点都属于且只属于某一个子域，即：

${{C}_{i}}\bigcap {{C}_{j}}=\varnothing ;\forall i,j,i\ne j,$

(1)

$\left| {{\bigcup }_{i}}{{C}_{i}} \right|=n$

(2)

为对问题及相关算法进行描述并建模，现提出以下定义：

定义1 控制链路。控制器和交换机之间传输控制信息的链路称作控制链路，其实现方式主要有两种：一是带内传输，即使用数据平面流量转发的链路传输控制信息；二是带外传输，即使用专用的链路传输控制信息。对于大规模网络，由于交换机数量多且控制器与交换机之间距离远，因此本文中所述的控制链路采用带内传输方式。

定义2 节点标签L(V)。初始化时给每个网络节点都分配一个互不相同的节点标签号L⁰(V)=(L⁰(v₁),L⁰(v₂),…,L⁰(v_n))，其中L⁰(v₁)=l₁，L⁰(v₂)=l₂，…，L⁰(v_n)=l_n。经过q次的传播，此时节点具有的标签为L^q(V)=(L^q(v₁),L^q(v₂),…,L^q(v_n))，其中L^q(v₁)=l_q1，L^q(v₂)=l_q2，…，L^q(v_n)=l_qn，且l_qk∈{l₁,l₂,…,l_n}，1≤k≤n。

定义3 连接状态矩阵X=[x_i,j]_n×n。其表示网络中控制器和交换机之间的连接关系，其中i，j分别表示交换机和控制器所在节点的标号，矩阵的值代表连接状态。当x_i,j=1时，意味着交换机v_i隶属于控制器s_j：

${{x}_{i,j}}=\left\{ \begin{matrix} 1, & 交换机{{v}_{i}}隶属于控制器{{s}_{j}} \\ 0, & 其他 \\ \end{matrix} \right.$

(3)

定义4 相邻节点间最短路径长度d(v_i,v_j) 。对于大规模广域网，不能将地面视为平面。假设地球是一个标准的球体，半径为 r，节点 v_i 的经度为 α_i，纬度为 β_i ；节点 v_j 的经度为 α_j，纬度为 β_j 。为方便计算现规定，计算经度时，东经为正，西经为负；计算纬度时，南纬为 90°+纬度值，北纬为 90°-纬度值，则相邻两点 (v_i,v_j)间最短路径长度为：

$\begin{align} & d\left( {{v}_{i}},{{v}_{j}} \right)=r\cdot \arccos \left( \sin \left( {{\beta }_{i}} \right)\sin \left( {{\beta }_{j}} \right)\cos \left( {{\alpha }_{i}}-{{\alpha }_{j}} \right)+ \right. \\ & \left. \cos \left( {{\beta }_{i}} \right)\cos \left( {{\beta }_{j}} \right) \right) \end{align}$

(4)

定义5 控制链路平均时延L_avg。由于节点之间距离较远，传输距离将会在很大程度上成为影响信号传播时延的主要因素，故用节点间的距离代表节点间信号传播的时延。每个子域中有且仅有一个控制器，并控制域中所有交换机。D(v_i,s_j)为交换机v_i∈V到控制器s_j∈S的最短路径长度，则对于控制器集合S和交换机集合V，平均控制时延L_avg为所有交换机到各自所属控制器之间的控制链路平均时延：

$\begin{align} & D\left( {{v}_{i}},{{s}_{j}} \right)=\underset{{{v}_{1}},{{v}_{2}}\cdots ,{{v}_{k}}}{\mathop{\min }}\,\left( d\left( {{v}_{i}},{{v}_{1}} \right)+d\left( {{v}_{1}},{{v}_{2}} \right)+\cdots \right. \\ & +d\left( {{v}_{k-1}},{{v}_{k}} \right)+d\left( {{v}_{k}},{{s}_{j}} \right) \end{align}$

(5)

${{L}_{avg}}\left( V,S \right)=\frac{1}{n}\sum\limits_{{{v}_{i}}\in V}{\sum\limits_{{{s}_{j}}\in S}{D({{v}_{i}},{{s}_{j}})\cdot {{x}_{i,j}}}}$

(6)

定义6 负载均衡指数B。控制器处理交换机提交的消息，消息量越大，则控制器的负载越大，控制器的性能会受到影响。因此最佳的分配方式是所有的控制器都有均衡的负载，避免出现有的控制器负载过大，而有的控制器过于空闲的情况。将网络划分成C₁，C₂，…，C_p等p个子域，且每个子域中仅布置一个控制器，设子域中交换机v_k向控制器提交的平均信息量为b_k，则网络中控制器负载均衡的状况可用子域间交换机提交的平均信息量之和的最大差值B表示：

$B\left( C \right)=\underset{i}{\mathop{\max }}\,\sum\limits_{{{v}_{p}}\in {{C}_{i}}}{{{b}_{p}}}-\underset{j}{\mathop{\min }}\,\sum\limits_{{{v}_{q}}\in {{C}_{j}}}{{{b}_{q}}}$

(7)

定义7 可靠性指数R。假设网络中交换节点都有等大的故障概率，且节点之间相互独立，因此控制器与交换机之间经过的节点跳数越多，则通信链路出现故障的概率越大，故控制链路的可靠性可以用节点间平均跳数的倒数R来衡量：

$\begin{align} & k\left( {{v}_{i}},{{s}_{j}} \right)=\left\{ k|\underset{{{v}_{1}},{{v}_{2}}\cdots ,{{v}_{k}}}{\mathop{\min }}\, \right.\left( d\left( {{v}_{i}},{{v}_{1}} \right)+d\left( {{v}_{1}},{{v}_{2}} \right)+\cdots \right. \\ & \left. \left. +d\left( {{v}_{k-1}},{{v}_{k}} \right)+d\left( {{v}_{k}},{{s}_{j}} \right) \right),{{v}_{i}}\in V,{{s}_{j}}\in S \right\} \end{align}$

(8)

$K_{{{s}_{j}}}^{{{v}_{i}}}=k\left( {{v}_{i}},{{s}_{j}} \right)+1$

(9)

$R=n/\sum\limits_{{{v}_{i}}\in V}{\sum\limits_{{{s}_{j}}\in S}{K_{{{s}_{j}}}^{{{v}_{i}}}\cdot {{x}_{i,j}}}}$

(10)

对于大规模SDN网络，优化控制链路传播时延、可靠性以及控制器负载均衡的模型如下：

$\text{min }{{L}_{avg}}$

(11)

$s.t.B\le {B}'$

(12)

$R\ge {R}'$

(13)

$\sum\limits_{j}{{{x}_{i,j}}=1;\text{ }\forall i}$

(14)

${{x}_{i,j}}\in \left\{ 0,1 \right\};\text{ }\forall i,j$

(15)

式(11)是模型的优化目标，使网络的控制链路平均时延最小；式(12~15)是模型的约束条件。式(12)中的B′为控制器负载均衡指数的上限，保证控制器的负载均衡程度维持在一定的范围内；式(13)中的R′为控制链路可靠性的最小值，避免控制链路跳数过多，保证链路的可靠性；式(14)保证网络中所有的交换机都分配且只分配给一个控制器；式(15)约束了连接状态矩阵的值，保证其只存在1或0，即连接或不连接两种状态。

2 算法描述及分析

文献^[9]提出一种基于标号传播的复杂网络社团发现算法LPA，不需要任何先验信息以及优化的目标函数，只根据其内部存在的网络结构特点，即可在线性时间内利用较少的计算和存储资源将网络合理划分成多个子域。但是由于网络结构不均匀，导致利用LPA划分的子域之间规模差异较大，造成控制器负载的不均衡。文献^[5]中提出基于K-center问题的CPP部署策略，优化目标是在网络中部署K个控制器，使得交换机到各自所属控制器之间的最短链路长度的最大值最小。

本文在上述两算法的基础上提出DPCPS算法，主要分为两个步骤。

步骤一 网络子域划分。

输入 网络拓扑图G=(V,E)，节点邻接矩阵A=[a_i,j]_n×n，负载均衡指数上限B′，可靠性指数下限R′；

输出 拓扑分域结果C。

1) L⁰(V)=(L⁰(v₁),L⁰(v₂),…,L⁰(v_n))

2) for t=0;t=t+1

3) $count({{L}^{t}}(V))=\underset{{{C}_{i}}}{\mathop{\cup }}\,count\left( {{L}^{t}}({{C}_{i}}) \right)$计算子域中节点数

4) V_k=∅

5) for each v_k∈V do

6) A,v_k→V_adj邻接节点集合

7) for each v_i∈V_adj do

8) if count(L^t(v_i))－min(count(L^t(V)))≤B′ && 1/K_vi≥R′

9) V_k=V_k∪v_i

10) end

11) end

12) L^t+1(v_k)={l_i|$\underset{{{l}_{i}}}{\mathop{\max }}\,$(countif(L^t(V_k)=l_i)), 1≤i≤n}

13) end

14) if L^t+1(V)=L^t(V)

15) C=(C₁,C₂,…,C_p)

16) break

17) end

18) end

步骤一是利用改进的LPA对网络进行分域处理，其中通过对子域规模的限制，保证控制器负载相对均衡。首先对网络中的节点进行初始化，每个节点分配到初始标号(行1))；随后每个节点开始向外传播标号，同时选取其相邻节点中出现次数最多的标号更新为自己新的标号(行12))，当有多个标号出现的次数相同时，随机选取其中一个；最后将具有相同标号的节点暂时划分至同一个子域中。经过有限次循环后网络中节点标号的状态如果收敛，即连续两次更新的标号保持一致，则退出循环(行14))，保存最后一次更新的结果作为最终的分域结果。其中，对标号传播的最大跳数进行约束(行8))，使得当标号传播一定跳数后停止继续向外传播，限制子域的半径，保证了控制链路的可靠性；每次循环更新之前，检查当前每个子域中交换节点的平均信息量之和(行8))，若子域之间负载差值已经达到设定的上限，则这个子域的标号在下一轮循环中暂停传播，以保证控制器的负载均衡性。

步骤二 域内控制器部署。

输入 拓扑分域结果C；

输出 连接状态矩阵X=[x_i,j]_n×n。

1) for each C_i∈C do

2) ${{s}_{j}}=\left\{ {{v}_{k}}\left| \underset{{{v}_{k}}}{\mathop{\min }}\,{{L}_{avg}}\left( {{C}_{i}},{{v}_{k}} \right),{{v}_{k}}\in {{C}_{i}} \right. \right\}$

3) S=S∪s_j输出控制器集合

4) for each v_i∈C_i do

5) x_i,j=1

6) end

7) end

8) x_i,j→X生成连接状态矩阵

步骤二是控制器部署位置的选取。由于子域划分时已经考虑到了控制器的负载均衡以及控制链路的可靠性，故在选取控制器位置时只需考虑链路时延，即遍历整个子域，搜索部署控制器的最佳位置，使得子域中所有交换机到控制器的控制链路平均时延L_avg最小(行2))。更新连接状态矩阵，将属同一子域的交换机与控制器在矩阵中所对应的值赋1(行5))。

3 实验结果及分析 3.1 仿真环境

对于实验的相关环境作出如下说明：

1) 本文选用Internet2 Network Advanced Layer 2 Service作为实验拓扑，并从topology zoo中选取多个合适的拓扑对算法进一步地验证。Internet2成立于1996年，是由美国120余所大学、科研机构和公司共同支持建设的下一代互联网络，用于教学以及科研等需求，整个拓扑共包含36个节点，遍布整个美国大陆。Topology zoo项目由阿德莱德大学主导，并得到澳大利亚政府的支持，目前已经从全世界收集了超过250个网络拓扑，具有较高的参考和研究价值。

2) 实验基于的硬件环境为Intel Core i7-3770 CPU 3.40 GHz，RAM 4 GB 的台式个人电脑。对DPCPS算法和原始LPA的仿真均采用在Matlab软件上模拟运行的方法，而对CCP算法仿真中的线性规划求解则采用CPLEX 7.0线性和混合整数规划求解器来求解计算。

3.2 参数设置

对于实验的相关参数作出如下说明：

1)为简化实验过程，仅验证算法的正确性，作出如下假设：不考虑节点间光缆在实际铺设中的弯曲，两点间的最短距离用球面上直线距离表示；不考虑控制器之间的差异性，所有控制器都有相同的负载容量、处理能力和传输速度等；不考虑交换机之间的差异性，假设所有交换机都向控制器提交相同数据量的信息，即b_k=1(k=1,2,…,n)，实际应用时可根据具体情况再相应设定。

2) 因DPCPS算法和CCP算法中控制器负载均衡指数可通过程序中参数B′的设定直接进行控制，而非通过启发式算法优化得到，故二者的对比实验中未对此指标进行比较。实验中设定B′=2，在保证控制器负载均衡的前提下比较控制链路平均时延和可靠性指标。

3) DPCPS算法采用启发式算法具有一定的随机性，导致每次的计算结果间可能存在差异。例如，令控制器数量为6，重复仿真500次，控制链路平均时延L_avg和可靠性指标R的取值情况如图 1。可见L_avg在区间[607,678]内波动，波动幅度为±5.54%；R则在集合{0.612 2，0.625 0，0.638 3，0.652 2，0.666 7}中波动，波动幅度为±4.26%。为保证实验结果的可信性，实验仿真中均采用多次重复仿真，根据具体实验具体分析取相应平均值或最佳值的方法来确定最终结果。图 1为重复实验500次的结果分布示意图。

3.3 实验分析 3.3.1 复杂度计算与比较

对于NP难问题，若要取得最佳结果，需采用穷举法。在具有n个节点的网络中部署p个控制器，遍历所有解决方案的计算量为O(n^p·pⁿ)，假设n=50，p=5，对于这样一个规模并不大的网络穷举所有可能情况所需的计算量为10³⁴，已经远远超出当前的计算能力。

文献^[5]中提出CCP算法，通过两阶段算法对这一整数线性规划模型进行求解。假设网络中有n个节点，m条边，第一阶段首先利用二分法对线性松弛后的问题进行求解，计算出控制器与交换机之间最大距离r的下限，若采用当前应用较多的具有多项式时间解法的内点法求解线性规划，则此阶段计算所需要的时间为O(n^3.5L² lg m)，L为线性规划约束的个数；第二阶段是在第一阶段结果的基础上对r的大小不断地调整修正，并同时求得次优解，所需的时间为O(n lg n)，因此整个算法所需要的时间为O(n^3.5L² lg m)。

本文提出的DPCPS算法在解决控制器部署问题时，所需计算量仅与网络规模呈线性关系。在具有n个节点，m条边的网络中，对所有节点的标号进行初始化需时间为O(n)；每次循环中，统计所有节点的标号，并计算当前每个子域中节点的数量，所需时间为O(n)；查表获得每个节点标号已传播的跳数，所需时间为O(n)；依次对每个节点的相邻节点的标号数量进行统计，需要的时间与此节点的度数d相关，为O(d)，则对于所有节点的总时间为O(m)；然后在相邻节点中选取最多的标号对此节点进行更新，在最差的情况下，即所有相邻节点的标号都各不相同，需要的时间为O(d)，对于所有节点的总时间为O(m)；综上，整个算法所需的时间仅为O(n+m)，与网络的规模(n,m)呈线性关系。不同算法时间复杂度的比较如表 1所示。

3.3.2 仿真结果分析

本节在Internet2以及topology zoo中选取的拓扑上分别对原始LPA、CCP算法和DPCPS算法进行仿真，并对实验结果中的控制链路平均时延、控制器负载均衡以及链路可靠性等指标进行比较分析。

首先在不同数量控制器的条件下，分别在Internet2、Geant2009、Canerie拓扑上进行仿真，比较原始LPA和DPCPS算法的负载均衡指标。实验采用多次仿真取平均值的方法，结果如图 2，原始LPA的负载均衡状态不可控，对于不同控制器数量的情况，负载均衡指数波动很大，且远远高于DPCPS算法，因此可能出现负载分配极不平衡的情况。这是由于原始LPA并未对子域的规模进行限制，节点的标号可以在网络中任意传播直至收敛，因此子域的划分完全取决于网络拓扑的结构，没有考虑负载均衡的因素。DPCPS算法对子域规模进行了限制，当某一子域中交换机数量过多，与其他子域规模的差值超过一定阈值时，暂停此域中的节点参与下一轮的标号传播，以达到限制子域规模的作用。实验表明，利用DPCPS算法进行优化部署，控制器负载均衡指数B保持稳定且较小，对实现控制器负载均衡起到了良好的效果。

然后比较DPCPS算法和CCP算法的控制链路平均时延和可靠性指标。实验采用多次仿真取最优值的方法，如图 3，随着控制器数量的增加，两种算法的控制链路平均时延L_avg都呈下凸曲线下降，即通过增加控制器数量可减小控制器平均时延，但增加控制器所带来的效果提升的趋势逐渐减弱。同样如图 4，两种算法得到的可靠性指标R都呈上凸曲线上升，因此对于可靠性指标也有类似的规律。

通过比较可以发现，DPCPS算法优化得到的平均时延和可靠性在相同控制器数量的条件下都优于CCP算法，且随着控制器数量的增加，DPCPS算法对比CCP算法的提升曲线大体呈先上升后下降的趋势。提升曲线先上升是因为CCP算法的模型基于受限的装箱问题，为优化链路时延，给控制器设置了最大控制范围ε，但拓扑中节点分布不均匀，部分节点相对稀疏，而部分相对密集，覆盖相同数量的节点时，位于稀疏部分的控制器需要的控制范围更大，因此设置的ε对于密集部分的控制器来说过大，使得限制相对松弛。并且当控制器增多时，密集区域控制器需要的控制范围变小，但受限于稀疏区域节点间的距离，ε减小的幅度相对很小甚至不减小，使得ε对密集区域控制器的限制更加松弛，从而导致密集区域控制链路时延和可靠性的优化效果变差，而DPCPS算法中节点标签在网络中各节点处并行传播，不会受拓扑分布的密集程度的影响，故相对于CCP算法的优势增大。但是当控制器数量增长达到足够多后，每个子域中节点数量太少，导致子域结构过于简单，再进一步优化提升的空间有限，故随着控制器数量进一步地增加，提升曲线呈整体下降的趋势。但实际网络中控制器与节点数量的比值一般较低，因此我们可以曲线忽略下降的部分，认为在合理的范围内，随着控制器数量的增加，DPCPS算法相对于CCP算法的优势增大。

为具体量化波动对实验结果的影响，在不同的控制器数量条件下分别重复仿真500次，统计结果中性能优于CCP算法的次数n，占总仿真数的比例p(p=n/500)和以99%概率获得优于CCP算法的结果所需的最多仿真次数m。实验结果如表 2，对于不同数量的控制器，DPCPS算法性能优于CCP算法的概率p普遍高于80%，甚至高于90%，且至多只需2次或3次重复仿真便可有大于99%的把握获得优于CCP算法的结果。由于DPCPS算法计算复杂度极低，因此有限次重复仿真后仍具有较大的计算复杂度上的优势。

最后，从topology zoo中选取10个拓扑对算法进一步验证，拓扑选取的标准为规模适中，且结构具有适度的复杂性。分别在每个拓扑中运用DPCPS算法和CCP算法部署$\left\lfloor n/15 \right\rfloor \tilde{\ }\left\lfloor n/5 \right\rfloor $个控制器(n为拓扑节点数)，比较并计算DPCPS算法相对于CCP算法的控制链路平均时延和可靠性指标提升比的平均值。仿真结果如图 5，对于所选取的10个拓扑，DPCPS算法的性能都优于CCP算法，且性能提升的程度与网络规模大小无关，而主要取决于拓扑的结构：节点的地理分布若不均匀，例如Geant2009拓扑中由于有一个节点远离其他所有节点，则导致CCP算法性能相对较差，DPCPS算法相对的优势较大;而对于节点分布均匀的拓扑，例如UsSignal，则DPCPS算法的优势相对较小。

4 结语

本文针对SDN多控制器架构的控制器部署问题，在LPA的基础上提出先对网络分域、再部署控制器两个步骤的DPCPS算法，。与原始的LPA相比，DPCPS算法利用改进的LPA对网络划分子域，综合考虑了负载、可靠性等多方面因素，更能适应SDN这一应用场景；相对于以往的控制器部署方法，如CCP算法，DPCPS算法降低模型的运算复杂度，并改善了控制链路平均时延和负载均衡等指标，尤其提升了节点地理分布不均匀时的网络服务质量。最后，分别在公共拓扑Internet2和topology zoo上对算法进行实验仿真，验证算法的有效性。

本文用交换机数量和节点跳数分别对控制器负载以及链路可靠性进行度量的标准略粗粒度，在接下来的工作中将会对其进行更细化的考量。