## 3 Network Coding Enabled Network Tomography
### Loss Estimation
A path-line matrix (usually denoted as routing matrix \(\mathbf{A}\)) \(\mathbf{\mathcal{M}}=(m_{ij})_{|\mathcal{P}|\times|\mathcal{E}|}\), whose \(|\mathcal{P}|\) rows correspond to the \(|\mathcal{P}|\) paths and \(|\mathcal{E}|\) columns correspond to the \(|\mathcal{E}|\) links, is defined as follows: the element \(m_{ij}\) is equal to \(1\) if the \(i\)-th path in \(\mathcal{P}\) includes the \(j\)-th link in \(\mathcal{E}\) and is equal to \(0\) otherwise. Furthermore, it is proven that the identifiability of a link, which only depends on the network topology, is a necessary and sufficient condition for the consistent estimation of link loss rates. Building on the concept of identifiability, the authors refer to _virtual links_ as the non-identifiable links that are included in the same paths. Therefore, a modified path-link matrix \(\overline{\mathbf{\mathcal{M}}}=(\overline{m}_{ij})_{|\mathcal{P}|\times|\mathcal{E }_{l}\times\mathcal{E}_{V}|}\) is defined as before, where \(\mathcal{E}_{l}\) is the set of identifiable links and \(\mathcal{E}_{V}\) is the set of virtual links. The packet losses on different links are modeled by a set of mutually independent Bernoulli processes; thus, _spatial and temporal independence_ is assumed. Therefore, packet losses may be represented by the following system:  
\[\prod_{j=1}^{|\mathcal{E}_{l}\times\mathcal{E}_{V}|}(\alpha_{j})^{\overline{m} _{ij}}=\beta_{i},i=1,...,|\mathcal{P}|\, \tag{1}\]  
where \(\alpha_{j}\in(0,1]\) is the success rate of the \(j\)-th link and \(\beta_{i}\) is the success rate of the \(i\)-th path, which, using a logarithmic transformation, can be written in the following form:  
\[\overline{\mathbf{\mathcal{M}}}\mathbf{a}=\mathbf{b}. \tag{2}\]  
In most cases, the system described by Equation (2) is under-determined; thus, the authors make use of the network coding technique in order to reveal the inherent correlation between packet losses on links and on different sets of paths, which results in increased bandwidth efficiency and reduced monitoring cost (when compared to multicast probing on trees). More precisely, they implement a framework in two phases. In the first phase, the probe coding scheme takes place. Specifically, \(n\) batches of probe packets are sent from the sources in a synchronized manner. The probe packets are binary vectors of length \(l\), which can be interpreted as elements in a finite field \(\mathcal{F}_{q}\) with an alphabet of size \(q=2^{l}\). In each time window, the coding points (i.e., the intermediate nodes with multiple incoming links) linearly combine incoming probes according to the coding coefficients. The authors establish a lower bound on the probe size, which is necessary for a _valid_ probe coding scheme, that is, a probe coding scheme that enables the identification of the paths that successfully transmitted a probe from the end-to-end observations. Within valid probe-coding schemes, the probe size \(l\) is desired to be as small as possible because it is directly related to bandwidth efficiency. It has been shown that, if one is given a directed acyclic graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with a set of monitored end-to-end paths \(\mathcal{P}\), for valid probe coding schemes, the size \(l\) of the probes transmitted on the paths in \(\mathcal{P}(h,r)\) (i.e., the set of end-to-end paths that include link (\(h\),\(r\)) which is adjacent to receiver \(r\in\mathcal{R}\)) satisfies \(l\geq\left|\mathcal{P}(h,r)\right|\). The second phase entails the inspection of the content of the received probe packets in order to estimate the success rate of all paths and combinations of paths, which increases the rank of the system, thus enabling the estimation of link loss rates. To that end, a modified path-link matrix, \(\widehat{\mathbf{M}}=(\widehat{m}_{ij})_{(|\mathcal{P}|-1)\times|\mathcal{E}_{l} \times\mathcal{E}_{V}|}\), is constructed, where \(\mathcal{P}=2^{|\mathcal{P}|}\) is the power set of \(\mathcal{P}\).