Packet Classification Algorithms

A curated collection of packet classification algorithms and their papers (2018–2026), including CutSplit, PartitionSort, TupleMerge, TabTree, CutTSS, MultilayerTuple, DynamicTuple, HybridTSS, PT-Tree, DBTable, KSet, and TupleTree-Compress, plus the ClassBench / ClassBench-NG benchmark tools. Sorted by publication year (oldest to newest).

---

Table of Contents

#	Algorithm	Type	Venue	Year
1	CutSplit	Decision Tree (Cut + Split)	IEEE INFOCOM	2018
2	PartitionSort	Hybrid TSS + Decision Tree	IEEE/ACM ToN	2018
3	TupleMerge	Merged Tuple Space	IEEE/ACM ToN	2019
4	TabTree	TSS-assisted Bit-selecting Tree	ACM/IEEE ANCS	2019
5	CutTSS	Decision Tree + TSS Hybrid	IEEE JSAC	2020
6	MultilayerTuple	Multi-layer Tuple Space	IEEE ICCCN	2021
7	DynamicTuple	Dynamic Adaptive Tuple	Computer Networks	2022
8	HybridTSS	Coarse/Fine-grained TSS Hybrid	APNet (ACM)	2022
9	PT-Tree	Cascading Prefix Tuple Tree	IEEE/ACM ToN	2024
10	DBTable	Discriminative Bitset Hash Table	IEEE/ACM ToN	2024
11	KSet	Hierarchical Hash Multi-field	IEEE Access	2025
12	TupleTree-Compress	Compressed Hash-based Decision Tree	Computer Networks	2026
—	ClassBench / ClassBench-NG	📦 Benchmark Tools	IEEE/ACM ToN · ANCS	2007 / 2017

MultilayerTuple, DynamicTuple, PT-Tree, DBTable, and KSet are the five core classifiers integrated in the AMPS (Adaptive Multi-Classifier Packet System) framework.

---

CutSplit

GitHub	https://github.com/wenjunpaper/CutSplit
Paper	CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification
Venue	IEEE INFOCOM 2018
Authors	Wenjun Li, Xianfeng Li, Hui Li et al.
Links	IEEE Xplore · Project

---

PartitionSort

GitHub	https://github.com/sorrachai/PartitonSort
Paper	A Sorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification
Venue	IEEE/ACM Transactions on Networking, 2018
Authors	Sorrachai Yingchareonthawornchai, James Daly, Alex X. Liu et al.
Links	IEEE Xplore

---

TupleMerge

GitHub	https://github.com/drjdaly/tuplemerge
Paper	TupleMerge: Fast Software Packet Processing for Online Packet Classification
Venue	IEEE/ACM Transactions on Networking, 2019
Authors	James Daly, Valerio Bruschi, Leonardo Linguaglossa et al.
Links	IEEE Xplore

---

TabTree

GitHub	https://github.com/wenjunpaper/TabTree
Paper	TabTree: A TSS-assisted Bit-selecting Tree Scheme for Packet Classification with Balanced Rule Mapping
Venue	ACM/IEEE ANCS 2019
Authors	Wenjun Li, Tong Yang, Yeim-Kuan Chang et al.
Links	IEEE Xplore · Project

---

CutTSS

GitHub	https://github.com/wenjunpaper/CutTSS
Paper	Tuple Space Assisted Packet Classification With High Performance on Both Search and Update
Venue	IEEE Journal on Selected Areas in Communications (JSAC), 2020
Authors	Wenjun Li, Tong Yang, Ori Rottenstreich et al.
Links	IEEE Xplore · Project

---

MultilayerTuple

GitHub	https://github.com/zcy-ict/MultilayerTuple
GitHub (AMPS)	https://github.com/JiaChangGit/amps/tree/main/src
Paper	MultilayerTuple: A General, Scalable and High-performance Packet Classification Algorithm for Software Defined Network System
Venue	IEEE ICCCN 2021
Authors	Chunyang Zhang, Gaogang Xie
Links	IEEE Xplore

---

DynamicTuple

GitHub	https://github.com/zcy-ict/DynamicTuple
GitHub (AMPS)	https://github.com/JiaChangGit/amps/tree/main/src
Paper	DynamicTuple: The Dynamic Adaptive Tuple for High-Performance Packet Classification
Venue	Computer Networks, 2022
Authors	Chunyang Zhang, Gaogang Xie, Xin Wang
Links	ScienceDirect

---

HybridTSS

GitHub	https://github.com/wenjunpaper/HybridTSS
Paper	HybridTSS: A Recursive Scheme Combining Coarse- and Fine-Grained Tuples for Packet Classification
Venue	APNet 2022
Authors	Yuxi Liu, Yao Xin, Wenjun Li et al.
Links	ACM DL · Project

---

PT-Tree

GitHub	https://github.com/lavline/PT-Tree
GitHub (AMPS)	https://github.com/JiaChangGit/amps/tree/main/src
Paper	PT-Tree: A Cascading Prefix Tuple Tree for Packet Classification in Dynamic Scenarios
Venue	IEEE/ACM Transactions on Networking, 2024
Authors	Zhengyu Liao, Shiyou Qian, Zhonglong Zheng et al.
Links	IEEE Xplore · ACM DL

---

DBTable

GitHub (AMPS)	https://github.com/JiaChangGit/amps/tree/main/src
Paper	DBTable: Leveraging Discriminative Bitsets for High-Performance Packet Classification
Venue	IEEE/ACM Transactions on Networking, 2024
Authors	Zhengyu Liao, Shiyou Qian, Zhonglong Zheng et al.
Links	IEEE Xplore

---

KSet

GitHub (AMPS)	https://github.com/JiaChangGit/amps/tree/main/src
Paper	Efficient Hierarchical Hash-Based Multi-Field Packet Classification with Fast Update for Software Switches
Venue	IEEE Access, 2025
Authors	Yeim-Kuan Chang, Yu-Hung Lin, Jia-Chang Chang et al.
Links	IEEE Xplore

---

TupleTree-Compress

GitHub	https://github.com/daveMmd/TupleTree-Compress/
Paper	TupleTree-Compress: Accelerating Hash-Based Packet Classification via Extreme Node Compression
Venue	Computer Networks, 2026
Authors	Jincheng Zhong, Tao Li, Gaofeng Lv et al.
Links	ScienceDirect
Base Algorithm	TupleTree — IEEE Transactions on Network and Service Management, 2023 · IEEE Xplore

---

ClassBench / ClassBench-NG

Standard benchmark tools for generating synthetic rule sets and packet traces used in packet classification research.

	ClassBench	ClassBench-NG
GitHub (integrated)	https://github.com/JiaChangGit/classbench-packet-classification	same (includes ng subdirectory)
Official GitHub	(hosted at WUSTL)	https://github.com/classbench-ng/classbench-ng
Paper	ClassBench: A Packet Classification Benchmark	ClassBench-ng: Recasting ClassBench After a Decade of Network Evolution
Venue	IEEE/ACM Transactions on Networking, 2007	ACM/IEEE ANCS 2017
Authors	David E. Taylor, Jonathan S. Turner	J. Matoušek, G. Antichi, A. Lučanský et al.
Links	ACM DL	ResearchGate · Project

ClassBench-NG extends the original (unmaintained) ClassBench with support for IPv6 and OpenFlow 1.0 rule generation, and improves IPv4 generation accuracy.