Friday, July 26, 2002
U. California, San Diego
Detecting Traffic Patterns at High Speeds in Routers
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 (to appear in SIGCOMM 2002). 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, related problems such as detecting port scans, some lower bounds, and connections with fields such as databases (e.g., iceberg queries), streaming algorithms in theory, and communication complexity.