Algorithmic Nuggets in Content Delivery
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
iostat - linux man page. http://linux.die.net/man/1/iostat. iostat - linux man page. http://linux.die.net/man/1/iostat.
Ravindra K. Ahuja , Thomas L. Magnanti , and James B. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , 1993 . Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
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 . 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.
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 . 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.
David Gale and Lloyd S . Shapley . College admissions and the stability of marriage. American Mathematical Monthly, pages 9--15, 1962. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, pages 9--15, 1962.
Michel Goemans . Load balancing in content delivery networks . IMA Annual Program Year Workshop: Network Management and Design , April 2003 . Michel Goemans. Load balancing in content delivery networks. IMA Annual Program Year Workshop: Network Management and Design, April 2003.
Dan Gusfield and Robert W. Irving . The Stable Marriage Problem: Structure and Algorithms . MIT Press , Cambridge, MA , 1989 . Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989.
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 . 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.
Leslie Lamport . Paxos made simple . ACM SIGACT News , 32 ( 4 ): 18 -- 25 , 2001 . Leslie Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, 2001.
Daniel M. Lewin . Consistent hashing and random trees: Algorithms for caching in distributed networks. Master's thesis , Massachusetts Institute of Technology , 1998 . Daniel M. Lewin. Consistent hashing and random trees: Algorithms for caching in distributed networks. Master's thesis, Massachusetts Institute of Technology, 1998.
Diego Ongaro and John Ousterhout . In search of an understandable consensus algorithm . In Proceedings of the USENIX Annual Technical Conference , pages 305 -- 320 , 2014 . Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In Proceedings of the USENIX Annual Technical Conference, pages 305--320, 2014.
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 . 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.
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 . 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.
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 . 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.
Donald E. Stokes . Pasteur's Quadrant: Basic Science and Technological Innovation . Brookings Institution Press , 1997 . Donald E. Stokes. Pasteur's Quadrant: Basic Science and Technological Innovation. Brookings Institution Press, 1997.