Web caching with request reordering

ABSTRACT

Current web caching algorithms process requests in the order of the arrival. While such restriction is inevitable in system paging due to the sequential nature of a program, the HTTP requests are (essentially) independent at a high volume proxy server. This gives a proxy server the flexibility to reorder requests, provided no request is inordinately delayed. The expectation is that reordering requests may lead to better performance. We formulate an online k-reordering problem that captures such phenomenon for unit caches. We give a dynamic programming algorithm to solve the offline case. We give O(1) upper and lower bound on the competitive ratio of the online algorithms. We also generalize this problem to any metric space.

REFERENCES

• 1: Houman Alborzi , Eric Torng , Patchrawat Uthaisombut , Stephen Wagner, The k-client problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.73-82, January 05-07, 1997, New Orleans, Louisiana, United States
• 2: Saks Michael, An Online Scheduling Problem with Job Set-ups, Certer for Discrete Mathematics & Theoretical Computer Science, 2000