Fault Diagnosis And Loss Inference In IP Network Based On Active Probing

With the increasing size and complexity of IP network, accurate and efficient diagnosis and loss inference in such network become more and more difficult. In the past several years, the classical approach to fault and performance management is passive event correlation. However, as the rapid growth of network techniques, the passive method, which has high cost and low accuracy, cannot satisfy the requirements of complex networks. Thus, active probing which can perform diagnosis efficiently and adaptively has entered into the view of researchers. However, active probing based technique also has its drawbacks. First, the probes may generate additional network load. Secondly, diagnosis and inference based on the probe results may cost much computing time. Last, noise is ubiquitous in networks, such as the changes of routings, topologies and the status of network nodes, the spurious symptoms, and the inaccurate knowledge about the network system. The noise makes the diagnosis and inference intractable.To address the above problems in active probing techniques, this thesis mainly makes the following contributions.(1) An efficient probe selection algorithm is proposed in this thesis. The new algorithm can select the least probes which have the approximate maximum diagnostic ability. Thus, it saves much probe cost. The new algorithm can deal with the noise in the network and can also be applied in the network with multiple faults. The results of experiments tell that, compared to an existing algorithm, the new algorithm can select the same probes with much less computing time.(2) Two diagnosis algorithms for complex networks are proposed in this thesis. The first algorithm can perform diagnosis in noisy networks with spurious symptoms. It models the system as a Bayesian network, and represents the noise as the conditional probabilities in the model. The new algorithm first filters spurious symptoms and limits the number of the faults. Hence, it can save much computing time and guarantee the diagnostic accuracy. The second algorithm can deal the changes of status of network nodes. It models the dynamic network system as a Dynamic Bayesian Network (DBN), and performs diagnosis on the DBN model.(3) A new method to find all identifiable links and link sequences in the network is proposed in this thesis. Although it is impossible to identify all the loss rates of links with the end-to-end probes in some cases, a major part of links in the network can be identified uniquely. The new method can efficiently find all these identifiable links simultaneously, and partition the rest of the links into several link sequences. The loss rate of each link sequence can be identified, while the subset of them cannot. Experimental results show that new method can perform the inference more efficiency and has finer granularity.(4) Two efficient algorithms to infer the loss rates of all network links are proposed in this thesis. It is impossible to infer the unidentifiable links without any additional information. The first algorithm performs the inference using the non-linear programming method, and the second algorithm utilizes the independence of network links. Compared with two former classical loss inference methods through experiments, the two new algorithms only use2%of their probes but make an improvement on both the inference accuracy and the computing time.