| Title | General Knapsack Bounds of Web Caching Performance Regarding the Properties of each Cacheable Object |
| Publication Type | Conference Paper |
| Year of Publication | 2020 |
| Authors | Hasslinger, Gerhard, Ntougias, Konstantinos, Hasslinger, Frank, Hohlfeld, Oliver |
| Conference Name | 2020 IFIP Networking Conference (Networking) |
| Keywords | cache hit& value ratio, Clocks, delays, FIFO, GreedyDual and score-gated web cache strategies, knapsack bounds, LFU, LRU, Market research, Markov processes, Metrics, Optimization, pubcrawl, quality of service, Resiliency, Scalability, Upper bound, Web Caching |
| Abstract | Caching strategies have been evaluated and compared in many studies, most often via simulation, but also in analytic methods. Knapsack solutions provide a general analytical approach for upper bounds on web caching performance. They assume objects of maximum (value/size) ratio being selected as cache content, with flexibility to define the caching value. Therefore the popularity, cost, size, time-to-live restrictions etc. per object can be included an overall caching goal, e.g., for reducing delay and/or transport path length in content delivery. The independent request model (IRM) leads to basic knapsack bounds for static optimum cache content. We show that a 2-dimensional (2D-)knapsack solution covers arbitrary request pattern, which selects dynamically changing content yielding maximum caching value for any predefined request sequence. Moreover, Belady's optimum strategy for clairvoyant caching is identified as a special case of our 2D-knapsack solution when all objects are unique. We also summarize a comprehensive picture of the demands and efficiency criteria for web caching, including updating speed and overheads. Our evaluations confirm significant performance gaps from LRU to advanced GreedyDual and score-based web caching methods and to the knapsack bounds. |
| Citation Key | hasslinger_general_2020 |
General Knapsack Bounds of Web Caching Performance Regarding the Properties of each Cacheable Object