Performance modelling of speculative prefetching for compound requests in low bandwidth networks

ABSTRACT

To improve the accuracy of access prediction, a prefetcher for web browsing should recognize the fact that a web page is a compound. By this term we mean that a user request for a single web page may require the retrieval of several multimedia items. Our prediction algorithm builds an access graph that captures the dynamics of web navigation rather than merely attaching probabilities to hypertext structure. When it comes to making prefetch decisions, most previous studies in speculative prefetching resort to simple heuristics, such as prefetching an item with access probabilities larger than a manually tuned threshold. The paper takes a different approach. Specifically, it models the performance of the prefetcher and develops a prefetch policy based on a theoretical analysis of the model. In the analysis, we derive a formula for the expected improvement in access time when prefetch is performed in anticipation for a compound request. We then develop an algorithm that integrates prefetch and cache replacement decisions so as to maximize this improvement. We present experimental results to demonstrate the effectiveness of compound-based prefetching in low bandwidth networks.

REFERENCES

• 1: Andonov, R., V. Poirriez, and S. Rajopadhye, "Unbounded knapsack problem: Dynamic programming revisited," Technical Report PI-1152, IRISA, France, (October 1997).
• 2: Bolot, J-C., and P. Hoschka, "Performance engineering of the world wide web," WWW Journal, 1(3):185-195 (1996).
• 3: Pei Cao, Application-controlled file caching and prefetching, Princeton University, Princeton, NJ, 1996
• 4: Carlos Cunha , Azer Bestavros , Mark Crovella, Characteristics of WWW Client-based Traces, Boston University, Boston, MA, 1995
• 5: Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
• 6: Griffioen, J. and R. "Appleton Reducing file system latency using a predictive approach," in Proc 1994 Summer USENIX Conference, pages 197-208, (June 1994).
• 7: Griffioen,J. and Randy Appleton, "Performance measurement of automatic prefetching,"In Proc of the ISCA International Conference on Parallel and Distributed Computing Systems, (September 1995).
• 8: Griffioen, J. and Randy Appleton,"The design, implementation and evaluation of a predictive caching file system," Technical Report CS-264-96, Department of Computer Science, University of Kentucky, (June 1996).
• 9: Jiang, Z. and L. Kleinrock, "An adaptive network prefetch scheme," IEEE Journal on Selected Areas in Communications, 16(3):358-368, (April 1998).
• 10: Lei, H. and D. Duchamp, "An analytical approach to file prefetching," In Proc USENIX Annual Technical Conf, (January 1997).
• 11: Markatos, E.P. and C.E. Chronaki, "A top- 10 approach to prefetching on the web," Technical Report TR 173, ICS-FORTH, Greece, (August 1996).
• 12: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 13: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]
• 14: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 15: Peter Scheuermann , Junho Shim , Radek Vingralek, WATCHMAN: A Data Warehouse Intelligent Cache Manager, Proceedings of the 22th International Conference on Very Large Data Bases, p.51-62, September 03-06, 1996
• 16: Peter Scheuermann , Junho Shim , Radek Vingralek, A case for delay-conscious caching of Web documents, Computer Networks and ISDN Systems, v.29 n.8-13, p.997-1005, Sep. 1997
• 17: Carl Downing Tait, A file system for mobile computing, Columbia University, New York, NY, 1993
• 18: N. J. Tuah , M. Kumar , S. Venkatesh, Investigation of a prefetch model for low bandwidth networks, Proceedings of the 1st ACM international workshop on Wireless mobile multimedia, p.38-47, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288338.288368]
• 19: 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
• 20: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
• 21: Roland P. Wooster , Marc Abrams, Proxy caching that estimates page load delays, Computer Networks and ISDN Systems, v.29 n.8-13, p.977-986, Sep. 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance, Theory

Keywords:
Web, caching, compound requests, speculative prefetching