12:45PM, Thursday, October 28th 2004.
Gates 104

 Traffic Matrix Estimation and Tracking

Antonio Nucci
Sprintlabs, Burlingame, CA

About the talk:
In this talk we present new methods for estimating and tracking a  traffic matrix for IP Networks.
The first part of the talk is focused on the estimation of the traffic  matrix. We investigate a new idea that makes the basic  problem less under-constrained, by deliberately changing the routing to obtain additional measurements. Because all these measurements are collected over disparate time intervals, we need to establish models for each Origin-Destination (OD) pair to capture the complex behaviors of internet traffic. We model each OD pair with two components: the diurnal pattern and the fluctuation process. We provide models that incorporate the two components above, to estimate both the first and second order moments of traffic matrices. We do this both for stationary and cyclo-stationary traffic scenarios. We formalize the problem of estimating the second order moment in a way that is completely independent from the first order moment. Moreover, we can estimate the second order moment without needing any routing changes for any realistic topology under the assumption of ``minimum cost routing'' and "strictly positive link weights".  We highlight how the second order moment helps the identification fraction of network traffic. We then propose a refined methodology consisting of using our variance estimator to identify the top largest flows, and estimate only these flows. The benefit of this method is that it dramatically reduces the number of routing changes needed.
In the second part of the talk we present a novel approach to monitoring OD flows. We start by building a state-space model for OD flows that is rich enough to fully capture temporal and spatial correlations. Our model enables a thorough analysis of OD flows and allows us to formalize a definition for "normal" behavior. We apply a Kalman Filter to our linear dynamic system and we show how this approach track the traffic matrix dynamics at small time scales and detects its deviation from the normal behavior.
We validate the effectiveness of our methodologies and the intuitions behind them by using real aggregated sampled Netflow data collected from a commercial Tier-1 backbone.

About the speaker:
Antonio Nucci received the MS and PhD degrees in Electrical Engineering from Politecnico di Torino, Italy in 1998 and 2002. Since September 2001 he has been a member of the IP Group at Sprintlabs, Burlingame, CA. His research interests are in the design and availability of communication networks, traffic engineering and performance analysis of IP Networks.