A Randomized Online Algorithm for the File Caching Problem

Seiichiro TANI; Toshiaki MIYAZAKI

A Randomized Online Algorithm for the File Caching Problem

Seiichiro TANI, Toshiaki MIYAZAKI

Full Text Views

0

Share
Cite this

Summary :

Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2^{log ^* k}) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^{log ^* k} is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.4 pp.686-697

Publication Date: 2003/04/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms

Cite this

Copy

Seiichiro TANI, Toshiaki MIYAZAKI, "A Randomized Online Algorithm for the File Caching Problem" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 4, pp. 686-697, April 2003, doi: .
Abstract: Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2^{log ^* k}) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^{log ^* k} is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e86-d_4_686/_p

Copy

@ARTICLE{e86-d_4_686,
author={Seiichiro TANI, Toshiaki MIYAZAKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Randomized Online Algorithm for the File Caching Problem},
year={2003},
volume={E86-D},
number={4},
pages={686-697},
abstract={Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2^{log ^* k}) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^{log ^* k} is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - A Randomized Online Algorithm for the File Caching Problem
T2 - IEICE TRANSACTIONS on Information
SP - 686
EP - 697
AU - Seiichiro TANI
AU - Toshiaki MIYAZAKI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2003
AB - Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2^{log ^* k}) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^{log ^* k} is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.
ER -