Flash Crowds and Denial of Service Attacks: Characterization and Implications for CDNs and Web Sites

Jaeyeon Jung*, Balachander Krishnamurthy**, and Michael Rabinovich**

MIT Laboratory for Computer Science*
200 Technology Square
Cambridge, MA 02139
jyjung@lcs.mit.edu

AT&T; Labs-Research**
180 Park Avenue
{bala,misha}@research.att.com

Abstract

Categories and Subject Descriptors

General Terms

Keywords

1. Introduction

Unlike science fiction, the effect of flash crowds on the servers operating at the Web sites and the network infrastructure is real and can be acute. Congestion at the network layer may even prevent some of the requests from reaching the servers, and if they do, it can be after significant delays caused by packet loss and retransmission attempts. Servers are unable to handle the volume of requests that actually reach it. Finally, users who are trying to obtain information during a flash crowd are often frustrated due to the resulting long delays or outright failures. In some cases, the Web server may have to be restarted due to the effects of the flash crowd [21]. Given the increase in the frequency of flash crowds and their overall unpredictability, it is important that we have a broad understanding of flash crowds.

Our contributions in this paper are threefold:

• We define the term flash event (an event that causes flash crowds) and provide a taxonomy to better understand its impact on Web servers.

• Before studying the impact of flash events on Web servers, we need to identify and separate a related but distinct phenomenon---that of denial of service attacks (DoS [13]). DoS attacks have been occurring fairly frequently in the last few years on the Internet. A DoS attack shares several characteristics with that of flash events but is not a flash event. Our taxonomy of flash event is used to clearly identify and separate DoS attacks from flash events.

• After separating DoS, we examine current solutions by Web servers for dealing with flash events. Specifically, we examine what roles Content Distribution Networks (CDNs) play and we offer some solutions of our own in this regard.

While Web sites can try to provision for the predictable flash events, they often fail to correctly predict the demand, as several well planned events (such as the Victoria Secret webcast) could attest [27]. Even when a Web site has prior knowledge that its site is going to experience a surge in demand, it may not have enough time to react and provision the necessary resources. The issue is complicated by competitive pressure where various sites are planning to display similar content (such as a major news story). Both predictable and unpredictable flash events can thus pose a serious risk to a Web site.

DoS attacks and flash events can both overload the server or the server's Internet connection and result in partial or complete failure. Unlike DoS attacks, which are simply malicious requests that do not have to be handled by a Web site, flash events consist of legitimate requests. A Web server has the responsibility to try and handle as many of the requests as possible during a flash event. By doing so, the site can increase its overall profile on the Web resulting in possible additional revenue. If a DoS attack occurs during a flash event, a Web server should aim to ignore DoS requests and handle the legitimate requests. This requires the Web site to be able to distinguish between the two sets of requests.

Content Distribution Networks (CDNs) have been in use for a few years primarily to help offload the request volume on Web servers during normal Web activity. A CDN typically serves a subset of resources (often static images) on behalf of a set of origin servers via an overlay network. Besides being used to improve routine access to Web sites, CDNs can also serve as insurance protection against flash events so that Web sites can continue to function normally. However, some CDNs are not always capable of dealing with flash events and we present circumstances under which a flash event can cause a Web site to fail even if it uses a CDN. The primary reason is the surge of cache misses in the beginning of flash events. In this paper, we thus propose an alternate approach, called an adaptive CDN , which addresses this problem.

The rest of the paper is divided as follows: Section 2 defines flash events and DoS attacks and discusses metrics that are useful to characterize them. Section 2.1 discusses the somewhat limited amount of related work in this area. Sections 3 and 4 present characteristics of flash events and DoS attacks, respectively, with a view towards distinguishing between them. Section 4.3 summarizes the behavioral differences of flash events and DoS attacks and develops some recommendations for Web servers based on these differences. Section 5 discusses the difficulties some CDNs face due to flash events and presents our notion of an adaptive CDN. We conclude with a look at ongoing and future work.

2. Characterizing Flash Events and DoS Attacks

The key semantic difference between an FE and DoS is that the former represents legitimate access of the Web site while the latter does not. However, this does not help in distinguishing between the two automatically. One needs to develop behavioral differences between the two phenomena after understanding their individual properties. We characterize FE and DoS along the following dimensions:

• Traffic patterns: Traffic patterns as seen by the Web site are important for several reasons. Overall traffic volume determines how much a server should provision resources to keep the site operational up to a certain level. If server load exceeds its maximum tolerance level which is pre-defined by its capacity, the server begins to slow down and can be driven to a shutdown. Thus, watching traffic patterns allows us to articulate the period when an unusually large number of clients can overwhelm a site and how much time the server has from the start of an FE or DoS to take defensive measures.

• Client characteristics: Understanding client characteristics can help identify malicious attackers who intentionally stress a server pretending to be legitimate clients. When a server faces an unexpectedly heavy load, detecting DoS clients quickly would allow the server to reject their requests and concentrate resources on serving legitimate clients. In particular, we use a network-aware clustering technique [20] to determine the topological distribution of clients in FE and DoS. Client clustering allows one to aggregate individual clients into groups belonging to the same administrative domain. Clustering uses a large collection of unique network prefixes assembled from a wide set of BGP routing tables. The various client IP addresses are grouped into clusters based on longest prefix matching.

• File reference characteristics: File reference characteristics could potentially provide additional differentiators to rule out suspicious activities. Once it is clear that all requests come from legitimate clients, we can utilize file referencing behavior to deal with flash crowds. Locality of reference enables a reduction of server load through caching. We exploit these characteristics in designing an adaptive CDN. We consider aggregate file references as seen by the server, reference patterns of individual clients, and reference patterns of client clusters.

2.1 Related Work

However, there has been little published on Web workload analysis when traffic is very high. The World Cup Web site study [5] presents a peak workload analysis pointing out that file referencing is more concentrated on a few extremely popular pages. Also many clients repeatedly visited the site with shorter inter-session time. A study of the 1998 Olympic Games Web site [16] analyzed the workload and developed traffic models that could be used to predict seasonal traffic variations and peak request rates at a Web site during its normal operation. Neither study is, however, concerned with DoS attacks or implications on CDNs. A recent study [8] examined IP-flow-level traffic at the border router of the university network and presented flow characteristics of associated DoS attacks and flash crowd behavior. They found that flash crowd behavior was identified by rapid rise in traffic to a particular flow followed by a gradual drop-off over time. One incident of a DoS attack, on the other hand, was detected by a very sharp increase and decrease of the number of outgoing flows to a target server because each attempt was from a distinct source address and port number which appeared as a separate flow in the analysis. Our work focuses on HTTP-level traffic measurement and shows much detailed analysis of HTTP traces recorded at several Web sites.

Crovella et al. showed that under the high workload, shortest connection first scheduling algorithm improved the mean response time of Web servers by the factor of four or five [10]. A study of the effect of Ken Starr's report on NLANR Web caches by Wessels pointed out that inappropriate settings of Expires and Last-Modified header fields prevented ordinary caches from dealing effectively with flash events [28]. In contrast, our study presents an approach for improved flash crowd protection using CDNs assuming existing Web site behavior.

There have been a few suggestions, such as the pushback technique [12] and route-based packet filtering [25] for dealing with DoS attacks at the router level but our technique does not rely on changing router architecture and is complementary to anything that might bypass such a filter that may be deployed.

Requests from spiders are another type of HTTP requests that may inconvenience a Web site and, while usually legitimate, might be good candidates for being dropped by an overloaded site. Previous work on identifying these requests appeared in [20, 4] and is orthogonal to our study.

3. Flash Events

3.1 Data

Table 1: Basic statistics for Play-along and Chile traces. Data size is counted over the traces compressed with a gzip utility

To explore properties of flash events, we analyzed HTTP traces collected from two busy Web servers, one from the play-along Web site for a popular TV show (referred to as the Play-along site for short) and the other from the Chilean election site (referred to as the Chile site). Both traces reflect flash events. The Play-along site experienced such an event during the show time on TV. The Chile Web site hosted the continuously updated results of the 1999 presidential election in Chile.

Table 1 summarizes statistics of the two traces separately for the entire trace and for the FE segment, including the number of requests, documents and clients found in the traces. The table also lists the number of client clusters obtained by the network-aware client clustering technique [20].

3.2 Traffic Volume

(a) Play-along	(b) Chile

Figure 1: Traffic volumes (averaged over successive 2-second intervals)

Figure 1 shows the request rate experienced by the two sites over time. According to our definition of a flash event (FE) as a sudden growth in the request rate, we classify noticeable peaks as FE in each trace. The figure shows that the request rate grows dramatically during an FE but that the duration of the FE is relatively short. So, when provisioned to handle the peak load, servers would stay practically idle most of the time.

(a) Play-along	(b) Chile

Figure 2: Request rate at the beginning of FE

To see how much time a site has to react in the face of an unfolding FE, Figure 2 shows the traffic pattern when we zoom in on the first 15 minutes of the FE. Both figures show that request rate increase, while rapid, is far from instantaneous. In the Play-along case, the rate increase occurs gradually over the 15-minute interval from the time index of 60,600 second and reaches 6,719 req/sec at 64,700 second. The Chile trace has a much steeper rate increase, but even here the increase occurs over a few tens of seconds (from 39,334 second to 39,374 second) and reaches only half the peak rate: the peak rate of about 610 req/sec is reached only later, outside the time window shown in Figure 2(b). We use this property in Section 5 to let a CDN adapt to the unfolding FE so that it offers better protection to origin sites against overload.

3.3 Characterizing Clients

(a) Play-along	(b) Chile

Figure 3: Distribution of clients and clusters over time

Figure 3 shows how the number of distinct clients and client clusters accessing the site in 10-second intervals change over time. We see that the spikes in request volumes during an FE correspond closely with the spikes in the number of clients accessing the site. Thus, the number of clients in a flash event is commensurate with the request rate.

(a) Play-along	(b) Chile

Figure 4: Average number of requests per client in a second

To verify this claim more directly, Figure 4 shows how the average request rate generated by a single client changes during and outside the flash event. The figure does not show any clear increase in per client request rate during the flash event, at least for the two FEs we consider. The per-client rates rather drop and remain lower during the flash events than any other time slots. Thus, the increase in traffic volume occurs largely because of the increase in the number of clients.

The fairly stable per-client request rate can also be used to identify robots or proxies that automatically retrieve documents from the Web, which would behave more aggressively. We picked out several clients in this way from the Chile trace that turned out to be proxies that had sporadically sent tens of requests in a row.

Figure 3 also shows that the number of distinct clusters during the FE is much smaller than the number of distinct clients. This is because that cluster size distribution is very skewed --- few clusters account for a large fraction of hosts --- and therefore new clients come disproportionately from existing clusters, which is more apparent during the flash events. We will see that this is not true in the case of DoS, and is one of the strongest differentiator between FE and DoS that we were able to identify.

To better understand the dynamics of client clusters accessing each Web site, we divided the trace into before and during an FE and marked an incoming cluster during the FE as old if it did appear before it. We then calculate the percentage of old clusters as the ratio of old clusters over the number of distinct clusters during the FE. Surprisingly, we found that a large number of clusters active during an FE had also visited the sites before the event. The amount of the cluster overlap is 42.7% in the Play-along trace and 82.9% in the Chile trace. A possible explanation is that big clusters are responsible for most of requests to the Web site. With a high overall request rate, most of these big clusters would have at least one client that accessed the site already, so this cluster will not be new no matter how many more clients from it access the site.

Figure 5: Cluster contribution to requests

To verify this explanation, Figure 5 shows the cumulative distribution of the requests contributed by clusters that visited the site. It shows that 10% of clusters contributed a majority of requests---60% to the Play-along site and 90% to the Chile site. The distribution of requests across clusters is indeed highly skewed and reflects the skewed distribution of cluster sizes [20]. This suggests that client distribution in an FE follows user distribution across networks.

3.4 Characterizing File Reference

• 60% (61% and 82% for Play-along and Chile, respectively) of documents are accessed only during flash events. This observation forms the basis of our insight of Section 5 that some current CDNs may not provide the desired level of protection against FE. Indeed, most CDN caches will not have these documents at the beginning of the FE; hence most of the requests at the beginning of the event would miss in the caches and be forwarded to the origin server. Although subsequent requests would be served from the caches, a CDN with many caches can send a large number of initial misses to the origin server in a short time.
  

  Figure 6: Cumulative distribution of document requests

• To deduce the popularity of documents during flash events in our traces, we plot the cumulative fraction of the requests accounted for by distinct documents, most popular first, in Figure 6. For both traces, less than 10% of most popular documents account for more than 90% of requests. This is a promising result, since it indicates that, in principle, intelligent caching of these documents might be able to address the FE problem.

  (a) Play-along	(b) Chile

  Figure 7: Correlation between document popularity and the number of clusters accessing the document

  Requests for popular documents come from a large number of clusters as shown in Figure 7. This again has implications for current CDNs with a large number of servers because requests from a large number of different clusters are likely to arrive at a large number of different CDN servers, and these requests will therefore generate a large number of misses that will seep through to origin servers.

4. DoS Attacks

4.1 Password Cracking

Table 2: Basic statistics for esg and ol. Requests with the response code 401 Unauthorized are considered password-cracking attempts and listed in the 401 row

While attempts to crack passwords technically do not fall under the rubric of DoS attacks, our proposed strategy treats them similarly, namely, to identify and discard these requests as early as possible (see Section 4.3). Thus, it is appropriate to study these attacks together.

(a) The number of requests per second (esg)	(a) The number of requests per second (ol)

Figure 8: Request rates in password cracking DoS attacks to esg and ol

We analyzed two log files, esg and ol, which recorded more than 1 million requests within 60 days. Table 2 summarizes high-level statistics for those traces. As shown in Figures 8(a) and 8(b), both recorded several peaks throughout the period. On closer examination, it turned out that those were attempts to access resources that required a password authorization. Interestingly, each peak was made by the same IP address which sent from 600 to 1,000 HEAD requests in a minute in most cases. The pattern resulting from this activity is two-fold:

• The surge in request rate during the attack occurs due to the increase in a per-client request rate. Comparisons of Figures 8(a) and 9(a) for the esg site and Figures 8(b) and 9(b) for the ol site show that peaks in the request rates match those in the per-client average request rates. This is a deviation from the behavior we observed in flash events.

  (a) The number of requests per clients in a second (esg)	(a) The number of requests per clients in a second (ol)

  Figure 9:The average per-client request rates to esg and ol

• An overwhelming majority of client clusters that generated requests during the attack were new clusters not seen by the site before the attack. Only 0.6% of the clusters seen at the esg site during the attack were also seen before, and the percentage of these clusters drops to 0.1% for the ol site.

4.2 Web Server Disabling

Table 3: Basic statistics for the traces containing a Code Red attack. A request is classified as DoS if it requests the URL generated by an infected host when Code Red spreads

 bit.nl 

The Code Red worm utilizing a previously disclosed buffer overflow flaw [19] disables vulnerable Microsoft IIS Web servers by sending a very large Request-URI (beginning with default.ida?...). We analyze 5 traces where each log file recorded a number of accesses from infected computers. Table 3 lists basic statistics for each trace. The trace for bit.nl contained only accesses by infected computers so we could not compute cluster overlap for this site.

(a) The number of requests per second	(b) The number of clients vs. clusters in second
(c) The number of requests per client in a second	(d) Client contribution to requests

Figure 10: Characteristics of a DoS attack to bit.nl

Figure 10 plots characteristics of the bit.nl trace, the largest among the traces we considered. As Figure 10(a) shows, the attack started with few requests followed by a surge of requests later. However, one can observe from Figure 10(b) that, this surge occurred because of new clusters joining in the attack. This is different from FEs which did not exhibit any surge in new cluster arrivals (see Figure 3). Figure 10(c) confirms this observation by showing that the request rate per cluster did not change during the surge in the request rate. The per-client request rate is three for all cases except for bit.nl where the ratio is three or six.

With respect to client distribution, we found that DoS requests came from clients widely distributed across clusters in the Internet. In fact, each client came from a unique cluster in the fullnote and creighton traces. The percentage of clusters with just one DoS client was 72% for the bit.nl trace, 84% for the rellim trace and 79% for the spccctxus trace. The distribution of DoS attackers is more broad than in the case of flash events. Two corresponding figures, Figure 10(b) and Figure 3(a) highlight the difference: while Figure 3(a) shows many fewer clusters than clients, the cluster and client curves in Figure 10(b) almost match. It is also noticeable that the distribution of requests among clusters are more spread across a number of clusters as shown in Figure 10(d).

Interestingly, for traces that contained both DoS and non-DoS accesses, not a single DoS client had previously accessed the Web site. The percentage of overlap increases slightly for clusters, but still remains far below what we have seen for FEs. Among the traces where we could calculate the cluster overlap, its value was 0.6% in the creighton site, 0% in the fullnote site, 1.8% in the spccctxus site and 14.3% rellim site. With the exception of the rellim site, these overlaps are are similar to the password-cracking attacks.

4.3 Comparative Characterization and Server Guidelines

Table 4: Comparative characteristics of flash events vs. DoS attacks

An important difference is that the Web site sees a much larger number of previously seen clusters during a flash event than during a DoS attack. For the Play-along and Chile events, 42.7% and 82.9% of all clusters that sent requests during the flash event had also sent requests before the flash event. This contrasts with only 0.6-14% of such old clusters seen in the Code Red attack. We should note that clustering is essential to draw this distinction because the percentage of previously seen individual clients was small in all events. This difference can be intuitively explained by the fact that legitimate requests are more likely to come from clusters where at least some clients had been interested in the Web site even before the flash event, whereas DoS attacks rely on random machines that the attacker was able to hijack.

Another difference is that in DoS attacks that involve a large number of clients (such as the Code Red attack), distribution of clients among clusters is much more uniform than in a flash event. The highly skewed distribution of clients among clusters in a flash event reflects the highly skewed distribution of cluster sizes [20]. However, an attack does not reflect the cluster size distribution. While password cracking has too few clients to infer the distribution, server disabling exhibits a more even distribution of clients over clusters than FEs. The same aspect can be seen when considering the distribution of requests among clusters: legitimate requests are more concentrated in a few most active clusters while DoS requests are more scattered across numerous clusters.

A third difference is in the regularity of request rate from individual clients in a DoS attack. In the Code Red attack each cluster produces exactly either 3 or 6 requests per minute. In the password-cracking attack, a single client generates a huge number of requests during a short period of time. On the other hand, the per-client request rates get lower during an FE than usual, which suggests that the time gap between successive requests from a client is larger due to a increased server processing time and a possible transmission delay by network congestion.

A fourth difference is in the pattern of requested files. In a flash event, unlike that of DoS attacks, the requested file distribution is Zipf-like. In the attacks we considered, all malicious requests were to a small set of files - three files in the password-cracking attack and one file in the server-disabling attack.

4.4 Server Strategy

The server can exploit the differences that we have identified so far. Cluster overlap and per-client request rates are the two characteristics that offer especially strong differentiation between an FE and DoS and are also easy to monitor. Consequently, a server can adopt the following simple procedure for choosing requests to ignore:

• Monitor the clients that access the site and their request rate.

• Periodically perform network aware clustering over the client set accumulated over the past period without flash or DoS events. We will call these clusters ``old clusters''.

• When performance degrades to an unacceptable level, discard packets (including initial TCP SYNs) that come from clients that do not belong to old clusters as well as from those nonproxy clients whose request rate deviates significantly from average.

There are well-known techniques to use dynamic shared libraries that function as system call filters [18, 17] that can be used selectively when the load on the Web server exceeds a certain threshold. The system call filter can use a modified accept() which decides if a requesting IP remote address meets the criteria for being dropped.

However, it is impossible to anticipate and defeat all DoS attacks and this is not our goal. DoS attacks often flood the links and rarely make it to the application level but if they do, we believe we have a way of dealing with them. We also realize disclosing techniques help attackers in finding ways to circumvent it. We believe that increasing the cost to DoS attackers without a corresponding increase on the server side is a potential alternative. Since a Web site does not make available the list of IP addresses (and thus clusters) of its frequent visitors, the DoS attackers would potentially have to send requests from a very large number of clusters. Additionally, since many of the newer DoS attackers don't bother to spoof addresses [13], we believe that our technique becomes advantageous.

This strategy is unfortunately biased against clients in small clusters: these clusters are less likely to be seen by the site before the FE than large clusters. Thus, the site is more likely to discard requests by clients from small clusters. Still, the strategy is beneficial overall because it allows to service more legitimate requests under overload conditions.

5. Flash Crowds and CDNs

5.1 The Behavior of Current CDNs during a Flash Event

We perform our analysis by means of trace-driven simulation using the two traces described earlier, Play-along and Chile. We assume an infinite lifetime for cached objects. This makes our results conservative in terms of the request rate at the origin server because this request rate would only grow if objects were allowed to expire in the cache.

Since clusters group topologically close clients, we assume that CDN caches are assigned to clients at the granularity of clusters: all clients in the same cluster are assigned to the same cache. In our simulations, each client cluster is randomly assigned to one of the caches as soon as it generates the first request and uses that cache afterward. In this subsection, our focus is on cache misses that reach the origin server and hence a different cache assignment will not change our results in any noticeable way (Indeed, with infinite cached object lifetime and infinite capacity, each cache has a miss only once per object for the entire run. Because each cache is likely to see requests for most FE objects at the start of the flash event regardless of the cache assignment, cache assignment will not have much effect on the miss rate at the origin server). In Section 5.2.1, where we consider load balancing among caches, more intelligent cache assignment would further improve the performance of our scheme.

Table 5: Cache configurations for the Play-along trace

Table 6: Cache configurations for the Chile trace

Tables 5 and 6 show cache configurations considered for each trace. The first column indicates the number of caches from which the system selects caches to assign to clusters. The second column gives the number of caches that were actually assigned. The third column provides the average number of objects each cache contains at the end of the run and the last column shows the average number of clusters assigned to a cache. The last row in the tables corresponds to the case when each cluster has a designated cache.

Figures 11(a) and 11(b) show the peak request rate at the origin server during the run for different numbers of caches in the system. It is this characteristic that determines the ability of the Web site to withstand the flash event in the presence of a CDN. This request rate increases rapidly with the number of caches because each cache must obtain an object from the server when the cache receives the first request for the object. The peak occurs in the beginning of FE, when clients request objects which are not yet cached, and reaches about 450 requests per second for thousand caches in the case of Play-along. Depending on the complexity of the processing involved in servicing a request, this rate can easily pose a problem for a server. Also note that the FEs we studied were rather modest (due to the unavailability of larger logs), with peak request rates in single thousands. For more significant FEs, the peak request rate at the origin in the presence of a thousand caches can be expected to be higher. Thus, we can conclude that a CDN with a thousand caches might not be able to provide an absolute protection against an FE.

One could keep the request rate at the origin server manageable by limiting the number of caches but that increases the load on individual caches, as Figures 11(c) and 11(d) illustrate (Given the small scale of Play-along FE, the absolute levels of per-cache request rate these FEs generate would not overload modern caches: these rates only reach about 250 req/sec without load balancing and 65 req/sec with perfect load balancing across 100 caches. However, the tradeoff in question that our traces illustrate can cause cache overload in a higher-scale FE).

This situation calls for an approach that would lower the peak rate at both the origin server and at caches. One technique is cooperative caching, where caches forward missed requests to other caches rather than to the origin server (see, e.g., [9, 22]). This imposes an extra overhead for missed requests even when the origin server is not overloaded. A rough indication of this overhead is provided in [26], which reported that a Squid campus proxy cache took up to 150 ms to send cached responses to clients. (Although CDNs are more likely to use commercial cache products, we are not aware of similar data for commercial caches.) We therefore propose a different technique that allows a CDN to break the above tradeoff between the request rate at the cache and the origin server without adding the extra overhead of cache cooperation when it is not warranted.

(a) Peak request rate forwarded to the origin (Play-along)	(b) Peak request rate forwarded to the origin (Chile)
(c) Average number of requests to each cache (Play-along)	(d) Average number of requests to each cache (Chile)

Figure 11: Simulated behavior of current CDN during a flash event. We assume a CDN that deploys caches in some of the clusters.

5.2 Adaptive CDN: Improved Protection of Origin Server

Figure 12: Architecture of an adaptive CDN

Figure 12 illustrates our proposed adaptive CDN architecture. Like all existing CDNs we are aware of, our architecture uses its Domain Name Server (DNS) to distribute client requests among CDN caches. As in most existing CDN architectures, we assume that there is a control component which collects feedback from caches and updates corresponding entries in the CDN's DNS server (Although CDNs can have multiple DNS servers controlling their network, we use a single DNS server in the rest of the paper without loss of generality). Many commercial DNS implementations provide the functionality to to support frequent changes of an entry in a seamless way, although this functionality would have to be added to the prevalent open-source DNS implementation --- BIND [15]. Caches are organized into groups, with one cache within a group selected to be the primary cache for a given Web site. Presumably, groups comprise topologically close caches, such as those on a LAN in a data center. To spread the load, different caches in the group serve as primaries for different sites.

Normally, a CDN's DNS server distributes client requests only among primary caches for respective Web sites. When the load on a primary cache reaches a dangerous level, the primary requests the DNS to start distributing requests among other members of the group called delegates . However, when a delegate receives a missed request, it forwards the request not to the origin server but to the delegate's primary. In this way, the number of caches that can forward misses to the origin server remains limited to the primaries and at the same time the load is spread among both primaries and delegates. When the flash event ends, the primary sends another report to the DNS server asking it to stop using delegates for future requests. When delegates are engaged, the system behaves similar to cooperative caching. However, such behavior occurs only during a flash event, so that the cooperative caching overhead is not incurred during normal operation. We call this technique dynamic delegation .

Note that a delegate for one Web site could be a primary cache for another Web site. Thus, with an appropriate allocation of primaries among Web sites, an adaptive CDN utilizes all available caches even when no delegates are engaged. Also, for efficiency, it makes sense for a primary to allocate delegates that are topologically close to the primary, e.g., on the same local area network (LAN).

The simple idea behind dynamic delegation comes from the two factors. First, flash crowd traffic are generated for a small set of hot documents from many individual clients scattered over the Internet. Secondly, a hierarchical caching absorbs a number of requests at the lower level of caches and only missed requests are forwarded to the caches in the upper level. In the case of a perfect hierarchical caching where trees are balanced with one top level caches, we can reduce the number of requests to be served from an origin server to the number of hot documents. In our architecture, a number of cache trees are dynamically constructed per server basis assuming that not every server becomes busy at the same time and some caches are available and take a role as a delegate to the other busy server.

There are a variety of algorithms to implement dynamic delegation. As a first approach, we simulated an algorithm where a primary decides whether to add a delegate at the time of request processing. This involves executing a light-weight protocol similar to ICP [14] except that our protocol is performed among topologically close caches (on a LAN) and it does not wait for the slowest response from a group of caches as ICP does on a miss. Equally possible is an asynchronous approach where each primary periodically considers its load and the load of its delegates and decides if adding or releasing delegates is warranted. We leave exploring this and other possible dynamic delegation algorithms for future work.

Specifically, our current dynamic delegation algorithm is as follows. Each cache retains load information during last δ seconds. The other two parameters of the algorithm are high and low load watermarks, l_h and l_l. Initially every primary p is in underloaded state. When a request arrives at a primary p, the following cases are possible:

• If p is in underloaded state and the load on p has not exceeded l_h in the last δ seconds, p processes the request.

• If p's load has exceeded l_h in the past δ seconds, p queries all members of its group that are not its delegates already for their load and adds the first cache d that responds with load below l_l as a new delegate. To this end, p informs the DNS server to add d to the set of current delegates of p. In addition, p responds to the current request with HTTP redirect to new delegate d (The idea is that such a response would be generated entirely from main memory and take less processing than responding to the request in a normal way.) Finally, p enters the overloaded state. When there is no cache available to perform as a delegate, the request is dropped with a 503 Service Unavailable response.

• If p is in overloaded state and its load is between l_h and l_l, then p selects an existing delegate d to redirect the request to, queries the delegate for its load and redirects the request to d unless d's load exceeds l_h in which case p adds a new delegate and redirects the request to it.

• If p's load has not reached l_l in the past δ seconds, p processes the request, releases all delegates (that is, informs the DNS server to stop using delegates for future requests), and enters the underloaded state.

5.2.1 Simulation Results

Table 7: Parameter settings for the simulation.

Table 7 shows the simulation configuration for each trace. Load on caches is computed as requests per second averaged over two-second intervals.

Considering the request rate at the origin server, the adaptive CDN with n primary caches generates exactly the same request rate as that of the conventional CDN with n caches (see Figures 11(a) and 11(b)). However, the conventional CDN with n caches will place much higher load on individual caches. To precisely compare the load on individual caches placed by conventional and adaptive CDNs would require knowing the exact load balancing algorithm used by conventional CDNs---information that is not publicly available. The simulation shows that with 100 primary caches, the number of delegates used is 116 for the Play-along trace and 6 for the Chile trace. The number of primary caches that ever had a delegate is 65 for the Play-along, while only two primary caches reached l_h and actively engaged delegates throughout FE for the Chile trace. This suggests that request sources are more skewed to a few busy clusters for the Chile case. It is also noticeable that none of the caches including delegates experienced the load above l_h .

(a) Play-along (dynamic delegation)	(b) Chile (dynamic delegation)

Figure 13: Request rate at the origin server with adaptive CDN

Figure 13 shows the simulation results plotting the number of requests per second at the origin server when there are 100 primary caches. Comparing this with Figure 1, which shows the request rate at the origin server without a CDN, we see that peak request rates are reduced by a factor of 50 for the Play-along trace and 20 for the Chile trace. There are still peaks in the beginning of FE but they are as small as 150 requests per second for the Play-along trace and 30 requests per second for the Chile trace. This suggests that an adaptive CDN effectively lowers peak request rates of an origin server in the case of FE. At the same time, by using dynamic delegation, the adaptive CDN also ensures that load on each cache remains low and that proximity-based cache selection is not compromised.

6. Conclusions

In the second half of the paper we explore the role of CDNs that claim to offer protection against flash crowds. We show that some CDNs as they are currently structured may not offer maximum protection and we propose an alternative architecture that uses adaptive techniques. In addition, we present trace-driven simulation results evaluating our proposed adaptive CDN architecture. By contrasting against an idealized allocation mechanism we show that adaptive CDNs can help handle extreme situations such as flash crowds. As future work, we would like to obtain larger flash crowd logs from diverse places and experiment against instrumented servers. In our proposed adaptive CDNs, we plan to prepopulate caches and experiment with alternate dynamic delegation algorithms. The dynamic delegation algorithm could also use alternate redirection mechanisms.

7. Acknowledgments

8. References