1 引言 1.1 研究背景及介绍

SDN (Software-Defined Networking)是一种将网络控制平面和数据平面分离、具备可编程性的新型网络架构^[1]. 基于OpenFlow协议的SDN架构将底层基础设施抽象出来, 使用户能够通过编程来集中控制网络转发行为. 当网络状态发生变化时, SDN控制器可通过下发新的转发规则更新交换机流表项, 从而管理整个网络状态. 尽管SDN实现了网络的集中控制, 但数据平面设备的分布式特性也带来了许多问题, 如交换机自身安装流表项的速度、交换机间的传输延迟等. 这使得流表项生效时间难以一致, 进而导致更新不一致, 增加了集中管理的难度^[2].

目前, 我们正在参与一项国家重点研发计划子课题的项目研究. 该项目的一个主要研究目标是在政务通信网络中提出一种能保证数据转发高可靠性、提供细粒度QoS保障的机制. 而数据转发的可靠性和细粒度QoS直接依赖于SDN转发策略的更新一致性. 因此, 保证SDN流表更新一致, 对保证项目中的数据转发高可靠性和细粒度QoS具有重大意义. 本文在此基础上, 研究能保证SDN流表更新一致、数据可靠转发、更新性能好的更新方案.

1.2 SDN流表一致性更新

在SDN网络中, 当交换机收到一个数据报后, 它首先查找转发流表. 若有匹配的流表项, 则执行相应的动作. 否则交换机会向控制器发送packetin消息, 将报文上报至控制器进行处理. 控制器处理后, 会向交换机下发新的转发流表项指导后续转发. 此外, 当网络状态发生变化时, 控制器会主动或被动向交换发送新的转发流表项, 以形成新的转发路径^[3].

由于数据平面的交换机呈分布式排列, 控制器向每台交换机下发新流表的时延会有不同, 交换机内部的更新速度也有差异, 这会导致新规则的所有流表项无法同时生效, 使数据包出现错误的转发处理, 引发数据转发中断、环路等问题, 影响网络流量传输的可靠性和细粒度QoS的保证.

因此, 在新旧规则的更新过程中, 必须要保持流表的一致性更新. 即控制器在更新交换机中的流表项时, 那些正在传输的数据包在每个交换机上要么匹配旧规则流表项, 要么匹配新规则流表项, 不能出现在交换机A上匹配旧规则, 而在交换机B上又匹配新规则的情况. 为了更好地说明SDN流表更新不一致性引起的问题, 下面以图1进行举例说明. 其中节点N_i (1≤i≤8)代表交换机, 实线代表旧转发路径, 虚线代表新转发路径.

假设某时刻SDN控制器同时向各个交换机下发更新命令: 将转发规则更新至新路径. 由于控制器和不同交换机的传输时延差异, 交换机无法同时完成更新. 当N₁完成更新而N₈尚未更新时, 即N₈没有匹配数据流的转发规则, 则转发到N₈的数据流将不知作何处理. 如果默认动作是丢弃报文, 则会引起流中断. 此外, 如果交换机N₆更新了而N₅尚未更新, 就会形成环路N₆→N₅→N₆. 这会长时间占用链路直至报文的TTL超时, 从而降低链路利用率和转发性能.

通常来说, SDN流表更新出现不一致时, 可能会导致网络中断、环路、安全漏洞等问题. 为确保从旧规则过渡到新规则期间, 网络能正确转发报文, 则必须要考虑所有可能出现的中间状态及其属性^[4]. 很明显, 流表的一致性更新, 关系到网络配置能否正确实现.

目前, 针对SDN流表更新一致性问题, 研究者已经提出了多种更新方案, 如两阶段更新^[5]、反向更新^[6]、基于分类时序更新^[7]、时间触发更新^[8]、分段更新^[9]等.

1.3 相关工作

为了确保更新无黑洞和无循环的一致性属性, Reitblatt等首先提出每流/每包一致性的定义^[5], 并基于此定义提出了两阶段更新方案进行策略转发更新.

周晔等^[10]、齐婵等^[7]在两阶段更新的基础上分别提出了基于分类和基于分类时序的流表更新一致性方案, 核心均在于根据更新操作类别对交换机进行分类, 并按照一定的顺序更新规则. 不同的是, 分类时序更新增加了对流表项的细分操作. 分类时序更新虽算法简单, 但其根据严格设定的顺序来更新新旧转发路径上的节点, 忽略了同时是新旧路径上的交换机的情况, 存在应用场景局限性. 此外, 不管更新拓扑复杂与否, 都需要等待一定的端到端最长时延才能进行下一阶段, 方案更新轮次固定, 更新时延过长.

基于节点依赖关系, Diogo等^[6]提出了反向更新方案. 该方案虽算法简单, 但其节点依赖复杂, 也没有考虑节点规则无须更新的情况, 严格依据新规则转发路径从目的节点递归向前更新以避免环路. 因此, 更新轮次多, 致使更新时延长. 另外, Fu等^[11]提出双向更新方案. 通过寻找满足当前更新状态下其子节点都已更新至新规则, 或者在最终状态下其所有父节点都已经更新至新规则这两个条件的节点依次更新. 但每次最多更新2个节点, 更新轮数依然过多. 针对依赖问题, Mahajan等^[12]提出了最优化更新. 方案设定每个节点都具有3个状态, 在保证无环的情况下, 让尽可能多的节点并行更新, 从而最大程度减少更新轮次. 但此方案每一轮都要全局遍历以更新节点状态, 节点搜索复杂度高.

1.4 基于分类搜索的无环更新

针对分类时序更新应用场景适用性差和更新时延长、最优化更新计算复杂度高等问题, 本文在两者基础上, 提出基于分类搜索的无环更新一致性方案(Categorical Search based loop-free Consistent Update scheme, CSCU). 在CSCU方案中, 我们设计了一种交换机分类模型和一种环路搜索优化模型, 其中优化模型包括环路检测模块和搜索模块. 两种模型结合的更新流程可概括为: 分类模型先分析所有节点的更新前后状态并初始化; 再调用环路搜索优化模型的环路检测模块获取对应节点集的可更新节点进行更新. 最后, 在未更新节点集中循环调用优化模型的搜索模块查找满足条件的可更新节点, 直至更新完成.

本文的主要贡献在于:

(1)改进分类时序更新算法中的分类方式, 构建了一种新的交换机分类模型, 它可以增大应用场景的适用性和减少更新等待时延.

(2)在分类和节点依赖的基础上, 通过分析更新前后转发规则的差异, 构建相应的环路搜索优化模型, 优化了更新的搜索计算复杂度和更新效率.

(3)在分类模型和环路搜索优化模型的基础上, 提出一种基于分类搜索的更新方案, 它具有更新时延短, 更新效率高的优点.

2 SDN系统模型

在本节中, 我们通过构建网络模型和更新模型对整个SDN网络的更新过程进行分析.

2.1 网络模型

我们将网络建模抽象为一个图G=(N, L), 其中, N是网络的节点集, L是节点间的链路集. 为了简化, 本节假设网络模型为单一控制器C₀和多OpenFlow交换机S={s₁, …, s_n−1}的模式, 图2展示了本节所述的网络模型. 其中, 实线是交换机间转发数据包的数据链路, 虚线是控制器和OpenFlow交换机间的控制链路(也称OpenFlow通道).

在SDN网络中, 节点集N可用数学表示为: ${{N}} = $ $ {{C}} \cup {{S}}$ , 其中, C是控制器集, S是交换机集. 链路集L可定义为 $L = L_{{{cc}}}\cup L_{{{cs}}} \cup L_{{{ss}}}$ , 其中, L_cc指代控制器与控制器之间的链路集, L_cs指代控制器和交换机间的控制链路集, L_ss指代交换机和交换机间的传输链路. 由于模型简化为单控制器模式, 因此集合L_cc为空, 集合L_cs的元素个数为|S|=n−1.

交换机流表规则R_i可定义为一个三元组<Pr_i, M_i, A_i>. 其中,Pr_i指代规则的优先级,M_i指代规则的匹配域集(OpenFlow协议中, 流规则使用多个字段来匹配数据包, 包括以太网源地址、以太网目的地址、VLAN ID等), A_i指代规则的动作集. 如果进入网络的数据包同时匹配多条规则, 则选择优先级最高的规则, 并执行相应的动作.

2.2 更新模型

网络更新是对网络配置的更新操作: SDN控制器生成更新消息并将其转发给交换机, 然后交换机根据此消息改变它的规则表. 很明显, 更新前后涉及交换机状态的变化. 因此可将t时刻的交换机状态定义为^[2]:

$ST_i(t) = \{ R_i(t),\;L_{{{c}}si}(t),\;L_{{{s}}si}(t)\} $

(1)

其中, R_i(t)指在t时刻的交换机S_i的规则集, L_csi(t)代表t时刻与S_i相关的控制链路集, L_ssi(t)代表t时刻与S_i相关的数据传输链路集.

网络配置, 即网络中所有交换机的状态并集, 则t时刻的网络配置可定义为:

$E(t) = \bigcup\limits_{i = 1}^{|S|} {ST_i(t)} $

(2)

网络更新是对网络配置的更新操作, 即不同时刻的网络配置的迁移. 因此, 网络更新可定义为:

$E_{{\rm{src}}}(t_i)\xrightarrow{U}E_{{\rm{dst}}}(t_j),\;t_i < t_j $

(3)

其中, E_src(t_i)代表更新前的网络配置, E_dst(t_j)代表更新后的网络配置, U指代网络配置迁移过程的更新操作集.

基于OpenFlow协议中流表的组成部分, 可以将数据包在交换机中的处理定义为布尔函数:

$f_s(p) = X \to Y$

(4)

其中, s代表交换机, p代表数据包; X代表匹配域, Y代表处理结果(包含动作: 将数据包转发到其他交换机或将数据包上传至控制器).

数据包从进入网络到离开网络, 是数据包在交换机间的相互转发过程. 由式(4)可知, 数据包在网络转发是个迭代处理过程, 因此, 可将数据包在网络中的操作以布尔函数的形式定义为网络转发函数F(p):

$F(p) = f_k(f_j(f_i(p))) $

(5)

其中, p指代数据包, i,j, k指代交换机编号(假设数据包在网络中的传输路径为i→j→k, 即数据包p先在交换机S_i被处理, 然后根据定义(4)得到的结果, 将数据包转发到交换机S_j中进行处理, 以此类推, 直至转发完成).

使用 ${\rm{\pi _{old}}}$ 表示旧数据包, 则旧数据包可定义为: 如果一个数据包p被尚未更新的交换机处理, 那么它就被标记为 ${\rm{\pi _{old}}}$ . 同理, 使用 ${\rm{\pi _{new}}}$ 表示新数据包, 则可定义为: 如果一个数据包被已更新了的交换机处理, 它将被标记为 ${\rm{\pi _{new}}}$ . 因此可将网络转发函数拓展为:

$\left\{ \begin{array}{l} F(p) = F_{{\rm{new}}}(p) \\ {\;\;\;\;\;\;\;\;\;\;\rm{or}} \\ F(p) = F_{{\rm{old}}}(p) \end{array} \right\} $

(6)

其中, F_new(p)和F_old(p)代表 ${\rm{\pi _{new}}}$ 和 ${\rm{\pi _{old}}}$ 由新/旧规则集处理.

包一致性. 由网络转发函数定义可得: 每个数据包的传输函数应该只涉及一个规则集: $F(p) = F_{{\rm{new}}}(p)$ 或 $F(p) = F_{{\rm{old}}}(p)$ , 而不能是两者的混合.

更新持续时间(U_d). U_d指控制器发送第一个更新消息和最后一个交换机更新完成之间的时间间隔.

更新轮次(U_round). 本节假设在单个交换机上安装的规则之间没有冲突或者依赖关系, 从而可以在单轮消息传递中更新交换机而不影响网络一致属性.U_round指更新过程所需的阶段更新次数, 在一定条件下, U_round直接影响U_d, 两者成正相关. 每轮中, 控制器更新一个交换机子集, 并保证以任何顺序更新该子集的交换机都能确保无环路产生. 控制器在确认前一轮中选择的交换机都已经在内存中安装了新的规则后, 再开始新一轮的更新.

节点操作复杂度(N_cp). 指更新过程对交换机流表操作的复杂程度. 流表规则更新操作类型和操作次数是N_cp的关键影响因素, 会直接影响U_d和更新性能.

本节模型构建主要为了优化更新调度算法, 提升更新性能. 因此, 我们可将本模型的优化目标和约束问题描述为:

$\left\{ \begin{array}{l} {\rm{min}}(U_{{\rm{round}}}) \\ {\rm{min}}(N_{{\rm{cp}}}) \end{array} \right\} \to {\rm{min}}(U_{{\rm{d}}}) $

(7)

$loop(E(t_i)\xrightarrow{U}E(t_j)) = \rm{false} $

(8)

$\left\{ \begin{array}{l} F(p) = F_{{\rm{new}}}(p) \\ {\;\;\;\;\;\;\;\;\;\rm{or}} \\ F(p) = F_{{\rm{old}}}(p) \end{array} \right\} $

(9)

其中, 式(7)为优化目标, 即通过最大程度的减少更新轮次U_round和降低节点操作复杂度N_cp来减少更新持续时间U_d. 式(8)和式(9)为约束问题, 其中, 式(8)代表更新过程需保证不会引起转发环路、式(9)代表更新过程需保持包级一致性.

本模型的难点在于如何设计更新调度算法, 在保证更新过程无环路产生、数据包转发保证一致性的前提下, 尽可能的减少更新所需时间, 提升更新性能. 由于单轮更新不会影响网络的一致属性, 因此, SDN控制器可协调交换机间的规则更新, 通过设计更新算法, 使更新轮次最小化, 减少完成更新的所需时间. 已经证明, 最小化更新轮数是NP完全问题^[13].

3 基于分类搜索的无环一致性更新方案 3.1 问题描述

定义P_old和P_new分别代表E_src(t_i)下的数据原始传输路径和E_dst(t_j)下的数据最终传输路径, $nexthop(s,P_{{\rm{old}}}/ $ $ P_{{\rm{new}}})$ 代表节点s在路径P_old或P_new的下一跳. 更新过程中, 配置是否更新成功受设备之间的实时交互时延、设备的实时更新操作所影响, 可能会因为上述因素导致网络中出现环路等问题. 基于以上定义, 可将方案的问题描述为: 已知E_src(t_i)和E_dst(t_j), 通过分析P_old和P_new上的节点, 在满足式(8)和式(9)的前提下, 设计更新算法, 寻找更新轮数较少、更新性能较优的操作集U, 求得式(7)的最优解.

3.2 基于分类搜索的更新方案 3.2.1 CSCU方案的节点集合定义

在构建模型过程中, 本方案基于分类和节点依赖搜索思想, 需要创建和更新以下相关集合, 如表1. 其中, P_new[length–1]指代最终传输路径上的最后一个节点、S_subi代表每一轮更新后剩余的待更新节点集、r_max代表完成整个更新过程所需要的最大更新轮数、 $check\_loop(s,P_{{\rm{old}}},P_{{\rm{new}}})$ 用于判断更新节点s是否引入环路、 $judge\_allfather(s,P_{{\rm{old}}},P_{{\rm{new}}})$ 用于判断节点s的父节点是否都已经更新至新规则.

3.2.2 CSCU方案的流程

先给出节点依赖关系的定义: 当节点N_a必须在节点N_b更新完成之后才能更新, 则节点N_a依赖于节点N_b. 另外, 由于目的节点不涉及规则更新, 定义为不需要更新节点. CSCU方案的更新流程如图3所示.

首先, CSCU方案利用节点分类模型对E_src(t_i)和E_dst(t_j)进行分析, 通过对比P_old和P_new节点状态, 初始化表1中的节点集.

分类模型初始化后, 执行环路搜索优化模型中的第一个模块. 调用基于拓扑排序算法的环路检测模块逐一检测S_node中的全部节点—直接给节点增添新的转发规则. 如果 $check\_loop({{N}}_i,P_{{\rm{old}}},P_{{\rm{new}}}) = {\rm{True}}$ , 即不会引入环路, 则将N_i添加到节点集T_i中(此时i=1). 检测完毕后, 并行更新节点集T_i和S_{del_old}中的节点. 其中, 对T_i中的节点实施以下操作: 下发新规则替换旧规则, 同时将节点转移至节点集S_updated中. 对于S_{del_old}中的节点, 直接删除对应的旧规则后, 移除该节点. 旧规则是否删除, 同样是判断一个节点是否已经更新的依据. S_{del_old}存储只需删除旧规则的节点, 由于节点规则失效时间不确定, 如果没有及时删除S_{del_old}中节点的旧规则, 会影响方案接下来根据依赖关系搜索可更新节点的算法. 当以上节点集更新完成, 算法继续.

接着, 调用环路搜索优化模型中的第二个模块. 对 ${{N}}_{i} \in {\textit{S}}_{{{\textit{\rm{node}}}} }- {\textit{S}}_{\textit{{{\rm{updated}}}}}$ 依次搜索可更新节点, 将满足条件 $Find\_father({{N}}_{i}) = {\rm{null}}$ 或 $judge\_allfather({{N}}_{i},P_{{\rm{old}}}, P_{{\rm{new}}}) $ $ = {\rm{True}}$ 的节点N_i加入T_i中, 前面两个条件表示当前状态下的节点N_i无父节点或者父节点都已更新. 搜索完后, 并行更新T_i的节点, 同时将T_i的节点转移至S_updated中. 如果 ${\textit{S}}_{\textit{{{\rm{node}}}}} - {\textit{S}}_{\textit{{{\rm{updated}}}}} \ne {\rm{null}}$ , 则循环执行搜索. 直至 ${\textit{S}}_{\textit{{{\rm{node}}}}} - {\textit{S}}_{\textit{{{\rm{updated}}}}} = {\rm{null}}$ , 方案结束.

后文我们将证明, 结合分类模型和环路搜索优化模型双模型, CSCU方案能有效提高更新效率, 且具有更低的计算复杂度.

3.2.3 CSCU方案的更新示例

现以图4所示拓扑为例, 将网络抽象为一个点对点有向图来演示CSCU方案的更新过程. 其中, 实线代表网络配置更新前数据转发路径, 虚线代表更新后数据转发路径. 更新步骤如图4所示.

(1) 执行节点分类模型初始化集合得: S_node={N₁, N₂, N₃, N₄, N₆, N₇, N₉, N₁₁}, S_{del_old}={N₅}, S_un={N₈, N₁₀}, S_updated =null, T_i =null.

(2) 调用环路搜索优化模型的环路检测模块检测得: T₁={N₁, N₂, N₄, N₆, N₁₁}. 并行更新节点集S_{del_old}和T₁中的节点, 对s∈T₁执行新旧规则替换并将s转移至S_updated中. 对s∈S_{del_old}执行删除旧规则操作, 并移除节点s. 此时得到S_updated={N₁, N₂, N₄, N₆, N₁₁}, S_{del_old}=null.

(3) 然后, 调用搜索模块从S_node−S_updated依次搜索符合条件的节点得T₂={N₃, N₇}, 执行更新后, 此时得到S_updated={N₁, N₂, N₃, N₄, N₆, N₇, N₁₁}.

(4) 循环搜索得T₃={N₉}, 执行更新后得S_node={N₁, N₂, N₃, N₄, N₆, N₇, N₉, N₁₁}. 很明显, 此时S_node−S_updated=null且S_{del_old}=null, 更新完毕.

3.2.4 与其他方案对比

以图4为例将CSCU方案与其他方案做比较:

(1) 基于分类时序更新^[7]: ① 控制器将交换机初始化, 分成4类: 入口交换机、新路径交换机、旧路径交换机、出口交换机. ② 更新出口交换机{N₁₀}和新路径交换机S_new={N₁, N₃, N₂, N₄, N₁₁, N₈, N₉, N₇, N₆}, 执行插入待新增流表项操作. ③ 等待一个最长端到端时延后, 更新入口交换机{N₁}, 执行修改流表项操作. ④ 等待最长端到端时延, 更新旧路径交换机S_old={N₁, N₂, N₃, N₄, N₅, N₆, N₇, N₈, N₉}和出口交换机{N₁₀}, 执行删除流表项操作, 全部更新完毕. 显然, 在新旧规则所涉及的交换机存在复杂关联时, 方案需要在不同阶段对大量共同交换机、不需更新的交换机进行不同的流表操作, 增加了交换机更新操作次数, 这会增加更新的等待时延.

(2) 反向更新^[6]: 该方案所有的节点严格依据新规则从目的节点递归向前更新. 由于默认目的节点不需更新, 因此, 所需的更新轮次=新规则涉及的节点数−1. 由图4示例可知, 新规则转发路径涉及的节点数为10, 即需要9轮才能完成更新.

(3) 双向更新^[11]: 依据两个搜索条件得到{(N₁, N₆)→(N₂, N₇)→(N₃, N₉)→(N₄, N₈)→(N₅, N₁₁)}, 共需要5轮才能完成更新.

(4) 最优化更新^[12]: 依次加入新规则对所有节点进行无环检测, 找到的依赖森林根节点有{N₁, N₂, N₄, N₅, N₆,N₁₁}, 分别删除其旧规则, 再通过无环检测寻找其子节点, 得到依赖树有: N₂→N₃,N₆→N₇→N₉, 故整个依赖森林为{N₁, N₂→N₃, N₄, N₅, N₆→N₇→N₉, N₁₁}. 其中, 依赖森林中依赖树的最大高度为所需更新轮次, 即完成更新共需要3轮.

本文提出的CSCU方案: 执行分类模型后, 通过执行环路搜索优化模型的无环检测模块, 得到的T₁={N₁, N₂, N₄, N₆, N₁₁}, 再循环执行搜索模块获得T₂={N₃, N₇}, T₃={N₉}. 所以, 经过3轮即可完成更新.

3.3 CSCU无环性验证

无环性是方案的主要研究点, 证明如下:

(1) 首先, 环路搜索优化模型中的无环检测模块不会引入环路. 事实上, 在更新过程中, 基于拓扑排序的无环检测模块对节点集S_node中的节点进行检测, 是根据直接增加新规则是否会产生环路来决定. 若产生环路则保持状态不变, 否则就将它逐一添加进节点集T_i中. 然后并行更新T_i和S_{del_old}中的节点: 对s∈T₁执行新旧规则替换并加入S_updated中, 对s∈S_{del_old}执行旧规则删除. 因为节点只有通过无环检测才确定是否更新, 并行更新T_i中的节点的过程显然不会引入环路. 另外, 对s∈S_{del_old}执行删除旧规则的操作, 只是释放相应的交换机内存空间, 不会引起无环. 所以, 无环检测更新过程不会引入环路.

(2) 其次, 环路搜索优化模型中的循环搜索模块也不会引入环路. 事实上, 按默认方法更新至最终状态的路径是不存在环路的. 现假设当前状态下有局部链路N₁→N₂→N_cur, N_cur尚未更新, 其父节点N₁, N₂都已更新. 更新N_cur, 形成环路N_cur→N₁→N₂→N_cur, 而根据假设, 其父节点都已更新, 即整个环路链路涉及的节点都已更新至新规则. 该环路是整个更新至最终状态的一个局部链路, 则与最终状态下的新规则中无环路的矛盾, 所以更新N_cur不会引入环路. 循环搜索更新, 直至S_node−S_updated =null时更新完毕, 整个更新过程都不会出现环路.

3.4 相关研究比较

本节将从适用性、更新持续时间U_d、更新节点操作复杂度N_cp、更新算法计算复杂度4个方面进行比较. 适用性, 指方案场景适用范围. U_d为整个更新过程每个阶段所用时间总和, 集中体现于更新过程的所需轮次U_round, 更新所需轮次越多, 等待更新的时间越长, U_d越大. N_cp指更新过程对节点操作的复杂程度, 集中体现于: 需在不同更新阶段执行不同更新操作的节点越多、对同一节点更新操作的次数越多, 更新等待时延就越长, U_d越大. 更新算法计算复杂度, 指切换更新规则过程中相应逻辑功能计算的复杂性.

本节将本文方案与第2节的相关研究进行比较, 结果如表2所示.

(1) 适用性. 不管网络拓扑复杂与否, 分类时序更新都依据新旧转发路径上的节点严格设定阶段进行更新. 若网络配置简单, 使用该方案反而降低更新效率. 若配置更新存在大量的共同交换机, 则需要分别在不同的更新阶段, 对同一交换机进行不同的流表操作, 更新操作量增加. 因此, 分类时序存在一定的应用场景局限性, 适用性较差. 本方案在分类初始化基础上, 设计能减少更新轮数的环路搜索优化模型, 无论拓扑结构复杂与否, 本方案更新效率都有保证.

(2) 更新持续时间U_d. 分类时序更新设定固定阶段更新, 下一个阶段的节点更新必须等待上一个阶段的节点更新完毕才能进行, 更新轮次固定. 若更新配置复杂, 还会因为等待旧包流出网络等待端到端的最长时延, 增加更新时间. 反向更新和双向更新节点依赖复杂, 导致更新轮次多, 更新时延高. 本方案结合分类模型和环路搜索优化模型, 平均更新轮次接近最优化更新, 更新持续时间短.

(3) 更新节点操作复杂度N_cp. 如3.2.4节所述, 更新配置复杂时, 分类时序更新需在不同阶段对大量节点进行不同的流表更新操作, 大量节点更新操作次数多. 因此, 方案的更新节点操作复杂程度高, 更新等待的时延长. 虽说细化流表项操作在更新某一阶段能使新旧数据包并行传输, 一定程度上降低控制器负载. 但与其产生的等待时延相比, 时间开销更为重要. 本方案只需针对相应节点集执行相应规则操作, 操作复杂度低, 等待时延少, 能进一步减少U_d.

(4) 算法计算复杂度. 假设使用邻接矩阵存储节点信息. 最优化更新中, 初始化所有节点状态、加入新规则检测是否引入环路都为O(n), 在状态转换过程中, 更新节点状态和下一轮节点的判环操作也都为O(n). 因此, 最优化更新的时间复杂度为O(n⁴). CSCU方案中, 分类初始化和对待更新的节点判环操作的总时间复杂度为O(n²), 搜索可更新的节点为O(n), 因此总的时间复杂度为O(n³). 而基于分类时序更新只需遍历矩阵进行分类, 然后在不同节点进行更新, 时间复杂度为O(n²).

4 仿真分析

为了分析比较相关方案在不同情况下更新的效果, 本文基于自主搭建的SDN仿真平台进行模拟实验. 平台所用设备为Ubuntu 16.04操作系统, RYU开源控制器和mininet网络仿真器. 仿真实验设定实验拓扑节点数, 设定源点和目的节点. 每次实验通过随机更改相邻节点的边权值来模拟网络拓扑结构的变化, 相邻节点的边权值服从(1–1000)的均匀分布. 权值确定后, 再通过OSPF算法获取源节点到目的节点的路径.

① 关于更新轮次和更新持续时间U_d的关系, 在上一节已经有详细解释. 在此, 通过300次仿真实验测试, 对相关研究方案每一次实验的更新轮次进行分析对比, 结果如图5所示.

实验结果显示, 反向更新的所需的更新轮次普遍多于其它方案, 这是因为反向更新只与新的转发规则相关, 更新轮次=新规则转发相关节点−1. 由于分类时序更新严格设计更新阶段, 因此更新轮次固定. 本方案的更新轮次接近最优化更新, 比其他方案都少.

② 配置更新交叉程度. 指配置更新过程中, 同时在新、旧路径上的交换机占与更新相关的交换机总数的比例. 配置更新交叉程度的大小影响CSCU方案的更新性能. 更新过程中, 在新路径上而不在旧路径上的交换机数越多, 涉及旧规则的交换机就越少, 就越难形成回路. 因此, 更新轮次就越少, 更新性能越好. 相反则需要更多的轮数来完成更新.

至此, 就配置更新交叉程度对本方案更新轮次的影响进行实验分析. 由于交叉程度低的时候形成环路的可能性低, 所以交叉程度为0和25%的结果参考价值不大. 因此本实验只对交叉程度为50%、75%、100%的情况进行实验, 结果如图6所示.

为了更好的与分类时序更新对比分析, 综合CSCU方案在不同交叉程度更新情况的实验结果, 求得配置更新不同交叉程度下的平均更新轮次. 实验结果表明, 本方案在配置更新交叉程度为0、50%、75%、100%下的平均更新轮次都比分类时序更新少, 结果如图7所示, 其中, 0、50%、75%、100%分别代表CSCU方案的配置更新交叉程度, timing代表分类时序更新.

③ 更新过程的节点操作复杂度直接体现于对同一交换机的流表项操作次数大于1的交换机数. 用num_large_1表示对同一交换机的流表项操作次数大于1的交换机数. 显然num_large_1越大, 更新的节点总操作次数越多, 更新过程的节点操作复杂度就越高. 针对节点操作复杂度, 本节设计多次实验, 假设实验的节点数固定为20、新旧路径跳数相同. 对分类时序更新进行测试分析, 得出num_large_1的平均值随路径跳数变化的情况, 实验结果如图8所示. 实验设定新旧路径源、目的节点, 所以num_large_1≥2.

分析实验可得, 网络节点数一定的情况下, num_large_1随着路径跳数的增大而增大. 即随着路径跳数的增多, 同是新旧路径上的节点的节点数就越多, 对所有节点的总操作次数就越多. 因此, 更新过程的节点操作复杂度就越高. 而本方案经分类初始化后, 与更新配置复杂度无关, 更新节点操作复杂度低.

综上所述, 相较于分类时序更新, 基于分类搜索的无环更新一致性方案有更好的场景适用性、更低的节点操作复杂度N_cp和更少的更新轮次U_round, 能够在满足模型约束条件(8)和(9)的前提下有效减少更新持续时间U_d、提升更新效率, 实现模型的优化目标. 另外, 在更新轮次方面, 本方案相对于其他相关研究方案都有着不同方面的性能提升.

5 结语

本文根据在研项目的研究目标, 对SDN流表更新一致性的相关研究成果进行了详细的研究. 并针对基于分类时序更新方案存在应用场景适用性差、更新时延长和节点更新复杂程度高等问题, 提出了一种基于分类搜索的无环更新方案. 随后, 本文通过更新示例的展示, 在适用性、更新时间等性能方面对该方案和相关研究方案进行了对比分析. 此外, 本文对该方案的无环一致性更新进行了理论分析, 证明了方案的可行性. 最后, 通过搭建SDN仿真平台进行了仿真实验. 仿真实验针对更新轮次对该方案与相关研究方案进行了分析对比, 也针对不同配置更新交叉程度和节点操作复杂度单独跟分类时序方案进行了对比. 仿真结果表明, CSCU方案具备应用场景适用性高、节点更新操作复杂度低的优点, 是一种能够有效的减少更新所需轮次、更新时延和降低计算时间复杂度的高效率更新方案.