The Costs of a Central Map

The CRISP mapping service allows independent proxy caches (e.g., at the department or branch level) to be coalesced to form a single large cache. However, this central structure imposes new costs to store the central map, and message exchanges to probe the map and notify it of fetches or evictions at participating proxies.

At first approximation, the dollar cost of the mapping service is the price of a machine with enough physical memory to hold what amounts to a replica of the directories of all participating proxy caches. The map is simply a hash of URLs, which are small relative to the Internet objects they name. A recent study [3] indicated that the average object is about 10K bytes. If we conservatively estimate the average URL size at 100 bytes, then the data that passes through the mapping service is about 1% of the aggregate size of the CRISP cache, e.g., a gigabyte of storage for a 100G cache. However, we require that the map reside in physical memory since disk accesses would add unacceptably to the mapping server latency.

The central mapping service is not a latency bottleneck or a significant barrier to scalability for three basic reasons:

• Requests to the map contain little more than a URL. Since no actual object data passes through the mapping server, it does not have the I/O or network demands of a cache, and is therefore able to serve the needs of many caches without saturating.
• The response time of a well-configured and properly functioning mapping server is well below the ability of a human being to perceive the delay, and is small relative to the cost of retrieving the object itself, even for a cache hit (see Section 3).
• A CRISP mapping service can expand incrementally by adding more mapping servers, dividing responsibilities by statically partitioning the URL space across the servers. While a statically partitioned mapping service may suffer from hot spots, this can be offset by configuring mapping servers well below their saturation point, which adds only marginally to the cost of a CRISP cache.

The key limitation of CRISP is that the round-trip network latency between each proxy and the mapping service must be low, say, 20 ms at most. This may in practice limit the geographical size of the cache. In general, we envision that mapping service traffic will be carried as high-priority traffic over an ISP's internal network.