## 3 Approximation of the IRM Hit Ratio for FIFO
### Maximum Error Cases of the FIFO Approximation for Small Cache Size \(M\)  
The FIFO hit ratio approximation is highly accurate for large caches, but larger errors are encountered for small caches. In order to identify maximum error cases, the following approach aims to cover the entire range of IRM popularity distributions for small \(M\), \(N\). In particular, we checked all 204 266 popularity distributions whose request probabilities are multiples of 1/50 = 2%, such that \(p_{k}=i_{k}\)/50 with integers \(i_{k}\) for \(k\leq N\leq 50\). The approximation of Equations (4) and (5) is compared to the product form analysis of Equation (2) for all those distributions and for all cache sizes \(M<N\), yielding over a million deviation results. The computation required 2 days on a usual PC, but an exponential increase in the number of distributions will soon impede extensions to a finer raster of 1/51, 1/52, etc. We separated the results for each cache size \(M\) and sorted them according to decreasing deviations. Finally, we obtained lists of the top-\(K\) largest deviations of the FIFO approximation for all popularity distributions in the 2% raster. They strongly suggest that maximum deviations are encountered for popularity distributions of the following type:  
\[p_{1}=p_{2}=\cdots=p_{n}=p/n;\,p_{n+1}=\cdots=p_{N}=(1-p)/(N-n)\to 0\text{ for }N\to\infty, \tag{6}\]  
i.e., there are \(n\) data objects with the same popularity among many more objects with negligible request probabilities. The parameters \(n\), \(p\) specify extreme distributions of the type (6) for different cache sizes \(M\). In our study of popularity distributions in the 2% raster, a sorted list of the largest deviations starts with hundreds of cases which are closest to a specific case of the format of Equation (6). The same behaviour has also been experienced by [PERSON] [23] and [PERSON] et al. [24] for maximum deviations of approximations to the LRU hit ratio; see Section 4. An example of the top-10 maximum error cases of approximations in the 2% raster is shown in Figure 4, which are all near the corresponding maximum error case of the format (6). The distribution type (6) leads to simple direct solutions for the approximation Equation (5) and for the exact approach of Equation (2). A substitution of Equation (6) into Equations (4) and (5) results in a quadratic equation for \(\overline{T}_{InCache}\) and an explicit solution for \(h_{IRM}^{FIFO}\):  
\[h_{IRM}^{FIFO}\approx n(p/n)\overline{T}_{InCache}/(\overline{T}_{InCache}+n/ p);h_{IRM}^{FIFO}\approx 1-M/\overline{T}_{InCache}\Rightarrow\]  
\[\overline{T}_{InCache}\approx M(\overline{T}_{InCache}+n/p)/(\overline{T}_{ InCache}+n/p-p\overline{T}_{InCache});\Rightarrow\]  
\[\overline{T}_{InCache}\approx(M-n/p\pm\sqrt{(M+n/p)^{2}-4 Mn})/(2-2p)\]  
The special format of Equation (6) also allows for computing the probabilities \(q_{mt}\) that we find \(m\) out of \(n\) popular objects in the cache for \(m\) = 0,..., \(\min(n,M)\). In this way, we obtain the exact hit ratio result \(h_{IRM}^{FIFO}\) = \(\sum_{m}q_{mt}\cdot m\cdot p/n\), especially for the format (6). We derive \(q_{m}\) by collecting all the corresponding components from Equation (2):  
\[q_{mt}=c\bigg{(} \begin{array}{c}n\\ m\end{array} \bigg{)}\bigg{(} \begin{array}{c}N-n\\ M-m\end{array} \bigg{)}\bigg{(} \begin{array}{c}p\\ n\end{array} \bigg{)}^{m}\bigg{(} \begin{array}{c}1-p\\ N-n\end{array} \bigg{)}^{N-m}\]  
A further evaluation of this expression in the limit \(N\to\infty\) yields the following simple scheme:  
\[q_{mt+1}/q_{mt}=(n-m)(M-m)p/[n(m+1)(1-p)],\]  
which leads to a direct evaluation of \(q_{0}\cdot\cdot\cdot\cdot\), \(q_{M}\) and finally of \(h_{IRM}^{FIFO}\). In Table 2, the worst FIFO error cases are listed for \(M\) = 1,..., 10. The parameters \(p\), \(n\) specify the probabilities \(p_{1}=\cdots=p_{n}=p/n\) of the extreme format (6). The approximation is exact for uniform distributions, as confirmed by substituting \(h_{IRM}^{FIFO}-M/N\) and \(p_{k}=1/N\) into Equation (5).