Internet Traffic Measurement: From Packets to Insight

One of the main reasons for the success of the internet is its service model that emphasizes flexibility. While this freedom enabled the widespread deployment of the applications popular today such as email and Web, it has also greatly complicated the task of administering these networks. To understand how a network is being used, or whether it is being abused, an administrator must inspect the flow of packets and "infer" the intent of users and applications. Existing measurement solutions either lack the necessary detail, do not scale up to the speeds of today's networks or are not flexible enough to keep up to the speeds of today's networks or are not flexible enough to keep up with the ever changing traffic mix. I will present two approaches to improve the state of the art.

My first approach is to develop fast and accurate algorithmic building blocks that allow routers to collect better measurement data. For example, it is often necessary to identify large flows of traffic, the "heavy hitters". I will present multistage filters which quickly and scalably identify heavy-hitters. A second useful building block scalably estimates the number of active flows or IP addresses using a family bitmap algorithms. I will show theoretical and experimental evaluations of the effectiveness of these building blocks.

My second approach is to improve the flexibility of offline analysis through a new method of traffic characterization. The conventional approach is a static analysis specialized to capture flows, applications, or network-to-network traffic matrices. By contrast, my analysis dynamically and automatically produces hybrid traffic definitions that match the underlying usage. I will describe a publicly available tool called AutoFocus that I built to implement this analysis, and its use on various production networks to infer such varied phenomena as new worms, denial of service attacks, routing changes, and traffic periodicities.