Structural Analysis of Network Traffic Flows

Monday, January 12, 2004 - 9:30am - 10:20am
Keller 3-180
Mark Crovella (Boston University)
Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic matrix estimation, capacity planning, forecasting and anomaly detection. However, to date, OD flows have not been closely studied, and there is very little known about their properties. In this talk, I will present the first analysis of complete sets of OD flow timeseries, taken from two different backbone networks (Abilene and Sprint-Europe). Using Principal Component Analysis (PCA), we have found that the set of OD flows has small intrinsic dimension. In fact, even in a network with over a hundred OD flows, these flows can be accurately captured in time using a small number (10 or less) of independent components or dimensions.

I will then show how to use PCA to systematically decompose the structure of OD flow timeseries into three main constituents: common periodic trends, short-lived bursts, and noise. Such a decomposition provides insight into how the various constituents contribute to the overall structure of OD flows. Finally, I will explore the extent to which this decomposition varies over time.

This is a joint work with Anukool Lakhina, Konstantina Papagiannaki, Christophe Diot, Eric D. Kolaczyk and Nina Taft.