University of Houston
Department of Computer Science


In partial fulfillment of the Requirements for the Degree of
Master of Science


Sui Shen
will defend her thesis

Design and Trace Driven Analysis of a HOME-Bias Cache Array Protocol


Abstract

Web caches are employed to reduce the latency for access to web pages and to alleviate network traffic. Multiple caches can cooperate to provide this service and several protocols exist to support that. In this work, we propose a new protocol for cooperative web caching called "HOME-Bias". CARP and ICP are two well-known existing protocols for cooperative caching. CARP eliminates duplication of objects and provides the best possible hit ratio for the array of caches. CARP also eliminates the need to check caches for objects. However, CARP inherently implies a low local cache hit ratio. ICP provides a high local cache hit ratio but leads to duplication and a lower cache array hit ratio. ICP also requires additional network communication to check caches for presence of objects. The goal of HOME-Bias is to get the best of CARP and ICP, that is, to minimize duplication, maximize array and local hit ratio, and minimize network traffic. In HOME-Bias, every web object has a designated home cache, but the object may be cached elsewhere also. When an object is not found on a local cache, only the home cache is checked. Each cache distinguishes between home and non-home objects. Home objects have explicit advantage over non-home objects. Two different approaches, age-based biasing and space-based biasing, can be used to implement the HOME-Bias protocol. Trace-driven simulation shows that HOME-Bias can achieve an array hit ratio very close to CARP and average response time comparable to ICP while minimizing network traffic. The simulation also shows that home objects should have significant advantage over non-home objects. This can be achieved by evicting home objects at a much older age or by reserving a large part of the cache for home objects. Simulation results also demonstrate the scalability of the HOME-Bias protocol.



Date: Thursday, March 28, 2002
Time: 4:00 PM
Place: 550-PGH


Faculty, students, and the general public are invited.
Thesis Advisor: Dr. Jaspal Subhlok