## 3 Network Coding Enabled Network Tomography
### Loss Estimation
\(\widehat{\mathbf{M}}\) is referred to as a _type-2 modified path-link matrix_, and the modified system is expressed as follows:  
\[\widehat{\mathbf{M}}\mathbf{a}=\mathbf{c}, \tag{3}\]  
where \(\mathbf{c}=(c_{i})_{(|\mathcal{P}|-1)\times 1}\), \(c_{i}=\log\theta_{i}\) and \(\theta_{i}\in\{\theta_{1},\theta_{2},...,\theta_{|\mathcal{P}|-1}\}\) denotes the success rate of the \(i\)-th path set in \(\mathcal{P}\setminus\emptyset\). For each path set in \(\mathcal{P}\setminus\emptyset\), the \(n\) probe batches sent can be considered as a binomial experiment with \(n\) trials; thus, a random variable \(Y_{i}\) can be defined as the number of received probes whose contents represent that a probe (or batch of probes) has been successfully transmitted on the path (or the paths) in the \(i\)-th path set. The sample proportion \(\hat{\theta}_{i}=Y_{i}/n\) is a maximum likelihood estimator of \(\theta_{i}\), which gives the estimator \(\hat{\mathbf{c}}\) of \(\mathbf{c}\). Now that the above system described by Equation (3) is over-determined \((|\mathcal{P}|-1)\geq|\mathcal{E}_{l}\times\mathcal{E}_{V}|)\), \(\hat{\mathbf{a}}\) can be calculated by means of _least squares_. Simulations comparing the proposed linear algebraic (LA) approach to the belief propagation (BP) approach showed that the former achieves better estimation accuracy after sending reasonably sufficient probes (\(n>400\) probe batches for a topology consisting of 10 nodes and 15 edges). Additionally, the proposed LA approach allows the use of a small number of sources, the locations of which in the network can be flexibly chosen. The work in [35] extends [34] by addressing the problems that were not explored there. Firstly, an algorithm is developed in order to find a valid probe coding scheme such that the minimum probe size is achieved. To that end, the authors of [35] construct auxiliary tree topologies, \(\mathcal{T}_{e}\), each associated with one particular end link \(e=(h,r)\) to the root node, where the root node of \(\mathcal{T}_{e}\) corresponds to the destination node \(r\) in \(\mathcal{G}\). The leaves of the auxiliary tree correspond to the sources of \(\mathcal{G}\) that use link \(e\) to relay packets to the root node. The number of leaves is equal to the number of paths that traverse link \(e\). Each \(\mathcal{T}_{e}\) corresponds to the subgraph \(\mathcal{G}_{e}\). Based on the auxiliary trees and, more specifically, based on the number \(n_{i}\) of leaf nodes that correspond to the \(i\)-th incoming link of a coding point \(u_{k}(v)\) in \(\mathcal{T}_{e}\), the coding coefficients are selected as \([2^{0},2^{n_{1}},2^{n_{1}+n_{2}},...,2^{n_{1}+n_{2}+\ldots+n_{t(n_{k}(v))-1}}]\), where \(t(u_{k}(v))\) is the number of incoming links to \(u_{k}(v)\). The size of the probe packets is decided by means of combining the different sets of subgraphs with overlapping links as one subgraph set, where the cardinality of the set of leaf nodes that corresponds to the combination of these subgraph sets is the maximum of the cardinalities of the sets of leaf nodes corresponding to each individual subgraph set. This extends the lower bound on probe size of [34] for a set of subgraphs with overlapping links, as follows: for the probes that are transmitted on subgraph set \(\mathcal{G}_{e}\), the probe size should satisfy \(l_{\mathcal{G}_{e}}\geq\max_{e\in\mathcal{  
for links and paths to be identifiable and _reversible_ (they introduce the notion of the _dual configuration_), (c) designing the probes that are sent from the sources (size and content) as well as the coding that will be done from the intermediate nodes with multiple incoming links (coding points) based on appropriate coding coefficients (they introduce the notion of _path monomials_), and ultimately, (d) presenting techniques for accurate loss estimation while calculating errors and confidence intervals using the _Fisher_ information matrix.