Multi-Dimensional Packet Classification Using Tuple Space Based on Bit-Parallelism

With the development of the Internet, routers must support extra functions such as packet filtering, QOS and traffic billing in addition to the routing lookup. The input packets should be processed at wire speed to meet these demands. Bit-Parallelism is a fast scheme for packet classification, but it scales poorly as the filter databases grow in size. In this paper, by taking the Bit-Parallelism scheme and introducing the ideas of bitmap mapping and tuple space, we present a new algorithm. The new algorithm reduces the complexities of both the time and space and it can scale well with the growth of the filter databases in size. At the end of this paper, we have realized the algorithm in a virtual environment and analyze the experimental data.