# Two-Layer Network Caching for Different Service Requirements
## 3 Model
### Caching Problems
#### 3.3.1 Case1: Fixed-Size Items  
This case study is the basic caching problem, the simplest one in this paper. The contents are the same size. The content popularity value can change from user to user and remain constant over time. In addition, the popularity value is known in advance for investigating the asymptotic performance. This model can be used to represent the access to contents of similar size, which is significantly lower than the cache size, for a time period in which the content popularity may be realistically assumed to be stationary. For example, a single day access to Instagram pictures can be modeled in this way. In fact, the trend of such content popularity after some time from publication can be estimated quite reliably, generally it does not show significant variations for a few days. We decided to include this problem in order to show some basic elements of our approach, which results to be light, and compare it with the optimal hit ratio determined by (2). Subsequent case studies will be characterized by higher complexity. For an item \(\zeta\) requested by the user \(i\), the hit ratio \(P_{hit}\) is given by the probability of finding it either at the layer-1 cache or at any of the layer-2 caches reachable by \(i\), that is, \(\{cache\quad j:\phi_{i,j}=1\}\). We assume the content popularity and the matrix \(\phi_{i,j}\) are given. The caching problem can be formulated as follows. **Problem 1**. : \[ \begin{array}{l}\max\limits_{\phi_{i},\zeta,\zeta}\quad P_{hit}\\ \text{st}\\ \sum\limits_{\zeta=1}^{\text{C}}g_{i,\zeta}\leq K_{2,j}\forall j\in[1,|K_{2}| ]\\ \sum\limits_{\zeta=1}^{\text{C}}q_{i,\zeta}\leq K_{1,i}\forall i\in[1,W]\\ g_{i,\zeta},q_{i,\zeta}\in\{0,1\}.\end{array} \] (3)  
The first two constraints are due to the finite size of caches. Problem 1 can be split in two subproblems. To show this, we first show the following Lemma. **Lemma 1**. : _For any content placement in layer-2 caches, the optimal content placement in cache \(i\) is found by selecting the items having higher popularity for customer \(i\)th from the set of the contents not already cached in layer-2 caches, that is, \(\{\xi\in\Xi:\phi_{i,j}g_{i,\zeta}=0,\forall j\}\)._ \begin{table}
\begin{tabular}{l l} \hline \hline
**Variable** & **Meaning** \\ \hline \(W\): & cardinality of the set of customers; \\ \(\varepsilon_{j}\): & set of items stored in cache \(j\); \\ \(\lambda_{i}:\) & mean request rate of user \(i\); \\ \(d(m,i)\): & density of popularity of item \(m\) for user \(i\); \\ \(\mathbf{D}\): & \([W\times C]\) matrix of \(d(m,i)\) values. \\ \(b_{min}:\) & minimum bandwidth for transmitting a chunk; \\ \(b_{i,j}\): & the bandwidth used to transfer items from cache \(j\) to customer \(i\). \\ \(B_{j}\): & output bandwidth at the \(j\)-th cache server \\ \(\tau:\) & maximum download time; \\ \(\sigma_{i,j}:\) & probability that layer-1 cache \(i\) is connected with the layer-2 cache \(j\). \\ \(P_{hit,i}\): & hit ratio at layer-1 cache \(i\). \\ \(P_{hit,K2}\): & hit ratio at layer-2 caches. \\ \(\mathbf{T}\): & \([1\times|K_{2}|]\) vector of layer-2 cache occupation thresholds. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._Proof. : Let \(P_{hit,i,1}\) be the hit ratio obtained by selecting items as mentioned above by customer \(i\)th. Assume by contradiction that \(\exists\) an item \(\xi_{x}\in\Xi\setminus\bigcup_{j=1}^{K_{2}}\left\{\xi\in\Xi:\phi_{i,j}\mathcal{S} _{j,\xi}=1:q_{i,\xi}=0\right\}\) and an item \(\xi_{y}\in\left\{\xi\in\Xi:q_{i,\xi}=1\right\}\) such that swapping them in cache \(i\), the resulting hit probability \(P_{hit,i,2}>P_{hit,i,1}\). Nevertheless, given the content selection by decreasing popularity generating to \(P_{hit,i,1}\), it results 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}\]  
which contradicts the assumption. Theorem 1.: _Problem 1 can be decomposed in two subproblems, each relevant to layer-1 and layer-2 caching, respectively._  
Proof.