A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> World-Wide Web proxy servers that cache documents can potentially reduce three quantities: the number of requests that reach popular servers, the volume of network traffic resulting from document requests, and the latency that an end-user experiences in retrieving a document. This paper examines the first two using the measures of cache hit rate and weighted hit rate (or fraction of client-requested bytes returned by the proxy). A client request for an uncached document may cause the removal of one or more cached documents. Variable document sizes and types allow a rich variety of policies to select a document for removal, in contrast to policies for CPU caches or demand paging, that manage homogeneous objects. We present a taxonomy of removal policies. Through trace-driven simulation, we determine the maximum possible hit rate and weighted hit rate that a cache could ever achieve, and the removal policy that maximizes hit rate and weighted hit rate. The experiments use five traces of 37 to 185 days of client URL requests. Surprisingly, the criteria used by several proxy-server removal policies (LRU, Hyper-G, and a proposal by Pitkow and Recker) are among the worst performing criteria in our simulation; instead, replacing documents based on size maximizes hit rate in each of the studied workloads. <s> BIB001 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> As the number of World-Wide Web users grow, so does the number of connections made to servers. This increases both network load and server load. Caching can reduce both loads by migrating copies of server files closer to the clients that use those files. Caching can either be done at a client or in the network (by a proxy server or gateway). We assess the potential of proxy servers to cache documents retrieved with the HTTP protocol. We monitored traffic corresponding to three types of educational workloads over a one semester period, and used this as input to a cache simulation. Our main findings are (1) that with our workloads a proxy has a 30-50% maximum possible hit rate no matter how it is designed; (2) that when the cache is full and a document is replaced, least recently used (LRU) is a poor policy, but simple variations can dramatically improve hit rate and reduce cache size; (3) that a proxy server really functions as a second level cache, and its hit rate may tend to decline with time after initial loading given a more or less constant set of users; and (4) that certain tuning configuration parameters for a cache may have little benefit. <s> BIB002 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> Abstract The quality of the service provided by the World Wide Web, namely convenient access to a tremendous amount of information in remote locations, depends in an important way on the time required to retrieve this information. This time in turn depends on a number of parameters, in particular the load at the server and in the network. Overloads are avoided by carefully dimensioning the server (so that it has enough resources such as CPU power and disk space to handle expected requests) and the network (so that it has enough resources such as bandwidth and buffers to transport requests and replies), and by using mechanisms such as caching that minimize the resource requirements of user requests. In this paper, we consider performance issues related to dimensioning and caching. Our contribution is twofold. Regarding dimensioning, we advocate the use of time series analysis techniques for Web traffic modeling and forecasting. We show using experimental data that quantities of interest such as the number of Web requests handled by a server, or the amount of data retrieved per hour by a server, can be accurately modeled with time series such as seasonal ARIMA models. We then use these models to make medium-term predictions of client requests characteristics (number of such requests and size of document retrieved), which in turn can be used as a basis for dimensioning decisions. Regarding caching, we advocate the use of novel cache replacement algorithms that explicitly take document size and network load into account so as to minimize the retrieval time perceived by clients. <s> BIB003 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> Abstract Do users wait less if proxy caches incorporate estimates of the current network conditions into document replacement algorithms? To answer this, we explore two new caching algorithms: (1) keep in the cache documents that take the longest to retrieve; and (2) use a hybrid of several factors, trying to keep in the cache documents from servers that take a long time to connect to, that must be loaded over the slowest Internet links, that have been referenced the most frequently, and that are small. The algorithms work by estimating the Web page download delays or proxy-to-Web server bandwidth using recent page fetches. The new algorithms are compared to the best three existing policies—LRU, LFU, and SIZE—using three measures-user response time and ability to minimize Web server loads and network bandwidth consumed—on workloads from Virginia Tech and Boston University. <s> BIB004 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> Caching at proxy servers plays an important role in reducing the latency of the user response, the network delays and the load on Web servers. The cache performance depends critically on the design of the cache replacement algorithm. Unfortunately, most cache replacement algorithms ignore the Web's scale. In this paper we argue for the design of delay-conscious cache replacement algorithms which explicitly consider the Web's scale by preferentially caching documents which require a long time to fetch to the cache. We present a new, delay-conscious cache replacement algorithm LNC-R-W3 which maximizes a performance metric called delay-savings-ratio. Subsequently, we test the performance of LNC-R-W3 experimentally and compare it with the performance of other existing cache replacement algorithms, namely LRU and LRU-MIN. <s> BIB005 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> To reduce user-perceived latency in retrieving documents on the world wide web, a commonly used technique is caching both at the client's browser and more gainfully (due to sharing) at a proxy. The effectiveness of Web caching hinges on the replacement policy that determines the relative value of caching different objects. An important component of such policy is to predict next-request times. We propose a caching policy utilizing statistics on resource inter-request times. Such statistics can be collected either locally or at the server, and piggybacked to the proxy. Using various Web server logs, we compared existing cache replacement policies with our server-assisted schemes. The experiments show that utilizing the server knowledge of access patterns can greatly improve the effectiveness of proxy caches. Our experimental evaluation and proposed policies use a price function framework. The price function values the utility of a unit of cache storage as a function of time. Instead of the usual tradeoffs of profit (combined value of cache hits) and cache size we measure tradeoffs of profit and caching cost (average allocated cache portion). The price-function framework allows us to evaluate and compare different replacement policies by using server logs, without having to construct a full workload model for each client's cache. <s> BIB006 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> With the recent explosion in usage of the World Wide Web, the problem of caching Web objects has gained considerable importance. Caching on the Web differs from traditional caching in several ways. The nonhomogeneity of the object sizes is probably the most important such difference. In this paper, we give an overview of caching policies designed specifically for Web objects and provide a new algorithm of our own. This new algorithm can be regarded as a generalization of the standard LRU algorithm. We examine the performance of this and other Web caching algorithms via event- and trace-driven simulation. <s> BIB007 </s> A survey of web caching schemes for the Internet <s> Traditional replacement policies and its direct extensions: <s> In a large-scale information system such as a digital library or the World Wide Web, a set of distributed caches can improve their effectiveness by coordinating their data placement decisions. Using simulation, we examine three practical cooperative placement algorithms, including one that is provably close to optimal, and we compare these algorithms to the optimal placement algorithm and several cooperative and non-cooperative replacement algorithms. We draw five conclusions from these experiments: (1) cooperative placement can significantly improve performance compared to local replacement algorithms, particularly when the size of individual caches is limited compared to the universe of objects; (2) although the Amortized Placement algorithm is only guaranteed to be within 14 times the optimal, in practice it seems to provide an excellent approximation of the optimal; (3) in a cooperative caching scenario, the GreedyDual local replacement algorithm performs much better than the other local replacement algorithms; (4) our Hierarchical GreedyDual replacement algorithm yields further improvements over the GreedyDual algorithm, especially when there are idle caches in the system; and (5) a key challenge to coordinated placement algorithms is generating good predictions of access patterns based on past accesses. <s> BIB008
• Least Recently Used (LRU) evicts the object which was requested the least recently. • Lease Frequently used (LFU) evicts the object which is accessed least frequently. • Pitkow/Recker BIB001 evicts objects in LRU order, except if all objects are accessed within the same day, in which case the largest one is removed. 2. Key-based replacement policies: (i.e. the replacement policies in this category evict objects based upon a primary key. Ties are broken based on secondary key, tertiary key, etc.) • Size BIB001 evicts the largest object. • LRU-MIN BIB002 biased in favor of smaller objects. If there are any objects in the cache which have size being at least S, LRU-MIN evicts the least recently used such object from the cache. If there are no objects with size being at least S, then LRU-MIN starts evicting objects in LRU order of size being at least S/2. That is, the object who has the largest log(size) and is the least recently used object among all objects with the same log(size) will be evicted first. • LRU-Threshold BIB002 is the same as LRU, but objects larger than a certain threshold size are never cached. • Hyper-G BIB001 is a refinement of LFU, break ties using the recency of last use and size. • Lowest Latency First BIB004 minimizes average latency by evicting the document with the lowest download latency first. 3. Cost-based replacement policies: (i.e. the replacement policies in this category employ a potential cost function derived from different factors such as time since last access, entry time of the object in the cache, transfer time cost, object expiration time and so on.) • GreedyDual-Size (GD-Size) associates a cost with each object and evicts object with the lowest cost/size. • Hybrid BIB004 associates a utility function with each object and evicts the one has the least utility to reduce the total latency. • Lowest Relative Value [54] evicts the object with the lowest utility value. • LeastNormalized CostReplacement (LCN-R) BIB005 employs a rational function of the access frequency, the transfer time cost and the size. • Bolot/Hoschka BIB003 employs a weighted rational function of transfer time cost, the size, and the time last access. • Size-Adjusted LRU (SLRU) BIB007 orders the object by ratio of cost to size and choose objects with the best costto-size ratio. • Server-assisted scheme BIB006 models the value of caching an object in terms of its fetching cost, size, next request time, and cache prices during the time period between requests.It evicts the object of the least value. • Hierarchical GreedyDual (Hierarchical GD) BIB008 does object placement and replacement cooperatively in a hierarchy. To sum up, a great deal of effort has been made to maximize the hit rate. However, the performance of replacement policies depends highly on traffic characteristics of WWW accesses. No known policy can outperform others for all Web access patterns.