Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-05-29
2003-04-08
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S133000, C711S134000, C709S219000
Reexamination Certificate
active
06546473
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of computer systems. Specifically, the present invention relates to a method of prioritizing documents in a web cache for efficient replacement.
BACKGROUND OF THE INVENTION
A web cache is a computer system located at the client, at the server, or at the network that keeps copies of the most-recently requested web pages in memory or on disk in order to speed up retrieval. Document caching is used to improve web performance. If a user requests a page that has already been stored in the cache, it is retrieved locally rather than from the Internet, thus resulting in faster file retrieval. A web cache has a limited amount of memory in which to store web pages. As a result, documents in the web cache must be periodically replaced with more popular documents.
An efficient cache replacement policy keeps popular documents in the cache and replaces rarely used ones. Many replacement policies for web caches have been proposed and are currently in use. Some of them are quite simple and easy to implement, while others are heavily parameterized or have aspects that do not allow for an efficient implementation (thus they can exhibit good results that serve as theoretical bounds on the best practically achievable performance). Two essential features distinguish web caching from conventional caching in general computer systems:
The HTTP protocol supports whole file transfers, thus a web cache can satisfy a request only if the entire file is cached.
Documents stored in a web cache are of different sizes, while CPU and disk caches deal with uniform-size pages.
A key element to good web cache performance is an efficient cache replacement policy for determining which files should be removed from cache to store newly requested documents. Further improvements can be achieved when such a policy is combined with a decision about whether a document is worth caching at all.
One previously proposed cache replacement policy for web documents is the Least-Recently-Used (LRU) method. The LRU policy is based simply on a clocking function that determines the file in the web cache that is the least recently accessed file. This file is evicted from the web cache to make room for the new file.
Another previously proposed cache replacement policy for web documents is the Greedy-Dual-Size (GDS) method. The GDS policy incorporates document size, cost, and an elegant aging mechanism in the decision process, and exhibits better performance compared to the LRU policy. However, it does not account for the number of times the requested file has been accessed.
The GDS policy has been extended, taking into consideration the document frequency, resulting in the Greedy-Dual-Frequency (GDF) policy, which considers a document's frequency plus the aging mechanism, and the Greedy-Dual-Frequency-Size (GDFS) policy, which also considers a document's size.
The typical measure of web cache efficiency is the file hit ratio: the fraction of times (over all accesses) the file was found in the cache. Since files are of different size, a complementary metric is also important, the byte hit ratio: the fraction of “bytes” returned from the cache among all the bytes accessed. While the GDFS policy achieves the best file hit ratio, it yields a modest byte hit ratio. Alternatively, the GDF policy results in the best byte hit ratio at the price of a worse file hit ratio.
Accordingly, a need exists for a more efficient replacement policy for a web cache. A need exists for a web replacement policy that allows for the optimization of both the file hit ratio and the byte hit ratio. Specifically, a need exists for an efficient web cache replacement policy that allows to emphasize (or de-emphasize) either the size or frequency (or both) parameters.
SUMMARY OF THE INVENTION
A method for determining the priority of a file in a web cache for use in a web cache replacement policy is described. The present invention provides a more efficient replacement policy for a web cache. The present invention provides a web replacement policy that allows for the optimization of both the file hit ratio and the byte hit ratio. The present invention allows for either the size or frequency (or both) parameters to be emphasized or de-emphasized, producing a more efficient web cache policy.
The present invention incorporates the document size and the frequency of file access in determining which documents to keep in the cache and which documents to replace. The priority of a document is determined using a ratio of the frequency of access of the document raised to a first value to the size of the document raised to a second value, wherein the first value and the second value are rational numbers other than one. Setting the values of the first value or the second value as greater than one emphasizes the role of the associated parameter. Similarly, setting the values of the first value or the second value as less than one de-emphasizes the role of the associated parameter. In one embodiment, the first value is greater than one and the second value is less than one.
In another embodiment, the age of the document is also considered in determining the priority of a document. In the present embodiment, the ratio is added to a clock value, wherein the clock value is a running counter associated with the document starting at the time the document was first stored in the web cache. In one embodiment, the clock value can be set to any monotonically increasing function to accommodate different aging mechanisms.
In one embodiment, the priority is determined by adding the ratio, a clock value, and the frequency of access. In another embodiment, the priority is determined by adding the ratio, a clock value, and the frequency of access, wherein the frequency raised to a first value equals one.
The present invention is a generalized method for assigning priority values to documents stored in a web cache. The priority value is used to determine which document or documents are to be replaced when new documents are added to the web cache. The present invention allows for the balancing of the emphasis of the frequency of access or document size. The present invention also allows for the design of faster or slower aging mechanisms. The present invention operates to define the family of web replacement policies balancing the impact of size and frequency of access such that both parameters can be optimized.
These and other objects and advantages of the present invention will become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
REFERENCES:
patent: 6012126 (2000-01-01), Aggarwal et al.
patent: 6266742 (2001-07-01), Challenger et al.
patent: 6415368 (2002-07-01), Glance et al.
patent: 6425057 (2002-07-01), Cherkasova et al.
Cherkasova Ludmila
Ciardo Gianfranco
Hewlett--Packard Company
Moazzami Nasser
Yoo Do Hyun
LandOfFree
Method for cache replacement of web documents does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for cache replacement of web documents, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for cache replacement of web documents will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3055263