Directory Structures for Collective Internet Caches

Efficient directory management is the key design problem for any Internet cache. Several considerations influence the design choices:

• Load on the internal network. Important to almost all configurations, internal network usage affects link contention and congestion and the potential for lost packets on the network connecting the caching servers, e.g., an ISP's internal network.

• Costs of external network usage. Web caches exist in part to reduce bandwidth demands on the external network. One reason to deploy Web caches is altruistic: if everyone is a ``good citizen'', then everyone benefits from reduced congestion on backbone links and Web servers. A second reason is that caches can directly affect access costs when Internet access charges are metered by traffic volume.

• Object fetch latency. From the perspective of an individual client, object fetch latency is the most important motivation for using a Web cache, and the only real measure of its success.

• Latency of the internal network. As the network distance between the servers in a collective cache increases, synchronous network exchanges with remote parts of the cache are no longer practical. Geographically dispersed caches must localize query traffic by replicating the directory or reducing the ``coverage'' of queries.

The following subsections explore several directory structures and evaluate them with respect to these considerations.