A packet classification and filter management system

Abstract

Packet classification and fast filter matching have been an important field of research. Several algorithms have been proposed for fast packet classification. We first present a new filter matching scheme called entry-pruned tuple search and discuss its advantages over previously presented algorithms. We then show how this algorithm blends very well with an earlier packet classification algorithm that uses markers and precomputation, to give a blended entry-pruned tuple search with markers and precomputation (EPTSMP). We present performance measurements using several real-life filter databases. For a large real-life database of 1777 filters, our preprocessing times were close to 9 seconds; a lookup takes about 20 memory accesses and the data structure takes about 500 K bytes of memory. Then, we present scenarios that will require various programs/modules to automatically generate and add filters to a filter processing engine. We then consider issues in enabling this. We need policies that govern what filters can be added by different modules. We present our filter policy management architecture. We then show how to support fast filter updates. We present an incremental update algorithm based on maintaining an event list that can be applied to many of the previously presented filter matching schemes which did not support incremental updates. We then describe the event list based incremental update algorithm as it applies to EPTSMP. To stress the generality of the approach, we also describe how our update technique can be used with the packet classification technique based on crossproducing. We conclude with an outline of a hardware implementation of EPTSMP that can handle OC192 rates with 40 byte minimum packet lengths.