Analysis of speculative prefetching

ABSTRACT

Prefetching is a potential method to reduce waiting time for retrieving data over wireless network connections that commonly occur in mobile scenarios. These connections typically exhibit low bandwidth as well as high latency. This article analyzes fundamental principles in speculative prefetching. Based on a simplified system model, the influence of parameters and strategies on prefetching performance is investigated, both analytically and in simulation. The reduction of the mean waiting time is used as performance metric. An example is given that makes use of the Zipf distribution to demonstrate the influence of the documents' probability distribution and its parameters. A low-complexity algorithm that performs optimally under the given assumptions is presented.

REFERENCES

• 1: Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. Web caching and Zipf-like distributions: Evidence and implications, Proc. of the IEEE Infocom '99, New York, NY, March 1999.
• 2: Mark Crovella and Paul Barford. The network effects of prefetching, Proc. of the IEEE Infocom '98, San Francisco, CA, March/April 1998.
• 3: Brian D. Davison, A Web Caching Primer, IEEE Internet Computing, v.5 n.4, p.38-45, July 2001 [doi>10.1109/4236.939449]
• 4: Li Fan , Pei Cao , Wei Lin , Quinn Jacobson, Web prefetching between low-bandwidth clients and proxies: potential and performance, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.178-187, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Thomas M. Kroeger and Darrell D. E. Long. Exploring the bounds of web latency reduction from caching and prefetching, Proceedings of the USENIX Symposium on Internet Technologies and Systems, Monterey, California, December 1997.
• 6: Nor Jaidi Tuah , Mohan Kumar , Svetha Venkatesh, A Performance Model of Speculative Prefetching in Distributed Information Systems, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.75-80, April 12-16, 1999
• 7: Arun Venkataramani , Praveen Yalagandula , Ravindranath Kokku , Sadia Sharif , Mike Dahlin, The Potential Costs and Benefits of Long-term Prefetching for ContentDistribution, University of Texas at Austin, Austin, TX, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Design, Performance