| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Objective-Optimal Algorithms for Long-Term Web Prefetching
January 2006 (vol. 55 no. 1)
pp. 2-17
Web prefetching is based on Web caching and attempts to reduce user-perceived latency. Unlike on-demand caching, Web prefetching fetches objects and stores them in advance, hoping that the prefetched objects are likely to be accessed in the near future and such accesses would be satisfied from the caches rather than by retrieving the objects from the Web server. This paper reviews the popular prefetching algorithms based on Popularity, Good Fetch, APL characteristic, and Lifetime, and then makes the following contributions: 1) The paper proposes a family of linear-time prefetching algorithms, Objective-Greedy prefetching, wherein each algorithm greedily prefetches those Web objects that most significantly improve the performance as per the targeted metric. 2) The Hit rate-Greedy and Bandwidth-Greedy algorithms are shown to be optimal for their respective objective metrics. A linear-time optimal prefetching algorithm that maximizes the H/B metric as the performance measure is proposed. 3) The paper shows the results of a performance analysis via simulations, comparing the proposed algorithms with the existing algorithms in terms of the respective objectives—the hit rate, bandwidth, and the H/B metrics. The proposed prefetching algorithms are seen to provide better objective-based performance than any existing algorithms. Further, H/B-Greedy performs almost as well as H/B-Optimal.
[1] 2 A. Bestavros, C.R. Cunha, and M.E. Crovella, “Characteristics of WWW Client-Based Traces,” technical report, Boston Univ., July 1995.[2] L. Breslau, P. Cao, L. Fan, G. Philips, and S. Shenker, “Web Caching and Zipf-Like Distributions: Evidence and Implications,” Proc. IEEE Infocom, pp. 126-134, 1999.[3] G. Cao, L. Yin, and C.R. Das, “Cooperative Cache-Based Data Access in Ad Hoc Networks,” Computer, vol. 37, no. 2, pp. 32-39, Feb. 2004.[4] G. Cao, “Proactive Power-Aware Cache Management for Mobile Computing Systems,” IEEE Trans. Computers, vol. 51, no. 6, pp. 608-621, June 2002.[5] P. Cao and S. Irani, “Cost-Aware WWW Proxy Caching Algorithms,” Proc. USENIX Symp. Internet Technologies and Systems, pp. 193-206, 1997.[6] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, “Selection in Expected Linear Time,” Introduction to Algorithms, second ed., pp. 185-189, 2001.[7] M.E. Crovella and A. Bestavros, “Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes,” IEEE/ACM Trans. Networking, vol. 5, no. 6, pp. 835-846, 1997.[8] M. Crovella and P. Barford, “The Network Effects of Prefetching,” Proc. IEEE Infocom, pp. 1232-1239, 1998.[9] P. Deolasee, A. Katkar, A. Panchbudhe, K. Ramamritham, and P.J. Shenoy, “Adaptive Push-Pull: Disseminating Dynamic Web Data,” Proc. WWW Conf. 2001, pp. 265-274, 2001.[10] F. Douglis, A. Feldmann, B. Krishnamurthy, and J.C. Mogul, “Rate of Change and Other Metrics: A Live Study of the World Wide Web,” Proc. USENIX Symp. Internet Technologies and Systems, pp. 147-158, 1997.[11] D. Eppstein and D.S. Hirschberg, “Choosing Subsets with Maximum Weighted Average,” J. Algorithms, vol. 24, no. 1, pp. 177-193, 1997.[12] S. Glassman, “A Caching Relay for the World Wide Web,” Computer Networks & ISDN Systems, vol. 27, no. 2, pp. 165-173, 1994.[13] Y. Jiang, M.Y. Wu, and W. Shu, “Web Prefetching: Cost, Benefits and Performance,” Proc. 11th World Wide Web Conf. (WWW), 2002.[14] R. Kokku, P. Yalagandula, A. Venkataramani, and M. Dahlin, “NPS: A Non-Interfering Deployable Web Prefetching System,” Proc. USENIX Symp. Internet Technologies and Systems, 2003.[15] T.M. Kroeger, D.E. Long, and J. Mogul, “Exploring the Bounds of Web Latency Reduction from Caching and Prefetching,” Proc. USENIX Symp. Internet Technologies and Systems, pp. 13-22, 1997.[16] C. Liu and P. Cao, “Maintaining Strong Cache Consistency in the World-Wide Web,” Proc. IEEE Int'l Conf. Distributed Computing Systems, pp. 12-21, 1997.[17] E.P. Markatos and C.E. Chironaki, “A Top 10 Approach for Prefetching the Web,” Proc. INET '98: Internet Global Summit, July 1998.[18] N. Nishikawa, T. Hosokawa, Y. Mori, K. Yoshidab, and H. Tsujia, “Memory Based Architecture with Distributed WWW Caching Proxy,” Computer Networks, vol. 30, nos. 1-7, pp. 205-214, 1998.[19] S. Shah, K. Ramamritham, and P.J. Shenoy, “Resilient and Coherence Preserving Dissemination of Dynamic Data Using Cooperating Peers,” IEEE Trans. Knowledge and Data Eng., vol. 16, no. 7, pp. 799-812, July 2004.[20] A. Venkataramani, P. Yalagandula, R. Kokku, S. Sharif, and M. Dahlin, “The Potential Costs and Benefits of Long-Term Prefetching,” Computer Comm., vol. 25, no. 4, pp. 367-375, 2002.[21] L. Yin, G. Cao, C. Das, and A. Ashraf, “Power-Aware Prefetch in Mobile Environments,” Proc. IEEE Int'l Conf. Distributed Computing Systems, pp. 571-578, 2002.
Index Terms:
Index Terms- Web server, World Wide Web, Web caching, Web prefetching, content distribution, Web object, hit rate, bandwidth, optimal object selection, randomized algorithm.
Citation:
Bin Wu, Ajay D. Kshemkalyani, "Objective-Optimal Algorithms for Long-Term Web Prefetching," IEEE Transactions on Computers, vol. 55, no. 1, pp. 2-17, Jan. 2006, doi:10.1109/TC.2006.12
