Statistical methods for the Origin Destination traffic matrix problem

Prof. Sandrine Vaton
TELECOM Bretagne, Brest, France

16 hours, 4 credits

June 14 - June 16, 2010

Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via Caruso, meeting room, ground floor

Contacts: Prof. Stefano Giordano



This series of lessons will give an overview of the main statistical methods that have been published over the last decade for the Origin Destination traffic matrix problem in a telecommunication network. The Origin Destination traffic matrix summarizes the volumes of traffic exchanged between any pair of Origin/Destination nodes (e.g. PoP) in a telecommunication network.

Although some solutions such as Netflow make it possible to estimate Origin Destination volumes by performing direct measurements at the flow level, till now these solutions are not easy to deploy on a large scale. On the contrary the SNMP protocol permits to gather the volume of traffic aggregated on any link by querying network equipments for some of the MIB variables. There is clearly a simple relation between the Origin Destination volumes and the volume of traffic on the links. And the problem has been identified as an ill posed linear inverse problem. This simple observation gave birth to a large bunch of literature on the "Traffic Matrix Problem" during the last ten years.

Different issues have been studied by the research community. They can be classified into three categories: (i) estimation of the OD traffic matrix (ii) detection (and localization) of anomalies in the OD traffic matrix (iii) and tracking of a non stationary OD traffic matrix, all problems being considered under the assumption that routing information and link level volumes are available.

We are going to draw a panorama of the research conducted in that field and discuss our own research results on that topic. Class room learning will be complemented by practicals (with software Matlab).


  • Introduction: definition of the trafic matrix (TM), ill posed linear inverse problem
  • Gravity methods: simple gravity and tomo-gravity estimates
  • Bayesian methods (and their application to the TM problem)
  • EM algorithm
  • MCMC methods
  • Tracking a non stationary TM with the Kalman filter
  • Anomaly detection
  • Principal Component Analysis
  • Spline Based analysis
  • Routing optimization with a polyedral TM (robust routing)