Packet classification on multiple fields
Pankaj Kumar Gupta, Nick McKeown · ACM SIGCOMM Computer Communication Review · 1999
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.
Cited by 317 works. doi:10.1145/316194.316217
Authors
References
- Random early detection gateways for congestion avoidance
- Analysis and simulation of a fair queueing algorithm
- A generalized processor sharing approach to flow control in integrated services networks: the single-node case
- Analysis and simulation of a fair queueing algorithm
- The BSD packet filter: a new architecture for user-level packet capture
- Efficient fair queuing using deficit round-robin
- Scalable high speed IP routing lookups
- High-speed policy-based packet forwarding using efficient multi-dimensional range matching
- Small forwarding tables for fast routing lookups
- Fast and scalable layer four switching