Hierarchical ICP Caches

Squid and other Harvest-derived hierarchical caches maintain no directory apart from each caching server's directory of its own contents; the global directory consists of the aggregate of the local directories. Caches are organized in a loose hierarchy: to probe the collective cache, a caching server multicasts an ICP message to its neighbors (siblings) and parents, which respond with a HIT only if they have a local copy of the requested object. If the request misses or times out, a selected parent continues the probe by repeating the process, multicasting to its neighbors and parents. If the request misses at each level of the hierarchy, then a top-level parent fetches the object from the source, caches it, and passes it back down the hierarchy.

This approach has several drawbacks:

• The ``cache coverage'' available to any caching server does not include the contents of its descendents or its ``cousins'' and their descendents. This is because queries only travel up the hierarchy, never down. This can result in a large number of false misses unless the parents are large enough to replicate most of the objects held by their descendents.

• The directory probe mechanism is combined with object transfer; fetched objects may pass through several intermediate caching servers on their way to the original requester. Tewari et al. [17] show that this leads to remarkably high latencies in some configurations, motivating shallower and ``bushier'' hierarchies. It also places unnecessary load on high-level servers that field the cache misses from all of their descendents.

• Multicasting can increase the probe load on all caching servers to unmanageable levels. Our studies [9] showed that a three-level hierarchy of caches using ICP can send an order of magnitude more query traffic through the network than a CRISP cache of equivalent size equipped with a central mapping server.

• Lost ICP messages or busy neighbor caches increase miss latencies. A caching server must wait for all neighbor caches to respond with a miss (or timeout) before directing the request upwards through the hierarchy. Bushier hierarchies increase the probe load on all children of a common parent, and increase the probability that some caching server will time out on a query. Our studies showed that ICP message drops and timeouts contribute to higher miss latencies, even in small configurations.

These problems motivate ``flat'' cache structures with a scalable directory structure that provides a more complete index of the collective cache's contents.