The effectiveness of request redirection on CDN robustness

Abstract

It is becoming increasingly common to construct network services using redundant resources geographically distributed across the Internet. Content Distribution Networks are a prime example. Such systems distribute client requests to an appropriate server based on a variety of factors---e.g., server load, network proximity, cache locality--in an effort to reduce response time and increase the system capacity under load. This paper explores the design space of strategies employed to redirect requests, and defines a class of new algorithms that carefully balance load, locality, and proximity. We use large-scale detailed simulations to evaluate the various strategies. These simulations clearly demonstrate the effectiveness of our new algorithms, which yield a 60--91% improvement in system capacity when compared with the best published CDN technology, yet user-perceived response latency remains low and the system scales well with the number of servers.

References

1. Akamai. Akamai content delivery network. http://www.akamai.com.
2. D. Andresen, T. Yang, V. Holmedahl, and O. lbarra. Sweb: Towards a scalable world wide web server on multicomputers, 1996.
3. A. Barbir, B. Cain, F. Douglis, M. Green, M. Hofmann, R. Nair, D. Potter, and O. Spatscheck. Known CN Request-Routing Mechanisms, Feb. 2002. Work in Progress, draft-ietf-cdi-known-request-routing-00.txt.
4. T. Brisco. DNS support for load balancing. Request for Comments 1794, Rutgers University, New Brunswick, New Jersey, Apr. 1995.
5. P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS), Monterey, CA, Dec. 1997.
6. V. Cardellini, M. Colajanni, and P. Yu. Geographic load balancing for scalable distributed web systems. In Proceedings of the International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), Aug. 2000.
7. A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrell. A hierarchical internet object cache. In USENIX Annual Technical Conference, pages 153--164, 1996.
8. J. Cohen, N. Phadnis, V. Valloppillil, and K. W. Ross. Cache array routing protocol v 1.1. http://ds 1.internic.net/internet-drafts/draft-vinod-carp-v1-01.txt, September 1997.
9. M. Colajanni, P. S. Yu, and V. Cardellini. Dynamic load balancing in geographically distributed heterogeneous web servers. In International Conference on Distributed Computing Systems, pages 295--302, 1998.
10. M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in web servers. In USENIX Symposium on Internet Technologies and Systems, 1999.
11. M. Crovella, M. Harchol-Balter, and C. D. Murta. Task assignment in a distributed system: Improving performance by unbalancing load (extended abstract). In Measurement and Modeling of Computer Systems, pages 268--269, 1998.
12. O. Damani, P. Y. Chung, Y. Huang, C. M. R. Kintala, and Y. M. Wang. ONE-IP: Techniques for hosting a service on a cluster of machines. In Proceedings of the Sixth International World-Wide Web Conference, 1997.
13. Digital Island. http://www.digitalisland.com.
14. Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. H. Ammar. A novel server selection technique for improving the response time of a replicated service. In INFOCOM (2), pages 783--791, 1998.
15. L. Garber. Technology news: Denial-of-service attacks rip the Internet. Computer, 33(4):12--17, Apr. 2000.
16. J. D. Guyton and M. E Schwartz. Locating nearby copies of replicated internet servers. In SIGCOMM, pages 288--298, 1995.
17. G. Hunt, E. Nahum, and J. Tracey. Enabling content-based load distribution for scalable services. Technical report, IBM T. J. Watson Research Center, May 1997.
18. K. L. Johnson, J. E Cam M. S. Day, and M. F. Kaashoek. The measured performance of content distribution networks. In Proceedings of The 5th International Web Caching and Content Delivery Workshop, Lisbon, Portugal, May 2000.
19. D. Karger, A. Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi. Web caching with consistent hashing. In Proceedings of the Eighth International World-Wide Web Conference, 1999.
20. D. R. Karger, E. Lehman, F. T. Leighton, R. Panigrahy, M. S. Levine, and D. Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In ACM Symposium on Theory of Computing, pages 654--663, 1997.
21. Mirror Image. http://www.mirror-image.com.
22. D. Moore, G. Voelker, and S. Savage. Inferring internet denial of service activity. In Proceedings of 2001 USENIX Security Symposium, Aug. 2001.
23. NS. (Network Simulator). http://www.isi.edu/nsnarn/ns/.
24. V. Pal, E Druschel, and W. Zwaenepoel. Flash: An efficient and portable web server. In USEN1X Annual Technical Conference, June 1999.
25. V. S. Pai, M. Aron, G. Banga, M. Svendsen, R Druschel, W. Zwaenepoel, and E. M. Nahum. Locality-aware request distribution in cluster-based network servers. In Architectural Support for Prograraraing Languages and Operating Systems, pages 205--216, 1998.
26. S. Ratnasamy, E Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proceedings of ACM SIGCOMM'01, Aug. 2001.
27. A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329--350, Nov. 2001.
28. S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical network support for IP traceback. In Proceedings of the 2000 ACM SIGCOMM Conference, Aug. 2000.
29. A.C. Snoeren, C. Partridge, L. A. Sanchez, C. E. Jones, F. Tchakountio, S. T. Kent, and W. T. Strayer. Hash-based ip traceback. In Proceedings of ACM SIGCOMM'01, Aug. 2001.
30. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of ACM SIGCOMM'01, Aug. 2001.
31. D. G. Thaler and C. V. Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 6(1):1--14, Feb. 1998.
32. A. Wolman, G. M. Voelker, N. Sharma, N. Cardwell, A. R. Karlin, and H. M. Levy. On the scale and performance of cooperative web proxy caching. In Symposium on Operating Systems Principles, pages 16--31, 1999.
33. L. Zhang, S. Floyd, and V. Jacobson. Adaptive web caching. In Proceedings of the 1997 NLANR Web Cache Workshop, June 1997.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation evaluation

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Operational analysis

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

    • Software system structures

      • Distributed systems organizing principles

      • Software architectures

        • Simulator / interpreter