|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Acharya, S., Franklin, M. J., and Zdonik S. 1995. Dissemination-based data delivery using broadcast disks. IEEE Personal Communications 2, 6, 50--60.
|
| |
2
|
Ammar, M. H. and Wong, J. W. 1985. The design of teletext broadcast cycles. Performance Evaluation 5, 4, 235--242.
|
| |
3
|
Anily, S., Glass, C. A., and Hassin, R. 1998. The scheduling of maintenance service. Discrete Applied Mathematics 82, 27--42.
|
| |
4
|
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.
|
| |
5
|
Bar-Noy, A. and Ladner, R. E. 2003. Windows scheduling problems for broadcast systems. SIAM Journal on Computing (SICOMP) 32, 4, 1091--1113.
|
| |
6
|
Bar-Noy, A., Ladner, R. E., and Tamir, T. 2003. Scheduling techniques for media-on-demand. In Proceedings of the 14th SODA, 791--800.
|
| |
7
|
Bar-Noy, A., Ladner, R. E., and Tamir, T. 2007. Windows scheduling as a restricted bin-packing problem. ACM Trans. Algorithms 3, 3.
|
| |
8
|
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).
|
| |
9
|
Baruah, S. K. and Lin, S.-S. 1998. Pfair scheduling of generalized pinwheel task systems. IEEE Trans. Comp. 47, 812--816.
|
| |
10
|
Chan W. T. and Wong, P. W. H. 2004. On-line windows scheduling of temporary items. In Proceedings of the 15th ISAAC, 259--270.
|
| |
11
|
Chan M. Y. and Chin, F. 1992. General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Computers 41, 755--768.
|
| |
12
|
Chan M. Y. and Chin F. 1993. Schedulers for larger classes of pinwheel instances. Algorithmica, 9, 425--462.
|
| |
13
|
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.
|
| |
14
|
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.
|
| |
15
|
Holte, R., Rosier, L., Tulchinsky, I., and Varvel, D. 1992. Pinwheel scheduling with two distinct numbers. Theoretical Computer Science 100, 105--135.
|
| |
16
|
Hua K. A. and Sheu, S. 2000. An efficient periodic broadcast technique for digital video libraries. Multimedia Tools and Applications 10, 157--177.
|
| |
17
|
Juhn, L. and Tseng, L. 1997. Harmonic broadcasting for video-on-demand service. IEEE Trans. on Broadcasting 43, 3, 268--271.
|
| |
18
|
Liu C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61.
|
| |
19
|
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.
|
| |
20
|
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.
|
| |
21
|
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.
|
| |
22
|
Tijdeman, R. 1980. The chairman assignment problem. Discrete Mathematics 32, 323--330.
|
| |
23
|
Viswanathan, S. and Imielinski, T. 1996. Metropolitan area video-on-demand service using pyramid broadcasting. ACM Multimedia Systems Journal 4, 3, 197--208.
|
| |
24
|
Wei W. and Liu, C. 1983. On a periodic maintenance problem. Operations Res. Letters, 2, 90--93.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2