Delay and traffic rate estimation in network tomography

Abstract

Network tomography deals with estimation of computer network features from measurements on links or terminal nodes. The area was pioneered with the work of Vanderbei and Iannonou in 1994 and Vardi in 1996. Of particular interest are estimation of source-destination traffic rates from link packet counts or from aggregated packet counts in input and output nodes, and estimation of link delay from source-destination delay measurements. Traffic rate estimation, and link propagation delay estimation, are inverse problems which require the solution of under-determined sets of linear equations. Iterative solutions based on moment matching and the expectation-maximization algorithm were proposed for traffic rate estimation, and a maximum entropy approach was developed for link propagation delay estimation. Traffic rate estimation was also performed using a Bayesian estimation approach. Estimation of link delay densities commonly involves exponential mixture models which entail independence of the delay on various links. Network tomography is useful for monitoring the performance of a network, and thus maintaining and expanding the network.