Competitive Analysis of the LRFU Paging Algorithm

   Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU is k +

A theoretical comparison of LRU and LRU-K

The paging algorithm Least Recently Used Second Last Request (LRU-2) was proposed for use in database disk buffering and shown experimentally to perform better than Least Recently Used (LRU). We compare LRU-2 and LRU theoretically, using both the standard competitive analysis and the newer relative worst order analysis. The competitive ratio for LRU-2 is shown to be 2k for cache size k, which is worse than LRU’s competitive ratio of k. However, using relative worst order analysis, we show that LRU-2 and LRU are comparable in LRU-2’s favor, giving a theoretical justification for the experimental results. Many of our results for LRU-2 also apply to its generalization, Least Recently Used Kth Last Request.     

A Unified Analysis of Paging and Caching

Paging (caching) is the problem of managing a two-level memory hierarchy in order to minimize the time required to process a sequence of memory accesses. In order to measure this quantity, which we refer to as the total memory access time, we define the system parameter miss penalty to represent the extra time required to access slow memory. We also introduce the system parameter page size. In the context of paging, miss penalty is quite large, so most previous studies of on-line paging have implicitly set miss penalty =∞ in order to simplify the model. We show that this seemingly insignificant simplification substantially alters the precision of derived results. For example, previous studies have essentially ignored page size. Consequently, we reintroduce the miss penalty and page size parameters to the paging problem and present a more accurate analysis of on-line paging (and caching). We validate using this more accurate model by deriving intuitively appealing results for the paging problem which cannot be derived using the simplified model. First, we present a natural, quantifiable definition of the amount of locality of reference in any access sequence. We also point out that the amount of locality of reference in an access sequence should depend on page size among other factors. We then show that deterministic and randomized marking algorithms such as the popular least recently used (LRU) algorithm achieve constant competitive ratios when processing typical access sequences which exhibit significant locality of reference; this represents the first competitive analysis result which (partially) explains why LRU performs as well as it is observed to in practice. Next, we show that finite lookahead can be used to obtain algorithms with improved competitive ratios. In particular, we prove that modified marking algorithms with sufficient lookahead achieve competitive ratios of 2. This is in stark contrast to the simplified model where lookahead cannot be used to obtain algorithms with improved competitive ratios. We conclude by using competitive analysis to evaluate the benefits of increasing associativity in caches. We accomplish this by specifying an algorithm and varying the system configuration rather than the usual process of specifying the system configuration and varying the algorithm. Received August 7, 1995; revised May 7, 1996, and August 6, 1996.     

The relative worst-order ratio applied to paging

The relative worst-order ratio, a relatively new measure for the quality of on-line algorithms, is extended and applied to the paging problem. We obtain results significantly different from those obtained with the competitive ratio. First, we devise a new deterministic paging algorithm, Retrospective-LRU, and show that, according to the relative worst-order ratio and in contrast with the competitive ratio, it performs better than LRU. Our experimental results, though not conclusive, are slightly positive and leave it possible that Retrospective-LRU or similar algorithms may be worth considering in practice. Furthermore, the relative worst-order ratio (and practice) indicates that LRU is better than the marking algorithm FWF, though all deterministic marking algorithms have the same competitive ratio. Look-ahead is also shown to be a significant advantage with this new measure, whereas the competitive ratio does not reflect that look-ahead can be helpful. Finally, with the relative worst-order ratio, as with the competitive ratio, no deterministic marking algorithm can be significantly better than LRU, but the randomized algorithm MARK is better than LRU.     

On Generalized Connection Caching

Cohen et al. [5] recently initiated the theoretical study of connection caching in the world-wide web. They extensively studied uniform connection caching, where the establishment cost is uniform for all connections [5], [6]. They showed that ordinary paging algorithms can be used to derive algorithms for uniform connection caching and analyzed various algorithms such as Belady's rule, LRU and Marking strategies. In particular, in [5] Cohen et al. showed that LRU yields a (2k-1) -competitive algorithm, where k is the size of the largest cache in the network. In [6] they investigated Marking algorithms with different types of communication among nodes and presented deterministic k -competitive algorithms. In this paper we study generalized connection caching , also introduced in [5], where connections can incur varying establishment costs. This model is reasonable because the cost of establishing a connection depends, for instance, on the distance of the nodes to be connected and on the congestion in the network. Algorithms for ordinary weighted caching can be used to derive algorithms for generalized connection caching. We present tight or nearly tight analyses on the performance achieved by the currently known weighted caching algorithms when applied in generalized connection caching. In particular we give online algorithms that achieve an optimal competitive ratio of k . Our deterministic algorithm uses extra communication while maintaining open connections. We develop a generalized algorithm that trades communication for performance and achieves a competitive ratio of (1+ε)k , for any 0<ε≤ 1 , using at most

On the relative dominance of paging algorithms

In this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. Using this technique, we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.     

A Comparative Study of Set Associative Memory Mapping Algorithms and Their Use for Cache and Main Memory

Set associative page mapping algorithms have become widespread for the operation of cache memories for reasons of cost and efficiency. We show how to calculate analytically the effectiveness of standard bit-selection set associative page mapping or random mapping relative to fully associative (unconstrained mapping) paging. For two miss ratio models, Saltzer's linear model and a mixed geometric model, we are able to obtain simple, closed-form expressions for the relative LRU fault rates. We also experiment with two (infeasible to implement) dynamic mapping algorithms, in which pages are assigned to sets either in an LRU or FIFO manner at fault times, and find that they often yield significantly lower miss ratios than static algorithms such as bit selection. Trace driven simulations are used to generate experimental results and to verify the accuracy of our calculations. We suggest that as electronically accessed third-level memories composed of electron-beam tubes, magnetic bubbles, or charge-coupled devices become available, algorithms currently used only for cache paging will be applied to main memory, for the same reasons of efficiency, implementation ease, and cost.     

On-Line File Caching

Abstract. Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost , maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k . This problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h ≤ k . For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k , the retrieval cost is either insignificant or at most a constant (independent of k ) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.     

Paging with Request Sets

A generalized paging problem is considered. Each request is expressed as a set of u pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the u pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case u=1 is simply the classical paging problem, which is known to be polynomially solvable. We show that for any u>1 the offline problem is NP-hard and hard to approximate if the cache size k is part of the input, but solvable in polynomial time for constant values of k. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of k, u. We study in more detail the cases where u and k are small. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for u=2. A preliminary version of this paper appeared in Proc. Scandinavian Workshop on Algorithm Theory (SWAT 2006), pp. 124–135, 2006. Research of R. van Stee supported by Alexander von Humboldt Foundation.     

On the Influence of Lookahead in Competitive Paging Algorithms

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is n-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal. Received April 8, 1994; revised May 15, 1995.     

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

Abstract. We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered in [4] and [5] is (k+1)/(k-h+1) competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP-complete ``offline' problem.     

Caching for Web Searching

Abstract. We study Web Caching when the input sequence is a depth first search traversal of some tree. There are at least two good motivations for investigating tree traversal as a search technique on the WWW: First, empirical studies of people browsing and searching the WWW have shown that user access patterns commonly are nearly depth first traversals of some tree. Secondly (as we will show in this paper), the problem of visiting all the pages on some WWW site using anchor clicks (clicks on links) and back button clicks—by far the two most common user actions—reduces to the problem of how best to cache a tree traversal sequence (up to constant factors). We show that for tree traversal sequences the optimal offline strategy can be computed efficiently. In the bit model, where the access time of a page is proportional to its size, we show that the online algorithm LRU is (1 + 1/ɛ) -competitive against an adversary with unbounded cache as long as LRU has a cache of size at least (1+ ɛ) times the size of the largest item in the input sequence. In the general model, where pages have arbitrary access times and sizes, we show that in order to be constant competitive, any online algorithm needs a cache large enough to store Ω(log n) pages; here n is the number of distinct pages in the input sequence. We provide a matching upper bound by showing that the online algorithm Landlord is constant competitive against an adversary with an unbounded cache if Landlord has a cache large enough to store the Ω(log n) largest pages. This is further theoretical evidence that Landlord is the ``right' algorithm for Web Caching.     

More on randomized on-line algorithms for caching

We address the tradeoff between the competitive ratio and the resources used by randomized on-line algorithms for caching. Two algorithms reported in the literature that achieve the optimal ratio H_k require a lot of memory and perform extensive computation at each step. On the other hand, a very simple algorithm called RMARK has competitive ratio 2H_k−1, within a factor of 2 of the optimum. A natural question that arises here is whether there is a tradeoff between simplicity and the competitive ratio. In particular, is it possible to achieve a competitive ratio better than 2H_k−1 with a simple algorithm like RMARK?

We first consider marking algorithms that are natural generalizations of RMARK, and we prove that, for any >0, there is no randomized marking algorithm for caching with competitive ratio (2−)H_k. Thus RMARK is essentially optimal among marking algorithms.

Another model of simple caching algorithms is that of trackless algorithms. These are algorithms that do not store any information about items that are not in the cache. It is known that, for k=2, there is no randomized trackless algorithm for caching with ratio better than . The trivial upper bound is 2, achieved even by deterministic algorithms LRU and FIFO. We reduce this gap by giving a trackless randomized algorithm with competitive ratio .     

Online Hierarchical Cooperative Caching

We address a hierarchical generalization of the well-known disk paging problem. In the hierarchical cooperative caching problem, a set of n machines residing in an ultrametric space cooperate with one another to satisfy a sequence of read requests to a collection of read-only files. A seminal result in the area of competitive analysis states that the "least recently used" (LRU) paging algorithm is constant-competitive if it is given a constant-factor blowup in capacity over the offline algorithm. Does such a constant-competitive deterministic algorithm, with a constant-factor blowup in the machine capacities, exist for the hierarchical cooperative caching problem? In this paper we present a deterministic hierarchical generalization of LRU that is constant-competitive when the capacity blowup is linear in d, the depth of the cache hierarchy. Furthermore, we exhibit an infinite family of depth-d hierarchies such that any randomized hierarchical cooperative caching algorithm with capacity blowup b has competitive ratio Ω(log(d/b)) against an oblivious adversary. Thus, our upper and lower bounds imply a tight bound of Θ(d) on the capacity blowup required to achieve constant competitiveness.     

Competitive Optimal On-Line Leasing

Consider an on-line player who needs some equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P . The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first k-1 times and then buying, where k = P/c . This strategy pays at most 2-1/k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We find that the optimal deterministic competitive ratio is 1 + (1+i)(1-1/k)(1 - k(i/1+i)) , a decreasing function of the interest i (for all reasonable values of i ). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive ratio of 2 - ( (k/(k-1)) ^γ - 2 )/( (k/(k-1)) ^γ -1 ) where γ = ln ( 1 - k(1 - 1/(1+i)) ) / ln(1/(1+i)) . Here again, this competitive ratio strictly decreases with i . We also study the leasing problem against a distributional adversary called ``Nature.' This adversary chooses the probability distribution of the number of leasing periods and announces this distribution before the on-line player chooses a strategy. Although at the outset this adversary appears to be weaker than the oblivious adversary, it is shown that the optimal competitive ratio against Nature equals the optimal ratio against the oblivious adversary. Received October 8, 1997; revised February 8, 1998.     

A strongly competitive randomized paging algorithm

Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH _k of optimum. (H _k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.Partial support for D. D. Sleator was provided by DARPA, ARPA Order 4976, Amendment 20, monitored by the Air Force Avionics Laboratory under Contract F33615-87-C-1499, and by the National Science Foundation under Grant CCR-8658139.     

Page Replacement with Multi-Size Pages and Applications to Web Caching

Abstract. We consider the paging problem where the pages have varying size. This problem has applications to page replacement policies for caches containing World Wide Web documents. We consider two models for the cost of an algorithm on a request sequence. In the first (the FAULT model) the goal is to minimize the number of page faults. In the second (the BIT model) the goal is to minimize the total number of bits that have to be read into the cache. We show offline algorithms for both cost models that obtain approximation factors of O(log k) , where k is the ratio of the size of the cache to the size of the smallest page. We show randomized online algorithms for both cost models that are O(log ² k) -competitive. In addition, if the input sequence is generated by a known distribution, we show an algorithm for the FAULT model whose expected cost is within a factor of O(log k) of any other online algorithm.     

Bounded size dictionary compression: SC-completeness and NC algorithms

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(log^kn), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(log^kn) space (that is, SC^k). We also introduce a variation of this heuristic that turns out to be an SC^k-complete problem (the original heuristic belongs to SC^k+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given.     

证书系统缓存替换算法的研究

Cache技术是一种能够减少时延，节省带宽和降低服务器负载的有效方法。文章分析了现有证书服务器中Cache算法和证书系统的结构特性；指出证书缓存的简单替换算法：FIFO(first in first out)和LRU(Least Recently Used)，无法提供较高的Cache命中率。文中提出了一种智能预留控制缓存替换算法，理论分析和仿真数据表明该算法能大大减少访问证书的时间，改善证书管理效率，并有效提高缓存的命中率。     

基于谱聚类的Web多级缓存替换策略

服务器缓存性能的核心是缓存替换策略,缓存替换策略直接影响缓存的命中率, Web缓存可以解决网络拥塞和用户访问延迟问题,提高服务器的性能.传统缓存替换算法的命中率往往不高,为此文中提出了一种基于谱聚类的多级缓存替换策略.该策略利用循环滑动窗口机制提取日志文件的多项时序特征和访问属性,通过谱聚类对过滤后的数据集进行聚类分析从而得到访问预测结果.多级缓存替换策略综合考虑了缓存对象的局部频率、全局频率以及资源大小能更好地对低价值资源进行剔除,同时对高价值资源进行保留.通过与传统替换算法LRU、LFU、RC、FIFO进行实验对比,实验结果表明本文将谱聚类和多级缓存替换策略进行结合有效地提高了缓存请求命中率和字节命中率.