The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Traffic Matrix Estimation in the Internet: Measurement Analysis, Estimation Methods and Applications

Ilmari Juva

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Electronics, Communications and Automation for public examination and debate in Auditorium S4 at Helsinki University of Technology (Espoo, Finland) on the 18th of April, 2008, at 12 noon.

Overview in PDF format (ISBN 978-951-22-9299-8)   [1737 KB]
Dissertation is also available in print (ISBN 978-951-22-9298-1)

Abstract

In a communication network, the traffic has a source, from which that particular traffic flow originates, and a destination, at which it terminates. Each origin-destination (OD) combination constitutes an OD pair. The knowledge of the amount of traffic of each such OD pair in the network is represented by a traffic matrix. The traffic matrix is a required input in many network management and traffic engineering tasks, where typically the traffic volumes are assumed to be known. However, in reality, they are seldom readily obtainable, but have to be estimated. The estimators use as input the available information, namely link load measurements and routing information. Solving the OD-pair traffic loads from these is a heavily underconstrained problem. Thus, it is not solvable unless some extra information is brought into the problem.

In the first part of the thesis we analyze measurements from a backbone link of the Finnish University and Research Network (Funet). We consider first the aggregate traffic on the link and then divide the traffic into OD pairs based on the IP addresses of the packets. The traffic traces are analyzed and the traffic is characterized in order to gain insight into the nature of Internet traffic and to study the validity of assumptions necessary in traffic matrix estimation, such as the Gaussian IID model and the functional relation between mean and variance of the traffic volume.

The second part of the thesis studies traffic matrix estimation. We give a brief overview of the proposed methods and note that the majority of them can be classified into two classes based on the extra information that the methods use. These are either the gravity model class or the class that uses the variance through the mean-variance relation.

We derive analytically the Cramér-Rao bounds for the variance of the maximum likelihood estimator. This makes it possible to analyze the performance bounds for the accuracy that can be achieved by the estimator. We propose two novel methods for traffic matrix estimation. The Quick method, based on link covariances, yields an analytical expression for the estimate and is thus computationally light-weight. The accuracy of the method is compared with that of other methods using second moment estimates by simulation under synthetic traffic scenarios. The Combined method incorporates both sources of extra information. This method is shown in many cases to outperform the current estimation methods that rely only on one or other of the sources.

In the third part of the thesis we study robust load balancing. Many traditional load balancing techniques assume the availability of an accurate traffic matrix. However, robust load balancing takes a different approach, and thus does not typically require knowledge of the traffic matrix. We study the robust method but also introduce a new variant of it where the accuracy of the robust method is improved by using an estimated traffic matrix. In this approach we take account the uncertainty in the estimator's accuracy.

This thesis consists of an overview and of the following 8 publications:

  1. Ilmari Juva, Riikka Susitaival, Markus Peuhkuri, and Samuli Aalto. 2005. Traffic characterization for traffic engineering purposes: Analysis of Funet data. In Proceedings of the 1st EuroNGI Conference on Next Generation Internet Networks (NGI 2005), Rome, Italy, 18-20 April 2005, pages 404-411. © 2005 IEEE. By permission.
  2. Riikka Susitaival, Ilmari Juva, Markus Peuhkuri, and Samuli Aalto. 2006. Characteristics of origin-destination pair traffic in Funet. Telecommunication Systems, volume 33, pages 67-88.
  3. Ilmari Juva, Riikka Susitaival, Markus Peuhkuri, and Samuli Aalto. 2007. Effects of spatial aggregation on the characteristics of origin-destination pair traffic in Funet. In Proceedings of the 7th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking (NEW2AN 2007), St. Petersburg, Russia, 10-14 September 2007, Lecture Notes in Computer Science, volume 4712, pages 1-12.
  4. Paola Bermolen, Sandrine Vaton, and Ilmari Juva. 2006. Search for optimality in traffic matrix estimation: A rational approach by Cramér-Rao lower bounds. In Proceedings of the 2nd Conference on Next Generation Internet Design and Engineering (NGI 2006), Valencia, Spain, 3-5 April 2006. © 2006 IEEE. By permission.
  5. Ilmari Juva, Sandrine Vaton, and Jorma Virtamo. 2006. Quick traffic matrix estimation based on link count covariances. In Proceedings of the 2006 IEEE International Conference on Communications (ICC 2006), Istanbul, Turkey, 11-15 June 2006, volume 2, pages 603-608. © 2006 IEEE. By permission.
  6. Ilmari Juva. 2007. Sensitivity of traffic matrix estimation techniques to their underlying assumptions. In Proceedings of the 2007 IEEE International Conference on Communications (ICC 2007), Glasgow, UK, 24-28 June 2007, pages 562-568. © 2007 IEEE. By permission.
  7. Ilmari Juva. 2007. Robust load balancing. In Proceedings of the 50th Annual IEEE Global Communications Conference (GLOBECOM 2007), Washington D.C., United States, 26-30 November 2007, pages 2708-2713. © 2007 IEEE. By permission.
  8. Ilmari Juva. 2007. Robust load balancing in wireless networks. In Proceedings of the EuroFGI Workshop on IP QoS and Traffic Control, Lisbon, Portugal, 6-7 December 2007, pages 127-134. © 2007 IST Press. By permission.

Errata of publication 1

Keywords: Internet measurements, traffic characterization, traffic engineering, traffic matrix estimation, robust load balancing

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2008 Helsinki University of Technology

Last update 2011-05-26