March 17 , 2004, 11am, CS 432
"Tomo-gravity"
Yin Zhang, AT&T Labs-Research

Abstract:

Traffic matrices, which specify the amount of traffic between origin and destination in a network, have tremendous potential utility for many IP network engineering applications, such as capacity planning, traffic engineering, and reliability analysis.  However, it is often difficult to directly measure traffic matrices in large operational IP networks.  So there has been a surge of interest in inferring traffic matrices from link loads and other more easily measured data. Unfortunately, this is a non-trivial task. The challenge lies in the ill-posed nature of the problem: the number of constraints (i.e., the link measurements) is typically much smaller than the number of unknowns (i.e., the matrix elements to be estimated).  So the problem is massively under-constrained for large networks.

In this talk, I will present a new method for practical and rapid inference of traffic matrices in IP networks from link load measurements, augmented by readily available network and routing configuration information. The method, "tomo-gravity", combines the advantages of transportation modeling (gravity models) with tomo-graphic methods such as those applied in medical imaging (CAT scans) and seismology.  It has a firm theoretical foundation in information theory, and we have shown that it is remarkably fast, accurate, flexible and robust on test data from AT&T's North American backbone network.  Currently, traffic matrices produced by tomo-gravity are in daily use for a number of network engineering tasks.  The operational experience has been very positive. On several occasions, reliability analysis led to reoptimized routing that successfully prevented service disruption during disastrous failure events. This clearly demonstrates the power of our technique.

Bio: Yin Zhang is a Senior Technical Staff Member in the Internet Research Department at AT&T Labs Research.  He earned his B.S. from Peking University in July 1997, and Ph.D. from Cornell University in August 2001, both in Computer Science.  His research interests span several areas of computer networks, including traffic engineering, anomaly and intrusion detection, data stream computation, overlay routing, and network measurement.