Probabilistic Diagnosis of Link Loss Using End-to-End Path Measurements and Maximum Likelihood Estimation

Internet fault diagnosis has attracted much attention in recent years. In this paper, the authors focus on the problem of finding the Link Pass Ratios (LPRs) when the Path Pass Ratios (PPRs) of a set of paths are given. Usually, given the PPRs of the paths, the LPRs of a significant percentage of the links cannot be uniquely determined because the system is under-constrained. They consider the Maximum Likelihood Estimation of the LPRs of such links. They prove that the problem of finding the Maximum Likelihood Estimation is NP-hard, then propose a simple algorithm based on divide-and-conquer. They first estimate the number of faulty links on a path, then use the global information to assign LPRs to the links.