A Quasi-Likelihood Approach for Accurate Traffic Matrix Estimation in a High Speed Network

Knowing the traffic matrix, i.e., packet/byte counts between pairs of nodes in a network, is important for network management. The main challenges for accurate traffic matrix estimation in a high speed network are the computation and memory limitations. In this paper, we propose a novel algorithm for traffic matrix estimation that can yield accurate estimates whereas uses small memory and per packet update overhead. Our algorithm constructs a compact probabilistic traffic digest at each network node, and derives a Quasi Maximum Likelihood Estimate (Quasi-MLE) of the traffic matrix by correlating the traffic digests received at a central location. Our new approach is highly efficient, requiring no prior knowledge of the exact packet size distributions. We derive accurate approximation of the relative error distribution of our estimate. For an origin- destination (OD) pair (o,d), we show that by using an array of size M for each traffic digest at o and d, the relative estimation standard error is O(M^-1/2(sigma_{o +}sigma_d)^1/2), where sigma_o,sigma_d are the noise-to-signal ratios, defined as the ratios of non-OD packet/byte counts to OD packet/byte counts at the origin and destination. This is superior to the state-of-the-art algorithms, especially for large sigma_o and sigma_d, where the estimation is more challenging. We further demonstrate the effectiveness of our approach using both model and real Internet trace-driven simulations.