基于可靠性与负载优化的多控制器弹性部署算法

陆 , ,

(国家数字交换系统工程技术研究中心,郑州 450002)

0 概述

随着软件定义网络(Software Defined Network,SDN)[1]的引入,传统网络中逻辑集中式架构开始朝着控制和数据平面分离的方向转变,这种转变能够方便网络的管理和维护,因此,受到学界和工业界的广泛关注。随着SDN网络规模的不断扩大,单个控制器已经难以满足现有的网络需求。为提高网络的可拓展性,避免单点失效,研究人员在集中式控制的基础上提出将网络划分为多个域,通过部署多个控制器来实现逻辑上集中、物理上分布的SDN网络[2]。多控制器的部署主要有3个关键:控制器的部署数量;控制器的部署位置;交换机与控制器间的映射关系,即哪些交换机由哪些控制器控制。一个网络所需的控制器数量由实际场景所决定,因此,本文主要研究和分析控制器的部署位置和交换机与控制器间的映射关系。

在实际中,要实现控制器的合理部署,会面临较多挑战。控制层的失效概率要满足特定的要求以保证网络的可靠性。同时,要利用控制器的负载优化来保证负载的合理分配,并减少交换机到控制器的时延,以提高网络性能。

目前,针对多控制器部署的研究主要分为两类:

1)考虑时延、负载均衡等因素,通过多目标优化来求解控制器部署的位置。文献[3]考虑控制报文的平均时延和最差时延后确定控制器的最佳部署位置。文献[4]针对控制器的负载过大导致时延显著增加的问题,提出在满足控制器负载均衡的条件下,寻求平均时延最优部署。文献[5]考虑额外的目标,如控制器之间的负载平衡问题,以在不同目标相互竞争的情况下,在不同的位置选择之间进行权衡。文献[6]利用谱分类算法,综合考虑时延与容量限制下的多控制器负载均衡问题,然后提出KCBP(K Controllers Balanced Placement)算法,该算法是基于Normalized Cut的标准化分割方式。文献[7]在K-means算法的基础上提出优化K-means算法,为避免初始值的选取对分区的影响,其使用一种逐步递进分区的方式。这类方案均以提高网络通信质量、设备利用率为目标,但是忽略了设备故障对网络的影响。

2)考虑控制器的可靠部署。文献[8]引入失效路径百分比来评价SDN网络的可靠性,并用数学方法证明可靠控制器部署(Reliable Controller Placement,RCP)是NP-Hard问题。文献[9]建立Survivor模型,其考虑路径连通性、控制器容量和快速恢复性3个指标。文献[10]通过分析表明,控制器位置选择对SDN网络可靠性有重要影响,同时,过多的控制器会显著增加运营成本。这类方案在考虑控制层的可靠性时,没有考虑数据转发层对控制层可靠性的影响。由于转发层和控制层实际上是复用同一个网络,因此当数据流量超过链路带宽时,数据层的拥塞也会导致控制层的失效。同时,这类方案仅通过考虑网络可靠性指标来进行控制器部署,其对于交换机分配、网络时延等因素缺乏考虑,容易导致控制器负载失衡。

针对上述方案存在的不足,本文在谱聚类思想的基础上,对控制路径时延、控制路径可靠性和控制器负载均衡3个指标进行描述,提出一种基于可靠性和负载优化的多控制器弹性部署(Multi-Controllers Elastic Placement,MCEP)算法。首先,利用节点间的相似关系将网络拓扑表示为相似矩阵,并将多控制器部署问题转化为相似矩阵的行向量分类问题;然后,采用基于模拟退火的改进k-medoids算法对行向量进行分类,以实现多控制器弹性部署;最后,通过实验验证该算法的可行性。

1 问题重述与建模

1.1 问题重述

在SDN中,控制器部署位置和交换机与控制器之间的映射关系会对整个控制网络的可靠性和性能造成影响。图1所示为在由6个节点和2个控制器组成的SDN网络中,3种不同的控制器部署方式对控制网络的影响。其中,实线表示物理链路,虚线表示控制链路。

图1 控制器部署方式对网络性能的影响

图1(a)、图1(c)表示相同的控制器部署位置、不同的交换机与控制器映射关系对控制器负载的影响。从中可以看出,在控制器处理容量相同的情况下,图1(a)的控制器负载更均衡。图1(b)、图1(c)表示网络分区相同、控制器部署位置不同对网络可靠性的影响。从中可以看出,假如B节点与C节点之间的物理链路发生故障,则图1(c)中有一条控制路径会失效,图1(b)中有2条控制路径会失效,即图1(c)的控制网络比图1(b)更可靠。

基于上述分析,本文所要研究的问题总结如下:

1)在给定网络拓扑和控制器数量的情况下,确定控制器的部署位置。

2)确定网络中交换机与控制器间的映射关系。

1.2 问题建模

将物理网络表示为一个无向图G(V,E,B)。其中,V是图中节点(交换机)的集合,V=(v1,v2,…,vn),|V|表示节点个数,E是边eij的集合,eij表示节点i和节点j之间直连链路的长度,非直连链路eij取值为0,B表示直连链路eij的带宽。对于SDN控制层,控制器的控制路径可以视为物理网络上的覆盖网络,如图1所示。

为解决多控制器部署问题,本文定义如下指标。

定义1(控制路径失效概率(Control Path Failure Probability,CPFP)) 路径失效可分为2种情况:

2)由于控制路径实际上是与物理转发层使用同一个网络,因此转发层数据流量过大会导致一些链路的拥塞,也会影响控制链路的可靠性。假设直连链路eij带宽为bij,流量为fij,当流量处于带宽允许的范围内时,不会导致链路拥塞,而当流量超过一定的阈值时,流量越大,链路拥塞程度越高。当流量大于带宽时,则认为该链路不可用,即拥塞的概率为1。因此,链路拥塞的概率可表示为:

其中,δ表示阈值。

综合考虑物理失效与链路拥塞,直连链路eij可用概率APij表示为:

∀i,j∈n,APij=APji

(4)

式(3)、式(4)表示链路可用概率与方向无关。对于一条控制路径Pst,其可用的概率取决于路径上各条直连链路的状态。因此,控制路径失效概率可表示为:

本文采用控制路径平均失效概率(Control Path Average Failure Probability,CPAFP)对网络的整体可靠性进行评估,其表示为:

定义2(控制路径时延(Control Path Delay,CPD))在SDN网络中,当新流到达交换机时,由交换机交付给控制器处理,该过程会产生时延,且时延对于SDN网络的性能有较大影响。通常情况下,时延可以分为4个方面:传播时延,处理时延,排队时延,发送时延。对于广域网而言,传播时延大于其他3种时延。本文主要进行广域网的SDN研究,因此,使用传播时延近似表示网络时延。

控制路径平均时延(Control Path Average Delay,CPAD)是所有控制路径时延的平均值,可表示为:

定义3(控制器负载标准差(Controller Load Standard Deviation,CLSD)) 控制器轻载会导致控制器性能浪费,而控制器过载时,由于控制器处理性能跟不上流请求速度,从而导致时延大幅增加,网络性能下降。因此,在多控制器位置部署中,需要考虑控制器之间的负载均衡。

本文将SDN中控制器的负载视为控制器因管理交换机而担负的计算负载。为论述方便,本文将一个控制器的负载视为该控制器所管理的交换机数目。控制器负载差异表示为各控制器实际管理交换机数量的差异,可通过各控制器所管理交换机数量的标准差来表示:

基于以上3个指标的定义,低时延与高可靠的多控制器均衡部署问题即为找到一个合适的方法,使CPAFP、CPAD、CLSD3个指标均达到最小。可表示为:

min[CPAFP,CPAD,CLSD]

(10)

s.t.CPFPij

(11)

CPDij

(12)

|SCj|

(13)

式(11)表示控制链路失效概率不能高于P,式(12)表示控制链路的最差时延不能高于D,式(13)表示单个控制器所管理交换机的个数不能多于N。

多控制器均衡部署问题是一个带约束的多目标优化问题,其难以在多项式时间内求得最优解。因此,本文采用谱聚类思想来求解。为实现对网络的合理划分,在对图上的节点进行聚类时,原则上将距离较近的节点聚为一类。而根据本文的需求,可以用2个节点之间的通信时延和可靠性来定义节点距离。此处,本文引入节点相似度来计算节点间的相似程度。

定义4(节点相似度) 相似度表示2个节点相似的程度,相似程度越高,表示2个节点归为一类的可能性越大。对应于本文的路径可靠性与时延,任意2个节点之间的时延越小,通信可靠性越大,其相似程度也越大。因此,首先定义包含可靠性和时延的节点相似度。因为CPEP是取值为(0,1)的概率值,而CPD是一个具体的数值,为方便两者的比较,对CPD做归一化处理:

其中,maxCPD表示网络中链路的最长时延,minCPD表示网络中链路的最短时延。

当2个节点之间的链路可靠性低于可容忍的可用概率P或时延超过可容忍的最大时延D时,将这2个节点的相似度设为0。因此,2个节点之间相似度wij表示为:

(15)

其中,α表示时延与可靠性之间的权值,当0≤α<0.5时,聚类更偏向于可靠性,当0.5≤α≤1时,聚类原则上偏向于时延。由各节点相似度可以得到表示整个网络拓扑的相似度矩阵W。

对于一个网络拓扑G,将其切割为2个子图A、B,定义A和B之间的切割为:

由切割的定义可得,若将网络拓扑切割为k个子图,则最小割可以表示为:

图2 最小割与比率割的网络分区结果对比

基于负载均衡的考虑,本文采用比率割(RatioCut)作为图划分的原则。RatioCut不仅考虑最小化切割Cut,而且考虑最大化每个子图节点的个数。RatioCut表示为:

其中,|Ai|表示区域Ai的节点个数。当子图划分不均匀时,如某个区域只包含很少的节点,则该子图的|Ai|会很小,导致总的RatioCut值很大。而整个图中的节点数是一个固定值,即|A1|+|A2|+…+|Ak|=|V|,由均值不等式可知,当各区域节点个数趋向均匀时,RatioCut最小。因此,式(18)的求解可以转化为求RatioCut的最小值,即:

argminRatioCut(A1,A2,…,Ak)

(19)

由于W是相似度矩阵,根据谱理论可知,度矩阵D表示为:

D=diag(d1,d2,…,dk)

(20)

L=D-W

(21)

对于任意n维向量f=[f1,f2,…,fn],有:

为对网络节点进行聚类,需要为每个节点赋予一个向量来指示该节点的类别。引入指示向量Hn×k=[h1,h2,…,hk]。对于任意一个n维向量hi,定义其元素hij为:

式(24)是将网络拓扑切分成2个子图的结果,因此,对于k个子图切分的RatioCut,可表示为:

Tr(H′LH)

(25)

因此,求解RatioCut最小值问题就转化为求解矩阵H′LH迹的问题,即:

argmin Tr(H′LH)

s.t.H′H=Ik

(26)

由Rayleigh-Ritz定理[11]可知,若L为实对称矩阵,其特征值λ1≤λ2≤…≤λn,且其对应的特征向量v1,v2,…,vn正交,则:

min Tr(H′LH)=λ1+λ2+…+λk

(27)

其中,最小值对应的矩阵H=[v1,v2,…,vk]。

由于H中向量的取值受到限制条件的影响,其取值是离散的,因此该问题的求解是NP-Hard。为求解该最小值,可将其进行松弛。将hij的取值放宽到实数范围[6],则最小实数解出现在矩阵L的前k个最小特征值对应的特征向量组成的矩阵H中。此时,H矩阵由n个k维行向量组成,其分别表示n个节点的k维坐标,每个节点的k维坐标分别代表该节点的k维属性,越相似的节点,其k维属性越相近。

在获得H矩阵后,谱聚类通常采用K-means算法对k维坐标系中的n个点进行分类。由前述推论可知,谱聚类的实质是一个降维过程,其将n×n维矩阵的分类问题转化为n×k维矩阵的分类问题,通常k<

2 算法描述与分析

2.1 算法描述

针对现有多控制器部署方案中存在控制路径可靠性差和控制器负载不均衡的问题,本文提出一种基于可靠性和负载优化的多控制器弹性部署算法MCEP。MCEP算法基于改进的RatioCut算法,并使用模拟退火的k-medoids算法对其聚类过程进行优化。MCEP算法的主要改进体现在:

1)采用k-medoids代替RatioCut中原有的K-means聚类,将中心点的选取限制在当前聚类所包含的数据点集合中,防止孤立点对聚类的影响。

2)初始聚类后,增加一个模拟退火的调整步骤,避免陷入局部最优。

对由矩阵Hn×k表示的n个节点进行分类,任意选取k个节点,按照k-medoids算法迭代,直至稳定,记录稳定状态时的分类结果并更新最优结果,用式(28)计算此时目标函数obj。然后将类中某个节点归入其邻居节点的类别,按照k-medoids算法迭代,直至能够稳定计算目标函数obj,若调整后,新obj的值减小,则保留调整之后的结果作为新的分类,并更新最优结果;若调整后obj的值增加,则以一定的概率值接受新结果。同时,按照退火速率降低该概率值。在连续多次退火后,结束调整,以最优结果作为最后的分类结果,输出。

MCEP算法具体描述如下:

算法1MCEP算法

输入控制器个数k,权重值α,链路流量矩阵F,离开温度Tmin,初始温度Torg,降温速度r

输出控制器位置bestVc,交换机与控制器之间的映射关系bestSC

1.for each i,j∈V do

2.CPFPst←式(5),CPDij←式(7)

3.end for

4.W←式(16),D←式(20),L=D-W

5.[H]=eigs(L,k),

6.tempVc←initKCenter(H,k),T=Torg

7.调用k-medoids,得tempVc,tempSC

8.bestVc←Vc←tempVc,bestSC←SC←tempSC

9.while(T>Tmin)

10.随机选择一个节点,将其归入邻居节点类别;调用k-medoids,得tempVc,tempSC

11.Δ=obj(tempSC)-obj(SC)

12.if (Δ≤0) SC←tempSC

13.if (obj(SC)

14.bestSC←SC,bestVc←Vc

15.end if

16.else

17.SC←以exp(-Δ/T)的概率将tempSC赋值

18.end if T=T*r

19.end while

20.return bestSC,bestVc

在MCEP算法中:第1行～第5行,得到矩阵L的特征值和特征向量,并从中选取k个最小特征值对应的特征向量组成矩阵H;第6行～第8行,使用传统的k-medoids算法对表示节点的k维行向量进行第一次分类;第9行～第19行表示基于模拟退火对分类结果进行调整;第20行输出最优的分类结果。

2.2 算法复杂度分析

MCEP算法首先利用Johnson算法[12]计算任意2点之间的最短路径,然后通过式(5)和式(7)得到相应的CPFP和CPD,其时间复杂度为O(V2lgV+VE)。计算矩阵W、D、L的时间复杂度为O(V),计算特征向量组成的矩阵H,其时间复杂度为O(V3),k-medoids算法的时间复杂度为O(V2kt),其中,t为k-medoids算法的迭代次数,因为在每次模拟退火的步骤中都需调用k-medoids进行分类,所以其调整时间为O(V2ktlogr(Tmin/Torg))。因此,MCEP算法总的时间复杂度为O(V3+V2logrT)。

3 实验结果与分析

3.1 实验环境

为评估MCEP算法的有效性和可行性,本文以实际网络拓扑OS3E[13]作为仿真进行分析。OS3E拓扑结构如图3所示,其由34个节点、42条边组成。仿真中控制器部署方法使用Matlab模拟实现,实验机配置为Intel Core i5 2.4 GHz,8 GB RAM。

图3 OS3E网络拓扑

通常链路流量处于动态范围内,且每条链路的带宽也并不相同。为使实验易于实现,在不影响结果的前提下,假定每条物理链路的带宽bij=50 Mb/s。所有链路有相同的流强度,且流量f服从强度为20 Mb/s的泊松分布[14]。链路物理失效的概率取决于链路材料和外部环境,在本实验中,假设所有的链路具有相同的物理失效概率,每100 km失效概率为0.01[15]。

3.2 算法性能分析

实验1验证在不同参数设置下MCEP算法的控制器部署和分区情况。对MCEP算法进行不同参数仿真,网络划分和控制器部署结果如图4所示。其中,相同的符号表示处于同一个子域,黑色实心符号表示控制器部署位置。图4(a)、图4(b)表示将网络分为2个区域时,α值不同对网络分区的影响。其中,α=1表示只考虑链路可靠性指标,此时长度较长的链路更有可能被切断。从图4(a)、图4(b)可以看出,尽管时延和可靠性都与链路的长度相关,但是链路失效的概率与链路长度成指数关系,而时延与链路长度成线性关系。因此,可靠性对链路长度更敏感。图4(c)、图4(d)的参数分别为k=3,α=0.5和k=4,α=0.5,其分别将网络划分成3个和4个区域,且划分出的子网大小较均匀。这表明可以通过改变MCEP的参数来调整SDN网络的可靠性和负载均衡之间的权衡关系。

图4 不同参数时MCEP算法的部署情况

实验2将MCEP算法与KCBP算法[6]、优化的K-means算法[7]在可靠性、时延与负载均衡3个指标上进行对比。实验中MCEP算法的权重α默认取0.5。图5所示为3种算法的控制路径可靠性对比结果,从中可以看出,随着控制器个数的增加,3种算法的可靠性均有所提高,原因是控制器数量增加,可以使每个子域更紧密,从而使可靠性得到提升。但在控制器数量相同时,MCEP算法的可靠性明显大于其他2个算法,与另外2个算法相比,MCEP算法的可靠性平均提升了17%。

图5 3种算法控制路径可靠性对比结果

图6所示为3种算法的平均时延情况,从中可以看出,随着控制器数量的增加,3种算法的控制路径平均时延均有所下降。其中,MCEP和KCBP算法在数值和下降趋势上都很接近,而优化K-means算法在时延指标上相对较差。这是由于优化K-means算法仅考虑负载均衡,没有考虑其他因素的约束,而MCEP和KCBP算法将时延作为控制器部署的一个参考因素。

图6 3种算法控制器平均时延对比结果

图7所示为3种算法的控制器负载标准差对比情况,从中可以看出,当控制器个数较少时,与优化K-means算法相比,MCEP算法的负载均衡性相对较差,但随着控制器个数的增加,MCEP算法负载均衡性可以得到显著优化。这是由于MCEP算法在部署控制器时,会同时考虑负载均衡、时延和可靠性3个指标。如图3所示,OS3E拓扑节点分布不均匀,东北区域节点较密集。当控制器数量较少时,MCEP算法会将东北区域置于一个控制器之下,这样虽然导致负载不均衡,但是可以保证低时延和高可靠性。而随着控制器数量的增加,MCEP算法通过在密集区域部署多个控制器,可以在不降低时延和可靠性的基础上,明显减少各控制器的负载差异。

图7 3种算法控制器负载标准差对比结果

4 结束语

为提高控制路径的可靠性并优化控制器负载,本文提出控制路径可用概率、控制路径平均时延和控制器负载标准差3个度量指标,在此基础上,设计一种基于可靠性和负载优化的多控制器弹性部署算法MCEP。仿真结果表明,相比KCBP和优化K-means算法,MCEP算法能够在保证低时延和负载均衡的基础上,使控制路径的平均可靠性提高17%。今后将进一步研究如何利用谱聚类算法来提高本文多控制器部署算法的鲁棒性。