An information-theoretic approach to traffic matrix estimation

By Yin Zhang, Matthew Roughan, Carsten Lund, David L. Donoho. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2003

330 citations recorded by the source corpus.

Traffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure these matrices directly, and so there has been recent interest in inferring traffic matrices from link measurements and other more easily measured data. Typically, this inference problem is ill-posed, as it involves significantly more unknowns than data. Experience in many scientific and engineering fields has shown that it is essential to approach such ill-posed problems via "regularization". This paper presents a new approach to traffic matrix estimation using a regularization based on "entropy penalization". Our solution chooses the traffic matrix consistent with the measured data that is information-theoretically closest to a model in which source/destination pairs are stochastically independent. We use fast algorithms based on modern convex optimization theory to solve for our traffic matrices. We evaluate the algorithm with real backbone traffic and routing data, and demonstrate that it is fast, accurate, robust, and flexible.

Subfields: Computational Mechanics, Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/e1cc28c0348b6264466fdc761c65231218fe6722

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

Mark Crovella

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Spatio-temporal compressive sensing and internet traffic matrices (2009, neutral): “The thrust of much of this research has been on measurement [10,28] and inference [9,17, 25,27,31–34] of TMs, and more recently on topics such as anomaly detection [13, 14, 21, 29, 30].”
Diagnosing network-wide traffic anomalies (2004, methodology): “As a result, most traffic matrix estimation work to date has concentrated on estimating mean values of large flows [18, 25].”
Bayesian Neural Networks for Internet Traffic Classification (2007, methodology): “In common with [1], we describe a method with application”
Structural analysis of network traffic flows (2004, background): “However, a wide range of important problems fa ced by network researchers today require modeling and analysis of traffic on all links simulta neously, including traffic engineering, traffic matrix estimation [17, 31, 32], anomaly detection [6 , 1], attack detection [30], traffic forecasting and capa”
Combining filtering and statistical methods for anomaly detection (2005, methodology): “Since we cannot know in advance where anomalies will originate, nor the path they will take, it is advantageous to consider the behavior of all the links in an enterprise simultaneously when developing both a model of normal traf.c and a method for analyzing the residuals .”
Data streaming algorithms for efficient and accurate estimation of flow size distribution (2004, background): “Recent work [9, 10] show that it is possible to use tomography techniques to infer the traffic matrix from link load and aggregate input/output traffic at each node.”
Providing public intradomain traffic matrices to the research community (2006, neutral): “Providing Public Intradomain Traf.c Matrices to the Research Community Steve Uhlig1, Bruno Quoitin Jean Lepropre2 , Simon Balon2 Computing Science and Engineering Research Unit in Networking Department University of Liege, Belgium University of Louvain-la-Neuve, Belgium…”
Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (2005, methodology): “Here, we adopt as standard metric for network performancethe maximum throughput of the network under a “gravity model” of end user traffic demands [ 108 ].”