Network Tomography - Compressed Sensing Techniques for Traffic Matrix Estimation

Abstract

Traffic Matrix Estimation (TME) techniques address the problem of determination of a network’s traffic demand matrix from its link load measurements and is considered critical for capacity planning, anomaly detection and many other network management related tasks. With the advent of cloud services such as IaaS (Infrastructure as a Service), Paas (Platform as a Service) and Saas (Software as a Service), the traffic patterns are difficult to model since they do not follow a single probability distribution such as Poisson, Gaussian, Negative Binomial etc., thus decreasing the estimation accuracy using the available methods. Traffic Matrix Estimation for a large network with accuracy is of utmost importance and is considered a challenging problem. Many approaches use statistical inference distribution on traffic matrix elements that rely on initial or available measurements of the traffic flow (mean and variance). This thesis asserts and proposes a solution for the estimation of traffic matrix that possibly exhibits over-dispersion, which is a more severe problem with mice flows (i.e. small flows) than the elephant flows (i.e. large flows). Moreover, this thesis presents a traffic matrix estimator which shows optimal performance while minimizing errors when there are sparse and limited measurements(training datasets) availability. Furthermore, this thesis inves- 1 List of Tables tigates the effects of sparsity and measurement errors (training data errors) for a large network. The main contribution of this thesis are 1) investigation for the traffic matrix that may experience over-dispersion and formulation of a two-step optimization approach with appropriate accuracy and additional constraint. 2) Investigate and development of a novel architecture that demonstrates superior outcomes for simulations for real datasets and 3) review the case of traffic matrix estimation in which the measurements (training datasets) may be limited in size and may have missing information or incomplete data with errors