Extended Journal Paper: FPGA-based Updatable Packet Classification using TSS-combined Bit-selecting Tree (IEEE/ACM Transactions on Networking, 2022)

  • Authors: Yao Xin, Wenjun Li*, Guoming Tang, Tong Yang, Xiaohe Hu, and Yi Wang
  • This work was conducted under the guidance of the corresponding author Wenjun Li (e-mail: wenjunli@pku.org.cn).

Abstract

OpenFlow switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. As a promising alternative to brutal force TCAMs, FPGA-based packet classification is being actively investigated. However, none of the existing FPGA designs can achieve high performance on both search and update for large-scale rule sets. To address this issue, we propose TcbTree, an FPGA-based algorithmic scheme for packet classification. Specifically, at the algorithmic side, i) a two-stage framework consisting of heterogeneous algorithms is proposed, where most rules can be mapped into several balanced trees without rule replications, ii) for the remaining few rules, a centralized TSS (Tuple Space Search) architecture together with a real-time feedback scheme is designed to enhance the efficiency of TSS search on FPGA, and iii) a tree dilution method is designed to equalize rule distribution in trees, so that the latency of tree search can be reduced. At the hardware side, i) an efficient data structure set is designed to convert tree traversal to addressing process, which breaks the constraints of limited tree depth and imbalanced node distribution, and ii) distinct from fully pipelined designs, multiple levels of parallelism are efficiently explored with multi-core, multi-search-engine and coarse-grained pipelines herein. Experimental results using ClassBench show that, with the implementation of TcbTree on FPGA, the average classification throughputs for 1k, 10k, 32k and 100k rule sets achieve 788.8 MPPS, 404.3 MPPS, 237 MPPS and 41.8 MPPS, respectively, and the update throughput for all benchmark rule sets is above 1 MUPS.



 

  TabTree: A TSS-assisted Bit-selecting Tree Scheme for Packet Classification with Balanced Rule Mapping (ACM/IEEE ANCS, 2019)

  • Authors: Wenjun Li*, Tong Yang, Yeim-Kuan Chang, Tao Li, and Hui Li
  • This work was conducted under the guidance of the corresponding author Wenjun Li (e-mail: wenjunli@pku.org.cn).

Abstract

To support fast rule updates in SDN, the Open vSwitch implements Priority Sorting Tuple Space Search (PSTSS) for its packet classifications. Although it has good performance on rule updates, it has a performance concern on table lookups. In contrast, decision tree methods are being actively investigated for high throughput, but they are not able to support fast updates because of rule replications. CutSplit, the state-of-the-art decision tree scheme, provides a novel rule update mechanism by avoiding tree reconstructions. However, its average update time is still two orders of magnitude larger than PSTSS. Meanwhile, existing decision trees are not only unbalanced but also depth unbounded, making them difficult to be optimized on FPGA. In this paper, we present a new decision tree scheme called TabTree, which achieves high performance on both lookups and updates. By mapping rules into tree nodes dynamically, a very limited number of balanced trees with bounded depths can be generated without the trouble of rule replications. Experimental results show that, TabTree has comparable update performance to PSTSS, but it outperforms PSTSS significantly in terms of number of memory accesses for packet classification. Additionally, TabTree is more practical for implementations on FPGA.

Downloads

News

2022.6.1: To help our readers to understand the proposed approach in details, the RTL codes of Algorithm 1 (i.e., rule insertion) and Algorithm 2 (i.e., rule deletion) have been uploaded.

2022.6.1: The extended journal paper of TabTree has been accepted by IEEE/ACM Transactions on Networking.

2019.11.11: Source code v1.0 has been uploaded.

2019.11.1: Paper and slides have been uploaded.

2019.10.15: The website of TabTree is under construction and will be finished soon.

Contact

E-mail: wenjunli@pku.org.cn, wenjun0816@qq.com.