Network tomography seeks to infer internal link status parameters (such as delay) through end-to-end measurements at (external) boundary nodes. As can be expected, such approaches generically suffer from identifiability problems; i.e., inability to uniquely identify individual link status for many typical network topologies. Background results characterizing network identifiability under end-to-end probe will be first presented. We next introduce an innovative approach to tomography based on linear network coding at all internal nodes and provide sufficient conditions under which any logical network is guaranteed to be identifiable.
Typically, network monitoring seeks to identify the few (relative to total number of network edges) congested links at any instant. In the second part of this talk, we describe methods that exploit this inherent sparsity in the problem. We establish a connection between network tomography problem and binary compressed sensing using expander graphs to
- provide conditions on the routing matrix of networks for which the network is k=1-identifiable.
- derive upper-bounds on estimation error on link delay when network in 1-identifiable.
Copyright Notice