Abstract
Emerging real-time and multimedia applications require quality of service (QoS) guarantees. The packet classifier in next-generation routers is an essential component in QoS provisioning. It is responsible for classifying incoming packets into distinct flows or differential service-classes according to pre-defined rules. A classification rule contains multiple fields, including source and destination addresses, source and destination ports, and protocol type, etc. Generally speaking, address fields are prefix-defined and port fields are range-defined. In order to simplify the complex packet classification (PC) problem, many published papers [8-11] do not deal with ranges and assume all fields are prefixes. The transformation between range and prefix is possible. However, this will result in the memory explosion. In this article, we develop an efficient two-stage packet classification algorithm. The first stage classifies packets by using prefix fields and the second one distinguishes them by using range fields. Our algorithm can save memory significantly since the range is not converted into prefixes. Experimental results indicate that we reduce 95% of the storage space in comparison with the conventional Hierarchical Tries (H-Tries). Furthermore, our solution demonstrates significant faster lookup time than the conventional one for numerous rules.