Temporal And Spatial Relationship Constraints Traffic Matrix Estimation Methods

With the rapid development of the Internet, the structure of the network has changed thoroughly. It is necessary to get into the inner property of the specific network to design, control and manage it successfully. Traffic Matrix is an important parameter of network flow engineering, it can provide strong guarantee for network flow engineering and network management such as network planning and optimization, traffic congestion control, traffic anomaly detection. It is difficult to measure traffic matrix directly as the Internet is becoming massive, distributed and heterogeneous. Estimating traffic matrix from link data now is becoming a research focus, traffic matrix estimation is an ill posed problem, it has multiple results, In order to get real correct result, we need some constraint information according to the character of the traffic matrix estimation, shrinking the solution space, to solve the multiple results problem. In this paper, we introduce time and space relationships among traffic matrix at a certain period of time to traffic matrix estimation methods and get more accurate results.Large-scale IP traffic matrix estimation is highly ill posed. Simulated Annealing is simple and can easily get the local optimal solution. Based on these features, we introduced a new algorithm based on simulated annealing algorithm to solve traffic matrix estimation. We adopt the following strategies to improve Estimation accuracy: (1)for the multiple solutions caused by different initial guess, using every OD traffic Historical average result regulate by IPFP(Iterative Proportional Fitting Procedure)to be the initial guess, historical average result reflect the time relationship, IPFP regulation reflect the space relationship, this initial guess approach more to the real traffic, can improve the accurate of solution.(2) In the process of simulated annealing, we get every OD traffic's range from link traffic, then narrow the solution reaching space, reduce the multiple solutions. Simulation results show that this Algorithm has high Real-time property, the estimation accurate better than generalized gravity model.In this paper we introduce another partial filter algorithm based on time and space relationship, it assume that OD traffic is a 1-time Markov process, using Bayesian method to get posterior average as eventual estimation result. In order to improve the Practicality, We adopt the following strategies: (1) The method is sensitive to the a priori value causing of multiple results, we model the OD traffic using Gamma model that reflects OD traffic's character more realistically. We introduce the time and space relationship by matrix form; establish more realistically dynamic Bayesian system, reduce the posterior model. (2) In order to reduce the complexity of this method, we use particle filter based on sample-resample-MCMC to estimate the parameter of Gamma model dynamic Bayesian system; (3) In order to further improve accuracy, firstly we sample Gamma model parameter to expand the sample space of OD traffic. Simulation results show that this Algorithm is better than the estimation method based on Simulated Annealing and generalized gravity model.