· 3389·
第11期
陆悠，等：基于拓扑划分的SDN多控制器部署方法
路)连接。这种存在高连通度局部拓扑的特性天然为实现多
控制器部署提供了支撑，若在上述物理区隔的各个高连通分量
中部署互为备份的控制器，能够有效降低多个控制器同时失效
的可能性，并为失效时实现控制器切换提供支撑，因此发现这
样的高连通分量并在其基础上实施多控制器部署是合理的思
路。此外，由于传统基于带内的控制一转发层面间链接方式会
使得区域内控制器到达其他区域转发设备存在跳数多、延迟大
等不平衡问题，不利于切换后控制策略的部署及收敛，所以引
入带外链接概念，尽可能提供控制器到其他区域的直接链路，
从而为失效后的控制器快速切换提供支撑。为了更好地讨论
上述内容，本文给出如下问题描述以及相关概念。
多控制器协作思想，提出了一个基于min—cut的图形分割算法
来部署控制器；Hu等人。13。同样基于多控制器协思想，对控制
层面的可靠性问题比较了几种不同的部署控制器的启发式方
法；Heller等人¨ 4o引入了平均情况延迟和最坏情况延迟这两
个指标，基于K—median和K—center思想计算协作控制时的控
制器数量及部署的位置；而Jimenez等人【1纠则针对协作控制的
鲁棒性，提出基于K—critical算法的控制器数量及部署规划方
法。然而这些方法主要针对转发节点出现失效，一旦有部分控
制器或者控制和转发层面间链路出现故障，上述方案并不能保
证控制层面能及时有效地恢复工作。因此，从确保SDN控制
层面的可靠性角度来看，现有的多控制器部署方法的研究成果
存在以下不足：
给定自治域，多控制器部署模型的解决思路为：一方面对
自治域进行拓扑分析，从中分析连通分量，并基于其结果确定
控制器数量及部署范围；另一方面根据分析结果设计控制器到
每个连通分量的带外控制链路，优化控制器到转发设备的传输
距离，从而实现具备高可靠性的控制层面。为了便于讨论，本
文给出如下概念：
a)更多考虑多控制器协同，较少考虑控制器备份。部分
工作使用多个控制器目的是为了适应更大规模的网络，而非控
制层面的失效和备份，难以保证SDN的可靠性。
b)更多考虑转发层面的节点失效问题，较少考虑控制器
自身失效以及控制层面和转发层面链路失效问题。部分工作
更多针对转发设备及其通信链路失效，通过在网络中部署多个
控制器来实现故障发现、处理等能力，但这些方法难以处理控
制器自身以及控制节点与转发节点间链路失效问题，同样不利
于SDN控制层面的可靠性。
定义l图、节点、边。
设给定自治域网络拓扑如图1所示，则可将网络拓扑抽象
为图G(V，E)，V为图中的节点(node)集合，对应传输层设备
(如OpenFlow交换机)；E为边(edge)集合，对应链路，显然有
e(“，口) E，口 V，“ V，u≠口。另外设整数m和／"t(I VI=／l，
lEI=m)分别表示图G中节点的数目和边的数目，为不失一般
性，网络中若一对传输设备中存在多条实际通信链路的情况，
则这些链路会被视为G中的同一条边。
e)较少从控制层面与转发层面的链接方面考虑如何提高
控制层面可靠性。现有的大部分多控制器部署方案并未单独
设计控制层面与转发设备的链接方式，而是采用带内(in—
band)模式链接控制和转发层面，逻辑上独立的控制与转发层
面的数据传输交织在一起，使得传输层面链路故障会对控制层
面造成影响，进一步削弱了SDN的可靠性。
蚋
基于以上分析，本文对当前SDN控制层面的可靠性问题
展开针对性研究，在已有研究基础上，提出了一个基于拓扑划
分的SDN多控制器部署方法，一方面从控制器部署和控制一
数据层面链路两方面人手，对现有方法进行改进，首先针对网
络拓扑本身存在高连通度的局部拓扑这一特性，提出基于最小
户乎衡边割的拓扑划分算法，通过计算高连通分量，进而基于
高连通分量来规划控制器数量及其部署位置；另一方面针对不
同位置部署控制器导致其与各转发设备的距离存在不平衡性，
引入带外(out—band)链接思路，设计控制器与传输节点的链接
规划方法，在每个控制器与不同连通分量间构建链接，从而进
一步提高控制层面的可靠性以及控制节点失效时的切换效率，
为失效后控制器切换提供支撑。基于实际网络拓扑的仿真实
验结果表明，与现有多控制器部署方法相比，本文方法在控制
器切换时的收敛速度、控制策略执行效率以及网络可靠性等多
个评价指标上表现更好，能够在控制层面或其链路失效时快速
有效地实现控制器切换。
粼
图1
f]ia域I司络拓扑■；例
定义2连通、连通值、直连通、直连通值。
衡量SDN能否正常工作，可以通过转发设备间的链接情
况来判断。如果网络中任意两个转发设备间存在一条可达路
径，称这两个节点间是连通的，其连通值为l；反之，则为不连
通的，连通值为0。在图G中用P(“，口)表示节点u、口间的连通
值，于是有
1
if eixst
G
f
e(u，”1)，e(“，”2)， ，in
otherwise
p(Ⅱ，口)={
【0
在p(Ⅱ，”)基础上可以得到图G的连通值P(G)= 。。，。，
P(Ⅱ，”)。如果网络任意两个转发节点间存在通信连路，称这两
个转发节点是直连通的，直连通值为1；反之为0。因此在图G
1
多控制器部署模型
中，可以用P(／／,，。)来表示节点“、”间的直连通值，在其基础上
1．1
E
问题描述及相关概念
I-m，若
可以得到图G的直连通值P(G)，显然P(G)=l
r凡、
应用SDN架构的网络如大型企业、学校等单位，其转发设
备的部署往往与实际部门或人员分布密切相关，而这些部门和
人员分布往往具备局部的内聚性，反映在网络拓扑上即整个网
络中可以分为若干物理区隔的区域，区域内转发设备内部连通
度较高，而区域间往往使用较少的链路(甚至是单条骨干链
P(G)=1．1，其中IyI=，z，则此图为完全连通图。
z
l
J
显然，如果图G是正常工作的网络，G中任意两个节点之
间都应该存在路径，此时称图G是连通图。本文处理的对象
都是正常工作的网络，因此下文中如果不加特别说明，所有的
万方数据
全部评论(0)