Link Delay Tomography Via Independent Samples of Path Delay Measurements

Link delay tomography is a practically viable approach to obtain statistical information about the delay across each link in a network using only path level measurements. In this talk, we present a novel method that can be used to estimate the complete distribution of the link delays upto any desired accuracy. The major highlight of this method is that, unlike all previous works, it requires as input only a sequence of independent samples of the end-to-end path delay measurements. The idea is to approximate each link delay distribution using a generalized hyperexponential distribution, whose exponential stage parameters are known in advance, and focus on estimating the unknown mixing weights. These weights are obtained by solving a set of polynomial systems based on the moment generating function of the end-to-end delays. For unique identifiability, it is only required that the network be 1-identifiable; a condition which is essentially true for all tree based networks.