New Algorithms On Traffic Matrix Estimation Of TCP/IP Network

Nowadays, as the Internet develops rapidly, the scale of the network is expanding quickly and the complexity of it is increasing promptly. So it requires high quality of network measuring. As the traffic matrix estimation is an important index of network measuring, it attracts more attention too. Traffic matrix (TM) reflects the volume of traffic that flows between all possible pairs of sources and destinations in a network. In TCP/IP network management, it is very useful to infer traffic matrix from link measurements and routing information, especially for the tasks of capacity planning, traffic engineering and network reliability analysis. Traffic matrix estimation has attracted more and more attention since Vardi proposed the term network tomography in 1996.Unfortunately, traffic matrices are generally unavailable in large operational TCP/IP networks. Current direct measurement approaches, such as Cisco's Netflow, are insufficient in that they are not deployed everywhere and involve too much overhead. On the other hand, link load measurements are readily available in TCP/IP networks. The relationship between the traffic matrix, the routing matrix and the link counts can be described by a system of linear equations Y = AX, where Y is the vector of link counts, X is the traffic matrix organized as a vector, and A denotes a routing matrix. Y and A are readily obtained. Therefore, research efforts in the area of traffic matrix estimation have focused on modeling combined with statistical inference techniques. However, this inference problem is ill-posed as it involves more unknowns than data and the challenge lies in this problem is its ill-posed nature.To overcome the ill-posed challenge, this thesis firstly describes the inference problem into an optimization problem, in which the objective is to minimize the Euclidean distance between a certain predetermined prior and the target TM subject to the routing constraints upon the link measurements and TM. Because the estimation is sensitive to the prior traffic matrix and the existing methods to generate the prior are inefficient, we improve the Gaussian distribution of the EM method to generate the prior.Basing on the Euclidean optimization model, we propose two novel methods to deal with the traffic matrix estimation problem, one is called {1}-INVERSE which solve this problem by calculating the {1}-INVERSE of the routing matrix; The other is MPLM that apply the optimization theory to deduce the traffic matrix, with the key mathematical techniques being the matrix transformations and Lagrange multipliers method. An expression is derived for calculating the TMs from the link measurements and the partitioning and the transformations of the routing matrix. We analyze the computational complexity of MPLM, which comes out to be much less than the state-of-the-art approaches.Through both theoretical analysis and numerical results, it is shown that both {1}-INVERSE method and the MPLM method achieve better performance than the existing representative methods.