Packet classification on multiple fields

TLDR

Routers classify packets to identify their flow and assign service, but doing so quickly across an arbitrary number of header fields is difficult and suffers from poor worst‑case performance. The study examines classifiers from real networks. We discover that real‑world classifiers exhibit structure and redundancy that can be exploited, enabling a simple multi‑stage algorithm (RFC) to process 30 million packets per second in pipelined hardware or one million per second in software.

Abstract

Routers classify packets to determine which flow they belong to, and to decide what service they should receive. Classification may, in general, be based on an arbitrary number of fields in the packet header. Performing classification quickly on an arbitrary number of fields is known to be difficult, and has poor worst-case performance. In this paper, we consider a number of classifiers taken from real networks. We find that the classifiers contain considerable structure and redundancy that can be exploited by the classification algorithm. In particular, we find that a simple multi-stage classification algorithm, called RFC (recursive flow classification), can classify 30 million packets per second in pipelined hardware, or one million packets per second in software.