I. Introduction
Packet classification is indispensable for the Internet routers to provide the quality of services. Packet classification is to classify incoming packets into flows based on pre-defined rules so that routers can treat each packet according to the service defined in the class that the input packet belongs to [1]. Classes are defined by rules composed of multiple header fields, mainly destination prefix, source prefix, destination port number, source port number, and protocol type. Each field requires different matching operations such as the exact matching for the protocol type, prefix matching for prefixes, and range matching for port numbers. The difficulty in the packet classification is that it not only involves complicated matching operations but also has to identify the highest priority rule among all matching rules. Moreover, the packet classification should be performed in real-time for every packet incoming in several million packets per second, and hence the search speed is the major concern of the packet classification. This letter proposes a new packet classification scheme providing high throughput and low memory requirement.