Probabilistic Analysis of LRU Caching in the WWW Environment

Predrag Jelenkovic

Dept. of Electrical Engineering, Columbia Univ.


Caching is widely recognized as an effective method for improving the efficiency and scalability of multimedia content delivery over the World Wide Web (WWW). It is essentially a process of keeping a smaller collection of frequently requested documents at points in the network where they can be accessed with high speed/low latency.

The most popular caching algorithms in practice are based on the Least-Recently-Used (LRU) cache replacement rule that possesses many desirable characteristics, including high hit ratio, low complexity and the flexibility to dynamically adopt to possible changes in request patterns. We present some of our recent results on the probabilistic analysis and modifications of LRU caching scheme for the WWW environment, characterized by strong statistical correlation of requests and variable document sizes.

Joint work with Ana Radovanovic

[Predrag Jelenkovic]
[Dept. of Electrical Engineering, Columbia Univ.]