Traffic matrix tracking using Kalman filters

ABSTRACT

In this work we develop a new approach to monitoring origin-destination flows in a large network. We start by building a state space model for OD flows that is rich enough to fully capture temporal and spatial correlations. We apply a Kalman filter to our linear dynamic system that can be used for both estimation and prediction of traffic matrices. We call our system a traffic matrix tracker due to its lightweight mechanism for temporal updates that enables tracking traffic matrix dynamics at small time scales. Our Kalman filter approach allows us to go beyond traffic matrix estimation in that our single system can also carry out traffic prediction and yield confidence bounds on the estimates, the predictions and the residual error processes. We show that these elements provide key functionalities needed by monitoring systems of the future for carrying out anomaly detection. Using real data collected from a Tier-1 ISP, we validate our model, illustrate that it can achieve low errors, and that our method is adaptive on both short and long timescales.

REFERENCES

• 1: CISCO. Netflow services and applications, 2002.
• 2: T. Kailath, A. H. Sayed, B. Hassibi, A. H. Sayed, and B. Hassibi. Linear Estimation. Prentice Hall, 2000.
• 3: Anukool Lakhina , Mark Crovella , Christophe Diot, Diagnosing network-wide traffic anomalies, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: Konstantina Papagiannaki , Nina Taft , Anukool Lakhina, A distributed approach to measure IP traffic matrices, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028808]
• 6: R. Shumway and D. Stoffer. Dynamic linear models with switching. Journal of the the American Statistical Association, 86, 1991.
• 7: Augustin Soule , Anukool Lakhina , Nina Taft , Konstantina Papagiannaki , Kave Salamatian , Antonio Nucci , Mark Crovella , Christophe Diot, Traffic matrices: balancing measurements, inference and modeling, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 8: Augustin Soule , Antonio Nucci , Rene Cruz , Emilio Leonardi , Nina Taft, How to identify and estimate the largest traffic matrix elements in a dynamic environment, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 9: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Design, Management, Measurement, Performance, Theory