Proxy Cache Replacement Algorithms : A History based Approach

Authors: A. Vakali

Title: Proxy Cache Replacement Algorithms : A History based Approach

Appeared in: World Wide Web Journal, Kluwer Academic Publishers, volume 4, issue 4, pages 277-298, 2001

Abstract: Accesing and circulation of Web objects has been facilitated by the design and implementation of effective caching schemes. Web caching has been integrated in prototype and commercial Web-based information systems in order to reduce the overall bandwidth and increase system’s fault tolerance. This paper presents an overview of a series of Web cache replacement algorithms based on the idea of preserving a history record for cached Web objects. The number of references to Web objects over a certain time period is a critical parameter for the cache content replacement. The proposed algorithms are simulated and experimented under a real workload of Web cache traces provided by a major (Squid) proxy cache server installation. Cache and bytes hit rates are given with respect to different cache sizes and a varying number of request workload sets and it is shown that the proposed cache replacement algorithms improve both cache and byte hit rates.

Περίληψη: Η προσπέλαση και η κυκλοφορία των αντικειμένων στον Παγκόσμιο Ιστό έχουν διευκολυνθεί σημαντικά από το σχεδιασμό και την υλοποίηση αποτελεσματικών σχημάτων εναποθήκευσης. Η εναποθήκευση στα πλαίσια του Παγκόσμιου Ιστού έχει ενσωματωθεί σε πρωτότυπα και εμπορικά πληροφοριακά συστήματα που βασίζονται στον Παγκόσμιο Ιστό, με σκοπό να μειωθεί το εύρος ζώνης και να αυξηθεί η ανοχή σφαλμάτων του συστήματος. Στην εργασία αυτή παρουσιάζεται μια σειρά από τους πιο σημαντικούς αλγορίθμους αντικατάστασης οι οποίοι βασίζονται στην ιδέα της διατήρησης ενός ιστορικού για τα εναποθηκευμένα αντικείμενα. Ο αριθμός των αναφορών των αντικειμένων του Παγκόσμιου Ιστού σε μία συγκεκριμένη χρονική περίοδο αποτελεί μια κρίσιμη παράμετρος για την αντικατάσταση του περιεχομένου της κρυφής μνήμης. Οι προτεινόμενοι αλγόριθμοι προσομοιώνονται και παρουσιάζεται πειραματισμός με πραγματικά δεδομένα φόρτου διακίνησης στο Διαδίκτυο. Διάφορες μετρικές επίδοσης (hit rate, byte hit rate) δίνονται αναφορικά με το μέγεθος της cache και των διάφορων φόρτων εργασίας. Τα πειραματικά αποτελέσματα είναι ιδιαίτερα θετικά για τη χρήση των προτεινόμενων αλγορίθμων στη διαδικασία αντικατάστασης των περιεχομένων της περιοχής εναποθήκευσης δεδομένων του Διαδικτύου αναφορικά με τις εξεταζόμενες μετρικές επίδοσης.

Download paper: ViewPDF