A unified analysis of hot video schedulers

ABSTRACT

In this paper we consider the notion of relative competitive analysis, which is a simple generalization of the conventional competitive analysis and extra-resource analysis for on-line algorithms. We apply this analysis to study on-line schedulers for stream merging in two different video-on-demand (VOD) systems, which are based on two common approaches, namely, piggybacking and skimming. Our new analysis, in its simplest form, reveals a 3-competitive algorithm for stream merging based on skimming as well as piggybacking. This improves all previous results [4, 8]. We also show how to obtain guarantee on the performance improvement based on adding extra resources, and more interestingly, we provide a unified methodology to compare piggybacking and skimming. We believe that our result gives a clue to system designers for choosing desirable configurations.

REFERENCES

• 1: Charu Aggarwal , Joel Wolf , Philip S. Yu, On optimal piggyback merging policies for video-on-demand systems, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.200-209, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 2: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 3: A. Bar-Noy, J. Goshi, R. E. Ladner and K. Tam. Comparison of stream merging algorithms for media-on-demand. In Proc. Conf. on Multi. Comput. and Net. (MMCN), pages 115--129, 2002.
• 4: Amotz Bar-Noy , Richard E. Ladner, Competitive on-line stream merging algorithms for media-on-demand, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 07-09, 2001, Washington, D.C., United States
• 5: Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
• 6: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 7: M. Brehob, E. Torng, and P. Uthaisombut. Applying extra-resource analysis to load balancing. J. Scheduling, 3(5):273--288, 2000.
• 8: Wun-Tat Chan , Tak Wah Lam , Hing-Fung Ting , Wai-Ha Wong, An 5-competitive on-line scheduler for merging video streams, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.201, April 23-27, 2001
• 9: Wun-Tat Chan , Tak Wah Lam , Hing-Fung Ting , Wai-Ha Wong, Improved On-Line Stream Merging: From a Restricted to a General Setting, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.432-442, August 20-23, 2001
• 10: D. Eager, M. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. In Proc. 5th Intl. Workshop on Advances in Multi. Info. Sys., pages 80--87, Indian Wells, CA, 1999.
• 11: Derek Eager , Mary Vernon , John Zahorjan, Optimal and efficient merging schedules for video-on-demand servers, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.199-202, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319601]
• 12: D. Eager, M. Vernon, and J. Zahorjan. Bandwidth skimming: A technique for cost-effective video-on-demand. In Proc. Conf. on Multi. Comput. and Net. (MMCN), pages 206--215, 2000.
• 13: Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
• 14: Leana Golubchik , John C. S. Lui , Richard Muntz, Reducing I/O demand in video-on-demand storage servers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.25-36, May 15-19, 1995, Ottawa, Ontario, Canada
• 15: Leana Golubchik , John C. S. Lui , Richard R. Muntz, Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage servers, Multimedia Systems, v.4 n.3, p.140-155, June 1996 [doi>10.1007/s005300050019]
• 16: Bala Kalyanasundaram , Kirk Pruhs, Maximizing Job Completions Online, Proceedings of the 6th Annual European Symposium on Algorithms, p.235-246, August 24-26, 1998
• 17: Bala Kalyanasundaram , Kirk R. Pruhs, The Online Transportation Problem, SIAM Journal on Discrete Mathematics, v.13 n.3, p.370-383, May—June 2000 [doi>10.1137/S0895480198342310]
• 18: Tak Wah Lam , Kar Keung To, Trade-offs between speed and processor in hard-deadline scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 17-19, 1999, Baltimore, Maryland, United States
• 19: Siu-Wah Lau , John C. S. Lui , Leana Golubchik, Merging video streams in a multimedia storage server: complexity and heuristics, Multimedia Systems, v.6 n.1, p.29-42, Jan. 1998 [doi>10.1007/s005300050074]
• 20: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory