# Two-Layer Network Caching for Different Service Requirements
## 3 Model
### Caching Problems
#### 3.3.1 Case1: Fixed-Size Items
: Let \(\left\{\xi\right\}_{opt}=\left\{\xi:\exists g_{j,\xi}=1\lor q_{i,\xi}=1\right\}\) be the optimal content placement due to the optimal solution of Problem 1. This solution can be written as \(\left\{\xi\right\}_{opt}=\left\{\xi\right\}_{K1}\bigcup\left\{\xi\right\}_{ K2}\), where \(\left\{\xi\right\}_{K1}=\left\{\xi:q_{i,\xi}=1\right\}\) and \(\left\{\xi\right\}_{K2}=\left\{\xi:\exists g_{j,\xi}=1\right\}\) are the set of items stored in layer-1 cache and layer-2 caches, respectively. Due to Lemma 1, given \(\left\{\xi\right\}_{K2}\), \(\left\{\xi\right\}_{K1}\) follows. Hence, Problem 1 can be written as follows:  
**Problem 2**. : \[\max_{q_{i,\xi}g_{j,\xi}}P_{hit}=\max_{g_{j,\xi}}P_{hit,K2}+\sum_{i=1}^{W} \max_{q_{i,\xi}g_{i,\xi}g_{i,\xi}=0}\quad P_{hit,i}\] (5) \[\sum_{\xi=1}^{C}g_{j,\xi}\leq K_{2,i}\forall j\in[1,|K_{2}|]\] \[\sum_{\xi=1}^{C}q_{i,\xi}\leq K_{1,i}\forall i\in[1,W]\] \[g_{j,\xi},q_{i,\xi}\in\left\{0,1\right\}.\]  
Since the part of the optimization problem relevant to layer-1 caches is readily solved through Lemma 1, the remaining problem to be solved is the following:  
**Problem 3**. : \[\max_{g_{j,\xi}} P_{hit,K2}\] (6) \[s!\] \[\sum_{\xi=1}^{C}g_{j,\xi}\leq K_{2,i}\forall j\in[1,|K_{2}|]\] \[g_{j,\xi} \in\{0,1\}.\]  
\(P_{hit,K2}\) can be written considering that an item requested by a customer could be cached in one or more than one layer-2 connected caches. This replication could be due to the different content popularity distribution for the customers connected to the same layer-2 cache. Figure 3 is a graphical representation of the parameters defined above. The example in this figure shows how they combine for including the popularity of a content in the optimization function, for a given user, by caching it in two out three reachable caches, indicated by ones in the \((i,j)\) plane. \[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}\]0Since the OR function in (7) is monotone not decreasing, and the marginal contribution for caching an additional item is not increasing with the size of the set of the previously cached items, the function \(P_{hit,K2}\) is \(submodular\)[32]. It is very easy to show that the inequality constraints in (6) can be mapped into a uniform matroid, with the ground set corresponding to the set of items. Some details on uniform matroids are reported in Appendix. Thus, the optimization problem consists of the maximization of a monotone submodular function over the independent sets of a matroid. This class of problems has been studied in depth [32]. They can be hastened by the use of greedy algorithms with known achievable performance. Looking at the maximization function (7), the atomic elements that can be greedily selected to increase its value are the individual items. The marginal contribution due to caching each element requested by a user \(i\) in the \(j\)-th cache depends on both its popularity for user \(i\) and the presence of the same element in other caches connected to the other users that can be served also by the \(j\)-th cache. Thus, the OR function affects the \(state\) of the cache before caching an additional element. When no items are already cached, the item that is greedily cached first is the one that adds the maximum amount of popularity. That is  
\[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}\]1  
where \(\Phi\) is the \([W\times|K_{2}|]\) matrix including the elements \(\phi_{i,j}\) and \(\mathbf{P}\) is the \([W\times C]\) popularity matrix initialized by the \(P_{MZ,i}(\xi)\) values for each referred item.