NXG05-4: Fast Packet Classification using Group Bit Vector

Packet classification is important in fulfilling the requirements of new services such as policy-based routing in next generation networks. In this paper, we propose a novel bit vector based two-dimensional packet classification algorithm called Group Bit Vector. The key feature of the proposed algorithm is its ability to set the length of the bit vector to perform AND operation (the operation bit vector) regardless of the size of rule databases by effectively aggregating the rules and constructing particular groups of a limited number of members. Moreover, the proposed algorithm avoids the problem of false matches, which may be brought by rules aggregation. Thus, the length of the operation bit vector can be adjusted to be suitable to the width of memories to improve the performance. Experimental results demonstrate the flexibility and effectiveness of the proposed algorithm.