Unicast Network Loss Tomography Based on k-th Order Markov Chain

This paper addresses the issue of temporal dependence network link loss inference, presents a k-th order Markov chain based unicast network loss tomography method. The method introduces firstly k-th order Markov Chain (k-MC) to describe the link packet loss process, and then uses pseudo maximum likelihood method to estimate the state transition probabilities of k-th order Markov chain. If k is large enough, then the method presented in this paper is capable of obtaining an accurate loss probability estimate of each packet based on unicast end-to-end measurements. ns-2 simulation validated the effectiveness of the method.