Performance Limitation of Group Testing in Network Failure Detection

Abstract

In a network system, there inevitably be a few connection failures at nodes, such as delay. Once a failure occurs, the network administrator must detect failure sources as soon as possible to maintain communication over the network. Group testing is a method for detecting failure nodes in networks using a small number of measurements, provided that the measurement matrix is constructed appropriately. A promising method for constructing measurement matrices is given by the binary correlation matrices. This study analyzes the performance limitation of group testing based on the binary correlation measurement matrix. We derive the upper and lower bounds of the minimum number of measurements needed for network detection. Moreover, we propose a sufficient condition of network topology, under which the failure vertices in the network can be detected with optimal performance, and we also provide a detection scheme with guaranteed exactness for the network. Numerical example indicates that for the network that satisfies the proposed sufficient condition, the administrator can exactly detect the failure vertices with optimal performance by using our proposed detection scheme.

Keywords

• Network
• failure detection
• group testing
• sparse reconstruction
• graph theory