How to compute accurate traffic matrices for your network in seconds
Date
2003
Authors
Zhang, Y.
Roughan, M.
Greenberg, A.
Donoho, D.
Duffield, N.
Lund, C.
Nguyen, Q.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of NANOG 29
Statement of Responsibility
Yin Zhang, Matthew Roughan, Albert Greenberg, David Donoho, Nick Duffield, Carsten Lund, and Quynh Nguyen
Conference Name
North American Network Operators' Group Meeting (29th : 2003 : Chicago, USA)
Abstract
A matrix giving the traffic volumes between origin and destination in a network has tremendously potential utility for IP network capacity planning and management. Unfortunately, traffic matrices are often hard to measure directly in large, operational IP networks. On the other hand, link load measurements are readily available in IP networks. In this presentation we will describe a new method for practical and rapid inference of traffic matrices in large IP networks from link load measurements, augmented by readily available network and routing configuration information. The method, "tomo-gravity," combines the better aspects of transportation modeling (gravity models) with tomo-graphic methods such as applied in medical imaging (CAT scans) and seismology. It has a firm theoretical foundation in information theory, and we have shown that it is is remarkably fast, accurate, flexible and robust on test data from AT&T's North American backbone network, and also on other network topologies obtained via the Rocketfuel project. The most useful tests of accuracy have come through test applications in reliability analysis and OSPF weight optimization, which have shown the power of this technique. In this talk, we will explain the algorithms, present data on how well the algorithms work for large ISP networks, and provide guidance on how well the algorithm is going to work for your network.