Advertisement

Harmonic Block Windows Scheduling Through Harmonic Windows Scheduling

  • Yi Sun
  • Tsunehiko Kameda
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3665)

Abstract

In Harmonic windows scheduling (HWS), a data file is divided into N pages and the pages are scheduled in c channels in such a way that each page i appears at least once in some channel in every window of size i. The optimal HWS problem aims to maximize N. Let κ be the largest integer satisfying H κ c, where H n is the n th harmonic number. Then κ is an upper bound on N, if the HWS framework is used. Thus an optimal HWS schedule wastes “bandwidth” at least cH κ . Harmonic block windows scheduling (HBWS) generalizes HWS by grouping b consecutive pages into a superpage. Let N be the total number of pages scheduled. The ratio N/b is directly proportional to the maximum initial waiting time in Media-on-Demand applications. We propose a method that starts with a HWS schedule and modifies it to generate a HBWS schedule that achieves a higher ratio N/b. For up to five channels, we demonstrate that we can always achieve N/b >κ. We also prove that as we increase b, N/b approaches the theoretical upper bound.

Keywords

Block Size Base Tree Round Robin Feasible Schedule Cyclic Schedule 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Bar-Noy, A., Ladner, R.E.: Windows scheduling problems for broadcast systems. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, pp. 433–442 (2002)Google Scholar
  2. 2.
    Bar-Noy, A., Nisgav, A., Patt-Shamir, B.: Nearly optimal perfectly-periodic schedules. In: Proc. 20th ACM Symp. on Principle of Distributed Computing, pp. 107–116 (2001)Google Scholar
  3. 3.
    Bar-Noy, A., Bhatia, R., Naor, J., Schieber, B.: Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research 27, 518–544 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Bar-Noy, A., Gosh, J., Ladner, R.E.: Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging. In: Proc. 15th ACM Symp. Parallel Algorithms and Atchitectures, pp. 164–173 (2003)Google Scholar
  5. 5.
    Bar-Noy, A., Ladner, R.E., Tamir, T.: Scheduling techniques for media-on-demand. In: Proc. ACM-SIAM Symp. on Discrete Algorithms, pp. 791–800 (2003)Google Scholar
  6. 6.
    Engebretsen, L., Sudan, M.: Harmonic broadcasting is optimal. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (2002)Google Scholar
  7. 7.
    Hua, K.A., Cai, Y., Sheu, S.: Patching: a multicast technique for true video-on-demand services. In: Proc. ACM Multimedia, pp. 191–200 (1998)Google Scholar
  8. 8.
    Hu, A., Nikolaidis, I., Van Beek, P.: On the design of efficient video-on-demand broadcast schedules. In: Proc. 7th Int’l. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 262–269 (1999)Google Scholar
  9. 9.
    Juhn, L., Tseng, L.: Harmonic broadcasting protocols for video-ondemand service. IEEE Trans. on Broadcasting 43, 268–271 (1997)CrossRefGoogle Scholar
  10. 10.
    Lin, Z.: Near-Optimal Heuristic Solutions to Truncated Harmonic Windows Scheduling and Harmonic Group Windows Scheduling. M.Sc. Thesis. School of Computing Science. Simon Fraser University (2004)Google Scholar
  11. 11.
    Ma, F.: Comparison of broadcasting schemes and stream-merging schemes for video-on-demand. CMPT415 Course Project Report (2003)Google Scholar
  12. 12.
    Pâris, J.-F.: A simple low-bandwidth broadcasting protocol for video-ondemand. In: Proc. 8th Int’l. Conf. on Computer Communications and Networks, pp. 118–123 (1999)Google Scholar
  13. 13.
    Pâris, J.-F., Carter, S.W., Long, D.D.E.: A low-bandwidth broadcasting protocol for video-on-demand. In: Proc. 7th Int’l. Conf. on Computer Communications and Networks, pp. 690–697 (1998)Google Scholar
  14. 14.
    Sun, Y., Kameda, T.: Harmonic block windows scheduling for video-on-demand. School of Computing Science, Simon Fraser University. Tech. Rept. 2005-05 (2005), ftp://fas.sfu.ca/pub/cs/TR/2005/CMPT2005-05.pdf (Submitted for publication)
  15. 15.
    Tseng, Y.-C., Yang, M.-H., Chang, C.-H.: A recursive frequency-splitting scheme for broadcasting hot videos in VOD service. IEEE Trans. on Communications 50, 1348–1355 (2002)CrossRefGoogle Scholar
  16. 16.
    Van Laarhoven, P.J.M., Aarts, E.H.L.: Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht (1987)zbMATHGoogle Scholar
  17. 17.
    Yan, E.M., Kameda, T.: An efficient VOD broadcasting scheme with user bandwidth limit. In: Proc. SPIE/ACM Conf. on Multimedia Computing and Networking, vol. 5019, pp. 200–208 (2003)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Yi Sun
    • 1
  • Tsunehiko Kameda
    • 1
  1. 1.School of Computing ScienceSimon Fraser UniversityBurnabyCanada

Personalised recommendations