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.     

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.     

Competitive snoopy caching

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. Each cache monitors the activity on the bus and in its own processor and decides which blocks of data to keep and which to discard. For several of the proposed architectures for snoopy caching systems, we present new on-line algorithms to be used by the caches to decide which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.A preliminary and condensed version of this paper appeared in theProceedings of the 27th Annual Symposium on the Foundations of Computer Science, IEEE, 1986.This author received support from an IBM doctoral fellowship, and did part of this work while a research student associate at IBM Almaden Research Center.     

New Results on Web Caching with Request Reordering

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models.     

Competitive snoopy caching

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. Each cache monitors the activity on the bus and in its own processor and decides which blocks of data to keep and which to discard. For several of the proposed architectures for snoopy caching systems, we present new on-line algorithms to be used by the caches to decide which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.     

Performance analysis of a caching algorithm for a catch-up television service

The catch-up TV (CUTV) service allows users to watch video content that was previously broadcast live on TV channels and later placed on an on-line video store. Upon a request from a user to watch a recently missed episode of his/her favourite TV series, the content is streamed from the video server to the customer’s receiver device. This requires that an individual flow is set up for the duration of the video, and since it is hard to impossible to employ multicast streaming for this purpose (as users seldomly issue a request for the same episode at the same time), these flows are unicast. In this paper, we demonstrate that with the growing popularity of the CUTV service, the number of simultaneously running unicast flows on the aggregation parts of the network threaten to lead to an unwieldy increase in required bandwidth. Anticipating this problem and trying to alleviate it, the network operators deploy caches in strategic places in the network. We investigate the performance of such a caching strategy and the impact of its size and the cache update logic. We first analyse and model the evolution of video popularity over time based on traces we collected during 10 months. Through simulations we compare the performance of the traditional least-recently used and least-frequently used caching algorithms to our own algorithm. We also compare their performance with a “perfect” caching algorithm, which knows and hence does not have to estimate the video request rates. In the experimental data, we see that the video parameters from the popularity evolution law can be clustered. Therefore, we investigate theoretical models that can capture these clusters and we study the impact of clustering on the caching performance. Finally, some considerations on the optimal cache placement are presented.     

Exploiting client caches to build large Web caches

New demands brought by the continuing growth of the Internet will be met in part by more effective and comprehensive use of caching. This paper proposes to exploit client browser caches in the context of cooperative proxy caching by constructing the client caches within each organization (e.g., corporate networks) as a peer-to-peer (P2P) client cache. Via trace-driven simulations we evaluate the potential performance benefit of cooperative proxy caching with/without exploiting client caches. We show that exploiting client caches in cooperative proxy caching can significantly improve performance, particularly when the size of individual proxy caches is limited compared to the universe of Web objects. We further devise a cooperative hierarchical greedy-dual replacement algorithm (Hier-GD), which not only provides some cache coordination but also utilizes client caches. Through Hier-GD, we explore the design issues of how to exploit client caches in cooperative proxy caching to build large Web caches. We show that Hier-GD is technically practical and can potentially improve the performance of cooperative proxy caching by utilizing client caches.

Randomized Weighted Caching with Two Page Weights

Abstract. We consider a special case of the weighted caching problem where the weight of every page is either 1 or some fixed number M > 1 . We present a randomized algorithm which achieves a competitive ratio which is O( log k) where k is the number of pages which can fit in the cache.     

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.     

一种基于近似LRU算法的高缓方案

提出了一个用于扩充高缓块管理的近似LRU算法。利用该算法，设计了一个可过滤LRU数据块的扩充高缓方案——LRU块过滤高缓(LBF高缓)。仿真结果显示，LBF高缓的性能优于类似结构的扩充高缓(如牺牲高缓和辅助高缓)，与具有2倍容量的直接映像高缓相比性能有所提高。     

Design and analysis of a variable bit rate caching algorithm for continuous media data

In this paper, the problem of caching continuous media data in a (main) memory and disk caching system is addressed. Caching schemes can significantly reduce the load on the network as well as on the servers, also the retrieval of documents from the cache requires short response time. In interval-level caching algorithms, an interval of data between two adjacent streams is the basic caching entity. In this paper, we design a novel algorithm, referred to as variable bit rate caching (VBRC) algorithm, which belongs to the interval-level caching algorithms. The proposed VBRC algorithm can be used in the system for memory caching or disk caching. VBRC can handle variable retrieval bandwidth as well as constant retrieval bandwidth . In designing the VBRC algorithm, we propose the strategies of reducing the number of switching operation, which will probably cause discontinuity of retrieving data. Also, we propose a just-in-time scheme for resource allocation in our VBRC algorithm and show that the caching performance in comparison with the reservation scheme adopted in the resource-based caching (RBC) algorithm is significantly improved. Our simulation study compares the recent and most popular generalized interval caching, RBC, and VBRC, on several influencing factors such as cache space size, cache I/O bandwidth, request arrival rate, and percentage of requests for large documents, with respect to the byte hit ratio and the number of switching operations. The simulation result confirms our analysis.

Network-aware partial caching for Internet streaming media

The delivery of multimedia over the Internet is affected by adverse network conditions such as high packet loss rate and long delay. This paper aims at mitigating such effects by leveraging client-side caching proxies. We present a novel cache architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. This architecture allows partial caching of media objects and joint delivery from caches and origin servers. Most importantly, the caching algorithms are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit rate requirements, and the available bandwidth between clients and servers. Using Internet bandwidth models derived from proxy cache logs and measured over real Internet paths, we have conducted extensive simulations to evaluate the performance of various cache management algorithms. Our experiments demonstrate that network-aware caching algorithms can significantly reduce startup delay and improve stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.Shudong Jin: Corespondence to This research was supported in part by NSF (awards ANI-9986397, ANI-0095988, ANI-0205294 and EJA-0202067) and by IBM. Part of this work was done while the first author was at IBM Research in 2001.     

Web cache management based on the expected cost of web objects

With the recent explosion in usage of the World Wide Web, Web caching has become increasingly important. However, due to the non-uniform cost/size property of data objects in this environment, design of an efficient caching algorithm becomes an even more difficult problem compared to the traditional caching problems. In this paper, we propose the Least Expected Cost (LEC) replacement algorithm for Web caches that provides a simple and robust framework for the estimation of reference probability and fair evaluation of non-uniform Web objects. LEC evaluates a Web object based on its cost per unit size multiplied by the estimated reference probability of the object. This results in a normalized assessment of the contribution to the cost-savings ratio, leading to a fair replacement algorithm. We show that this normalization method finds optimal solution under some assumptions. Trace-driven simulations with actual Web cache logs show that LEC offers the performance of caches more than twice its size compared with other algorithms we considered. Nevertheless, it is simple, having no parameters to tune. We also show how the algorithm can be effectively implemented as a Web cache replacement module.     

嵌入式浏览器缓存策略的设计与实现

给出了一种嵌入式浏览器缓存的实现策略,将网络数据进行分类,通过使用内存缓存技术,合理地缓冲网络数据,同时根据网页的结构和访问信息,使用一种简单可行的缓存淘汰策略,充分地利用缓存资源,使系统具有了较好的性能。     

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 .     

A phase adaptive cache hierarchy for SMT processors

Resizable caches can trade-off capacity for access speed to dynamically match the needs of the workload. In single-threaded cores, resizable caches have demonstrated their ability to improve processor performance by adapting to the phases of the running application. In Simultaneous Multi-Threaded (SMT) cores, the caching needs can vary greatly across the number of threads and their characteristics, thus, offering even more opportunities to dynamically adjust cache resources to the workload.In this paper, we demonstrate that the preferred control methodology for data cache reconfiguring in a SMT core changes as the number of running threads increases. In workloads with one or two threads, the resizable cache control algorithm should optimize for cache miss behavior because misses typically form the critical path. In contrast, with several independent threads running, we show that optimizing for cache hit behavior has more impact, since large SMT workloads have other threads to run during a cache miss. Moreover, we demonstrate that these seemingly diametrically opposed policies are closely related mathematically; the former minimizes the arithmetic mean cache access time (which we will call AMAT), while the latter minimizes its harmonic mean. We introduce an algorithm (HAMAT) that smoothly and naturally adjusts between the two strategies with the degree of multi-threading.We extend a previously proposed Globally Asynchronous, Locally Synchronous (GALS) processor core with SMT support and dynamically resizable caches. We show that the HAMAT algorithm significantly outperforms the AMAT algorithm on four-thread workloads while matching its performance on one and two thread workloads. Moreover, HAMAT achieves overall performance improvements of 18.7%, 10.1%, and 14.2% on one, two, and four thread workloads, respectively, over the best fixed-configuration cache design.     

Scalable Federation of Web Cache Servers

Web caches are traditionally organised in a simple tree like hierarchy. In this paper, a new architecture is proposed, where federations of caches are distributed globally, caching data partially. The advantages of the proposed system are that contention on global caches is reduced, while at the same time improving the scalability of the system since extra cache resources can be added on the fly. Among other topics discussed in this papers, is the scalability of the proposed system, the algorithms used to control the federation of Web caches and the approach used to identify the potential Web cache partners. In order to obtain a successful collaborative Web caching system, the formation of federations must be controlled by an algorithm that takes the dynamics of the Internet traffic into consideration. We use the history of Web cache access in order to determine how federations should be formed. Initial performance results of a simulation of a number of nodes are promising.     

Real-time integrated prefetching and caching

The high latencies for access to background memory like hard disks or flash memory can be reduced by caching or hidden by prefetching. We consider the problem of scheduling the resulting I/Os when the available fast cache memory is limited and when we have real-time constraints where for each requested data block we are given a time interval during which this block needs to be in main memory. We give a near linear time algorithm for this problem which produces a feasible schedule whenever one exists. Another algorithm additionally minimizes I/Os and still runs in polynomial-time. For the online variant of the problem, we give a competitive algorithm that uses lookahead and augmented disk speed. We show a tight relationship between the amount of lookahead and the speed required to get a competitive algorithm.     

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

Value complete,column complete,predicate complete

Caching is a proven remedy to enhance scalability and availability of software systems as well as to reduce latency of user requests. In contrast to Web caching where single Web objects are accessed and kept ready somewhere in caches in the user-to-server path, database caching uses full-fledged database management systems as caches, close to application servers at the edge of the Web, to adaptively maintain sets of records from a remote database and to evaluate queries on them. We analyze a new class of approaches to database caching where the extensions of query predicates that are to be evaluated are constructed by constraints in the cache. Starting from the key concept of value completeness, we explore the application of cache constraints and their implications on query evaluation correctness and on controllable cache loading called cache safeness. Furthermore, we identify simple rules for the design of cache groups and their optimization before discussing the use of single cache groups and cache group federations. Finally, we argue that predicate completeness can be used to develop new variants of constraint-based database caching.