Search for: All records

Network tomography aims at estimating source–destination traffic rates from link traffic measurements. This inverse problem was formulated by Vardi in 1996 for Poisson traffic over networks operating under deterministic as well as random routing regimes. In this article, we expand Vardi's second-order moment matching rate estimation approach to higher-order cumulant matching with the goal of increasing the column rank of the mapping and consequently improving the rate estimation accuracy. We develop a systematic set of linear cumulant matching equations and express them compactly in terms of the Khatri–Rao product. Both least squares estimation and iterative minimum I-divergence estimation are considered. We develop an upper bound on the mean squared error (MSE) in least squares rate estimation from empirical cumulants. We demonstrate that supplementing Vardi's approach with the third-order empirical cumulant reduces its minimum averaged normalized MSE in rate estimation by almost 20% when iterative minimum I-divergence estimation was used. 

Network tomography aims at estimating source-destination traffic rates from link traffic measurements. This inverse problem was formulated by Vardi in 1996 for independent Poisson traffic over networks operating under deterministic as well as random routing regimes. Vardi used a second-order moment matching approach to estimate the rates where a solution for the resulting linear matrix equation was obtained using an iterative minimum I-divergence procedure. Vardi’s second-order moment matching approach was recently extended to higher order cumulant matching approach with the goal of improving the rank of the system of linear equations. In this paper we go one step further and develop a moment generating function matching approach for rate estimation, and seek a least squares as well as an iterative minimum I-divergence solution of the resulting linear equations. We also specialize this approach to a characteristic function matching approach which exhibits some advantages. These follow from the fact that the characteristic function matching approach results in fewer conflicting equations involving the empirical estimates. We demonstrate that the new approach outperforms the cumulant matching approach while being conceptually simpler. 

We extend network tomography to traffic flows that are not necessarily Poisson random processes. This assumption has governed the field since its inception in 1996 by Y. Vardi. We allow the distribution of the packet count of each traffic flow in a given time interval to be a mixture of Poisson random variables. Both discrete as well as continuous mixtures are studied. For the latter case, we focus on mixed Poisson distributions with Gamma mixing distribution. As is well known, this mixed Poisson distribution is the negative binomial distribution. Other mixing distributions, such as Wald or the inverse Gaussian distribution can be used. Mixture distributions are overdispersed with variance larger than the mean. Thus, they are more suitable for Internet traffic than the Poisson model. We develop a second-order moment matching approach for estimating the mean traffic rate for each source-destination pair using least squares and the minimum I-divergence iterative procedure. We demonstrate the performance of the proposed approach by several numerical examples. The results show that the averaged normalized mean squared error in rate estimation is of the same order as in the classic Poisson based network tomography. Furthermore, no degradation in performance was observed when traffic rates are Poisson but Poisson mixtures are assumed.