Reseach On Non-Stationary Network Topology Tomography Base On Wavelet Transform

In order to monitor the network effectively and design the network applications effectively, it is very important to learn the network topology accurately. The traditional estimation method requires cooperation of the internal nodes to obtain network topology. But now, due to the security and performance considerations, many internal nodes are no longer involved in the measurement, leading to failure of this method. The topology estimation method based on network tomography doesn’t require cooperation of the internal nodes. It only needs to send and receive probe packets between the terminal nodes to get end-to-end data and then use statistics to estimate the network topology.The topology estimation methods based on network tomography usually consider the link state of the network is stable throughout the entire measurement period. However, in the actual network, the high burstiness of network traffic leads to the state of the network link changing constantly. So there may be large error between the estimation results and the real network topology. To solve these problems, this thesis proposes a new estimate method for non-stationary network topology estimation. This method use wavelet transform to extract the feature vectors of end-to-end delay variation, and then use the hierarchical clustering to restore the topology. The main work includes the following three aspects:(1) End-to-end delay measurement based on package group detection model. The delay variation of different destination nodes in the network has consistency in shared path. In order to capture the delay variation characteristics of non-stationary network and reflect this consistency, this thesis introduces package group detection model into the estimation of non-stationary network topology for the first time. Using the correlation between detection packets, we can capture the same variation characteristics of different path delay in non-stationary networks.(2) Extraction variation feature of the delay curve based on wavelet packet decomposition. Traditional tomography methods are based on a single statistical feature of network performance parameters(such as the delay inequality or variance of time delay) as a measure of the shared path length, but the single statistics don’t reflect the time-varying of network performance parameters. In view of the above questions, this thesis regard the end to end delay curve network as a non-stationary signal. then we use wavelet packet decomposition to capture the network end-to-end delay variation.(3) Network topology estimation method based on delay variation. In this thesis, we use wavelet packet coefficient composing the feature vectors of different nodes. Then we use these feature vectors as the input of network topology estimation method. Then we regard the problem of network topology estimation as hierarchical clustering problem. Hierarchical clustering method cluster nodes based on the approximate degree of the input feature vector. The nodes of high approximate degree are are clustered into one class. Finally we construct the tree topology structure utill we can’t continue clustering.In this thesis, we use NS2 to simulate the entire process. The simulation results show that under the non-stationary network, the non-stationary network topology estimation method based on wavelet transform can infer the network topology accurately. By compared with the network topology estimation method based on the path time delay covariance, we prove the accuracy and effectiveness of the method we proposed.