|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
A Design Framework for Online Algorithms Solving the Object Replacement Problem
Seiichiro TANI Toshiaki MIYAZAKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E84-D
No.9
pp.1135-1143 Publication Date: 2001/09/01 Online ISSN:
DOI: Print ISSN: 0916-8532 Type of Manuscript: PAPER Category: Algorithms Keyword: network, cache, competitive, online algorithm,
Full Text: PDF>>
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).
|
|
|