Duplicated Hash Routing: A Robust Algorithm for a Distributed WWW Cache System

Eiji KAWAI  Kadohito OSUGA  Ken-ichi CHINEN  Suguru YAMAGUCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.5   pp.1039-1047
Publication Date: 2000/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Next Generation Internet Technologies and Their Applications)
Category: 
Keyword: 
fault tolerance,  distributed WWW caching systems,  hash routing,  hit rates,  network traffic,  

Full Text: PDF(922.2KB)>>
Buy this Article




Summary: 
Hash routing is an algorithm for a distributed WWW caching system that achieves a high hit rate by preventing overlaps of objects between caches. However, one of the drawbacks of hash routing is its lack of robustness against failure. Because WWW becomes a vital service on the Internet, the capabilities of fault tolerance of systems that provide the WWW service come to be important. In this paper, we propose a duplicated hash routing algorithm, an extension of hash routing. Our algorithm introduces minimum redundancy to keep system performance when some caching nodes are crashed. In addition, we optionally allow each node to cache objects requested by its local clients (local caching), which may waste cache capacity of the system but it can cut down the network traffic between caching nodes. We evaluate various aspects of the system performance such as hit rates, error rates and network traffic by simulations and compare them with those of other algorithms. The results show that our algorithm achieves both high fault tolerance and high performance with low system overhead.