Research Of Mutil-stage Network Fault Detection By Graph Partition

The ever-increasing network scale puts forward higher requirements for network fault management,and network measurement is the most important method to discover network anomalies.Active measurement is widely used in network anomaly detection due to its flexibility and privacy,but the active measurement method will inject additional detection traffic into the network.The measurement object of this research is the linklevel failures.To detect all link failures,the most common design is the measurement cover all links,which will undoubtedly inject a large number of detection packets.In any typical scenario,the number of congested links is only a small part of the network.The ideal design goal is to use the fewest probes to cover these few congested links.To reduce the measurement cost caused by active measurement,this paper designs a two-stage measurement method based on graph partition.The main work is as follows:(1)We proposed a partition-based link transmission importance evaluation method and given an example of the algorithm.Then we could get a set of links to be tested for the first round of measurement according to the order of importance.A greedy-based algorithm is designed to select detection paths according to the set of links.A simulation model of the first round measurement was performed to verify that this method can detect most of the faults,and we also verified the influence of the number of parts on the measurement.(2)According to the detection path status returned by the first round of measurement,the second round of measurement needs to find the suspicious area and further detect the suspicious area.To obtain the suspicious area,we proposed a fault location algorithm based on the link-state and a concept of the minimum recognizable set.The minimum identifiable set obtained by the positioning is called the minimum fault set,and the corresponding area is called the suspicious area.The second round measurement aims at the links in the suspicious area that are not covered by the detect paths selected in the first round.(3)To evaluate the measurement cost of the measurement method proposed in this paper,three types of common random network models are selected,and different parameters are chosen to generate experimental topologies of various scales.To thoroughly verify the applicability of the method,three types of common traffic patterns were selected to simulate the experimental topology.Experiments have proved that,compared with common full coverage methods,the partition-based measurement scheme proposed in our paper has significant advantages in measurement cost.