A scalable hardware solution for packet classification

One of interesting hardware solutions proposed to solve the packet classification problem is bit-vector algorithm. Different from other hardware solutions such as ternary CAM, it efficiently utilizes the memories to achieve an excellent performance in medium size policy database; however, it cannot scale up with the policy number increases. In this paper, we proposed an improved bit-vector algorithm named Bit Vector Condensation which can be adapted to large policy databases. Experiments showed that our proposed algorithm drastically improves in the storage requirements and search speed as compared to the original algorithm.