Dynamic field skipping Aggregated Bit Vector (DFSABV) Algorithm For Optimized Search

In this paper, we explore the optimization of decomposition-based packet classification algorithms by leveraging the Aggregated Bit Vector (ABV) algorithm. Decomposition-based algorithms use either 8 or 16-bit lookup to search packet field values in the rule database by breaking down the field values into smaller chunks. By selectively skipping specific field bytes in search database, we enhance the classification speed. Our solution incorporates both static and dynamic field skipping approaches, customized to the given rule dataset. Static field skipping reduces memory usage and optimizes rule update performance, but may experience efficiency loss due to updates in rule dataset. To address this, we introduce dynamic field skipping that adapts to such scenarios and modifies the skipped fields dynamically. Additionally, we develop an algorithm to monitor the effectiveness of our solution in terms of number of fields to be skipped. If the classification speed does not meet expectations, our algorithm automatically adjusts the configuration of skipped fields for improved efficiency. Overall, we achieve approximately $\mathbf{1 0 - 4 0 \%}$ search optimization across various scenarios compared to original ABV. Our solution framework can be extended to almost all decomposition-based packet classification algorithms, demonstrating its potential to optimize classification speed of those algorithms apart from ABV.