Algorithmic Nuggets in Content Delivery

Computer Communication Review - Tập 45 Số 3 - Trang 52-66 - 2015
Bruce M. Maggs1, Ramesh K. Sitaraman2
1Duke University, Durham, NC, USA
2University of Massachusetts, Amherst, MA USA

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.

10.1257/000282805774670167

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.

10.1145/777412.777437

10.1016/S0166-218X(99)00203-6

10.1145/362686.362692

10.1080/15427951.2004.10129096

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.

10.1109/MIC.2002.1036038

10.1109/90.851975

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.

10.1109/ICKS.2008.7

10.1016/S1389-1286(99)00055-9

10.1145/258533.258660

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.

10.1109/JPROC.2004.832956

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.

10.1145/357172.357176

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.

10.5555/1076315

10.1145/1842733.1842736

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.

10.1162/0033553041382157

10.1016/S0169-7552(98)00251-7

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.

Thông tin
Thông tin xuất bản

Computer Communication Review

Tập 45 Số 3

52-66

Thông tin tác giả