The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -