Detecting Packet Patterns at High Speeds
George Varghese
University of California, San Diego
(Half Day - Day 1 PM)

Content:

This tutorial provides 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.

This tutorial will start with a set of models intended to introduce hardware design issues (on chip SRAMs, busses, pins, interleaved memories etc.) and a set of principles intended to help the audience think about new router problems. We will then delve into details of the best known solutions for detecting a variety of traditional router processing patterns (IP lookups, packet classification, QoS) and then move on to important new processing patterns in security (e.g., DOS attack detection, accounting). We will also briefly contrast network and traditional processor architectures. We will not cover switch design.

Intended Audience:

This tutorial is intended for students and implementers who would like to:

· Understand the issues that affect what can and cannot be implemented in router line cards
· Understand the state of the art for many traditional line card processing tasks
· Explore a space of new ideas for newer processing tasks
· Learn to think from a combination of architectural, system and algorithmic viewpoints about further router processing tasks the audience may encounter in their research or jobs

Speaker's Biography:

GEORGE VARGHESE worked at DEC for several years designing DECNET protocols before obtaining his Ph.D in 1992 from MIT. He joined Washington University in 1993 as an Associate Professor where he won the ONR Young Investigator Award in 1996. He is currently a Professor at the University of California, San Diego where he works on efficient protocol implementation and protocol design. Several of the algorithms he has helped develop (e.g., IP Lookups, timing wheels, DRR) have found their way into commercial systems that range from HotMail to the Cisco GSR Router.