## 2 Markov Analysis Results for Basic Caching Strategies
### Common Hit Ratio Analysis of FIFO, RANDOM and Clock-Based Caching  
FIFO caches replace the object that is present in the cache for the longest time with the requested object in the case of a cache miss. [PERSON] [8] showed that FIFO caching follows a Markov process under IRM with a transition per request, whose steady state content distribution has a product form solution. The probability \(p_{FIFO}(O_{k1}\), \(\cdots\), \(O_{kM})\) to find the objects \(O_{k1}\), \(\cdots\), \(O_{kM}\) in positions 1, \(\ldots\), \(M\) of a FIFO cache is given by  
\[p_{FIFO}(O_{k1},\,\cdots,\,O_{kM})=c\,p_{k1}\,\cdots\,\,p_{kM}\,(\forall\,j\
eq l \colon O_{kj}\
eq O_{kM};M\text{: cache size; }c\text{: norm. constant}).\]  
[PERSON] [6] proved the same product form solution to be valid also for a RANDOM caching strategy, which randomly chooses the eviction candidate with probability 1/\(M\) among the objects in the cache. Moreover, we confirm a broader scope of product form solutions, including clock-based caching and combinations of FIFO/RANDOM/clock. Clock methods indicate an eviction candidate by a clock hand, which steps one position forward per request (CpR). Upon a cache miss, the requested object replaces the eviction candidate. [PERSON] [4] proposed several variants of the basic CpR method. Soregated clock [11] is a clock scheme which admits new content only if it has a higher score than the eviction candidate. The steady state probabilities \(p_{CpR}(O_{k1},\,\cdots,\,O_{kM})\) of CpR cache content follow the same product form as for FIFO and RANDOM. \[p_{CpR}(O_{k1},\,\cdots,\,O_{kM})=p_{FIFO}(O_{k1},\,\cdots,\,O_{kM})=p_{ RANDOM}(O_{k1},\,\cdots,\,O_{kM})=c\,p_{k1}\,\cdots\,\,p_{kM} \tag{1}\]  
As the main step of a proof, we insert this solution into the equilibrium equations of the underlying Markov chain for CpR cache content. Figure 1 illustrates which transitions are possible from previous states to the content \(O_{k1}\), \(\cdots\), \(O_{kM}\). For a cache hit, a cyclic clock shift leads from content \(O_{k2}\), \(\cdots\), \(O_{kM}\), \(O_{k1}\) to \(O_{k1}\), \(\cdots\), \(O_{kM}\) with a corresponding transition probability \(p_{k1}+\cdots+p_{kM}\). Otherwise, a cache miss leads to \(O_{k1}\), \(\cdots\), \(O_{kM}\)if \(O_{k1}\) is requested as an external object, i.e., with transition probability \(p_{k1}\) from a previous content state \(O_{k2}\), \(\cdots\), \(O_{kM}\), \(O_{l}\). We obtain the following equilibrium equations corresponding to one-step transitions per request to \(O_{k1}\), \(\cdots\), \(O_{kM}\):  
\[p_{CpR}(O_{k_{1}},\ldots,O_{k_{M}})=p_{CpR}(O_{k2},\ldots,O_{kM},O_{k_{1}}) \sum\limits_{j=1}^{M}p_{kj_{j}}+p_{k_{1}}\hskip 28.452756 pt\sum\limits_{l=1}^{N}p_{CpR}(O _{k2},\ldots,O_{k_{M}},O_{l})\]  
The product form solution is substituted and verified for those equilibrium equations:  
\[cp_{k_{1}}\ldots p_{k_{M}}=cp_{k_{2}}\ldots p_{k_{M}}p_{k_{1}} \sum\limits_{j=1}^{M}p_{kj_{j}}+p_{k_{1}}\hskip 28.452756 pt\sum\limits_{l=1}^{N}cp_{k _{2}}\ldots p_{k_{M}}p_{l}\Leftrightarrow\] \[1\
eq\{k_{1},\ldots k_{M}\}\] \[1=\sum\limits_{j=1}^{M}p_{kj_{j}}+p_{k_{1}}\hskip 28.452756 pt\sum \limits_{l=1}^{N}\hskip 28.452756 pt\sum\limits_{ \begin{array}{c}l=1\\ l\
otin\{k_{1},\ldots k_{M}\}\end{array} }^{N}\hskip 28.452756 pt\frac{p_{l}}{p_{k_{1}}}= \sum\limits_{j=1}^{M}p_{kj_{j}}+\sum\limits_{l=1}^{N}p_{l}-\sum\limits_{l=1}^{M }p_{kj_{l}}=1\]  
This main step for proving the CpR steady state solution applies to FIFO and RANDOM strategies in a similar way [6,8]. Transitions in steady state are encountered only  
Figure 1: State transitions for CpR and FIFO to the cache content \(O_{k1}\), \(\cdots\), \(O_{kM}\). between content states representing a full cache, while states with less than \(M\) objects are transient. The proof of the product form solution, Equation (1), is completed by checking whether the Markov chain is ergodic; i.e., a transition path must lead from each content state \(O_{k1}\),..., \(O_{kM}\) to each other with nonzero probability.