Bruce M. Maggs
Abstract
This paper "peeks under the covers" at the subsystems that provide the basic functionality of a leading content delivery network. Based on our experiences in building one of the largest distributed systems in the world, we illustrate how sophisticated algorithmic research has been adapted to balance the load between and within server clusters, manage the caches on servers, select paths through an overlay routing network, and elect leaders in various contexts. In each instance, we first explain the theory underlying the algorithms, then introduce practical considerations not captured by the theoretical models, and finally describe what is implemented in practice. Through these examples, we highlight the role of algorithmic research in the design of complex networked systems. The paper also illustrates the close synergy that exists between research and industry where research ideas cross over into products and product requirements drive future research.
- iostat - linux man page. http://linux.die.net/man/1/iostat.Google Scholar
- Atila Abdulkadiroğlu, Parag A. Pathak, and Alvin E. Roth. The New York City high school match. American Economic Review, pages 364--367, 2005.Google ScholarCross Ref
- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. Google ScholarDigital Library
- Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Jevan Saks, and Ramesh K. Sitaraman. Algorithms for constructing overlay networks for live streaming. arXiv preprint arXiv:1109.4114, 2011.Google Scholar
- Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, and Ramesh K. Sitaraman. Designing overlay multicast networks for streaming. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 149--158. ACM, 2003. Google ScholarDigital Library
- Mourad Baıou and Michel Balinski. Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Discrete Applied Mathematics, 101(1):1--12, 2000. Google ScholarDigital Library
- Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970. Google ScholarDigital Library
- Andrei Broder and Michael Mitzenmacher. Network applications of Bloom filters: A survey. Internet Mathematics, 1(4):485--509, 2004.Google ScholarCross Ref
- Fangfei Cheng, Ramesh K. Sitaraman, and Marcelo Torres. End-user mapping: Next generation request routing for content delivery. In Proceedings of the 2015 ACM Conference on SIGCOMM, SIGCOMM '15, 2015.Google Scholar
- John Dilley, Bruce Maggs, Jay Parikh, Harald Prokop, Ramesh Sitaraman, and Bill Weihl. Globally distributed content delivery. Internet Computing, IEEE, 6(5):50--58, 2002. Google ScholarDigital Library
- Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. Summary cache: a scalable wide-area Web cache sharing protocol. IEEE/ACM Transactions on Networking (TON), 8(3):281--293, 2000. Google ScholarDigital Library
- David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, pages 9--15, 1962.Google Scholar
- Michel Goemans. Load balancing in content delivery networks. IMA Annual Program Year Workshop: Network Management and Design, April 2003.Google Scholar
- Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989. Google ScholarDigital Library
- Kazuo Iwama and Shuichi Miyazaki. A survey of the stable marriage problem and its variants. In Informatics Education and Research for Knowledge-Circulating Society, 2008. ICKS 2008. International Conference on, pages 131--136. IEEE, 2008. Google ScholarDigital Library
- D. Karger, A. Sherman, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi. Web caching with consistent hashing. Computer Networks, 31(11):1203--1213, 1999. Google ScholarDigital Library
- David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 654--663, May 1997. Google ScholarDigital Library
- David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. U.S. patent number 8,458,259: Method and apparatus for distributing requests among a plurality of resources, August 2002.Google Scholar
- Leonidas Kontothanassis, Ramesh Sitaraman, Joel Wein, Duke Hong, Robert Kleinberg, Brian Mancuso, David Shaw, and Daniel Stodolsky. A transport layer for live streaming in a content delivery network. Proceedings of the IEEE, 92(9):1408--1419, 2004.Google ScholarCross Ref
- Leslie Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, 2001.Google Scholar
- Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382--401, 1982. Google ScholarDigital Library
- Daniel M. Lewin. Consistent hashing and random trees: Algorithms for caching in distributed networks. Master's thesis, Massachusetts Institute of Technology, 1998.Google Scholar
- Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google ScholarDigital Library
- Erik Nygren, Ramesh K. Sitaraman, and Jennifer Sun. The Akamai network: a platform for high-performance internet applications. ACM SIGOPS Operating Systems Review, 44(3):2--19, 2010. Google ScholarDigital Library
- Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In Proceedings of the USENIX Annual Technical Conference, pages 305--320, 2014. Google ScholarDigital Library
- H. Rahul, M. Kasbekar, R. Sitaraman, and A. Berger. Towards realizing the performance and availability benefits of a global overlay network. In Proceedings of the Passive and Active Measurement Conference, 2006.Google Scholar
- Alvin E. Roth and Elliott Peranson. The redesign of the matching market for American physicians: Some engineering aspects of economic design. Technical report, National Bureau of Economic Research, 1999.Google Scholar
- Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Kidney exchange. The Quarterly Journal of Economics, pages 457--488, 2004.Google ScholarCross Ref
- Alex Rousskov and Duane Wessels. Cache digests. Computer Networks and ISDN Systems, 30(22):2155--2168, 1998. Google ScholarDigital Library
- Ramesh K. Sitaraman, Mangesh Kasbekar, Woody Lichtenstein, and Manish Jain. Overlay networks: An Akamai perspective. In Pathan, Sitaraman, and Robinson, editors, Advanced Content Delivery, Streaming, and Cloud Services. John Wiley & Sons, 2014.Google Scholar
- Donald E. Stokes. Pasteur's Quadrant: Basic Science and Technological Innovation. Brookings Institution Press, 1997.Google Scholar
Index Terms
- Algorithmic Nuggets in Content Delivery
Recommendations
End-User Mapping: Next Generation Request Routing for Content Delivery
SIGCOMM'15Content Delivery Networks (CDNs) deliver much of the world's web, video, and application content on the Internet today. A key component of a CDN is the mapping system that uses the DNS protocol to route each client's request to a ``proximal'' server ...
Survey on peer-assisted content delivery networks
Peer-assisted content delivery networks have recently emerged as an economically viable alternative to traditional content delivery approaches: the feasibility studies conducted for several large content providers suggested a remarkable potential of ...
Araneola: A scalable reliable multicast system for dynamic environments
This paper presents Araneola (Araneola means ''little spider'' in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully ...
Reviews
Soubhik Chakraborty
Those who design and operate content delivery networks look for speed, dependability, and consistency. Though several methods are required to achieve these objectives, this paper focuses on those that the authors find "technically interesting." To be more precise, the paper "walks through the steps" required to be completed from the moment a request for some content is made, through some browser, to its actual delivery. Being an empirical researcher in algorithm analysis myself, I fully agree with the authors that "algorithm design does not end when the last theorem is proved." In fact, theoretical results are often contradicted experimentally; for example, an asymptotic bound may not be realistic over a finite range over which a computer experiment can be conducted. The authors are quite right in assessing that speedy, scalable, and cost-effective implementations require practical considerations. They have accordingly focused on the translation of algorithms that are of recent demand in the industry. Some of the algorithms discussed in the paper, along with their empirical benefits, are global load balancing, the stable marriage problem, consistent hashing, bloom filters, and overlay routing. The paper contains useful material and will certainly draw interest among researchers working in the client/server environment. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments