Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs

Abstract

We consider the problem of detecting failures for all-optical networks, with the objective of keeping the diagnosis cost low. Compared to the passive paradigm based on parity check in SONET, optical probing signals are sent proactively along lightpaths to probe their state of health and failure pattern is identified through the set of test results (i.e., probe syndromes). As an alternative to our previous adaptive approach where all the probes are sent sequentially, we consider in this work a non-adaptive approach where all the probes are sent in parallel. The design objective is to minimize the number of parallel probes, so as to keep network cost low. The non-adaptive fault diagnosis approach motivates a new technical framework that we introduce: combinatorial group testing with graph-based constraints. Using this framework, we develop several new probing schemes to detect network faults for all-optical networks with different topologies. The efficiency of our schemes often depends on the network topology; in many cases we can show that our schemes are optimal in minimizing the number of probes.