## 4 Compressed Sensing Enabled Network Tomography
### Loss Estimation  
Building on [32], the authors in [51] claim that it is not necessary for all links to be equally likely to be congested, i.e., to have the same prior probability of being congested. They present a different approach consisting of two steps: (i) the congestion probabilities of the links are uniquely identified from a small set of full network measurements (snapshots) over a period of time by using properties of Boolean algebra, and (ii) the estimated link congestion probabilities are used as prior information, together with subsequent snapshots, to find the links that are actually congested at any time using a _Maximum A-Posteriori (MAP)_ estimator. Let \(\mathcal{P}\) be the set of all paths between the nodes of the overlay monitoring system, referred to as _vantage points_. The number of paths is \(n_{p}=|\mathcal{P}|=n_{B}\cdot(n_{B}-1)\), where \(n_{B}\) is the number of vantage points. For a known topology \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) and set of paths \(\mathcal{P}\), the _routing matrix_\(\mathbf{A}\) is computed as follows: \(a_{ij}=1\) if the path \(p(s,t)\equiv p_{i}\), with \(i=(s,t)\), contains the link \(e_{j}\) and \(a_{ij}=0\) otherwise. Therefore, each row of \(A\) corresponds to a path and each column corresponds to a link. If a column has only zero entries, then the state of the corresponding link cannot be inferred from measurements of the paths in \(\mathcal{P}\). Therefore, by dropping the columns that contain only zero entries, a matrix of dimensions \(n_{p}\times n_{c}\), where \(n_{c}=|\mathcal{E}_{c}|\leq|\mathcal{E}|\) is the number of links that are covered by at least one path in \(\mathcal{P}\), is obtained. If \(Y_{i}\) represents the state of the path \(p_{i}\) (i.e., \(Y_{i}=0\) if \(p_{i}\) is good and \(Y_{i}=1\) otherwise) and \(Z_{k}\equiv Z_{\alpha_{k}}\) is the state of link \(e_{k}\) (\(Z_{k}=0\) if \(e_{k}\) is good and \(Z_{k}=1\) otherwise), the following system of Boolean algebra linear equations between link and path states is established:  
\[Y_{i}=\bigvee_{k=1}^{n_{c}}Z_{k}\cdot a_{ik}, \tag{9}\]  
where \"\(\vee\)\" denotes the binary max operation and each input \(Y_{i}\) is obtained from end-to-end measurements by comparing the path transmission rate \(\phi_{i}\) to a threshold \(t_{p}=t_{l}^{h}\), with \(t_{l}\) being the link threshold and \(h\) being the length of the path: \(Y_{i}=0\) if \(\phi_{i}\geq t_{p}\) and \(Y_{i}=1\) otherwise. Although these equations have multiple solutions (since it is very rare in practice that all the columns of \(\mathbf{A}\) are linearly independent in Boolean algebra), the most probable solution can be found by using the additional information of the probability \(q_{k}\) that link \(e_{k}\) is congested. The vector \(\mathbf{q}=[q_{1}\;q_{2}\;\ldots\;q_{n_{c}}]^{\intercal}\) of the link state probabilities can be uniquely identified from a small number of snapshots. The actual congested links can be estimated by using the resulting vector \(\mathbf{q}\) as prior link state probabilities. Assuming that the set of paths remains unchanged during the measurement period, that the link states are independent from each other, and that there are no disconnected links (i.e., \(0\leq q_{k}<1\;for\;1\leq k\leq n_{c}\)), the link state probability vector \(\mathbf{q}\) is identifiable if and only if the columns of the routing matrix \(A\) are all distinct, i.e., the prior probabilities can be learned by a sufficient large number of snapshots. Given the routing matrix \(\mathbf{A}\) and \(m\) measured snapshots \(\mathcal{Y}=\{\mathbf{y}^{1},\mathbf{y}^{2},\ldots,\mathbf{y}^{m}\}\), with \(\mathbf{y}^{t}=[Y_{1}^{t}\;Y_{2}^{t}\;\ldots\;Y_{n_{p}}^{t}]^{\intercal}\) denoting the \(t\)-th snapshot, the prior probabilities can be calculated.