A Design Framework for Online Algorithms Solving the Object Replacement Problem

スポンサーリンク

概要

• 論文の詳細を見る

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

• 社団法人電子情報通信学会の論文
• 2001-09-01

著者

• Tani Seiichiro

  With Ntt Network Innovation Labs.

• MIYAZAKI Toshiaki

  with NTT Network Innovation Labs.

関連論文

• A Design Framework for Online Algorithms Solving the Object Replacement Problem

スポンサーリンク