Web Caching - Computer Engineering


The World Wide Web can be considered as a large distributed information system that provides access to shared data objects. As one of the most popular applications currently running on the Internet, The World Wide Web is of an exponential growth in size, which results in network congestion and server overloading. Web caching has been recognized as one of the effective schemes to alleviate the service bottleneck and reduce the network traffic, thereby minimize the user access latency.

Proxy Caching

Proxy servers are generally used to allow access to the Internet from users within a firewall. For security reasons, companies run a special type of HTTP servers called "proxy" on their firewall machines. A Proxy server typically processes requests from within a firewall by forwarding them to the remote servers, intercepting the responses, and sending the replies back to the clients. Since the same proxy servers are typically shared by all clients inside of the firewall, naturally this leads to the question of the effectiveness of using these proxies to cache documents.
Web Caching Seminar Report
Clients within the same firewall usually belong to the same organization and likely share common interests. They would probably access the same set of documents and each client tends to browse back and forth within a short period of time. Therefore on the proxy server a previously requested and cached document would likely result in future hits. Web caching at proxy server can not only save network bandwidth but also lower access latency for the clients.

Cost-Based Replacement Policies

Greedy Dual Size (GD-Size): It associates a cost with each object and evicts objects with least cost/size. This is a generalization of the LRU algorithm to the case where each object has a different fetch cost. The motivation behind the GD-Size scheme is that objects with large fetch costs should stay in the cache for longer time. The algorithm maintains a value for each object that is currently stored in the cache. When an object is fetched into the cache, its value is set to its fetch cost.

When a cache miss occurs, the object with the minimum value is evicted from the cache, and the values of all other objects in the cache are reduced by this minimum value. And if an object in the cache is accessed, then its value is restored to its fetch cost. A further implementation optimization is to note that it is only the relative value that matters in this algorithm. So, instead of deleting a fixed quantity from the value of each cached entry, the fixed quantity could be added to the value of the new object, and the effect would remain the same.

Hierarchical Greedy Dual (Hierarchical GD): This algorithm does object placement and replacement cooperatively in a hierarchy. Cooperative placement helps to utilize a nearby idle cache and the hit rates in the cache hierarchy are increased by placement of unique objects. It is the same as GD-size with the added advantage of cooperative caching. In this scheme, when an object is evicted from one of the child clusters, it is sent to its parent cluster. The parent first checks whether it has another copy of the object among its caches. If not, it picks the minimum valued object among all its cached objects. Out of the two objects, it retains the one that was used more recently. It propagates the other object recursively to its parent.

Between Browser Clients And Proxies

                        Prefetching can also be done between browser clients and proxies. One approach is to predict which cached documents a user might reference next (based on PPM) and take the advantage of idle time between user requests to push the documents to the users.
                        The first two approaches run the risk of increasing wide area network traffic, while the last one only affects the traffic over the modems or the LANs. All of these approaches attempt to prefetch either documents that are considered as popular at servers or documents that are predicted to be accessed by user in the near future based on the access pattern.

Strong Cache Consistency

a)        Client validation: This approach is also called polling-every-time. The proxy treats cached resources as potentially out-of-date on each access and sends an If-Modified-Since header with each access of the resources. This approach can lead to many 304 responses (HTTP response code for "Not Modified") by server if the resource does not actually change.

b)        Server invalidation: Upon detecting a resource change, the server sends invalidation messages to all clients that have recently accessed and potentially cached the resource. This approach requires a server to keep track of lists of clients to use for invalidating cached copies of changed resources and can become unwieldy for a server when the number of clients is large. In addition, the lists themselves can become out-of-date causing the server to send invalidation messages to clients who are no longer caching the resource.