TY - JOUR
T1 - Passive Network Tomography for Erroneous Networks
T2 - A Network Coding Approach
AU - Yao, Hongyi
AU - Jaggi, Sidharth
AU - Chen, Minghua
PY - 2012/9
Y1 - 2012/9
N2 - 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 such as packet losses and link delays, etc. © 1963-2012 IEEE.
AB - 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 such as packet losses and link delays, etc. © 1963-2012 IEEE.
KW - Adversaries
KW - network coding
KW - network errors
KW - passive network tomography
UR - http://www.scopus.com/inward/record.url?scp=84865410774&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84865410774&origin=recordpage
U2 - 10.1109/TIT.2012.2204532
DO - 10.1109/TIT.2012.2204532
M3 - 21_Publication in refereed journal
VL - 58
SP - 5922
EP - 5940
JO - IRE Transactions on Information Theory
JF - IRE Transactions on Information Theory
SN - 0018-9448
IS - 9
M1 - 6216435
ER -