Interreference interval for purged objects: a new metric for design and analysis of Web caching algorithms

Author

Tanaka, Atsuhiro ; Tatsukawa, Kosuke

Author_Institution

Internet Syst. Res. Labs., NEC Corp., Kanagawa, Japan

fYear

2003

fDate

9-11 April 2003

Firstpage

549

Lastpage

554

Abstract

This paper proposes a new metric, called interreference interval for purged objects (II-PO for short) to capture temporal locality in Web references. The metric is used in a partitioned cache model to design and optimize Web caching algorithms. We derive an optimal condition, using the proposed metric, for cache hit ratio in a partitioned cache model. An optimization of the 2Q algorithm is described, as an example, through the obtained optimal partitioning. The case study with the WebPolygraph3 benchmark shows up to 20% relative improvement of the cache hit ratio over the Least Recently Used (LRU) algorithm.

Keywords

cache storage; file servers; optimisation; 2Q algorithm optimization; II-PO; LRU algorithm; Web caching algorithms analysis; Web caching algorithms design; Web references; WebPolygraph3 benchmark; cache hit ratio; interreference interval for purged objects; least recently used algorithm; optimal condition; partitioned cache model; temporal locality; Algorithm design and analysis; Design optimization; Internet; Laboratories; Load management; Mathematical model; National electric code; Partitioning algorithms; Random variables; Web server;

fLanguage

English

Publisher

ieee

Conference_Titel

Performance, Computing, and Communications Conference, 2003. Conference Proceedings of the 2003 IEEE International

ISSN

1097-2641

Print_ISBN

0-7803-7893-8

Type

conf

DOI

10.1109/PCCC.2003.1203742

Filename

1203742