A Caltech Library Service

Passive Network Tomography for Erroneous Networks: A Network Coding Approach

Yao, Hongyi and Jaggi, Sidharth and Chen, Minghua (2012) Passive Network Tomography for Erroneous Networks: A Network Coding Approach. IEEE Transactions on Information Theory, 58 (9). pp. 5922-5940. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 work provides a comprehensive study of passive network tomography in the presence of network (random or adversarial) faults. To be concrete, this work is developed along two directions: 1) 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). We consider RLNC designed with common randomness, i.e., the receiver knows the random codebooks of all intermediate nodes. (To justify this, we show an upper bound for the problem of topology estimation in networks using RLNC without common randomness.) In this setting, we present the first set of algorithms that characterize the network topology exactly. Our algorithm for topology estimation with random network errors has time complexity that is polynomial in network parameters. For the problem of network error localization given the topology information, we present the first computationally tractable algorithm to localize random errors, and prove that it is computationally intractable to localize adversarial errors. 2) New network coding schemes are designed that improve the tomographic performance of RLNC while maintaining the desirable low-complexity, throughput-optimal, distributed linear network coding properties of RLNC. In particular, we design network codes based on Reed–Solomon codes so that a maximal number of adversarial errors can be localized in a computationally efficient manner even without the information of network topology. The tomography schemes proposed in the paper can be used to monitor networks with other faults su- h as packet losses and link delays, etc.

Item Type:Article
Related URLs:
Additional Information:© 2012 IEEE. Manuscript received April 15, 2010; revised September 16, 2011; accepted October 04, 2011. Date of publication June 12, 2012; date of current version August 14, 2012. All the authors wish to thank the reviewers for their careful and diligent reading of this paper—their comments have significantly improved the results and the structure of this work. The authors also thank Alon Rosen for his comment about pseudorandomness, and Tracey Ho for her suggestions on approximate adversary localization under NRSC. H. Yao was supported by the National Basic Research Program of China under Grants 2007CB807900 and 2007CB807901, the National Natural Science Foundation of China under Grants 61073174, 61033001, and 61061130540, and the National Science Foundation under Grant CNS-0905615. S. Jaggi was supported by the RGC GRF Grants 412608 and 412809, the CUHK MoE-Microsoft Key Laboratory of Human-Centric Computing and Interface Technologies, the Institute of Theoretical Computer Science and Communications, and the University Grants Committee of the Hong Kong Special Administrative Region through Project AoE/E-02/08. M. Chen was supported by the China 973 Program 2012CB315904, the General Research Fund Grants (Project 411008, 411009, 411010, and 411011), and an Area of Excellence Grant (Project AoE/E-02/08), all established under the University Grant Committee of the Hong Kong, as well as two gift Grants from Microsoft and Cisco.
Funding AgencyGrant Number
National Basic Research Program of China2007CB807900
National Basic Research Program of China2007CB807901
National Natural Science Foundation of China61073174
National Natural Science Foundation of China61033001
National Natural Science Foundation of China61061130540
RGC GRF Grant412608
RGC GRF Grant412809
Human-Centric Computing and Interface Technologies CUHK MoE-Microsoft Key LaboratoryUNSPECIFIED
Institute of Theoretical Computer Science and CommunicationsUNSPECIFIED
Hong Kong Special Administrative Region University Grants CommitteeAoE/E-02/08
China 973 Program2012CB315904
General Research Fund Grant411008
General Research Fund Grant411009
General Research Fund Grant411010
General Research Fund Grant411011
University Grant Committee Area of Excellence Grant ProjectAoE/E-02/08
Subject Keywords:Adversaries; network coding; network errors; passive network tomography
Issue or Number:9
Record Number:CaltechAUTHORS:20121005-092958563
Persistent URL:
Official Citation:Yao, H.; Jaggi, S.; Chen, M.; , "Passive Network Tomography for Erroneous Networks: A Network Coding Approach," Information Theory, IEEE Transactions on , vol.58, no.9, pp.5922-5940, Sept. 2012 doi: 10.1109/TIT.2012.2204532 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34701
Deposited By: Tony Diaz
Deposited On:05 Oct 2012 20:46
Last Modified:03 Oct 2019 04:21

Repository Staff Only: item control page