Research On The Key Technology Of Large-scale IP Traffic Matrix Estimation

With the exponential increase in the size of the IP network and the urgent demands in network management and maintenance, traffic matrix estimation has currently become an interesting topic. As the IP network fast advances, network operators need to know how data packets among the nodes in a network are forwarded so that they can well make many network activities. These activities include load balancing, traffic detecting, route optimization, network maintenance, network designing, network planning and so on. As a key input of network activities, traffic matrix is extensively paid attention to by the researchers at home and abroad. It becomes an important research topic of the IP network at present. Traffic matrix denotes the volume of network traffic flowing among the Original-Destination (OD) nodes in a network (namely the volume of traffic for OD flows). Its dimension amounts to the number of all the OD flows in the network. It describes, from a global perspective, how the data in the whole network flow. And it is used by network operators to make many decisions. However, though traffic matrix is significantly important, it is very difficult to obtain it by the direct measurement and even is not practical sometimes. Traffic matrix estimation obtains the value of traffic matrix by the indirect measurement. It can avoid the problems met with the direct measurement. Due to this merit, this dissertation investigates the estimation problem of traffic matrix in the large-scale IP backbone network (namely large-scale IP traffic matrix), including: the optimal estimation of large-scale IP traffic matrix, large-scale IP traffic matrix estimation based on Fratar model, large-scale IP traffic matrix estimation based on regressive model, large-scale IP traffic matrix estimation based on recurrent neural network, and large-scale IP traffic matrix estimation based on feedforward neural network.According to router matrix, network traffic flows in a network and is aggregated into link loads on links. Thus there exist the constraints among traffic matrix, router matrix and link loads. However, the number of OD flows is much more than that of links in the IP network, especially in large-scale IP backbone network. This leads to the highly ill-posed nature that traffic matrix estimation problem holds. How to overcome the ill-posed nature of this problem is the main challenge faced currently. Therefore, based on the numerical optimal theory, Chapter 2 seeks the methods to overcome the problems, which is that the results of large-scale IP traffic matrix estimation are not stable or unique, from two perspectives. (1) The simplex method is used to estimate traffic matrix. Firstly, traffic matrix estimation problem is described into the linear programming process under the constraints. Then the simplex method is combined with resolution matrix to handle this linear programming process. As a result, traffic matrix estimation is obtained. (2) The simulated annealing method is used to estimate traffic matrix. Firstly, traffic matrix estimation problem is described into the simulated annealing process. With temperature dropping, the estimation results of traffic matrix approach slowly to the real value with the result that the ill-posed nature of this problem is overcome. And then to overcome further the ill-posed nature of this problem, Euclid distance and Mahalanobis distance is used as the optimal metric. The optimal estimation of traffic matrix in the time-varying context can be attained by iterative process.Previous works study traffic matrix estimation mostly based on the statistic models. Current research shows that traffic matrix holds spatio-temporal correlations. It is difficult of statistic models to capture these characteristics. Based on Fratar model, Chapter 3 estimates large-scale IP traffic matrix from two perspectives. (1) Fratar model is used to model the OD flows in large-scale IP backbone networks. By Fratar model, the spatio-temporal correlations of traffic matrix can be captured and its prior value can be obtained accurately. Then by iterative process, we can attain the estimation of traffic matrix. (2) Because the iterative process in (1) needs the complex computations, it takes long time. Based on Fratar model, this dissertation uses algebraic reconstruction technique (ART) to estimate traffic matrix. ART is a key technique in the image reconstruction. By the process of projecting and iterating, it seeks the solution without the complex computations and long time. Thus ART can fast attain the estimation results of traffic matrix.When network traffic is investigated in details, the researchers find that it does not only hold spatio-temporal correlations, but also hold heavy-tailed distribution, self-similarity, short-range dependence (SRD), and long-range dependence (LRD) nature. Conventional models about network traffic can not accurately capture these characteristics. Chapter 4 uses regressive model to estimate large-scale IP traffic matrix from two perspectives. (1) To capture the temporal correlations of network traffic, OD flows are modeled as autoregressive moving average (ARMA) model. At the same time, traffic matrix estimation problem is described into the optimal process under Mahalanobis distance by taking the advantage of Mahalanobis distance. Then we can obtain the accurate estimation of traffic matrix by iterative process. (2) Autocorrelation function denotes that network traffic is nonstationary. And thus it is a time-varying and nonstationary traffic. In the time-varying and nonstationary context, this dissertation models OD flows into the generalized autoregressive conditional heteroscedasticity (GARCH) model. Unlike conventional model, GARCH model does not regard the variance of network traffic as constant value, but thinks that it changes with time. By GARCH model, this dissertation can well capture the heavy-tailed distribution, self-similarity, and LRD nature and thus can accurately estimate traffic matrix.Though there are many modeling methods about traffic matrix, it is significantly difficult to build the accurate model about traffic matrix because it holds the time-varying and nonstationary nature, spatio-temporal correlations, heavy-tailed distribution, self-similarity, SRD, and LRD nature. Recurrent neural network can make the learning and generalization. It can be used to model the linear and nonlinear systems. Thus it holds the powerful modeling ability. Chapter 5 exploits the powerful modeling ability of recurrent neural network to estimate large-scale IP traffic matrix from two perspectives. (1) Recurrent multiplayer perceptron (RMLP) network is used to build the estimation model of traffic matrix. By modeling every OD flow in large-scale IP backbone network with RMLP network, a multi-input and multi-output estimation model of traffic matrix is built. Then the estimation results of traffic matrix satisfied with linear constraints is obtained. (2) This dissertation also investigates large-scale IP traffic matrix estimation based on Elman neural network. Unlike RMLP network, Elman neural network is used to model simultaneously all OD flows. By modifying conventional Elman neural network, spatio-temporal correlations of traffic matrix can be captured more accurately. Then the accurate estimation of traffic matrix is obtained.In contrast to the conventional modeling methods, recurrent neural network avoids complex computations and well handle the modeling problem of traffic matrix estimation. However, because recurrent neural network holds feedback connections, it will take long time to train it with complex computations needed. Chapter 6 uses feedforward neural network to estimate large-scale IP traffic matrix from three perspectives. (1) Based on backpropagation (BP) neural network, this dissertation models traffic matrix estimation problem as a multi-input and multi-output estimation model. By using the input-output data pairs to train BP neural network, this estimation model can quickly be built Then traffic matrix estimation is fast obtained by seeking the optimal solution under the constraints. (2) Based on the characteristics that the generalized regression neural network (GRNN) converges to the underlying regression surface and can be used for any regression problem, this dissertation exploits GRNN to investigate large-scale IP traffic matrix estimation problem. (3) Radial basis function (RBF) neural network is another new modeling tool. It is better than BP neural network in terms of approximate capability, classification ability, and learning speed. This dissertation uses RBF neural network to discuss large-scale IP traffic matrix estimation problem. By modifying conventional RBF neural network, the characteristics of traffic matrix can be captured accurately. Then under Euclid distance and Mahalanobis distance, the accurate estimation of traffic matrix can be obtained by iterative process.Finally, Chapter 7 summarizes the dissertation, reviews the above research work, and presents the future research directions.