Evaluating the Utility of Multi-Layer WWW Cache Hierarchies Erich Nahum and Srini Seshan IBM T.J. Watson Research Center Yorktown Heights, NY 10598 Many proposals are being been made to dynamically and automatically establish WWW cache hierarchies (e.g., [1,2,3]). A growing mesh of WWW caches has occurred worldwide, with the NLANR's squid cache in the US backbone a good example [4]. However, it is not clear that multi-level cache hierarchies will provide similar benefit for the WWW as it does for other systems such as CPU caches. - The basic principle of caching states that a cache is only useful if both sufficient locality of reference exists and miss penalties are great enough. Simply adding caches to a hierarchy does not necessarily increase performance; this is why PC's do not have 6 levels of cache. While network miss penalties are certainly high enough, proxy cache hit ratios seem very low [12], even assuming things such as infinite size caches. In addition, each layer of cache removes locality from the remaining reference stream. - Chankhuntod et. al. [4] claim that adding an additional layer of cache adds between "4-10 milliseconds of latency", but this latency can grow as load increases on the cache, causing requests to queue up. The deeper in the network the cache is located, the larger the number of requests may potentially be, increasing the liklihood of queuing delays. - In order for hierarchy to help, it is necessary that there be locality in working sets between cache domains that is *not* present in a single domain. It is not clear that this is the case. Thus, we are concerned with the assumption that multi-layer WWW cache hierarchies will necessarily improve user performance and/or reduce network traffic. Our plan is to evaluate whether adding hierarchies can improve this situation, tracing multiple client sites to see if there is any shared aggregation that can be exploited. Adding further support for caching to to HTTP may also improve this situation [10]. Some other research from the computer architecture community that may help illuminate related issues in WWW caching include: - Multiprocessor cache coherency, which states that the choice of invalidation-based versus update based coherency protocols depends on application behavior. The behavior of WWW requests, particularly given that there is a single writer, can guide us as to how to design coherency into the WWW hierarchy. Liu and Cao [9] provides encouraging evidence that invalidation may be the appropriate mechanism. - In multiple-level CPU caches, when a piece of data is modified, an invalidation is typically delivered to each cache that holds a copy. The inclusion property states that, in order for a lower-layer cache to know whether to propagate an invalidation to a higher-layer cache, the lower-level cache must include all documents contained at higher layers. If an invalidation does not affect the lower-level cache, it need not propagate the signal up the hierarchy. In the WWW, however, a proxy need not contain the entire document to propagate invalidations, but simply the URL. This way, a proxy cache need not waste space caching documents that it knows are cached upstream. This may improve the hit rates of proxies deep in the network. Additional issues that we think are worth exploring at the workshop and beyond include: - There is a relationship to routing that should be examined: document routing rather than packet routing. An OSPF or BGP-like protocol seems likely that considers "next cache hop" routing with different service metrics. - Security must be considered. With the deployment of SSL and IP security (IPSEC), caching WWW documents may become even more difficult, due to either encryption or authentication. IBM Global Network is a growing provider of network services. Like any ISP, IGN may be able to benefit from the presence of a WWW cache infrastructure. We look forward to discussing these issues with participants at the NLANR Cache Workshop. References: [1] Floyd, Jacobson, and Zhang. Adaptive Web Caching. NLANR Web Caching workshop, 1997. [2] Heddaya, Suliman, and Yates. Diffusion-Based Caching along Routing Paths. NLANR Web Caching workshop, 1997. [3] Chankhunthod, Danzig, Neerdaels, Schwartz, and Worrell. A Hierarchical Internet Object Cache. USENIX 96. [4] NLANR Squid Cache pages, www.nlanr.net. [5] Balakrishnan, Seshan, Stemm, and Katz. Analyzing Stability in Wide-Area Networks. Sigmetrics 97. [6] Liu and Cao. Maintaining Strong Cache Consistency in the World-Wide Web. ICDCS 97. [7] Duane Wessels and Klaffy. Internet Cache Protocol (ICP), version 2. Internet draft . [8] Patterson and Hennessy. Computer Architecture: A Quantitative Approach. 2nd Edition, 1995. Morgan-Kaufman, publishers. [9] Baer and Wang. On the Inclusion Property for Multi-Level Cache Hierarchies. ISCA 88. [10] Fielding et. al. Hypertext Transfer Protocol -- HTTP 1.1. RFC 2068. [11] Jon Postel, Ed. Transmission Control Protocol. RFC 793. [12] Maltzahn, Richardson and Grunwald. Performance Issues of Enterprise-Level Web Proxies. SigMetrics 97.