# Cache Servers Placement Based on Important Switches for SDN-Based ICN
## 3 Proposed Work
### Computing Important Switches  
As mentioned before that the traffic matrices of the network are spars, we can solve it by using the SVD and QR factorization with column pivoting techniques of linear algebra as follows. First, our proposed approach applies SVD function (technique) on the matrix \(M\) in order to show how SVD can reveal the spatial correlation. After applying the SVD on the matrix \(M\), it decomposes the matrix into three matrices as given in Equation (1):  
\[M_{t\times s}=U_{txt}S_{t\times s}V_{s\times s}^{T}, \tag{1}\]  
where \(U\in\Re^{t\times t}\) and \(U^{T}U=I\), \(V\in\Re^{s\times s}\) and \(V^{T}V=I\), and \(S_{t\times s}\) is a diagonal matrix with diagonal values; they are, say, represented by \(\{\sigma_{i}|i\in\{1,...,t\}\}\) in descending order (i.e., a diagonal value \(\sigma_{i}\geq\sigma_{i+1}\)). These diagonal values are also called singular values and represent the importance of a switch in the matrix \(M\). \(U_{txt}\) is known as the left singular matrix. \(U_{txt}\)'s columns, say they are represented as \(\{u_{i}|i\in\{1,...t\}\}\), represent the left singular vectors and are orthogonal to each other. \(V_{s\times s}\) is the right singular matrix. \(V_{s\times s}^{T}\)'s columns, say they are represented by \(\{v_{i}|i\in\{1,...,s\}\}\), are known as the right singular vectors and are orthogonal to each other. The relation given in Equation (2) is the crucial property of SVD:  
\[M_{t\times s}=\sigma_{1}u_{1}v_{1}^{T}+\sigma_{2}u_{2}v_{2}^{T}+...+\sigma_{s} u_{s}v_{s}^{T}. \tag{2}\]  
It is worth noting that a singular value can be \(\sigma_{i}\geq 0\) in Equation (2). Suppose that we have \(q\) number of positive singular values out of \(s\) number of singular values. Then, one can infer from Equation (2) that every column of \(M\) can be computed by a linear combination of \(q\) left singular vectors, \(\{u_{i}|\sigma_{i}>0,i\in\{1,...q\}\}\), and every one of these vectors \(u_{i}\) has its coefficient of a positive singular value. The \(q\) is called the rank of \(M\). These \(q\) left singular vectors are orthogonal basic vectors and spanning the column space of \(M\). This phenomenon indicates that each \(M\)'s column represents a linear combination of these \(q\) basic vectors. In other words, the \(q\) basic vectors can be recovered using exactly the \(q\) columns of \(M\)[31]. We call such \(q\) columns in \(M\) as its basic columns. Thus, by considering the traffic matrix \(M\in\Re^{t\times s}\) of rank \(q\), we compute its \(q\) basic columns, which represent the \(q\) basic switches in our target scenario. Therefore, the traffic information passing through each switch is completely represented using the linear combination of the traffic information passing through such \(q\) basic switches. In other words, we can completely and correctly represent the matrix \(M\) through these \(q\) basic columns. For collecting the traffic information passing through the switch, the rank \(q\) of a traffic matrix shows that traffic information passing though \(q\) switches can be used to completely and correctly recover the global traffic matrix. Moreover, the traffic matrix \(M\) of a network usually also has a lower rank, say \(k\), which is also known as effective rank and \(k\ll q\). This indicates that the set of singular values are sparsely distributed. In other words, for traffic matrix \(M\), we have only a few large singular values, and other singular values have minimal values. To explain this concept, let consider Equation (2) again. This equation shows that the information of the matrix \(M\) is distributed into \(s\) terms in the right-hand side of the equation. Each term \(\sigma_{i}u_{i}v_{i}^{T}\) isthe product of a coefficient \(\sigma_{i}\) and a matrix \(u_{i}v_{i}^{T}\). Suppose that the first \(k\) terms are very large singular values, where \(k\ll q\), and the rest are small singular values. This means that the first \(k\) terms in Equation (2) concentrates a major portion of \(M\)'s information.