KickTree: A Recursive Algorithmic Scheme for Packet Classification with Bounded Worst-Case Performance

Xin，Yao1; Liu，Yuxi2; Li，Wenjun1,3; Yao，Ruyi4; Xu，Yang4; Wang，Yi2

10.1145/3493425.3502752

2021-12-13

ANCS 2021 - Proceedings of the 2021 Symposium on Architectures for Networking and Communications Systems

23-30

As a promising alternative to TCAM-based solutions for packet classification, FPGA has received increasing attention. Although extensive research has been conducted in this area, existing FPGA-based packet classifiers cannot satisfy the burgeoning needs from OpenFlow, which demands large-scale rule sets and frequent rule updates. As a recently proposed hardware-specific approach, TabTree avoids rule replication and supports dynamic rule update. However, it still faces problems of unbalanced rule subset partition, unevenly distributed subtrees and excessive TSS leaf nodes when implemented on FPGA. In this paper, we propose a hardware-friendly packet classification approach called KickTree, which is elaborated by considering hardware properties. To take advantage of intrinsic parallelism of FPGA, KickTree adopts multiple balanced decision trees which can run simultaneously. The bit selection is more flexible which breaks the restriction of rule subset. Moreover, each subset size is strictly limited, leading to bounded and evenly-distributed

decision tree FPGA packet classification SDN

其他

英语

EI

20220611603644

Field programmable gate arrays (FPGA) ; Logic gates

Logic Elements:721.2 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Systems Science:961

2-s2.0-85124137706

Scopus

1.Peng Cheng Laboratory,Shenzhen,China
2.Southern University of Science and Technology,Shenzhen,China
3.Harvard University,United States
4.Fudan University,Shanghai,China

Xin，Yao,Liu，Yuxi,Li，Wenjun,et al. KickTree: A Recursive Algorithmic Scheme for Packet Classification with Bounded Worst-Case Performance[C],2021:23-30.