Online Paging and File Caching with Expiration Times

We consider a paging problem in which each page is assigned an
expiration time at the time it is brought into the cache. The
expiration time indicates the latest time that the fetched copy of the
page may be used. Requests that occur later than the expiration time
must be satisfied by bringing a new copy of the page into the cache.
The problem has applications in caching of documents on the World Wide
Web. We show that a natural extension of the well-studied Least
Recently Used (LRU) paging algorithm is strongly competitive for the
uniform retrieval cost, uniform size case. We then describe a similar
extension of a recently proposed algorithm for the case of arbitrary
retrieval costs and sizes, and prove that it is strongly competitive.
The results extend to the loose model of competitiveness as well.

By: Tracy Kimbrel

Published in: Theoretical Computer Science, volume 268, (no 1), pages 119-31 in 2001

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .