0 概述

软件定义网络(Software Defined Network, SDN)是一种将网络控制和转发功能相分离的新型网络架构^[1], 其可简化网络管理, 提高网络的可编程性和灵活性。近年来, 随着机器学习技术的快速发展, 研究人员开始尝试在SDN中引入机器学习方法, 以提高网络管理和控制效率, 解决传统方法中依赖配件、配置复杂的问题。

分布式SDN的架构包括扁平式和层次式^[2]2种方式, 其中, 扁平式架构将整个网络划分为若干个SDN子域, 每个子域内分配一个控制器负责集中管理域内交换机, 且多个控制器被分别部署在不同的子域内, 从而构建一个逻辑上集中、而物理位置上分布的SDN架构, 如Onix^[3]、Hyperflow^[4]等。在扁平式架构下, 主要采用交换机迁移和重定向流的策略^[5]来平衡多个控制器之间的负载, 以减轻控制器的负载, 但是频繁迁移交换机将会增加网络延迟和开销, 降低网络性能。层次式架构将控制平面划分为垂直的层次, 常见的方式为将控制器分为普通控制器和全局控制器两层^[6-7], 或者在控制器和交换机之间增加一个中间层^[8], 但是这些方案均未对全局控制器或者中间层控制器的过载问题进行深入研究和解决。

文献[9]提出了SHLB模型, 在控制平面与数据平面之间插入一个中间层, 在中间层采用分流策略将不同类型的数据流传输给不同类型的控制器, 可有效缓解控制平面负载不均的问题, 并采用文献[10]中的实时调度策略解决中间层过载问题。但是全局控制器在发现某个控制器资源负载过轻或过重时, 需要合并或者开启新的控制器, 在此过程中, 将会涉及大量流控制策略的迁移, 造成网络延迟的增加, 从而影响网络性能。

与以往的单边研究思路不同, 本文在提出网络流量预测算法后, 通过收集不同的网络参数, 在SHLB模型的基础上对其进行改进, 并提出基于最大熵和隐马尔科夫算法的流量预测与多控制器预部署PPME模型。该模型基于捕获的历史数据流, 利用最大熵算法预测未来一段时间内数据流的分布, 从而产生控制平面内各类控制器的预部署方案, 加入隐马尔科夫链对预测方案进行优化, 并采用增强学习算法对实际数据流与预测数据流进行比较。

1 相关工作 1.1 SHLB模型

SHLB模型是一个可扩展的、分层的SDN控制平面负载均衡模型, 该模型在控制平面与数据平面之间增加一个中间层, 将SDN网络分为控制层、中间层和数据层三层。控制层包含若干个控制器, 其接收中间层转发的数据流, 按照设定规则对数据流进行处理, 并将处理结果反馈给中间层。中间层接收到数据层交换机的消息流后, 按类别或者其他规则将其转发给某个控制器, 再接收该控制器的处理结果并通知其相应的交换机。数据层由大量的SDN交换机组成, 其将无法处理的数据流转发给中间层, 接收中间层的处理结果并更新流表规则。SHLB模型架构如图 1所示。

SHLB模型控制层中的控制器按角色可分为全局控制器和局部控制器, 其中, 全局控制器负责保障控制层的负载均衡, 并对局部控制器进行动态调整。局部控制器一方面接收、处理与响应中间层的数据流和请求, 另一方面需周期性地向全局控制器报告实时的资源利用率并接收其命令。

从细粒度的时间点来看, 网络流是一个不断变化的动态变量, 但是从一个时间范围来看, 其又是相对稳定的。如果负载均衡模型只基于当前时间点考虑这种变化, 而不考虑未来数据流的变化趋势, 可能会造成控制器的低性价比迁移, 即这种迁移并不能保证一定时间段内网络性能的整体提高, 而只对当前突发的网络数据流提供帮助, 可能造成整体网络延迟的增加。为了解决该问题, 本文提出了PPME模型, 采用增强学习算法对实际数据流与预测数据流进行比较, 若偏差大于设定阈值, 则重新生成部署方案; 否则, 仍采用旧方案。在方案运行期间, 控制器不再进行迁移, 以降低迁移对网络性能的影响。

1.2 最大熵原理

最大熵模型^[11]是一种对数线性模型, 其是在给定事件集上挖掘潜在约束条件, 并在样本数据有限的情况下, 选取一种能够满足已知约束条件, 且尽可能使未知事件均匀分布的恰当模型。最大熵模型是采用概率估计的方法, 基于信息熵理论^[12]而建立起来的概率统计模型。信息熵作为一个随机事件不确定性的度量, 随机事件越不确定, 则其熵越大; 若随机事件退化为确定事件, 则其熵为0。随机变量X的信息熵可以被定义为:

定义1   假设X={x₁, x₂, …, x_n}是一个离散随机变量, 则其熵H(X)表示为:

$ H(X) = - \sum\limits_{i = 1}^n {{p_i}} {\rm{lb}}{p_i} $

(1)

其中, n为离散随机变量可取值的总数量, p_i=P{X=x_i}表示X取值为x_i的概率, 若某一项p_i=0, 即X取值为x_i的概率为0。

定义2  随机变量X与Y的联合分布形成的联合熵用H(X, Y)表示, 则其条件熵为:

$ H(X{\rm{|}}Y) = H(X, Y) - H(Y) = - \sum\limits_{x, y} p (x, y){\mathop{\rm lb}\nolimits} p(x{\rm{|}}y) $

(2)

定义3  假设p(x)、q(x)是X中取值的2个概率分布, 则p对q的相对熵为:

$ D(p\parallel q) = \sum\limits_x p (x){\rm{lb}}\frac{{p(x)}}{{q(x)}} = {E_{P(x)}}{\rm{lb}}\frac{{p(x)}}{{q(y)}} $

(3)

随机变量X与Y的互信息定义为X与Y的联合分布和独立分布乘积的相对熵, 分别如下所示:

$ I(X, Y) = D(P(X, Y)\parallel P(X)P(Y)) $

(4)

$ I(X, Y) = \sum\limits_{x, y} p (x, y){\rm{lb}}\frac{{p(x, y)}}{{p(x)p(y)}} $

(5)

1.2.1 最大熵迭代算法

最大熵迭代算法具体步骤为:

输入   特征函数f₁, f₂, …, f_n

输出  最优参数值w^*, 最优模型P_w

步骤1   在经验分布$\tilde P(X, Y)$、模型P_w(y|x)中, 对所有的i∈{1, 2, …, n}, 取初值w_i=0, 对每个i∈{1, 2, …, n}:

1) 令∂_i是方程$\sum\limits_{x, y} {\tilde P} (x)P(y|x){f_i}(x, y)\exp \left( {{\partial _i}{f^*}(x, y)} \right) = {E_{\tilde P}}\left( {{f_i}} \right)$的解, 且${f^*}(x, y) = \sum\limits_{i = 1}^n {{f_i}} (x, y)$。

2) 更新w_i值, w_i←w_i+∂_i。

步骤2  如果不是所有的w_i都收敛, 则重复步骤1。

近年来, 最大熵算法不仅被广泛应用于机器翻译、词性标注、语法分析与文本分类等领域^[13-15], 还被应用于构建预测模型。文献[16]运用最大熵算法预测在RCP2.6和RCP8.5 2个未来气候变暖的情景下, 水杨柳在云南省的潜在分布情况。文献[17]采用最大熵原理构建流量预测算法, 根据历史预测误差对各种单一预测算法进行取舍, 最终得到预测结果的分布情况。通过对实际网络流量进行预测与测量, 结果发现, 与其他预测算法相比, 最大熵算法具有较高的预测精度, 且预测结果更合理。

网络流量会随着时间和空间不断发生变化。在时间维度上, 网络流量会随着一天中的不同时段发生变化, 比如白天的流量高于夜晩的流量, 此外, 网络流量还可能在极短的时间内发生剧烈变化^[18]。本文提出的PPME模型在SDN控制层中利用最大熵算法, 通过历史网络流量预测未来网络流量, 从而实现对控制器的预部署, 以降低控制器迁移的频率, 提高网络性能。

1.2.2 隐马尔科夫算法

隐马尔科夫算法^[19-20]广泛应用于语言识别、强化学习和生物信息学等领域。隐马尔科夫算法是一个有限离散时间的马尔科夫模型, 该模型假设系统是一个具有隐状态的马尔科夫过程。它可以被定义为一组λ=(Π, A, B), Π是初始概率分布, A是转移概率矩阵, B是一个观测概率序列(发射概率)。具体来说, 一个隐马尔科夫算法是由以下要素^[21]定义的:

1) Q={q₁, q₂, …, q_N}是一组状态, 其中, N为隐藏状态的数量, q_t为t时刻的隐藏状态。

2) O={o₁, o₂, …, o_T}是一组观测值, 其中, T是观测值的数量, o_T是T时刻的可观测状态。每个观测状态都来源于一个词汇表V={v₁, v₂, …, v_M}, 其中, M为观测值的数量。

3) A={a₁₁, a₁₂, …, a_N1, …, a_NN}是一个N×N的转移概率矩阵。a_ij(1≤i, j≤N)表示状态i变为状态j的概率, 具体表示方法为:

$ {{a_{ij}} = P\left( {{q_{t + 1}} = {s_j}|{q_t} = {s_i}} \right)} $

(6)

$ {{a_{ij}} \ge 0, \forall i, j} $

(7)

$ {\sum\limits_{j = 1}^N {{a_{ij}}} = 1, \forall i} $

(8)

隐马尔科夫算法的状态图如图 2所示, 其中, H_i(i=1, 2, …, T)为隐藏状态集合, O_i(i=1, 2, …, T)为观测值集合。马尔科夫过程位于可观测状态之上, 由当前状态决定, A只能观测O_i, 且O_i由马尔科夫过程和B的隐状态决定。

2 本文模型设计

针对传统方法不能对网络流量的变化特征进行准确描述, 且预测精度较低的问题, 本文提出PPME模型, 该模型在控制层引入最大熵和隐马尔科夫算法, 通过学习历史数据流来预测未来一段时间的数据流, 从而提前部署控制器, 以减少控制器的迁移次数, 缩短网络延迟。PPME模型的设计总共分为3个部分, 首先, 收集历史网络数据流并对其进行分类。其次, 利用最大熵算法对未来网络流进行预测, 并产生预测结果, 最后, 利用隐马尔科夫算法对预测结果进行评估, 优化控制器部署。

2.1 数据流收集与分类 2.1.1 数据预处理

本文从MAWI Working Group获取了12月×30天×24小时的流量集, 该流量集已被广泛应用于流分类, 可以帮助研究人员评估其流量检测方法^[22]。数据集中的数据特征包括产生数据包的时间、传输控制层的协议、目标地址、发送地址以及数据包配置信息(数据包大小、端口号与MAC地址)等。对于本文来说, 影响流量预测的主要因素是数据包的数量、时间和协议类型, 因此, PPME模型以数据包大小、数据包协议名称和时间作为特征值, 通过对数据进行整理, 生成了网络流数据矩阵, 具体如图 3所示, 其中, 行表示每秒内各个协议数据包的数量, 列表示各种协议类型。在单位时间内, 不同协议的数据流数量差别较大, 如图 4所示, 其中, HTTP数据流最多, 且HTTPS、UDP和ICMP数据流相差不大, 而IPv6、UDPv6及其他数据流较少, 利用该流量分布指导控制层中控制器的分类及部署。

2.1.2 数据流分类

关于数据流的分类, 部分研究采用机器学习的方法, 如文献[23]提出的TrAdaBoost模型, 其是AdaBoost模型的改进, 在解决多级网络流量的分类方面具有较好的性能。实验比较了TrAdaBoost模型与本文模型对所得数据流的识别效果, 如表 1所示。从表 1可以看出, 在准确度与所需时间方面, 本文PPME模型更具有优势。

2.2 数据流预测

在了解一个随机事件的概率分布时, 预测满足所有的约束且不进行任何条件下的主观假设, 概率分布最均匀时预测风险最小, 从而得到概率分布的熵最大, 即最大熵数学模型。因为网络流复杂多变, 且很多人为的主观预测很难得到验证, 通过客观的历史数据构造概率矩阵, 以求得最大熵情况下的概率矩阵作为当时的预测结果, 可以最大程度地提高预测的准确性。

由于数据包的数量能够客观反映数据流量, 因此PPME模型将数据包的数量和数据包的协议类型作为主要特征参数, 并设计了数据流预测算法, 数据流预测算法为基于最大熵的网络流预测算法, 其中, G为数据包矩阵, N为数据包总数, Z为概率矩阵, E为最小常数误差。最大熵网络流预测算法的具体步骤为:

步骤1   将训练矩阵转化为概率矩阵, 即Z(i, j)=G(i, j)/N。

步骤2   将训练矩阵乘以其转置矩阵, 得到概率方阵, 即Z₁=Z₀×Z₀^T。

步骤3   对概率方阵进行迭代幂运算, Z₂=Z₁×Z₁^T, Z₃=Z₂×Z₂^T, …, Z_n=Z_n-1×Z_n-1^T。

步骤4   计算方差|Z_n-Z_n-1|, 直到方差小于设置的常数E, 则结果收敛, 且在该结果上进行预测时产生的误差最小; 否则重复步骤3。

在最大熵算法中, 通过将训练矩阵乘以训练矩阵的转置矩阵可以得到一个概率方阵, 通过对该概率方阵进行迭代幂运算, 最终可得到一个趋于稳定的各种协议数据流量的比例关系。根据该比例关系对控制器进行预部署, 可以提高控制器的利用率, 降低控制器迁移过程对网络运行的影响, 从而提高网络性能。

2.3 预测结果的优化

由于最大熵算法的计算量非常庞大, 目前还没有有效的方法能彻底解决其计算复杂度问题, 导致PPME控制器预部署方案的生成需要花费较长时间, 对于合理的部署方案, 尽可能延长其工作时间是非常有必要的。通过对预测流量与实际流量进行拟合, 结果发现, 最大熵算法的预测结果在一段时间内具有较为稳定的预测准确度, 如图 5所示。最大熵算法在模拟流量曲线的过程中, 流量变化曲线的导数越大, 则算法的预测准确度越低, 且时效性越差。在理想条件下, 导数为0且流量曲线不变化时是预测算法的理想状态, 但是对于网络流来说, 其流量曲线在不断变化, 几乎不可能出现导数为0的情况, 因此单一的最大熵算法无法满足较长时间的预测准确度。为了解决该问题, PPME模型在控制层引入了隐马尔科夫链, 利用隐马尔科夫的五元组(隐含状态S, 观测状态O, 初始状态概率矩阵P、隐含状态转移概率矩阵M, 观测状态转移概率矩阵K), 通过对不同阶段的预测结果给予奖励或惩罚, 并对历时较长的隐马尔科夫过程给予γ平方衰减, 以降低其权重。

不同阶段的训练奖励机制可以在很大程度上提高最大熵算法预测结果的准确度。通过对每个阶段的数据进行最大熵预测, 极大地减少了最大熵算法的运算量, 提高了运算效率。

在部署周期优化算法中, 设置初始指数W₀为1 000, 警戒比例K₀为0.618, 阻尼指数K₂为1, 假设矩阵Z有n行、m列, 其具体步骤为:

步骤1  对矩阵的每行进行遍历, for x in range(n), x∈[0, n)。

步骤2  对矩阵的每列进行遍历, for y in range(m), y∈[0, m)。

步骤3  初始化:令W_X=W₀。

步骤4  加强学习, W_X=W_X+K₂×Z[x, y]。

步骤5  如果W_X>K₀×W₀, 保持使用原有预测方案, 否则重新使用最大熵算法进行网络流量预测, 并部署控制器。

实验验证了加入隐马尔科夫算法后的预测拟合效果, 如图 6所示。使用单一的最大熵算法在前600 min内, 预测准确度较高, 但随着时间的延长, 预测准确度呈降低趋势; 加入隐马尔科夫后该算法仍可以保持较高的预测准确度, 这说明了本文算法通过不断调整每个阶段预测结果的准确度, 可在多数情况下较准确地预测复杂场景下的网络流量情况, 优化最大熵算法的预测结果。

3 实验结果评估 3.1 最大熵算法预测结果的准确度

本文对所采集的网络流以8:2的比例进行分割, 分别作为训练集和测试集。实验将采用最大熵算法对训练集中的数据进行训练, 并预测之后时间段的流量。通过比较预测结果与实际流量来评估最大熵算法预测结果的准确度。

本文以4个不同大小的数据集(流量包个数依次为12 104、63 741、180 040、623 120)为研究对象, 实验采用支持向量回归(Support Vector Regression, SVR)模型、梯度提升回归树(Gradient Boosting Regression Tree, GBRT)模型与本文提出的PPME模型对其下一时刻流量值的预测情况与实际流量进行对比, 如图 7所示。从图 7可以看出, 对于不同的数据集, 预测准确度存在差异, 当数据量较小时, 3种算法的预测准确度相差不大, 且均能达到85%左右, 但是随着流量数据的增加, SVR模型和GBRT模型的预测误差逐渐增大, 而本文提出的PPME模型仍然保持较高的预测准确度, 且最大熵的核心是收敛的, 因此数据集的大小不会影响最大熵的准确度, 在大型复杂的网络场景下, 最大熵算法的预测准确度较稳定。

3.2 预部署的有效性

本文模型将不同协议的网络流分配到相应类型的控制器中进行处理, 实验采用与SHLB模型相同的计算机作为控制器, 每个控制器所能装载的数据包个数如图 8所示。从图 8可以看出, 当数据流达到30 000个/s时, 控制器负载率达到了80%, 即认为控制器满负载。因此, 本文对每个控制器每秒最多分配30 000个数据包, 然后再进行部署。

图 9比较了PPME模型与SHLB模型部署的控制器个数。考虑到图 4所示的各协议数据包的分布情况, 相比SHLB模型, PPME模型考虑了一段时间内各类网络流的整体情况, 对于数据量巨大的HTTP数据流, PPME模型部署了多余的控制器, 避免当HTTP数据流增加时控制器发生迁移, 而对于数量相对较少的HTTPS、UDP及ICMP数据流则部署较少的控制器, 避免了资源浪费, 同时降低了控制器迁移的次数与频率。

在进行控制器分配后, 对于多组数据, 实验通过发送包工具发送不同速率的流量数据包对PPME模型和SHLB模型进行测试, 中间层实体资源利用情况和网络响应时间如图 10和图 11所示。实验结果表明, PPME模型在网络发生特殊状况后, 系统的处理速度和性能均更好, 且承受突发状况的能力更强。

4 结束语

本文基于最大熵和隐马尔科夫算法构建了PPME模型, 通过对不同类型的网络数据包数量进行预测, 为SDN模型中的控制器提供预部署方案的理论依据。PPME模型能够实现在复杂网络情景下对流量的准确预测, 同时, 将网络流量以协议类型进行分类, 能够达到对SDN中多控制器实现预部署的目的。实验结果表明, PPME模型对网络流量的预测准确度达到85%以上, 实现了对SDN中控制器的预部署策略, 有效缓解网络中的拥堵问题, 提高SDN环境中的资源利用率和控制器的工作效率, 且保证了SDN控制网络的稳定性。下一步将在云环境下, 将各控制器的决策控制情况汇报给云端, 并在云端利用EM高斯方差进行聚类分析。