Adaptive boolean network tomography for link failure detection

In this paper, we consider boolean network tomography to identify link failures in a network. In boolean network tomography, the relationship between end-to-end measurements and link states are represented with a system of boolean equations, and failure links are identified by solving the equations. In order to establish measurement paths efficiently, we propose an adaptive boolean network tomography scheme, where measurement paths are established sequentially according to a candidate set of failure links. Here, to derive the candidate set, we extend CBP (Combinatorial Basis Pursuit), a representative decoding algorithm in Combinatorial Group Testing, and utilize its property that it can identify failure links without false negative errors. We evaluate the performance of the proposed scheme in terms of the number of measurement paths and compare it with a non-adaptive boolean network tomography scheme. Furthermore, we propose mobility-assisted boolean network tomography, which can improve the ambiguity problem in boolean network tomography.