EUVIMEDEUVIMED entdecken
Crossref

T2Tree: A Deterministic Algorithmic Framework for High-Speed Packet Classification

Yao Xin, Shufan Cao, Yuqiao Luo, Chuan Chen, Wenhao Jia, Jiangang Shu, Lingfeng Qu

IEEE Transactions on Network Science and Engineering · 2026 · 13 · 7880-7898

DOI: 10.1109/tnse.2026.3676491 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Network Science and Engineering, 2026. Verfasst von Yao Xin und 6 weiteren Autor:innen. Die Arbeit nennt 87 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Science and Technology Innovation Project of Guangdong.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Packet classification in high-speed networks requires hardware acceleration for line-rate processing, yet existing decision tree algorithms struggle to effectively harness hardware parallelism. This paper presents T2Tree, a hardware-centric algorithm that strategically distributes wildcard-heavy rules across tree nodes to maximize parallel processing. T2Tree’s key innovation lies in its hardware-aware rule distribution: by embedding wildcard-heavy rules throughout the hierarchy, it enables concurrent matching during traversal, potentially hiding latency within pipeline stages and achieving minimal overhead. The elimination of rule replication while maintaining full coverage allows T2Tree to dramatically reduce the number of decision trees required, making complete rule set implementation feasible within constrained on-chip resources. The algorithm features a unified framework that adapts to diverse rule sets without reconfiguration, a critical advantage for programmable hardware. Experimental results demonstrate significant improvements in throughput and memory efficiency compared to state-of-the-art approaches, while maintaining robust update performance. This hardware-software co-design is particularly suitable for FPGA-based accelerators and packet processing engines where deterministic latency, resource efficiency, and predictable memory usage are paramount.

Förderung

  • National Natural Science Foundation of China
  • Science and Technology Innovation Project of Guangdong

Zitieren

APA

Xin, Y., Cao, S., Luo, Y., Chen, C., Jia, W., Shu, J., & Qu, L. (2026). T2Tree: A Deterministic Algorithmic Framework for High-Speed Packet Classification. IEEE Transactions on Network Science and Engineering, 13, 7880-7898. https://doi.org/10.1109/tnse.2026.3676491

Vancouver

Xin Y, Cao S, Luo Y, Chen C, Jia W, Shu J, et al. T2Tree: A Deterministic Algorithmic Framework for High-Speed Packet Classification. IEEE Transactions on Network Science and Engineering. 2026;13:7880-7898. doi:10.1109/tnse.2026.3676491

BibTeX
@article{Xin2026,
  author = {Xin, Yao and Cao, Shufan and Luo, Yuqiao and Chen, Chuan and Jia, Wenhao and Shu, Jiangang and Qu, Lingfeng},
  title = {T2Tree: A Deterministic Algorithmic Framework for High-Speed Packet Classification},
  journal = {IEEE Transactions on Network Science and Engineering},
  year = {2026},
  volume = {13},
  pages = {7880--7898},
  doi = {10.1109/tnse.2026.3676491}
}
Kostenlos starten →