ITOC: An Improved Trie-Based Algorithm for Online Packet Classification

Applied Sciences

Jinlin Wang¹  Xiao Chen¹  Yifei Li¹  Jinghong Wu¹ 

[1] 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;

关键词: SDN;    SDN switch;    packet c;    update latency;   

DOI  :  10.3390/app11188693

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown