Biblio

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.

Caching methods are developed since 50 years for paging in CPU and database systems, and since 25 years for web caching as main application areas among others. Pages of unique size are usual in CPU caches, whereas web caches are storing data chunks of different size in a widely varying range. We study the impact of different object sizes on the performance and the overhead of web caching. This entails different caching goals, starting from the byte and object hit ratio to a generalized value hit ratio for optimized costs and benefits of caching regarding traffic engineering (TE), reduced delays and other QoS measures. The selection of the cache contents turns out to be crucial for the web cache efficiency with awareness of the size and other properties in a score for each object. We introduce a new class of rank exchange caching methods and show how their performance compares to other strategies with extensions needed to include the size and scores for QoS and TE caching goals. Finally, we derive bounds on the object, byte and value hit ratio for the independent request model (IRM) based on optimum knapsack solutions of the cache content.