EUVIMEDEUVIMED entdecken
Crossref

Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGA

Yao Xin, Wenjun Li, Chengjun Jia, Xianfeng Li, Yang Xu, Bin Liu, Zhihong Tian, Weizhe Zhang

IEEE/ACM Transactions on Networking · 2024-04 · 32 (2) · 1707-1722

DOI: 10.1109/tnet.2023.3330381 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE/ACM Transactions on Networking, 2024-04. Verfasst von Yao Xin und 7 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 77 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China, Key-Area Research and Development Program of Guangdong.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

As a programmable accelerator, SmartNIC provides more opportunities for algorithmic packet classification. Our aim in this work is to achieve both line-speed rule search and efficient rule update, two highly desired metrics for SDN data plane. We leverage the parallelism offered by the FPGA in SmartNIC following an algorithm/hardware co-design paradigm. Particularly, we first design an algorithm that constructs multiple trees for the rule set with a recursive rule sifting process. Unlike traditional space-cutting-based multi-tree construction, our rule sifting mechanism breaks the space constraints of rule-to-tree mapping and enables bounded height on each tree, thus providing the potential of bounded worst-case and line-speed performance. We then design a flexible hardware architecture with multiple systolic arrays that can be implemented in parallel on FPGA. Each systolic array works as a coarse-grained pipeline, and the multiple trees constructed earlier will be mapped onto these pipeline stages. This hardware-software mapping enables bounded worst-case rule searching. Additionally, incremental rule update is achieved simply by traversing the pipeline in one pass, with little and bounded impact on rule searching. Experimental results show that our design achieves an average classification throughput of 600.8/147.5 MPPS and an update throughput of 8.2/5.9 MUPS for 10k/100k-scale 5-tuple and OpenFlow rule sets.

Förderung

  • National Key Research and Development Program of China
  • National Natural Science Foundation of China
  • Key-Area Research and Development Program of Guangdong
  • Major Key Project of Peng Cheng Laboratory
  • 173 Program of China
  • China Postdoctoral Science Foundation

Zitieren

APA

Xin, Y., Li, W., Jia, C., Li, X., Xu, Y., Liu, B., Tian, Z., & Zhang, W. (2024). Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGA. IEEE/ACM Transactions on Networking, 32(2), 1707-1722. https://doi.org/10.1109/tnet.2023.3330381

Vancouver

Xin Y, Li W, Jia C, Li X, Xu Y, Liu B, et al. Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGA. IEEE/ACM Transactions on Networking. 2024;32(2):1707-1722. doi:10.1109/tnet.2023.3330381

BibTeX
@article{Xin2024,
  author = {Xin, Yao and Li, Wenjun and Jia, Chengjun and Li, Xianfeng and Xu, Yang and Liu, Bin and Tian, Zhihong and Zhang, Weizhe},
  title = {Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGA},
  journal = {IEEE/ACM Transactions on Networking},
  year = {2024},
  volume = {32},
  number = {2},
  pages = {1707--1722},
  doi = {10.1109/tnet.2023.3330381}
}
Kostenlos starten →