# Two-Layer Network Caching for Different Service Requirements
## 3 Model
### Caching Problems
#### 3.3.3 Case 3: Guaranteed Download Time
In this way, it is possible to weight the popularity of contents for each customer with the probability of connection with caches. This approach would lead to the maximization of the expected popularity of the cached contents, without any specific guarantees. Although this case study could be of interest in operation, no significant algorithmic novelties can be added with respect to the previous cases. Thus, we present a more challenging problem that can be formulated by using stochastic network connections between users and layer-2 caches. This problem consists of maximizing the popularity of cached contents while providing the same guarantees of Problem 3, along with a given probability bound of accessing them. In more detail, we still include the possibility of taking advantage of parallel content download. This means that contents can be of different size and they can be split in portions of arbitrary size, in order to cache them in the free cache memory. In addition, we require that the entire content is cached. Since the links between users and layer-2 caches are stochastic, we consider a probability threshold \(P_{t}\) of accessing the cached contents. This is the probability value for which the cached contents are considered available to users. Below this probability value, the caching service is considered unacceptable. Since the probability of links can be lower than \(P_{t}\), in order to obtain the desired probability it is possible to replicate contents, or a portion of them, in different caches. In what follows, we assume statistically independent links, so in case of storing the same replica of content in different caches, the probability of having the content available can be found by considering statistically independent events. In synthesis, a content can be split and cached in different caches for having the whole of it available, and any portion of it can replicated in any caches for obtaining the desired access probability. This case study may be representative of different challenging situation that have recently generated research interests. For example, some edge computing applications, typical of 5G systems, leverage real time capabilities of cellular systems. Layer 2 caches with performance guarantees may either be implemented in the edge, for example, in the intersection of different network slices. The stochastic nature of the radio links make the proposed case study of interest. In what follows \(\sigma_{i,j}\) indicates the probability of the link \((i,j)\). The relevant problem can be formulated as as follows:



Note that in case of equal size layer-2 caches, the steps 13 and 14 are not necessary. In this case, it is easily to see that the worst case computational cost of the procedure is \(K_{2}^{2}\), corresponding the extreme case that each cache probability is below the threshold \(P_{t}\) and each cache is combined with all others. After the Procedure3 is accomplished, Algorithm3 can be used to allocate contents to virtual caches, and this allocation is used to store contents in physical caches. Figure 4: Cache processing procedure: (**a**): Physical caches; (**b**): Physical caches under probability threshold; (**c**): Cache combination; (**d**): Virtual caches. ### Population of Layer-1 Caches

Once layer-2 caches are populated, layer-1 caches can be easily populated by selecting, for each user, the most convenient contents not cached in the reachable layer-2 caches. The criterion used may either be the content popularity for fixed content size, or density of popularity for variable content size. The Procedure4 in Code 7 below is for fixed content size. The extension to variable content size is straightforward.