How to compute accurate traffic matrices for your network in seconds

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.