OpenFlow交换机流表溢出缓解技术研究综述

谢升旭 邢长友 张国敏 宋丽华 胡谷雨

(陆军工程大学指挥控制工程学院 南京 210007)

自从Mckeown等人[1]提出后，软件定义网络(soft-ware defined networking， SDN)技术得到了学术界和产业界的广泛关注，其架构也在不断地发展完善.近些年来，随着云环境的大量部署使用，SDN的热度进一步增加，并出现了许多较为成熟的商业应用，如谷歌的B4项目[2]，Facebook的开放计算项目(open compute project， OCP)[3]等.得益于其控制平面与数据平面相分离的特点，SDN技术相较于传统网络的发展更加具有优势.然而，作为一种新兴的网络架构，SDN在带来便利性的同时也引入了新的安全问题[4-5].数据平面[6]、安全通道[7]、控制平面[8]等都存在着大量的安全隐患.在各类安全威胁中，交换机的流表溢出问题是SDN面临的一个重要挑战.

现阶段，网络管理和流量调度越来越趋向于细粒度化，同时，SDN大量部署于数据中心网络和核心网中[9]，这势必会导致交换机中的流表项数目大幅度地增加.然而SDN硬件交换机受限于有限的流表资源，很容易出现流表溢出问题，使得网络吞吐量、时延等受到严重影响.本文通过深入分析SDN环境中流表溢出问题，详细介绍了流表溢出造成的影响以及目前缓解流表溢出的相关技术，为有效降低该问题对网络性能的影响提供支持.

1 背 景

本节主要介绍SDN与OpenFlow协议、三态内容寻址存储器(ternary content addressable memory， TCAM)的特点及其局限性.同时，通过实验验证并分析流表溢出对SDN网络性能的影响.

1.1 SDN与OpenFlow协议

在当今网络快速发展的时代，网络规模不断扩大，网络复杂度也持续增加.SDN作为一种全新的网络架构被提出，用以解决传统网络中存在的网络协议多且实现复杂、流管理灵活度不足以及网络新业务部署周期长等问题.

SDN被定义为一种转发与控制分离、软件可编程的新型网络体系架构.它将传统控制平面功能从各个网络节点中抽象出来，将原来分布式控制的网络架构重构为集中控制的网络架构.其基本架构如图1所示，主要包含3个平面和2个接口：应用平面(application plane)、控制平面(control plane)、数据平面(data plane)、北向接口(northbound interface)以及南向接口(southbound interface).

Fig. 1 Basic architecture of SDN图1 SDN的基本架构

在SDN架构中，网络用户可以通过编程的方式制定网络管理策略应用，并部署到SDN应用平面.这些SDN应用通过北向接口将网络行为请求交给控制平面.SDN控制器(SDN controller)在接收到SDN应用的请求后，通过南向接口交给数据平面中的网元(network element)，使得网元能够正确地处理和转发数据.同时，控制平面为SDN应用提供底层网络的抽象模型，包含全局的网络拓扑视图状态以及网元连接事件等.

在众多南向接口协议中，OpenFlow已经成为既定的标准.OpenFlow作为一种通信协议，将对等的数据平面转发设备和SDN控制器连接起来，其架构如图2所示.在OpenFlow v1.3版本中，支持该协议的SDN交换机主要包含3个部分：组表(group table)、流水线(pipeline)以及安全通道(secure channel).其中流水线上的流表(flow table)可以看作为一组策略表项(即流表项)的集合，数据分组在流水线上的多张流表间跳转进行匹配；组表用来聚合具有相同指令的不同流表项以提高流表的资源利用率；而安全通道则是连接OpenFlow交换机与控制器的接口，用来保护两者之间的通信不受干扰.

Fig. 2 Architecture of OpenFlow v1.3图2 OpenFlow v1.3架构图

图3描述了基于OpenFlow的SDN环境下网络流的基本转变过程，Pkt0和Pkt1是同一条流(首部字段相同)的前2个数据包.当OpenFlow交换机S收到主机1发往主机2的新流的第1个数据包时，该流的处理过程如图3中点划线箭头所示.首先交换机S接收到该新流并进行匹配；在未匹配到相应流表项后，向控制器发送封装有该流首部信息的packet_in消息；控制器接收到packet_in消息后根据网络管理策略生成相应的流规则，并向交换机S发送flow_mod消息以下发该流规则对应的流表项；最后，交换机S根据该流表项对流进行转发等操作.而当交换机收到主机1发往主机2的一条旧流(指交换机中已经安装有对应的流表项)的数据分组时，该数据分组的转发过程如图3中虚线箭头所示.即交换机匹配到该分组对应的流表项，并根据该流表项的动作对分组进行转发等操作.

Fig. 3 Forwarding process of flow in SDN environment图3 网络流在SDN环境中转发过程

1.2 TCAM原理及其局限性

线性查找法(linear search, LS)、二叉树查找法(binary search tree， BST)、散列表(Hash table)查找等传统的表项查找方法都是基于静态随机存取存储器(static random access memory， SRAM)的软件查找方法，共同特点是查找速度慢.在这种背景下，基于硬件的TCAM查找方法被提出.在进行TCAM查找时，整个表项空间的所有数据在同一时刻被查询，查找速度不受表项空间数据大小影响，每个时钟周期可以完成一次查找.相较于典型的内存搜寻算法，TCAM电路的方式由于平行比对所有储存数据，从而有效缩短了搜寻的时间.

此外，与传统的基于内容寻址寄存器(content addressable memory, CAM)相比，TCAM在每个比特位上的状态不仅包含“0”和“1”，还有另一个由掩码来实现的“don’t care”状态.正是由于TCAM的第3种状态，使得其既能够进行精确匹配查找，又能够进行模糊匹配查找，因此被广泛应用于SDN硬件交换机中[10].

虽然TCAM在匹配能力上比较灵活高效，但相较于传统随机存取存储器(random access memory， RAM)，价格昂贵且耗电量大[11].这导致当前商用OpenFlow交换机只拥有几千至上万条流表项的空间[12]，在大规模网络中部署时SDN交换机容易出现流表溢出现象，进而对网络性能造成影响.目前网络安全服务链[13]、路由故障恢复[14]等典型SDN应用场景都会受到流表空间不足的影响.

1.3 流表溢出对网络性能的影响

为了进一步说明流表溢出对网络性能的影响，我们使用如图4(a)所示的网络拓扑，通过主机1至主机4相互之间发送流量造成流表空间溢出.同时，通过主机5和主机6互ping来验证流表溢出对网络性能的影响.控制器匹配五元组(源IP地址，源端口，目的IP地址，目的端口，协议),当流表溢出时，采取由控制器packet_in和packet_out机制转发未能匹配到流表项的新流.

图4(b)为实验结果，从图4(b)中实线可以看出，当流表未发生溢出时，ping时延几乎为0.而从图4(b)中虚线可以看出，当流表发生溢出时，ping时延始终在50 ms上下浮动.由此可知，当交换机流表发生溢出时，SDN网络性能将有所下降.

除上述处理机制外，在SDN硬件交换机发生流表溢出时，控制器也可以采取其他类型的策略，如直接丢弃新流，不下发对应流表项也不进行数据转发；或者删除已有流表项来为下发新的流表项腾出空间等.然而，这些方法都会对网络中的流量造成影响，使得网络性能下降.本文后续将着重分析目前有效缓解流表溢出而导致网络性能下降的方法.

2 面向正常网络流的流表溢出缓解机制

在部署SDN网络的域间骨干或大型数据中心网络中往往运行着庞大的流量，而OpenFlow交换机有限的流表空间很可能无法安装控制器下发的大量流表项条目数.尤其在出现短时间内突然有大量流经过网络的情况下，流表项更容易出现溢出问题.由于这些流都是网络中的合法流量，SDN网络必须高效地进行转发处理.对于该情况下的流表溢出缓解问题，研究人员主要从2个方面进行了考虑：1)优化交换机流表空间架构及利用率，以避免交换机频繁发生流表项溢出；2)当发生流表溢出时，设计合理的流表项替换算法，选择性地剔除旧的流表项，进而为新流表项的下发腾出空间.

2.1 交换机流表空间及利用率优化

2.1.1 流表空间架构优化

SDN硬件交换机流表溢出的根本原因在于受限的TCAM空间大小.因此，通过优化交换机的流表空间，有助于提高支持流表项数量的上限.研究人员提出了一种结合SRAM的串行多级流表架构[15].如图5所示，该架构在使用TCAM实现流表的基础上，通过在TCAM尾部增加SRAM，以串行的方式使流表空间得到大大增加.使用该流表架构的交换机在处理到达的新流时，首先在TCAM流表中查找匹配，若没有对应匹配流表项，则进一步在SRAM的流表中查找.这种串行架构的好处在于，当流量较小时，能优先使用TCAM来快速查找，使流表空间具有很好的伸缩性.

Fig. 5 Multi-level flow table architecture combining TCAM and SRAM图5 结合TCAM和SRAM的多级流表架构

然而，在该串行架构中，当流数量较多的情况下，平均查表速度将显著下降.与串行架构不同的是，一种利用TCAM与RAM构造的双流表空间并行架构CacheFlow被提了出来[16].如图6所示，该架构基于网络流量往往遵循Zipf分布的特点(即绝大多数流量与相对较少的规则匹配)[17]，将最常见流的规则存储在容量较小的TCAM中以达到快速查找、匹配、更新流规则，而将其余的流规则存储在使用RAM的软件交换机(硬件交换机中的一部分)中.存储在TCAM中的流规则相较于RAM中的流规则具有更高的优先级，能优先被匹配.

Fig. 6 CacheFlow architecture diagram图6 CacheFlow架构图

由于CacheFlow没有考虑到在流表溢出时对流表项存储位置的处理，一种新的MMS(memory management system)架构被提出[18].此外，与Cache-Flow使用位于SDN交换机上虚拟内存机制不同的是，MMS使用的是控制器上的RAM.MMS通过Swap out的方式在流表空间溢出时将最新被匹配了的流表项置换到控制器上的RAM中以及通过Swap in的方式将需要再次匹配的流表项重新安装在交换机的TCAM中.MMS在有效地扩大流表空间的同时，提高了TCAM流表空间的利用率，但平均查表速度值得通过实验进行进一步分析.

2.1.2 流表项匹配规则优化

对于OpenFlow交换机来说，流表溢出直接原因在于控制器下发的流表项超过了交换机所能支持的上限.因此，通过对流表项匹配规则的优化，能够起到减少下发流表项数量的作用.

OpenFlow v1.3作为重要的一个稳定版本，在设计架构上相较于v1.0版本增加了多级流表(multiple flow tables， MFT)的结构[19].MFT在一定程度上减轻了单一流表臃肿的问题，同时也为流表管理带来了新的途径.Agg-Extable作为一种多级流表管理方法，能在一定程度上减少流表中流表项数量[20].该方法主要基于2个算法：1)利用剪枝算法剪去流表中的冗余项；2)基于TCAM任意掩码，利用Quine-McCluskey算法定期聚合多级流表中具有相同动作(action)的流表项.如图7所示，流表项E1，E2和E4，E5被聚合的同时，掩码位也进行了调整.与之相类似的工作包括FTRS机制，通过聚合流表项的相同action和匹配域中相同的地址来节省流表空间[21].同时，在SDN网络中如何快速进行流表聚合[22-23]以及如何确保流表项聚合时保证流表项的依赖[24]都被广泛的研究.

Fig. 7 Example of aggregation of flow entries based on mask图7 基于掩码聚合流表项的示例

相较于流表的管理，Compact TCAM方法在保持SDN交换机对流的动态处理等特性的情况下，能够通过改变流表项结构而优化流表空间使用[25].如图8所示，该方法对流的转发主要分为3步：首先，当流F1:P1到达入口交换机Sin时，控制器根据流的首部信息生成一个特定的FLOW-ID并存储在控制器的FLOW-ID Table中，然后用FLOW-ID替换该流的首部信息进行转发；其次，对处在中间链路上的交换机Smid下发匹配域为FLOW-ID的流表项，对流进行处理；最后在出口交换机Sout处，将FLOW-ID换回该流原来的首部信息.由于FLOW-ID使用比原始流表项匹配域比特数更短的标记来标识流，因此大大提高了TCAM的利用率.文献[26]也采用了类似在边缘交换机上对流首部字段进行改变的思想，提出了一种按需目标地址转换和源端口转换的机制.它基于地址修改和端口重写，主动创造更多可以聚合的流表项.

Fig. 8 Compact TCAM method for new flow processing图8 Compact TCAM方法对新流处理的流程

此外，Palette方案在保留SDN原有整体语义的情况下，根据匹配域掩码将流表分解为多个子表并分布式地部署在网络的不同位置上，同时保证每条流在路径中对每种类型的子表至少能匹配一次[27]，如图9所示.Palette方案能够平衡跨网络的流表大小，并在不同连接之间共享资源，进而达到降低流表项数量的作用.文献[28]则提出了一种针对异构流表(不同的控制器应用程序会有不同的流策略，导致所有流的流规则集不尽相同)的流规则划分和分配算法，同时保证了语义不变.SA(sub-table allocation)和SSP(size-balancing sub-table partition)算法，则被用于平衡子表以及减少规则开销[29].

Fig. 9 Flow table separation deployment图9 流表分解部署

2.1.3 流表项超时时间优化

为了能够使交换机主动且适时地删除流表项，OpenFlow协议规定了每条流表项都包含一个超时时间(timeouts)组件，用来指明交换机中的流表项在过期之前的最大生存时间量以及最长空闲时间量.控制器需要在向交换机安装流表项时设置超时时间，包含2个值：hard_timeout和idle_timeout.hard_timeout表示流表项自安装时起至该时间结束时，交换机会主动删除该流表项.idle_timeout表示流表项在匹配到数据包后的这段时间内如果未匹配到后续数据包，则会被交换机删除.

超时时间设置一般分为如表1所示的4种情况，其中a，b为正常数.当hard_timeout和idle_timeout都设置为0时，该流表项不会因超时而删除；而当hard_timeout和idle_timeout其中一个设置为0另一个设置为正常数时，该流表项的生存时间取决于非零项超时时间；若2个超时时间都设置为正常数时，该流表项的生存时间取决于2个超时时间谁先到期.

Table 1 4 Types of Timeout of Flow Entries表1 4种流表项超时时间设置 s

由于超时时间设置的长短决定了流表项在交换机中存储的时间，因此，过长会降低流表利用率，过短又会因频繁的packet_in事件导致控制器-交换机之间的交互增加，如图10所示.此外，较长的超时时间设置将更容易导致流表项溢出[30].一种简单的方法是在P4交换机上，通过识别TCP数据包的FIN标记位来判断TCP连接的最后一个数据包，进而在最后一个数据包得到转发后，将相应的流表项删除以减少无效时间，从而提高流表利用率[31].

Fig. 10 Impact of timeout configuration图10 超时时间配置影响示意图

在智能动态优化流表项超时时间设置方面，HQTimer机制实现了为不同的流规则分配不同的超时时间[32].该机制包含2个部分：混合超时时间机制和基于Q-learning的适应逻辑.其中混合超时时间机制负责流表项的下发和删除，而基于Q-learning的适应逻辑负责超时时间的动态决策.HQTimer的实现包含3个模块：超时决策模块、流规则下发模块、流规则删除模块.超时决策模块实现了基于Q-learning的适应逻辑，以流规则下发模块提供的table-miss规则作为输入，通过运行神经网络，为table-miss规则获取一个适当的超时时间；同时，以流规则删除模块提供的已删除的流规则信息来计算奖励，在此基础上对模型进行训练，该机制的具体实现如图11所示.文献[33]则基于Markov模型推测流表项的到期时间，并通过超时时间设置使该流表项在相同的时间内删除.

Fig. 11 HQTimer architecture diagram and Q-learning logic图11 HQTimer架构图和Q-learning逻辑

虽然智能预测算法精确度相对较高，但设计复杂度以及对控制器性能影响都比较大.因此，一些较为简单的启发式方法也被用来动态地优化流表项的超时时间.基于网络中99%的流都是短流(活跃时间不超过0.4 s)这一特点[34]，一种动态超时机制(dynamic hybrid timeout method， DHTM)被设计出来[35].DHTM包含2个方法：动态Hard Timeout方法和动态Idle Timeout方法.默认使用动态Hard Timeout方法，而当不满足：1)流表空间利用率超过90%；2)没有足够的流历史信息；3)平均持续时间小于2 s；4)已经分类为短流或者非频繁流这4条件之一时，则使用动态Idle Timeout方法.2个方法设置的动态时间都在基于最小时间(1 s和2 s)的情况下，依据后续流的到达情况以1 s为步进增加或减少超时时间.

IHTA(dynamic Idle-Hard Timeout allocation)算法通过分析分组到达时间的分布也得出了以1 s为初始idle_timeout值[36].不同的是，IHTA对2个超时时间的动态调整考虑了流表空间利用率同时设置了最大超时时间.类似的工作还有，自适应硬超时的方法(adaptive Hard Timeout method， AHTM)[37]以及根据可预测流和不可预测流来分配不同的硬超时时间[38].

与预测流实际生存时间来动态配置流表项超时时间不同的是，根据网络负载变化情况来动态配置流表项的超时时间.一种是通过预测下一时刻新增流表项数量，再结合网络当前负载情况，对流表项的超时时间进行动态优化配置，如利用动态指数平滑(DES)模型进行预测的DTO算法[39]以及使用AR进行预测的方法[40]等.另一种则是依据交换机流表使用率变化情况来动态的调整空闲超时时间[41].

2.1.4 基于网络流路径优化的交换机流表均衡

网络一般依赖于严格的路由策略(比如最短路径路由)，这会使网络中的部分链路成为核心链路，而核心链路上的交换机因流量汇聚导致流表空间使用率大大增加.相反，不依赖于严格的路由策略可以更好地利用网络容量，同时能够减少带宽浪费和拥塞事件[2].因此，对网络流路径优化可以在一定程度上缓解流表溢出问题.目前该研究主要分为2类，即基于全网流的路径优化和基于核心节点流的重定向.

1) 基于全网流的路径优化

如图12所示，1个网络共有8个交换机、2个出口链路(南北)和2个入口链路(东西).当A，B这2个流需要到北向出口而其他流需要到南向出口时，3个子图分别代表了3种路由策略下的流表项数量情况.图12(a)使用最短路径路由策略，在网络中共安装了15条流表项.图12(b)则使用最小化流表项数量策略，共安装了9条流表项，但带来的是A，B流的路由跳数增加.图12(c)则表示在每个交换机仅仅只有2个流表项空间大小的约束下，网络仍能对流进行路由转发.由此可以看出，在交换机流表空间大小的约束条件下，可以通过网络流路径优化来减少交换机中流表项数量.

Fig. 12 Example of the routing policy图12 路由策略示意图

基于这种全网流的路径优化思想，软件定义自适应路由(software-defined adaptive routing， STAR)策略利用SDN具有全网拓扑视图以及灵活的网络控制特性对网络流量进行路由规划[42].该策略通过全网所有SDN交换机流表利用率的实时检测，对于入网的新流根据交换机流表利用率情况选择合适的路径通过网络，以避免因流表溢出带来的网络性能下降.而多项式时间的启发式算法OFFICER被提出用来找出不同的路径以满足在不显著增加路径长度的情况下提升网络流的承载能力[43].此外，文献[44]提出的“big switch”概念，将全局的高级策略映射到网络中每个交换机的等价低级流规则集，来对交换机的流表资源进行整体分配.

然而，在结合路径优化和流表项聚合问题上，由于采取去中心化路由(decentralized routing， DR)(DR表示路由分布在整个网络中，且大多数路由经过的链路不重合)可以实现流表均衡，使平均时延最小化，但不利于流表项的聚合.而采取中心化路由(centralized routing， CR)(CR表示路由集中在网络中，大部分路由都经过相同的链路)会导致平均传输时延增加，但可以聚合更多的流表项以节省流表空间.对此，文献[45]提出了一种整型线性规划方案(integer linear program， ILP)，用来均衡传输时延和流表空间利用率，同时提出快速启发式ORWFA算法来实现最优折中.

2) 基于核心节点流的重定向

在网络中，流表溢出大部分时间都发生在部分核心节点上，因此解决核心节点上交换机流表空间的利用问题不失为一种有效的缓解方法.FTS架构的提出可以用来缓解网络中部分交换机流表溢出问题[46-47].该架构针对流分布不均匀的现象，将流表负载过重的交换机中触发table-miss事件的流(新流)随机转发给邻近负载较轻的交换机进行精确匹配处理.如图13所示，图13(a)展示了经典架构下当S2交换机流表空间已满时对新流的处理情况，图13(b)则展示了FTS架构处理情况.在经典架构下，当一条新流到达流表空间已满的S2交换机，packet_in消息将触发控制器删除交换机已有的流表项进而下发针对该流的流表项，这会导致原本活跃的流的转发被迫中断.而在FTS架构下，当新流到达S2交换机，如果流表没有溢出，则转发至控制器；若流表溢出则将新流随机转发至源端口以外的某一端口.由此可见，FTS在交换机发生流表溢出的情况下保证了原有活跃流的通信质量.

Fig. 13 Normal architecture and FTS architecture图13 经典架构和FTS架构

在FTS架构的基础上，采用路由松弛策略可以最大化流量效率[48].即在流表空间已满的交换机中，保留大流的流表项，而将小流通过默认(default)流表项转发至其他交换机进行精确匹配.

虽然将流从饱和的交换机中重定向至有足够空余流表空间的空闲交换机可以有效地缓解流表溢出问题.但是，该方法的性能依赖于空闲资源的数量，当没有足够的空闲交换机来满足大量流时，容易导致全网交换机受流表溢出的影响.

2.2 流表项替换策略优化

在不改变网络其他配置的情况下，为了缓解因交换机流表空间缓存溢出而导致网络性能下降的问题，研究人员提出了多种流表项替换策略，即按照特定的规则删除交换机中已有流表项，以便为新流表项的下发腾出空间.

2.2.1 被动替换策略

被动替换策略的核心思想在于，只有在交换机流表处于饱和状态且发生新流到达事件时，控制器才会选择删除一条已有流表项并为该新流下发对应的流表项.最典型的工作是OpenFlow协议1.4版本[49]增加了对流表满载情况的处理机制，控制器对下发的流表项设置不同的重要度(important)值，进而允许OpenFlow交换机在流表发生溢出时可以删除那些重要度值较低的流表项.

典型的流表项删除策略，包括最近最少使用(least recently used, LRU)、先进先出(first in first out, FIFO)和随机(random)[50].研究发现FIFO删除策略比LRU要差，但优于随机策略[51].

在流表溢出时，为了更好地选择出最适合删除的流表项，结合近些年较为热门的机器学习思想，一种基于机器学习的剔除方法(machine learning based eviction approach， MLBEA)被用来找出并剔除不活跃的流表项[52].该方法以五元组(源IP地址，源端口，目的IP地址，目的端口，协议)定义流，通过数据流的协议、流表项未匹配时间长度、平均包间隔以及最后N个数据包的长度4个特征组成的向量，使用UNIV，UNIBS等网络数据集进行离线训练随机森林分类器，并将训练结果通过在线仿真的方式进行验证.结果显示，基于机器学习选择合适流表项进行删除的方法要远好于LRU方法.

与MLBEA高复杂度相比，短流优先策略(short flow first， SFF)要简单得多[53].SFF动态标记流表项是长流还是短流，在流表发生溢出时，选择短流表项进行删除替换，并使长流能够提供更长时间的匹配.具体动态标记的方法如图14所示.①首先将到达交换机的新流所对应的流表项标记为短流.②如果该流表项在被删除之前与第2个到达的包匹配，则将该流表项标记为长流，同时设置最大等待时间(maximum waiting time， MWT)，其中t为2次匹配的时间间隔，α为权重因子.③在最大等待时间内若没有再匹配到数据包，则将该流表项重新标记为短流.④被重新标记为短流后，如果再次匹配到数据包，则重新将流表项标记为长流，同时更新匹配时间为t′.实验显示，SFF策略比FIFO，LRU的替换删除策略都要好.

Fig. 14 Flow identification in SFF scheme图14 短流优先策略中流的鉴定方法

2.2.2 主动替换策略

被动替换策略具有实现简单等优点，但由于流表项的替换发生在交换机流表溢出时，此时需要消耗大量时间来找出相应需要删除的流表项，因此会大大增加新流的处理时延，导致网络性能不太理想[54].为了解决溢出时替换造成的时延增大问题，需在流表项将要发生溢出之前，通过流的筛选策略，提前剔除流表空间中的一部分流表项，以供即将到达的新流使用.一般分为2种方式：

1) 设定流表空间使用阈值

即当流表空间使用率超过一定阈值时，删除特定流表项.如一种基于隐Markov模型(hidden Markov model, HMM)的流表项主动剔除方案，在流表空间超过阈值时通过HMM选出最低匹配概率的流表项并删除，直到流表利用率下降到阈值以下[55].此外，研究发现阈值大小的设定会对网络性能带来一定的影响.当阈值设置较低时，流表可用空间增加，但会导致频繁地用新流表项替换旧的流表项而带来额外的开销，因此阈值可以与数据包的到达速率成反比；同样的，在一段时间内到达的数据包数量增加是因为网络中主机增加导致，因此阈值可以与主机数量成反比[56].

2) 对流表溢出进行预测

即当预测到流表即将要发生溢出时，删除特定流表项.如，基于流表项溢出预测的CPD架构[57].如图15所示，该架构包含3个模块：流表状态采集模块(flow table state collection)、新流预测模块(predict module)、流表项删除模块(delete module).流表状态采集模块负责采集各个周期内流表空间使用情况，包括流表空间总大小和剩余流表空间大小.新流预测模块负责使用泰勒级数通过各周期内统计的packet_in数量预测下一个采样周期新流到达的数量.流表项删除模块则是根据预测新流数量与流表空间使用情况判断下一周期内是否会出现流表溢出问题，若流表会出现溢出，则删除最不可能再被匹配到的流表项.

Fig. 15 The architecture of CPD图15 CPD架构示意图

3 面向攻击行为的流表溢出缓解机制

由于流表溢出对网络性能会产生重要影响，因此越来越多的研究开始关注于流表溢出攻击及其防御策略.网络攻击者可以通过网络探测手段获取SDN交换机的相关配置、控制器网络管理策略以及网络拓扑等信息.基于这些信息，攻击者可以设计发起针对SDN交换机的流表溢出攻击.从攻击流的角度区分，这类攻击主要分为2种形式：一般性攻击流和精心设计的低速率攻击流.与正常网络下的优化技术相比，针对流表溢出的攻击，必须能够有效地检测出攻击并进行遏制，否则即使再优的方案，攻击者也总能使流表空间被攻击流占满.本节将以流表溢出攻击为背景，首先介绍相关网络探测手段，进而分别介绍一般性攻击流和低速率攻击流情况下的缓解方案.

3.1 网络配置信息探测

在SDN网络环境中，网络配置信息探测一般分为2种方式：1)控制器感染，即攻击者通过病毒、SQL注入等形式获得SDN控制器的相关权限来获取相关配置信息；2)网络测量，即攻击者通过向网络中发送特定的探测流来获取相关配置信息.控制器作为SDN网络的核心部件，被感染则意味着攻击者可以获取网络的任意信息[58].相较于控制器感染，通过网络测量获取网络配置信息具有实现较为容易、不易被发现等优点，已经成为攻击者获取网络配置信息的主要手段.本节主要介绍通过网络测量的方法获取流表项生存时间配置、流规则配置、流表容量及其使用情况等信息.

3.1.1 流表项超时时间及流规则配置探测

若流表项超时时间设置较长，攻击者将有足够的时间通过恶意流量使交换机流表空间占满.因此，文献[59]研究了攻击者如何通过向网络发送构建的数据包，来探测控制器对流表项idle_timeout和hard_timeout的配置以及流规则配置情况.探测示意图如图16所示，由于新的数据流(控制器流规则下的不同流)在SDN网络中没有对应流表项，需要通过packet_in和flow_mod消息下发对应流表项，这就使得新流的往返时延(round-trip time， RTT)要远大于直接匹配到流表项的流.因此攻击者通过控制发送数据包的间隔以及每个数据包的RTT时间大小来判断超时时间设置，如图17所示.图18则给出了匹配域的掩码推测示例.

Fig. 16 The processing of probing timeout configuration图16 探测流表项超时时间配置示意图

Fig. 17 Inference of timeout period图17 超时时间推测示意图

Fig. 18 Inference of match field of flow entry图18 流表项匹配域掩码推测

3.1.2 流表容量及使用情况探测

交换机支持的最大流表项数量直接决定了攻击者短期内需要发送攻击流数量的下限，因此流表容量探测对于攻击者来说显得尤为重要.一种利用流RTT大小变化情况进行推测的方法，可以推断出在流表溢出时使用基于FIFO和LRU的流表删除规则的OpenFlow交换机的流表容量以及使用情况[60].图19给出了该方法基于FIFO的流表空间推测示意图，其中ABCD为流表空间的4种状态，菱形填充的小矩形为正常流占用的流表空间，斜线填充的小矩形为攻击者发送的探测数据流占用的流表空间，空白部分为剩余未使用的空间.探测分为3个步骤，首先在起始状态A的情况下，向网络中不断注入探测流到状态B；其次，当发现发送的新流的RTT增加时，说明控制器进行了流表项FIFO的删除动作，因此可以判断到达状态C，即流表空间已被占满；最后，随着探测流的不断注入，当有已经注入的流的后续包出现RTT突然增大时，说明到达状态D，即流表空间全部被探测流的流表项给占满.在整个探测过程中，攻击者始终记录着探测流的数量，因此在到达状态D时可以推断出流表空间大小，再结合状态C可以推断出流表空间的使用情况.

Fig. 19 Inference of flow table space based on FIFO图19 基于FIFO的流表空间推测示意图

3.2 一般性攻击

若攻击者需要消耗整个网络的流表资源而不是单个交换机的流表资源，则意味着它们必须提高攻击流的请求速度或延长攻击的持续时间，这2种方法通常代价都非常高.利用该攻击特点而设计出的基于QoS感知的缓解策略(即对等支持策略)可以有效地缓解这种类型的流表溢出攻击[61].该策略在交换机流表空间满状态时，通过向交换机下发带有通配符的流表项，引导流量到对等的路径上.因此该策略集成了整个SDN系统可用的空闲流表资源，能够在遭受流表溢出攻击时，使网络可以维持更长的时间以及更易检测流表溢出攻击.

此外，通过网络拓扑分析最有可能被攻击的目标交换机(中间节点交换机Smid)可以在保证检测精度的情况下提高检测效率.例如，文献[62]通过使用外部流消耗增长(growth of foreign flow consump-tion， GFFC)、流量偏差(deviation of amount， DFA)、流进入的共性(commonness of flow entry， CFE) 3个指标对攻击进行检测，并使用令牌桶模型(token bucket model， TBM)进行限速.对于检测出的攻击端，通过令牌桶限制控制器下发流表项的速度，以避免流表空间被占满.如图20所示，当Smid这个中间交换机通过3个指标检测出攻击端Sattack时，通过控制器中的令牌桶限制从Sattack到达的流的对应流表项的下发速度.

Fig. 20 Limit the speed of flow entries installation图20 限制流表项下发速度示意图

该缓解方法的不足在于，当网络中恶意用户的数据流不断增加，整个流表空间会被耗尽，使得正常用户的数据流可能会遭受流表不足的问题.为此，一种基于行为优先级感知的防御策略——FTGuard被设计提出[63].如图21所示，FTGuard架构中流量特征采集(traffic feature collection)模块用于采集数据信息，包括新流的到达频率、每个流的包数量，然后再通过评价分值计算(evaluation score calcu-lation)模块计算分值，最后通过优先级配置(priority encapsulation)模块依据分值对不同用户的流分配不同的优先级.当流表满时，优先级最低的流条目会被删除，为下发新流的流表项提供空间.

Fig. 21 The architecture of FTGuard图21 FTGuard架构示意图

此外，文献[64]分析了流表溢出攻击的2种攻击手段：控制器中恶意APP和网络数据包，并提出了基于事件处理的剔除模型.该模型实现了对每一个新的数据包的分析，并通过日志验证源地址，对于黑名单中的源地址，将删除超过一定流量阈值的流，以保证正常用户数据流的正常通信.

3.3 低速率攻击

相较于一般性的流表溢出攻击，低速率流表溢出攻击的攻击流是经攻击者精心策划过，即以最少的攻击流造成交换机流表溢出，相对于传统的攻击方式进一步增加了检测难度.

基于低速率拒绝服务攻击(low-rate denial-of-service， LDoS)特点以及OpenFlow流规则特性，研究人员提出了低速率流表溢出攻击机制(low-rate flow table overflow attack， LOFT)[59].攻击方式如图22所示，假设其中Pi表示第i条攻击流的数据包，idle_timeout为10 s，hard_timeout为15 s，交换机最多能够支持5条流表项.图22(a)中对于特定的idle_timeout设置，攻击者通过每隔2 s在idle_timeout内发送足够使交换机流表发生溢出的攻击流数量(图22中5条新流，分别为P0至P4)，这些流再以idle_timeout为周期进行发送，则会始终导致交换机流表空间处于溢出状态.图22(b)中，若同时设置了idle_timeout和hard_timeout，则攻击者可以在idle_timeout时间内发送足够的攻击流的同时以hard_timeout为周期，重复发送攻击流.对于该方式的攻击，作者提出了2种可行的防御方案：1)在数据流的头几个包的传递过程中加入适当的时间抖动，例如控制器在接收到packet_in消息后不立即为新流下发流表项；2)使用动态的超时时间值.

Fig. 22 Diagram of LDoS attack in two cases图22 2种情况下的LDoS攻击示意图

4 分析及研究展望

4.1 分 析

面对OpenFlow交换机流表溢出问题，虽然已经从流表空间架构、流表项匹配规则、流表项删除替换等众多方面进行研究，但都不可避免地对网络性能造成影响，或是对OpenFlow相关软硬件进行了修改，这在一定程度上削弱了SDN网络的能力.在此，本节对几类代表性的交换机流表溢出缓解方法进行比较分析.

由于不同的流表溢出缓解方法的效果评估方式具有差异性，例如有些使用网络数据集[49]，有些则使用自定义的仿真环境[36]等.因此，为了更加直观分析各流表溢出缓解方法的特点，我们从网络性能(通信时延、链路负载)、对交换机额外的修改、控制器模块、控制器负载影响、OpenFlow协议更改等多个方面做了统计，结果如表2所示(比较是在正常通信且流表未发生溢出的情况下进行的).

分析表2可以发现，流匹配规则优化中的流表聚合方法(Agg-Extable， FTRS)会因流表项匹配域字段的掩码位数增加而导致流管理精细度下降，而更改匹配字段(Compact TCAM， Palette)需要对OpenFlow协议规定的流表项匹配域进行修改；流路径优化机制中流的重路由实现方法(FTS，STAR)，都会因为流需要经过的链路数增加而导致网络时延增加同时平均链路负载加重；而在使用主动/被动流表项删除、针对流表溢出攻击的缓解机制实现中，因需要采集交换机中统计字段信息以判断流表空间是否将要溢出、流表项是否活跃以及网络中的流是否是攻击流，这些都会因为频繁数据请求增加控制器与交换机之间的通信量使得安全通道负载加重，从而影响SDN网络性能.

4.2 研究展望

随着SDN网络的大量应用部署以及网络流量不断增多的趋势，OpenFlow交换机流表溢出是一个迫切需要解决的问题.结合SDN特点、新技术发展以及应用部署等方面，未来工作可以考虑5个问题：

1) 应用感知的流表溢出缓解机制设计

SDN通过在集中的控制器上部署各种SDN应用程序来实现对网络的灵活管理.在流表溢出缓解机制的方案实现中，大多需要在SDN应用平面安装相应的SDN应用，以对数据平面的相关信息进行采集和实现相应的流表管理，如信息采集包括流表空间使用率[57]、流表项匹配信息[63]等，流表管理包括进行流表项的修改以实现流表项聚合[20]、流的重路由[47]、删除不活跃流表项[55]等.而SDN应用平面上安装流表溢出缓解应用时，需要考虑与其他各种SDN应用程序(如QoS、流量工程等)有无策略冲突.例如QoS应用将某流设定为高优先级，而流表溢出缓解应用判断其为不重要的流从而优先删除或重定向.在以后的工作中需要解决这类策略不一致性问题.

Table 2 Comparison of Flow Table Overflow Mitigation Methods表2 流表溢出缓解方法比较

2) 降低流表溢出缓解机制对网络的整体影响

已有的优化方案在实现过程中或多或少对SDN网络都有一定的影响，如通过流表项聚合减少流表空间占用的同时会使网络流管理的细粒度降低[20]、路由优化中的流重定向以均衡流表空间负载的同时增加了链路负载和时延[44]等.以后的研究中，可以综合考虑流管理细粒度、链路带宽、时延、安全通道负载等性能的影响，并结合多种机制提出新的缓解方案.在缓解OpenFlow交换机流表溢出问题的同时进一步降低对SDN网络整体性能的影响.

例如，从网络拓扑的角度出发，通常情况下，流表溢出发生在网络中的核心节点交换机上，因此研究网络中不同位置的交换机使用不同细粒度的流匹配规则，使网络既能保证相应流能够获得精确的统计信息，又能减轻核心节点交换机流表负载，同时不影响网络通信性能.

3) 运用新技术解决流表溢出问题

OpenFlow交换机容易发生流表溢出问题的根本原因在于其使用了TCAM从而导致流表空间严重不足.而若严格按照OpenFlow协议标准，流表的实现只能使用TCAM.因此，提高单位功耗单位价格的TCAM容量是一个值得研究的方向.

结合P4等技术的发展[65]，未来可以研究改进OpenFlow相关协议，例如在使用P4交换机时，增加交换机流表项主动删除判定条件以便及时删除无效流表项；增加交换机相关统计字段主动上报，以便分析相应流的特性，从而在进行流表优化的同时能够减少信息采集量.

此外，可以利用机器学习相关算法来应对流表溢出问题.在正常网络环境中，机器学习算法已经有了很好的应用，如通过强化学习算法判断流表项合适的超时时间值[32]、使用随机深林算法选出最不活跃的流表项进行删除[52]等.未来，可以研究智能算法用在流表空间溢出预测、流表空间溢出攻击流识别等其他领域.

4) 针对流表溢出的攻击行为进行研究

在正常网络中，流表空间可以通过优化方案提升承载能力，但在面向流表溢出攻击的情形下，优化方案只能治标不能治本.这部分的研究目前整体偏少.未来研究可以从2个方面出发：

首先，可以在网络配置信息探测层面进行阻断或提高探测难度.包括：①通过SDN网络拓扑混淆技术[66]，阻止攻击者通过分布式攻击流使某些核心节点交换机流表发生溢出；②使用动态随机的流表项超时时间以及不同粒度的流处理规则，可以有效增加攻击者发送针对性攻击流难度，从而使攻击更容易被检测出来；③由于流表容量和使用情况探测是基于RTT时间变化进行推测，因此可以对网络流适当增加时延抖动，以提升攻击者的分析难度.

其次，需要研究针对流表溢出的攻击流典型模式，尤其是低速率攻击.包括：①不同流占用多个流表项空间的情况，可以从流首部信息、流路径分布、新流到达速率等角度考虑；②相同流占用一个流表项空间的情况，可以从流的不同数据包大小分布、到达时间分布等角度考虑.这部分研究有利于在未来提出更有效的攻击检测方案，进而可以有效抑制攻击.

5) 在实际环境中部署进行效果验证

目前大多数流表溢出缓解机制都只停留在学术研究上，或者在实验仿真环境中进行了实现，如使用非SDN网络的流量数据集进行流匹配预测、使用Mininet工具生成仿真SDN环境等.这些实验方法虽然可以在理论上对方案效果进行验证，但在真实SDN网络环境中会存在各种难以预知的情况，尤其是在网络节点数量、网络流总量都十分巨大的场景下.如何保证所提出的流表溢出方案在真实SDN环境中能够平稳有效运行，在未来是值得验证评估的.

5 总 结

在SDN网络环境中，若OpenFlow交换机流表发生溢出，会导致网络时延、吞吐量等性能下降.而商用OpenFlow交换机考虑到TCAM的功耗、价格等原因，其能够支持的流表空间大小十分有限，导致OpenFlow交换机面临严重的流表溢出问题.同时，随着近些年来SDN的广泛部署，OpenFlow交换机流表溢出问题在TCAM架构、流表均衡、OpenFlow机制以及流表溢出攻击等方面得到广泛的研究.本文对本领域目前的相关工作进行了综述分析，对SDN环境下OpenFlow硬件交换机基于TCAM的流表溢出问题进行了深入探讨，并对下一步的研究趋势进行了展望，以期为解决交换机的流表溢出问题提供进一步的研究支撑.