## 6 FIFO and LRU Caching Analysis with Data of Different Sizes
### No Common FIFO, RANDOM and CpR Solution for Objects of Different Sizes  
In contrast to LRU, the common IRM product form solution of Equation (2) is restricted to a unit data size. Because we did not find an explicit statement on this limitation in the literature, we show that hit ratios of FIFO, RANDOM and CpR can differ already in a simple example for \(N=3\) objects \(A\), \(B\), \(C\) with sizes \(sA=1\); \(s_{B}=2\); and \(s_{C}=3\) and a cache size of \(M=4\). Then two objects fit together in the cache, except for \(B\) and \(C\) (\(s_{B}+s_{C}=5>M\)). In this example, the IRM hit ratios of LRU, FIFO, RANDOM and CpR can be analysed by Markov chains, with states for the relevant cache content and state transitions according to the replacement principles of each strategy, as shown in Figure 6. There are six states with one (\(B\) or \(C\)) or two (\(A\) and \(B\), \(A\) and \(C\), \(B\) and \(A\), \(C\) and \(A\)) objects as cache content in steady state. Other content states are ignored as transient states (\(A\)) or when they exceed the cache size (\(B\) and \(C\), \(A\) and \(B\) and \(C\)). The top and bottom cache positions are not distinguished for random evictions, such that four states are sufficient for RANDOM. Figure 6: Markov chains for steady state hit ratio analysis of the caching strategies. The IRM hit ratio analysis first determines the steady state probabilities from equilibrium equations. State-specific hit ratios are given by the sum of the request probabilities of the objects in the cache. The total hit ratio is the sum of state-specific hit ratios weighted by their steady state probabilities. In the case of FIFO, we finally obtain \(h_{IRM}^{FIFO}=1-2p_{B}p_{C}/(p_{B}+p_{C})-p_{A}p_{B}p_{C}/(p_{A}p_{B}+p_{A}p_{C}+ p_{B}p_{C})\). In the case of LRU, the direct computation of the hit ratio via Equation (13) is simpler and equivalent. The exact analysis shows differences in the hit ratios of the four caching strategies. In the example \(p_{A}=0.2\), \(p_{B}=0.7\) and \(p_{C}=0.1\) we obtain the following:  
\[h_{IRM}^{LRU}=\frac{1373}{1800}\approx 76.28\%<h_{IRM}^{FIFO}=\frac{703}{920} \approx 76.41\%<h_{IRM}^{CpR}=\frac{10139}{13240}\approx 76.58\%<h_{IRM}^{ RANDOM}=\frac{3109}{4040}\approx 76.96\%\]  
The differences in the IRM hit ratio results are not large, but they indicate that several well-known results for unit object size do not hold for data of different sizes:  
1. The FIFO, RANDOM and CpR hit ratios are different for variable data sizes. Their common product form solution (2) [6] is restricted to unit-size objects. 2. The proven \"LRU is better than FIFO under IRM\" result [40] is also restricted to unit data size and again violated in the previous example. 3. Moreover, a monotonous increase in the LRU, FIFO, RANDOM and CpR hit ratio curves (HRC) with the cache size \(M\) again holds only for unit data size. Simulations of large caches with objects of different sizes still show results close to the unit size properties, with negligible differences between FIFO, RANDOM and CpR. However, LRU performance can largely deviate from FIFO, etc. for objects of different sizes. The LRU preference for popular objects leads to a higher hit ratio when those objects are small or to a lower hit ratio when they are large. _Value and Byte Hit Ratio_  
Steady state Markov results are usually derived for the object hit ratio. We can include a caching value \(v_{k}\) per object for the benefit of serving the object from the cache. \(v_{k}\) may refer to measures for reduced link load and energy consumption on a transport network or to reduced delay, improved throughput and other QoS aspects from the user's perspective. The value hit ratio (\(VHR\)) of a cache is defined as (\(\forall\)\(j\
eq l\): \(k_{j}\
eq k_{l}\))  
\[VHR_{RMR}=\sum_{ \begin{subarray}{c}k_{l},\ldots,k_{k}=1\\ s_{1},\ldots,s_{k_{l}},\ldots,s_{k_{l}},s_{M}\end{subarray}