Web Caching with Request Reordering

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 exibility 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 oine 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