Bipartion Graph Fault Propagation Model And Diagnosis Algorithm

With the rapid development of information technology, computer network fault management is becoming more and more important. Network fault diagnosis is the core of network management. How to improve the ability of network fault diagnosis and how to achieve diagnosis efficiently and accurately are becoming more and more important. It is also important as to reduce the cost of network maintenance and improve service reliability. This article focuses on achieving efficient network fault diagnosis, doing a lot of research on improving fault propagation model and fault diagnosis algorithm.Firstly, we have done research on the network transmission failures phenomena. This article uses topological sorting and breadth-first search theory to remove those redundant information of the traditional model which based on the fault propagation causal map. Then introduce hierarchical diagnostic theory, which proposes the top-Layered fault propagation model of bipartite graph. This model removes the disadvantages of the traditional model, which has large amount of calculation and complex model.Secondly, according to the different size of network and requirement, we propose two different fault diagnosis algorithms. And put the heuristic idea into recursive fault diagnosis algorithm, and then propose fault diagnosis based on improving heuristic and recursive algorithm; this algorithm overcomes the disadvantages of traditional recursive fault diagnosis algorithm on high time complexity and has high reliability. But with the increase of network nodes, the heuristic fault diagnosis algorithm heavily increases time complexity, which doesn’t fit large-scale network environment. Through the change of fault diagnosis objective function, turning fault diagnosis problem into0-1integer programming problem. Lagrangian relaxation algorithm can solve the0-1optimization problems efficiently, and then propose the Lagrange fault diagnosis algorithm, through the simulation analysis, we draw a conclusion that the Lagrange fault diagnosis algorithm has higher accuracy, higher speed, and it fits large-scale network system. And fault diagnosis based on improving heuristic and recursive algorithm fits the small-scale network system which requies very high level of reliability.Finally, we build up a set of fault diagnosis system. System uses distributed system structure. And the system includes the user interface, the data acquisition module, reference fault diagnosis module, data processing, management, and storage module.