Competitive analysis of most-request-first for scheduling broadcasts with start-up delay

ABSTRACT

In this paper, we give a tight and complete mathematical analysis of the Most-Request-First algorithm for scheduling on-demand broadcasts with start-up delay. The algorithm is natural and simple, yet its practical performance is surprisingly good. We derive tight upper and lower bounds on its competitive ratio under different system configurations. Our results reveal an interesting relationship between the start-up delay and the competitiveness of the algorithm.

REFERENCES

• [1]: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• [2]: Ruchi Agrawal , Panos K. Chrysanthis, Efficient Data Dissemination to Mobile Clients in E-Commerce Applications, Proceedings of the Third International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems (WECWIS '01), p.58, June 21-22, 2001
• [3]: D. Aksoy, M. Franklin, Scheduling for large-scale on-demand data broadcasting, in: Proceedings of the Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, 1998, pp. 651¿659
• [4]: Antone F. Alber, Videotex/teletext principles & practices, McGraw-Hill, Inc., New York, NY, 1985
• [5]: Amotz Bar-Noy , Juan A. Garay , Amir Herzberg, Sharing video on demand, Discrete Applied Mathematics, v.129 n.1, p.3-30, 15 June 2003 [doi>10.1016/S0166-218X(02)00231-7]
• [6]: Bar-Noy, A., Goshi, J. and Ladner, R.E., Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging. Journal of Discrete Algorithms. v4 i1. 72-105.
• [7]: Sanjoy K. Baruah , Jayant R. Haritsa, Scheduling for Overload in Real-Time Systems, IEEE Transactions on Computers, v.46 n.9, p.1034-1039, September 1997 [doi>10.1109/12.620484]
• [8]: W.T. Chan, T.W. Lam, H.F. Ting, W.H. Wong, New results on on-demand broadcasting with deadline via job scheduling with cancellation, in: Proceedings of the 10th Annual International Conference on Computing and Combinatorics, 2004, pp. 210¿218
• [9]: A. Dan , D. Sitaram , P. Shahabuddin, Scheduling policies for an on-demand video server with batching, Proceedings of the second ACM international conference on Multimedia, p.15-23, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192614]
• [10]: H.D. Dykeman, M. Ammar, J.W. Wong, Scheduling algorithms for videotex systems under broadcast delivery, in: Proceedings of International Conference on Communications, 1986, pp. 1847¿1851
• [11]: Jeff Edmonds , Kirk Pruhs, A maiden analysis of longest wait first, ACM Transactions on Algorithms (TALG), v.1 n.1, p.14-32, July 2005 [doi>10.1145/1077464.1077467]
• [12]: A. Feldmann, B. Maggs, J. Sgall, D.D. Sleator, A. Tomkins, Competitive analysis of call admission algorithms that allow delay, Technical Report CMU-CS-95-102, School of Computer Science, Carnegie Mellon University, 1995
• [13]: Sally A. Goldman , Jyoti Parwatikar , Subhash Suri, Online scheduling with hard deadlines, Journal of Algorithms, v.34 n.2, p.370-389, Feb. 2000 [doi>10.1006/jagm.1999.1060]
• [14]: Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Journal of Scheduling, v.6 n.2, p.183-211, March/April 2003 [doi>10.1023/A:1022994010777]
• [15]: A.T. Hawkins, W. Mao, On multi-channel data broadcast scheduling, in: Proceedings of the 2nd Workshop on Intelligent Multimedia Computing and Networking, 2002, pp. 915¿918
• [16]: Regant Y.S. Hung, H.F. Ting, Design and analysis of online batching systems, in: Proceedings of the 7th Latin American Theoretical Informatics Symposium, 2006, pp. 605¿616
• [17]: Shu Jiang , Nitin H. Vaidya, Scheduling data broadcast to “impatient” users, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.52-59, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313300.313385]
• [18]: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• [19]: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• [20]: B. Kalyanasundaram, M. Velauthapillai, On-demand broadcasting under deadline, in: Proceedings of the 11th Annual European Symposium on Algorithms, 2003, pp. 313¿324
• [21]: Jae-Hoon Kim , Kyung-Yong Chwa, Scheduling broadcasts with deadlines, Theoretical Computer Science, v.325 n.3, p.479-488, 6 October 2004 [doi>10.1016/j.tcs.2004.02.047]
• [22]: W. Mao, Competitive Analysis of On-line Algorithms for On-demand Data Broadcast Scheduling, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.292, December 07-07, 2000
• [23]: Navrati Saxena , Kalyan Basu , Sajal K. Das , Christina M. Pinotti, A Dynamic Hybrid Scheduling Algorithm with Clients' Departure for Impatient Clients in Heterogeneous Environments, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.241.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.20]
• [24]: Mohamed A. Sharaf , Panos K. Chrysanthis, On-demand data broadcasting for mobile decision making, Mobile Networks and Applications, v.9 n.6, p.703-714, December 2004 [doi>10.1145/1035715.1035730]
• [25]: H.F. Ting, A near optimal scheduler for on-demand data broadcasts, in: Proceedings of the 6th International Conference on Algorithms and Complexity, 2006, pp. 163¿174
• [26].: Broadcast delivery. Proceedings of the IEEE. v76 i12. 1566-1577.
• [27]: Ping Xuan , Subhabrata Sen , Oscar Gonzalez , Jesus Fernandez , Krithi Ramamritham, Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.38, June 09-11, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
Competitive analysis, Lower bounds, Non-preemptive scheduling, On-demand data broadcasts, Upper bounds