Optimization study of a packet classification algorithm

Packet classification is a central function in filtering systems such as firewalls or intrusion detection mechanisms. Several mechanisms for fast packet classification have been proposed. But, existing algorithms are not always scalable to large filters databases in terms of search time and memory storage requirements. In this paper, we present a novel multifields packet classification algorithm based on an existing algorithm called PACARS and we show its advantages compared to previously proposed algorithms. We give performance measurements using a publicly available benchmark developed at Washington University. We show how our algorithm offers improved search times without any limitation in terms of incremental updates.