On the theoretical limit to the diagnosis of links in communication networks

We characterize the maximum number of link faults that can be detected automatically in a communication network that is modeled as a undirected graph. The theory of system-level diagnosis, originally developed for diagnosing multiprocessor systems, is used with some enhancements to accomplish this characterization. The concept of one-step t_n, t-diagnosability is developed and a relation is established between the number of nodes n in the system and the maximum number of faulty nodes t_n and links t_l that can be detected. It is shown that a system is t_n, t_l-diagnosable if t_l⩽(n-1)/2-1, thus giving a theoretical upper bound on the number of link failures that can be diagnosed in a network. We also discuss the practical applicability of t _n, t_l-diagnosability to the fault diagnosis of communication networks. The results obtained have implications for network management and system reliability