## 3 Network Coding Enabled Network Tomography
### Topology Inference
A similar procedure is followed in the presence of packet losses, according to which, after performing several independent experiments and collecting a number of observations (coded packets that have arrived at the receivers), the candidate topologies can be distinguished depending on whether \(r_{1}=r_{2}\) and on the observed coefficient differences \(c_{12}-c_{22}\). The described procedures can be applied to a 2-by-\(N\) network on every one of the \({N\choose 2}\) possible pairs of receivers, inferring in this way (in parallel and independently) the type of all constituent 2-by-2 components. Two algorithms that merge the identified 2-by-2 components in order to recover the 2-by-\(N\) topology are provided. The first is suitable when the 1-by-\(N\) tree rooted at source \(S_{1}\) and containing only branching points is known (e.g., it can be inferred using some tomographic method), and the second does not require any such prior knowledge. Both merging algorithms can localize every joining point between two branching points. Starting from a 2-by-\(N\) topology, the inference technique can be extended to the \(M\)-by-\(N\) topology by adding one source at a time in order to connect the 1-by-\(N\) (single source) trees of the remaining \(M-2\) sources. Another active tomography method for the logical topology inference of directed acyclic graphs with \(M\) sources, \(N\) receivers (\(M\)-by-\(N\) network) and maximum total degree \(\Delta+1\) is presented in [30]. Assuming the nodes in the network are capable of (scalar linear) network coding, the exact logical DAG topology is inferred with a single probing experiment during which each link is traversed by only one probe packet and synchronization between the sources is not required. The proposedapproach comprises four stages. First, each of the \(M\) sources generates and transmits (asynchronously) a single probe packet. Every probe packet consists of two parts: the information field and the hop-length field (an integer up to the maximum number of possible intermediate nodes in the topology). The information field of the probe packet \(P_{i}\) generated by source \(S_{i}\) is set according to \(x_{j}\left(P_{i}\right)=\mathbb{1}\{i\ =\ j\}\), \(j=1,2,\ldots,M\), and the hop-length field \(h\left(P_{i}\right)\) is set to 0. In the second stage, every intermediate node \(u\) with \(k\) incoming and \(r\) outgoing links constructs the information fields of the outgoing probe packets according to a component-wise multiplication (provided in [30]). In the third stage, each receiver \(R_{i}\) eventually gets the packet \(\left[\boldsymbol{y}_{i},h_{i}\right]\), where \(\boldsymbol{y}_{i}=\left(y_{i,1},y_{i,2},\cdots,y_{i,M}\right)\in\mathcal{F}_ {q}^{M}\) and the hop-length of \(R_{i}\) is \(h_{i}+1\). The component \(y_{i,j}\) can be expressed as a power of \(\alpha\) as \(y_{i,j}=\alpha^{c_{ij}}\) with \(c_{i,j}=\sum_{l=0}^{h_{i}-1}c_{i,l}^{l}\Delta^{l}\). Based on the above exponents, the hop lengths of the pairwise joining (between two sources and a receiver) and pairwise branching (between one source and two receivers) nodes can be computed. These hop lengths can be leveraged for calculating the path lengths of the three path segments of the 1-by-2 and 2-by-1 components that were proven to uniquely determine the DAG topology in [29]. A 2-step explicit algorithm that recovers the topology of the network from the determined hop lengths of the pairwise branching and joining nodes is provided and comprises the final stage of the proposed approach. In [31], random linear network coding (RLNC) is explored in the context of passive network tomography in the presence of errors, both adversarial and random. The main idea is that the linear transformations produced by RLNC provide insights about the network structure that can significantly aid tomography. Furthermore, given that end-to-end network error-correcting codes are employed, no dedicated probe packets are necessary; hence, passive tomography is a suitable option.