Optimal delivery of multi-media content over networks

ABSTRACT

In this paper, we describe scalable optimal methods for delivering archived and live multi-media content from servers to multi-media client players endowed with substantial RAM or disk-based buffers. These methods result from the application of linearoptimization theory (linear programming) to the problem of how best to modulate the flow rate of constant-bit-rate (CBR) content for all sessions linking a server to its clients, in which session flow rates are subject to upper and lower bound constraints, and aggregate flow cannot exceed a specified maximum. An efficient O(n) algorithm to maximize aggregate flow is described. We propose a tunable minimum constraint on session flows that is shown to result in a rapid and sustained accumulation of reserve content within a player's buffer. An associated Call Admission Control (CAC) algorithm is also described. The benefits of the methods described include improved server efficiency, enhanced end-user experience (QOS), cost effective end to-end content delivery, directly from origin servers to clients without need of intervening edge-caching technology.

REFERENCES

• 1: Kang Li, Jonathan Walpole, Dylan McNamee, Calton Pu, and David Steere. A Rate-Matching Packet Scheduler for Real-Rate Applications, in proceedings of Multimedia Computing and Networking 200 1, San Jose, California, January, 2001
• 2: Sassan Pejhan , Ti-Hao Chiang , Ya-Qin Zhang, Dynamic frame rate control for video streams, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.141-144, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319481]
• 3: RealNetworks Corp. Surestream Whitepaper http:llwww.realnetworks.com/devzoneldocumentationl wp_surestream.html?src=noref,rnhmpg_O2070 I ,rnhmt n,nosrc
• 4: RealNetworks Corp. RealSystem Proxy White Paper http://docs.real.com/docs/m/RealSystem_ProxyS.pdf?s rc=r-realnetworks,proxy-0 1100 1
• 5: G. Ghinea , J. P. Thomas , R. S. Fish, Multimedia, network protocols and users—bridging the gap, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.473-476, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319689]
• 6: M. Hofmann, E. Ng, K. Guo, S. Paul, and H. Zhang. Caching techniques for streaming multimedia over the internet. Technical Report BLO 1134-990409-04TM, Bell Laboratories, April 1999.
• 7: Matthew Andrews , Kameshwar Munagala, Online Algorithms for Caching Multimedia Streams, Proceedings of the 8th Annual European Symposium on Algorithms, p.64-75, September 05-08, 2000
• 8: S. Sen, J. Rexford, J. Dey, J. Kurose, and D. Towsley, Online Smoothing of Variable-Bit-Rate Streaming Video, Tech. Rep. 98-75, Department of Computer Science, University of Massachusetts Amherst, 1998
• 9: J. Rexford, S. Sen, and A. Basso, A Smoothing Proxy Service for Variable Bit-rate Streaming Video, in Proc. IEEE Global Internet Symposium, Rio de Janeiro, Brazil, Dec. 1999
• 10: James D. Salehi , Shi-Li Zhang , Jim Kurose , Don Towsley, Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.397-410, Aug. 1998 [doi>10.1109/90.720873]
• 11: R. Lang et al. US patents 4,963,995 (issued 10/16/90), 5,057,932 (i s s u e d 10/15/91), 5,164,839 (issued 1 l/17/92) 5,995,705 (issued 1 l/30/99)
• 12: N. Polish. US patent 5,963,202 (issued 10/5/99)
• 13: L.Gradshteyn, L. Ryzhik. Table of Integrals Series and Products, Academic Press, 2000.
• 14: Approach Inc. Report at URL http://burst.burst.comlf/ar>proach.pdf

INDEX TERMS

General Terms:
Algorithms, Design, Economics, Experimentation, Performance, Theory

Keywords:
CAC, CBR, QOS, VBR bandwidth smoothing, ad insertion, edge-caching, linear programming, live events, optimization, video-on-Demand