Network Traffic Matrix Estimation

Traffic matrix (TM) sheds light on interior traffic of a network with each its element revealing the volume of one corresponding origin-destination flow and thus is of extreme importance as a critical input to many network engineering applications and managements like load-balancing, congestion control, network security and so on. Consequently, TM has its great practical meanings. Unfortunately, direct accurate measurement of TM is very complex and costly due to the limited inconsistent router support for flow level measurement capability in the current network. Consequently, method of TM estimation combining with mathematical methods becomes more feasible. However, precise estimation of TM is still a challenging task even though enormous research efforts have been directed to this subject in recent decades.In this paper, through our deep analysis of the deficiencies of many current representative TM estimation methods, we propose three different novel approaches by three different research ways, based on our deep analysis of the deficiencies of many current representative TM estimation methods.The first approach is termed as Advanced-Tomogravity method, which is based on a precise gravity model and the tomography method. First, the precise gravity model is proposed on the basis of the existing generalized gravity model by introducing a relativity factor vector parameter, which defines the relativity between the solution of the existing generalized gravity model and its real TM. The solution obtained from this precise gravity model is then refined by the basic model of the tomography method. By mathematical analysis, we give the explicit expression of the relativity factor vector parameter in the proposed precise gravity model by the Moore-Penrose inverse and the minimum-norm least-square solution. The vector parameter is subsequently determined with the aid of small amount of historical real data of TM. A general algorithm of the proposed approach is therefore designed. Finally, our approach is validated by simulation using the real data of the Abilene Network. The simulation results indicate that it reduces the relative errors to less than one-half, better tracks not only the dynamic fluctuations but also the overall mean behavior of traffic flow.The second one is named as Tomofanout, for the estimation of TM in large-scale IP network using the available link load data, routing matrix and partial direct measurement data of TM. Firstly, we propose an edge link fanout model which defines each edge link's fanout, i.e., each edge link's fractions of traffic emitting from that edge link to other edge links. Secondly, benefited from the edge link fanout's diurnal pattern and stability, we are able to compute the edge link baseline fanout to estimate the TM at the following days by multiplying it by the edge link loads at the corresponding time intervals. In such, an initial link-to-link TM estimation result is calculated by the edge link fanout model. Further, by making the corresponding transformation to the link-to-link TM, the router-to-router TM estimation result is thus obtained. Thirdly, The solution is then refined by the basic model of the tomography method to keep consistent with both the edge and the interior link loads for further improvement of accuracy in estimation. In particular, the Expectation Maximization (EM) iteration of the basic model of tomography method is used for further refinement. As the iteration running on, the edge link fanout model solution is gradually approaching to the final estimation result, which is compatible with both the edge and the interior link loads. Fourthly, a general algorithm is proposed for computing the edge link baseline fanout and the estimation of the TM. Finally, the Tomofanout approach is validated by simulation studies using the real data from the Abilene Network. The simulation results demonstrate that Tomofanout achieves extremely high accuracy:its Spatial Relative Error (SRE) is less than one-half of Tomogravity's; while its Temporal Relative Error (TRE) is less than one half of Fanout's and is only one-third of Tomogravity's.The last proposed one is an accurate method, i.e., the Moore-Penrose inverse based neural network approach for estimation of IP network traffic matrix with extended input and expectation maximization iteration, which is termed as MNETME for short. Firstly, MNETME adopts the extended input component, i.e., the product of routing matrix's Moore-Penrose inverse and the link load vector, as the input to the neural network. Secondly, the EM algorithm is incorporated into its architecture to deal with the output data of the neural network. Therefore, MNETME manifests itself with the advantages that it needs less input data, but has better accuracy of estimation.We theoretically analyze the algorithm and then study its performance using the real data from the Abilene Network. The simulations results show that MNETME leads to a more accurate estimation in contrast to the previous methods, meanwhile it holds better robustness and can well track the traffic fluctuations. We finally extend MNETME to random routing networks by proposing a new model of random routing which overcomes three fatal deficiencies of the existing model and it is easier, more practical and more precise.