Paper Info
Title
Non-Adaptive Fault Diagnosis For All-Optical Networks Via Combinatorial Group Testing On Graphs
Abstract
We consider the problem of detecting failures for alloptical 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.
Year
DOI
Venue
2007
10.1109/INFCOM.2007.87
INFOCOM 2007, VOLS 1-5
Keywords
Field
DocType
network topology,sonet,fault detection,signal processing,parity check,lower bound,testing,network management,group testing,graph theory
Graph theory,Signal processing,Parity bit,Fault detection and isolation,Network topology,Network management,Mathematics,Synchronous optical networking,Design objective,Distributed computing
Conference
ISSN
Citations 
PageRank 
0743-166X
19
1.60
References 
Authors
11
5
Name
Order
Citations
PageRank
Nicholas J. A. Harvey190957.85
Mihai Patrascu2115349.84
Yonggang Wen32512156.47
Sergey Yekhanin498352.33
Vincent W. S. Chan513023.21