软件定义网络中OpenFlow流表空间优化技术研究进展

唐菀，冯伟，杨喜敏，田野

(中南民族大学 计算机科学学院，武汉 430074)

当前，学术界和工业界对业务可扩展、网络资源虚拟化方面进行了大量研究，以期探寻能适应互联网技术及业务高速发展的网络架构.一种新的网络架构——软件定义网络(Software-Defined Networking，SDN)应运而生，SDN解耦网络的控制逻辑和数据转发逻辑，实现对网络的集中管控，利用可编程特性支持网络业务的创新[1-3].OpenFlow协议为SDN南向交互的事实通信标准，在支持OpenFlow协议的交换机中存储着一个或多个流表.每一个流表由多条表项组成，支持抽象转发和控制规范，实现数据流线性匹配.随着业务控制需求增加和网络规模扩大，流表空间有限的存储和有效利用等成为近些年基于OpenFlow的SDN网络关键问题，受到业界研究者广泛关注.希望本文的工作对SDN中流表存储优化的研究提供借鉴，能对流表一致性和流表安全性问题的解决有一定启发.

1 流表空间问题描述

SDN中的OpenFlow流表空间有限性存储和有效性管理问题，根据侧重点不同，可归纳为以下三方面：

(1)硬件电路复杂、价格不菲，且存储容量不足.OpenFlow交换机中存储流表的三态内容寻址寄存器(Ternary Content Addressable Memory, TCAM)硬件电路复杂，价格较为昂贵.此外，TCAM支持表项的并行查找，大量的匹配操作使得其功耗开销大，故商用SDN交换机中流表存储空间十分有限，如Pica8 P-3290交换机支持存储最大的TCAM表项数为2000条[4-6].

(2)大量业务和固有流表超时机制会带来大量流表存储的需求.SDN提供基于流的细粒度控制，一条数据流可能匹配多条细粒度表项，分组分类流表的规模不断扩大；OpenFlow固有的流表超时机制会导致大量无用表项滞留在交换机中，使交换机需存储的流表数显著增加.过多的流表存储导致流表更新的速度降低[1]，流表匹配率下降.

(3)流表表项匹配域扩大，结构越来越复杂.OpenFlow协议采用扁平化设计，囊括1～4层的协议信息，表项匹配域不断扩大，从OpenFlow1.0所支持的12个匹配字段，不断扩展到OpenFlow1.5的45个匹配字段.表项结构也变得越来越复杂[7,8]，对TCAM流表空间优化管理带来巨大挑战，大量多元匹配影响了流表查询效率，从而大大降低了OpenFlow流表空间有效利用率.

现有针对OpenFlow流表空间有限存储和有效利用问题的解决方案较为零散，本文通过对相关文献资料提出的研究方案进行定性分析，发现主要的研究工作大多是从硬件、软件或硬软件结合的3个角度来优化OpenFlow流表空间管理，因此将这些解决方案归纳为3类：

1)流表存储机制改进——结合网络通信和业务流的差异性，将流表匹配或业务处理作为约束和优化目标，改进流表存储体系，使流表表项不再单一存储在交换机硬件TCAM中，如CacheFlow[9]；

2)基于软件的流表扩容——通过算法或策略来聚合压缩流表表项，对流表实现软件上的间接扩容，如FFTA[10]；

3)流表超时时间管理——结合数据流量特征对流表超时时间进行管理，如时间序列预测[11]，通过优化流表固定的超时时间，依据流表超时机制来删除部分冗余或即将超时的表项.

针对流表空间的有限存储和有效利用，3类流表空间管理优化方案主要采用TCAM存储所需流表数量和流表线性查询效率两个评价指标.通过监测时间周期内活动表项(即流表中能和任意一条或多条数据流成功匹配的表项)数目，对TCAM存储空间利用率进行对比分析.线性查询效率是通过计算和统计时间周期内数据包的平均匹配耗时时间，对比验证优化方案的可行性和有效性.流表存储机制改进方案利用流表空间利用率作为反馈来评价此类存储机制改进的有效性，目标是减少TCAM中存储所需流表的数量.基于软件的流表扩容通过压缩或聚合流表表项来保证OpenFlow交换机存储空间的有效性，同时对流表查询效率进行验证.流表超时时间管理方案结合流量的差异性特征，通过优化流表超时时间及时或提前删除无效表项，使得流表存储空间利用率和匹配率两方面都有一定的提升[9-11].

2 流表存储机制改进

流表存储机制改进方案变更原有流表存储方式，对流表存储空间实现扩容.采用软硬件结合的方式将当前常用表项存储在交换机硬件TCAM中，而剩余表项存储在交换机或其他远程设备上.依据流表表项存放位置和管理方式的不同，可分为层级存储、分布存储和其他存储3种存储机制改进.

2.1 层级存储

层级存储将流表进行分类并存储在两类不同的存储介质中，将常用表项或粗粒度表项存放在TCAM中，不常用流表则存放在交换机缓存中.KATTA N等[9]提出CacheFlow机制，该机制依据流表间的依赖关系设计相应缓存算法，将大部分不常用的流表存储在CacheMaster结构中，OpenFlow交换机保存能匹配大部分数据包的少数流表.MARSCIO A等[12]提出内存交换机制，将TCAM和RAM(Random Access Memory)作为交换机内存存储系统，利用此两层存储介质分别存储最近最常匹配的流表和最少匹配的流表.

2.2 分布存储

分布存储将流表分散地存储在各网络设备中，如交换机或远程设备.依据数据流路由请求和资源利用情况，控制平面为交换机选择安装合适且适量的表项.MA H等设计的分布式存储DSFoF[13]将流表存放于多个较小容量的TCAM交换机之中.KANIZO Y等引入Palette[5]，基于图论原理及算法，将表项分割为多个均等的子表项并下发到传输路径的交换机中，同时保证了路由传输和最小化资源的利用.此类方法在保证SDN处理性能的前提下，采用流表分布存储，减少网络中单交换机所存储的最大流表数量.

2.3 其他存储方案

刘中金等[14]引入多级流表模型，计算单一流表的多元匹配域映射增益，并将匹配域提取出来在新一级流表中进行压缩存储，解决单一流表字段过长的问题.唐亚哲等[15]基于布隆过滤器(Bloom Filter)设计新型流表存储结构，使用一级TCAM流表连接多级Bloom Filter流表.传统的流表替换算法LRU(Least Recently Used)、FIFO、RANDOM等，分别采用不同的删除策略对流表表项进行删除[16]，其中LRU最常用，但其数据存储和查询维护复杂度较高.

YU M等通过DIFANE机制实现域内交换机集中存储方式[17].SDN控制器下发分区规则对网络区域进行划分，每个分区包含一个权威交换机和若干普通交换机，权威交换机具备部分控制功能.SDN控制器预先下发权威规则给权威交换机，当域内普通交换机接收到新的数据流时，会将其转向分区内的权威交换机，权威交换机依据权威规则直接对数据包执行转发策略而不发往原交换机.权威交换机集中存储流表，减少了非权威交换机存储的流表数量，并通过去除控制器处理时延提高数据包的处理效率.

流表存储体系改进方案变更了原有流表线性存储方式，提高了SDN网络流管理的适应性和稳定性.层级存储基于流表分类，通过有效的存储设计和管理，流表的查询效率有所提高.分布存储使得流表存储分布较为均衡，可减少单交换机中的流表数量，但在满足真实业务需求时，路由计算和表项刷新对于控制器负载提出较高要求.其他方案包括DIFANE和多级流表等，能一定程度上提高数据的处理效率，但此类方案对流表结构提升了管理难度，易导致流表性能降低.

3 基于软件的流表扩容

基于软件的流表扩容是通过聚合或压缩方式对流表结构、大小和数量进行缩减，实现流表的间接扩容，提高流表空间有效利用率.根据作用对象不同，主要分为表项聚合和表项压缩两大类.

表1 基于软件的流表扩容方案

如表1所示，表项聚合针对流表多元匹配字段，采用前缀聚合或非前缀聚合方法对表项进行聚合，改进表项复杂的数据结构，优化流表存储空间；表项压缩通过拆分流表，将表项分割为多个子表，减少每次匹配的匹配域的长度，另外一些研究[24,25]通过引入标识减少表项的比特大小或合并压缩表项来达到优化流表空间的目的.

3.1 表项聚合

表项聚合方式不依赖于网络数据流的特征规律，将具有相关性的多流表表项合并为一个表项，依据聚合位置的不同，主要分为前缀聚合和非前缀聚合.前缀聚合[18]主要用于IP路由，合并具有相同转发目的地的表项，而OpenFlow具有多元匹配域，且是变长结构，需要依据实际需求进行非前缀聚合，采用如启发式等聚合算法对相关字段进行聚合，分类如表2所示.

表2 表项聚合方案分类对比

MEINERS C R等提出适用于数据包分类的TCAM表项压缩算法TCAM razor[18]和Bit weaving[19].TCAM razor采用前缀聚合，通过判定图、贪心算法动态编码和前缀聚合冗余消除来压缩数据包分类器中的TCAM表项，但只能采用构造前缀聚合的方式来聚合表项.而Bit weaving可实现对已聚合表项的再一次聚合，解决了TCAM razor只能进行前缀聚合的不足.

FFTA[10]、FTRS[20]、IDFA[21]等均是基于SDN而设计的表项聚合方案.FFTA为一种高效的表项聚合算法，基于Bit Weaving 技术，通过构建二叉树将非前缀规则划分为多个可置换的前缀分区，采用基于优化路由表构造器(Optimal Routing Table Constructor，ORTC)算法进行聚合.FTRS和IDFA通过基于目的IP地址的聚合，其中，IDFA采用分解和重排技术对局域网IP和随机IP进行聚合，得到压缩比分别为26.3%和43%，而实验验证FTRS能有效地聚合流表表项，保证了SDN控制器的处理性能.

3.2 表项压缩

表项压缩采用压缩算法对流表结构、大小和数量进行压缩处理.常用的表项压缩降低了表项规模，依据作用对象不同可分为表项分割、标识改进和合并3类压缩方式.

GE J等[22]提出启发式流表存储空间优化算法H-SOFT，通过表项间的共生关系和互斥关系将大表项划分为多个规模较小的子表项，再将子表项依据表项中的多元匹配域情况分割为多个字段，以达到节省流表存储空间的目的.孙鹏浩等[23]利用信息熵对各表项匹配域间的冗余关系和相关度进行分析建模，得到匹配域提取目标进行裁剪，减少流表长度.

其他相关工作主要通过改进表项标识、资源复用等来解决流表空间存储有限的问题[24-26].BANERJEE S等[24]采用两层标签Tag来替换原始流表表项，关联到数据流的标签和路由标识标签，通过标签标识的方法生成流表表项，从而减少流表表项所占比特数.KANNAN K等[25]依据原始流表在入口交换机上的数据包头部加入流ID，中间传输的交换机也通过存储流ID来匹配和转发数据包，减少了标识流所需的比特位数，使TCAM能容纳较多的流表表项.基于资源复用的方案[26]也是通过压缩合并表项来优化存储问题，设计基于Mask值和Range值的流表关联度算法，计算待增表项与已存表项的关联度，将待增表项与最大关联度的已存表项进行合并.

基于软件的流表扩容主要通过表项聚合和表项压缩等手段来解决流表容量不足的问题.表项聚合分析流表多元匹配域中存在的冗余信息，对不同的匹配字段进行聚合，利用较少的表项实现原有的表项规则，但表项聚合可能破坏流表语义，丢失部分粒度控制信息，并不具有较强的通用性.表项压缩主要针对流表大小、规模进行优化，使TCAM能容纳更多的流表表项，此类方案针对流表表项压缩需求，利用流表的逻辑结构特征，结合流表结构的冗余性和可压缩性实现流表空间的优化，但表项压缩算法的设计与实现较为复杂，不适用于小规模的表项压缩.

4 流表超时时间管理

OpenFlow流表超时时间管理是通过超时时间来控制流表表项的生存时间.OpenFlow协议提供两种超时时间：硬超时时间(hard_timeout)和停滞等待超时时间(idle_timeout)，表项在交换机中的生存时间超过了预设定硬超时时间就会被删除，在停滞等待时间内流表表项未匹配到任何数据包也将会被删除(说明：后文中未指明具体超时时间的情况下，“超时时间”指停滞等待超时时间).基于流表超时时间管理对表项进行删除的方案主要分为时间序列预测、资源特征感知和其他针对流表超时时间的方案.时间序列预测主要是通过流表的匹配情况来调整流表超时时间，实现流表更新，提高流表空间的有效利用率和流表表项的匹配率；资源特征感知结合数据流特征或流表、控制器资源来对超时时间进行调整；其他方案主要通过提前删除无效流表表项、调整或转换超时时间等来优化流表空间存储和利用的问题.

4.1 时间序列预测

基于预测机制是结合历史流量或表项信息，通过时间序列预测的方式动态调整当前表项的超时时间，删除近期不会被匹配的流表表项，从而达到存储表项和下发表项数量的均衡，保证流表空间的有效性，过程如图1所示.

图1 时间序列预测处理图

KIM E D等[16]利用自回归模型来预测下一采样时刻流表中新到达流的数量，并估计下一采样周期内存活的流表表项数量.然后，在采样时刻动态刷新当前所有表项的超时时间来容纳新的流.LIU Y等[27]基于KIM E D提出的方案，考虑控制器刷新交换机中表项成本，通过调整采样周期内新到达流的超时时间，而非在采样时刻刷新所有流表表项的超时时间，从而优化流表存储空间，防止下一周期内流表溢出.

但是，自回归算法对数据依赖性强，需收集大量历史数据才能得出预测结果.史少平等[28]采用二次移动平均(Second Moving Average，SMA)算法对历史流表表项数量进行了分析，预测下一采样周期内新增的流表表项的数量，并对流表超时时间做出调整.在数据波动较大时，SMA算法比自回归算法预测准确度更高.

4.2 资源特征感知

除了时间序列预测，还可通过结合资源特征，如数据流特征或网络资源等使用情况，对流表超时时间作动态调整，表3给出相关文献的研究工作.

表3 资源特征感知方案对比

梁昊驰[29]针对即时消息流信息，建立ON/OFF模型，以控制器处理资源有限性为约束，建立优化问题来求解满足该条件的合理超时时间，但该方案在处理过程中没有考虑不同数据流类型的差异性.TimeoutX[30]和基于数据流特征的智能更新算法[31]从全局网络资源使用情况出发，结合数据流差异性特征，为不同的表项设定不同的超时时间.

ZHU H等[32]在控制中添加缓存模块来记录上一次流表表项到期时间，新安装流表时间与其比较作为差值，来确定流表超时时间；结合流表空间资源利用状况作为负载反馈，来调整最大超时时间.VISHNOI A等[33]提出SmartTime系统，利用启发式算法来计算最合适的超时时间.ZHANG L L等[34]将流表处理建模为排队，借助排队论定量分析超时时间对流截断次数和阻塞概率的影响，利用AHTM算法设定合理的硬超时时间，基于硬超时时间的调整机制在网络应用中灵活性较差，不能很好地满足传输要求.

4.3 其他管理方案

还有一些研究则是提前删除无效的流表表项，而非在超时时间到达之后才进行删除.HE C H等[35]在解析完TCP数据头部信息后，利用P4交换机中的Learn Table来探测和解析TCP流中的最后发送的数据包中的FIN和RST位来判定TCP连接是否即将关闭，以提前移除相应的流表表项，而不必等到停滞等待超时时间才进行删除.KANNAN K等[36]基于超时时间提前移除最近一段时间内不会被匹配的流表表项.此外，还可以基于流表字段超时时间的特点，对超时时间进行转化或调整.王敢甫等[37]依据流表超时时间的特点，提出流表表项的动静态转化机制，将静态流表表项转化为动态流表表项.

基于流表表项超时时间管理的机制，通过调整表项固有的超时时间来提高流表匹配率，从而有效利用流表空间.时序预测机制结合历史流和表项信息来设定超时时间，但未以控制层和转发层处理性能作为约束前提，且在实际操作中选取和实现能反映大部分数据信息、设计简单、运行速率高的预测算法较为困难和复杂.资源特征感知方案在结合数据流特征、流表资源和控制器资源约束时未能对数据流作出更为细致的分类，并且调整超时时间的算法设计复杂，不能改善流表查询效率和匹配率.其余方案提前删除无效表项，或从网络传输、流表匹配特性对表项超时时间作调整，在实际网络应用中，对于不同特征的数据流和更细粒度的控制需求，如何智能而有效地优化超时时间，还有待深入研究和验证.

5 总结与展望

基于OpenFlow协议的SDN架构给网络部署、管理带来了显著的灵活性和创造性，但不断扩展的网络业务需求对OpenFlow交换机的流表空间提出了更高的要求.

流表空间的有限性和有效性管理问题可通过基于缓存机制、表项压缩和超时时间等3类方案进行优化，本文对这些方案的特点分别进行了归纳总结.3类方案从TCAM存储流表容量和流表表项线性查询效率等方面进行了相关验证，在保证数据流正常传输的前提下，在不同的程度上可有效地解决流表空间管理问题.此外，OpenFlow流表作为SDN南向通信的核心部件，在部署应用中的空间优化还需要结合以下几方面作进一步研究：

(1)设计时间复杂度低、执行效率高、尽可能少地影响其他网络性能的缓存算法、压缩聚合算法和预测算法.在面向大规模网络时，真实网络中的性能需求、海量数据、可扩展性和路由是制约SDN发展的重要因素，优化算法或策略需要真实有效地反映实际的业务需求；

(2)兼顾流表空间利用率、流表查询效率和匹配率.在面对细粒度业务流控制需求时，对流表的空间优化尽可能同时保证查询效率与匹配率；

(3)保证表项规则的一致性和SDN安全需求设计.流表空间保证表项规则的存储，故存储安全和表项一致性关系到整个网络的可靠性，例如：缓存机制中的存储安全性设计对管理流和抵抗某些网络攻击具有一定的意义.

基于OpenFlow的SDN交换机中，流表空间的有限性和有效利用是软件定义网络技术的核心问题之一，鉴于当前流表的复杂性和日益剧增的网络业务类型及流量，如何管理和优化流表空间依旧亟待探索和解决.