تجزیه و تحلیل حد سیال FIFO و ذخیره سازی RR برای مدل های مرجع مستقل

We study the fluid limit analysis of random replacement (RR) caching for the independent reference model. Applying the limit theorem for the mean field interaction model, we derive the fluid limit of fault probability in the transient state as well as in the steady state. Since the stationary fault probability for the RR cache is identical to that for the first-in first-out (FIFO) cache, our results on the stationary fault probability are available for the FIFO caching. We see that the fluid limit of stationary fault probability that we obtain is coincident with the existing heuristic approximation of stationary fault probability. That is, our fluid limit analysis gives a rigorous theoretical foundation to the heuristic approximation.

In computer systems and communication networks, a caching technique is used for high-speed access to a finite subset out of a large number of items by storing the subset in a quickly accessible memory, called a cache. For this technique to work well, a replacement rule called a caching algorithm is crucial; that is, which items should be stored in the cache and how they should be updated. The performance of a caching algorithm is often evaluated in terms of the fault probability, which is the probability with which the requested item is not found in the cache. The least-recently-used (LRU) and first-in first-out (FIFO) caching algorithms are well-known simple algorithms and have been studied in the literature. To keep frequently requested items in the cache, the LRU algorithm works as follows: when the requested item is not in the cache, the least recently requested item in the cache is replaced with the requested one. In the FIFO algorithm, on the other hand, when the requested item is not in the cache, the oldest item in the cache is replaced with the requested one. While the LRU algorithm performs relatively well and has been applied in many systems, the FIFO is shown to have higher fault probability than the LRU for the independent reference model, where requests for items are independent and identically distributed (i.i.d.) (see, e.g., [1]). Nevertheless, since some complex caching algorithms combining the LRU and FIFO have been proposed recently, such as the Full2Q by Johnson and Shasha [2] and the Multi-Queue by Zhou et al. [3], it is still meaningful to study the FIFO algorithm to evaluate the performance of such complex algorithms. The existing works concerning the analysis of the FIFO algorithm have almost all been done for the independent reference model. King [4] considered a homogeneous Markov chain representing the evolution of cache contents and derived the stationary fault probability for the FIFO cache, as well as for the LRU. The evaluation of fault probability based on King’s analysis, however, suffers from the computational complexity when the number of items and/or the capacity of cache are large. Dan and Towsley [5] then presented a computationally efficient approximation evaluating the stationary fault probability for both the FIFO and LRU caches. While their approximation reportedly agrees well with simulation results, the argument for derivation is rather informal. Also, Gelenbe [6] showed the identity of stationary fault probability for the FIFO cache with that for the random replacement (RR) cache, where an item is chosen uniformly at random in the cache and is replaced with the requested one if it is not in the cache. Since the stationary fault probabilities for the FIFO and RR are identical [6], we, in this paper, investigate the RR caching algorithm for the independent reference model, instead of the FIFO. We here study the fluid limit analysis of RR caching. As for the LRU, several works have considered the fluid limit analysis and presented some simple expressions evaluating the fault probability (see, e.g., Jelenković [7], and also Hirade and Osogami [8] for some complex caching algorithms, and Hattori and Hattori [9] for the related move-to-front list). It is, however, difficult to apply the techniques therein to the RR caching as well as to the FIFO, since these previous works built on such a special feature of LRU that an item is pushed out from the cache when the number of other distinct items requested at least once reaches the cache capacity before the same item is requested again. We thus associate the stochastic model of RR caching with a mean field interaction model studied by Benaïm and Le Boudec [10] (see also [11]) and apply the limit theorem for it. While the limit theorem for the mean field interaction model of [10] captures the transient behavior of the model in average, it does not yield satisfying results on the stationary behavior. For the stationary analysis, we then apply the recent results obtained by Le Boudec [12] exploiting the reversibility of the stochastic model under consideration. We can see that the fluid limit of stationary fault probability, which we obtain, is coincident with the approximated fault probability provided by [5], so that we can say that our fluid limit analysis gives a rigorous theoretical foundation to Dan–Towsley’s approximation. The rest of this paper is organized as follows. In the next section, we describe our stochastic model of a caching system and briefly review some related existing results in the works of [4], [6] and [5]. The main results are given in Section 3, where we first derive the fluid limit of empirical measure for the cache contents in the transient state and then obtain the corresponding fluid limit in the steady state. The fluid limits of fault probabilities are derived from those of the empirical measure. The proofs are provided in Section 4, where we apply the limit theorem for the mean field interaction model of [10] for the proof of transient result and apply the results obtained by [12] for the steady state. Finally, we make some concluding remarks in Section 5.

In this paper, we have studied the RR caching and have derived the fluid limit of transient behavior by applying the limit theorem for mean field interaction models of [10]. The fluid limit in the steady state has also been obtained by applying the results of [12]. The results in the steady state are available for the FIFO caching since these two caching algorithms have the same stationary fault probability. We have seen that the fluid limit of stationary fault probability is coincident with the approximation of that for the FIFO caching provided by [5]. Though we have considered the independent reference model, we may extend some results to a dependent reference model by associating it with the mean field interaction model with a resource (see [10] and [11] for details). To investigate caching algorithms that are more complex by the fluid limit approach, we may have to further develop the limit theory of mean field models with interactions.