Efficient replacement of nonuniform objects in Web caches

Cache performance depends heavily on replacement algorithms, which dynamically select a suitable subset of objects for caching in a finite space. Developing such algorithms for wide-area distributed environments is challenging because, unlike traditional paging systems, retrieval costs and object sizes are not necessarily uniform. In a uniform caching environment, a replacement algorithm generally seeks to reduce cache misses, usually by replacing an object with the least likelihood of re-reference. In contrast, reducing total cost incurred due to cache misses is more important in nonuniform caching environments. The authors present the least-unified value algorithm, which performs better than existing algorithms for replacing nonuniform data objects in wide-area distributed environments.