Combining request scheduling with web caching

We extend the classic paging model by allowing reordering of requests under the constraint that a request is delayed by no longer than a predetermined number of time steps. We first give a dynamic programming algorithm to solve the offline case. Then we give tight bounds on competitive ratios for the online case. For caches of size k, we obtain bounds of k+O(1) for deterministic algorithms and Θ(log k) for randomized algorithms. We also give bounds for the case where either the online or the offline algorithm can reorder the requests, but not both. Finally, we extend our analysis to the case where pages have different sizes.

Authors

• Tomás Feder
• Rajeev Motwani
• Rina Panigrahy
• Steve Seiden
• Rob van Stee
• An Zhu

Keywords

• Paging
• Web caching
• Request reordering