Field-trimming Compression Model for Rule Set of Packet Classification
SUN Penghao① LAN Julong① LU Xiaoyuan② HU Yuxiang① MA Teng①
①(National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, China) ②(Shanghai Engineering Research Center for Broadband Technologies & Applications, Shanghai 200336, China)
With the emergence of multi-field packet classification such as OpenFlow, the increasing number of match fields, continuous growth in bit-width of entries and ever growing scale of rule set all bring much pressure on the storage space in hardware. To improve the utilization of the existing Ternary Content Addressable Memory (TCAM) resources, a match field reduction scheme Field Trimmer is proposed based on the analysis of rule feature. On the one hand, with the analysis of logical relationships among different match fields, some fields can be merged to reduce the number of match fields. On the other hand, with the analysis of statistical features in a rule set, some of the match fields are picked up to achieve the classification function of the whole set. Experiment result shows that with less algorithm complexity, the proposed scheme can save around 50% storage space in the rule set of OpenFlow compared to the best prior art, and about 40% storage space in the popular 5-tuple packet classification rule set.
孙鹏浩,兰巨龙, 陆肖元,胡宇翔,马腾. 一种基于匹配域裁剪的包分类规则集压缩方法[J]. 电子与信息学报, 2017, 39(5): 1185-1192.
SUN Penghao, LAN Julong, LU Xiaoyuan, HU Yuxiang, MA Teng. Field-trimming Compression Model for Rule Set of Packet Classification. JEIT, 2017, 39(5): 1185-1192.
MCKEOWN N. Software-defined networking[C]. INFOCOM Keynote Talk, Rio de Janero, Brazil, 2009: 30-32.
[2]
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. doi: 10.1145/1355734.1355746.
[3]
LAKSHMINARAYANAN K, RANGARAJAN A, and VENKATACHARY S. Algorithms for advanced packet classification with ternary CAMs[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(4): 193-204. doi: 10.1145/1090191.1080115.
[4]
VAMANAN B, VOSKUILEN G, and VIJAYKUMAR T N. EffiCuts: Optimizing packet classification for memory and throughput[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 207-218. doi: 10.1145/1851182.1851208.
[5]
SONG H and TURNER J S. ABC: Adaptive binary cuttings for multidimensional packet classification[J]. IEEE/ACM Transactions on Networking, 2013, 21(1): 98-109. doi: 10. 1109/TNET.2012.2190519.
CHEN Zhenghu, LAN Julong, HUANG Wanwei, et al. A TCAM service identification algorithm based on access compression using bloom-filter[J]. Journal of Electronics & Information Technology, 2011, 33(9): 2212-2218. doi: 10. 3724/SP.J.1146.2011.00058.
[7]
BREMLER-BARR A and HENDLER D. Space-efficient TCAM-based classification using Gray coding[J]. IEEE Transactions on Computers, 2012, 61(1): 18-30. doi: 10.1109/ TC.2010.267.
[8]
BREMLER-BARR A, HAY D, and HENDLER D. Layered interval codes for TCAM-based classification[C]. INFOCOM 2009, Rio de Janero, Brazil, 2009: 1305-1313. doi: 10.1109/ INFCOM.2009.5062045.
[9]
MEINERS C R, LIU A X, and 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. doi: 10.1109/TNET.2011.2165323.
[10]
WEI Rihua, XU Yang, and CHAO H J. Finding nonequivalent classifiers in Boolean space to reduce TCAM usage[J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 968-981. doi: 10.1109/TNET.2015.2402093.
[11]
MISHRA T, SAHNI S, and SEETHARAMAN G. PC-DUOS: Fast TCAM lookup and update for packet classifiers[C]. IEEE Symposium on Computers and Communications, Kerkyra, Corfu, Greece, 2011: 265-270. doi: 10.1109/ ISCC.2011.5983851.
[12]
BANERJEE T, SAHNI S, and SEETHARAMAN G. PC- DUOS+: A TCAM architecture for packet classifiers[J]. IEEE Transactions on Computers, 2014, 63(6): 1527-1540. doi: 10.1109/TC.2012.287.
[13]
BANERJEE T, SAHNI S, and SEETHARAMAN G. PC-TRIO: A power efficient TCAM architecture for packet classifiers[J]. IEEE Transactions on Computers, 2015, 64(4): 1104-1118. doi: 10.1109/TC.2014.2315645.
[14]
CHANG D Y and WANG P C. TCAM-based multi-match packet classification using multidimensional rule layering[J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 1125-1138. doi: 10.1109/TNET.2015.2411274.
[15]
SCHRIFF L, AFEK Y, and BREMLER-BARR A. Orange: Multi field OpenFlow based range classifier[C]. ACM/IEEE Symposium on Architectures for Networking & Communications Systems, Oakland, CA, USA, 2015: 63-73. doi: 10.1109/ANCS.2015.7110121.
[16]
KOGAN K, NIKOLENKO S I, ROTTENSTREICH O, et al. Exploiting order independence for scalable and expressive packet classification[J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 1251-1264. doi: 10.1109/TNET. 2015.2407831.
[17]
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. doi: 10.1145/2785956. 2789998.
[18]
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. doi: 10.1002/cpe.3206.
[19]
YUN R Q and VIKTOR K P. High-performance and dynamically updatable packet classification engine on FPGA[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(1): 197-209. doi: 10.1109/TPDS.2015. 2389239.
TAYLOR D E and TURNER J S. ClassBench: A packet classification benchmark[J]. IEEE/ACM Transactions on Networking, 2005, 3(3): 499-511. doi: 10.1109/TNET.2007. 893156.