Passive Network Tomography for Erroneous Networks: A Network Coding Approach

Date Added: Oct 2011
Format: PDF

Passive network tomography uses end-to-end observations of network communications to characterize the network, for instance, to estimate the network topology and to localize random or adversarial faults. Under the setting of linear network coding, this paper provides a comprehensive study of passive network tomography in the presence of network (random or adversarial) faults. To be concrete, this paper is developed along two directions: tomographic upper and lower bounds (i.e., the most adverse conditions in each problem setting under which network tomography is possible, and corresponding schemes (computationally efficient, if possible) that achieve this performance) are presented for Random Linear Network Coding (RLNC).