2017/12/28 by Nicola Galesi, Galesi, Nicola, Fariba Ranjbar +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1712.09856
arxiv created 2019/10/24 · arxiv updated 2019/10/25
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 Ω(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.