Network Tomography: Identifiability and Fourier Domain Estimation

The statistical problem for network tomography is
to infer the distribution of X, with mutually independent components,
from a measurement model Y=AX, where A is a given
binary matrix representing the routing topology of a network
under consideration. The challenge is that the dimension of X is
much larger than that of Y and thus the problem is often ill-posed.
This paper studies some statistical aspects of network tomography.
We first develop a unifying theory on the identifiability of the distribution
of X. We then focus on an important instance of network
tomography—network delay tomography, where the problem is
to infer internal link delay distributions using end-to-end delay
measurements. We propose a novel mixture model for link delays
and develop a fast algorithm for estimation based on the General
Method of Moments. Through extensive model simulations and
real Internet trace driven simulation, the proposed approach is
shown to be favorable to previous methods using simple discretization
for inferring link delays in a heterogeneous network.