Ulana Legedza and John Guttag
Software Devices and Systems Group
Laboratory for Computer Science
Massachusetts Institute of Technology
545 Technology Square, room 536
Cambridge, MA 02138 USA
{ulana,guttag}@lcs.mit.edu
http://www.sds.lcs.mit.edu/
Phone: +1 617 253 2376
Topic: Caching Infrastructures
We present the design of a new distributed Web caching infrastructure. Our work is motivated by the need to provide effective caching not only for the small number of extremely popular Web documents, but also for the large number of documents of only intermediate popularity. In other currently existing and proposed systems, requests for less popular documents suffer from long latency stemming from the inefficiencies of routing through an application-level overlay network. We combat this problem by integrating cache routing into the network layer. This results in shorter search paths and fewer application-level checks.
It is widely agreed that a distributed cooperative Web caching infrastructure is needed to provide scalable and timely access to all Internet servers. Most proposed approaches construct a network of caches as an overlay on the Internet. A key challenge for such schemes is the design of an efficient algorithm for searching the network of caches for the desired document. While very popular documents can usually be found quickly, the search for less popular documents may follow a long and circuitous path of numerous failed checks. The impact of this is substantial since, as seen in [2], the hit rate on web caches is typically less than 50%, indicating a large number of documents of only low to moderate popularity.
Our work is aimed both at reducing the time needed to find relatively unpopular, but cached, documents and at reducing the latency of searching for documents that are not cached. At the same time, we want to avoid sacrificing the other important goals of: ease of configuration, balancing load across the caches, efficient use of storage and bandwidth resources, and low latency for fetching popular documents.
The key idea behind our approach is to do more work at the network level. In particular, we integrate the routing of requests to caches with the routing services already provided within the network. Although deployment of the approach involves some changes and extensions to network routers, packet headers and endpoint protocol processing, this effort is justified by the following benefits:
The paper is organized as follows. In the next two sections, we elaborate on the cache routing problem and describe our solution. Then we present related work and end with concluding remarks.
Scalability and deployment concerns have led most designers of Web caching infrastructures to design schemes based on deploying a large number of Web caches scattered around the Internet. The main challenge in such approaches is being able to quickly find a cache containing the desired document. While this problem is similar to the general problem of network routing, it cannot be solved in the same way.
Conventional routing protocols scale because of the route aggregation made possible by hierarchical addressing. However, since documents with the same URL prefixes or server address prefixes will not necessarily be delivered to the same clients, there is no necessary relation among their cache locations. With no way to aggregate routes, the cache routing tables would be unmanageably large. In addition, they would have to be updated frequently.
This problem leads us to do cache routing by searching. Some sequence of caches is checked for the document, and if it isn't found in any of them, the request is forwarded to the home server. Additionally, some of the checked caches request the document for themselves, to help out future requests.
The question, of course, is how to make this search fast? The common wisdom is to grow a caching distribution tree away from each popular server towards sources of high demand. This works well for requests for very popular documents, because these documents will propagate out to many caches, and so will be found quickly. However, requests for less popular documents are likely to suffer. Unpopular documents will be cached in only a few places, if anywhere. So, requests for these documents will undergo numerous failed cache checks before either finding the document, or going to the home server after all. As caching systems scale to accommodate a growing Internet, this number of failed checks will be large. This can introduce two significant sources of latency: repeated transitions between application and network layers and, since cache placement is independent of network topology, a large number of network hops.
Most currently deployed distributed Web caching systems are manually configured hierarchical systems based on Harvest/Squid [1, 10], such as the NLANR hierarchy in the U.S. [11]. Caches joining such a hierarchy may represent individual client sites, geographical regions, or countries. Requests for Web documents are forwarded up the hierarchy in search of a cached copy. In an attempt to keep from overloading caches at the root, caches query their siblings before passing requests upwards. This approach lengthens the duration of each check. As the hierarchy grows to accommodate more users and more documents, there is an adverse impact on the numerous requests for objects that are not very popular. Also, as described in [13], in upper levels of the hierarchy, requests can be deflected far away from their original route to the home server.
Some of these problems are addressed in Adaptive Web Caching [13] in which a mesh of caches is used, and distribution trees for each server are built in the mesh. The caches in the mesh are organized into overlapping multicast groups through which a request travels in search of a cached document. This scheme benefits from constructing different distribution trees for different servers (so no one root node will be overloaded) and being robust and self-configuring. However, less popular queries still suffer because they will travel through many caches, and each check requires a query to and responses from a group of machines. The authors suggest dealing with this problem by limiting the number of caches a request will access, but this may greatly reduce the hit rate for everything other than the most popular pages.
These approaches suffer from trying to do routing at the application layer, through an overlay network. Our approach, described next, avoids these inefficiencies by pushing the task of routing requests to caches down into the router/network level.
Like many approaches, ours addresses the situation where a number of caches are scattered throughout the Internet. Also like other approaches, we grow a distribution tree for each server towards the sources of high demand. The principal novelty of our approach is that it addresses the problem of searching for less popular documents by,
The complications arise in deciding which documents to cache where and in maintaining this information in the appropriate routers.
To diffuse a server hot spot, cache redirection pointers are placed in the network nodes forming the routing tree leading to the overloaded server, usually at traffic aggregation points. Each router's redirection pointers redirect requests for cached documents to a nearby Web cache. Other requests are simply forwarded on to their home server destination. This will reduce the load converging on the hot spot by intercepting some of the traffic heading towards it. Two important benefits result from the redirection pointers lying directly in the path of the targeted traffic: 1) caches become in some sense easy to "find," so caches do not need to be manually configured with the addresses of their neighbors, and 2) requests for items that are not cached anywhere are not redirected away from their original shortest path to their destination. Also, requests for less popular documents experience at most one application-level check.
In figure 1, the solid lines and black nodes form part of the routing tree extending from two neighboring servers, S and T. C1 to C4 are application-level Web caches. Each dotted line connects a router to the cache that is closest to it. Imagine that S is currently very popular, its outgoing traffic causing a bottleneck at link 7-6. As a result, traffic coming from T suffers. In the proposed approach, caching of some of S's data at node C1 would be dynamically enabled by placing a redirection pointer at node 6. This would divert some of the load from S to C1, eliminating the bottleneck. As demand for S grows, redirection may also be enabled at nodes 1 and 5, bringing in the help of cache C2. In this way, a cache-based distribution tree for S's data grows towards the sources of highest demand.
In order to implement a complete system using the above basic framework, the following are needed:
Here we describe how to accomplish these tasks.
Each participating router node maintains a URL-indexed table of cache addresses indicating if and where a particular document is (or should be) cached at a nearby cache. The table size is kept under control since the URLs of documents not cached nearby do not have table entries. To make indexing by URL easier, we index the table by the MD5 hash of the URL string. To avoid re-computation at every node, this hash could be carried along in the request packet header. As a Web request packet travels through the Internet towards its URL's home server, routers along the way perform a table lookup using the URL hash in the packet. The request is rerouted only if an entry is found.
Since each table entry is small (256 bytes: 128 for the hash and 128 for the IPv6 cache address), a large number of redirection pointers can be cached. Table lookup takes about as much time as a routing table lookup, so this slows down the routing of Web request packets by a factor of two in the case of a miss.
When a request arrives at a cache, it is either serviced locally or first retrieved from the home server. To avoid redirection loops, requests from cache nodes are specially marked and not redirected to any other caches.
In most Web caching systems, caches observe all the Web request traffic passing through a particular link or network region, and thus can make a well-informed decision of what documents to cache. In our scheme, caches are only allowed to see requests for documents that have already been flagged for caching. This means that some other entity must determine document popularity, and install appropriate redirection pointers to reroute requests. In our design, each document's home server performs this role.
A server, upon detecting that it is busy, and soon to be overloaded, performs traffic analysis to determine which documents to cache where. It first triggers the packets traveling to it to collect the IP addresses of the participating routers they travel through. The server then uses this information to reconstruct a routing tree leading to it. Using this tree, the server figures out where most of the traffic is concentrated, and where caching would be most useful. The server then sends a message to the appropriate node(s) to enable caching there.
This scheme can be viewed as a new implementation of the push-caching [3] approach. The network support we provide allows us to gather better information on the sources of demand for each document (using network paths rather than geographical and zip code information) and to implement push-caching in a simpler way.
A server detects that it is busy by observing an increase in its request rate. While busy, the server periodically monitors the source of its high load by enabling path-tracing on all new connections for a period of time. During this interval, the server responds to document requests with an ACK packet that has a special path-trace bit set. This prompts the client to send out its next packet (an ACK, or request for data) as a path-tracing packet, that collects the IP addresses of all routers it passes through. The server collects this information for many connections into a tree data structure resembling the routing tree leading to it. After the monitoring period is over, the server traverses the tree to determine the network regions generating a large fraction of its traffic, and chooses routers at the roots of such regions to serve as redirection points for its traffic. The server then sends a message with the unique ID's of its most popular documents to the chosen routers. Each router installs the pointers in its table and sends an ACK to the server. For reliability, the server re-transmits if no ACK is received.
Because each router's table size is limited, the pointers installed by one server may be evicted to make room for the pointers of more popular documents from another server. This may cause a server to repeatedly and frequently send pointer-enable messages to a particular router. To avoid this, the server employs a backoff strategy for each router it contacts during a busy period. To work well, this strategy needs feedback from the routers about the rate at which table entries are being added and about how often documents to that server are being requested through that router. This feedback can be easily obtained from the traffic analysis.
When patterns of demand change, it may be necessary to disable some redirection pointers. To remove stale redirection pointers, we rely on two mechanisms. First, routers employ an LRU (or other appropriate) policy for table entries, so some entries for documents that are no longer popular will be evicted because of space constraints. Second, a cache may choose to delete pointers for documents that it has evicted from its own storage. In order to enable this, every time a router performs a redirection, it appends its own IP address to the packet header. Then, when a cache receives a request for a recently evicted page, it can send a pointer removal message to the appropriate router.
In order for routers to discover the caches around them, caches send out periodic broadcasts (of limited radius or scope). Routers not receiving any broadcast messages do not participate in cache redirection. If a router receives more than one cache announcement message, it can choose to use some subset of the caches based on a cache characteristic advertised in the message (e.g., distance from router, size, load). This cache discovery scheme makes it easy to deploy new caches because it does not require manual configuration of routers with cache addresses. In addition, it enables routers to dynamically adapt to changing conditions by selecting different caches.
In order to keep from redirecting requests to a cache that is no longer responding, these broadcasts also serve as keep-alive messages. A router does not redirect requests to any cache it has not heard from recently.
Deploying a scheme of this kind is not a trivial matter. Our design requires changes and extensions to network routers, packet headers, and endpoint protocol processing. Instead of treating all packets alike, routers must perform different processing for document request (connection setup) packets and for data transfer and acknowledgement packets.
Incorporating such a scheme into the current Internet would require replacing a large number of routers (though not all). Instead of attempting that, we are using Active Network [8] technology as a deployment mechanism. An active router is one that can be dynamically extended to provide many different types of services beyond conventional IP routing and forwarding. This extensibility makes it possible to deploy new services while avoiding the difficulty of modifying existing routers. In an ANTS-style [12] active network, a packets specifies a particular service routine to be loaded run on its behalf on each active router it encounters. This routine can perform arbitrary (but short) computation, store information in soft-state, and create and send packets back out into the network. The ANTS system takes care of obtaining the code for this routine from its own code cache or from previous nodes in the packet's path. The default routine performs conventional IP forwarding. We are currently implementing our caching scheme on the ANTS network in our lab, and plan to deploy it on the nationwide (U.S.) ABone.
As an alternative to significant change in network infrastructure, we have also developed a variant of our approach that does not have as many benefits, but can be deployed much more easily. It leverages existing router technology - specifically, Cisco Cache Engine routers [7], which can be configured to redirect all incoming Web traffic to a nearby cache. We use these routers to create a Web caching infrastructure that keeps requests on paths closely resembling the shortest paths to the home server, but does require numerous (but simple) application-level cache checks.
Using these routers, caches can be scattered around the network as before, but each participating router must be statically configured to be associated with some cache. While this is the only way to use these routers at present, it has a key drawback. Requests for less popular objects are serviced at every cache along their paths, making latency long. However, if we change the caches to service only requests for relatively popular documents (by keeping a count for each URL request it sees during a time), then the cache service time for requests for less popular documents is greatly shortened, only consisting of the presence check and counter increment. While many application-level checks are made, they are shorter, and the request's path length should not be greatly lengthened.
In this section, we describe how our work relates to previous work on distributed Web caching infrastructures. We consider schemes that redirect requests to application-level cache servers scattered throughout the Internet. We also consider other efforts to provide network-level support for Web caching.
A recurring problem in most application-level distributed Web caching systems is the long latency incurred by requests for objects that are cached in very few places, if anywhere. Section 2 described why this is the case for multicast-based Adaptive Web Caching [13] and hierarchical approaches like Squid/NLANR [11]. Here we provide several more examples.
Like Squid/NLANR, Povey and Harrison [6] construct a manually-configured hierarchy that must be traversed by all requests. Their scheme is promising in that it reduces load on top-level caches by only keeping location pointers in the hierarchy, but it suffers from the same inefficiencies for less popular documents.
Panigrahy [5] describes a theoretically-based technique for constructing per-server distribution trees with good load balancing properties. However, since server load is not taken into account when determining tree size, the trees for small and/or lightly-loaded servers may be too big, resulting in many useless application-level checks. Also, since trees are random, the client-server paths through them are likely to be much longer than the regular routing path from client to server.
Wang and Crowcroft [9] describe a preliminary plan to put cache routing tables in caches to specify, for each page or server, where to look next if the local cache does not hold the document. A default route for some documents would help to keep table size reasonable. Our approach can be considered to be a network-supported implementation of this very general idea. Our tables are located in routers (separate from the caches, however), and the default route is simply the path to the home server. Since any application-level implementation would have to route requests through an overlay network, it would exhibit the same inefficiencies as the other approaches.
In a different approach, push-caching [3], Gwertzman and Seltzer propose having each server track geographical access information and mirror its data accordingly. For example, if a server in California is overloaded, and a large percentage of requests is coming from the East Coast, then a mirror site is set up on the East Coast. The home server redirects future requests from the East Coast to the East Coast mirror. Our approach implements this general idea and improves upon it in several ways. First, we collect more accurate topology information to help choose a better location for the mirror. Also, our redirection pointers will intercept requests from the East Coast and redirect them to the mirror automatically, avoiding the cross-continental latency otherwise required to find out about possible mirrors.
Both Cisco's Cache Engine [7] and USC's translucent caching [4] are similar to our approach in that they provide network-level support for redirecting Web requests to an appropriate application-level cache. The Cache Engine router simply redirects all incoming Web traffic to its associated cache. It does not provide a scheme for managing a network of such caches. Earlier in this paper we described a scheme that improves this situation. Translucent caching routers intercept Web requests, and forward the address of a nearby cache back to the requestor. This scheme increases the latency of requests by adding a round trip at each hop.
Our work is motivated by the need to provide effective caching not only for the small number of extremely popular Web documents, but also for the large number of documents of only intermediate popularity. In all the currently existing and proposed systems with which we are familiar, requests for less popular documents suffer from long latency stemming. We combat this problem by integrating cache routing into the network layer in a way that results in shorter search paths and fewer application-level checks.
In our scheme, servers place per-document redirection pointers in routers to direct requests for popular documents to nearby caches. Router support for path tracing allows servers to gather the information needed to make intelligent choices on pointer placement. The result is that requests for less popular documents are allowed to travel quickly to the home server or to a cache near a traffic aggregation point. This approach exhibits the benefits of having caches in routers without actually having to put them there. Also, configuration of the system is simplified by the fact that caches do not need to know about each other in order to cooperate.
The key technology enabling our approach is a collection of router mechanisms that export network-level information to the application--in this case, Web caching. In some sense, this dependence on network-level support is a liability because it makes it difficult to implement our approach in the current network infrastructure. On the other hand, the benefits of our scheme demonstrate the need for such network-level support, and our work can serve to to suggest new services that should be incorporated into future routers.
We thank David Wetherall for many helpful discussions about network caching and for his work on ANTS. We also thank Frans Kaashoek, Vanu Bose, and Hariharan S. Rahul for their insightful comments on the design of our approach.
This work was supported by DARPA and by seed funding from Sun Microsystems Inc., and monitored by the Office of Naval Research under contract No. N66001-96-C-85221.