New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Caching of Multiple Request Chains

SpeakerVeronika Sonigo

Co-authorKersani, Trystram, Wagner and Xu

In this talk, we deal with the caching problem of multiple request chains on a web server. In the classical approach of web caching only one request chain is considered and we extend this problem to multiple concurrent request chains, which we call multi-threaded caching problem. We consider a single web server with a cache of size K. Users send several requests to the server for treatment. This induces processing times and the server can store intermediate results in the cache to save on processing time. In this context, we are interested in makespan minimization as well as in the minimization of the mean completion time of the request chains. Two caching models are considered. In the first model caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as a bound for inapproximation.