Turning flash crowds into smart mobs with real-time stochastic detection and adaptive cooperative caching

ABSTRACT

The past decade has experienced a continued increase in the popular use of Web services. Unfortunately, the growth of Web services, coupled with their their role as a vital source of news and information has lead to many well published sources of stress that tend to cripple performance at both the client and the server side [1, 4]. Our work considers one such type of stress, called a flash crowd. A flash crowd arrives as a tidal wave, where the initial (and largest) spike in traffic generally occurs within the first few minutes. This gives client and servers only a few tens of seconds to adapt to the incoming traffic! In addition, flash crowds are infrequent and unpredictable. Hence, any solution deployed to mitigate flash crowd must consist of: (1) proactive and real-time mechanisms to detect the flash crowd while (or even before) it happens, and (2) an initiation of immediate action that can mask the effects of the stress.

A variety of system designs for content delivery have emerged over the past few years. Based on their underlying design methodologies, we classify these existing designs into <i>four</i> classes. We use this taxonomy to compare the effectiveness of the existing designs to mitigate flash crowds. The four classes are: (1) Single server solutions that target core server performance, such as SEDA [6]; (2) Server cooperation solutions that distribute content through cooperation amongst multiple servers, such as Coral [2]; (3) Server-Client solutions that require changes to the behavior of both the client and server side, such as Overhaul [5]; (4) Client cooperative caching solutions that utilize peer-to-peer routing substrates, such as Squirrel [3].

We follow a four-step approach in our study of flash crowds:

&bull; <b>Characteristics of flash crowds:</b> We study the properties of six real flash crowds based on traces collected from the respective websites.

&bull; <b>Real-time Flash Crowd Detector:</b> We present the design and implementation of a real-time stochastic detector of flash crowds, running at the server. A detector must continuously monitor visitor traffic and resource utilization, and be able to immediately and accurately flag a flash crowd in real-time. Additionally, the detector must run efficiently, without consuming significant computational and memory resources, especially during normal operations. <i>We find that our design enables us to detect a flash crowd while the event is happening</i>.

&bull; <b>Comparison of existing solutions:</b> We use flash crowd traces to compare the effectiveness of three of the four methodologies discussed above. We measure both network utilization of the server (a resource which directly affects the content provider's costs) and the quality of service as perceived by the clients (i.e., the turnaround latency for each request).

&bull; <b>Design of an Adaptive Cooperative Caching Solution:</b> We combine our real-time flash crowd detector at the server, with a cooperative caching scheme among clients, to design an adaptive cooperative caching solution for flash crowds. We compare the performance of this scheme with the existing methodologies. <i>Our results reveal that such an approach is extremely effective in turning a flash crowd into a smart mob.</i>

REFERENCES

• 1: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 2: M. J. Freedman, E. Freudenthal, and D. Mazières. Democratizing content publication with Coral. In Proc. of NSDI 2004, Mar. 2004.
• 3: Sitaram Iyer , Antony Rowstron , Peter Druschel, Squirrel: a decentralized peer-to-peer web cache, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571861]
• 4: Jaeyeon Jung , Balachander Krishnamurthy , Michael Rabinovich, Flash crowds and denial of service attacks: characterization and implications for CDNs and web sites, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511485]
• 5: J. A. Patel and I. Gupta. Overhaul: Extending HTTP to combat flash crowds. In Proc. of WCW 2004, Oct. 2004.
• 6: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada