| author: | Predrag R. Jelenković, Xiaozhu Kang and Ana Radovanović |
|---|---|
| title: | Near optimality of the discrete persistent access caching algorithm |
| keywords: | persistent-access-caching, least-recently-used caching, least-frequently-used caching, move-to-front searching, generalized Zipf's law distributions, heavy-tailed distributions, Web caching, cache fault probability, average-case analysis |
| abstract: |
Renewed interest in caching techniques stems from their
application to improving the performance of the World Wide
Web, where storing popular documents in proxy caches closer
to end-users can significantly reduce the document download
latency and overall network congestion. Rules used to
update the collection of frequently accessed documents
inside a cache are referred to as cache replacement
algorithms. Due to many different factors that influence
the Web performance, the most desirable attributes of a
cache replacement scheme are low complexity and high
adaptability to variability in Web access patterns. These
properties are primarily the reason why most of the
practical Web caching algorithms are based on the easily
implemented Least-Recently-Used (LRU) cache replacement
heuristic. In our recent paper [JERA04tr], we introduce a
new algorithm, termed Persistent Access Caching (PAC),
that, in addition to desirable low complexity and
adaptability, somewhat surprisingly achieves nearly optimal
performance for the independent reference model and
generalized Zipf's law request probabilities. Two drawbacks
of the PAC algorithm are its dependence on the request
arrival times and variable storage requirements. In this
paper, we resolve these problems by introducing a discrete
version of the PAC policy (DPAC) that, after a cache miss,
places the requested document in the cache only if it is
requested at least
k
times among the last
m
,
m≥k
, requests. However, from a mathematical perspective,
due to the inherent coupling of the replacement decisions
for different documents, the DPAC algorithm is considerably
harder to analyze than the original PAC policy. In this
regard, we develop a new analytical technique for
estimating the performance of the DPAC rule. Using our
analysis, we show that this algorithm is close to optimal
even for small values of
k
and
m
, and, therefore, adds negligible additional storage
and processing complexity in comparison to the ordinary LRU
policy.
|
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Predrag R. Jelenković and Xiaozhu Kang and Ana Radovanović (2005), Near optimality of the discrete persistent access caching algorithm, in 2005 International Conference on Analysis of Algorithms, Conrado Martínez (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AD, pp. 201-222 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAD0120.ps.gz (153 K) |
| ps-source: | dmAD0120.ps (402 K) |
| pdf-source: | dmAD0120.pdf (308 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.