Result: A study of integrated document and connection caching in the WWW

Title:
A study of integrated document and connection caching in the WWW
Authors:
ALBERS, Susanne, VAN STEE, Rob
Source:
An APPOL meeting in Bertinoro, Italy, 23-28 March 2003Algorithmica. 47(3):239-252
Publisher Information:
New York, NY: Springer, 2007.
Publication Year:
2007
Physical Description:
print, 11 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme déterministe, Deterministic algorithms, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Antémémoire, Cache memory, Antememoria, Compétitivité, Competitiveness, Competitividad, En ligne, On line, En línea, Modélisation, Modeling, Modelización, Plan randomisé, Randomized design, Plan aleatorizado, Structure document, Document structure, Estructura documental, Transmission donnée, Data transmission, Transmisión datos, Caching, Connection caching, Online algorithms
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Informatik, Albert -Ludwigs -Universität, Georges -Köhler -Allee, 79110 Freiburg, Germany
Fakultät für Informatik, Universität Karlsruhe, 76128 Karlsruhe, Germany
ISSN:
0178-4617
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18660758
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18660758
Database:
PASCAL Archive

Further Information

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.