基于网络拓扑划分的大规模SDN控制器部署

张元龙，廖晓群，张佳庚

(1.西安科技大学 信息网络中心，陕西 西安 710054；2.西安交通大学 网络信息中心，陕西 西安 710049)

0 引 言

软件定义网络(software defined network，SDN)体系架构通过网络可编程和开放接口技术解耦合了网络控制与转发平面，使得新型网络具备逻辑集中可编程控制能力[1]。然而，网络部署规模的扩大带来了网络业务需求和转发流量的快速增加，单一集中控制器无法对大规模流量请求进行实时处理以服务网络业务需求。因此，分布式多控制器部署成为未来SDN大规模部署应用的关键方向[2,3]。

近年来，关于控制器部署问题的研究主要从全局网络视角出发建立以通信时延、弹性、可靠性、能耗和负载均衡等为单/多目标的优化方案[1-3]。文献[4]基于Pareto最优控制器部署框架，考虑了控制器与交换机之间和控制器彼此之间的时延和通信代价以及负载均衡等多种性能指标来实现最优控制。然而，此类方法应用在大规模复杂网络中时存在全局部署过于复杂且会陷入局部次优解等问题。采用分而治之思想，学者提出基于网络划分技术的分布式多控制器部署方案，以达到简化部署复杂度和保证部署性能的目的。文献[5]提出一种I-K-means部署方案，以减小网络质心节点及其关联节点之间的最大传播时延为目标来实现网络分区和子域部署求解。文献[6]则在K均值聚类基础上提出启发式控制器部署策略，通过划分子域中控制节点和交换机节点之间传播时延最小化为目标来实现多控制器部署。文献[7]提出一种基于密度聚类划分的控制器部署方法，通过参考子域交换机密度实现网络划分和局部部署。文献[8,9]提出利用谱聚类(spectral clustering，SC)结合真实网络拓扑结构特性来实现全局网络的有效划分，并基于划分子域来实现控制器部署。文献[10]在谱聚类基础上结合矩阵摄动理论和特征间隙法，自主发现网络稳定结构并确定最优网络划分，从而实现更合理的控制器部署。然而，这类标准聚类方法需要预先指定分类簇数或阈值，受限于初始化和人为因素影响，无法在大规模复杂网络中提供稳定且合理的网络划分，网络可靠性得不到保障。

考虑到网络结构本身可作为控制器部署线索，本文提出了一种改进Louvain社区检测[11]算法的控制器部署策略Modified-Louvain，包括两个阶段：第一是网络社区的均衡划分，为了使社区的紧密性最大化，基于节点距离相似度重定义链路权重，然后在Louvain社区检测算法中引入社区容量约束因子，提出一种平衡负载的社区检测算法，可独立根据网络拓扑结构来实现全局网络的准确合理划分。第二是启发式部署控制器，针对每个划分子网以控制器与交换机之间传播时延最小化为目标来确定控制器的部署位置。总之，所提Modified-Louvain控制器部署方案通过识别大规模网络中具有社区属性的网络结构，可独立确定合理的分区。同时该算法引入尺度约束因子，平衡子网的大小规模，保证将整个网络划分为多个规模适中的子域，提供可靠控制器部署策略。

1 相关工作

多控制器部署方案[12-14]逐渐应用并实践于大型SDN网络。解决SDN面向大规模网络部署的趋势是通过分布式理念将多个控制器部署到不同的控制域内，形成一个物理上分布的控制平面，通过控制器间的通信协作最终形成逻辑上集中的控制平面来统一管理全网设备。考虑到多控制器管控的网络场景，自然诞生出如何决策控制器数量和位置的问题，即控制器部署问题(controller placement problem，CPP)。具体来说，CPP需要解决以下两个问题[15]：

(1)需要多少控制器？

(2)控制器应该部署在哪些位置？

图1所示一个大型SDN网络的控制器部署，可看出控制器所管辖的网络子域范围可能包括企业、学校、政府和数据中心等多种异构节点，为满足某种特定的网络性能指标需要合理决策控制器数量和部署位置。目前研究方向包括两方面：性能优化和部署模型。从性能优化视角来看，主要依据的网络性能指标包括传播时延[15]、控制器容量[9]、节点故障[16]、部署代价[17]和能耗效率[18]等，其中控制器与交换机的传播时延直接影响流表规则的转发效率，因此被视作主要优化性能指标。而当多个性能指标同时考虑时，CPP通常定义为组合优化问题，这对于大型SDN网络来说求解复杂度通常较高。从部署模型来看，聚类算法广泛用于求解CPP，通过划分类簇和确定类簇中心来完成控制器数量和位置的确定[5-10]。然而现有应用广泛的聚类方法过于依赖初始化和人为随机因素，因此无法提供合理且稳定的控制器部署方案。本文考虑到大规模SDN网络对于控制器部署的高效稳定要求，提出基于网络社区划分机制的控制器部署策略，将高复杂的全局部署问题分解为多个低复杂的局部部署问题，进而采用启发式机制来优化网络性能指标。最后，该方法的网络分区及部署性能在实际网络拓扑上得到了验证。

图1 大型SDN网络

2 控制器部署建模

对于一个SDN网络，主要网络元素构成包括控制器、交换机和链路。考虑到SDN网络中交换机节点之间可上下行传播流量，将SDN网络建模为无向图G=(V,E)， 其中V代表交换机节点，E代表连接两个节点的物理链路。假定在SDN网络中部署的控制器数量为K，定义集合={ci|i=1,2,…,K} 为控制器集。φ(c)(c∈) 表示将单个控制器与一组交换机连接起来的映射函数。那么整个网络G将被K个控制器所管理并满足

φ(ci)≠∅, ∀ci∈

(1)

φ(ci)∩φ(cj)=∅, ∀i≠j,ci,cj∈

(2)

(3)

上述公式表示每个子网络必须包含至少一个节点，而且每个节点仅分配给一个子网络且所有子网络必须覆盖整个网络。

在大规模SDN网络中，通信的及时性是影响网络性能的一个重要因素。在本文工作中，网络被划分为多个子网，控制器和交换机之间的传播时延将直接影响数据平面的数据包转发效率，因此被用作关键性能指标。其中，平均时延和最大时延模型定义为

(4)

(5)

式(4)表示交换机和控制器间的平均时延；式(5)表示交换机和控制器间的最大时延。其中d(s,c) 表示两点间的Dijkstra最短路径距离，对应于交换机s到关联控制器c的传播时延，c∈φ(c) 表示控制器c将被部署至某一个交换机所在的位置。|φ(c)| 表示被控制器c所管理的交换机数目。

3 控制器部署策略

3.1 Modified-Louvain算法

假定SDN网络拓扑G=(V,E)， 类似于式(1)～式(5)的目标，CPP的目的在于确定控制器数量和部署位置，以及确定控制器与交换机间的连接关系，从而确保某种网络性能指标的优化。与此同时，还必须保证任何时候控制流量负载不能超过关联控制器的负载容量上限[16]，定义为

(6)

式中：Load(c) 表示控制器c的最大负载容量，load(n) 表示控制交换机n所需的控制流量负载。因此，求解CPP的主要目标就是在式(6)的约束下来最小化每个控制域内控制器与交换机之间的传播时延

(7)

(8)

s.t.constraints(6)

(9)

为了叙述的完整性，首先介绍标准Louvain算法。给定图G(V,E)具有节点集V和边集E，社区检测将网络划分成不相交区域C={c1,c2,…,ck}， 使得V=c1∪c2…∪ck并且ci∩cj=∅,i≠j。 每条边e(u,v)∈E具有属性权重w(u,v)。 模块度Q用于量化划分质量[11]

(10)

(11)

(12)

其中，节点间权重越大表示两个节点的关联越紧密，越有可能分布在同一社区。在网络中，节点之间权重越大意味着邻接关系更为紧密。以最大化网络社区紧密性为目标，重新定义节点间边权重函数

(13)

式中：d(u,v) 表示节点对 (u,v) 间的最短路径长度，而dmax表示所有节点对间最长的最短路径长度。

模块度已被广泛应用于评价社区检测的质量[19]。然而，模块度的优化本质上是一个NP-完全问题。一般用于优化模块度最大化的策略包括4种：贪婪、模拟退火、极值和谱优化。贪婪优化采用不同的方法将顶点合并到社区中以获得更高的模块性，这通常会生成高质量的社区；模拟退火采用概率方法对模块性进行全局优化；极值优化是一个启发式搜索过程；谱优化利用特殊矩阵的特征值和特征向量进行模块化优化。本文关注于贪婪搜索策略，即如何通过探索模块度增益来评价网络划分质量的好坏，根据式(10)所定义的模块度，模块增益度定义为

(14)

算法1：Modified-Louvain算法

输入：G(V,E,W)： 加权网络；θ：控制器负载最大容量；φu：交换机u所需控制负载

输出：C：平衡子网络集合；Qbest：最优模块度

whileTruedo

C←{{u}}, ∀u∈V;

load(c)←∑u∈cφu,Ltotal←{∑c∈Cload(c)}

whileCchanges do // 阶段1

foru∈Vandu∈cdo

load(c)=loadtemp(c);

end for

ifQ-Qbest≤0 then break;

end if

Qbest←Q;

C′←{c},∀c∈C;

// 阶段2：重构图

V′←C′;

E′←{e(c,c′)}, ∃e(u,v)∈E,u∈c,v∈c′;

wc,c′←∑wu,v, ∀e(u,v)∈E,u∈c,v∈c′;

V←V′;E←E′.

end while

3.2 控制器位置选择问题

图2 网络中控制器位置选择

算法2：基于最小化平均时延的控制器位置选择策略

输入：拓扑划分集C；

forc∈Cdo

Γ1←{};

foru∈cdo

lu←0; //定义从节点u到其它节点的时延总和

forv∈cdo

lu←lu+l(u,v);

end for

Γ←Γ∪{lu/|c|}

end for

end for

算法3：基于最小化最大时延的控制器位置选择策略

输入：拓扑划分集C；

forc∈Cdo

Γ←{};

foru∈cdo

Γ2←{}

forv∈cdo

Γ2←Γ2∪{l(u,v)};

end for

end for

end for

3.3 复杂度分析

基于网络划分的控制器部署算法主要包括两个步骤，分别是针对网络拓扑的社区检测(子网络划分)和每个子网络中的控制器位置选择过程。相比较于全局部署策略，基于网络划分机制的方案将全局部署分隔成单独的两个子过程，而且只需要考虑将控制器方案限定于小规模子网络中，从而在一定程度上降低了问题的复杂性。对于一个具有N个节点的网络拓扑，基于Louvain社区检测算法的执行时间复杂度是O(NlogN)。 理想情况下可以得到m个平衡社区，也就是说每个社区包含相同数量的节点，表示为n=N/m。 而位置选择过程的执行复杂度为O(m·n2)， 因此总体基于Louvain划分的控制器部署时间复杂度为O((mn)log(mn))+O(m·n2)。 采用枚举的载荷约束控制其部署算法执行复杂度是Ο(mNNm)。 总体而言，所提Modified Louvain可高效率地提供一个稳定且准确的控制器部署方案。

4 仿真实验

在本节实验中，为了评估Modified Louvain在SDN控制器部署问题中的性能，从SNDlib[20]中选择3种不同尺度的大型骨干网拓扑，通过实验来验证算法在不同网络规模中的部署性能。所有拓扑的属性见表1，其中链路长度采用半正矢公式求解球面距离。为了评估基于Modified Louvain的CPP(简写为ML-CPP)部署方案的有效性，选取同样属于网络划分机制的基于谱聚类的控制器部署算法(简写为SC-CPP)[8-10]作为对比策略，这两种算法均将CPP问题转换为等价的网络划分问题，通过求解网络划分过程将全网拓扑划分为多个子域，然后在每个子域中确定以优化某个网络性能指标的控制器放置策略。在本节实验中假定每个子域仅部署一个控制器，即最终网络划分所得的子域个数就是所需部署的控制器数量。

表1 网络拓扑属性

首先，对比分析ML-CPP和SC-CPP两种网络划分策略的负载均衡性能，即控制器所管辖的交换机数量的平衡指数。本实验假设所有控制器具有统一的容量负载能力，而且每个交换机所需要的控制流量负载也都相同。因此，令φu=1， 同时对3个网络拓扑设定控制器容量分别为θ={8,10,11}， 即每个子网络中所能容纳的交换机数量不能超过控制器负载容量。另外定义量化的负载均衡性能指标

(15)

式中：K表示划分分区个数，N表示网络中总的节点数，Ni表示第i个分区中节点数，λ越小，其负载均衡性能越好。

图3所示ML-CPP和SC-CPP两种方案分别执行100次实验后的平均λ对比情况，其中对于Nobel-EU、Janos-US-CA和Germany50这3种网络拓扑，ML-CPP所获得的网络分区数分别是 {6,6,7}。 从图中所知，基于Modified-Louvain的网络划分机制可以保证网络化分结果的稳定性，同时生成具有更低负载均衡指数的划分结果，在3种网络拓扑上均表现出比谱聚类(SC)更稳定且更好的性能。由于谱聚类受限于随机因素的影响，为降低实验结果的随机性，每次独立实验重复进行了100次。接下来，针对这些结果将统计不同控制器部署方案下的平均传播时延和最大传播时延的累计分布曲线(cumulative distribution function，CDF)。

图3 基于不同控制器部署策略的网络负载均衡性能指标

图4展示了在Nobel-EU网络拓扑上基于ML-CPP和SC-CPP两种网络划分策略的控制器部署性能。从图中可以看出ML-CPP可以提供稳定且最优的平均时延和最大时延，而SC-CPP由于受限于人为参数和随机初始化因素的影响，所产生的控制器部署性能差异较大，平均时延和最大时延抖动范围分别是[2.52 ms,2.73 ms]和[5.94 ms,6.98 ms]，这些变化范围均大于对应基于ML-CPP的平均时延和最大时延。

图4 Nobel-EU网络上控制器部署方案的时延性能对比

图5展示了在Janos-US-CA网络拓扑上基于ML-CPP和SC-CPP两种网络划分策略的控制器部署性能。从图5(a)可看出基于ML-CPP的平均时延(2.81 ms)持续小于基于SC-CPP所得到的平均时延范围[3.34 ms,4.18 ms]。另外，对比最大时延性能，从图5(b)中可以发现ML-CPP仍然确保了稳定的最大时延(8.76 ms)，而基于SC-CPP的最大时延变化范围为[6.84 ms,21.12 ms]，虽然存在56%的基于SC-CPP的最大时延小于ML-CPP，但是仍有44%的基于SC-CPP的部署方案产生的最大时延远高于8.76 ms。

图5 Janos-US-CA网络上控制器部署方案的时延性能对比

图6展示了在Germany50网络拓扑上基于ML-CPP和基于SC-CPP两种网络划分策略的控制器部署性能。从图6(a)和图6(b)可以看出基于ML-CPP的控制器部署方案所产生的平均时延和最大时延均小于基于SC-CPP的控制器部署性能结果，而且ML-CPP可确保稳定的控制器部署性能，从而提供更加可靠的控制器部署方案。

图6 Germany50网络上控制器部署方案的时延性能对比

5 结束语

为了在大规模SDN网络环境下设计高效稳定的控制器部署方案，并降低全局SDN网络控制器部署的复杂性，本文基于社区检测的网络划分机制来简化大规模SDN网络的控制器部署复杂度，结合控制器负载容量约束条件，提出一种改进的均衡负载网络社区划分方法(Modified-Louvain)用于准确识别控制器所管辖的子网络，并以最小化平均时延和最大时延为目标启发式求解控制器的最优部署位置。所提控制器部署方案在复杂网络分析理论的支持下，考虑了网络社区结构属性可以作为控制器配置的线索，通过启发式求解可提供快速准确的控制器部署方案，进而可为SDN控制平面管理提供性能保障。仿真结果表明，所提方法可有效处理大规模SDN网络下的控制器部署问题，在均衡控制器负载的同时保证控制器与交换机之间传播时延的最小化目标，能够提供可靠部署策略。