A Design Framework for Online Algorithms Solving the Object Replacement Problem
Summary :
Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).
- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.9 pp.1135-1143
- Publication Date
- 2001/09/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Seiichiro TANI, Toshiaki MIYAZAKI, "A Design Framework for Online Algorithms Solving the Object Replacement Problem" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 9, pp. 1135-1143, September 2001, doi: .
Abstract: Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_9_1135/_p
Copy
@ARTICLE{e84-d_9_1135,
author={Seiichiro TANI, Toshiaki MIYAZAKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Design Framework for Online Algorithms Solving the Object Replacement Problem},
year={2001},
volume={E84-D},
number={9},
pages={1135-1143},
abstract={Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - A Design Framework for Online Algorithms Solving the Object Replacement Problem
T2 - IEICE TRANSACTIONS on Information
SP - 1135
EP - 1143
AU - Seiichiro TANI
AU - Toshiaki MIYAZAKI
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2001
AB - Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).
ER -
English
