Identification

Adaptive Web Caching:
Towards a New Global Caching Architecture

Abstract

1. Introduction

As Zhang, Floyd, and Jacobson argued in [31], an adaptive, highly scalable, and robust web caching system is needed to effectively handle the exponential growth and extreme dynamic environment of the World Wide Web. This paper elaborates on the initial architecture for an adaptive web caching system outlined in [31]. When this web caching architecture was initially proposed, several other approaches to building a caching system for the World Wide Web were also introduced, including the SQUID web-caching system, which has since been widely deployed and has emerged as the de facto standard for web caching. Although the SQUID system has proven successful in accomplishing many the goals of web caching, we believe our adaptive approach to the problem provides an effective, natural evolutionary step towards a truly scalable, robust, efficient, and demand-driven web-caching system.

The dominant web-cache infrastructure on the Internet today consists of a hierarchy of SQUID Object Caches. In the SQUID system, all cache servers are inter-connected in a manually configured hierarchical tree. Each cache server exchanges Internet Cache Protocol (ICP) queries and replies with its "peers" (siblings and parent) in order to determine the most appropriate peer from which to retrieve a client's requested web content (either via a cached copy or directly from the origin server). Fueled in part by SQUID's success in demonstrating the potential benefits of web caching on the Internet, a proliferation of research in possible improvements to the system has recently emerged. For instance, it has been observed that the required manual configuration of the SQUID hierarchy can be significantly improved in the following ways. First, this aspect of the system may be enhanced to eliminate the heavy burden placed on system administrators who must coordinate with each other. Second, it may be modified to make the system less prone to both human error and system administrators' misunderstanding of the issues concerning the performance of the overall system. Third, it should be changed to address the fact that manual configuration may significantly hinder both the scalability of the system as well as the system's ability to adapt to changing network conditions. In addition, SQUID's single, static hierarchy may be enhanced to address the potential problem of inefficient routing of web requests. This problem can arise since all cache misses must first be fetched by a root node, which may be significantly farther from the origin server than the client's proxy cache. Moreover, the fact that the static hierarchy is not necessarily well suited to the unpredictable, roving nature of web hot-spots is also subject to improvement. SQUID can be further optimized to avoid the inordinate amount of delay associated with the 3-way handshake protocol for exchanging ICP messages. Lastly, the possibility that upper nodes in the SQUID hierarchy may become excessively loaded and degrade both the system's performance and ability to scale offers another opportunity for enhancement. Thus, these challenges associated with improving the SQUID system suggest that the system must evolve towards a more scalable, adaptive, efficient, and self-configuring web-caching system in order to effectively support the phenomenal growth in demand for web content on the Internet.

We believe our adaptive web caching system provides an effective evolutionary step towards this goal. As originally presented in [31], the general architecture of the envisioned adaptive web caching system would be comprised of many cache servers that self-organize themselves into a tight mesh of overlapping multicast groups and adapt themselves as necessary to changing conditions (see Figure 1). This mesh of overlapping groups forms a scalable, implicit hierarchy that is used to efficiently diffuse popular web content towards the demand. (The reader is referred to [31] for further details of the general architecture). There are two important research issues associated with this approach: (1) how to self-organize web caches to establish the different paths of communication among the cache groups in the mesh/hierarchy; and (2) how to forward requests and other information along the most appropriate path. The high-level focus of our work, then, is (1) to design a reasonable architecture for an adaptive, scalable web caching system; and (2) to determine the most effective direction of evolution from the current web caching infrastructure to our proposed system.

This paper extends our original white paper on adaptive web caching [31] by first proposing how the current web-caching infrastructure may evolve towards an adaptive web-caching system and by discussing the system and its associated research issues, including those mentioned above, in greater detail than before. The paper is organized as follows: We first discuss in Section 2 a realistic evolutionary path from the currently deployed SQUID caching infrastructure to our proposed adaptive system. In Section 3, we discuss how caches may share information about their contents, and in Section 4, we present our recent progress in our protocol for forwarding requests through our mesh of cache groups. We then describe the issues and mechanisms of self-organization in Section 5, and finally, we conclude our paper in Section 6.

2. Time Scales

Incremental deployment is critical in introducing or modifying any global-scale system; it is infeasible to envision the one-step deployment or modification of such large systems. A good plan for incremental deployment is especially important for an adaptive caching system since multicast, an important element in the system architecture, is not yet ubiquitously supported, and some of the research goals are on a longer time scale than others (e.g., self-organization is a longer term research topic). In addition, an adaptive caching system would be built on top of the existing web caching infrastructure, and this requires small, incremental changes to the system.

As a result, we envision a deployment of adaptive web caching in three distinct phases, in which the evolution from one stage to the next would occur in tandem with the evolution of the Internet itself as needed functionality for adaptive web caching becomes widely supported in the Internet. The three deployment phases would be (1) the introduction of adaptive web caching for distributing information and web requests among the cache mesh, without multicast and self-organization; (2) the addition of multicast as a mechanism for both efficient group communication and as a building block for the self-organization of groups, which will be introduced in the third phase; and finally (3) the introduction of self-organization into the adaptive web caching system to make it completely adaptive and robust.

It is unlikely that multicast will be ubiquitously supported on the Internet in the near-term, and thus we cannot assume that adaptive web caching will initially be able to leverage the efficiencies and useful properties of multicast. At the same time, even if the long-term research goal of enabling cache servers to self-organize themselves into reasonable overlapping groups in an adaptive and fully distributed manner was fully realized, it would not be likely to be deployed in the current web caching infrastructure in the near term. An initial deployment of adaptive web caching, then, would take place in a mesh of manually organized cache servers that communicate with each other largely using unicast communications. It should be noted that although multicast serves a more important purpose than only as an efficient group communication mechanism in our system, the use of unicast suffices in an initial deployment of adaptive web caching with cache groups that are manually configured and static. That is, in an initial deployment of adaptive web caching, the routing of information among the cache mesh would be adaptive, but the underlying communication infrastructure among the web caches would not static. In this short-term system, there are two important research issues that we will address: (1) how web caches share and make use of information about the contents of other nearby caches; and (2) how to best route requests through the manually configured cache mesh (including how to handle "cold" page requests). Both of these issues are discussed in more detail in the next section.

Once multicast is sufficiently widely supported on the Internet, the second phase of deployment of adaptive web caching may be initiated. Adding multicast to our system provides two primary benefits. First, it allows members of a group to communicate and share information efficiently; and second, it provides the necessary functionality for a scalable, fully distributed algorithm to self-organize the cache servers into overlapping multicast groups. (Such an algorithm requires that each cache server be able to freely join or leave cache groups without having to inform anyone in the group. Multicast groups provide this capability).

Thus, the primary research issue for this intermediate-term system is how to best leverage multicast both in the intermediate-term as well as in the long-term final system.

Finally, an adaptive web caching system can only be fully deployed after the achievement of a long-term research goal of developing a scalable, robust, adaptive, and fully distributed protocol for self-organizing an arbitrary number of cache servers into overlapping multicast groups based on some vector of metrics (e.g. delay and bandwidth between group members, demand for web content, cache server load). The addition of self-organization to an adaptive web caching system will in turn make the whole system scalable, adaptive, and robust. Some of the fundamental underlying research issues here will be (1) how to efficiently self-organize the groups to provide good communication paths among the caches in the cache mesh; (2) how to organize caches separated by some political or resource-constrained boundary (e.g., transoceanic links, network boundaries between secure organizations); and (3) whether an implicit hierarchy (cache mesh) is adequate or if an explicit hierarchy (a second level cache structure overlaid over a lower level cache mesh) is needed. These research issues along with others associated with self-organization are discussed in greater detail in Section 5.

3. Information about the Contents of Nearby Caches

There are two distinct issues in applying adaptive algorithms for the exchange of information among caches in a cache mesh. First, within a region or local area, caches receiving a request for data check to see if some nearby cache already has the requested contents. A second step dynamically routes the request to another cache or caches within the cache mesh after the first step has failed. In this section we address the first step, of caches availing themselves of the contents of nearby caches.

In our earliest thoughts of a adaptive web caching architecture, as in the current SQUID caching infrastructure, caches used explicit probing to query neighboring caches about their cache contents. In the SQUID architecture, for example, a SQUID cache sends a query to its sibling caches and waits for a positive acknowledgment that the requested content is cached within the sibling group. Several recent proposals have proposed alternative mechanisms that would reduce the unnecessary delay of this explicit probing behavior. One such approach is [9], where Bloom filter hash code sets are periodically exchanged between siblings. This allows each sibling to make an informed judgment about whether or not a requested URL is cached elsewhere in the group. These exchanges also can eliminate the replica effect of nearby caches all caching the same data, thus enlarging the aggregate cache capacity of the sibling group.

(Footnote: A completely different issue is that of neighboring or co-located caches under common administrative control. In this case, hash codes can be used not only to disseminate information about cache contents, but in fact to allocate different portions of the URL address space to different caches within the cache group. [21])

Our current approach to adaptive web caching is that caches exchange content state periodically with other members of their cache group, eliminating the delay and unnecessary use of resources of explicit cache probing. Adaptive web caches exchange their entire content state with the other members of their cache groups. URL hash coding is employed as a compression mechanism. Each URL whose contents occur in a single cache is decomposed into scheme (e.g., "html"), network location (DNS host name), and following path components. Repeated URL decompositions are organized as a tree. A depth first traversal of the tree yields a string of hash codes, which are subsequently exchanged.

An immediate concern is the size of the multicast message as caches accumulate a large number of URLs. This content state exchange is only transmitted to an individual cache's group membership, and not globally to all adaptive web cache groups. The size of the content state message scales in the number of the tree nodes. There is a tradeoff between the reduced delay that results from more complete information about other caches' URL decomposition trees, and the additional imposed load of larger or more frequent state exchange messages. Another immediate concern is the effectiveness of the hashing scheme and the number of false positives. This is a piece of ongoing research. A secondary concern is cache update synchronization, as [10] found in routers exchanging RIP protocol messages. As [10] proposes, synchronization can be broken by randomizing the exchange interval.

4. Forwarding Requests

In this section, we consider adaptive approaches for the forwarding of requests within the cache mesh. These forwarding mechanisms are used after a cache has decided that none of its nearby caches themselves have the requested contents. In some cases, it is sufficient for a cache to forward requests to a fixed set of ``parent'' caches in a hierarchy. This is a reasonable approach for the current web caching infrastructure, when one of the first-order limitations is that of congested trans-oceanic links connecting clients in other continents with busy web servers situated in North America. A fixed hierarchy for forwarding requests is also sufficient for those extremely hot web pages that are quickly disseminated to web caches throughout the global web caching infrastructure. However, as the web caching infrastructure increases in both size and content diversity, the importance of adaptive algorithms increases when requests cannot be satisfied locally and must be forwarded towards the origin server, a nearby replicated server, or a closer large cache judged likely to have the desired contents.

As articulately argued in [25], design principles for the global web caching infrastructure include minimizing both the number of cache hops to access the data and the delay for a request that cannot be satisfied by the web caching infrastructure. For requests that are not sufficiently hot and thus not pervasively distributed among the web caching infrastructure, minimizing the number of cache hops to access the data is accomplished by forwarding the request to a cache or caches significantly closer to the origin or replicated server, thereby significantly increasing the likelihood of reaching a cache that already has the requested data. In certain cases, minimizing the number of cache hops to access the data is also accomplished by forwarding the request to a cache known to be significantly more likely to have the data, regardless of that cache's distance to the origin or replicated server. For a request that is not sent directly to the origin server, the delay in the case of a miss is only minimized if that request was routed to a cache closer towards the origin/replicated server.

We propose that web caches maintain a URL routing table, and use this URL routing table to decide when to forward a request to another cache in the web caching infrastructure. The URL routing table bears a resemblance to the IP routing table: caches would maintain a URL prefix table just as routers maintain an IP network prefix table. This URL routing mechanism could be deployed in the current unicast-based web caching infrastructure or in an infrastructure based on multicast groups of web caches. The URL routing table's primary keys are URL prefixes, with which are associated one or more identifiers to the next-hop caches or cache groups. The URL prefix may be a distinct, complete URL, or, more typically, an aggregation of URLs designated by their common scheme, network location and path components. For URLs that do not match to anything more specific in the URL routing table, a default entry may exist in the table, similar to the default forwarding entry maintained in many IP routing tables. This allows the familiar tradeoff between minimizing overhead and optimizing request routing (by decreasing or increasing the level of detail in the URL routing table).

The information for the URL routing table is learned from caches within the participating caching infrastructure, transparent to web clients and servers. The initial information for the URL routing table comes from source-based entries from regional caches which determine from their own experience of sending requests directly to servers that they are near in seconds to the server or servers for URLs matching a particular URL prefix. These source-based entries result from a cache's proximity to a specific server or replicated server, or from that cache's more general proximity to an entire set of servers (e.g., all the servers from "*.berkeley.edu", or all the servers from the same country). The information for the source-based entries include the URL prefix, an identifier for the cache, and a metric reflecting that cache's average measured delay in seconds to retrieve a request from a matching URL.

A second information source for the URL routing table is derived from content-based entries. Content-based entries are learned from caches which accumulate URLs matching a certain URL prefix, either as the result of administrative policy or their own request history. An example scenario where content-based entries are necessary is the Japan cache in the United States [19], created to cache entries from servers with domain names "*.jp". Caches distinguish between source-based and content-based entries. Because forwarding decisions made on content-based entries are less likely to head towards the origin server, these forwarding decisions are more likely to increase request delay in the event of a cache miss.

We are exploring a range of possible approaches for caches to build URL routing tables based on these source-based and content-based entries from other web caches. One possibility is to use a distance-vector-style routing algorithm among the web caches, based on the rough measured metric of "seconds" between caches and their neighboring caches.

A second approach to building the URL routing table restricts the global URL routing table to a subset (e.g., at most several hundred) of large caches. These large caches would use a link-state routing analogue to learn the inter-cache distances among the large caches. This approach reflects an inherent underlying structure of the web caching infrastructure into larger regional caches that participate in the global URL routing table, and smaller local caches that tend to serve their local community. Each cache constructs its own URL routing table based on its knowledge of the cache topology, combined with the source-based and content-based entries distributed among the large web caches indicating which caches are close in seconds to which URL prefixes. In the case of replicated servers, several distant large caches would report themselves as close to the same URL prefix.

5. Self-Organization

We are still in the early stage of developing a Cache Group Management Protocol (CGMP) to let autonomous Web caches organize themselves into multiple, overlapping multicast groups, forming a transport substrate for URL requests and data flow. We envision that, on the base of this mesh of overlapping cache groups, each popular page grows its own cache tree. Cache trees for "flash spots" may come and go highly dynamically, but the cache groups can remain relatively stable. They gradually and continuously adjust themselves according to dynamic changes in the operational environment, such as changes in network topology due to new cache servers coming up and existing ones removed or links coming up or going down, and changes in traffic load and user demand levels.

We have considered several possible mechanisms for self-configuration of cache groups. These included approaches based on reaction-diffusion models found in biology as well as more traditional negotiation techniques. Further examination of scaling issues, however, led us to abandon those approaches in favor of a new voting scheme with which we have had success in preliminary simulation studies.

The fundamental design goals of CGMP include making the entire cache topology group-wise connected, making the grouping follow and match the topological constraints, and grouping caches to minimize the number of "hops" a URL request must travel upon cache fault. Groups that cross trans-oceanic links should keep the group size minimal in order to minimize the intra-group communication cost, while nearby caches with high bandwidth connectivity should group themselves together. Furthermore, a group should cover a contiguous neighborhood in network topology (that is, not fragmented by intersections with other groups). The last point implies that whether a cache joins a group G should not be determined by whether its location is close to a single member of G, but by taking into account the locations of all members in G.

In the proposed voting scheme, cache servers periodically send a voting message for each group for which it is a member to a well-known multicast address, at the same time individually deciding which cache groups to join based on the voting announcements received from other cache servers. The overlapping of cache groups is achieved by letting caches join more than one group. Each voting message contains the group ID for the cache group and a voting signal. Recipients of a voting message from member M of group G evaluate the voting signal relative to their distance from M, and then treat this value as the partial support from M for their membership in G. The sum of all the partial supports a cache received from members of G indicates its appropriateness for membership in group G. If the support for membership in G surpasses a threshold, a cache wishing to join G (an "applicant") may simply begin operating as a member of G. If a member of G notices a decline in voting support below a different threshold, it will exit group G (it has been "voted out").

In addition to sending periodic voting messages to all other caches, members and applicants of a group G also multicast "voting requests" to the multicast group G; an unconnected cache may simply send requests to the well-known address. These requests call for some relative increase or decrease in the voting signal. Group members average the requests, and alter the form and distance of their voting signals in response. In this way, each member indirectly responds to every applicant, as members attempt to balance the strength of the voting signal to be "strong enough" to support distant members and applicants as it can, while not being "too strong" for those members that are close-by.

Using a well-known multicast address to bootstrap auto-configuration allows for transparent neighborhood discovery and configuration-free initialization. The associated overhead can be controlled by adjusting both the frequency of the voting messages and the maximum distance to which the messages travel. To achieve cache connectivity, an unconnected cache sends "voting requests" with increasing TTL values until it can receive voting signals. Because the TTL value controls the number of router hops a message travels, a trans-oceanic link is counted the same way as a FDDI hop. Thus an increasing TTL value assures that the request eventually reaches other existing caches. On the other hand, caches take into account measured delays and connectivity between each other in considering the appropriateness of group membership, so that a group crossing a trans-oceanic link will most likely result in the minimal size of two caches (one at each end), and a group crossing a campus FDDI ring will include all the caches connected to the ring. A special case that is yet to be incorporated into our design is handling of satellite channels --- although it has a long propagation delay, its broadcast nature suggests the grouping of all its connected caches.

Preliminary simulation results have shown the voting scheme to be stable, resistant to node failures, adaptive to changing topology, and successful in forming and maintaining the group at any desired size. The simulations performed so far are based on small topologies and very coarse-grained, however. We are moving onto larger scale simulation tests to examine the proposed scheme in more realistic network settings.

6. Conclusion

Extending Zhang's, Floyd's, and Jacobson's original Adaptive Web Caching proposal in [31], we have discussed both our recent progress in designing our adaptive caching system as well as some of the important research issues associated with our work. In particular, we have presented our research towards building an adaptive mesh of overlapping multicast groups of cache servers via a self-organizing mechanism. We have also discussed how we intend to forward web requests and content through the cache mesh such that the web content can efficiently meet its demand.

We believe our proposed adaptive, self-configuring web caching system is needed to adequately accommodate the current exponential growth in demand for web content. Our design has specifically been designed to scale well with the total traffic volume as well as with the number of users, hosts, and networks in the Internet. At the same time, our system is designed to remain robust and efficient in the face of the dynamic network conditions that typically characterize the Internet. Although our system is being designed specifically for the World Wide Web, we believe that many of the research issues that we are addressing can be more generally applied to other Internet systems that face issues of scale and that can benefit from caching (such as FTP).

8. Bibliography

1. G. Andulla, E.A. Fox, M. Abrams, S. Williams, "WWW Proxy Traffic Characterization with application to caching" http://csgrad.cs.vt.edu/~abdulla/proxy/proxy-char.ps
2. M. Baentsch, L. Baum, Georg Molter, S. Rothkugel, and P. Sturm, "World Wide Web Caching: The Application-Level View of the Internet", IEEE Communications, June 1997.
3. M. Baentch, A. Lauer, L. Baum, G. Molter, S. Rothkugel, P. Sturm, "Quantifying the overall impact of caching and replication in the Web", http://www.uni-kl.de/AG-Nehmer/Projekte/GeneSys/Papers/tr0297.ps
4. Bhattacharjee, S., Calvert, K., and Zegura, E., "Self-Organizing Wide-Area Network Caches", Infocom 98.
5. Cohen, J.D. "Recursive Hashing Functions for n-grams", ACM Transactions on Information Systems, vol 15, no. 5, 291-320, July 1997.
6. C.R. Cuhna, A. Bestavros, M.E. Crovella, "Characteristics of WWW client-based Traces", http://www.cs.bu.edu/techreports/abstracts/95-010
7. G. Dias, G. Cope, R. Wijayyaratne, "A Smart internet caching system", http://www.isoc.org.ar/inet96/proc/a4/a4_3.htm
8. B.M. Duska, D. Marwood, M.J. Feeley, "The measured Access Characteristic of WWW Client Proxy Caches", Proceedings, USENIX Symposium on Internet technologies and Systems. http://cs.ubc.ca/spider/marwood/Projects/SPA/wwap/
9. Li Fan, Pei Cao, Jussara Almeida, and Andrei Broder, "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", Technical Report 1361, Computer Sciences Department, University of Wisconsin-Madison.
10. Floyd, S. and Jacobson, V. "The synchronization of periodic routing messages". IEEE/ACM Transactions on Networking, vol. 2, no. 2, April 1194, pp. 122-136.
11. S. Gadde, M. Rabinovich, J. Chase, "Reduce, Reuse, Recycle: An approach to building large internet caches", http://www.cs.duke.edu/ari/cisi/crisp-recycle/crisp-recycle.htm
12. S. Galssman, "A caching relay for the WWW", http://www.research.digital.com/SRC/personal/Steve_Glassman/CachingTheWeb.ps
13. S.D. Gribble, E.A. Brewer, "System design issues for internet middleware services: deductions form a larg client trace". http://www.cs.berkeley.edu/~gribble/papers/sys_trace.ps.gz
14. A. Heddaya, S. Mirdrad, D. Yates, "Diffusion based caching along routing paths", http://cs-www.bu.edu/faculty/heddaya/Papers-NonTR/webcache-wkp.ps.Z
15. J. Jung, K. Chon, "Nation-wide Caching project in Korea - Design and Experimentation", http://ircache.nlanr.net/Cache/Workshop97/Papers/Jaeyeon/jaeyeon.html
16. R. Malpani, J. Lorch, D. Berger, "Making WWW caching servers cooperate", http://www.w3j.com/1/lorch.059/paper/059.html
17. Masaaki Nabeshima, "The Japan Cache Project: An Experiment on Domain Cache", WWW6 proceedings.
18. I. Melve, L. Slettjord, H. Bekker, T. Verschuren, "Building a web caching system - Architectural considerations", http://ircache.nlanr.net/Cache/Workshop97/Papers/Bekker/bekker.ps
19. M. Nabeshima, "The Japan cache project", http://ircache.nlanr.net/Cache/Workshop97/Papers/Nabeshima/nabeshima.html
20. M. Ogushi, K. Ono, "A study of caching proxy mechanisms realized on wide area distributed networks", Proceedings of the Fifth IEEE International Symposium on High Performance Distributed Computing.
21. Ross, K., "Hash Routing for Collections of Shared Web Caches", IEEE Networks, vol. 11, no. 6, November/December 1997, 37-44.
22. J.E. Pitkow, M.M. Recker, "A simple yet robust caching algorithm based on dynamic access patterns", http://www.vuw.ac.nz/~mimi/www/www-caching/caching.html
23. Dean Povey and John Harrison, "Distributed Internet Cache", 20th Australasian Computer Science Conference, February 1997.
24. Radhika Malpani, Jacob Lorch and David Berger, "Making World Wide Web Caching Servers Cooperate", Proceedings of the Fourth International World Wide Web Conference, Boston, December 1995.
25. Renu Tewari, Michael Dahlin, Harrick Vin and Jon Kay, "Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet", Technical Report TR98-04, Department of Computer Sciences, University of Texas at Austin, February 1998.
26. Renu Tewari, Harrick Vin, Asit Dan and Dinkar Sitaram, "Resource Based Caching for Web Servers", Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking(MMCN), San Jose, January 1998.
27. Russell Tewksbury, "Is the Internet Heading for a Cache Crunch? ", OnTheInternet, January/February 1998.
28. D. Wessels, "Intelligent caching for WWW Objects", http://info.isoc.org/HMP/PAPER/139/archive/papers.ps.9505216
29. R.P. Wooster, "Optimizing response time, rather than hit rates, of WWW proxy caches", http://scholar.lib.vt.edu/theses/public/etd-34131420119653540/etd.pdf, 1996.
30. R.P. Wooster, M. Abrams, "Proxy Caching that Estimates Page Load Delays", http://www.cs.vt.edu/~chitra/docs/www6r/
31. L. Zhang, S. Floyd, and V. Jacobson, "Adaptive Web Caching", Initial proposal, February 1997.
32. Zheng Wang and Jon Crowcroft, "Cachemesh: A Distributed Cache System For World Wide Web", Extended abstract, June 1997.