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

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

通信学报 ›› 2017, Vol. 38 ›› Issue (5): 182-189.doi: 10.11959/j.issn.1000-436x.2017048

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

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

国家数字交换系统工程技术研究中心，河南郑州 450002

修回日期:2017-01-17 出版日期:2017-05-01 发布日期:2017-05-28
作者简介:孙鹏浩（1992-），男，山东青岛人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为可编程网络、数字交换技术。|兰巨龙（1962-），男，河北张北人，博士，国家数字交换系统工程技术研究中心总工程师、教授、博士生导师，主要研究方向为新一代信息网络关键理论与技术。|张少军（1989-），男，山西新绛人，国家数字交换系统工程技术研究中心博士生，主要研究方向为软件定义网络。|李军飞（1989-），男，河南安阳人，国家数字交换系统工程技术研究中心博士生，主要研究方向为软件定义网络。
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目(2013CB329104);国家自然科学基金资助项目(61521003);国家高技术研究发展计划（“863”计划）基金资助项目(2015AA016102)

Information entropy based match field cutting algorithm

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

National Digital Switching System Engineering and Technological R＆D Center (NDSC),Zhengzhou 450002,China

Revised:2017-01-17 Online:2017-05-01 Published:2017-05-28
Supported by:
The National Basic Research Program of China (973 Program)(2013CB329104);The National Natural Science Foundation of China(61521003);The National High Technology Research and Development Program of China (863 Program)(2015AA016102)

摘要/Abstract

摘要：

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

关键词: 分组分类, 三态内容寻址存储器, OpenFlow, 信息熵

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.

Key words: packet classification, TCAM, OpenFlow, information entropy

中图分类号:

TP393

孙鹏浩,兰巨龙,张少军,李军飞. 基于信息熵的匹配域裁剪算法[J]. 通信学报, 2017, 38(5): 182-189.

Peng-hao SUN,Ju-long LAN,Shao-jun ZHANG,Jun-fei LI. Information entropy based match field cutting algorithm[J]. Journal on Communications, 2017, 38(5): 182-189.

图/表 10

图1

图2

图3

图4

图5

图7

图6

图8

图10

图9

参考文献 16

[1]	TAYLOR D E . Survey and taxonomy of packet classification techniques[J]. ACM Computing Surveys, 2005,37(3): 238-275.
[2]	KANNAN K , BANERJEE S . Compact TCAM:flow entry compaction in TCAM for power aware SDN[C]// Distributed Computing and Networking. 2013: 439-444.
[3]	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.
[4]	LAKSHMINARAYANAN K , RANGARAJAN A , VENKATACHARY S . Algorithms for advanced packet classification with ternary CAMs[C]// ACM Sigcomm Computer Communication Review. 2005: 193-204.
[5]	BREMLER-BARR A , HENDLER D . Space-efficient TCAM-based classification using Gray coding[J]. IEEE Transactions on Computers, 2012,61(1): 18-30.
[6]	BREMLER-BARR A , HAY D , HENDLER D . Layered interval codes for TCAM-based classification[C]// INFOCOM 2009. 2009: 1305-1313.
[7]	BREMLER-BARR A , HARCHOL Y , HAY D ,et al. Encoding short ranges in TCAM without expansion:efficient algorithm and applications[C]// ACM Symposium. 2016.
[8]	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.
[9]	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.
[10]	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.
[11]	BANERJEE T , SAHNI S , SEETHARAMAN G . PC-DUOS+:a TCAM architecture for packet classifiers[J]. IEEE Transactions on Computers, 2014,63(6): 1527-1540.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	TAYLOR D E , TURNER J S . ClassBench:a packet classification benchmark[J]. IEEE/ACM Transactions on Networking, 2005,3(3): 499-511.

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

Information entropy based match field cutting algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 16

相关文章 15

Metrics

推荐阅读 0

[1]	张忠平, 刘伟雄, 张玉停, 邓禹, 魏棉鑫. ERDOF：基于相对熵权密度离群因子的离群点检测算法[J]. 通信学报, 2021, 42(9): 133-143.
[2]	毛伊敏, 邓千虎, 陈志刚. 基于信息熵与遗传算法的并行关联规则增量挖掘算法[J]. 通信学报, 2021, 42(5): 122-136.
[3]	俞艺涵,付钰,吴晓平. 基于Shannon信息熵与BP神经网络的隐私数据度量与分级模型[J]. 通信学报, 2018, 39(12): 10-17.
[4]	胡慧,陈鸣,刘波,许博,邢长友,胡超. 消除OpenFlow网络中UDP冗余控制分组的机制[J]. 通信学报, 2017, 38(9): 167-175.
[5]	王涛,陈鸿昶,程国振. 软件定义网络及安全防御技术研究[J]. 通信学报, 2017, 38(11): 133-160.
[6]	邱欣逸,李俊,周建二,李菁菁. OpenFlow中基于精确时间戳的延迟测量方法[J]. 通信学报, 2017, 38(11): 178-187.
[7]	胡毅勋,郑康锋,杨义先,钮心忻. 基于OpenFlow的网络层移动目标防御方案[J]. 通信学报, 2017, 38(10): 102-112.
[8]	刘江,黄韬,张晨,张歌. SDN试验床网络虚拟化切片机制综述[J]. 通信学报, 2016, 37(4): 159-171.
[9]	李春强,董永强,吴国新. 多单元散列表与TCAM结合的OpenFlow流表查找方法[J]. 通信学报, 2016, 37(10): 128-140.
[10]	王秀磊,张国敏,胡超,陈鸣,魏祥麟. SDFAC：软件定义的流接入控制机制[J]. 通信学报, 2015, 36(Z1): 188-196.
[11]	王哲,梁满贵,及晓萌. 源端控制的OpenFlow数据面[J]. 通信学报, 2015, 36(3): 195-201.
[12]	翁溪,陈鸣,张国敏,许博,邢长友. OpenFlow网络测量分析系统的设计实现[J]. 通信学报, 2015, 36(3): 81-88.
[13]	陈立南，刘阳，马严，黄小红，赵庆聪，魏伟. 基于统计的高效决策树分组分类算法[J]. 通信学报, 2014, 35(Z1): 12-64.
[14]	陈立南,刘阳,马严,黄小红,赵庆聪,魏伟. 基于统计的高效决策树分组分类算法[J]. 通信学报, 2014, 35(Z1): 58-64.
[15]	史衍伟,曹争. 自治系统内IP子网和SDN子网的互联机制[J]. 通信学报, 2014, 35(Z1): 76-81.