## 3 Network Coding Enabled Network Tomography
### Loss Estimation  
Any link statistic (e.g., loss rate or mean delay) can be mapped to a binary (good/bad) performance measure by setting a threshold above which the performance is classified as bad (otherwise, it is classified as good). The same classification can be extended to paths comprising multiple links, i.e., a path is considered bad if it contains at least one bad link. A class of network tomography in which links can have one of two states, namely good or bad, and that consists of observing the status of end-to-end paths and based on that inferring the status of individual network links has been introduced in [32]. In particular, the author presents a quick and simple inference algorithm that identifies with high likelihood the worst performing links using only uncorrelated end-to-end measurements. The author considers a logical routing tree network topology consisting of paths from a single source (the root) to multiple destinations (the leaves), assuming that this topology is accurately known. The proposed _Smallest Consistent Failure Set_ (SCFS) algorithm infers the locations of bad links in a (logical) routing tree, using a single measurement (snapshot) of the good/bad status of each source-to-leaf path. It attributes a pattern of bad paths as being caused by the smallest possible set of bad interior links consistent with it. Specifically, it designates as bad only the links nearest the root that are consistent with the observed set of bad paths. A link is classified as bad when there are no good paths from the corresponding terminating node to its descendant leaves but a path through its parent is known to be good. Adopting the previous formulation (i.e., assuming that the vector \(\mathbf{X}\) of the individual link attributes is binary with \(X_{i}=1\) or \(0\) indicating if the corresponding link is congested or not), the authors in [33] focus on the case of a single congested link within the network, i.e., vector \(\mathbf{X}\) has only one nonzero component. Sufficient conditions on the network coding coefficients of the intermediate nodes and the training sequence under which 1-identifiability (congestion status of a single link can be inferred from the end-to-end measurements) is guaranteed for any logical network (i.e., a network in which the interior nodes have degrees greater than or equal to three) are derived. Based on these conditions, a lower bound for the probability of 1-identifiability under random network coding (i.e, nodes pick their network-coding coefficients randomly) is calculated. Furthermore, a way to construct a training sequence that allows identifying the location of a congested link inside the network is presented, and the trade-off between the length of training slots and the size of the network coding alphabet (i.e., the time needed to identify the congested link and the size of network coding packets) is established. Although the previous results are derived for networks with a single source-destination pair, they can be applied to a multiple-source multiple-destination network by considering the equivalent single-source single-destination network, where the set of sources and destinations have been substituted by a single super node source and destination, respectively. In [34], a linear algebraic approach for developing consistent estimators of link loss rates in mesh topologies using network coding is presented. The network is modeled as a directed acyclic graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) and \(\mathcal{S},\mathcal{R}\) represent the set of source nodes and the set of receiver nodes, respectively.