Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-08-27
2002-07-23
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C709S219000
Reexamination Certificate
active
06425057
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to retaining objects in cache and, more particularly, to methods and systems for implementing a protocol for replacing cached objects with recently received objects.
BACKGROUND ART
With the growth of the World Wide Web, an increasingly large fraction of available bandwidth on the Internet is used to transfer Web documents. Access to the Web documents is generally structured around the HyperText Transfer Protocol (HTTP), which is a request-and-response protocol. When a user at a client device, such as a personal computer, designates a particular Web page, at least one request is generated. The number of requests is dependent upon the sophistication of the designated Web page. Often, a Web page is formed of a number of files, such as text files, graphics files, audio files and video files. Each one of the files is referred to as an “object.” A multi-object page is aesthetically pleasing, but each object requires a separate request and a separate response. Therefore, each request-and-response round trip time plays a role in determining the total time a user must wait to view the complete designated Web page.
The total latency in downloading a Web page or other Internet document (e.g., a FTP file) depends upon a number of factors, including the transmission speeds of communication links between a client device and a server on which the file is stored, delays that are incurred at the server in accessing the document, and delays incurred at any-device located between the client device and the server. The intermediate devices may include proxies and routers. If there are a number of objects embedded within a Web page, the delays occur for each object.
Web proxies serve as intermediaries between browsers on a client side of an Internet connection and servers on the opposite side. An important benefit of a Web proxy is the ability of the proxy to cache objects. The caching operations of the Web proxy will be described with reference to FIG.
1
. When a client device
12
generates a request
14
for a particular object, the cache of a proxy
16
is searched to determine whether the object is stored at the proxy. If the object is not found in the cache, the request is directed to a server
18
via the Internet
20
. In
FIG. 1
, the requested object
10
is indicated in phantom. As an example, the object
10
may be a HTML file. A response
22
from the server is directed through the proxy
16
to the client device
12
. Preferably, the object
10
that is contained within the response
22
is cached at the proxy
16
. At a later time, either the same client device or a different client device
24
may generate a request
26
for the same object. The object
10
is in the cache of the proxy, allowing the object to be forwarded to the client device
24
directly from the proxy, as shown by response
28
. This eliminates delays encountered in communicating between the proxy
16
and the server
18
.
The first request
14
resulted in a “cache miss,” since the requested object
10
was not retained in cache of the proxy
16
. On the other hand, the second request
26
resulted in a “cache hit.” By storing copies of objects, the proxy
16
can reduce the number of requests that are directed to servers
18
, as well as the volume of traffic on Internet backbones as a result of transmitting the responses in the form of a number of packets that must be reassembled at the client device
12
.
Ideally, the cache at the proxy
16
can retain all of the objects that are transferred through the proxy. However, the typical storage capacity for the proxy is in the range of 256 megabytes to 1 terabyte, with most Web proxy capacity being at the lower half of the range. Therefore, it is important to form a replacement strategy for determining which objects are evicted from cache when a recently received object is to be cached within exhausted storage space. Two important metrics that are used to measure proxy cache performance are cache hit rate and byte hit rate. The cache hit rate is the percentage of all user requests
14
and
26
that are satisfied by the proxy
16
, rather than by access to the original server
18
. Byte hit rate is the percentage of all network traffic, measured in bytes, transferred directly from the proxy cache, instead of across the external network.
There are a number of replacement strategies that have been proposed by the scientific community with regard to Web proxy caching. Some of the strategies are relatively simple and easy to implement, while others rely heavily upon setting parameters and are difficult to implement. A well organized survey of currently known Web replacement strategies is provided by Pei Cao and Sandy Irani in an article entitled, “Cost-Aware WWW Proxy Caching Algorithms,”
Proceedings of USENIX Symposium on Internet Technologies and Systems
, Monterey, Calif., pages 193-206, December, 1997. The article describes ten previously known replacement algorithms.
According to the least-recently-used (LRU) algorithm, when an eviction is required in order to store a recently received object, the previously cached object that was requested least recently is evicted. This is a traditional strategy and operates well for CPU caches and virtual memory systems. However, it does not work as well for proxy caching, since time accesses for Web traffic often exhibit very different patterns. For example, some Web pages may be popular only during certain times of the day or certain days of the month.
A second known strategy is the least-frequently-used (LFU) algorithm that replaces the object which has been accessed the least number of times. This strategy attempts to keep more popular objects and replace rarely used objects. However, some objects can build a high frequency count over a short period of time and be rarely accessed after the subject matter is no longer “hot.” Such objects often remain within cache long after network performance is enhanced by retaining the documents in cache. The traditional LFU strategy does not provide any mechanism to remove such documents, leading to “cache pollution.” Typical examples are objects of a Web site dedicated to a one-time, high-profile event.
A third strategy is to evict the largest document stored in cache. This size strategy attempts to maximize the cache hit rate by evicting one large object, rather than a number of small objects. However, some of the small objects may never be accessed again. This third strategy does not provide any mechanism to evict such documents, leading to cache pollution.
A fourth strategy identified in the Cao and Irani article is referred to as an LRU-threshold strategy. This strategy is equivalent to the LRU policy, but it does not cache documents larger than a certain threshold size.
Another refinement of the LRU strategy is the log (size) +LRU strategy that replaces the document which has the largest log (size) and is the least recently used among the same log (size) documents. A hyper-G strategy is a refinement of the LFU strategy with last access time and size considerations. Yet another strategy is referred to as the Pitkow/Recker strategy that replaces the least recently used document, unless all of the documents were accessed on that particular day. In this case, the largest document is replaced. This strategy attempts to monitor the daily time access patterns specific to the Web documents. This replacement strategy has been proposed as one to run at the end of a day, in order to free space occupied by “old” least-recently accessed documents.
An eighth strategy is the lowest-latency-first policy that removes the document with the lowest download latency. The strategy is directed to minimizing average latency.
A ninth identified strategy is a hybrid policy that also targets reducing the average latency. For each object, a utility value of retaining the object in cache is computed. Objects with the smallest utility value are replaced. The utility value is designed to capture the utility of retaining a given object in the cache. The valu
Arlitt Martin F.
Cherkasova Ludmila
Friedrich Richard J.
Jin Tai
Courtenay III St. John
Hewlett--Packard Company
LandOfFree
Caching protocol method and system based on request... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Caching protocol method and system based on request..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching protocol method and system based on request... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905714