New results on web caching with request reordering

ABSTRACT

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. [6], who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. [7] gave online strategies that have nearly optimal competitive ratios in several cost models.In this paper we first present a deterministic online algorithm that achieves an optimal competitiveness, for the most general cost model and all cache sizes. We then investigate the offline problem, which is NP-hard in general. We develop the first polynomial time algorithms that can manage arbitrary cache sizes. Our strategies achieve small constant factor approximation ratios. The algorithms are based on a general technique that reduces web caching with request reordering to a problem of computing batched service schedules.Our approximation result for the Fault Model also improves upon the best previous approximation guarantee known for web caching without request reordering.

REFERENCES

• 1: Dimitris Achlioptas , Marek Chrobak , John Noga, Competitive analysis of randomized paging algorithms, Theoretical Computer Science, v.234 n.1-2, p.203-218, March 6, 2000 [doi>10.1016/S0304-3975(98)00116-9]
• 2: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 3: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 4: L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78--101, 1966.
• 5: P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. Proc. USENIX Symposium on Internet Technology and Systems, 193--206, 1997.
• 6: Tomás Feder , Rajeev Motwani , Rina Panigrahy , An Zhu, Web caching with request reordering, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.104-105, January 06-08, 2002, San Francisco, California
• 7: Tomás Feder , Rajeev Motwani , Rina Panigrahy , Steve Seiden , Rob van Stee , An Zhu, Combining request scheduling with web caching, Theoretical Computer Science, v.324 n.2-3, p.201-218, 20 September 2004 [doi>10.1016/j.tcs.2004.05.016]
• 8: A. Feldmann, A. Karlin, S. Irani and S. Phillips. Private communication, transmitted through {11}, 1996.
• 9: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 10: Parikshit Gopalan , Howard Karloff , Aranyak Mehta , Milena Mihail , Nisheeth Vishnoi, Caching with expiration times, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.540-547, January 06-08, 2002, San Francisco, California
• 11: Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
• 12: L.A. McGeoch and D.D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816--825, 1991.
• 13: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 14: Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
approximation, batch, cache, competitive, document, offline, online