# Cache Servers Placement Based on Important Switches for SDN-Based ICN
## 3 Proposed Work
### Computing Important Switches
This, in turn, indicates that only \(k\) basic vectors can represent the whole matrix \(M\). In comparison with the considering all columns of \(M\) and using only \(q\) basic columns, the approximated representation of \(M\) using only \(k\) basic columns decreases the computation time by decreasing a large number of required basic columns. Now, we have to find \(k\ll q\) basic columns of \(M\) such that they can be used to approximately represent \(M\). This problem belongs to subset selection problems in linear algebra [31] and is NP-complete. There is no algorithm to determine its optimal solution. However, our proposed approach use an approximation solution in [31] to compute a subset of \(k\) columns of \(M\) that represent the space formed by its first \(k\) basic vectors \(\{u_{i}|i\in\{1,...k\}\}\). The first \(k\) basic vectors represent the basic vectors \(u_{i}\) in the first \(k\) terms in the right-hand side of Equation (2). The switches associated with the \(k\) basic columns in \(M\) are called basic or important switches. We explain the subset selection problem to find \(k\) basic columns as follows. **Problem 1**. : _For the matrix \(M_{t\times s}\) and the integer \(k\),the subset selection problem is to find the permutation matrix \(P\) such that_  
\[MP=[M1_{t\times k}\,M2_{t\times(s-k)}], \tag{3}\]  
_where \(M1_{t\times k}\) and \(M2_{t\times(s-k)}\) are matrices. The goal is to contain maximum information and to let all the columns sufficiently independent in \(M1_{t\times k}\)._  
To determine all the columns sufficiently independent of \(M1\), it means to maximize the smallest singular value of \(M1\). For this purpose, first, our proposed approach performs SVD on \(M\) as given in Equation (1). After this, our proposed approach multiplies the matrix \(P\) with the right singular matrix \(V\) and gets:  
\[P^{T}V=\left( \begin{array}{cc}V_{11}&V_{12}\\ V_{21}&V_{22}\end{array} \right),\]  
where \(V_{11}\Re^{k\times k}\). In case \(V_{11}\) is non-singular, we can obtain the lower bound on the smallest singular value \(\sigma_{k}(M1)\) of \(M1\) as follows:  
\[\sigma_{k}(M1)\geq\frac{\sigma_{k}(M)}{||V_{11}^{-1}||}, \tag{4}\]  
where \(\sigma_{k}\left(M1\right)\) represents the \(k\)th (smallest) singular value of \(M_{1}\). By maximizing \(\sigma_{k}\left(M1\right)\), it is equivalent to maximizing the lower bound of \(\sigma_{k}\left(M1\right)\). This is equivalent to minimizing \(||V_{11}^{-1}||\) in Equation (4). To solve this problem, then our proposed approach applies the QR factorization with column pivoting [31] on \(M\). Algorithm 1 describes the overall solution. After computing the important switches, we configure the cache servers to the important switches and do the necessary configuration; we describe the procedure in Section 3.3. ```
Input: matrix \(M_{t\times s}\) and integer \(k\) Output:\(MP=(M1,M2)\) where \(M1\) is matrix of \(t\times k\) Step1: Apply SVD over \(M_{t\times s}\) using Equation (1) Step2: Apply QR factorization with column pivoting to \(M\) using following Equation: \(M=QRP^{T}\) Here, \(Q\), \(R\), and \(P\) are matrices. \(P\) is a permutation matrix. Step2: Perform permutation to all columns of \(M\) through multiplication of \(M\) with \(P\). After this, the first \(k\) columns of \(M\) is \(M1\) as given below \(MP=[M1_{t\times k}\ M2_{t\times(s-k)}]\)
```  
**Algorithm 1** Algorithm for Finding Important Switches.