## 3 Network Coding Enabled Network Tomography
### Loss Estimation
The network is again modeled as a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{E}\) corresponds to logical links and packet loss on link \(e\) is an independent and identically distributed (i.i.d.) Bernoulli variable with probability \(0\leq\overline{a}_{e}<1\), where \(\overline{a}_{e}=1-a_{e}\) and \(a_{e}\) is the success probability of link \(e\). The observations at all receivers form a vector \(\mathbf{Y}_{(R)}=(Y_{1},...,Y_{N})\) in the space \(\Omega\subseteq(\mathcal{F}_{q^{M}})^{N}\), where \(M=|\mathcal{S}|\) is the number of sources and \(N=|\mathcal{R}|\) is the number of receivers in the network. The probability mass function for a single observation \(Y\in\Omega\) is \(p(Y;a)=\mathbb{P}_{a}(\mathbf{Y}_{(R)}=Y)\). By letting \(n(Y)\) denote the number of probes during \(n\) conducted experiments for which the observation \(Y\in\Omega\) is obtained, the authors obtain the probability of \(n\) independent observations \(Y^{1},...,Y^{n}\) analytically. In order to measure the per link estimation accuracy, they use the _mean-squared error_ (MSE), while the estimation performance of all links is measured by means of an entropy measure and the covariance matrix is approximated using the Fisher information matrix \(\mathcal{I}\). Applying network coding in trees can be considered as combining probes from different incoming links (at the coding points) using the bitwise XOR operation. Hence, network coding increases bandwidth efficiency as well as the number of identifiable links, since a single packet carries information on more than one paths, which is a compressed way to carry enhanced information (taking advantage of the correlation between different links and paths). Based on the mild assumption that all coding points are located above all branching points, the authors propose an algorithm that efficiently computes the MLE of _all links at the same time_. They define the triplet \((\mathcal{G},\mathcal{S},\mathcal{R})\) as a configuration and \((\mathcal{G}^{d},\mathcal{S}^{d},\mathcal{R}^{d})\) as the dual configuration of \((\mathcal{G},\mathcal{S},\mathcal{R})\) on a graph \(\mathcal{G}^{d}=(\mathcal{V},\mathcal{E}^{d})\) that has the same nodes but reversed edges, i.e., \(e=(i,j)\in\mathcal{E}\) if and only if \(e^{d}=(j,i)\in\mathcal{E}^{d}\), and success rate \(a_{e}^{d}=a_{e}\), associated with every edge \(e^{d}\in\mathcal{E}^{d}\). They select sources \(\mathcal{S}^{d}=\mathcal{R}\) and receivers \(\mathcal{R}^{d}=\mathcal{S}\), noting that a multicast tree (MT) is the dual configuration of a reversed multicast tree (RMT) and that the MLE of those two has the same functional form. Algorithm 1 of [37] implements the above mentioned procedure. The estimates that this algorithm produces are the link loss rates of the original tree. Additional heuristic approaches are presented for loss estimation. Firstly, _subtree decomposition_ partitions the original tree into MTs separated by coding points and, in each of them, employs the Maximum Likelihood Estimator (MLE). Observations of the coding points are inferred from the observations of the leaves; therefore, this algorithm is suboptimal. In addition, a _belief propagation_ (BP) approach is presented, which is based on creating a _factor graph_ corresponding to the estimation problem. The factor graph is a bipartite graph: one set of nodes represents the links (variable nodes) of which the loss rates need to be estimated, while the other set of nodes represents paths (function nodes) that are observed by each received probe. An edge exists in the factor graph between a link and a path if the link belongs to this path in the original graph. This approach can be applied in general topologies as well, while the previous one is applied only on tree topologies. In more general topologies, the benefits of network coding are more pronounced than in tree topologies but so are the challenges posed due to the presence of cycles. Subsequently, an orientation algorithm is proposed for the construction of DAGs.