## 6 FIFO and LRU Caching Analysis with Data of Different Sizes
### Approximation Scheme for the Mean Unused Space in FIFO Caches  
Let \(F_{m}\) denote the cache fill level before the \(m\)th request. The fill level stays unchanged for a cache hit: \(F_{m+1}=F_{m}\). In the case of a cache miss, \(F_{m}\) is increasing by the size of the requested object and decreasing by compensating evictions. We obtain  
\[F_{m+1}=F_{m}+s_{m}^{R}-\sum_{k=1}^{K}s_{m,k}^{E} \tag{18}\]  
where \(s_{m}^{R}\) denotes the size of the object of the \(m\)th request and \(s_{m,k}^{E}\) are the sizes of eviction candidates. \(K\) is the number of required evictions until the requested object fits into the cache, where \(K=0\) if it fits into the currently empty space, i.e., if \(F_{m}+s_{m}^{R}\leq M\). The size \(s_{m}^{R}\) of objects that enter the cache has a discrete distribution \(s(j)\) for the number of bytes or kbytes, with a maximum size \(s_{\max}\). We obtain \(s(j)=\Sigma_{k}\,p_{Entor}(O_{k})\,\text{Prob}(s_{k}=j)\), where the probability \(p_{Entor}(O_{k})\) that an object \(O_{k}\) (re-)enters the cache is computed via Equation (15) on the basis of the FIFO approximation. We assign the same discrete distribution \(s(j)\) also as the size to the eviction candidates. Finally, the fill level \(F_{m}\) can be evaluated in the format of discrete distributions \(f_{m}(j)=\text{Prob}(F_{m}=j)\), where \(M-s_{\max}\leq F_{m}\leq M\). The mean fill level \(E[F]\) is iteratively computed via Equation (18) until steady state is approached when the difference \(|\text{E}[F_{m+1}]-\text{E}[F_{m}]|<\varepsilon\) is becoming negligibly small:  
\[\text{E}[F]=\lim\;_{m\rightarrow\infty}E[F_{m}];\,\text{E}[UCS]=M-\text{E}[F].\]  
The entire computation scheme for the mean fill level \(E[F]\) versus unused cache space \(\text{E}[UCS]\) is described in detail in [21] for LRU caches. As the main difference in a transfer to FIFO, the probability \(p_{Enter}(O_{k})\) is obtained via Equation (15), with an impact also on the distribution of the object sizes \(s(j)\). We compare FIFO approximations in the basic format (14) with the previously described scheme for _UCS_ correction. Therefore, we consider an example with \(N=50\) objects with a uniform size distribution, i.e., \(s_{1}=1,\,\ldots,\,s_{50}=50\), and with independent and Zipfdistributed requests \(p_{k}=\alpha k^{-\beta}\) for \(k=1,\,\ldots,\,50\), where \(\alpha=1/\sum_{k}k^{-\beta}\)[31]. Figure 7 shows the hit ratio curves (HRCs) for three examples:  
1. \(\beta=0\), i.e., for uniform requests among all data objects (\(p_{1}=\ldots=p_{50}=2\%\)),
2. \(\beta=0.8\) with a preference for small objects (\(p_{1}\approx 15.3\%\), \(p_{2}\approx 8.8\%\),..., \(p_{50}\approx 0.67\%\)), and
3. \(\beta=0.8\) with a preference for large objects (\(p_{50}\approx 15.3\%\),..., \(p_{1}\approx 0.67\%\)). The mean object size per request is \(E(S)=25.5\) for uniform requests, and it is \(E(S)\approx 14.1\) or \(E(S)\approx 36.9\), respectively, when small or large objects are preferred. A preference for small objects yields the highest hit ratio, whereas uniform requests lead to the lowest hit ratio for cache sizes \(M\geq 50\). For \(M<50\), the caching efficiency is reduced because of oversize objects if \(s_{k}=k>M\), with the highest drawback in the third case. The three FIFO HRCs in Figure 7 are obtained via simulation, being accompanied by a curve for the basic FIFO approximation of Equation (14) as FIFO Approx.-1, marked with circles, and the approximation with UCS correction as FIFO Approx.-2, marked with triangles. We conclude that the FIFO approximation can be subject to significant deviations when the cache size \(M\) is small in the starting part of the HRC and some popular data objects have a size close to \(M\) or larger. The UCS correction can only partly improve the basic FIFO approximation but indicates the extent of corresponding deviations. We have evaluated the scenario of Figure 7 also for LRU with the basic extended Che approximation [28] and a variant with UCS compensation [21].