基于Holt 双参数指数平滑法的SDN 交换机流表超时优化策略*

王宣立，黄道颖*，张安琳，董 帅，刘江豪

（1.郑州轻工业大学计算机与通信工程学院，郑州 450000；2.郑州轻工业大学工程训练中心，郑州 450000）

0 引言

软件定义网络（Software Defined Network，SDN）［1］作为一种集中控制的网络架构，它将控制与转发分离，将所有的控制功能交给控制器，可以让用户在控制器上根据不同功能的应用程序进行软件编程，因此，其特别适用于计算机军用网络未来架构。通过在军用网络中实现SDN 控制器的功能，达到对网络节点全方位的掌控，能更好地适应战场变化，满足现代体系作战网络中对各联网平台的高效受控传输要求。目前SDN 主要使用OpenFlow 作为控制器与交换机之间的标准交互协议，在SDN 中，“流”被定义为具有一系列相同特征的数据包集合，如具有相同的目的MAC 地址、目的IP 地址等，而“流”的转发则依靠OpenFlow 交换机中的流表来完成。为了实现对流不同粒度的匹配，OpenFlow 允许流表项匹配域中存在任意（ANY）字段，这使得OpenFlow 交换机采用三态内容寻址存储器（Ternary Content Addressable Memory，TCAM）来保存控制器下发的流表项，但TCAM 是一种昂贵且功耗高的存储设备，且随着OpenFlow 的发展，每条流表项的匹配字段达到15 个元组、356 位，这使得目前大部分的OpenFlow交换机仅能支持10 K～40 K 条流表规则，而这一数量远远小于网络正常工作所需要的数量［2］，且在网络流量高峰时期，大量的数据包导致流表项的突发性增多，使TCAM 内存不足的问题更加突显，这将导致严重的丢包和网络延迟问题。OpenFlow 面临着严重的流表容量受限的问题，所以流表优化就成了一个研究热点。

当前OpenFlow 空间流表优化主要有3 种方式:1）基于流表资源复用的优化方式，计算流表项间的关联度，将具有相同匹配域的流表项进行压缩，增加流表空间中的可用流表项数量［3-4］，但压缩算法会影响对流细粒度的管理，且压缩算法较为复杂，会占用大量控制器计算资源；2）基于多级流表的优化方式，OpenFlow1.1 版本提出了多级流表的流表结构，多级流表技术扩大了存储空间，但仍可以通过优化流表之间的映射关系，提高资源使用效率［5-6］；3）基于流表超时时间的方式，每条流表项在被下发时，会被配置匹配域、计数器、超时时间等信息，通过调整流表超时时间，实现无效流表项的清除与有效流表项安装的动态平衡，实现对TCAM 的充分使用。相较前两种方式，基于流表超时时间的优化方式，更具有可操作性和扩展性，现有的研究成果仍有可供改进之处，所以本文通过对流表超时时间进行优化，实现对数据平面转发能力的优化。

现有基于流表超时时间优化方式中，文献［7］通过分析OpenFlow 的流表超时机制，计算流表项的空闲资源代价，提出了一种动态流表项和静态流表项相互转化的机制，提高了控制器和交换机的流表资源利用率，但该方法未考虑实际的网络负载情况；文献［8］在控制器中添加缓存模块，使用基于历史信息的算法来预测合适的有效时间，并结合流表负载情况，避免流表空间溢出；文献［9］采用统计分析新增流表项的数量，使用了二次指数平滑法预测下一个取样周期的流表增量趋势，动态调整流表中流表项的超时时间，以达到提高流表空间利用率的目的，但没有考虑特定流表项的使用频率问题，容易清除一些重要的流表项；文献［10］采用ARMA 模型对交换机中的流表项进行预测，并通过改进现有的LRU 算法，提升了交换机中有效流表的数量，但ARMA 算法较为复杂，相较于其他的算法占用更多的控制器资源；文献［11］结合控制器资源、OpenFlow交换机资源以及链路负载情况等信息，通过代价函数调整流表项的超时时间，但该方法需综合多项信息，计算较为复杂，且在收集控制器信息时会产生大量的交互信息，会占用部分安全通道的资源。

本文通过Holt 双参数指数平滑法的改进算法，预测OpenFlow 交换机中流表数目的变化情况，以调整流表项超时时间的方式，实现交换机TCAM 的有效利用，且该算法相较于二次指数平滑法以及ARMA 算法具有实现简单、计算量少以及控制器资源占用较少的特点，在调整流表超时时间的过程中，无需频繁地与控制器进行交互。

1 基于Holt 双参数指数平滑法的流表超时更新策略

1.1 OpenFlow 流表更新机制

当一条新的数据流到达交换机中，若无可以匹配的流表项，则由控制器通过Packet-in 消息将数据包的包头信息封装后上传给控制器，由控制器计算转发路径并通过Flow-Mod 消息下发给交换机，从而实现数据包的转发。

OpenFlow 的流表更新机制为控制器在下发流表项时会配置流表项的失效时间来清除流表，流表项的失效时间有Hard-timeout 和Idle-timeout 两个参数，前者表示经过该段时间后将流表项从流表中删除；后者表示在该时间内若无数据流匹配，则清除该条流表项，若匹配成功，则延长该流表的失效时间。设置Hard-timeout 的方式将超时时间设为一个固定值，这会导致某些使用频率较高的流表项在达到超时时间后被删除，从而触发Packet-in 消息，请求再次下发流表项，从而增加控制器的负担。所以，控制器通常为流表项配置Idle-timeout，这样使用率较高的流表项就不会被删除。当流表空间满载时，控制器会通过FIFO 算法和LRU 算法清除流表项，这两种算法实现简单，但都是基于局部特性，且有很大的随机性，容易删除一些重要的流表项，从而导致控制器需要重新计算新流的路径，进而导致占用控制器的资源。

本文通过采集OpenFlow 交换机流表项新增数目，预测接下来一个或多个周期内流表空间的新增流表项数目，将流表项新增数目的预测转为一个时间序列预测问题，通过适用于时间序列预测的算法，调整流表超时时间，达到提高OpenFlow 交换机利用率的效果。

1.2 预测方法分析

指数平滑法是一种简单易用的预测方法，在各种基于时态的时间序列预测场景中有着广泛的应用，它以时间序列的历史数据为参考，通过对时间序列的历史值赋予不同的权重，对时间序列未来的趋势进行预测。在应用中，若是对时间序列进行长期预测，通常会对权重值赋予较小的值，这样可以获得较好的平滑效果，但若要能够对时间序列发生波动时进行及时响应，则采用“重近轻远”的思想，对距离预测值较近的观察值赋予较大的权重，距离预测值较远的观察值权重会较小。

T 为预测期数，T 越大，预测的期数越多。

二次指数平滑值是建立在一次指数平滑值基础上的，将一次指数平滑公式递推后可得到如下的展开式:

引入自适应平滑参数后，Holt 双参数指数平滑法在保留了指数平滑法“重近轻远”思想的同时，解决了指数平滑法初值难以确定、平滑参数无法自适应调整的问题，且无需对时间序列进行二次平滑，充分使用时间序列自身的信息，相较于二次指数平滑法，Holt 双参数指数平滑法更适用于时间序列的预测。

1.3 基于Holt 双参数指数平滑法的流表超时更新策略

OpenFlow 交换机流表空间大小可用流表项的数量反应，总的流表空间由已存在的流表项和剩余流表空间组成，它们之间的关系可用下式表示:

其中，Nmax表示总的流表空间，Nactive表示当前流表空间中存活的流表项数量，Nempty表示空余空间可容纳流表项数量。

本文的主要目的是为了解决网络流量高峰时期固定流表超时时间机制下无效流表项占用大量流表空间的问题，通过新增流表项数量的变化，反映网络流量高峰时期网络流量的变化。

综上所述，给出基于Holt 双参数指数平滑法的流表超时时间更新策略的流程图，如图1 所示。本流表超时时间更新策略周期性地采集交换机流表项新增数目构建时间序列X，使用Holt 双参数指数平滑法预测下一个周期的新增流表项数量，倘若剩余流表空间可以满足预测新增流表项的需要，则不对现有流表项的超时时间进行调整；但若剩余流表空间不能够满足新增流表项的需要，则选取足够数目的、流表项Idle-age 最大的流表项对其进行超时时间的调整，调整后若不能使无效流表项的删除与新增流表项达到动态平衡，则继续构建流表新增数目的时间序列，预测新增流表项与交换机流表空间的需求关系，调整流表项的超时时间。

根据流程图，给出基于Holt 双参数指数平滑法的流表超时时间更新策略的伪代码如下所示:

图1 基于Holt 双参数指数平滑法的流表超时更新策略流程图

本文提出的流表超时时间更新策略，将Open-Flow 交换机负载状态的变化转化为时间序列预测问题，根据预测结果调整流表超时时间，以实现交换机有限流表空间的高效利用。相较于直接删除流表项或对所有的流表项进行超时时间调整的方法，本文借鉴LRU 算法的思想，通过流表项的统计信息Idle-age，找出未到达流表超时时间的、最久未匹配过的流表项，对其进行调整，减少了OpenFlow 交换机的流表空间震荡，也在一定程度上减少OpenFlow交换机请求流表项下发消息的数目。

2 实验与仿真分析

为验证本文的算法，本文通过R 语言搭建模型，数据集选择真实的网络数据流，从中随机选取5 000 类数据流，交换机的流表容量被设置为500条，每秒到达交换机中的数据流的最大数量为500条，控制器的性能设置为30 个/s，缓存10 组。

本文将从流表空间利用率、流表适配率和数据转发成功率3 个方面检验本机制效果，并与文献［9］提出的二次指数平滑法（以下用SESM 表示）以及原有的机制（以下用Fixed 表示）进行对比。

图2 反映随着数据流流速改变交换机中活动流表项的数目，原有的方法会造成超过1/3 的空间得不到有效利用，本文提出的方法及基于二次指数平滑法的流表超时时间动态调整方法，都可以使交换机的内存空间得到充分使用。并且由于本文通过读取Idle-age 对部分流表项进行调整，使更多的流获得更久的存活时间，从而保证足够数量的流表项用于保证数据包的转发。

图2 不同数据流速率下3 种机制的流表空间利用率

流表适配率反映数据流与交换机中存在的流表匹配成功的概率。从图3 可以看出，因为在最开始的时候，控制器根据交换机上传的Packet-in 消息计算完转发路径后下发流表项给控制器，这时大多数流表项都可以得到匹配，所以3 种方法都有较好的适配效果，但随着数据流速率的增大，固定Idle-timeout 超时机制因为无效流表项占用了部分空间，导致了新的有效流表项无法安装，从而影响了匹配效果。本方法和SESM 方法都可以通过动态调整流表项超时时间的方式调整流表项的生存时间，获得了较好的适配效果。但从图中可以看到本方法的表现更好。

图3 不同数据流速率下3 种机制的流表适配率

图4 表示3 种机制在不同数据流速率下的数据转发成功率。从曲线可知，在最初交换机流表空间未满时，大多数数据包都可以得到顺利转发，但随着时间的推移，3 种方法转发成功率都有下降，原有的机制在网络流量高并发时因无法及时安装新的流表项，导致了丢包现象的产生，降低了转发成功率。本文提出的方法相较于基于二次指数平滑法的流表超时时间，更能对流量的变化作出及时响应，从而获得了更好的效果。

图4 不同数据流速率下3 种机制的数据包转发成功率

3 结论

针对控制器设定固定值作为流表项的停滞超时时间造成交换机流表空间资源浪费及影响网络性能的问题，本文通过引入自适应权重参数的Holt双参数指数平滑法预测下一个周期流表项新增数量，根据交换机负载情况调整现有流表项的存活时间，提高了流表项的适配率和数据包的转发效率，使交换机的资源得到更加充分的利用。但本方法并未对流表项进行分类，有些业务的数据流可能存在较大的数据包时间间隔，这可能会导致其被频繁删除，从而影响该类业务的服务质量，因此，本方法还存在可改进之处。