Internet Packet Classification Using Prefix-Based Bitmap Intersection

Internet Packet Classification Using Prefix-Based Bitmap Intersection

Abstract

Packet classification is a central function for a number of network applications, such as routing, Quality of Service (QoS) provisioning and policy-based firewall deployment. A packet classifier categorizes incoming packets into specific flows, service classes or aggregates according to predefined rules. All packets belonging to the same flow obey a pre-defined rule and are processed in a similar manner by the router. Classification may, in general, be based on an arbitrary number of fields in the packet header. Performing classification on an arbitrary number of fields is known to be difficult, and has poor worst-case performance. Although there are significant previous works in this area, existing algorithms for packet classification reported in the literature scale poorly in either time or space as classifier grows in size. In this paper we propose a new method called Prefix-Based Bitmap Intersection (PBBI) which exploits some characteristics of actual classification rules to reduce memory consumption and classification time of previous methods. Mathematical evaluation and experimental results indicate a considerable performance improvement. It has been shown that our approach consumes memory less than previous work and has lower classification time. This makes our method suitable for implementing actual classifier even when the rule database grows largely.

References