URL forwarding and compression in adaptive Web caching

Abstract

Web caching is generally acknowledged as an important service for alleviating focused overloads when certain WWW servers' contents suddenly become popular. Cooperative caching systems are more effective than independent caches due to the larger collective backing store that cooperation creates. One such system currently being developed at UCLA, adaptive Web caching (AWC), uses an application-level forwarding table to locate the nearest copy of a requested URL's contents. This paper describes one specific design in AWC, a simple URL table compression algorithm allowing efficient content information-sharing among neighboring caches. The compression algorithm is based on a hierarchical URL decomposition to aggregate URL sharing common prefixes and an incremental hashing function to minimize collisions between prefixes. The algorithm's collision rate is derived analytically and verified by five sets of Web trace data. The results demonstrate that the collision rate is bounded and has little impact on page fetching latency. Finally, this compression method is compared to the summary cache method.