Research On The Strategy Of End-to-End Network Traffic Recovery Based On Compressive Sensing

With the rapid development of the information and communication technology,the scale of an IP network is much more tremendous than before,and it is a complex and heterogeneous network due to various types of services supported by our networks.A reasonable and efficient network management task is necessary to make our networks available.A network operator need to the status of packets transmitted between each node pair in order to make decisions for network planning,load balancing and routing configuration.A traffic matrix,that is a crucial input for network management,describe the volume of traffic flows between all possible origin and destination node pairs.Initially,an IP network is designed simply whose destination just transmits packets for customers as quickly as possible,thus this design strategy decreases the observation of our networks.On the other hand,direct measurement for an IP network is wasteful and unpractical for a large-scale IP backbone network,due to the enormous consumption of existing monitoring techniques.Hence,traffic matrix estimation,which estimates a traffic matrix from other readily available network information,is widely used in practice instead of direct measurement,and has become an important issue all over the world.Network tomography is a common traffic matrix estimation technique,where the traffic matrix is inferred via the relationship between the traffic matrix,the routing matrix and the link loads.However,for traffic matrix estimation in a large-scale IP backbone network,the network tomography model is an inverse inference problem with a highly under-constrained feature.Therefore,the traffic matrix estimation problem still has a great number of challenges in a large-scale IP backbone network.Motivated by that,this thesis focuses on the problems of traffic matrix estimation in a large-scale IP backbone network.The known statistical properties of traffic flows consist of long-range dependence,short-range dependence,self-similarity and fluctuation.For these properties,the time-varying property and modeling of traffic flows are studied at first,and two traffic matrix estimation approaches based on the Multifractal Wavelet Model and the Bayesian network are proposed,repectively.The method based on the Multifractal Wavelet Model trains the Multifractal Wavelet Model using measured network traffic data for capturing the statistical properties of traffic flows in order to obtain an initianl estimator of traffic matrix.Meanwhile,the Iterative Proportional Fitting Procedure algorithm is adopted in the proposed method,and the estimates will obey the network tomography model in order to approximate the real network traffic by numerical iterations.The method based on the Bayesian network builds a Bayesian network structure to extract the statistical properties of traffic flows.Based on the proposed structure,the joint probability distribution of network traffic is achieved by the maximum a posteriori approach,and then the traffic matrix is estimated in terms of a regularized optimization model.Motivated by the ill-posed feature of network tomography model,chapter 3 studies the property of the network tomography system,and a traffic matrix estimation method based on a deep architecture is proposed.In this method,a training data made up of the prior of traffic matrix is used to train the deep architecture based on the deep belief network,and then this deep architecture can learn the system property of the network tomography model for traffic matrix estimation.End-to-end network traffic has various statistical features in time domain,and yields a low-rank and a power law in space.Chapter 4 focuses on the spatial property of traffic matrix,and takes advantage of compressive sensing techniques to overcome the ill-posed feature of the network tomography model.This chapter deals with two problems of traffic matrix estimation.(1)A network tomography model based on a perturbation is proposed for traffic matrix estimation.This method first perturb the traditional network tomography model by a random matrix,and then use the principal component analysis method to extract the spatial property of traffic matrix to build an sparse representation of traffic matrix approximately.By a diagonal matrix for filtering,the modified network tomography model will obey the constraints of compressive sensing,and then the traffic matrix can be estimated by the Orthogonal Match Pursuit algorithm.(2)A traffic matrix reconstruction method based on the Boolean Compressive Sensing is proposed.This approach is a pure data-driven traffic matrix reconstruction method,and a Bernoulli matrix is adopted to select a set of partial OD flows measured directly for obtain the measurements.Meanwhile,a dictionary learning algorithm for the sparse representation of traffic matrix is proposed.According to this sparse representation of traffic matrix,the traffic matrix is estimated by the compressive sensing reconstruction algorithms.The reconstruction method based on the Boolean Compressive Sensing needs a great number of OD flows measured directly,although compressive sensing is an efficient solution for handling with an ill-posed system.In order to reduce the consumption of direct measurement,chapter 5 involves the group testing techniques for traffic matrix estimation.Group testing is widely used in medical,electron,and communication.Especially,the graph-constrained group testing that arises for the problems of network tomography and sensor networks is adopted to estimate the delay and packet loss rate.In chapter 5,a group testing-based approach for traffic matrix estimation is proposed,where the traffic matrix model is determined by random walks on an undirected complete graph which can remarkably reduce the number of OD flows measured directly.Although the proposed method can improve the cost of direct measurement signally,it neglects the spatio-temporal feature of traffic matrix.In order to improve the proposed method,a traffic matrix estimation method is proposed named the spatio-temporal group testing,where the l1-norm regularization is adopted to model the traffic matrix estimation problem for capturing the spatio-temporal feature of traffic matrix as an additional information.With the diversification of network applications,the network traffic is much more complex,hence a single statistical model or additional information is insufficient for estimating a traffic matrix precisely.Especially,the statistical model is sensitive for the prior information,thus a hybrid method is proposed in chapter 6.This method takes into account the spatio-temporal feature of traffic matrix,and uses few measured OD flows as additional information to construct the estimation model for traffic matrix estimation.Finally,chapter 7 will conclude our work of this thesis,and present the future research directions.