A statistical admission control algorithm for multimedia servers

ABSTRACT

A large-scale multimedia server, in practice, has to service a large number of clients simultaneously. Given the real-time requirements of each client and the fixed data transfer bandwidth of disks, a multimedia server must employ admission control algorithms to decide whether a new client can be admitted for service without violating the requirements of the clients already being serviced. In this paper, we present an admission control algorithm for multimedia servers which: (1) exploits the variation in access times of media blocks from disk as well as the variation in client load induced by variable rate compression schemes, and (2) provides statistical service guarantees to each client. The effectiveness of the algorithm is demonstrated through trace-driven simulations.

REFERENCES

• 1: David P. Anderson , Yoshitomo Osawa , Ramesh Govindan, A file system for continuous media, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.311-337, Nov. 1992 [doi>10.1145/138873.138875]
• 2: Jim Gemmell , Stavros Christodoulakis, Principles of delay-sensitive multimedia data storage retrieval, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.51-90, Jan. 1992 [doi>10.1145/128756.128758]
• 3: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 4: Gene Miller , Greg Baber , Mark Gilliland, News on-demand for multimedia networks, Proceedings of the first ACM international conference on Multimedia, p.383-392, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.168432]
• 5: A. Papoulis. Probability, Random Variables, and Stochastic Processes. McCaaw Hill, 1991.
• 6: A. L. Narasimha Reddy , Jim Wyllie, Disk scheduling in a multimedia I/O system, Proceedings of the first ACM international conference on Multimedia, p.225-233, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166292]
• 7: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
• 8: Fouad A. Tobagi , Joseph Pang , Randall Baird , Mark Gang, Streaming RAID: a disk array management system for video files, Proceedings of the first ACM international conference on Multimedia, p.393-400, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.168435]
• 9: Harrick M. Vin, Alok Goyal, Anshuman Goyal, and Pawan Goyal. An Observation-Based Approach For Designing Multimedia Servers. In Proceedings of the IEEE international Conference on Multimedia Computing and Systems, Boston, MA, pages 234-243, May 1994.
• 10: Harrick M. Vin and P. Venkat Rangan. Designing a Multi-User HDTV Storage Server. IEEE Journal on Selected Areas in Communications, 11(1):153-164, January 1993.
• 11: Philip S. Yu, Mon-Song Chen, Dilip D. Kandlur: Design and Analysis of a Grouped Sweeping Scheme for Multimedia Storage Management, Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, p.44-55, November 12-13, 1992

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Video (e.g., tape, disk, DVI)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Performance