Efficient packet classification using spatial cutting

To provide a more discriminating form of packet forwarding, a router has to determine how to forward a packet not only based on the destination address, but also other fields of the packet header, such as the source address, TCP and UDP port numbers. Since a router may contain a larger number of filters, it is a challenging work to design a packet classification algorithm with fast lookup speed and efficient memory usage. In this paper, we propose a spatial cutting scheme, which divides the filters into different groups from the viewpoint of space. For example, a two-dimensional filter can be seen as a rectangle in the space. The proposed scheme generates squares according to the filters. Each filter is covered by at least one square. Classifying a packet only requires two steps: locating the smallest square covering the packet and finding the matching filter in the square. Since the proposed scheme effectively divides the filters, it is able to provide fast lookup speed and reduce the required storage significantly.