CMT: An Efficient Algorithm for Scalable Packet Classification. (26th March 2021)

• Record Type: Journal Article
• Authors: Chen, Shuhui; Zhong, Jincheng; Huang, Teng; Wei, Ziling; Zhao, Shuang
• Is Part Of: Computer journal. Volume 64:Number 6(2021)
• Page Start: 941
• Page End: 959
• Publication Date: 2021-03-26
• Subjects: packet classification -- common mask tree -- decision tree -- n-range matching -- SDN; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab005
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Packet classification plays an essential role in diverse network functions such as quality of service, firewall filtering and load balancer. However, implementing an efficient packet classifier is a challenging problem. The problem even gets worse in the era of software-defined network, in which frequent rule updates are performed, and complex flow tables are used. This paper proposes CMT, a new software algorithm named by its novel data structure—common mask tree—to implement an efficient multi-field packet classifier. The core idea of CMT is to combine the strengths of both decision-tree and tuple-space schemes by employing tree-like structures and hash tables simultaneously. The objective of CMT is to achieve both high classification performance and fast rule updates. In the evaluation section, CMT is compared with decision-tree and tuple-space schemes. Compared to the state-of-the-art decision-tree methods, CMT performs rule updates at two orders of magnitude faster. CMT has a stable performance on different rulesets and achieves a 40% improvement in memory access compared to the state-of-the-art tuple-space method.