Research On Network Tomography Based On Sparsity

With the rapid development of the Internet technology,as well as the increasing scale and complexity of the network,accurate and timely performance data becomes critical to network management.However,the vast modern network and the limitations of existing measurement techniques make it impractical to collect complete measurements.Network tomography is a concept derived from CT in medicine,the core of which is to infer the required indicators by an easily observable quantity.Network tomography can be divided into two categories.The first type is used to derive the performance parameters?such as link delay and packet loss rate?of the internal links of network.The second type is used to estimate the traffic volume from a source to a destination?or several destinations?.For both categories,it is very difficult or even impossible to directly measurement the metrics.Network tomography does not need to measure these performance metrics directly,but estimates them from more readily available measurements.However,inferring network performance data from an easily observable measure-ment is often a very difficult problem,and most current work uses statistical reasoning.In this paper,we analyze the sparse property of network data,that is,the performance met-rics itself is sparse or sparse under certain dictionaries.As an emerging signal analysis and synthesis method,the sparse representation of signals has attracted a lot of attention from researchers,and has been successfully applied to signal coding,compressed sens-ing,and blind source separation etc.At present,some network tomography work has demonstrated the sparse characteristics of network data,so we expect a better estima-tion performance by fully exploiting this feature of network data.This thesis conducts research on this cross field and achieves the following corresponding results:1.As the cornerstone of the whole thesis,we first analyzes the sparse characteristic of network data,including the sparseness of link parameters such as delay and packet loss rate.We also illustrate the sparse representation of OD?Origin-Destination?stream under base transformation using actual network traffic.Then the idea of using sparsity to estimate link parameters from path measurements is proposed.In addition to the classicl₁ minimization in the field of compressed sensing,a sparse Bayesian learning method is proposed to recover the network link state.Experimental results verify the effectiveness of the proposed scheme.2.In terms of the measurement path selection issue in network tomography,a path selection algorithm based on the mutual coherence of routing matrix is proposed.The method takes advantage of the inherent sparsity of link parameters,and selects the paths to minimize the mutual coherence value of constructed routing matrix.Firstly,the NP-complete property of the method is proved,and the theory of submodular is used to analyze the objective function.Then a greedy algorithm is proposed.At each iteration,the algorithm preferentially selects the measurement path to minimize the increment of mutual coherence.Experimental results confirm that the proposed scheme can select a small number of measurement paths while maintaining high link identification.3.In addition to the sparse feature of link state,this thesis further explores the time domain correlation between links,and proposes a time-space network congestion diagnosis scheme:weightedl₁ minimization.The method combines the sparsity of link performance parameters with the congestion prior probability.Note that if the sparsity is regarded as the spatial property of link parameters,then the prior probability can be viewed as the time correlation of the links.Firstly,the recovery error of the weightedl₁ minimization is analyzed theoretically,and we point out that selecting appropriate weights will eventually improve the recovery accuracy.Then the Maximum A-Posteriori estimator is used to determine the weights.Experimental results show that the proposed scheme is superior to the algorithm using only sparsity or the algorithm using only con-gestion probability,and has higher estimation accuracy.4.In terms of the traffic matrix estimation issue in network,an estimation method using sparse representation of traffic matrix is proposed.This method adopts a part of the wavelet base as the dictionary,and minimizes the sum of thel₁ norm of the columns of OD matrix.It successfully solves the ill-posed problem in the traffic estimation.We theoretically proves the error-free estimation condition of the proposed method.Since the actual OD traffic usually contains abnormal components,modeling the two separately can obtain more accurate results.Theoretical analysis shows that the normal and abnormal components of the OD flow matrix can be recovered completely if both components are sufficiently sparse in their respective dictionaries.We conduct experiments of estimating the OD matrix from the link measurements,the results show that the proposed scheme has higher accuracy for both anomaly detection and traffic matrix recovery.By solving the above problems,the sparsity theory is introduced into the network tomography,which has achieved better results than the traditional methods.At the same time,because this thesis contains a number of theoretical analysis on sparsity,the conclu-sions from these analysis also enrich the theoretical system in the field of sparse signal processing.