分布式SDN控制平面下可靠的控制流传输路径选择

孙敏铭，张 栋

(福州大学数学与计算机科学学院，福建 福州 350108)

0 引言

软件定义网络(software-defined networking，SDN)作为一种新型网络架构，将控制平面与数据平面相分离，成为网络发展的重要趋势之一[1].SDN控制平面负责做出适当决策以满足多变的网络需求；SDN数据平面根据控制平面下发的流表转发数据包.集中控制的特性使SDN比传统网络更加灵活高效地管理网络,但由于单控制器的SDN网络存在诸多负载限制，若干研究提出以分布式多控制器的SDN控制平面架构来提升网络鲁棒性.

分布式SDN控制平面[2-3]及控制器放置问题(controller placement problem，CPP)[4]已经有系列研究，但较少考虑分布式控制平面下控制器与交换机间的控制流传输路径选择.现有研究通常默认交换机到控制器的最短路径作为控制流的传输路径，而忽略传输路径的可靠性对SDN性能的影响[5].特别是在In-Band控制平面下，控制流传输路径的可靠性非常重要，网络故障将导致大量交换机的控制流无法被正常转发，进而影响SDN网络正常运行.

现有的控制流路径研究主要分为两类： 一是基于交换机本地的切换机制，二是在基于全局拓扑的控制流路径选择.第一类研究专注于在单个SDN交换机上实现各类机制来选择控制流路径,这类机制仅考虑本地环境，可能导致控制流环路甚至网络级联故障.第二类研究则是根据物理拓扑，为网络中每个交换机选择控制流的传输路径.文献[6]提出构造以控制器为根的生成树用于转发控制流，树中的其他节点是网络中的交换机节点，树的枝干用于传输交换机节点的控制流.在此基础上，文献[7]提出在分布式SDN控制平面中为每个控制器构造生成树.然而，该方法是基于静态的控制域划分，每个生成树在相应的控制域内单独计算，使算法无法找到最优的生成树.本研究针对上述问题，详尽地分析了分布式SDN控制平面下的控制流传输保护机制，并提出一种动态构造多生成树的算法.在该算法中，根据控制流传输的可靠性要求为每个控制器构造生成树并划分控制域，以避免静态控制域导致的控制流传输可靠性下降.

本研究将分布式SDN控制平面构造可靠的生成树问题定义为控制森林构造问题(control forest construction problem,CFCP),即对给定的网络及控制器放置，为每个交换机选择控制流的路径以提升传输的可靠性及容错性.同时，针对CFCP提出了控制流路径选择算法(control traffic paths selection,CTPS)，该算法基于广度优先搜索，从控制器节点出发，为每个交换机节点搜索适当的父节点，并在搜索结束后进行启发式的调整以获得近似最优解.实验结果表明,CTPS能够有效提高控制流传输的可靠性.

1 控制流路径相关问题概述

近年来，随着SDN的流行，SDN控制流路径的选择受到广泛关注.文献[8]设计了带宽感知的控制流本地重路由机制，在原转发端口带宽剩余不足的情况下选择剩余带宽最多的本地端口转发控制流.文献[9]提出在In-Band控制平面中使用MPTCP，同时选择多条不相交的路径来转发控制流，提升控制流传输的容错性.文献[10]设计了一种动态的控制平面，能够在控制器或某个控制流路径负载过大时，为控制流重新分配传输路径.然而，该机制需要较大的通信与计算开销，从而影响网络的响应时间.文献[6]提出基于快速故障恢复的生成树，当某个交换机故障时，其子交换机节点可利用预配置的非树链路来进行快速重路由，确保其父节点故障时能快速恢复下游交换机节点的控制流，提高控制流传输的可靠性.文献[11]建立了生成树构造问题的整数线性规划模型(integer linear programming,ILP).在此基础上，文献[12]提出了启发式的DDOT算法，该算法通过启发式修改树中交换机节点的位置来寻找最优的生成树.但是，该算法仍然只针对单个控制器.与单生成树构造不同，文献[7]提出多生成树构造算法GSA，该算法基于每个控制域中的最小生成树.然而，GSA算法仅将分布式控制平面划分为若干个控制域，在每个控制域中构造生成树，没有考虑域间邻居节点及链路对可靠性的影响.

2 控制森林问题模型

可靠的控制流传输路径选择问题目标在于尽可能为每个交换机节点选择一条可靠的路径来传输控制流，以保证在底层网络故障时，交换机能够重路由控制流来保持与控制平面的连接.

2.1 单生成树

图1 单控制器的生成树Fig.1 A spanning tree rooted at single controller

(1)

(2)

其中: 变量yij=1表示节点i被节点j简单保护或兄弟保护,否则yij=0; 变量sij=1表示节点i与节点j是兄弟节点,否则sij=0.

由于生成树的存在，当节点A被保护时，其子孙节点的控制流不会因节点A的父节点故障而受影响.当发生故障时，节点A能快速重路由自身及子孙节点的控制流到其他节点，比如图1中的S8能够将控制流重路由到S7，从而保护控制流传输不会中断.另一方面，当节点A不是被保护节点时，无论其子孙节点是否被保护，都将因节点A的父节点的故障而失去与控制器的连接.因此，将一个节点i的权重wi定义为以节点i为根的子树中的节点数量，表示为：

(3)

2.2 控制森林

分布式SDN控制平面需要多个生成树来转发各个控制域的控制流，将这样的多个生成树的集合称为控制森林F=(Vf,Ef).其中,Vf表示SDN网络中数据平面的交换机节点的集合，Ef表示控制森林中边的集合.另外，用集合R表示控制器放置节点的集合，即R⊆V.使用mir=1表示交换机节点i由放置在节点r控制器管理，即交换机节点i是以r为根的生成树中的一个节点；否则，mir=0.

如图2所示，控制器C1和C2是控制森林中的两个控制器.在图2(a)中S7连接到控制器C1,若S7的父节点S8故障，S7因缺少非树链路重路由控制流导致其将与C1失去连接，即S7是一个不被保护的节点.而在图2(b)中，S7连接到C2，因此能够被S3保护.

图2 控制森林Fig.2 Control forest

(4)

(5)

(6)

在保护机制的基础上，通过定义控制森林的权重来衡量分布式SDN控制平面下的控制流传输可靠性.对于给定的控制森林F的权重w(F)定义为：

(7)

其中:pi可以根据下式计算：

(8)

因此，根据上述的定义，控制森林构造问题的目标函数为：

minw(F)

(9)

约束条件为：

(10)

(11)

(12)

(13)

约束(10)表示每个交换机节点只能被一台控制器管理；约束(11)表示控制森林中一共有N-C；约束(12)表示除根节点外,其余所有节点均有一个父节点；约束(13)表示控制器的负载不能超过其上限.

3 控制森林构造算法

本研究提出的CTPS算法分为3个阶段： 初始森林构造、负载调整以及可靠性调整.初始森林构造阶段根据网络底层拓扑构造初始的生成树；负载调整阶段将调整树结构以确保每个控制器的负载不会超过上限；最后可靠性调整阶段启发式修改森林中节点的父节点，寻找更优的控制森林.与现有的生成森林构建算法GSA[7]不同，CTPS在构造初始森林及可靠性调整时不止考虑域内节点，而是考虑所有的邻居节点.同时，由于CTPS不是基于静态的控制域划分，因此，加入负载调整阶段以确保初始森林的控制器不会过载.

3.1 初始森林构建

CTPS算法的初始森林构建阶段基于广度搜索,该阶段如算法1所示，从根节点开始，每轮搜索均会将队列中节点的邻居加入相应的队列并设为其子节点.同时，为避免出现某个节点没有非树链路可用的情况，在连接节点到森林时考虑了父节点的连接情况： 若节点A只剩下一条非树链路，则不会将A设置为任何节点的父节点.广度搜索结束后再将未加入森林的节点根据其邻居节点情况加入控制森林.

算法1 初始森林构造输入: 网络拓扑图G=(V, E); 控制器放置位置Θ;输出: 初始森林F; 1) 为每个根节点r创建一个队列, 将r压入队列; 2) 依次将每个队列中的节点压出, 检查每个压出的节点i的所有邻居节点j:

算法1 初始森林构造 如果j还未加入森林, 且i存在两条以上的非树链路, 则将i置为j的父节点, 将j压入i的原队列, 否则, 不操作; 3) 重复2), 直到所有队列为空; 4) 随机选择一个未加入森林的节点i, 选择i的邻居中树高最小的节点j作为i父节点, 5) 对于剩余未加入森林的节点: 如果节点i有一个被保护的邻居节点j, 则将j置为i父节点; 否则, 不操作; 6) 重复4)～5), 直到所有节点均加入森林; 7) 返回初始森林F

3.2 负载调整

考虑到控制器的负载问题，算法需要调整森林的结构防止控制平面过载.首先检查森林中是否有生成树的节点过多，超过控制器的负载限制；若存在，按树中节点到根的距离降序排列节点，并尝试将该树中的节点加入其他生成树，直到所有控制器管理的交换机均没超过Lr.按降序排序节点是为尽可能调整少量节点来避免其他控制器超负载.该阶段如算法2所示:

算法2 负载调整 Ⅰ) 将temp_F中所有节点按照节点到控制器的距离降序排序; Ⅱ) 如果控制器r管理的节点超出了Lr, 则按序处理r管理的节点, ∀i∈{mir=1}: 如果节点i有一个邻居节点j由控制器r1管理且Lrr1i=1, 那么将j置为i的父节点, 否则, 处理序列中下一个节点; Ⅲ) 重复Ⅱ), 直到所有控制器的负载都没有超过Lr;Ⅴ) 返回temp_F

3.3 可靠性调整

在可靠性调整阶段，CTPS算法根据当前的权重修改森林中节点的父节点.首先,按照节点到控制器的距离升序排序节点；之后，对每一个节点进行启发式调整；最后，选择其中最优的控制森林.该阶段如算法3所示，在算法3中Γ(F1)>Γ(F)表示森林F1权重小于F权重，或两个权重相等且森林F1的平均高度小于F；Fcurrent表示修改后的控制森林.

算法3 可靠性调整① 将temp_F中所有节点按照节点到控制器的距离升序排序; ② 对序列中的所有节点, ∀i∈VF: 如果存在一个i的非父非子孙邻居节点j, 使得当i成为j子节点后, 满足Γ(Fcurrent)>Γ(F), 则置j为i的父节点; ③ 重复②直到w(temp_F)不再减少; ④ 返回当前控制森林F

4 实验与结果

4.1 实验参数设置

本研究采用2个真实的物理拓扑[13]进行实验： AboveNet和PionierL3.其中,AboveNet有23个节点，31条边；PionierL3有38个节点，53条边.将提出的CTPS算法与文献[7]的GSA比较,实验中的控制器位置则是根据最小平均时延及最小最大时延放置[14]，即CTPS与GSA分别以两种控制器放置位置为输入构造控制森林.

4.2 实验结果

图3～4是两种算法在两种放置方法下，控制器从3个增加到6个时的森林权重的统计结果，其中，控制器负载上限Lr设置为网络中的节点数.从实验结果可知，随着控制器数量的增加，w(F)下降.对于节点数量较少的AboveNet，当控制器的数量为5个时，CTPS算法构造的控制森林中只有一个叶节点未被保护，w(F)=1；而GSA算法构造的森林在两种放置的场景下w(F)分别是3和5，并且GSA算法需要6个控制器才能将权重下降到1.这是因为CTPS算法根据w(F)为每个节点选择控制器，而不是根据就近原则来选择；CTPS算法会将一些无法被保护的节点的子孙节点移到其他控制树，可以大量减少其数量，即减少节点的权重，从而降低w(F)，提高可靠性.

图3 AboveNet中可靠性对比 Fig.3 Reliability comparison in AboveNet

图4 PionierL3中可靠性对比Fig.4 Reliability comparison in PionierL3

图5～6是两种算法在两种放置方法下，控制器从3个增加到6个时的控制流传输路径平均长度的统计结果，其中，控制器负载上限Lr设置为网络中的节点数.在控制器数量为3个时，CTPS生成的控制森林的平均长度比GSA的平均长度分别高出了6.25%及13.41%左右，这是由于CTPS算法可以将子孙节点连接到更远的控制器来提升可靠性.并且，平均长度的差距会随着控制器数量的增加而减少.

图5 AbvoeNet中平均路径长度对比Fig.5 Average path length comparison in AboveNet

图6 PionierL3中平均路径长度对比Fig.6 Average path length comparison in PionierL3

图7 AbvoeNet中可靠性随负载变化的对比Fig.7 Reliability comparison with load in AboveNet

图7是AboveNet中两种算法在两种放置方法下，Lr分别为14，16，18，20，22个交换机时控制森林w(F)的统计结果.显然，随着Lr的增加，两种算法生成的森林的w(F)均有一定程度的下降.然而，实验结果表明，CTPS算法对控制器的负载更加敏感,当Lr上升到22个时，w(F)下降到了原先的31%，而GSA只下降了50%左右.甚至，在基于最小平均时延的控制器放置方案下，GSA的效果只提升14.29%.这种差距是由于GSA算法基于静态的控制域分配，无法调整节点所在的生成树，使得一些权重较大的节点因为找不到满足负载约束的保护控制器而无法被保护造成的.

5 结语

本研究分析了分布式SDN控制平面下控制流传输路径可靠性问题.首先分析了分布式环境下控制流传输的保护机制并提出了CTPS算法，该算法基于可靠性为每个节点选择控制屏并规划控制流的传输路径.实验表明，在控制器放置相同时，CTPS算法构造的控制森林能够提供更可靠的控制流传输.同时，CTPS算法能够更有效地利用控制器的负载来保护不同控制域中的交换机的控制流，以应对分布式控制平面中的控制器故障.