Research On Optimization Technology Of Bit-Vector-Based Packet Classification

High-performance packet classification algorithms have been widely studied during the past decade.With the rapid growth of link-speed,FPGA is widely used in real-time network processing because of its high performance and programmability.The BitVector-based(BV-based)packet classification algorithms proposed for FPGA can achieve high throughput through the fine-grained decomposition of rules.Recently,the new network architecture SDN has attracted continuous attention because of its high flexibility.Packet classification of SDN is also one core function,which requires high performance,supporting plenty of matching fields and fast rule updates.However,the increasing number of matching fields and rules have challenged the limited resources of FPGAs.Meanwhile,the existing BV-based packet classification algorithms can hardly support the fast rule updates for large-scale rulesets.The update latency of these algorithms increases exponentially with the number of rules.To solve the above problems,this paper studies the optimization techniques of the BV-based packet classification algorithms.Our contributions in this work include:1.A BV-baesd packet classification technique named WeeBV(Wildcard-removed Bit-Vector)for memory optimization.The resource consumption of FPGA is saved by eliminating useless wildcards in the rules.WeeBV consists of a heterogeneous twodimensional matching pipeline and an optimized heuristic algorithm that search almost all removable wildcard positions.WeeBV can significantly reduce memory consumption without damaging the high throughput of the original algorithm.2.A BV-based packet classification technique named Spli BV(Splitting Bit-Vector)for update latency optimization.The original ruleset is splitted into parallel matching subrulesets by several distinguishable bits,thus reducing the worst-case update latency.SplitBV consists of a hybrid matching pipeline and a constrained recursive splitting algorithm that select bits for optimal solution.With the negligible growth of memory consumption,SplitBV significantly reduces worst-case update latency.3.The prototype systems of WeeBV and SplitBV were implemented and evaluated through simulation.The results show that,for the synthesized 5-tuple rules and Open Flow rules,WeeBV can save 37% and 41% of memory consumption on average,and SplitBV can reduce update latency by 71% and 37% on average.In summary,to solve the drawbacks of the existing BV-based packet classification algorithms,this paper proposes two optimization techniques to satisfy the memory consumption or update latency requirements for different network application scenarios.