# Two-Layer Network Caching for Different Service Requirements
## 3 Model
### Caching Problems
#### 3.3.1 Case1: Fixed-Size Items
Once an item \(\xi^{*}\) is cached in \(j^{*}\), in order to allow selecting the same \(\xi^{*}\) element to be cached in other layer-2 caches, that is to implement the OR function in case the same \(\xi^{*}\) element is already cached in some layer-2 caches, the popularity matrix is updated as follows:  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]2  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]3 Mutual relation between parameters. This way, all users connected to the cache \(j^{*}\) will not contribute to the optimization metric if \(\xi^{*}\) is cached in another cache. In order to compare the maximum popularity value of the contents for different users, it is necessary to weight the popularity values with the mean request rate of each customers. In synthesis, we propose the heuristic solution Algorithm1 illustrated in Code 1 for Problem 3. Note that row 7 of Algorithm1 makes a greedy random selection of content \(\xi^{*}\) and cache \(j^{*}\) if multiple pairs that maximize the optimization function exist. ```
1:functionAlgorithm1(\(\Xi,\Phi,\mathbf{P}\), \(K_{2}\), \(\{\lambda_{i}\}\))\(\rightarrow\)\(\varepsilon_{j}\)
2:\(\varepsilon_{j}\leftarrow\phi\quad\forall j\)\(\triangleright\) initialization
3:\(step\gets 1\)\(T_{j}\gets 0\quad\forall j\)\(\triangleright\) thresholds on the cache occupation
4:\(\mathbf{P}(i,\xi)\leftarrow\mathbf{P}(i,\xi)\lambda_{i}\quad\forall i\)
5:while\((\exists j:T_{j}<K_{2,j})\land(step\leq C)\)do\(\triangleright\) core of the greedy algorithm
6:\(\xi^{*},j^{*}\leftarrow\text{random}\;\text{argmax}\big{(}\Phi^{T}\mathbf{P} \big{)}\)
7:if\(T_{j^{*}}=K_{2,j}\)then
8:\(\phi(i,j^{*})\gets 0\quad\forall i\)
9:endif
10:\(T_{j^{*}}\gets T_{j^{*}}+1\)
11: step \(\leftarrow\) step+1
12:\(\mathbf{P}(i,\xi^{*})\leftarrow\mathbf{P}(i,\xi^{*})\big{(}1-\Phi^{T}(j^{*},i)\big{)}\quad\forall i\in[1,W]\)
13:\(\varepsilon_{j^{*}}\leftarrow\varepsilon_{j^{*}}\cup\{\xi^{*}\}\)
14:endwhile
15:return\(\varepsilon_{j}\)
16:endfunction
```  
**Code 1** Solution to Problem 3. The algorithm completes in \(K=\sum_{j=1}^{|K_{2}|}K_{2,j}\) iterations. Let \(M_{opt}\) denote the optimum solution, that is the maximum achievable value of \(P_{hit,K2}\), and \(M_{i}\) the metric produced by Algorithm1 at step \(i\). Given the greedy nature of the algorithm and submodularity of the optimization function, it follows that  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]4  
that is equivalent to say that  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]5  
Hence  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]6 \[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]7 \[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]8  
At the final step of the algorithm  
\[P_{hit,i,2}(\xi)=P_{MZ,i}(\xi_{y})+P_{hit,i,1}-P_{MZ,i}(\xi_{x})\leq P_{hit,i,1}, \tag{4}\]9since \(\left(1-\frac{1}{k}\right)^{K}\leq\frac{1}{e}\). This is a good result since in [32] the authors show that the maximum approximation ratio of a greedy algorithm over a matroid constraint is \(\left(1-\frac{1}{e}\right)M_{opt}\) unless \(\mathrm{P}=\mathrm{NP}\). Under the hypothesis that \(C>>K\), as expected in operation, the complexity of the Algorithm1 is determined by row 7 of it, consisting of a \(\left[\left|K_{2}\right|\times W\right]\) and \(\left[W\times C\right]\) matrix products plus a max determination out of \(\left|K_{2}\right|\times C\) elements iterated \(K\) times. Thus, the complexity of Algorithm 1 is \(O(W|K_{2}|CK)\). If we restrict the set of contents considered to a subset having the higher popularity and are actually candidate for caching, the size of this subset is proportional to \(K\), thus making the complexity of Algorithm1\(O(W|K_{2}|K^{2})\).