Research On Link Delay Distribution Inference Algorithm In Network Tomography

Network monitoring has great significance for network administrators to manage their network. But direct measurement of network characteristics is sometimes infeasible. Network tomography comes out as an effective solution for this problem. It makes inference for network internal parameters with end-to-end measurement, and introduces probabilistic reasoning idea into network measurement.In this paper, we analyze the network tomography technique, and make fully investigation on link delay distribution inference algorithm in network tomography. On the basis of basic EM algorithm for delay distribution inference, this paper makes several improvements and design the efficient link delay distribution inference algorithm ACC-EM for large scale network tomography, discusses the factors that influence its accuracy and efficiency, and considers its application approach in special cases.This paper first clearly brings forward the significance of network tomography, summarizes the research category of network tomography, introduces the main applications of network tomography, and points out the development route of network tomography. Focusing on the efficiency problem in large scale network tomography, this paper points out several methods to reduce the computational complexity of delay distribution inference based on basic EM algorithm, that is decreasing the vector searching space, accelerating in the time window, accelerating during the time window and parallelized probing, in the end schemes out the more efficient ACC-EM algorithm. This paper specifies the realization process of this algorithm, discusses the factors that have influence on the accuracy and efficiency of this algorithm, that is the number of probes, the size of the delay bin, the number of the receivers and the numbers of layers of the topology, and puts this algorithm into use of special cases, such as multi-source and missing data situations. It makes furthest use of probing data and expands the application of the delay inference algorithm. Experiment result shows that, the link delay distribution inference algorithm ACC-EM designed in this paper runs obviously fast than the basic EM algorithm, and can get good result under special cases, which has great significance for large scale network monitoring.