A survey of web caching schemes for the Internet <s> Cache coherence mechanisms <s> Abstract We present a piggyback server invalidation (PSI) mechanism for maintaining stronger cache coherency in Web proxy caches while reducing overall costs. The basic idea is for servers to piggyback on a reply to a proxy client, the list of resources that have changed since the last access by the client. The proxy client invalidates cached entries on the list and can extend the lifetime of entries not on the list. This continues our prior work on piggyback cache validation (PCV) where we focused on piggybacking validation requests from the proxy cache to the server. Trace-driven simulation of PSI on two large, independent proxy log data sets, augmented with data from several server logs, shows PSI provides close to strong cache coherency while reducing the request traffic compared to existing cache coherency techniques. The best overall performance is obtained when the PSI and PCV techniques are combined. Compared to the best TTL-based policy, this hybrid policy reduces the average cost (considering response latency, request messages and bandwidth) by 7–9%, reduces the staleness ratio by 82–86%, yielding a staleness ratio of 0.001. © 1998 Published by Elsevier Science B.V. All rights reserved. <s> BIB001 </s> A survey of web caching schemes for the Internet <s> Cache coherence mechanisms <s> The rapid growth of the World Wide Web has caused serious performance degradation on the Internet. This paper offers an end-to-end approach to improving Web performance by collectively examining the Web components --- clients, proxies, servers, and the network. Our goal is to reduce user-perceived latency and the number of TCP connections, improve cache coherency and cache replacement, and enable prefetching of resources that are likely to be accessed in the near future. In our scheme, server response messages include piggybacked information customized to the requesting proxy. Our enhancement to the existing request-response protocol does not require per-proxy state at a server, and a very small amount of transient per-server state at the proxy, and can be implemented without changes to HTTP 1.1. The server groups related resources into volumes (based on access patterns and the file system's directory structure) and applies a proxy-generated filter (indicating the type of information of interest to the proxy) to tailor the piggyback information. We present efficient data structures for constructing server volumes and applying proxy filters, and a transparent way to perform volume maintenance and piggyback generation at a router along the path between the proxy and the server. We demonstrate the effectiveness of our end-to-end approach by evaluating various volume construction and filtering techniques across a collection of large client and server logs. <s> BIB002 </s> A survey of web caching schemes for the Internet <s> Cache coherence mechanisms <s> This work studies the interaction of Web proxy cache coherency and replacement policies using trace-driven simulations. We specifically examine the relative importance of each type of policy in affecting the overall costs, the potential of incorporating coherency issues in cache replacement and the inclusion of additional factors such as frequency of resource use in replacement and coherency policies. The results show that the cache replacement policy in use is the primary cost determinant for relatively small caches, while the cache coherency policy is the determinant for larger caches. Incorporating cache coherency issues in cache replacement policies yields little improvement in overall performance. The use of access frequency in cache replacement, along with temporal locality and size information, results in a simple and better performing policy than found in previously published work. Combining this new replacement policy with the best piggyback-based cache coherency policy results in a 4.5% decrease in costs and 89% reduction in staleness ratio when compared to policy combinations in current use. Preliminary work indicates that cache replacement and coherency policies continue to affect costs in the presence of HTTP protocol enhancements such as persistent connections. <s> BIB003
(b) Piggyback Invalidation. Krishnamurthy Three invalidation mechanisms are proposed. The Pig: gyback Cache Validation (PCV)  capitalizes on requests sent from the proxy cache to the server to improve coherency. In the simplest case, whenever a proxy cache has a reason to communicate with a server it piggybacks a list of cached, but potentially stale, resources from that server for validation. The basic idea of the Piggyback Server Invalidation (PSI) mechanism BIB001 is for servers to piggyback on a reply to a proxy, the list of resources that have changed since the last access by this proxy. The proxy invalidates cached entries on the list and can extend the lifetime of entries not on the list. They also proposed a hybrid approach which combines the PSI and the PCV techniques to achieve the best overall performance BIB003 . The choice of the mechanism depends on the time since the proxy last requested invalidation for the volume BIB002 . If the time is small, then the PSI mechanism is used, while for longer gaps the PCV mechanism is used to explicitly validate cache contents. The rationale is that for short gaps, the number of invalidations sent with PSI is relatively small, but as the time grows longer the overhead for sending invalidation will be larger than the overhead for requesting validations.