## 3 Network Coding Enabled Network Tomography
### Topology Inference
Assuming directed acyclic and delay-free networks where the capacity of each edge is normalized to one symbol of \(\mathcal{F}_{q}\) per unit time and there is a single source that communicates with a single receiver, both topology inference (the receiver wishes to correctly estimate the upstream network topology) and error localization (the receiver wishes to identify the locations of occurred network errors) are considered. Common randomness (i.e., all candidate local coding coefficients \(\{\beta(u,v,w),\ u,w\in\mathcal{V}\}\) of node \(v\in\mathcal{V}\) are chosen from its local random codebook \(\mathcal{R}_{v}\) and the set of all local random codebooks \(\mathfrak{R}=\{\mathcal{R}_{v},\ v\in\mathcal{V}\}\) is a priori known to the receiver) is shown to be necessary and sufficient for recovering the topology under RLNC. Specifically, two types of common randomness are defined: (i) weak type for random errors, where each distinct element \((u,w)\in\mathcal{V}\times\mathcal{V}\) indexes a distinct element in the codebook \(R_{v}\) of node \(v\in\mathcal{V}\) and the local coding coefficient \(\beta(u,v,w)\) is chosen as the element \(\mathcal{R}_{v}(u,w)\), and (ii) strong type for adversarial errors, where each distinct element \((u,w,w^{\prime})\in\mathcal{V}\times\mathcal{V}\times\mathcal{V}\) indexes a distinct element in the codebook \(R_{v}\) of node \(v\in\mathcal{V}\) and the coding coefficient \(\beta(u,v,w)\) is chosen as \(\beta(u,v,w)=\sum_{(v,w^{\prime})\in\mathbf{Out}(v)}\mathcal{R}_{v}(u,w,w^{ \prime})\), with \(e(v,w^{\prime})\) denoting the edge from node \(v\) to node \(w^{\prime}\) and \(\mathbf{Out}(v)\) corresponding to the set of all outgoing edges of node \(v\). Topology inference in the presence of adversarial errors is based on the idea that, for strongly connected networks, the transform matrices generated by every pair of networks are very different. Hence, no matter what changes an adversary may perform, he/she is unable to make the transform matrix of one network resemble that of another. The proposed algorithm operates on the overall (polluted with the adversarial errors) transform matrix that is observed by the receiver and finds the closest (in terms of rank distance) matrix that corresponds to an error-free network. The topology is estimated as the one corresponding to this closest matrix. Furthermore, a polynomial time algorithm for inferring the topology under random errors is also provided. The algorithm proceeds in two stages. First, a set of candidate _Impulse Response Vectors_ (IRVs--unit impulse responses, linear transformations from each edge to receiver) is recovered during several rounds of successful (i.e., the number of errors does not exceed the bound \(C\)-1, where \(C\) is the min-cut from source to receiver) source generations. Then, the obtained IRV information is leveraged to recover the topology after filtering out the fake candidate IRVs. Regarding error localization, the detection of the edges where adversarial errors have been introduced is reduced to the problem of detecting IRVs in the error matrix. This detection is shown to be computationally intractable even when the receiver knows in advance the topology and the local encoding coefficients. A polynomial time algorithm is presented for the localization of random errors. Finally, a new type of RLNC called _Network Reed-Solomon Coding_ (NRSC) that is based on Reed-Solomon codes and incorporates the use of virtual IRVs is proposed in order to improve the performance of tomographic algorithms in terms of computational efficiency and robustness to dynamicity. This applies especially to the adversarial error model, for which the previously presented schemes require exponential time in terms of network parameters. Under NRSC, a maximal number of adversarial errors can be localized in a computationally efficient manner even without knowing the network topology.