提高软件定义网络交换机存储能力的流表压缩算法  

A Flow Table Compression Algorithm for Improving the Storage Capacity of Software-Defined Network Switches

作　　者：沈剑良 王崇越[1,2] 汤先拓 张霞 SHEN Jianliang;WANG Chongyue;TANG Xiantuo;ZHANG Xia(PLA Strategic Support Force Information Engineering University,Zhengzhou 450003,China;National Digital Switch System Engineering and Technological Research Center,Zhengzhou 450002,China)

机构地区：[1]中国人民解放军战略支援部队信息工程大学,郑州450003 [2]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《西安交通大学学报》2022年第11期186-194,共9页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(61872382)。

摘　　要：针对目前软件定义网络(SDN)中流表规模不断增大且存储效率较低的问题,提出了一种新的提高SDN交换机存储能力的流表压缩算法。首先对传统前缀编码算法分析,发现2的指数幂(2 n)范围编码后字符串最高有效位递增,且其余低位均为通配符;其次对流表中范围字段按照2的指数幂进行分割,得到多个范围字段,利用最高位和通配符实现仅用一条表项编码2的指数幂范围字段,其他范围字段采用前缀编码;最后将编码结果存储至不同三态内容寻址存储器,进行分类存储。实验结果表明,与已有的算法相比,所提流表压缩算法在独立于流表内容的基础上具备更高的更新速度与更低的最坏情况拓展比,在防火墙类型规则集编码后平均可减少86%和83%的表项数量,且不需要占用额外比特位,从更细粒度层次实现了存储空间的优化使用,具有良好的应用前景。This paper proposes a new flow table compression algorithm to tackle the problem of increasing flow tables in software-defined network and low storage efficiency,thus improving the storage capacity of SDN switches.Firstly,the conventional prefix coding algorithm is analyzed.The results show that the highest significant bit of the string is incremented after the exponentiation range value of 2 is encoded,and that the remaining low bits are wildcards.Secondly,the range field in the flow table is divided according to the exponential power of 2 to obtain multiple range fields.Using the highest bit and wildcards,only one table item is used to encode the exponential power range field of 2,and other range fields are prefix encoded.Finally,the coding results are stored in different ternary content addressable memories for classified storage.According to the simulation results,compared with the existing algorithms,the proposed method realizes higher update speed and lower worst-case expansion ratio on the basis of being independent of the content of the flow table.In addition,it can reduce the number of table items by 86%and 83%on average after the firewall type rule set is coded.The range value storage based on the proposed method requires no additional bits,realizing the optimal use of storage space from a more fine-grained level,which has good application prospects.

关 键 词：软件定义网络 三态内容寻址存储器 范围编码 流表 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]