Detecting Traffic Patterns at High Speeds in Routers

George Varghese
University of California at San Diego

In this talk I will describe research into detecting traffic patterns
in real-time in Internet Routers. Any such processing must be done in
a packet arrival time (8 nsec at the highest link speeds today) and
hence must take a small number of memory references, and also store
state in high speed memories (analogous to cache or register memory)
that are limited in size. The problem is to detect important patterns
(e.g., Internet lookups, Denial-of-Service Attacks) in a small
constant number of operations using a relatively modest amount of
state. I will concentrate on two scalable measurement schemes
(IMW 2001). The scalable measurement algorithms show how to quickly
process a traffic stream to identify the customers that send more than
a threshold (e.g., 1% of the total bandwidth) using memory only
proportional to the maximum number of such customers (e.g., 100). Our
new methods have a relative error that scales inversely with the amount
of memory available, unlike schemes based on classical sampling where the
error scales inversely with the square root of available memory. I will
also briefly describe the problem of scalably counting the number of flows
using a small amount of memory, and related problems such as detecting
port scans.


Back to Long Programs