A study of integrated document and connection caching in the WWW

Susanne Albers, Rob Van Stee

Research output: Contribution to journalArticlepeer-review

Abstract

Document caching and connection caching are extensively studied problems. In document caching, one has to maintain caches containing documents accessible in a network. In connection caching, one has to maintain a set of open network connections that handle data transfer. Previous work investigated these two problems separately while in practice the problems occur together: In order to load a document, one has to establish a connection between network nodes if the required connection is not already open. In this paper we present the first study that integrates document and connection caching. We first consider a very basic model in which all documents have the same size and the cost of loading a document or establishing a connection is equal to 1. We present deterministic and randomized online algorithms that achieve nearly optimal competitive ratios unless the size of the connection cache is extremely small. We then consider general settings where documents have varying sizes. We investigate a FAULT model in which the loading cost of a document is 1 as well as a BIT model in which the loading cost is equal to the size of the document.

Original languageEnglish
Pages (from-to)239-252
Number of pages14
JournalAlgorithmica
Volume47
Issue number3
DOIs
StatePublished - Apr 2007
Externally publishedYes

Keywords

  • Caching
  • Connection caching
  • Online algorithms

Fingerprint

Dive into the research topics of 'A study of integrated document and connection caching in the WWW'. Together they form a unique fingerprint.

Cite this