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
네트워크 캐시는 네트워크 트래픽과 사용자 응답 시간을 줄여줍니다. 네트워크 캐시를 구현할 때 객체 교체 문제는 핵심 문제 중 하나입니다. 문제는 공간이 부족할 때 캐시에서 어떤 개체를 제거해야 하는지 결정하는 것입니다. 이 논문은 먼저 문제를 공식화하고 결정론적 온라인 알고리즘이 경쟁력을 갖추기 위한 간단하면서도 충분한 조건을 제공합니다. 이 조건을 바탕으로 비경쟁적인 알고리즘을 경쟁력 있게 만들기 위한 일반적인 프레임워크를 구축합니다. 프레임워크의 적용으로 Competitive_SIZE라는 온라인 알고리즘을 제안한다. 이벤트 기반 및 추적 기반 시뮬레이션 모두 Competitive_SIZE가 LRU(Least Recent Used)와 같은 이전에 제안된 알고리즘보다 우수하다는 것을 보여줍니다.
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.
부
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
부
@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},}
부
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 -