## 4 Compressed Sensing Enabled Network Tomography
### Loss Estimation
We note that a \((t,\epsilon)\)-expander is a bipartite simple graph \(\mathcal{G}=(\mathcal{A},\mathcal{B},\mathcal{E})\) with left degree \(d\) such that, for any \(\Theta\subset\mathcal{A}\) with \(|\Theta|\leq t\), the following condition holds: \(|\mathcal{N}(\Theta)|\geq(1-\epsilon)d|\Theta|\), where \(\mathcal{N}(\Theta)\) is the set of neighbors of \(\Theta\), \(t\) is the _expansion factor_, and \(\epsilon\) is the error parameter. Simulation results show that _weighted \(\ell_{1}\) minimization_ method performs better than both the unweighted counterpart and CLINK algorithm [51] in terms of estimation accuracy, detection rate (i.e., the fraction of links that are correctly identified as bad), and false positive rate (i.e., the fraction of links that are good but are diagnosed as bad). Another method for the localization of the \(k\)-sparsely congested links (the rest links have packet loss rate near zero) with only a limited number of path measurements is presented in [53]. The authors propose a CS based method for estimating the congestion probabilities of the individual links based on the deficient (i.e., not full rank) measurement matrix (i.e., the historical deficient path measurements). These estimated congestion probabilities are then utilized in conjunction with the most recent measurement snapshot by a greedy iterative estimation algorithm that locates the most possible sparsely congested links. In [54], a different approach to loss tomography is proposed. Based on compressed sensing, the proposed scheme consists of offline and online parts. The offline part is responsible for the measurement paths (or equivalently the routing matrix) construction when a network with only two monitoring nodes (a single source and a single destination) is considered. Moreover, it is assumed that an arbitrary number of bidirectional measurement paths can be established between the two monitoring nodes. The algorithm that constructs the measurement paths is combined with an algorithm that discovers if a set of low-quality links (where low-quality links correspond to the nonzero componentsof the link vector \(\mathbf{X_{t}}\) in the \(t\)-th time window) is a \(k\)-sparse-identifiable set or not in order to create a \(k\)-identifiable routing matrix \(\mathbf{A}\) that enables the solution of equation \(\mathbf{Y_{t}}=\mathbf{A}\mathbf{X_{t}}\), when \(\mathbf{X_{t}}\) is \(k\)-sparse. In greater detail, the construction of measurement paths from source \(s\) to destination \(d\) and vice versa (reverse paths) takes place in three steps by adding appropriate paths one at a time from the set of all possible paths between the two nodes. First, the maximum set of link-disjoint paths (i.e., no links are shared among the paths) is constructed. Then, the set of all existing acyclic paths from \(s\) to \(d\) and the respective reverse paths are given by a path enumeration algorithm. New measurement paths are selected one by one based on the minimization of a suitable cost function until the maximum number \(N_{max}\) of \(k\)-sparse-identifiable sets corresponding to the potential use of all existing paths and reverse paths is reached. The online part is responsible for low quality link detection. The authors consider practical situations in which link quality vector \(\mathbf{X}\) is _approximately sparse_ and estimate the _steady-state path loss rates_\(Q_{w_{i}}^{(t)}\) (where \(w_{i}\) refers to the \(i\)-th path and \(t\) refers to the \(t\)-th time window), which they subtract from both vector \(\mathbf{X}\) and the measurement vector \(\mathbf{Y}\), thus formulating modified vectors \(\mathbf{X}^{(t)}\) and \(\mathbf{Y}^{(t)}\). Via this procedure, the values of the elements of \(\mathbf{X}^{(t)}\) representing normal links are closer to 0 than the corresponding values of \(\mathbf{X}\); thus, \(\mathbf{X}^{(t)}\) is closer than \(\mathbf{X}\) to an exactly sparse vector.