ITOC: An Improved Trie-Based Algorithm for Online Packet Classification
Source abstract
Abstract
With the development of SDN, packet classifiers nowadays need to be provided with low update latency besides fast lookup performance because switches need to respond to update control messages from controllers in time to guarantee real-time service in SDN implementations. Classification in this scenario is called online packet classification. In this paper, we put forward an improved trie-based algorithm for online packet classification (ITOC), in which we provide a trie selection strategy to avoid occasional high update latency in the update process of online trie-based algorithms. Experiments are conducted to validate the effectiveness of our optimization and compare the performance of ITOC with the offline methods, DPDK ACL. Experimental results demonstrate that ITOC has the same level of lookup speed with DPDK ACL and greatly decreased the update latency as well. The update latency of ITOC is only 6.85% of DPDK ACL library in the best case.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Network Packet Processing and Optimization · Network Security and Intrusion Detection · Internet Traffic Analysis and Secure E-voting
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences, No. 21, North Fourth Ring Road, Haidian District, Beijing 100190, China
School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, No. 19(A), Yuquan Road, Shijingshan District, Beijing 100049, China
Funding
Strategic Leadership Project of Chinese Academy of Sciences: SEANET Technology Standardization Research System Development
References (23)
Show source-provided references
1. Fast packet processing: A survey10.1109/COMST.2018.2851072 ↗
2. (2021, June 04). ONF—Open Network Foundation. Available online: http:/opennetworking.org/.
3. SEANet:Architecture and Technologies of an On-site, Elastic, Autonomous Network
4. DRES: Dynamic range encoding scheme for TCAM coprocessors10.1109/TC.2007.70838 ↗
5. TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs10.1109/TNET.2009.2030188 ↗
6. Meiners, C.R., Liu, A.X., Torng, E., and Patel, J. (2011, January 3–4). Split: Optimizing space, power, and throughput for TCAM-based classification. Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems, Brooklyn, NY, USA.10.1109/ANCS.2011.36 ↗
7. Exploiting order independence for scalable and expressive packet classification10.1109/TNET.2015.2407831 ↗
8. Ahmed, O., Areibi, S., and Fayek, D. (2010, January 11–14). PCIU: An efficient packet classification algorithm with an incremental update capability. Proceedings of the 2010 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’10), Ottawa, ON, Canada.
9. A scalable and modular architecture for high-performance packet classification10.1109/TPDS.2013.261 ↗
10. High-performance and dynamically updatable packet classification engine on FPGA10.1109/TPDS.2015.2389239 ↗
11. Classifying packets with hierarchical intelligent cuttings10.1109/40.820051 ↗
12. Singh, S., Baboescu, F., Varghese, G., and Wang, J. (2003, January 25–29). Packet classification using multidimensional cutting. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Karlsruhe, Germany.10.1145/863955.863980 ↗
13. EffiCuts: Optimizing packet classification for memory and throughput10.1145/1851275.1851208 ↗
14. Li, W., Li, X., Li, H., and Xie, G. (2018, January 16–19). Cutsplit: A decision-tree combining cutting and splitting for scalable packet classification. Proceedings of the IEEE INFOCOM 2018-IEEE Conference on Computer Communications, Honolulu, HI, USA.10.1109/INFOCOM.2018.8485947 ↗
15. Srinivasan, V., Suri, S., and Varghese, G. (September, January 30). Packet classification using tuple space search. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Cambridge, MA, USA.
16. Trie memory10.1145/367390.367400 ↗
17. Burst tries: A fast, efficient data structure for string keys10.1145/506309.506312 ↗
18. Yingchareonthawornchai, S., Daly, J., Liu, A.X., and Torng, E. (2016, January 8–11). A sorted partitioning approach to high-speed and fast-update OpenFlow classification. Proceedings of the 2016 IEEE 24th International Conference on Network Protocols (ICNP), Singapore.10.1109/ICNP.2016.7784429 ↗
19. Tuplemerge: Fast software packet processing for online packet classification10.1109/TNET.2019.2920718 ↗
20. Song, H. (2013, January 16). Protocol-oblivious forwarding: Unleash the power of SDN through a future-proof forwarding plane. Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, China.10.1145/2491185.2491190 ↗
21. (2021, June 04). DPDK. Available online: http://www.dpdk.org/.
22. Classbench: A packet classification benchmark10.1109/TNET.2007.893156 ↗
23. Matoušek, J., Antichi, G., Lučanskỳ, A., Moore, A.W., and Kořenek, J. (2017, January 18–19). Classbench-ng: Recasting classbench after a decade of network evolution. Proceedings of the 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), Beijing, China.10.1109/ANCS.2017.33 ↗