This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Mookerjee, V. S. Articles by Tan, Y. Search for Related Content

Analysis of a Least Recently Used Cache Management Policy for Web Browsers

University of Texas at Dallas, JO4.624, School of Management, Richardson, Texas 75083-0688
University of Washington, School of Business, Box 353200, Seattle, Washington 98195-3200
vijaym{at}utdallas.edu
ytan{at}u.washington.edu

Experience shows that document caching by a web browser is a cheap and effective way to improve the performance of the World Wide Web. This study analyzes a LRU (Least Recently Used) policy for cache management in a web browser. In this policy, the cache is filled with documents based upon a document's "age," defined as the time elapsed since the document was last accessed. The user's preference for a document is modeled as a general function that declines with the document's age. Two popular measures—the expected delay per document access, and the hit-ratio—are used to evaluate the LRU policy. Unlike many previous studies that evaluate caching policies using simulation methods, this study derives analytical expressions to evaluate performance. The study also presents an approximate, easy-to-compute method to evaluate performance. Numerical tests show this approximation to be extremely accurate. A variety of other numerical results are presented that help describe the behavior ofthe LRU policy under different situations (e.g., when the documents need to be updated periodically). We also compare the LRU policy with other caching policies (both static and dynamic) for small problems. Our comparison suggests that finding a good caching policy that is conscious of document size and delay may be difficult.

Subject classifications: Information systems: analysis and design; Computers/computer science: system design and operation; Probability: stochastic model applications.
History: Received January 1999; revision received August 1999; accepted August 2000.