Scheduling techniques for media-on-demand

ABSTRACT

Broadcasting popular media to clients is the ultimate scalable solution for media-on-demand. Recently, it was shown that if clients can receive data at a rate faster than what they need for playback and if they can store later parts of the media in their buffers, then much higher scalability may be obtained. In the paper we focus on scheduling problems arising from these new systems for media-on-demand.For given amount of bandwidth, we improve the guaranteed start-up delay time for an uninterrupted playback. We achieve our results by introducing two techniques. In the first, the media is arranged on the channels such that clients gain from buffering later parts of the transmission before the actual start of the playback. In the second, segments of different media may be mixed together on the same channel. We introduce a simple class of recursive round-robin scheduling algorithms that implement our techniques.Our results improve the best known asymptotic results. Moreover, our scheduling algorithms outperform known results for "practical" values for number of media and number of broadcasting channels. For some specific small values, we present hand designed solutions that are better than those achieved by our algorithms.

REFERENCES

• 1: Amotz Bar-Noy , Richard E. Ladner, Windows scheduling problems for broadcast systems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.433-442, January 06-08, 2002, San Francisco, California
• 2: Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly-periodic schedules, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.107-116, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383998]
• 3: Steven W. Carter , Darrell D. E. Long , Jehan-François Paris, Video-on-demand broadcasting protocols, Multimedia communications: directions and innovations, Academic Press, Inc., Orlando, FL, 2001
• 4: Asit Dan , Dinkar Sitaram , Perwez Shahabuddin, Dynamic batching policies for an on-demand video server, Multimedia Systems, v.4 n.3, p.112-121, June 1996 [doi>10.1007/s005300050016 ]
• 5: Lars Engebretsen , Madhu Sudan, Harmonic broadcasting is optimal, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.431-432, January 06-08, 2002, San Francisco, California
• 6: Exploiting Client Bandwidth for More Efficient Video Broadcast, Proceedings of the International Conference on Computer Communications and Networks, p.848, October 12-15, 1998
• 7: L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Trans. on Broadcasting, Vol. 43, No. 3, 268--271, 1997.
• 8: L. Juhn and L. Tseng. Fast data broadcasting and receiving scheme for popular video service. IEEE Trans. on Broadcasting, Vol. 44(1), 100--105, 1998.
• 9: J. Pâris. A simple low-bandwidth broadcasting protocol for video-on-demand. In Proc. off the 8-th International Conference on Computer Communications and Networks (IC3N), 118--123, 1999.
• 10: A Low Bandwidth Broadcasting Protocol for Video on Demand, Proceedings of the International Conference on Computer Communications and Networks, p.690, October 12-15, 1998
• 11: J. Pâis, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proc. off the IS&T/SPIE Conference on Multimedia Computing and Networking (MMCN), 317--326, 1999.
• 12: J. Pâris and D. D. E. Long. Limiting the receiving bandwidth of broadcasting protocols for video-on-demand. In Proc. Euromedia Conf., 107--111, 2000.
• 13: S. Viswanathan , T. Imielinski, Metropolitan area video-on-demand service using pyramid broadcasting, Multimedia Systems, v.4 n.4, p.197-208, Aug. 1996 [doi>10.1007/s005300050023 ]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Electronic data interchange (EDI)

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Economics, Theory