一种改进社区检测算法的SDN控制器部署策略

赵季红,孙天骜,曲 桦,张 茵,翟凡妮

(1.西安邮电大学 网络空间安全学院,西安 710061; 2.西安交通大学 软件学院,西安 710049)

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=(v1,v2,…,vn),n=|V|表示交换机个数。E表示网络中交换机之间的链路集合,E=(e1,e2,…,em),m=|E|表示链路个数,e(u,v)∈E表示交换机u和交换机v之间相连的链路。C表示控制器集合,C=(c1,c2,…,ck)。将网络划分成K个不相交的社区,P表示划分的社区集合,P=(p1,p2,…,pk),每个社区包含一个控制器和任意t(1≤t≤n)个交换机,pj=(v1j,v2j,…,vtj,cj)。

定义1映射关系矩阵Xn×n表示控制器与交换机的映射关系,如式(1)所示,若交换机vi映射到控制器cj,则xi,j=1,否则为0。

(1)

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

(2)

其中,mind(vj,cj)表示交换机vj∈pj与其所属控制器cj∈pj之间的最短路径。

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

(3)

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

(4)

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

Ltotal=Lsc-avg+Lcc-avg

(5)

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

(6)

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

(7)

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

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

minLtotal

(8)

s.t.β≤β′

(9)

δ≤R

(10)

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

2 本文算法描述与分析

2.1 本文算法分析

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

(11)

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

(12)

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

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

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

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)所示:

(13)

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

(14)

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

2.2 算法步骤

2.2.1 网络社区划分算法

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

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

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

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

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

算法1的伪代码为:

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

输出社区集合P

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

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

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

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

7.else

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

9.end if

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.初始化社区p1中控制器c1的位置使得min Lp1-avg;

2.for 社区p1每一个节点vi∈p1do

3.if(c1≠vi) then

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

5.记录当前c1的位置;

6.end if;

7.for j=2,j≤k do

9.记录当前cj的位置;

10.k=k+1;

11.end for

12.计算δ′;

15.else

16.返回步骤2;

17.end if

18.end for

3 仿真与分析

3.1 仿真环境

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

表1 实验拓扑属性

3.2 参数设置

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

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

可靠性指标:为保证实验结果的真实可靠,通过将多次实验结果取平均值来选取可靠性指标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(k2×n)。

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

3.4 实验结果分析

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

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

图1 3种算法在不同拓扑下的控制器个数

图2 Janos-US拓扑下控制器位置

实验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 3种算法在不同拓扑下的控制平面总平均传播时延

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

图4 3种算法在不同拓扑下的负载均衡指数

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

图5 3种算法的控制路径平均损失率

4 结束语

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