BiCuts: A fast packet classification algorithm using bit-level cutting 2019/5/8 BiCuts: A fast packet classification algorithm using bit-level cutting Authors :Zhi Liu,Shijie Sun,Hang Zhu,Jiaqi Gao ,Jun Presenter : Yi-Fang, Huang Conference :  Computer Communications volume109(September 2017) 1 CSIE CIAL Lab

2019/5/8 Introduction This paper proposes BitCuts, a decision-tree algorithm that performs bit-level cutting. The contributions of this paper are summarized as follows: “Bit-level cut” is able to zoom into densely clustered rule space and cut at the right granularity, which avoids unnecessary partitions and excessive memory consumption. BitCuts uses parallel bitindexing to support fast child-node traversal and enable large node fanout. For 5-tuple rules, the child-node indexing can be implemented by two bit-manipulation instructions, achieving ultra-fast decision-tree traversal. 由於FPGA的可重複改寫的特性和高頻寬介面，使FPGA成為發展網路架構的選擇。 但是，它們的有限內存限制了可以存儲在芯片內部的information，並且off chip memory通常太慢以至於不能滿足高速網絡的需求。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/5/8 Motivations The distribution of rules greatly impacts the decision-tree met- rics and is an important consideration in the algorithm design. Therefore, an in-depth study of the ruleset distribution is made. The real-world rulesets, which contain rules for ACL (Access Control), FW (Firewall), and IPC (IP Chain). Small ranges are co-located Wildcard rules overlap with small ranges Example : ACLRuleset 753 rules 由於FPGA的可重複改寫的特性和高頻寬介面，使FPGA成為發展網路架構的選擇。 但是，它們的有限內存限制了可以存儲在芯片內部的information，並且off chip memory通常太慢以至於不能滿足高速網絡的需求。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/5/8 The Bitcuts overview we provide an overview of BitCuts by introducing its two stages: offline preprocessing and online classification Offline preprocessing Online classification 過濾幾個數據包時，所有通過link的數據包必須檢查filter為 正常運行的 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Bit-selection algorithm 2019/5/8 Bit-selection algorithm 過濾幾個數據包時，所有通過link的數據包必須檢查filter為 正常運行的 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/5/8 The Bitcuts overview 過濾幾個數據包時，所有通過link的數據包必須檢查filter為 正常運行的 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Bit-selection algorithm 2019/5/8 Bit-selection algorithm Bit indexing In BitCuts, bit indexing is implemented by PEXT(Parallel Bits Extract) instruction PEXT is included in the BMI2 instruction set, which was intro- duced with the Intel Haswell processor, and currently is supported by a wide range of processors The instruction takes only 3 cycles and supports data length of 64 bits on Intel 64 architecture . For 5-tuple header (104 bits), the bit indexing takes up to 2 PEXT operations, which is far more efficient than “shift and compare”and enables fast lookup for BitCuts decision trees. 過濾幾個數據包時，所有通過link的數據包必須檢查filter為 正常運行的 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

BitCuts lookup procedure 2019/5/8 BitCuts lookup procedure 過濾幾個數據包時，所有通過link的數據包必須檢查filter為 正常運行的 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Evaluation BINT H = 8 and spfac = 4 2019/5/8 Evaluation BINT H = 8 and spfac = 4 The rulesets generated by ClassBench 如果user指定了某個pad(Pcap中某個Packet段)，則它將包含在模塊頭中 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/5/8 Evaluation 如果user指定了某個pad(Pcap中某個Packet段)，則它將包含在模塊頭中 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/5/8 Evaluation The ruleset ACL10K is used to test the throughput of the decision-tree lookup. The testbed is set up on two HP Z228 work- stations, each with a 4-core Intel Xeon Processor E3-1225 CPU, 20 GB memory, and an X710 NIC with two 10 Gbps ports. The packet size of the testing traffic is 64 bytes. 如果user指定了某個pad(Pcap中某個Packet段)，則它將包含在模塊頭中 BitCuts achieves about 2.1 ×the throughput of HyperSplit, 2.0 ×that of HyperCuts and 2.2 ×that of EffiCuts. National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab