Server-based smoothing of variable bit-rate streams

ABSTRACT

We introduce an algorithm that uses buffer space available at the server for smoothing disk transfers of variable bit-rate streams. Previous smoothing techniques prefetched stream data into the client buffer space, instead. However, emergence of personal computing devices with widely different hardware configurations means that we should not always assume abundance of resources at the client side. The new algorithm is shown to have optimal smoothing effect under the specified constraints. We incorporate it into a prototype server, and demonstrate significant increase in the number of streams concurrently supported at different system scales. We also extend our algorithm for striping variable bit-rate streams on heterogeneous disks. High bandwidth utilization is achieved across all the different disks, which leads to server throughput improved by several factors at high loads.

REFERENCES

• 1: Anastasiadis, S. V., Sevcik, K. C., and Stumm, M. Disk Striping Scalability in the Exedra Media Server. In ACM/SPIE Multimedia Computing and Networking Conj. (San Jose, CA, Jan. 2001), pp. 175-189.
• 2: Anastasiadis, S. V., Sevcik, K. C., and Stumm, M. Modular and Efficient Resource Management in the Exedra Media Server. In USENIX Symposium on Internet Technologies and Systems (San Francisco, CA, Mar. 2001). (to appear).
• 3: Biersack, E. W., and Hamdi, M. Cost-optimal Data Retrieval for Video Servers with Variable Bit Rate Video Streams. In Intl. Work. Network and Operating System Support .for Digital Audio and Video ICambridee. UK. Julv 1998), pp. 295-302.
• 4: Bolosky, W. J., Barrera, J. S., Draves, R. P., Fitzgerald, R. P., Gibson, G. A., Jones, M. B., Levi, S. P., Myhrvold, N. P., and Rashid, R. F. The Tiger Video Fileserver. In Intl. Work. on Network and Operating System Support for Digital Audio and Video (Zushi, Japan, Apr. 1996), pp. 97-104.
• 5: ChengFu Chou , Leana Golubchik , John C. S. Lui, A performance study of dynamic replication techniques in continuous media servers, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.202-203, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Asit Dan , Dinkar Sitaram, An online video placement policy based on bandwidth to space ratio (BSR), Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.376-385, May 22-25, 1995, San Jose, California, United States
• 7: Wu-chi Feng , Jennifer Rexford, A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.58, April 09-11, 1997
• 8: Ganger, G. R., Worthington, B. L., and Patt, Y. N. The DiskSim Simulation Environment: Version 2.0 Reference Manual. Tech. Rep. CSE-TR-358-98, Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan, Dec. 1999.
• 9: Rules of Thumb in Data Engineering, Proceedings of the 16th International Conference on Data Engineering, p.3, February 28-March 03, 2000
• 10: Gringeri, S., Shuaib, K., Egorov, R., Lewis, A., Khasnabish, B., and Basch, B. Traffic Shaping, Bandwidth Allocation, and Quality Assessment for MPEG Video Distribution over Broadband Networks. IEEE Network, 6 (Nov/Dec 1998), 94-107.
• 11: George McDaniel, IBM dictionary of computing, McGraw-Hill, Inc., New York, NY, 1994
• 12: Kim, I.-H., Kim, J.-W., Lee, S.-W., and Chung, K.-D. VBR Video Data Scheduling using Window-Based Prefetching. In IEEE Multimedia Computing and Systems (Florence, Italy, June 1999), pp. 159-164.
• 13: Lakshman, T. V., Ortega, A., and Reibman, A. R. VBR Video: Tradeoffs and Potentials. Proceedings of the IEEE 86, 5 (May 1998), 952-973 .
• 14: Dong-Young Lee , Heon Y. Yeom, Tip Prefetching: Dealing with the Bit Rate Variability of Video Streams, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.352, June 07-11, 1999
• 15: Dwight Makaroff , Gerald Neufeld , Norman Hutchinson, An evaluation of VBR disk admission algorithms for continuous media file servers, Proceedings of the fifth ACM international conference on Multimedia, p.143-154, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266354]
• 16: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 17: Marshall, A. W., and Olkin, I. Inequalities: Theory of Majorization and its Applications. Academic Press, New York, 1979.
• 18: McManus, J., and Ross, K. A Dynamic Programming Methodology for Managing Prerecorded VBR Sources in Packet-Switched Networks. Telecommunications Systems 9 (1998), 223-247.
• 19: Muirhead, R. F. Some methods applicable to identities and inequalities of symmetric algebraic functions of n letters. In Proc. Edinburgh Mathematical Society (1903), vol. 21, pp. 144-157.
• 20: Paek, S., and Chang, S.-F. Video Server Retrieval Scheduling for Variable Bit Rate Scalable Video. In IEEE Multimedia Computing and Systems (Hiroshima, Japan, June 1996), p p . 108-112 .
• 21: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: Reddy, A. L. N., and Wijayaratne, R. Techniques for improving the throughput of VBR streams. In ACM/SPIE Multimedia Computing and Networking (San Jose, CA, Jan. 1999), p p . 216-227.
• 23: Rexford, J., Sen, S., Dey, J., Feng, W., Kurose, J., Stankovic, J., and Towsley, D. Online Smoothing of Live, Variable-Bit-Rate Video. IEEE Trans. on Multimedia 2, 1 (Mar. ZOOO), 3 7 -4 8 .
• 24: On the Efficient Retrieval of VBR Video in a Multimedia Server, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.46, June 03-06, 1997 [doi>10.1109/MMCS.1997.609559]
• 25: James D. Salehi , Zhi-Li Zhang , James F. Kurose , Don Towsley, Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.222-231, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 26: Jose Renato Santos , Richard Muntz, Performance analysis of the RIO multimedia storage system with heterogeneous disk configurations, Proceedings of the sixth ACM international conference on Multimedia, p.303-308, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290786]
• 27: Sen, S., Rexford, J., and Towsley, D. Proxy Prefix Caching for Multimedia Streams. In IEEE INFOCOM (New York, NY, Mar. 1999), p p . 1310-1319.
• 28: Prashant J. Shenoy , Harrick M. Vin, Efficient striping techniques for variable bit rate continuous media file servers, Performance Evaluation, v.38 n.3-4, p.175-199, Dec. 1999 [doi>10.1016/S0166-5316(99)00044-9]
• 29: Weighted Striping in Multimedia Servers, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.102, June 03-06, 1997 [doi>10.1109/MMCS.1997.609580]
• 30: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt , John Wilkes, On-line extraction of SCSI disk drive parameters, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.146-156, May 15-19, 1995, Ottawa, Ontario, Canada
• 31: Wei Zhao , Satish K. Tripathi, Bandwidth-efficient continuous media streaming through optimal multiplexing, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.13-22, May 01-04, 1999, Atlanta, Georgia, United States
• 32: Roger Zimmermann , Shahram Ghandeharizadeh, Continuous display using heterogeneous disk-subsystems, Proceedings of the fifth ACM international conference on Multimedia, p.227-238, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266374]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Video analysis

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Data communications

General Terms:
Algorithms, Design, Experimentation