Introduction
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.
 |
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.
0 comments: