Web Prefetching Between Low-Bandwidth Clients and Proxies: Potential and Performance

Li Fan, Quinn Jacobson, Pei Cao and Wei Lin.



The majority of the Internet population access the World Wide Web via dial-up modem connections. Studies have shown that the limited modem bandwidth is the main contributor to latency perceived by users. In this paper, we investigate one approach to reduce latency: prefetching between caching proxies and browsers. The approach relies on the proxy to predict which cached documents a user might reference next, and takes advantage of the idle time between user requests to push or pull the documents to the user. Using traces of modem Web accesses, we evaluate the potential of the technique at reducing client latency, examine the design of prediction algorithms, and investigate their performance varying the parameters and implementation concerns. Our results show that prefetching combined with large browser cache and delta-compression can reduce client latency up to 23.4\%. The reduction is achieved using the Prediction-by-Partial-Matching (PPM) algorithm, whose accuracy ranges from 40\% to 73\% depending on its parameters, and which generates 1\% to 15\% extra traffic on the modem links. A perfect predictor can increase the latency reduction to 28.5\%, whereas without prefetching, large browser cache and delta-compression can only reduce latency by 14.4\%. Depending on the desired properties of the algorithm, several configurations for PPM can be best choices. Among several attractive simplifications of the scheme, some do more harm than others; in particular, it is important for the predictor to observe all accesses made by users, including browser cache hits.

Here is the gzip-ed postscript version of the paper.

There will be a techreport version of the paper that includes more numbers and we will put it here when it is ready.