Duplicated hash routing: A robust algorithm for a distributed WWW cache system

Hash routing is an algorithm for a distributed WWW caching system that achi eves a high hit rate by preventing overlaps of objects between caches. Howe ver, one of the drawbacks of hash routing is its lack of robustness against failure. Because WWW becomes a vital service on the Internet, the capabili ties of fault tolerance of systems that provide the WWW service come to be important. In this paper, we propose a duplicated hash routing algorithm, a n 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 clien ts (local caching), which may waste cache capacity of the system but it can cut down the network traffic between caching nodes. We evaluate various as pects 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 hig h performance with low system overhead.