Amotz Bar-Noy
Richard E. Ladner
Abstract
Broadcasting is an efficient alternative to unicast for delivering popular on-demand media requests. Broadcasting schemes that are based on windows scheduling algorithms provide a way to satisfy all requests with both low bandwidth and low latency.
Consider a system of n pages that need to be scheduled (transmitted) on identical channels an infinite number of times. Time is slotted, and it takes one time slot to transmit each page. In the windows scheduling problem (WS) each page i, 1 ≤ i ≤ n, is associated with a request window wi. In a feasible schedule for WS, page i must be scheduled at least once in any window of wi time slots. The objective function is to minimize the number of channels required to schedule all the pages.
The main contribution of this paper is the design of a general buffer scheme for the windows scheduling problem such that any algorithm for WS follows this scheme. As a result, this scheme can serve as a tool to analyze and/or exhaust all possible WS-algorithms.
The buffer scheme is based on modelling the system as a nondeterministic finite state machine in which any directed cycle corresponds to a legal schedule and vice-versa. Since WS is NP-hard, we present some heuristics and pruning-rules for cycle detection that ensure reasonable cycle-search time.
By introducing various rules, the buffer scheme can be transformed into deterministic scheduling algorithms. We show that a simple page-selection rule for the buffer scheme provides an optimal schedule to WS for the case where all the wi's have divisible sizes, and other good schedules for some other general cases. By using an exhaustive-search, we prove impossibility results for other important instances.
We also show how to extend the buffer scheme to more generalized environments in which (i) pages are arriving and departing on-line, (ii) the window constraint has some jitter, and (iii) different pages might have different lengths.
- Acharya, S., Franklin, M. J., and Zdonik S. 1995. Dissemination-based data delivery using broadcast disks. IEEE Personal Communications 2, 6, 50--60.Google Scholar
Cross Ref
- Ammar, M. H. and Wong, J. W. 1985. The design of teletext broadcast cycles. Performance Evaluation 5, 4, 235--242.Google ScholarCross Ref
- Anily, S., Glass, C. A., and Hassin, R. 1998. The scheduling of maintenance service. Discrete Applied Mathematics 82, 27--42. Google ScholarDigital Library
- Bar-Noy, A., Bhatia, R., Naor, J., and Schieber, B. 2002. Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research 27, 3, 518--544.Google ScholarDigital Library
- Bar-Noy, A. and Ladner, R. E. 2003. Windows scheduling problems for broadcast systems. SIAM Journal on Computing (SICOMP) 32, 4, 1091--1113. Google ScholarDigital Library
- Bar-Noy, A., Ladner, R. E., and Tamir, T. 2003. Scheduling techniques for media-on-demand. In Proceedings of the 14th SODA, 791--800. Google ScholarDigital Library
- Bar-Noy, A., Ladner, R. E., and Tamir, T. 2007. Windows scheduling as a restricted bin-packing problem. ACM Trans. Algorithms 3, 3. Google ScholarDigital Library
- Bar-Noy, A., Ladner, R. E. Tamir, T., and VanDeGrift, T. 2005. Windows scheduling of arbitrary length jobs on parallel machines. In Proceedings of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA). Google ScholarDigital Library
- Baruah, S. K. and Lin, S.-S. 1998. Pfair scheduling of generalized pinwheel task systems. IEEE Trans. Comp. 47, 812--816. Google ScholarDigital Library
- Chan W. T. and Wong, P. W. H. 2004. On-line windows scheduling of temporary items. In Proceedings of the 15th ISAAC, 259--270. Google ScholarDigital Library
- Chan M. Y. and Chin, F. 1992. General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Computers 41, 755--768. Google ScholarDigital Library
- Chan M. Y. and Chin F. 1993. Schedulers for larger classes of pinwheel instances. Algorithmica, 9, 425--462.Google ScholarCross Ref
- Feinberg, E. A., Bender, M., Curry, M., Huang, D., Koutsoudis, T., and Bernstein, J. 2002. Sensor resource management for an airborne early warning radar. In Proceedings of SPIE the International Society of Optical Engineering, 145--156.Google Scholar
- Holte, R., Mok, A., Rosier, L., Tulchinsky, I., and Varvel, D. 1989. The pinwheel: A real-time scheduling problem. In Proceedings of the 22nd Hawaii International Conference on System Sciences, 693--702.Google Scholar
- Holte, R., Rosier, L., Tulchinsky, I., and Varvel, D. 1992. Pinwheel scheduling with two distinct numbers. Theoretical Computer Science 100, 105--135. Google ScholarDigital Library
- Hua K. A. and Sheu, S. 2000. An efficient periodic broadcast technique for digital video libraries. Multimedia Tools and Applications 10, 157--177. Google ScholarDigital Library
- Juhn, L. and Tseng, L. 1997. Harmonic broadcasting for video-on-demand service. IEEE Trans. on Broadcasting 43, 3, 268--271.Google ScholarCross Ref
- Liu C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61. Google ScholarDigital Library
- Pâris, J. F., Carter, S. W., and Long, D. D. E. 1999. A hybrid broadcasting protocol for video on demand. In Proceedings of the IS&T/SPIE Conference on Multimedia Computing and Networking, 317--326.Google Scholar
- Pâris, J. F. 2002. A broadcasting protocol for video-on-demand using optional partial preloading. In Proceedings of the 11th International Conference on Computing I, 319--329.Google Scholar
- Sgall, J., Shachnai, H., and Tamir, T. 2005. Fairness-free periodic scheduling with vacations. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), 592--603. Google ScholarDigital Library
- Tijdeman, R. 1980. The chairman assignment problem. Discrete Mathematics 32, 323--330.Google ScholarDigital Library
- Viswanathan, S. and Imielinski, T. 1996. Metropolitan area video-on-demand service using pyramid broadcasting. ACM Multimedia Systems Journal 4, 3, 197--208. Google ScholarDigital Library
- Wei W. and Liu, C. 1983. On a periodic maintenance problem. Operations Res. Letters, 2, 90--93.Google ScholarDigital Library
Index Terms
- A general buffer scheme for the windows scheduling problem
Recommendations
A general buffer scheme for the windows scheduling problem
WEA'05: Proceedings of the 4th international conference on Experimental and Efficient AlgorithmsBroadcasting is an efficient alternative to unicast for delivering popular on-demand media requests. Windows scheduling algorithms provide a way to satisfy all requests with both low bandwidth and low latency. Consider a system of n pages that need to ...
Windows scheduling of arbitrary length jobs on parallel machines
SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architecturesThe generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w1, l1),(w2, l 2),...,(wn, ln) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The ...
Windows scheduling of arbitrary-length jobs on multiple machines
The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I = ( w 1, 1),( w 2, 2), ,( w n , n ) of n pairs of positive integers that are associated with the jobs 1,2, , ...
Reviews
Jerzy W. Jaromczyk
A goal of window scheduling is to build a schedule-efficient under a number of different measures-to broadcast a set of pages of n different types, via a limited number of channels. The schedule is constrained by the requirement that for each of the types, the corresponding pages must appear in the schedule with some prescribed frequency-that is, within the given time windows. Although simple, if the frequencies or the number of channels are sufficiently large, schedules for tighter time windows are either hard to find or even nonexistent. This paper proposes a general framework, called the buffer scheme, that can be viewed as a nondeterministic finite automaton. In this buffer scheme model, all window-scheduling algorithms can be presented in a uniform way, by defining deterministic rules for selecting the next page to broadcast. In the language of the finite automaton model, such rules make the automaton deterministic and, thus, computationally efficient. In the experimental portion of the paper, numerous deterministic rules are checked for the quality of produced schedules and their number of channels. Although the buffer scheme is rather straightforward, it contributes a strong tool for analyzing new algorithms, constructing schedules, and analyzing their existence. For example, the problem of finding the schedule is reduced to detecting cycles in some directed graph with a finite number of nodes. Similarly, since the buffer scheme encapsulates all window scheduling algorithms, the exhaustive analysis allows for either finding the best schedules or proving that they do not exist for some time window sizes, for the given number of channels. As a final comment, although window scheduling is formulated in the language of broadcasting, it is a combinatorial problem. Keeping this abstraction clear throughout the paper might have resulted in a more succinct and possibly simpler presentation of its many interesting results. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments