Performance Improvement of Hardware-Based Packet Classification Algorithm

Abstract. Packet classification is important in fulfilling the require-ments of differentiated services in next generation networks. In the pre-vious work, we presented an efficient hardware scheme, Condensate Bit Vector, based on bit vectors. The scheme significantly improves the scal-ability of packet classification. In this work, the characteristics of Con-densate Bit Vector are further illustrated, and two drawbacks that may negatively affect the performance of Condensate Bit Vector are revealed. We show the solution to resolve the weaknesses and introduce the new schemes, Condensate Ordered Bit Vector and Condensate and Aggregate Ordered Bit Vector. Experiments show that our new algorithms drasti-cally improve the search speed as compared to the original algorithm.