Scheduling policies for an on-demand video server with batching

ABSTRACT

In an on-demand video server environment, clients make requests for movies to a centralized video server. Due to the stringent response time requirements, continuous delivery of a video stream to the client has to be guaranteed by reserving sufficient resources required to deliver a stream. Hence there is a hard limit on the number of streams that can be simultaneously delivered by a server. The server can satisfy multiple requests for the same movie using a single disk I/O stream by sending the same data pages to multiple clients (using the multicast facility if present in the system). This can be achieved by batching requests for the same movie that arrive within a short duration of time. In this paper, we consider various policies for selecting the movie to be multicast. The choice of a policy depends very much on the customer waiting time tolerance before reneging. We show that an FCFS policy that schedules the movie with the longest outstanding request can perform better than the MQL policy that chooses the movie with the maximum number of outstanding requests. Additionally, if the user behavior can be influenced by guaranteeing maximum waiting time then it may be beneficial to pre-allocate a fixed number of streams for popular movies. Finally, we demonstrate using empirical distribution for movie requests, that a substantial reduction (of the order of 60%) in required server capacity can be achieved by batching.

REFERENCES

• 1: David P. Anderson, Metascheduling for continuous media, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.226-252, Aug. 1993 [doi>10.1145/152864.152866]
• 2: Dan. A., and D. Sitaram. "Buffer Management Policy for an On- Demand Video Server". IBM Reset~rc'h Report, RC 19347. Yorktown Heights, NY, 1993.
• 3: Dan. A., D. Sitaram. and P. Shahabu(~in. "Scheduling Policies for an On-Demand Video Server with Balching". IBM Research Report. RC 19381, Yorktown Heights, NY, 1993.
• 4: Dan. A., D. Sitaram and P. Shahabuddin, "Scheduling Policies with Grouping for providing VCR Control Functions in a Multi-media Server", U.S. Docket No Y0993.030, 1994 ~patent pending).
• 5: Dan, A., P. Shahabuddin. D. Sitaram and D. Towsley. "Channel Allocation under Balching and VCR Control in Movie-On-Demand Servers". IBM Resear~'h Report RC19588. Yorktown HeighLs. NY. 1994.
• 6: Dan. A.. M. Kienzl~ and D. Sitaram, "Dynamic Segment Replication Policy for Load-Balancing in Video-on-Demand Servers". IBM Research Report. RC 19589. Yorklown Heights. NY. 1994.
• 7: Dykcman, H. D,, M. H. Ammar, and J. W. Wong. "Scheduling Algorithms lot Videotex Systems under Broadcast Delivery". Proc ICC'86. 1986, pp. 1847-1851.
• 8: Edward A. Fox, The coming revolution in interactive digital video, Communications of the ACM, v.32 n.7, p.794-801, July 1989 [doi>10.1145/65445.65446]
• 9: Gelman, A. D. and S. Hallin. "Analysis of Resource Sharing in Informarion Providing Services." Proc. IEEE Global Telecommunicatiotls Cot?~erence atut Exhibition } 990, Vol. I, 1990.
• 10: Kleinrock. L.. Queuemg Systems. Volume 1.' Theory. John Wiley and Sons - New York. Chichester. Brisbane. Toronto, 1975, pp 105.
• 11: Jean-Yves Le Boudec, The Asynchronous Transfer Mode: a tutorial, Computer Networks and ISDN Systems, v.24 n.4, p.279-309, May 15, 1992 [doi>10.1016/0169-7552(92)90114-6]
• 12: Marchok. D. J., C. Rohrs. and M. R. Schafer, "Multicasting in a Growable Packet tATM) Switch," IEEE INbDCOM, lC)gl, pp. 850- 858.
• 13: Peha, J. M., and E A, Tobagi, "Evaluating Scheduling Algorithms for Traffic with Heterogeneous Performance Objectives." IEEE GLOBE- COM, 1990, pp. 21-27.
• 14: Rangan, P. V., H. M. Vin, and S. Ramanathan, "Designing an On-Demand Multimedia Service," IEEE Communication Magazine, Vol. 30, July 1992, pp. 56-65.
• 15: W. D. Sincoskie, System architecture for a large scale video on demand service, Computer Networks and ISDN Systems, v.22 n.2, p.155-162, Sept. 1991 [doi>10.1016/0169-7552(91)90007-Y]
• 16: Stankovic, J.. K. Ramamritham. and S. Chang, "Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-Time Systems,'' IEEE TrcaLsactions on Computers, Vol. C-,M, No. 12, December 1985, pp. 1130-1143.
• 17: Electronic' Engineering Times. March 15, 1993. pp 72.
• 18: Video Store Magazine. Dec. 13, 1992.
• 19: J. W. Wong , M. H. Ammar, Analysis of broadcast delivery in a videotex system, IEEE Transactions on Computers, v.34 n.9, p.863-866, Sept. 1985 [doi>10.1109/TC.1985.1676645]
• 20: Zhao. Z. X., S, S. Panwar, and D. Towsley. "Queueing Pefformax:e with Impatient Customers." IEEE INFOCOM, 1991, pp. 4(X~409.

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
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Design, Human Factors, Performance