This talk is a summary of a half-day tutorial session by George Varghese
titled "Detecting Packet Patterns at High Speeds", held at SIGCOMM 2002.

The tutorial provided an introduction to a set of old and new problems
that must be solved for router line cards to operate at wire speeds. Line
cards need to be able to detect important patterns (e.g., Internet
lookups, packet classification, QoS enforcement, detecting
Denial-of-Service Attacks and port scans, maintaining packet counters) on
arriving packets. Any such processing must be completed within a packet
interarrival time (8 nsec at the highest link speeds today) and hence must
take a small number of memory references, and also store state in
limited-size high speed memories (analogous to cache or register
memory). Many of these problems may be easily solved if one had memory for
each flow but the number of flows appears to be much larger than the
amount of available SRAM. Therefore, these pattern detection algorithms
must use a small constant number of operations and a relatively modest
amount of state.

The presentation will consist of a brief discussion of the hardware models
that one should keep in mind while designing algorithms to accomplish such
tasks and a set of principles intended to aid the design of such schemes.
Then, we will move on to describing traditional router processing patterns
(IP lookups, packet classification, QoS). This will be followed by a
discussion of new processing patterns (security, accounting) and the
sampling and filtering techniques being considered for detecting such
patterns.