Most data accessed on the Internet today contain text and images. Hence, simple adaptations of the conventional memory caching algorithms are adequate for managing disk-based web caches. However, as streaming of audio and video data gain popularity, web caches will need to reserve cache bandwidth for each object. Given that disk caches are limited in both space and bandwidth, web caching algorithms will have to efficiently manage both these resources. We have developed a Resource-based Caching (RBC) algorithm for web caches that addresses this problem. The resource-based caching algorithm characterizes each object by its bandwidth and space requirements, and models the disk cache as a two-constraint knapsack. It: (1) selects the granularity of the entity to be cached that minimally uses the limited cache resource (i.e., bandwidth or space), and (2) replaces the cached entities based on their cache resource usage and caching gain. The RBC algorithm achieves higher hit ratios as compared to several existing algorithms for various workloads and cache configurations. We have implemented this algorithm in the Squid proxy cache, and have deployed it in our distributed cache prototype.

Representative Publications: