The authors investigate the effects of caching when dealing with both access frequency and expiration times, using the common least-recently used algorithm as a starting point. They present and analyze three different classes of algorithms for dealing with the problem. There exist deterministic marking algorithms that are competitive relative to the size of the cache. They also discuss randomized marking algorithms and the optimal offline algorithm.