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

软件定义网络的转发控制分离、集中控制、开放接口等特性使网络变得灵活可控,其架构得到了充分的发展.由于与各种云化业务的良好结合,软件定义网络(software defined networking,SDN)在近些年来得到了大量的商业部署.在基于OpenFlow的SDN架构中,为了实现流表项的快速查找、掩码匹配等目标,商业部署的硬件交换机大多使用三态内容寻址存储器(ternary content addressable memory,TCAM)来存储控制器下发的流表项.但受限于TCAM的容量和价格,目前商用OpenFlow交换机至多能支持存储数万条流表项,导致其存在因突发流和流表攻击等原因而产生流表溢出问题,严重影响了网络性能.因此,如何建立高效的流表溢出缓解机制引起了研究人员的广泛关注.首先对OpenFlow交换机流表溢出问题产生的原因及其影响进行了分析,在此基础上按照流量突发和攻击行为2种情况归纳对比了流表溢出缓解技术的研究现状,总结分析了现有研究存在的问题与不足,并展望了未来的发展方向和面临的挑战.     

DAFT:一种OpenFlow大规模流表区分存储与加速查找架构

软件定义网络作为一种数据转发与逻辑控制相解耦的创新网络范式,当采用OpenFlow协议进行大规模部署时,其数据平面的流表规模急剧增大,对OpenFlow交换机的流表存储资源和分组转发性能提出了严峻的挑战.对此,本文构建了一种OpenFlow大规模流表区分存储与加速查找架构DAFT.该架构根据流量分布特性将OpenFlow网络流区分为重要流和次要流,进而采用TCAM和SRAM分别存储其标识字段,并采用DRAM单独存储其内容字段,有效缓解OpenFlow流表存储资源紧张问题.针对重要流/次要流区分问题,在分析传统大象流/老鼠流区分方法的基础上,基于OpenFlow网络流的包成批特性,提出活跃流/空闲流区分方法,以提高TCAM命中率.针对SRAM流表查找性能瓶颈,利用掩码访问不均匀的特点,采用"往前移1"启发法自适应调整掩码顺序,以减少后续数据包的掩码失败探测次数;利用掩码探测多数会失败的特点,借助计数型布鲁姆过滤器预测元组查找失败结果,从而绕过对应的子流表遍历过程.最后,借助骨干网络流量样本,对本文所提DAFT流表架构的查找性能进行实验评估.实验结果表明:DAFT流表架构的TCAM命中率、SRAM平均查找长度和平均流表访问时间均明显优于传统的大象流/老鼠流架构,且稳定性强,有效提升了OpenFlow交换机的分组转发性能.     

基于匹配动作表模型的可编程数据平面流表归并

与传统网络技术相比,SDN技术将网络的控制平面与数据平面分离,使网络具有一定的可编程能力。以OpenFlow、POF、P4等为代表,领域内常见的SDN交换机大多基于匹配动作表模型实现。与协议相关的OpenFlow等技术不同,协议无感知的SDN技术使用{偏移,长度}等结构表示协议字段,从而实现对任意协议字段的解析和处理。然而,待处理的数据包可能带有不同长度的数据包头,所以这些数据包中特定协议字段的偏移也会不同,需要多个匹配域偏移不同的流表去完成数据流的解析,从而造成流表和流水线结构复杂。针对上述问题,本文提出一种基于MAT模型的可编程数据平面流表归并方案,扩展MAT模型中的动作集,在数据包查询流表时使用特定的动作动态地调整数据包的起始偏移,使不同数据包同一协议字段的偏移保持一致,实现匹配域相同的流表的归并。本文方案在兼容VLAN、QinQ的POF Switch实验场景下,以跳转流表时多执行一条动作为代价,缩减了约69%的流表内存消耗。     

TCAM路由更新的硬件优化

现代核心路由器对查找速率、表项更新速度、查找表容量等提出越来越高的要求。目前工业厂商大多采用基于TCAM(三态内容关联存储器)的解决方案。TCAM最大特点是查找速度快,但其更新算法会浪费很大的存储空间。针对这个问题该文提出一种利用FPGA提供硬件支持的路由更新方法,增加新表项时,只需对新增表项进行一次预处理,转发表无需按前缀长度排序,消除了预留空闲表项造成的存储空间浪费。     

SDN交换机转发规则TCAM存储优化综述

软件定义网络(SDN)将传统网络的控制平面和数据平面解耦,通过控制平面的控制器灵活地对网络进行管理,目前应用最广泛的控制协议是OpenFlow.三态内容寻址存储器(TCAM)查找速度快、支持三态掩码存储,在SDN网络中应用广泛.但TCAM成本高、功耗大,并且在存储含有范围字段匹配域的规则时候存在范围膨胀问题,因此交换机中可存储的转发规则数量,尤其是匹配域的数量和类型都比较多的OpenFlow规则数目非常有限,这成为约束SDN网络大规模扩展和应用的瓶颈.研究机构从不同角度提出了针对SDN中交换机转发规则的TCAM存储优化方案.本文从转发规则存储架构优化、本地交换机转发规则压缩、全局转发规则动态优化以及控制器参与的网络转发规则管理四个角度总结了相关研究工作,并提出了适合未来SDN网络的转发规则存储的综合优化方案.     

SDN动态停滞超时时间优化算法

针对当软件定义网络(SDN)数据量高峰时,SDN交换机有限的流表项资源会对网络性能有很大限制这一问题,提出了一种动态停滞超时时间优化(DTO)算法。先用动态指数平滑(DES)算法估计出下一时间周期内网络中的新增流表项数量,而后依据SDN中的实际负载状况,采用动态参数对流表项的停滞超时时间进行动态优化调整。经Mininet仿真证明:优化算法能有效提高流表匹配率、流表资源利用率以及网络平均吞吐量,提升整体网络性能。     

基于独立规则集位提取的包分类压缩方法

针对当前互联网中多匹配域流表规模不断膨胀、匹配宽度不断增大，导致硬件存储压力过大的问题，提出了一种基于独立规则子集位提取（BEIS）的压缩方案。首先，根据多匹配域之间的逻辑关系进行匹配域合并，从而减少匹配域个数、减小流表位宽；其次，对合并后的规则集进行独立规则子集分割，将分割后的子集进行可区分的位提取，从而使用部分位完成匹配查找功能，进一步缩减所用的三态内容寻址寄存器（TCAM）空间；最后，提出了实现该方案的硬件查找架构。仿真结果表明，对于OpenFlow流表，该方案在一定的时间复杂度下，比匹配域裁剪（FT）方案减少了20%的存储空间；另外，对于实际应用中常见的访问控制列表、防火墙等包分类规则集，可实现20%到40%的压缩比率。     

数据流特征感知的交换机流表智能更新方法

针对软件定义网络（SDN）中交换机流表匹配率低的问题,提出了数据流特征感知的交换机流表智能更新方法。首先,论述流表项的生存超时时间timeout对数据包匹配的影响,并且分析比较基于先进先出（FIFO）、近期最少使用（LRU）等一般方法存在的不足;其次,根据流表项的生存时间和数据流的特征密切相关的思想,利用基于隐马尔可夫模型（HMM）的深度流检测（DFI）技术对数据流进行分类;最后,根据流表资源和控制器计算资源状况,实现对不同类型数据流流表项的智能更新。采用校园数据中心网络行为数据的模拟实验表明,与流表更新的一般方法相比,智能方法能使流表匹配率提高5%以上,对SDN交换机的管理有实际意义。     

基于ARMA模型预测的交换机流表更新算法

针对SDN网络中交换机在网络流量高峰期流表匹配率低以及控制器负载过重的问题,提出了一种基于自回归移动平均（ARMA）模型预测的交换机流表更新算法。算法首先收集每个取样周期内的新增流表项数量作为历史数据,然后使用ARMA模型对收集的历史数据进行分析,预测下一个周期内新增加的流表项数量,并结合当前流表空间的使用情况,清除交换机中过去一段时间内使用频率较低的流表项。采用真实数据中心网络数据的模拟实验结果表明,与流表更新的一般方法相比,该算法有效地提高了交换机流表的匹配率,并减少了交换机与控制器之间交互的次数,降低了控制器端的负载。     

基于预测缓存的OpenFlow虚拟流表高效查找方法

OpenFlow支持通配符查找,会造成严重的流表查找性能瓶颈。为此,基于网络流量局部性,提出一种OpenFlow虚拟流表查找方法。通过缓存在数据包流中近期频繁出现的连接和对应的掩码,对大部分数据包直接定位其掩码,进而查找流表,无需逐个探测掩码数组。理论分析和实验结果表明,相比于目前主流虚拟交换机中的流表查找方法OFT-OVS,该方法的平均查找长度较小,可有效提升OpenFlow虚拟交换机的数据转发性能。     

一种基于MapReduce的OpenFlow网络属性并行验证算法

针对OpenFlow网络中流表配置错误引起转发回路、路由黑洞和访问控制规则失效等问题,提出一种并行的基于MapReduce的OpenFlow网络属性验证算法。通过在Map阶段划分规则等价类,在Reduce阶段为规则等价类构建基于交换机端口谓词的网络转发图并分析可达性,实现对网络属性的并行验证。同时,通过采用原子谓词将传统可达性分析中的规则匹配域多维集合运算转换为整数集合运算,以进一步提高可达性分析效率。此外,基于原子谓词的谓词表达方式可消除交换机端口谓词集合中的冗余项,降低存储开销。最后,通过理论分析和仿真实验验证了算法的正确性及在时间和存储开销方面的优越性。     

采用集合切分编码的大容量模式匹配算法*

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。     

基于三态内容寻址存储器的多模式匹配算法

传统模式匹配算法在高速环境下无法实现数据包的实时处理。为此,提出一种基于三态内容寻址存储器(TCAM)的快速多模式匹配算法,通过模式移位将长模式截取为若干个子串,第1级TCAM存储子串,第2级TCAM存储子串的序列编号。搜索模式时,第1级TCAM向后端输出命中表项的编号,第2级TCAM实现序列编号的匹配,从而获得长模式的匹配信息,并通过编号空间划分方法压缩表项数目以提高资源利用率。实验结果表明,该算法可以实现网络数据的高速匹配处理,与基于hash标识的移位存储算法相比,具有空间消耗少的优势。     

面向星载计算机的双重索引数据压缩方法

随着星载计算机系统功能的日益复杂,程序规模也在快速扩大.在存储资源极其受限的背景下,需要稳定、有效的代码压缩功能来保障星载软件的正常存储与运行.混合压缩算法是目前无损数据压缩的主流算法,具有压缩率高、代码规模和计算资源需求大的特点.然而,在航天星载计算机等嵌入式系统中,由于其运行环境特殊,需要较高的可靠性和抗干扰能力,无法实现混合压缩算法应有的效果.同时,单一压缩模型压缩率较低.针对以上问题,在LZ77算法代码体积和内存消耗优势的基础上提出了改进方法为压缩过程设计一种新的匹配记录表以存储高价值数据索引来辅助压缩,实现了原算法局部性优势与高价值数据全局分布的互补,更大程度上减少了数据冗余;结合动态填充、变长编码等进一步优化编码结构,降低存储需求;最终,设计并实现了一种更加适合航天嵌入式环境的无损数据压缩算法(LZRC).实验结果表明:(1)新算法在比LZ77算法代码体积仅多出3.5 KB的条件下,对软件代码的平均压缩比提高了17%;(2)新算法的运行内存需求仅为混合压缩算法的12%,代码体积也减少了84%,更加适合星载计算机系统.     

基于正则表达式的DFA拆分算法研究

深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表：间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。     

一种节约空间的AC算法与国产化平台实现

AC算法作为多模式匹配算法的一种,在入侵检测、内容过滤防火墙、病毒检测等场景中得到了广泛的应用。AC算法的性能不仅受限于算法本身,还与算法运行的平台相关。使用普通的CPU进行模式匹配,只能达到300 Mbps左右的吞吐率,而使用FPGA进行匹配,吞吐率可以达到1 Gbps以上。但是FPGA的存储容量有限,可以匹配的模式个数受限。本文提出了一种节约空间的AC算法,设计了适用于FPGA存储的状态转移表,降低了AC算法需要的存储空间大小,同时在匹配过程中不带来额外的运算开销,尤其适用于内容过滤防火墙等对实时性要求较高的应用。     

一种基于双重状态编码的多模式匹配算法

基于自动机的多模式匹配算法是网络内容过滤与业务监管的核心技术之一,但随着模式集合的扩大,对存储资源消耗过大。为降低当前匹配算法的空间复杂度,同时保持较低的时间复杂度,提出了一种基于关键字预处理和状态编码的优化方法。关键字预处理用于过滤冗杂内容,大大降低了处理复杂度;而采用状态编码消除了NFA中的大量failure转移,可有效降低其开销。理论分析和实验仿真表明,相对于传统的基于TCAM的匹配算法,该算法在大大减少内存需求的情况下,实现了模式的高效匹配。