Network coding for network tomography
Athina P. Markopoulou, Pegah Sattari · 2012
Network tomography aims at inferring internal network characteristics, such as topology and/or link-level characteristics, such as loss rate or delay, based on measurements at the edge of the network. There is a significant body of work on this problem using multicast and/or unicast end-to-end probes. Independently, recent advances in network coding have shown that there are several advantages from allowing intermediate nodes to process and combine, in addition to just forward, incoming packets. In this dissertation, we revisit the problem of network tomography with network coding. We show that network coding offers several benefits in terms of complexity, accuracy, and bandwidth savings. Our key intuition is that network coding at intermediate nodes introduces topology-dependent correlation in the content of coded packets, which can then be exploited for inferring the coding points. This thesis makes three contributions. First, we revisit multiple-source loss tomography in tree topologies with multicast and network coding capabilities, and we provide, for the first time, a low-complexity Maximum Likelihood Estimator (MLE) for the link loss rates. In addition to the MLE, we also apply and evaluate message-passing algorithms for link loss estimation, both in trees and in general topologies. Second, we study the topology inference problem in multiple-source multiple-receiver (M-by-N) networks. We build on prior work, which infers a general M-by-N topology by first inferring several 2-by-2 subnetwork components, and then merging them to obtain the M-by-N topology. We show that, with simple network coding operations at intermediate nodes, it is possible to perfectly identify every 2-by-2 component, which was not possible previously using only multicast or unicast probes. Furthermore, we propose a new algorithm for merging all 2-by-2 components to obtain the M-by-N topology. We cast the problem as multiple hypotheses testing (in particular, generalized binary search), and we design a greedy algorithm that adaptively selects which 2-by-2 components to measure so as to minimize the number of measurements needed to infer the M-by-N topology, and we analyze its performance. In the last part of the thesis, we revisit the traceback problem, which arises in the context of denial-of-service attacks, where multiple attack sources flood a victim destination by sending a large number of packets. The goal of traceback is to identify the paths traversed by these malicious packets all the way back to the attack sources, by allowing intermediate nodes to mark a dedicated field on headers of packets passing through them with the node id. We incorporate, for the first time, network coding in two different types of traceback schemes: probabilistic packet marking schemes and algebraic traceback. In probabilistic packet marking, routers probabilistically mark packets with a function of their router id. We demonstrate the benefit of network coding, by essentially reducing the traceback problem to a coupon collector's problem. In contrast, algebraic traceback encodes the ids of routers on a single path as coefficients in a polynomial of a single variable. We extend that idea to encode multiple paths into a multivariate polynomial and we establish a one-to-one mapping between multi-path algebraic traceback and a particular network coding problem.