一種基于匹配域裁剪的包分類規(guī)則集壓縮方法

孫鵬浩; 蘭巨龍; 陸肖元; 胡宇翔; 馬騰

doi:10.11999/JEIT160740

一種基于匹配域裁剪的包分類規(guī)則集壓縮方法

doi: 10.11999/JEIT160740 cstr: 32379.14.JEIT160740

1.
(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心鄭州 450002) ②(上海未來寬帶技術(shù)及應(yīng)用工程研究中心上海 200336)

基金項(xiàng)目:

國家973計(jì)劃項(xiàng)目(2012CB315901)，國家自然科學(xué)基金(61521003)，國家863計(jì)劃項(xiàng)目(2013AA013505)

計(jì)量
- 文章訪問數(shù): 1322
- HTML全文瀏覽量: 136
- PDF下載量: 305
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2016-07-11
- 修回日期: 2017-02-08
- 刊出日期: 2017-05-19

Field-trimming Compression Model for Rule Set of Packet Classification

1.
(National Digital Switching System Engineering &
2.
(Shanghai Engineering Research Center for Broadband Technologies &

Funds:

The National 973 Program of China (2012CB315901), The National Natural Science Foundation of China (61521003), The National 863 Program of China (2013AA013505)

摘要

摘要: 隨著以O(shè)penFlow為代表的多匹配域包分類規(guī)則的出現(xiàn)，匹配域數(shù)量的不斷增加、流表寬度的不斷增大以及流表規(guī)模的不斷膨脹，大大增加了硬件存儲的壓力。為提高現(xiàn)有三態(tài)內(nèi)容可尋此存儲器(TCAM)資源利用率，該文提出一種基于規(guī)則集特征分析的匹配域裁剪模型Field Trimmer。一方面基于對規(guī)則集中匹配域的邏輯關(guān)系分析，實(shí)現(xiàn)匹配域的合并, 從而減少匹配域的數(shù)量；另一方面基于對規(guī)則集統(tǒng)計(jì)規(guī)律的分析，實(shí)現(xiàn)匹配域的裁剪，使用部分匹配域來達(dá)到整體的匹配效果。實(shí)驗(yàn)結(jié)果表明，相比于其他方案，該方案在較小的時間復(fù)雜度下，能夠進(jìn)一步節(jié)省OpenFlow流表的TCAM存儲空間需求50%左右；對于常見的包分類規(guī)則集，該方案所需的儲存空間能夠節(jié)省40%以上。
- 包分類 /
- 三態(tài)內(nèi)容可尋此存儲器 /
- OpenFlow
Abstract: 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.
- Packet classification /
- Ternary Content Addressable Memory (TCAM) /
- OpenFlow

HTML全文

參考文獻(xiàn)(21)

MCKEOWN N. Software-defined networking[C]. INFOCOM Keynote Talk, Rio de Janero, Brazil, 2009: 30-32.

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.

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.

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.

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.

陳正虎, 蘭巨龍, 黃萬偉, 等. 一種基于Bloom-filter表項(xiàng)壓縮的TCAM業(yè)務(wù)識別算法[J]. 電子與信息學(xué)報(bào), 2011, 33(9): 2212-2218. doi: 10.3724/SP.J.1146.2011.00058.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)