The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Os caches de rede reduzem o tráfego de rede e também o tempo de resposta do usuário. Ao implementar caches de rede, o problema de substituição de objetos é um dos principais problemas; O problema é determinar quais objetos devem ser removidos de um cache quando não houver espaço suficiente. Este artigo primeiro formaliza o problema e fornece uma condição simples, mas suficiente para que algoritmos determinísticos online sejam competitivos. Com base na condição, é construída uma estrutura geral para tornar competitivo um algoritmo não competitivo. Como aplicação do framework, é proposto um algoritmo online, denominado Competitive_SIZE. Ambas as simulações orientadas por eventos e por rastreamento mostram que Competitive_SIZE é melhor do que algoritmos propostos anteriormente, como LRU (Least Recentemente Usado).
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.
Copiar
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
Copiar
@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},}
Copiar
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 -