Cache-Based Compaction: A New Technique for Optimizing Web Transfer

Despite the announcements of many new technologies (e.g., cable modem, ADSL), the speed of the last hop will remain a bottleneck for some time to come. This is especially true for the emerging area of wireless access to the Internet. In this paper, we propose and study a new technique, which we call cache-based compaction for reducing the latency of Web browsing over a slow link. Our compaction technique trades computation for bandwidth. The key observation is that an object can be coded in a highly compact form for transfer if similar objects that have been transferred earlier can be used as references. The contributions of this paper are: (1) an efficient selection algorithm for selecting similar objects as references, and (2) an encoding/decoding algorithm that reduces the size of a Web object by exploiting its similarities with the reference objects. We verify the efficacy of our proposal through detailed experimental evaluations. Our compaction technique significantly generalizes previous work on optimizing Web transfer using compression or differencing, and provides a systematic foundation that ties together caching, compression and prefetching.