SDN中基于PSVD的交换机迁移算法

0 引 言

软件 定 义 网 络 （Software Defined Network，SDN）［1］是一种传输与控制分离、软件可编程和集中式控制的新型网络体系架构，其被业界用来解决目前网络结构僵化的问题。但是当SDN部署在大规模网络中时，集中式控制平面会面临很大的挑战［2－3］，并且控制器与交换机之间不能动态地适应流量变化，从而会导致控制器上负载不均衡［4］。

文献［5］提出，可以通过进行周期性的Open-Flow交换机迁移来维持网络整体负载均衡，但没有提出具体的迁移算法。目前已有的负载均衡算法［6－8］存在以下两点缺陷：（1）迁移选择策略只基于某一个固定阈值，即如果交换机的负载超过了负载阈值的上限，则触发迁移机制。这种基于固定阈值的迁移算法在遇到突发的网络负载峰值时就会触发交换机在两个控制器上进行迁移，容易产生迁移开销。（2）多个交换机节点会选择同一个控制器作为迁移的目标节点，导致该目标控制器的负载信息急剧增加，容易造成群聚效应。

本文提出一种SDN中基于奇异值分解性能预测（Performance Prediction of Singular Value Decomposition，PSVD）的交换机迁移选择算法。首先基于PSVD算法对SDN中交换机动态迁移问题进行物理建模，然后提出基于PSVD的交换机迁移选择算法，给出算法的具体流程，最后通过仿真实验的分析与对比，验证该算法的可行性与有效性。

1 交换机迁移选择建模

给定网络G（V0，E），其中，V0 为所有交换机节点的集合，节点总数为｜V0｜＝n；E为链路集合，链路权重表示时延。

定义集合：

控制器集合为C＝｛c1，c2，…，cn｝；

交换机集合为V0＝｛v1，v2，…，vn｝。

二进制变量定义：

这里假定根据交换机动态迁移选择算法，将交换机v1从控制器c1迁移到控制器c2上。图1所示为有两个控制器的交换机迁移物理拓扑图，图中，控制器c1连接v1、v2和v3等交换机。假定交换机v1上的总负载较多，使得控制器c1的负载超出阈值，而控制器c2上的总负载较少，且空闲流量可以支撑交换机v1的运行，则可将交换机v1从控制器c1上迁移到控制器c2上，以充分利用控制器c2的空闲资源，保证控制器的负载均衡。

图1 交换机迁移物理拓扑图

2 基于PSVD的交换机迁移选择算法设计

2.1 PSVD算法

PSVD算法是一种基于奇异值分解（Singular Value Decomposition，SVD）理论以及负载信息矩阵得到下一时刻的性能预测值，进而分析迁移选择的趋势的算法。负载信息矩阵R为各个控制器在过去t时间段内的负载信息，负载信息L主要包括3种资源数据：CPUlcpu、内存lmem以及流量lbw。 控制器的CPU负责处理所有数据，控制器的内存用来存取数据。OpenFlow交换机若在本地的流表中找不到与收到的数据包相匹配的流表项，则会根据配置，把收到的数据包的报头或者整个数据包封装到packet＿in消息中，发送给OpenFlow控制器。控制器收到报文后决定如何处理当前流，并通过OpenFlow协议把处理意见转化为流表，下发至OpenFlow交换机［9］。因此对流量统计就是对控制器处理packet＿in个数的统计。矩阵R的形式化表示如式（1）所示：

式中：Rij为i（i＝0，1，…，m）时刻对该控制器的负载信息资源j∈｛0，1，2｝的使用情况；m 为T 时间段内的m个时刻，m＞3。

取控制器m个时刻的负载信息组合成负载信息矩阵R，根据SVD理论，R可分解成3个线性独立的矩阵T、W 和VT，如式（2）所示：

式中：T为m×m的列正交矩阵，为时间参数相关矩阵；W 为m×3的对角矩阵，且对角线元素非负；VT为矩阵V的转置，是3×3的正交矩阵，为资源参数相关矩阵。

矩阵T为关于时间参数的列正交矩阵，其行向量珒ti为在i时刻的时间参数相关向量。假定过去某一时刻的时间参数相关向量珒tj与当前时刻的时间参数相关向量珒t0有一定相似度，则认为珒tj的下一时刻珒tj－1最接近预测值。在基于向量的信息检索中，有许多常用的相似度计算方案［10］，比如内积、Dice系数、Jaccand系数和余弦系数。本文使用余弦相似度［11］计算当前时间向量珒t0与过去每个时间参数向量珒ti的相似度，如果珒tj时间参数向量与当前时间参数向量的余弦系数最大，则表示珒tj时间参数向量与当前时刻的珒t0相似度最高，应取珒tj－1作为一个未来时刻负载信息的时间参考向量。然后，将当前时刻与历史最相似时刻的时间参数相关向量作为预测未来时刻的参考值。

式中，Sim（珒ti，珒tj）为i时刻的时间参数相关向量和j时刻的时间参数相关向量的余弦系数。

式中：珒tf为预测的未来时刻的时间参数向量；α、β分别为当前时刻与过去时刻的参考权重，均为不大于1且不小于0的参数。α越大，表示未来时刻的时间参数向量参考当前时刻的权重越多，而β越大，则表示未来时刻的时间参数向量参考过去相似时刻的权重越多。

式中：Rf为未来时刻的负载信息L；W′为修正干扰因子后的降维矩阵。

PSVD算法的重点是对负载信息矩阵R的生成，并根据SVD理论得到时间参数相关矩阵T、奇异值对角矩阵W 和资源参数相关矩阵V。通过对奇异值对角矩阵的降维处理以及对未来时间的预测，最终得到未来时刻的负载信息。在预测前，将过去时刻的负载信息作为输入，该时刻的负载信息作为输出，调整相关的参数，并通过学习和测试使不同的输入矩阵得到相应的负载信息，通过一定的样本训练系统，就可以使用PSVD算法实现对控制器的性能预测。使用PSVD算法预测控制器性能的流程图如图2所示。

图2 PSVD算法预测控制器性能流程图

2.2 交换机动态迁移选择算法

在交换机从低负载的控制器迁移到高负载的控制器的问题上，保持网络负载均衡需要具备3个条件：（1）确定迁移时机，即确定在什么时刻应该迁移一个交换机，从而确保整个网络的控制器负载处于平衡态；（2）确定候选迁移交换机，即确定哪些交换机应该迁移；（3）确定交换机迁移的目标控制器，即确定交换机应该被迁移到哪个目标控制器上。基于PSVD算法预测控制器的负载信息Lf，从而完成交换机的动态迁移选择。

式中：L为控制器的负载，定义Lhigh为控制器负载阈值的上限，Llow为负载阈值的下限，Llow＞L表示控制器处于低负载状态，Lhigh＜L表示控制器处于高负载状态，仅当Llow＜L＜Lhigh时，该控制器的负载处于平衡态；lcpu为该控制器上CPU的使用率；lmem为该控制器上内存的使用率；lbw为该控制器上流量的处理率，同时也是控制器上统计的Packet-In个数／最 大处理个数；δ1、δ2和δ3分别为CPU、内存和流量所占控制器负载的权重，且均为大于0小于1的参数，这里分别设置为0.3、0.3和0.4。

基于PSVD的交换机迁移选择算法的详细步骤设计如下：

（1）交换机迁移的触发时机

步骤1：根据式（6）计算控制器c1的当前负载L，判断L是否超出高负载阈值Lhigh，如果Lhigh＜L，表示当前控制器处于高负载状态，则转步骤2。

步骤2：计算该控制器未来时刻的负载信息，从而判断当前负载是否属于突发性负载。利用PSVD算法得到未来时刻的负载Lf＝Rf，如果Lhigh＜Lf，则触发一次迁移，反之，不触发迁移。

（2）确定候选迁移交换机

步骤1：根据PSVD算法对未来时刻负载信息的预测结果，分析具有最大占有率的资源类型Li。

步骤2：针对具有最大占有率的资源类型Li，选择出占用资源最多的交换机，即候选迁移的交换机s1。

（3）确定交换机迁移的目标控制器

步骤1：根据式（6）计算当前控制器的负载L，并选择具有较小负载信息的控制器c2。

步骤2：使用PSVD算法预测未来时刻的负载信息Lf＝Rf，如果选择出的具有较小负载信息的控制器c2的未来负载仍然处于较低状态，则转步骤3，否则，转步骤1。

步骤3：如果控制器c2未来时刻的负载信息与候选迁移的交换机s1的负载信息相加不会超过高负载阈值Lhigh，则确定选择控制器c2为交换机迁移的目标控制器，否则，转步骤1。

3 仿真结果及分析

3.1 PSVD算法实验设计

实验采用Internet2OS3E拓扑进行验证，将流量数据用于OpenDaylight和Mininet仿真平台上，可以获取到控制器以及各交换机的CPU、内存和流量的全部负载信息。

在预测前，将过去时刻的负载信息作为输入，该时刻的负载信息作为输出，通过学习和测试，使不同的输入矩阵得到相应的负载信息，通过负载信息调整相关的参数。

定义参数“平均偏差”，衡量3个算法的优越性。平均偏差越小，表示算法的预测值越接近真实值，算法的性能越好。预测值与真实值的平均偏差表示如下：

式中：Pi为预测值；Ri为真实值；n为监测数据的组数。

3.2 PSVD算法实验结果及分析

通过计算每种预测算法的平均偏差来比较各预测算法的性能，计算结果如表1所示。

表1 3种预测算法的平均偏差值比较

图3～5所示分别为在PSVD算法、简单平均法和最近邻法3种预测算法下对控制器负载性能参数CPU、内存和流量的比较。

图3 CPU预测值的比较

根据上述数据分析及图形的比较结果可知，PSVD算法预测性能的准确性要优于简单平均法和最近邻法。

3.3 基于PSVD算法的交换机迁移选择算法实验设计

交换机迁移选择问题主要是利用性能预测算法确定迁移时机、候选迁移交换机和迁移目标控制器。仍然采用简单平均法预测和最近邻法预测对比PSVD算法预测解决交换机迁移问题。3种算法分别记为PSVD的迁移选择法、简单平均－阈值法和加权－阈值法。

图4 内存预测值的比较

图5 流量包预测值的比较

定义参数“迁移次数”，用于判断比较迁移选择算法的优越性，尤其是系统应对突发性负载的能力。迁移次数越小，表明算法的选择结果更优。定义参数“控制器资源占用率的标准方差”，用于判断迁移后的负载均衡性。标准方差越小，说明整体网络的负载越均衡。

3.4 基于PSVD算法的交换机迁移选择算法实验结果及分析

在负载阈值上限相同的情况下，PSVD的迁移选择法、简单平均－阈值法和加权－阈值法的交换机迁移次数如表2所示。

表2 3种算法的迁移次数比较

由表2分析可知，相比于简单平均－阈值法和加权－阈值法，基于PSVD的交换机迁移选择算法可以更好地应对突发性负载，显著提高网络的稳定性。其中交换机进行一次迁移的前后，整体网络的负载变化如图6所示。

图6 算法的负载均衡效果比较

4 结束语

本文在SDN中应用了基于PSVD的交换机迁移选择算法，该方法是将负载大的控制器管理下的某一个交换机迁移到负载小的其他控制器上。最后与简单平均法和最近邻法做了比较，仿真实验结果表明，PSVD算法预测性能的准确性要优于简单平均法和最近邻法，而且可以更好地应对突发性负载，显著提高网络的稳定性。