时延和可靠性感知的多控制器均衡部署策略

赵文文, 孟相如, 康巧燕, 苏玉泽

(1.空军工程大学信息与导航学院，西安，710038；2.94303部队, 山东潍坊, 261000)

传统网络因其数据和控制平面高度耦合，使得网络的实时动态调整与快速升级部署比较困难。软件定义网(software-defined networks, SDN)通过对网络数据平面和控制平面的功能解耦，让网络功能扩展更加灵活高效，并通过北向接口向上层用户提供程序接口，为网络运行维护的程序化、自动化提供了可能。

多控制器SDN中如何多控制器SDN数量和部署位置，并合理划分控制域等问题一直是当今研究的热点。Heller等人在2012年首次提出SDN中控制器部署是NP-Hard问题，并研究了不同部署位置对系统平均时延和最大时延带来的影响[1]。文献[3～5]分别从不同角度，考虑了时延和负载指标下多控制器部署问题，而对可靠性问题涉及不足。文献[6]在考虑控制器负载和响应时间的基础上，研究了在考虑可靠性情况下的控制器部署策略，然而其仅考虑了最差时延，未考虑全网平均控制时延和控制器之间负载均衡差异，且其使用的细菌觅食算法收敛性较差。文献[7]通过综合权衡节点效能和路径质量评估节点可靠性，并设定负载均衡因子以优化控制器部署位置，而没有考虑控制时延因素。文献[8]建立了一种针对链路故障引起的控制时延变动的SDN控制网络可靠性模型，提出了一种控制器部署算法，却并未考虑负载均衡因素。文献[9]以交换机节点的负载和拓扑中心度为依据，建立网络可靠度模型，通过该模型计算满足可靠性要求的控制器部署方案，但其仅以节点拓扑中心度作为可靠性依据，对网络实际运行时的可靠性考虑较少。文献[10]在已知交换节点和控制器节点故障率的条件下，建立了一种可容错的控制器部署模型(fault tolerant controller placement，FTCP)，但其仅考虑了可靠性，对时延、负载等因素没有考虑。

文献[7]、文献[11]均提出了随机部署算法，在满足控制器负载容量限制的前提下，采用一定随机策略在交换节点中选取控制器部署位置，随机部署策略在计算速度上有一定优势，但由于没有考虑其他因素，导致所得解空间的整体性表现不佳。文献[12]提出了用k-means聚类算法解决控制器部署问题，将控制器部署和控制域划分转换为类簇中心点的确定和类簇的划分问题，然而其仅依据物理距离进行控制域划分，没有考虑负载均衡等问题，且初始类簇数量和类簇中心点的选取对聚类效果的好坏有很大的影响。

综上所述，针对控制器部署问题，当前研究只考虑了网络时延、负载均衡和可靠性中的部分因素，而对上述因素综合考虑较少[13-15]，针对该问题，本文在综合衡量时延、可靠性和负载均衡因素的基础上，建立了控制器部署评价模型，提出了基于模拟退火-遗传算法(simulated annealing genetic algorithm，SAGA)的时延和可靠性感知的多控制器均衡部署策略(delay and reliability awared balancing strategy based on SAGA，SAGA-DRABS)。

1 问题描述与模型构建

SDN按照控制信息流经的路径不同，分为带内控制SDN和带外控制SDN。本文讨论采用带内控制方式时SDN的多控制器部署问题，即按照一定的评价策略和指标，在底层交换网络选取合适的交换机节点，部署SDN控制器，并对控制器所管理的交换节点合理划分，使网络性能达到最优。

底层交换网络用加权有向图G(S,E)表示，其中S={s1,s2,…,sn}，Si为交换机节点，n为交换机的数量，E={eij|i,j≤n}为图G中边的集合，其中eij=为节点si与sj之间的边，边的权值wij为路径的物理距离。将交换网络划分为k个控制域等价于将图G划分为k个子图，可以表示为：

Gcut={G1,G2,…,Gk|k≤n},∩Gj=Ø(Gj∈Gcut)

(1)

控制器用集合C={c1,c2,…,ck|k≤n}表示，其中cj(j≤k)为控制域Gj的控制器。控制域Gj的大小为|Gj|，表示Gj中交换机的数量。如前所述，在对G进行分割时，主要考虑以下因素：控制时延、负载均衡度、可靠性和DRB度量(MDRB)。

1.1 控制时延

SDN控制时延是SDN南向接口运行效率的重要表征，也是SDN控制网络最重要性能指标之一。SDN控制时延包括控制器与控制器之间的时延和控制器与交换机之间的时延，在实际应用中，控制器东西向接口之间通常用高速度大容量高带宽专线连接，与控制器与交换机之间的时延相比，控制器之间的时延几乎可以忽略不计，因此本文主要考虑控制器与交换机之间的时延，用网络平均时延进行衡量，为此，先定义各节点时延如下：

(2)

α+β+γ=1

(3)

0≤α，β，γ≤1

(4)

式中：α、β、γ为比例参数，针对不同场景可以设置不同的比例参数，比如，在数据中心网络中，由于各交换节点部署较为集中，传播时延对控制器部署影响不大，可设置γ的值为0。

(5)

1.2 负载均衡度(BL)

本文用负载均衡度来衡量SDN控制网络中各控制器的负载均衡情况，为此定义各控制器的负载和负载均衡度如下所示：

定义3控制器cj的负载(RNj)。控制器负载主要由四部分组成：①处理事件中packet_in请求数据包并将处理结果传递给应用程序和交换机；②维护控制域内网络视图；③与其他控制器交互后形成全局网络视图；④向南向接口安装由北向接口产生的流量。网络场景不同，各部分的权重也不同，然而处理事件中packet_in请求数据包通常被认为是控制器负载的最重要部分[12]。因此，本文用控制器处理的packet_in请求数据包的数量作为控制器负载的度量。在控制域Gj中，设交换机si向控制器cj发送packet_in请求的数量为pi，控制器cj的负载RNj可定义为式(6)，其中Ωj为控制器cj的额定负载。

(6)

(7)

τ+ξ=1

(8)

式中：τ、ξ为权重参数；BL1表示各控制器之间的负载差额，BL1越小表示各控制器之间负载越趋于均衡；BL2表示各控制器负载方差。BL1和BL2定义见式(9)、(10)。

(9)

(10)

定义4控制器cj的负载率(ηj)。指控制器cj中，当前负载占额定负载的比率，当控制器达到额定负载时，控制器对未知数据包的请求开始排队处理。

(11)

在对RN进行控制域划分时，为控制器cj的负载率ηj设定负载阈值ηthr，使ηj≤ηthr，当ηj>ηthr时，重新调整控制域。

1.3 可靠性

SDN控制网络中，控制器为每个交换节点分别维护一条控制路径，控制路径的可靠性表示控制信息和流表信息从控制器到交换节点的可达程度，流表和控制信息的延迟可能造成控制时延和网络时延抖动。在带内控制的情形下，当底层交换节点的可靠性不同时，控制器的部署位置会导致各控制路径的可靠性也不尽相同[7-10]，图1中，A、B、C表示交换机节点，D代表控制器，假设交换机的可靠性分别为0.9、0.6、0.3，橙色表示控制器部署位置，在忽略链路可靠性、仅考虑节点可靠性的前提下，3种部署方案所形成控制路径的可靠性分别为：R(a)=0.9+0.9×0.6+0.9×0.6×0.3=1.602；R(b)=0.6+0.6×0.3+0.6×0.9=1.32；R(c)=0.3+0.3×0.6+0.3×0.6×0.9=0.642。

图1 部署位置对可靠性的影响

可以看出，对同一交换网络，不同的控制器部署位置会导致控制路径的可靠性也不同。本文在假定各交换节点的可靠度已知的前提下，分别定义了控制路径、控制域和网络整体可靠性。进行控制器部署就是选取合适的部署策略，使得网络的整体可靠性达到最高。

定义5控制域可靠度(RGj)。SDN中，每个控制域由多条控制路径组成，本文定义控制域的可靠性度量(RGj)为各控制路径可靠性之和，如式(12)所示。

(12)

式中：Rk表示交换节点sk的可靠度，为0到1区间的正数；Rij指控制器cj到交换节点si的控制路径Pij的可靠性，该可靠性度量了控制信息和流表信息到交换节点的可达程度。

定义6控制网络可靠度(Rtotal)。控制网络可靠度是全网的可靠性度量，为SDN中所有控制域的可靠性之和，如式(13)所示：

(13)

式中：RGj为控制域Gj的可靠度。

1.4 DRB度量(MDRB)

基于上述定义，本文提出用DRB度量MDRB来衡量控制器部署策略的整体性能，其与时延和负载均衡度成反比，与可靠性成正比，见式(14)：

(14)

σ+υ+ω=1

(15)

0≤σ,υ,ω≤1

(16)

式中：QT、QB、QR为缩放系数，用于平衡量纲，σ、υ、ω分别为比例系数，总和为1。

根据以上指标，基于时延和可靠性感知的多控制器均衡部署策略就是找到一个合适方案，使得目标值达到最大，为此，建立带约束的最优化模型如下式所示：

max{MDRB}=

(17)

σ+υ+ω=1

(18)

s.t.0≤σ,υ,ω≤1

(19)

ηi≤ηthr

(20)

式中:QT、QB、QR为缩放系数，用于平衡量纲；σ、υ、ω分别为比例系数，总和为1，式(20)表示控制器的负载不超过其额定负载。

2 策略描述

2.1 模拟退火-遗传算法(SAGA)

遗传算法借鉴生物进化相关理论，将生物种群染色体编码、选择、交叉等进化机制引入复杂非线性问题解空间的寻优过程，同时通过变异操作帮助算法跳出局部最优陷阱，一定程度上保证了解空间的全局特性。然而遗传算法由于其子代种群的个数与父代适应度大小成正比，且在算法早期因个体适应度差异较大，容易使少数优秀个体的后代占满种群造成“早熟”，而在后期又由于适应度趋于一致，无法较好地发挥优秀个体的遗传作用，导致算法较早陷入局部最优解。

模拟退火算法(SA)将待优化问题求解过程模拟为统计热力学中的物理降温过程，在搜索到最优解(达到热平衡)之前，反复降温，每次降温采用Metropolis接受准则，使算法跳离局部最优的“陷阱”。

本文将模拟退火算法与遗传算法相结合用于控制器部署位置选择，由于模拟退火算法和遗传算法可以互相取长补短，通过在遗传算法后期适应度趋于一致时，引入模拟退火的降温过程，对种群采用Metropolis接受准则进行取舍，较好地克服了传统遗传算法的早熟现象，使该算法更有效、快速地搜寻到全局较优解。

2.2 部署策略

针对上述模型，本文引入模拟退火遗传算法提出了一种时延和可靠性感知的多控制器均衡部署策略SAGA-DRABS。图2为策略的具体流程。

图2 SAGA-DRABS策略流程示意图

SAGA-DRABS首先采用随机选取的办法确定控制器部署位置，组成原始解空间并编码后，形成初始种群，利用式(15)计算各部署位置的MDRB值，即该种群所有个体的目标值，得出SAGA的适应度值fitValue。而后进入退火降温过程，对由不同部署位置的解空间形成的初始种群利用迭代方法进行交叉、选择、变异等进化操作形成子代个体，每一次进化操作(交叉、选择、变异)后，计算新个体的适应度值Mnew。若Mnew>MDRB，说明进化后的子代优于父代个体，将该子代个体加入种群，否则，利用Metropolis接受准则进行取舍，形成本轮最优种群。继续进入下一轮降温过程，每一轮降温过程都是在上一轮最优种群的基础上，进行交叉、选择、变异等进化操作后，以概率p进行取舍得出最优种群，如此反复，直至达到最终温度，此时从所得最优种群中选取最优个体即所求结果。

pchoose=exp ((Mnew-MDRB)Ti)

(21)

式中：Ti为每轮降温过程的当前温度值；Mnew和MDRB分别表示每次进化形成个体的适应度值。算法伪代码如表1所示。

表1 SAGA-DRABS策略伪代码

3 实验仿真

3.1 仿真设置

基于Matlab平台进行实验仿真，仿真在随机生成的包含80个交换节点、604条物理链路，分布在2 500 km范围内的模拟网络(见图3)上进行。实验中，假设到达交换机的未知流数量服从以λ=1/14、μ=1/20为参数的泊松分布。控制器额定负载服从以σload=1 000、μload为参数的高斯分布，见式(23)：

图3 仿真网络

(23)

式中：np为未知流数量；k为控制器数量；ηi为控制器额定负载率。设节点可靠度Ri服从μreliability=0.95、σreliability=0.1为参数的高斯分布。网络传输带宽为1 Gbits/s。

SAGA算法变量初始化方面，设定种群大小Npop=10，最大进化次数Xmax=10，交叉概率Pinter=0.6，变异概率Phet=0.05，退火初始温度Tint=100，变异概率Ccool=0.6，终止温度Tend=0。

3.2 仿真结果与分析

为对比不同部署策略对SDN性能的影响，本文将SAGA-DRABS分别与采用k-means聚类策略、贪心策略(greedy deployment, GRE)和随机部署(random deployment, RD)策略进行控制器部署时的性能进行了比较。对所有策略进行50次计算后取各自结果的算数平均。

图4显示当控制器数量为4时，通过SAGA-DRABS策略对图3所示网络进行控制器部署和控制域划分的结果，图中不同颜色表示不同控制域，其中控制器部署位置用相应颜色的“★”表示，编号用红色标出。

图4 控制器部署结果

图5显示SAGA-DRABS的寻优曲线，本次计算共经过11次降温，每次降温过程中，分别进行10轮遗传算法迭代，每轮迭代求出当前局部最优解，后一次降温均在前一次降温取得最优解的基础上进行新的遗传算法迭代。SAGA-DRABS中每次降温可以看作一个完整的传统遗传算法流程，可以看出，该策略在传统遗传算法的基础上，又进行了多次降温过程，使当前最优解跳出局部陷阱，进一步增强了解空间的全局特性。

图5 SAGA-DRABS寻优曲线

图6显示不同控制器数量情况下，各算法所得部署策略的MDRB值。可以看出，相比其他算法，通过 SAGA-DRABS所得的MDRB值更高，主要原因是该策略在考虑网络平均控制时延最小的同时，也将可靠性和负载均衡度纳入评价指标，同时通过SAGA算法使所求结果具有较好的全局特性。作为对比，k-means算法主要是基于距离影响的全网平均控制时延因素所得的部署策略，在整体目标衡量上要劣于SAGA-DRABS，GRE算法主要基于当前最优解寻求控制器最佳部署策略，其MDRB值与SAGA-DRABS算法相比，明显缺乏全局最优特性。而RD算法主要采取在满足负载率的情况下的随机部署方法，其DRB值也相应为最小。

图6 各策略DRB度量指标

图7～图9显示在不同控制器数量情况下，各算法所得部署策略在全网平均控制时延、负载均衡和可靠性度量上的表现，可以看出，由于k-means算法主要基于距离因素进行控制器部署，因此在时延表现上要略优于SAGA-DRABS。而在负载均衡方面，由于贪心算法主要基于当前局部的DRB值，既没有考虑DRB值的全局性，也缺乏对负载均衡的单独考量，导致该算法相较其他算法，所得策略在负载均衡方面表现较差，而随机部署算法由于在部署时仅考虑控制器负载容量限制，导致该算法在负载均衡度量上表现较优。在可靠性方面可以看出， SAGA-DRABS所求策略的可靠性较k-means算法有较为明显的优势，分析原因，也是因为DRA-SAGA既在目标函数中考虑了可靠性因素，也强化了全局最优解的搜索能力，保证了部署策略的可靠性。

图7 各策略时延指标对比

图8 各策略负载均衡指标对比

图9 各策略可靠性指标对比

4 结语

本文研究了SDN中多控制器部署问题，通过建立相应模型，研究了不同部署策略对网络时延、负载均衡和可靠性方面的影响，提出了一种时延和可靠性感知的控制器均衡部署策略。仿真结果表明，提出的部署策略在保证负载均衡的前提下，提高了控制网络的可靠性，降低了网络时延，进而提高了网络的整体性能，从而为面向QoS的网络应用提供了可靠的保障。