An efficient web cache replacement policy

Several replacement policies for web caches have been proposed and studied extensively in the literature. Different replacement policies perform better in terms of (i) the number of objects found in the cache (cache hit), (ii) the network traffic avoided by fetching the referenced object from the cache, or (iii) the savings in response time. In this paper, we propose a simple and efficient replacement policy (hereafter known as SE) which improves all three performance measures. Trace-driven simulations were done to evaluate the performance of SE. We compare SE with two widely used and efficient replacement policies, namely Least Recently Used (LRU) and Least Unified Value (LUV) algorithms. Our results show that SE performs at least as well as, if not better than, both these replacement policies. Unlike various other replacement policies proposed in literature, our SE policy does not require parameter tuning or a-priori trace analysis and has an efficient and simple implementation that can be incorporated in any existing proxy server or web server with ease.

CACHE REPLACEMENT STRATEGIES FOR MOBILE DATA CACHING.

Data caching is an important technique in mobile computing environments for improving data availability and access latencies particularly because these computing environments are characterized by narrow bandwidth wireless links and frequent disconnections. Cache replacement policy plays a vital role to improve the performance in a cached mobile environment, since the amount of data stored in a client cache is small. In this paper we reviewed some of the well known cache replacement policies proposed for mobile data caches. We made a comparison between these policies after classifying them based on the criteria used for evicting documents. In addition, this paper suggests some alternative techniques for cache replacement

A key based cache replacement policy for cooperative caching in mobile ad hoc networks

Cooperative caching in mobile ad hoc networks aims at improving the efficiency of information access by reducing access latency and bandwidth usage. Cache replacement policy plays a vital role in improving the performance of a cache in a mobile node since it has limited memory. In this paper we propose a new key based cache replacement policy called E-LRU for cooperative caching in ad hoc networks. The proposed scheme for replacement considers the time interval between the recent references, size and consistency as key factors for replacement. Simulation study shows that the proposed replacement policy can significantly improve the cache performance in terms of cache hit ratio and query delay

A flexible receiver-driven cache replacement scheme for continuous media objects in best-effort networks

In this paper, we investigate the potential of caching to improve quality of reception (QoR) in the context of continuous media applications over best-effort networks. Specifically, we investigate the influence of parameters such as loss rate, jitter, delay and area in determining a proxy's cache contents. We propose the use of a flexible cost function in caching algorithms and develop a framework for benchmarking continuous media caching algorithms. The cost function incorporates parameters in which, an administrator and or a client can tune to influence a proxy's cache. Traditional caching systems typically base decisions around static schemes that do not take into account the interest of their receiver pool. Based on the flexible cost function, an improvised Greedy Dual (GD) algorithm called GD-multi has been developed for layered multiresolution multimedia streams. The effectiveness of the proposed scheme is evaluated by simulation-based performance studies. Performance of several caching schemes are evaluated and compared with those of the proposed scheme. Our empirical results indicate GD-multi performs well despite employing a generalized caching policy.

Study and evaluation of several cache replacement policies on a commercial MIPS Processor

Actualmente, el rendimiento de los computadores es un tema candente. Existen importantes limitaciones físicas y tecnológicas en los semiconductores de hoy en día, por lo que se realiza un gran esfuerzo desde las universidades y la industria para garantizar la continuidad de la ley de Moore. Este proyecto está centrado en el estudio de la cache y la jerarquía de memoria, uno de los grandes temas en la materia. Para ello, hemos escogido MIPSfpga, una plataforma hardware abierta de Imagination Technologies, lo que nos ha permitido implementar y testear diferentes políticas de reemplazamiento como prueba de concepto, demostrando, además, las bondades de la plataforma.

A Novel Cache Resolution Technique For Cooperative Caching In Wireless Mobile Networks

Cooperative caching is used in mobile ad hoc networks to reduce the latency perceived by the mobile clients while retrieving data and to reduce the traffic load in the network. Caching also increases the availability of data due to server disconnections. The implementation of a cooperative caching technique essentially involves four major design considerations (i) cache placement and resolution, which decides where to place and how to locate the cached data (ii) Cache admission control which decides the data to be cached (iii) Cache replacement which makes the replacement decision when the cache is full and (iv) consistency maintenance, i.e. maintaining consistency between the data in server and cache. In this paper we propose an effective cache resolution technique, which reduces the number of messages flooded in to the network to find the requested data. The experimental results gives a promising result based on the metrics of studies.

Energy Efficient Cache Discovery in Wireless Mobile Ad oc Networks

Data caching is an attractive solution for reducing bandwidth demands and network latency in mobile ad hoc networks. Deploying caches in mobile nodes can reduce the overall traf c considerably. Cache hits eliminate the need to contact the data source frequently, which avoids additional network overhead. In this paper we propose a data discovery and cache management policy for cooperative caching, which reduces the power usage, caching overhead and delay by reducing the number of control messages flooded into the network .A cache discovery process based on position cordinates of neighboring nodes is developed for this .The stimulstion results gives a promising result based on the metrics of the studies.

File replacement algorithm for storage resource managers in data grids

The main problem in data grids is how to provide good and timely access to huge data given the limited number and size of storage devices and high latency of the interconnection network. One approach to address this problem is to cache the files locally such that remote access overheads are avoided. Caching requires a cache-replacement algorithm, which is the focus of this paper. Specifically, we propose a new replacement policy and compare it with an existing policy using simulations. The results of the simulation show that the proposed policy performs better than the baseline policy.

AMC: an adaptive multi-level cache algorithm in hybrid storage systems

Hybrid storage systems that consist of flash-based solid state drives (SSDs) and traditional disks are now widely used. In hybrid storage systems, there exists a two-level cache hierarchy that regard dynamic random access memory (DRAM) as the first level cache and SSD as the second level cache for disk storage. However, this two-level cache hierarchy typically uses independent cache replacement policies for each level, which makes cache resource management inefficient and reduces system performance. In this paper, we propose a novel adaptive multi-level cache (AMC) replacement algorithm in hybrid storage systems. The AMC algorithm adaptively adjusts cache blocks between DRAM and SSD cache levels using an integrated solution. AMC uses combined selective promote and demote operations to dynamically determine the level in which the blocks are to be cached. In this manner, the AMC algorithm achieves multi-level cache exclusiveness and makes cache resource management more efficient. By using real-life storage traces, our evaluation shows the proposed algorithm improves hybrid multi-level cache performance and also increases the SSD lifetime compared with traditional multi-level cache replacement algorithms.

On erasure coding for distributed storage and streaming communications

The work presented in this thesis revolves around erasure correction coding, as applied to distributed data storage and real-time streaming communications.

First, we examine the problem of allocating a given storage budget over a set of nodes for maximum reliability. The objective is to find an allocation of the budget that maximizes the probability of successful recovery by a data collector accessing a random subset of the nodes. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models, and determine the optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) for a variety of cases. Although the optimal allocation can have nonintuitive structure and can be difficult to find in general, our results suggest that, as a simple heuristic, reliable storage can be achieved by spreading the budget maximally over all nodes when the budget is large, and spreading it minimally over a few nodes when it is small. Coding would therefore be beneficial in the former case, while uncoded replication would suffice in the latter case.

Second, we study how distributed storage allocations affect the recovery delay in a mobile setting. Specifically, two recovery delay optimization problems are considered for a network of mobile storage nodes: the maximization of the probability of successful recovery by a given deadline, and the minimization of the expected recovery delay. We show that the first problem is closely related to the earlier allocation problem, and solve the second problem completely for the case of symmetric allocations. It turns out that the optimal allocations for the two problems can be quite different. In a simulation study, we evaluated the performance of a simple data dissemination and storage protocol for mobile delay-tolerant networks, and observed that the choice of allocation can have a significant impact on the recovery delay under a variety of scenarios.

Third, we consider a real-time streaming system where messages created at regular time intervals at a source are encoded for transmission to a receiver over a packet erasure link; the receiver must subsequently decode each message within a given delay from its creation time. For erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts whose maximum length is sufficiently short or long, we show that a time-invariant intrasession code asymptotically achieves the maximum message size among all codes that allow decoding under all admissible erasure patterns. For the bursty erasure model, we also show that diagonally interleaved codes derived from specific systematic block codes are asymptotically optimal over all codes in certain cases. We also study an i.i.d. erasure model in which each transmitted packet is erased independently with the same probability; the objective is to maximize the decoding probability for a given message size. We derive an upper bound on the decoding probability for any time-invariant code, and show that the gap between this bound and the performance of a family of time-invariant intrasession codes is small when the message size and packet erasure probability are small. In a simulation study, these codes performed well against a family of random time-invariant convolutional codes under a number of scenarios.

Finally, we consider the joint problems of routing and caching for named data networking. We propose a backpressure-based policy that employs virtual interest packets to make routing and caching decisions. In a packet-level simulation, the proposed policy outperformed a basic protocol that combines shortest-path routing with least-recently-used (LRU) cache replacement.

基于序列模式的Servlet容器缓存替换

Servlet缓存能够有效地提高Servlet容器的吞吐量,缩短用户请求的响应时间.然而,Servlet缓存的性能受到缓存替换算法的影响.Servlet容器中的Servlet对应着一定的业务功能,挖掘Servlet之间的业务关联来指导缓存替换算法的设计可以提高Servlet缓存的命中率,进而提高Servlet容器的性能.然而,目前常见的LRU(least recently used),LFU(least frequently used),GDSF(greedy dual size frequency)等缓存替换算法均没有考虑上述问题.将Servlet对应的业务关联定义为Servlet容器序列模式,并提出k步可缓存转移概率图的概念加以表示,给出了序列模式发现算法KCTPG_Discovery.最后,基于Servlet容器序列模式设计了缓存替换算法KP-LRU(k-steps prediction least recently used)和KP-GDSF(k-steps prediction least frequently used).实验结果表明,KP-LRU与KP-GDSF算法比对应的LRU算法和GDSF算法具有更高的缓存命中率,有效地提高了Servlet容器的性能.

On the Intrinsic Locality Properties of Web Reference Streams

There has been considerable work done in the study of Web reference streams: sequences of requests for Web objects. In particular, many studies have looked at the locality properties of such streams, because of the impact of locality on the design and performance of caching and prefetching systems. However, a general framework for understanding why reference streams exhibit given locality properties has not yet emerged. In this work we take a first step in this direction, based on viewing the Web as a set of reference streams that are transformed by Web components (clients, servers, and intermediaries). We propose a graph-based framework for describing this collection of streams and components. We identify three basic stream transformations that occur at nodes of the graph: aggregation, disaggregation and filtering, and we show how these transformations can be used to abstract the effects of different Web components on their associated reference streams. This view allows a structured approach to the analysis of why reference streams show given properties at different points in the Web. Applying this approach to the study of locality requires good metrics for locality. These metrics must meet three criteria: 1) they must accurately capture temporal locality; 2) they must be independent of trace artifacts such as trace length; and 3) they must not involve manual procedures or model-based assumptions. We describe two metrics meeting these criteria that each capture a different kind of temporal locality in reference streams. The popularity component of temporal locality is captured by entropy, while the correlation component is captured by interreference coefficient of variation. We argue that these metrics are more natural and more useful than previously proposed metrics for temporal locality. We use this framework to analyze a diverse set of Web reference traces. We find that this framework can shed light on how and why locality properties vary across different locations in the Web topology. For example, we find that filtering and aggregation have opposing effects on the popularity component of the temporal locality, which helps to explain why multilevel caching can be effective in the Web. Furthermore, we find that all transformations tend to diminish the correlation component of temporal locality, which has implications for the utility of different cache replacement policies at different points in the Web.

Popularity-Aware GreedyDual-Size Web Proxy Caching Algorithms

Web caching aims to reduce network traffic, server load, and user-perceived retrieval delays by replicating "popular" content on proxy caches that are strategically placed within the network. While key to effective cache utilization, popularity information (e.g. relative access frequencies of objects requested through a proxy) is seldom incorporated directly in cache replacement algorithms. Rather, other properties of the request stream (e.g. temporal locality and content size), which are easier to capture in an on-line fashion, are used to indirectly infer popularity information, and hence drive cache replacement policies. Recent studies suggest that the correlation between these secondary properties and popularity is weakening due in part to the prevalence of efficient client and proxy caches (which tend to mask these correlations). This trend points to the need for proxy cache replacement algorithms that directly capture and use popularity information. In this paper, we (1) present an on-line algorithm that effectively captures and maintains an accurate popularity profile of Web objects requested through a caching proxy, (2) propose a novel cache replacement policy that uses such information to generalize the well-known GreedyDual-Size algorithm, and (3) show the superiority of our proposed algorithm by comparing it to a host of recently-proposed and widely-used algorithms using extensive trace-driven simulations and a variety of performance metrics.

Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications

Temporal locality of reference in Web request streams emerges from two distinct phenomena: the popularity of Web objects and the {\em temporal correlation} of requests. Capturing these two elements of temporal locality is important because it enables cache replacement policies to adjust how they capitalize on temporal locality based on the relative prevalence of these phenomena. In this paper, we show that temporal locality metrics proposed in the literature are unable to delineate between these two sources of temporal locality. In particular, we show that the commonly-used distribution of reference interarrival times is predominantly determined by the power law governing the popularity of documents in a request stream. To capture (and more importantly quantify) both sources of temporal locality in a request stream, we propose a new and robust metric that enables accurate delineation between locality due to popularity and that due to temporal correlation. Using this metric, we characterize the locality of reference in a number of representative proxy cache traces. Our findings show that there are measurable differences between the degrees (and sources) of temporal locality across these traces, and that these differences are effectively captured using our proposed metric. We illustrate the significance of our findings by summarizing the performance of a novel Web cache replacement policy---called GreedyDual*---which exploits both long-term popularity and short-term temporal correlation in an adaptive fashion. Our trace-driven simulation experiments (which are detailed in an accompanying Technical Report) show the superior performance of GreedyDual* when compared to other Web cache replacement policies.

GreedyDual* Web Caching Algorithm: Exploiting the Two Sources of Temporal Locality in Web Request Streams

The relative importance of long-term popularity and short-term temporal correlation of references for Web cache replacement policies has not been studied thoroughly. This is partially due to the lack of accurate characterization of temporal locality that enables the identification of the relative strengths of these two sources of temporal locality in a reference stream. In [21], we have proposed such a metric and have shown that Web reference streams differ significantly in the prevalence of these two sources of temporal locality. These finding underscore the importance of a Web caching strategy that can adapt in a dynamic fashion to the prevalence of these two sources of temporal locality. In this paper, we propose a novel cache replacement algorithm, GreedyDual*, which is a generalization of GreedyDual-Size. GreedyDual* uses the metrics proposed in [21] to adjust the relative worth of long-term popularity versus short-term temporal correlation of references. Our trace-driven simulation experiments show the superior performance of GreedyDual* when compared to other Web cache replacement policies proposed in the literature.