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>>
Buy this Article


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).