Time-Varying Network Tomography: Router Link Data

Abstract

The origin-destination (OD) traffic matrix of a computer network is useful for solving problems in design, routing, configuration debugging, monitoring, and pricing. Directly measuring this matrix is not usually feasible, but less informative link measurements are easy to obtain.

This work studies the inference of OD byte counts from link byte counts measured at router interfaces under a fixed routing scheme. A basic model of the OD counts assumes that they are independent normal over OD pairs and iid over successive measurement periods. The normal means and variances are functionally related through a power law. We deal with the time-varying nature of the counts by fitting the basic iid model locally using a moving data window. Identifiability of the model is proved for router link data and maximum likelihood is used for parameter estimation. The OD counts are estimated by their conditional expectations given the link counts and estimated parameters. Thus, OD estimates are forced to be positive and to harmonize with the link count measurements and the routing scheme. Finally, maximum likelihood estimation is improved by using an adaptive prior.

Proposed methods are applied to two simple networks at Lucent Technologies and found to perform well. Furthermore, the estimates are validated in a single-router network for which direct measurements of origin-destination counts are available through special software.

Key Words:

• Expectation-Maximization algorithm
• Filtering
• Normal
• Inverse problem
• Link data
• Maximum likelihood estimation
• Network traffic
• Smoothing
• Variance model