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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/09/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
network, cache, competitive, online algorithm,
Full Text: PDF>>
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).