|
USENIX Technical Program - Abstract - Internet Technologies & Systems 99
Using Full Reference History for Efficient Document Replacement in Web Caches
Hyokyung Bahn, Seoul National University; Sam H. Noh, Hong-lk University; Kern Koh, Seoul National University; and Sang Lyul Min, Seoul National University
Abstract
With the increase in popularity
of the World Wide Web, the research community has recently seen a proliferation
of Web caching algorithms. This paper presents a new such algorithm, that is
efficient and robust, called Least Unified-Value (LUV). LUV evaluates a Web document
based on its cost normalized by the likelihood of it being re-referenced. This
results in a normalized assessment of the contribution to the value of a
document, leading to a fair replacement policy. LUV can conform to arbitrary
cost functions of Web documents, so it can optimize any particular performance
measure of interest, such as the hit rate, the byte hit rate, or the
delay-savings ratio. Unlike most existing algorithms, LUV exploits complete
reference history of documents, in terms of reference frequency and recency, to
estimate the likelihood of being re-referenced. Nevertheless, LUV allows for an
efficient implementation in both space and time complexities. The space needed to
maintain the reference history of a document is only a few bytes and furthermore,
the time complexity of the algorithm is O(log2n), where n is the
number of documents in the cache. Trace-driven simulations show that the LUV
algorithm outperforms existing algorithms for various performance measures for
a wide range of cache configurations.
- View the full text of this paper in
HTML form and
PDF form.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
- To become a USENIX Member, please see our Membership Information.
|
Need help? Use our Contacts page.
Technical Program