0 概述

面对网络流量的爆炸式增长和新业务的快速发展, 传统网络架构已经无法满足日益增长的网络需求, 出现了服务质量和可扩展性差、可靠性低等问题^[1]。在该背景下, 软件定义网络(Software Defined Network, SDN)^[2]技术应运而生。SDN是一种创新性的网络架构, 它通过开放接口将传统的网络体系结构解耦为数据平面、控制平面和应用平面, 在逻辑上实现了网络的集中控制和管理^[3-4], 且SDN中的控制器不仅可以将控制信息下发至底层的数据平面执行, 还对整个网络拓扑和状态进行实时维护, 为应用平面提供可扩展的编程接口。随着SDN架构的不断推广, 数据平面的数据量和应用平面的业务量逐渐增加, 单一的控制器已无法及时处理大量的流量请求, 因此研究SDN中的多控制器部署策略^[5]非常必要。

近年来, 关于控制器部署问题的研究分为两类:一类是考虑单一性能指标, 通过优化单目标求解控制器位置。文献[6]较先提出控制器部署问题, 定义了平均时延和最坏时延, 并采用贪婪算法对控制器进行部署。文献[7]考虑到控制器负载, 将控制器部署问题建模为在整数线性规划问题中求解控制器的最小个数以及最优位置。文献[8]考虑了交换机和链路的故障概率, 并提出可靠性指标控制路径损失预期率。文献[9]为最小化交换机和相关控制器之间的传输时延, 提出一种基于相似性传播的改进聚类方法，该方法不预先指定控制器的个数和位置, 而是根据网络拓扑结构自适应学习控制器的最佳个数和位置。文献[10]提出改进的I-K-means聚类算法, 利用网络分区降低网络中的质心节点和关联节点之间的最大时延, 但是该算法考虑的目标较为单一, 不能适用于复杂的网络环境。另一类是考虑多种性能指标, 将控制器部署问题转化为多目标规划问题。文献[11]定义了全局时延并将粒子群优化算法用于解决控制器部署问题。文献[12]在Pareto最优控制器部署框架下研究控制器的弹性部署, 并考虑到控制器间传播时延、控制器负载均衡、控制器故障以及网络可靠性等多种性能指标, 存在算法复杂度较高、不适用于大规模网络的问题。同时, 还有部分研究通过网络划分降低控制器对大型网络管理的复杂度。如文献[13]提出基于密度聚类的控制器部署算法, 该算法通过密度聚类将网络划分成多个子网络, 得到最佳控制器个数后对控制器进行部署。文献[14]基于改进的标签传播算法将网络划分成多个子域, 并在子域中分别部署控制器, 将平均时延、可靠性和控制器负载均衡纳入约束条件以达到最优部署。文献[15]提出一种基于社区特征的控制器部署策略, 先基于模块度的遗传算法对网络进行划分, 再通过协调控制器之间的传播时延和控制器与交换机之间的控制时延来部署控制器。但是上述研究划分的网络结构不合理, 且网络可靠性也不能得到保障。

针对以上研究方案中存在的问题, 结合改进的Louvain社区检测算法^[16], 本文提出一种SDN控制器部署策略。利用节点相似度重新定义链路权重, 并计算社区模块度, 通过引入控制器负载差异度对整个网络拓扑进行划分, 独立地根据网络拓扑结构划分合适的分区, 以提高网络负载均衡。同时，本文还通过交换机到控制器间传播时延、控制器间传播时延、控制链路可靠性3个性能指标对已经划分好的各个子域进行域内单控制器部署。

1 模型描述与建立

将大型SDN表示为一个无向图G=(V, E)。其中, V表示网络中交换机集合, V=(v₁, v₂, …, v_n), n=|V|表示交换机个数。E表示网络中交换机之间的链路集合, E=(e₁, e₂, …, e_m), m=|E|表示链路个数, e(u, v)∈E表示交换机u和交换机v之间相连的链路。C表示控制器集合, C=(c₁, c₂, …, c_k)。将网络划分成K个不相交的社区, P表示划分的社区集合, P=(p₁, p₂, …, p_k), 每个社区包含一个控制器和任意t(1≤t≤n)个交换机, p_j=(v_1j, v_2j, …, v_tj, c_j)。

定义1  映射关系矩阵X_n×n表示控制器与交换机的映射关系, 如式(1)所示, 若交换机v_i映射到控制器c_j, 则x_{i, j}=1, 否则为0。

$ {x_{i, j}} = \left\{ {\begin{array}{*{20}{l}} {1, {\rm{ 交换机}}{\kern 1pt} {\kern 1pt} {v_i}{\kern 1pt} {\kern 1pt} {\rm{映射到控制器}}{\kern 1pt} {\kern 1pt} {c_j}}\\ {0, {\rm{ 其他 }}} \end{array}} \right. $

(1)

定义2  社区p_j内交换机到控制器的平均传播时延L_pj-avg如式(2)所示:

$ {L_{{p_j} - {\rm{avg}}}} = \frac{1}{t}\sum\limits_{{v_j}, {c_j} \in {p_j}} {{\rm{min}}} {\kern 1pt} {\kern 1pt} d({v_j}, {c_j}) $

(2)

其中, min d(v_j, c_j)表示交换机v_j∈p_j与其所属控制器c_j∈p_j之间的最短路径。

定义3  交换机到控制器的总平均传播时延L_sc-avg, 其表示各个社区交换机到控制器平均时延之和, 计算方法如式(3)所示:

$ {L_{sc - {\rm{avg}}}} = \sum\limits_{j = 1}^k {{L_{{p_j} - {\rm{avg}}}}} $

(3)

定义4  网络的控制逻辑分布在多个控制器上, 这些控制器需要同步以保持一致的全局状态, 各个控制器之间的时延起重要作用, 控制器间平均传播时延L_cc-avg的计算方法如式(4)所示:

$ {L_{cc - {\rm{avg}}}} = \frac{1}{k}\sum\limits_{{c_i}, {c_j} \in C} {{\rm{min}}} {\kern 1pt} {\kern 1pt} d({c_i}, {c_j}) $

(4)

定义5  控制平面总平均传播时延。控制平面时延包括交换机到控制器以及控制器间的传播时延, 因此将控制平面的总平均传播时延表示为:

$ {L_{{\rm{ total }}}} = {L_{sc - {\rm{avg}}}} + {L_{cc - {\rm{avg}}}} $

(5)

定义6  控制器负载差异度。控制器控制的交换机越多, 控制器负载越大, 将会导致负载资源不均衡, 不同控制区域内部的通信延迟情况不同, 对网络性能造成影响, 严重情况下很可能导致网络故障。因此为了防止控制器过载, 分配给不同控制器的交换机数量应该是均衡的。假设控制器控制一个交换机所需的流量为l(n), 子网间的负载平衡状况可由控制器负载最大差值来表示:

$ \beta = {\rm{max}}\sum\limits_{n \in {p_i}} l (n) - {\rm{min}}\sum\limits_{m \in {p_j}} l (m) $

(6)

定义7  控制路径平均损失率。控制路径定义为用于交换机与其控制器之间传输控制信息的链路, 其实现方式主要有2种, 一种是带内传输, 即使用数据平面流量转发的链路传输控制信息; 另一种是带外传输, 即使用专用的链路来传输控制信息^[17]。对于大规模网络, 由于交换机数量多且控制器与交换机之间距离较远, 因此本文的控制链路选用带内传输方式对信息进行传输。当控制器、交换机、物理链路出现故障时, 都会促使控制链路失效, 从而导致整个网络瘫痪, 因此控制器与交换机之间的控制链路越长, 则控制链路出现的故障概率越大。控制路径的平均损失率如式(7)所示:

$ \delta = \frac{1}{{{m_c}}}\sum\limits_{l \in (V, E)} {{d_l}} {p_l} $

(7)

其中, l表示物理网络组件, 包括控制器、交换机与物理链路。d_l表示控制路径, p_l表示网络组件l的故障率, m_c表示控制路径总数量, 且m_c=n。控制路径平均损失率δ越小, 说明方法的可靠性越高。

针对大规模SDN, 优化控制平面总平均传播时延、控制器负载以及控制链路可靠性的目标分别定义为:

$ {\rm{min}}{\kern 1pt} {\kern 1pt} {L_{{\rm{ total }}}} $

(8)

$ {{\rm{ s}}{\rm{. t}}{\rm{. }}\beta \le {\beta ^\prime }} $

(9)

$ {\delta \le R} $

(10)

其中, β′表示控制器负载最大差值的上限, R表示控制路径平均损失率的最大值。

2 本文算法描述与分析 2.1 本文算法分析

Louvain算法是一种基于多层次(逐轮启发式迭代)优化模块度的算法, 该算法通过最大化每一层的目标函数Q^[18]来检测最佳社区。模块度Q是评判划分社区结构强度的方法, 同时也是优化后的目标函数。它能够刻画发现的社区紧密程度, 好的社区划分结果要求社区内节点相对紧密, 社区外节点相对稀疏。基于模块度的社区发现算法都是以最大化模块度Q为目标, 模块度Q的计算方法如式(11)所示:

$ \mathit{\boldsymbol{Q}} = \sum\limits_c {\left[ {\frac{{\sum {{\rm{in}}} }}{{2A}} - {{\left( {\frac{{\sum {{\rm{tot}}} }}{{2A}}} \right)}^2}} \right]} $

(11)

其中, ∑in表示社区p内的链路权重之和, ∑in=∑w(u, v), ∀u, v∈p, e(u, v)∈E。∑tot表示与社区p内节点相连的链路权重之和, ∑tot=∑w(u, v), {u, v}∩p≠Ø, e(u, v)∈E。A表示所有链路权重之和, A=∑w(u, v), e(u, v)∈E。

将节点从其社区中移除并移动到相邻社区来评估模块度Q的增益, 模块度增益如式(12)所示:

$ \Delta {Q_{u \to p}} = \frac{1}{{2A}}\left( {{w_{u \to p}} - \frac{{\sum {{\rm{ tot }}} \times w(u)}}{A}} \right) $

(12)

其中, ΔQ_u→p表示将节点u移动到相邻社区p的模块度增益, w_u→p表示社区p中与节点u相连的所有链路权重之和。

Louvain算法主要分为以下2个阶段:

1) 在第一阶段, 首先为每一个节点分配一个不同的社区, 社区数目与节点个数相同。其次对于每个节点v_i, 将v_i从其社区中移除并将其移动到相邻社区p_j中来评估模块度增益ΔQ。接着, 将节点v_i移动到模块度增益最大的社区中, 但前提是max ΔQ>0, 否则节点v_i保持原社区不变。最后, 对所有的节点按顺序重复此过程直至所有节点的社区不再发生变化。

2) 第二阶段的目的是建立一个新的网络, 将第一阶段生成的社区压缩成一个新的节点, 新节点之间的链路权重由对应2个社区中节点之间的链路权重之和表示。重复第一阶段的步骤直至整个网络的模块度不再发生变化。Louvain算法步骤简单、复杂度较低, 且计算速度快, 因此适用于大型网络。

本文提出一种改进的Louvain社区部署策略(Louvain Community Placement Strategy, LCPS), 用于解决大规模SDN下的多控制器部署问题。该策略的目标是缩短控制器与其隶属交换机之间的平均时延和控制器间的平均时延, 并提高控制器的负载以及控制链路的可靠性。LCPS由2种算法组成:算法1是利用改进的Louvain算法对网络社区进行划分, 算法2是在已经划分好的社区中部署控制器。传统的Louvain算法存在不足, 如社区划分效果依赖计算链路权重的方法, 聚类过程中没有及时收敛而导致划分的社区过大等问题。针对该问题, 本文提出以下2种解决方法:

1) 根据节点相似度重新定义链路权重的概念。在网络中, 节点u和节点v之间的最短路径越小, 则这2个节点的相似度越高。基于最短路径定义节点相似度函数sim(u, v)如式(13)所示:

$ {\rm{ sim}} (u, v) = \frac{1}{{1 + d(u, v)}} $

(13)

传统的社交网络运用Louvain算法划分社区时, 2个节点之间的权重越大, 这2个节点合并到同一个社区的可能性越大。将Louvain算法应用到大规模SDN网络下, 节点间的相似度越高, 则它们之间的联系越紧密。为了最大化社区的紧密度, 根据节点相似度定义相应的链路权重函数w(u, v)如式(14)所示:

$ w(u, v) = \frac{1}{{1 + d(u, v)}} $

(14)

其中, d(u, v)表示节点u和节点v之间的最短路径。w(u, v)的取值范围为[0, 1], 且其值越高, 则节点u和节点v越容易合并到同一个社区。

2) 划分社区时, 引入控制器负载差异度β′来限制社区的大小, 以平衡控制器的负载。传统的Louvain算法通过移动节点到max ΔQ>0的社区来划分网络, LCPS通过将节点移动到满足max ΔQ>0且$\max \sum\limits_{n\in {{p}_{i}}}{l\left( n \right)-\min \sum\limits_{m\in {{p}_{j}}}{l\left( m \right)}}\le {\beta }'$的社区来划分网络, 这样划分的网络负载更加均衡。

2.2 算法步骤 2.2.1 网络社区划分算法

算法1的核心思想是利用改进的Louvain算法实现网络的均衡划分。算法1的具体步骤为:

步骤1  将网络中每个节点看成一个独立的社区, 初始社区数目与节点个数相同。

步骤2  依次尝试将每个节点移动到相邻节点所在的社区并计算ΔQ, 将该节点移动到满足max ΔQ>0且$\max \sum\limits_{n\in {{p}_{i}}}{l\left( n \right)-\min \sum\limits_{m\in {{p}_{j}}}{l\left( m \right)}}\le {\beta }'$的社区。若不满足该条件, 则节点保持原社区不变。

步骤3  重复上述步骤, 直至所有节点的所在社区不再发生变化。

步骤4  对图进行重构, 将所有在同一个社区的节点压缩成一个新的节点, 社区内节点之间的链路权重更新为新节点环的权重, 社区间的链路权重更新为新节点间的链路权重。

步骤5  重复步骤2, 直至整个图的总模块度不再发生变化。

算法1的伪代码为:

输入  网络拓扑图G=(V, E), 负载最大差异度β′

输出  社区集合P

1.初始化社区的数目与节点个数相同;

2.计算社区总模块度totalQ=$\sum\limits_{{{\text{p}}_{\text{i}}}}{{{\text{Q}}_{\text{i}}}}$;

3.for每一个节点v_i∈v do

4.计算节点迁移到相邻社区的模块度增益ΔQ；

5.if max ΔQ>0且max∑n∈$\max \sum\limits_{{\rm{n}} \in {{\rm{p}}_{\rm{i}}}} {{\rm{l}}\left( {\rm{n}} \right)} - \min \sum\limits_{{\rm{m}} \in {{\rm{p}}_{\rm{j}}}} {{\rm{l}}\left( {\rm{m}} \right)} \le {\rm{ \mathsf{ β} '}}$ then

6.将节点迁移到目标社区;

7.else

8.节点不进行迁移, 保持原有社区;

9.end if

10.计算社区总模块度totalQ′=$\sum\limits_{{{\text{p}}_{\text{i}}}}{{{\text{Q}}_{\text{i}}}}$；

11.end for

12.if totalQ≠totalQ′

13.计算每个社区内节点之间的链路权重, 更新为新节点环的权重;

14.计算每个社区之间链路权重之和, 更新为新节点之间的链路权重;

15.重复步骤1;

16.else

17.输出社区集合P;

18.end if

2.2.2 控制器部署策略

算法2的核心思想是遍历所有社区, 搜索控制平面总平均传播时延最小、控制路径平均损失率小于可靠性指数R的最佳控制器位置。该算法的伪代码为:

输入  社区集合P, 可靠性指数R

输出  控制器位置集合C

1.初始化社区p₁中控制器c₁的位置使得min L_p1-avg;

2.for社区p₁每一个节点v_i∈p₁ do

3.if(c₁≠v_i) then

4.计算当前社区L_p1-avg;

5.记录当前c₁的位置;

6.end if;

7.for j=2, j≤k do

8.计算当前j个社区的全局平均传播时延min L′_total;

9.记录当前c_j的位置;

10.k=k+1;

11.end for

12.计算δ′;

13.if(min L′_total≤min L_total & & δ′≤R) then

14.min L_total=min L′_total;

15.else

16.返回步骤2;

17.end if

18.end for

3 仿真与分析 3.1 仿真环境

实验基于Java语言, 使用Eclipse IDE软件对本文算法进行仿真。从SNDlib^[19]中选取5种规模不同的拓扑模型来评估本文的部署策略, 拓扑属性如表 1所示。

3.2 参数设置

链路长度:用Haversine公式代替欧几里得距离计算链路长度, 流量传播速度为光速的2/3。

控制器负载:本文假设所有控制器都具有相同的负载能力, 并且每个交换机所需的控制流量都是相同的, 即l(n)=1, 因此可用各社区交换机数量的最大差值表示子网间的负载平衡状况, 实验设定最大社区和最小社区的节点差异度不大于2, 即β′=2。

负载均衡指数:算法的负载平衡指标用各社区控制器管理的交换机标准差来表示, 即$B = \sqrt {\frac{1}{k}\sum\limits_{j = 1}^k {{{\left( {{t_j} - \frac{n}{k}} \right)}^2}} } $, 其中, t_j表示社区j内的交换机个数。B越小, 则该网络负载均衡性越高。

可靠性指标:为保证实验结果的真实可靠, 通过将多次实验结果取平均值来选取可靠性指标R值。

3.3 算法复杂度分析

LCPS算法时间复杂度由以下2个部分组成:

1) 网络社区划分:该算法分为2个阶段, 第一阶段社区间节点转移的时间复杂度为O(n), n为实验拓扑中的链路数量，第二阶段将社区压缩为一个新节点的时间复杂度为O(n+m), m为本轮迭代中节点的个数。因此网络社区划分算法的时间复杂度为O(n+m), 且过程中所需计算量与网络规模呈线性关系。

2) 域内控制器部署:计算k个社区中心的时间复杂度为O(k×n), 计算社区的控制平面总平均传播时延的复杂度为O(k×n), 总共迭代k次, 因此该过程的时间复杂度为O(k²×n)。

综上可知, 整个LCPS算法的时间复杂度为O(k²×n)。

3.4 实验结果分析

为了验证本文算法的性能, 实验比较了原始Louvain算法、LCPS算法和GABCC算法^[15]在传播时延、负载均衡、控制链路可靠性3个方面的差异。

实验1  在不同网络规模下比较3种算法得到的控制器数量, 结果如图 1所示。从图 1可以看出, 原始Louvain算法在不同拓扑下得到的控制器个数均为2, 且GABCC算法与原始Louvain算法在不同拓扑下得到的控制器个数均小于LCPS算法, 这是因为LCPS算法可以根据拓扑大小灵活地划分社区, 确定控制器的数量和位置, 且随着网络规模的增大, 控制器数量呈现递增趋势。图 2显示了在Janos-US拓扑下, LCPS算法划分的社区以及控制器部署位置。从图 2可以看出, 整个网络被划分成4个社区, 其中, 实心代表控制器位置, 空心代表交换机位置, 具有相同形状的节点属于同一个社区。

实验2  实验比较了3种算法在5种不同网络拓扑下的控制平面总平均传播时延, 结果如图 3所示。从图 3可以看出, LCPS算法在降低传播时延方面优于其他2种算法。当网络规模较小时, 3种算法得到的控制平面总平均时延都很接近, 但随着网络规模的增大, LCPS算法与其他2种算法得到的控制平面总平均时延差异逐渐增大。如在Janos-US拓扑下, LCPS算法、原始Louvain算法、GABCC算法得到的控制平面总平均传播时延分别为8.28 ms、9.34 ms、8.61 ms, 相比其他2种算法，LCPS算法的控制平面总平均传播时延分别降低了11.3%和3.8%;在TA2拓扑下, 3种算法得到的控制平面总平均传播时延分别为49.67 ms、63.27 ms、61.20 ms, 相比原始Louvain算法, LCPS算法的控制平面总平均传播时延最多降低了21.4%, 这是由于LCPS算法根据节点相似度定义的链路权重更加合理, 划分的社区内部节点相对紧密, 从而降低了交换机到控制器间的传播时延。

实验3  本文采用负载均衡指数B评价3种算法得到的控制器负载分布状况, 结果如图 4所示。从图 4可以看出, 在不同网络拓扑下, LCPS算法的负载均衡指数明显低于其他2种算法, 且稳定在[0.4, 0.5]之间, 这是由于LCPS算法在划分社区时引入控制器负载差异度, 可以限制社区规模, 平衡控制器负载; 原始Louvain算法的负载均衡状态不可控, 对于不同规模的网络拓扑, 负载均衡指数波动较大, 且高于LCPS算法, 因此可能出现负载分配不平衡的情况。这是由于原始Louvain算法并未对社区的规模进行限制, 社区聚类的过程中没有及时收敛, 社区划分完全取决于网络拓扑结构, 没有考虑负载均衡的因素; GABCC算法基于遗传算法对网络进行划分, 该控制器部署方式过于复杂, 且负载均衡指数仍处于一个较高水平。

实验4  实验测试3种算法在Janos-US拓扑下的控制链路可靠性。本文只考虑链路发生故障的场景, 假设所有的链路具有相同的故障率, 单位长度链路故障率p_l取值为[0, 0.1]。图 5表示链路故障率与控制链路平均损失率之间的关系。从图 5可以看出, 随着链路故障率的逐渐增大, 控制链路平均损失率呈逐渐增长的趋势。当链路故障率相同时, LCPS算法的控制链路平均损失率最低, GABCC算法最高。随着链路故障率不断增大, GABCC算法的控制链路平均损失率增长速度最快, LCPS算法最慢。当链路故障率为0.1时, GABCC算法的控制链路平均损失率高达0.367, 这是因为GABCC算法在部署控制器时并未考虑控制链路可靠性, 因此当发生链路故障时, 数据传输将会很快中断。相比GABCC算法和原始Louvain算法, LCPS算法的部署方案能够有效降低控制链路平均损失率, 提高控制链路可靠性。

4 结束语

本文基于改进的Louvain社区检测算法实现大规模SDN网络下多控制器的均衡部署。通过在划分子网时引入控制器负载差异度, 可以限制子网的大小, 从而确保网络均衡的划分。在部署控制器时, 综合考虑控制平面总平均传播时延和控制链路可靠性, 以达到最小化控制平面传播时延和控制链路平均故障率的目的。仿真结果表明, 本文提出的控制器部署策略可以根据不同规模的网络拓扑, 划分合适的网络分区, 有效降低时延, 提高控制链路可靠性。下一步将采用基于迁移效率感知的动态交换机迁移策略^[20]，对网络流量动态变化的场景进行研究，以平衡控制器负载、减小控制器响应时间。