CMT: An Efficient Algorithm for Scalable Packet Classification. (26th March 2021)
- Record Type:
- Journal Article
- Title:
- CMT: An Efficient Algorithm for Scalable Packet Classification. (26th March 2021)
- Main Title:
- CMT: An Efficient Algorithm for Scalable Packet Classification
- Authors:
- Chen, Shuhui
Zhong, Jincheng
Huang, Teng
Wei, Ziling
Zhao, Shuang - 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.
- Is Part Of:
- Computer journal. Volume 64:Number 6(2021)
- Journal:
- Computer journal
- Issue:
- Volume 64:Number 6(2021)
- Issue Display:
- Volume 64, Issue 6 (2021)
- Year:
- 2021
- Volume:
- 64
- Issue:
- 6
- Issue Sort Value:
- 2021-0064-0006-0000
- 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 - Journal URLs:
- http://comjnl.oxfordjournals.org/ ↗
http://ukcatalogue.oup.com/ ↗ - DOI:
- 10.1093/comjnl/bxab005 ↗
- Languages:
- English
- ISSNs:
- 0010-4620
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.060000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 17319.xml