Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography

We study maximal identifiability, a measure recently introduced in Boolean Network Tomography to characterize networks' capability to localize failure nodes in end-to-end path measurements. We prove tight upper and lower bounds on the maximal identifiability of failure nodes for specific classes of network topologies, such as trees and d-dimensional grids, in both directed and undirected cases. We prove that directed d-dimensional grids with support n have maximal identifiability d using 2d(n-1)+2 monitors; and in the undirected case we show that 2d monitors suffice to get identifiability of d-1. We then study identifiability under embeddings: we establish relations between maximal identifiability, embeddability and graph dimension when network topologies are model as DAGs. Our results suggest the design of networks over N nodes with maximal identifiability Omega(log N) using O(log N) monitors and a heuristic to boost maximal identifiability on a given network by simulating d-dimensional grids. We provide positive evidence of this heuristic through data extracted by exact computation of maximal identifiability on examples of small real networks.