Diagnosis, Network Tomography-based Multi-slot Failed Link

Network tomography received widespread concern, because it can estimate the internal accurate performance parameters by end-to-end measurement without the collaboration between the internal nodes. In fact, not all of the network management and maintenance and maintenance work is required to obtain the precise internal link performance parameters values. Using the general end-to-end unicast probe packets fast and accurate positioning performance parameters below a certain standard link (bad link) is more important. Most existing Lossy link identification methods are based on single-link slot measurement data, and rely on the assumption that each link of the network have the same probability be the bad link and the probability is very small. This kind of algorithm in ideal network environment can obtain good effect, but the above assumptions in the actual network environment often exist in the deviation, which make algorithm have some disadvantages in the accuracy and stability.Study found that, the multi-slot end-to-end measurement helps to obtain more accurate link-state model, using this information can estimate the prior probability of the link be congestion, the prior probability can provide effective reference. In this paper, we study the Multi-slots lossy link identification, and obtain the following results:1. In this paper we discuss the lossy link identification which base on the multi-slots end-to-end measurement, First, we use the Bernoulli model describes the state of the link in every slot, and assume that the state of each link is independent, Then proposed two new methods for estimating the link state prior probability, respectively, One is the factor graph-sum product algorithm which is based on maximum posterior probability,the other is EM algorithm which is based on maximum likelihood estimation. The former method describes the joint probability of the state between the link and the path by factor graph, then use the sum-product algorithm obtain the solution which maximize the marginal probability of the link state, The EM algorithm will the network into a series of only two leaf node sub-tree, for each child tree link-state distribution of the maximum likelihood solution, obtained the largest global pseudo likelihood solutions, Analysis showed that in the larger the network, the proposed algorithm more efficient than existing methods. On this basis, with the current slot end-to-end measurement data and the prior probability of links state, Adopt greed strategy of fault time identifying the current bad link. Simulation results show that the method has high detection rate and low false detection rate.2. As the link performance parameters change continuously over time, so the link state in every slot have temporal dependence. Bernoulli model can not describe the link state accurately, the paper further proposed use k-th order Markov Chain describe the link state, we use pseudo maximum likelihood inference method to estimate the state transition probabilities of k-th order Markov Chain. when k is large enough, the method presented in this paper is capable of obtaining the accurate the PMF of the link.