Information entropy based match field cutting algorithm

Peng-hao SUN; Ju-long LAN; Shao-jun ZHANG; Jun-fei LI

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

您当前的位置：

首页 >

文章列表页 >

Information entropy based match field cutting algorithm

Academic communication | 更新时间：2024-06-05

- Information entropy based match field cutting algorithm
- Journal on Communications Vol. 38, Issue 5, Pages: 182-189(2017)
- 作者机构：
  
  国家数字交换系统工程技术研究中心，河南郑州 450002
- 作者简介：
- 基金信息：
  
  The National Basic Research Program of China (973 Program)(2013CB329104);The Innovation Group Program Project of National Natural Science Foundation of China(61521003);The National High Technology Research and Development Program of China (863 Program)(2015AA016102)
- DOI：10.11959/j.issn.1000-436x.2017048
  CLC： TP393
- Online First：2017-05，
  
  Published：25 May 2017
- 稿件说明：
移动端阅览
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：

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 .

Views

2092

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

ERDOF: outlier detection algorithm based on entropy weight distance and relative density outlier factor

Parallel association rules incremental mining algorithm based on information entropy and genetic algorithm

Metric and classification model for privacy data based on Shannon information entropy and BP neural network

New delay measurement method based on accurate timestamp in OpenFlow

Research on software-defined network and the security defense technology

Related Author

Mianxin WEI

Yu DENG

Yuting ZHANG

Weixiong LIU

Zhongping ZHANG

Zhigang CHEN

Qianhu DENG

Yimin MAO

Related Institution

The Key Laboratory of Software Engineering of Hebei Province

The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province

College of Information Science and Engineering, Yanshan University

College of Computer Science and Engineering, Central South University

School of Information Engineering, Jiangxi University of Science and Technology

AI问答

⁰