An information-theoretic approach to traffic matrix estimation
- 25 August 2003
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 301-312
- https://doi.org/10.1145/863955.863990
Abstract
Copyright 2003 ACMTraffic 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 informationtheoretically 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.Yin Zhang, Matthew Roughan, Carsten Lund and David DonohKeywords
This publication has 21 references indexed in Scilit:
- Deriving traffic demands for operational IP networks: methodology and experienceIEEE/ACM Transactions on Networking, 2001
- Atomic Decomposition by Basis PursuitSIAM Review, 2001
- Time-Varying Network Tomography: Router Link DataJournal of the American Statistical Association, 2000
- NetScope: traffic engineering for IP networksIEEE Network, 2000
- Bayesian Inference on Network Traffic Using Link Count DataJournal of the American Statistical Association, 1998
- Solving Ill-Conditioned and Singular Linear Systems: A Tutorial on RegularizationSIAM Review, 1998
- Network Tomography: Estimating Source-Destination Traffic Intensities from Link DataJournal of the American Statistical Association, 1996
- The Axioms of Maximum EntropyPublished by Springer Nature ,1988
- Ill-posed problems in early visionProceedings of the IEEE, 1988
- Stein's Paradox in StatisticsScientific American, 1977