基于信息熵的匹配域裁剪算法

孙鹏浩; 兰巨龙; 张少军; 李军飞

doi:10.11959/j.issn.1000-436x.2017048

您当前的位置：

首页 >

文章列表页 >

基于信息熵的匹配域裁剪算法

学术通信 | 更新时间：2024-06-05

- 基于信息熵的匹配域裁剪算法
- Information entropy based match field cutting algorithm
- 通信学报 2017年38卷第5期页码：182-189
- 作者机构：
  
  国家数字交换系统工程技术研究中心，河南郑州 450002
- 作者简介：
  
  [ "孙鹏浩（1992-），男，山东青岛人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为可编程网络、数字交换技术。" ]
  [ "兰巨龙（1962-），男，河北张北人，博士，国家数字交换系统工程技术研究中心总工程师、教授、博士生导师，主要研究方向为新一代信息网络关键理论与技术。" ]
  [ "张少军（1989-），男，山西新绛人，国家数字交换系统工程技术研究中心博士生，主要研究方向为软件定义网络。" ]
  [ "李军飞（1989-），男，河南安阳人，国家数字交换系统工程技术研究中心博士生，主要研究方向为软件定义网络。" ]
- 基金信息：
  
  国家重点基础研究发展计划（“973计划）基金资助项目(2013CB329104);国家自然科学基金创新群体基金资助项目(61521003);国家高技术研究发展计划（“863”计划）基金资助项目(2015AA016102)
- DOI：10.11959/j.issn.1000-436x.2017048
  中图分类号： TP393
- 网络出版日期：2017-05，
  
  纸质出版日期：2017-05-25
- 稿件说明：
移动端阅览
孙鹏浩, 兰巨龙, 张少军, 等. 基于信息熵的匹配域裁剪算法[J]. 通信学报, 2017,38(5):182-189.

Peng-hao SUN, Ju-long LAN, Shao-jun ZHANG, et al. Information entropy based match field cutting algorithm[J]. Journal on communications, 2017, 38(5): 182-189.
孙鹏浩, 兰巨龙, 张少军, 等. 基于信息熵的匹配域裁剪算法[J]. 通信学报, 2017,38(5):182-189. DOI： 10.11959/j.issn.1000-436x.2017048.

Peng-hao SUN, Ju-long LAN, Shao-jun ZHANG, et al. Information entropy based match field cutting algorithm[J]. Journal on communications, 2017, 38(5): 182-189. DOI： 10.11959/j.issn.1000-436x.2017048.

摘要

随着网络功能日益多样化，分组分类技术对匹配域数量、表项深度等需求不断提高，加剧了硬件存储压力。为保证查表效率和硬件资源利用率，提出基于信息熵的匹配域裁剪算法。通过分析匹配域冗余信息，提出匹配域裁剪模型；通过分组头部信息熵的映射建模，将匹配域裁剪算法复杂度从NP难降为线性复杂度。实验结果表明，较现有方案，所提方案所需三态内容寻址存储器（TCAM，ternary content-addressable memory）存储空间能够进一步减少40%以上，或随着流表规模增长，所提案能够明显减少算法运行时间。

Abstract

With the increasing diversity of network functions

packet classification had a higher demand on the number of match fields and depth of match table

which placed a severe burden on the storage capacity of hardware.To ensure the efficiency of matching process while at the same time improve the usage of storage devices

an information entropy based cutting algorithm on match fields was proposed.By the analysis on the redundancy of match fields and distribution pattern in a rule set

a match field cutting model was proposed.With the mapping of matching process to the process of entropy reduction

the complexity of optimal match field cutting was reduced from NP-hard to linear complexity.Experiment results show that compared to existing schemes

this scheme can need 40% less TCAM storage space

and on the other side

with the growing of table size

the time complexity of this algorithm is also far less than other algorithms.

关键词

Keywords

references

TAYLOR D E . Survey and taxonomy of packet classification techniques [J ] . ACM Computing Surveys , 2005 , 37 ( 3 ): 238 - 275 .

KANNAN K , BANERJEE S . Compact TCAM:flow entry compaction in TCAM for power aware SDN [C ] // Distributed Computing and Networking . 2013 : 439 - 444 .

MCKEOWN N , ANDERSON T , BALAKRISHNAN H , et al . OpenFlow:enabling innovation in campus networks [J ] . ACM Sigcomm Computer Communication Review , 2008 , 38 ( 2 ): 69 - 74 .

LAKSHMINARAYANAN K , RANGARAJAN A , VENKATACHARY S . Algorithms for advanced packet classification with ternary CAMs [C ] // ACM Sigcomm Computer Communication Review . 2005 : 193 - 204 .

BREMLER-BARR A , HENDLER D . Space-efficient TCAM-based classification using Gray coding [J ] . IEEE Transactions on Computers , 2012 , 61 ( 1 ): 18 - 30 .

BREMLER-BARR A , HAY D , HENDLER D . Layered interval codes for TCAM-based classification [C ] // INFOCOM 2009 . 2009 : 1305 - 1313 .

BREMLER-BARR A , HARCHOL Y , HAY D , et al . Encoding short ranges in TCAM without expansion:efficient algorithm and applications [C ] // ACM Symposium . 2016 .

MEINERS C R , LIU A X , TORNG E . Bit weaving:a non-prefix approach to compressing packet classifiers in TCAMs [J ] . IEEE/ACM Transactions on Networking , 2012 , 20 ( 2 ): 93 - 102 .

CHANG D Y , WANG P C . TCAM-based multi-match packet classification using multidimensional rule layering [J ] . IEEE/ACM Transactions on Networking , 2016 , 24 ( 2 ): 1125 - 1138 .

MISHRA T , SAHNI S , SEETHARAMAN G . PC-DUOS:fast TCAM lookup and update for packet classifiers [J ] . IEEE Symposium on Computers and Communications , 2011 , 34 ( 17 ): 265 - 270 .

BANERJEE T , SAHNI S , SEETHARAMAN G . PC-DUOS+:a TCAM architecture for packet classifiers [J ] . IEEE Transactions on Computers , 2014 , 63 ( 6 ): 1527 - 1540 .

BANERJEE T , SAHNI S , SEETHARAMAN G . PC-TRIO:a power efficient TCAM architecture for packet classifiers [J ] . IEEE Transactions on Computers , 2015 , 64 ( 4 ): 1104 - 1118 .

GE J , CHEN Z , WU Y , et al . H-SOFT:a heuristic storage space optimisation algorithm for flow table of OpenFlow [J ] . Concurrency &Computation Practice & Experience , 2014 , 27 ( 13 ): 3497 - 3509 .

KOGAN K , NIKOLENKO S I , ROTTENSTREICH O , et al . Exploiting order independence for scalable and expressive packet classification [J ] . IEEE/ACM Transactions on Networking , 2015 ( 99 ): 1 - 14 .

LIU Z , WANG X , YANG B , et al . BitCuts:towards fast packet classification for order-independent rules [J ] . ACM SIGCOMM Computer Communication Review , 2015 , 45 ( 4 ): 339 - 340 .

TAYLOR D E , TURNER J S . ClassBench:a packet classification benchmark [J ] . IEEE/ACM Transactions on Networking , 2005 , 3 ( 3 ): 499 - 511 .

浏览量

1057

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

ERDOF：基于相对熵权密度离群因子的离群点检测算法

基于信息熵与遗传算法的并行关联规则增量挖掘算法

基于Shannon信息熵与BP神经网络的隐私数据度量与分级模型

OpenFlow中基于精确时间戳的延迟测量方法

软件定义网络及安全防御技术研究