## 1 Introduction: Basic Caching Methods and Their Evaluations  
Caching strategies are essential for the performance of local caches in CPU, GPU and database systems [1] as well as for content delivery on the Internet [2, 3]. A set of basic caching strategies, such as first-in-first-out (FIFO), least recently/frequently used (LRU/LFU) and clock-based caching [1, 4, 5, 6, 7, 8, 9], were studied in early caching approaches almost 50 years ago, and they are still preferably applied today. Other caching methods that include detailed properties, caching costs and values per data object can optimize the efficiency on the basis of score rankings [10, 11] or machine-learning approaches [12, 13]. However, FIFO and LRU are still attractive caching principles because of their simple and fast data management [3, 14, 15, 16]. We compare analysis and approximation methods for the FIFO and LRU hit ratio evaluation, where RANDOM and clock-based caches are included, because their performance is partly equivalent to FIFO [6]. Moreover, simulation is a usual performance evaluation approach for caches. Simulations are flexibly applied for many caching methods and variants [2, 11, 17, 18, 19], but they are subject to random deviations, which require long runs for accurate results in narrow confidence intervals. Exact analytic hit ratio solutions were derived long ago by [PERSON] [8] and [PERSON] [6] for the independent reference model. In the past decade, the state of the art has advanced towards solutions for multisegment/multilevel caches [20], and for LRU caches with data objects of different sizes, including the cache startup or filling phase [21, 22]. However, those exact solutions are tractable only for small caches. In addition to exact analysis and simulation, approximation formulas form a third pillar for a simpler evaluation of basic caching methods, as proposed by [PERSON] [23] and [PERSON] et al. [24] for LRU as well as by [PERSON] and [PERSON] [25] for FIFO. Recent research has approved asymptotical exactness of both LRU variants for large caches [26; 27; 28; 29]. The motivation and purpose of this work is to present a complete picture of the currently available analysis and approximation results for FIFO and LRU. Our focus is mainly on FIFO results [14; 16], which are only sparsely addressed in the literature, in contrast to LRU [9; 18; 21; 22]. The product form solution of the FIFO hit ratio for independent requests [6; 8] is scalable for large caches and applicable to clock-based caching (CpR: clock per request), in contrast to LRU analysis results. We show that the FIFO approximation [25] has similar properties, as confirmed for LRU [26; 27; 28; 29] for data of unit size, and we extend the approaches for data of variable sizes as required for web content delivery. An overview of the similarities and differences in the results for FIFO and LRU is provided in Table 1. The scope of the analysis methods is clarified in the main part, and the accuracy of the approximations is studied in an extensive quantitative investigation. On the basis of detailed insights and a comparison of the alternative cache performance evaluation methods, we finally recommend the most appropriate evaluation options for the considered caching use cases. As new contributions of this work,  
* product form solutions are extended to clock-based methods and combinations of those methods, with FIFO and RANDOM for single and multilevel caches,
* the scope of analytical solutions is clarified regarding scalable computation as well as the solutions' applicability for data of different sizes, and
* quantitative evaluations of the accuracy of approximations identify the worst cases and error bound extensions for varying data sizes in caches. We start with exact analysis results for the FIFO, CpR and RANDOM hit ratio and assess their scalability, in Section 2. The precision of approximations for FIFO and LRU caching strategies is evaluated in Sections 3 and 4. Extensions to multisegment caches are addressed in Section 5.