Network Tomography Based Multi-path Fault Link Diagnosis

The Internet has been more and more widely used in many aspects of the basicnecessities of people, which making people becoming increasingly dependent on theInternet. Under this situation, it tends to bring great inconvenience to the work and lifeof people once the network fails. So, it is truly necessary to detect and eliminate faultstimely in the network through network monitoring and management in some way.Existing network failed link diagnosis is made on the assumption that the targetnetwork is a tree logical topology network and regards the end-to-end measurementdata as the main input of the algorithm for the diagnosis of the failed link. When thenetwork traffic balancing routing policy (such as ECMP) has been implemented in thetarget network, the logical topology of the target network can introduce a sense ofuncertainty. For the reason that the routing path to the destination node is not unique,the traditional methods can not be directly applied to the diagnosis of the failed link inthe multi-path routing situation. To overcome this limitations of traditional methods,this paper study on the method of diagnosis of the failed link of the multipath routingnetwork. The main innovation is:1. Designed an experimental platform which consists of hardware componentsand software components. The hardware part consists of routers with layer3routingfunction and a computer with dual-NIC(to simulate multi-path routing destinationnode). The software part consists of an UDP based probe program which can achievethe end-to-end measurement. In addition, in order to facilitate the background flowcontrol, we realize an TCP based background flow generator.2. This paper summarized some features of the traditional algorithms of thediagnosis of failed link and brought the definition problem of failure threshold of thefailed path in the multi-path routing situation. By learning from the failure thresholdmodel of the tree logical network, this paper defined the failure threshold of the failedpath and gave a detailed theoretical derivation in the multi-path situation.3. Due to the uniqueness demand for the end-to-end data of the traditional diagnosis of the failed link, we proposed a method, which was based on the k-meansclustering, to do the diagnosis of the failed link in the multi-path situation. In thismethod, after clustering the end-to-end measurement data of the multi-path, we gave ajudgment to the classified data to decide which routing path they belonged to. Bydoing so, it to some extent solved the uncertainty of the end-to-end data of themulti-path destination node in the multi-path situation. Then, we changed thediagnosis problem from the non-tree topology situation into the tree topologysituation. At last, this paper used a classic SCFS algorithm to locate the failed link.Through the analysis of the experimental results, we can come to the conclusionthat: the proposed approach can detect the link state of the last hop which was close tothe multi-path destination node accurately in the minor fault situation.