臺灣博碩士論文加值系統

隨選視訊系統提供使用者選擇影片的服務，並提供如錄放影機的互動功能。如何有效的利用系統資源提供更多客戶享受視訊服務，是架構隨選視訊系統的重要課題之一。批次服務便是屬於這樣的一種技術，它使用資源共享的觀念，利用一份系統的資源來同時服務多個使用者，達到資源的有效應用。但批次服務產生的等待時間將導至使用者取消其視訊要求，而影響到整個系統的服務品質。一個有效的批次排程方法是批次系統設計的核心技術。在這篇論文中，我們提出一個新的批次排程方法來提高服務品質。我們將重點集中在使用者離去的行為模式，先服務可能離去機率較高的視訊要求，以減少批次系統所造成的負面影響。我們也研討及設計使用者互動下有效分享資源的方法並降低緩衝區的需求。根據模擬實驗的分析證明我們所提的方法，確實能有效的利用系統資源，提昇系統服務的效能。

A Video-on-Demand (VOD) system provides the ultimate flexibility in video services by allowing users to select video programs, at any time, and to perform VCR-like user interactions. To design a VOD server, one approach is to have a dedicated video stream for each customer. This is expensive, especially when multiple identical video streams are sent to multiple customers accessing the same video program. Batching of video requests is often used to reduce I/O demand and to improve throughput. The basic idea is to delay the user requests for a certain amount of time so that more requests for the same video arriving during the current batching interval may be serviced using the same stream. As the delay grows larger, viewers might leave the system without being served. In this thesis, we consider the user reneging behavior models and propose the Maximum Expected Loss (MEL) batching policy. We then improve the MEL policy by combining the Maximum Factored Queue Length (MFQ) scheme to become a better policy. It is referred to as the MEL*MFQ policy and performs as an excellent choice batching scheme with respect to all of the performance measures. To support user interactions under batching, we design a Split and Merge protocol with adaptive piggybacking (SAM_AP) to reduce the cost of additional buffer. The small interaction delay constraint of user interactions is a critical issue. In order to reduce user interaction delay, in our SAM_AP protocol, we maintain a small pool of reserved streams for the purpose of immediately providing user interaction requests. A simulation is developed in this thesis and simulation results show that our proposed batching system does utilize system resources effectively and improvement the overall system performance.

摘要…………………………………………………………………………………….i
Abstract…………………………………….………………………………………….ii
Acknowledgement…………………………………………………………………….iv
Table of Contents………………………………………………………………..……..v
List of Figures……………………………………………………………………..…vii
List of Tables………………………………………………………………………...viii
Chapter 1 Introduction……………………………………………………………...…1
1.1 Motivation……………………………………………………………………1
1.2 Organization………………………………………………………………….6
Chapter 2 Background…………………………………………………………………7
2.1 Performance Metrics…………………………………………………………7
2.2 Related Works of Batching Policies……………………………….…………9
2.2.1 FCFS……………………………………………………………………9
2.2.2 MQL…………………………………………………………………..10
2.2.3 FCFS-n………………………………………………………………..10
2.2.4 MFQ…………………………………………………………………..11
2.2.5 IML……………………………………………………………………14
2.3 Related Works of User Interaction Support………………………………...16
2.3.1 The Look-Ahead Scheduling Scheme………………………………..16
2.3.2 Channel Allocation under Batching and VCR Control………………18
2.3.3 The Split and Merge Protocol……………………………….………..19
Chapter 3 Proposed Batching System………………………………………………..22
3.1 Proposed Batching Policy…………………………………………………..22
3.2 User Interaction Support……………………………………………………26
3.2.1 Adaptive Piggybacking……………………………………………….26
3.2.2 Proposed SAM_AP Protocol………………………………………….28
Chapter 4 Simulation Study………………………………………………………….31
4.1 Simulation Model………………………………………………….………..31
4.1.1 Customer Arrival Behavior Model……………………………………31
4.1.2 Customer Reneging Behavior Model…………………………………33
4.1.3 Default Values of Simulation Parameters……………………..………35
4.2 Simulation Results……………………………………………………..……36
4.2.1 Effect of User Reneging Model………………………………….……36
4.2.2 Effect of Service Requirement………………………………………..40
4.2.3 Effect of Mean Time to Renege..……………………………………..42
4.2.4 Effect of System Capacity………………………………………….…44
4.2.5 Effect of Video Access Skew…………………………………………46
4.2.6 Effect of VOD without Guaranteed Service...………………………..48
4.2.7 Effect of User Interactions……………………………………………50
Chapter 5 Conclusions and Future Works……………………………………………53

[1] A. Dan, D. Sitaram, and P. Shahabuddin, "Dynamic batching policies for an on-demand video server," Multimedia Systems, Vol. 4, No. 1, pp. 112-121, 1996.
[2] C. C. Aggarwal, J. L. Wolf, and P. S. Yu, "On optimal batching policies for video-on-demand storage servers", Proc. of IEEE Multimedia'96, pp. 253-258, 1996.
[3] H. Shachnai, and P. S. Yu, " The Role of Wait Tolerance in Effective Batching: A Paradigm for Multimedia Scheduling Systems", Research Report RC 20038, IBM TJ Watson Research Center, Yorktown Heights, NY, 1995.
[4] L. Golubchik, C. S. Lui, and R. R. Muntz, "Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage server," Multimedia Systems, Vol. 4, No. 2, pp. 140-155, 1996.
[5] S. Berson, R. Muntz, S. Ghandeharizadeh, and X. Ju, "Staggered striping in multimedia information systems", Proc. of ACM SIGMOD, pp. 79-90, 1994.
[6] P. S. Yu and J. L. Wolf and H. Shachnai, "Design and analysis of a look-ahead scheduling scheme to support pause-resume for video-on-demand application", ACM Multimedia Systems, Vol. 3, No. 4, pp.137-150, 1995.
[7] A. Dan, P. Shahabuddin, D. Sitaram, D. Towsley, "Channel allocation underbatching and VCR control in video-on-demand servers", Journal of Parallel and Distributed Computing, Vol. 30, No. 2, pp. 168-179, 1995.
[8] W. J. Liao and V. O. K. Li, "The Split and Merge (SAM) Protocol for Interactive Video-on-Demand Systems", in Proc. IEEE INFOCOM'97, Kobe, Japan, pp. 1351-1358, 1997.
[9] Robert O. Banker et al., "Method of providing video on demand with VCR like functions", U.S. Patent 5357276, 1994.
[10] K. C. Almeroth and M. H. Ammar, "The use of multicast delivery to provide a scalable and interactive video-on-demand service", IEEE Journal on Selected Areas in Communications, Vol. 14, No. 6, pp. 1110-1122, 1996.
[11] M. Kamath, D. Towsley and K. Ramamritham, "Buffer management for continuous media sharing in multimedia database systems", Technical Report 94-11, Univ. of Massachusetts, 1994.
[12] P. Chen, E. Lee, G. Gibson, R. Katz and D. Patterson, "RAID: High Performance, Reliable Secondary Storage", ACM Computing Surveys, Vol. 26, No. 2, pp. 145-185, 1994.
[13] A. Mourad, "Issues in the design of a storage server for video-on-demand," Multimedia Systems, Vol. 4, No. 2, pp. 70-86, 1996.
[14] M. S.Chen, D. D. Kandlur, and P. S. Yu, "Storage and retrieval methods to support fully interactive playout in a disk-array-based video server," Multimedia Systems, Vol. 3, No.3, pp. 126-135, 1995.
[15] T. G. Kwon, Y. Choi, S. Lee, "Disk placement for arbitrary-rate playback in an interactive video server," Multimedia Systems, Vol. 5, No. 1, pp. 271-281, 1997.
[16] D. E. Knuth, "The art of computer programming", Reading, MA:addison-Wesley, Vol. 3, pp.397, 1937.
[17] Video Store Magazine. Dec. 13, 1992.
[18] P. S. Yu, M. S. Chen and D. D. Kandlur, "Grouped Sweeping Scheduling for DASD-based multimedia storage management," Multimedia Systems, Vol. 1, No. 3, pp. 99-109, 1993.
[19] R. T. Ng and J. Yang, "An analysis of buffer sharing and prefetching techniques for multimedia systems," Multimedia Systems, Vol. 4, No. 2, pp. 53-69, 1996.
[20] C. H. Chen, Storage management of a KTV video server, Master thesis, Institute of Computer Science and Information Engineering, NCTU, June 1996.
[21] B. Ozden, R. Rastogi, A. Silberschatz, "On the design of a low cost video-on-demand storage system," Multimedia systems, Vol. 4, No. 1, pp. 40-54, 1996.
[22] B. Ozden, R. Rastogi and A. Siberschatz. "Disk striping in video server environments," Data Engineering, Vol 18. No. 4, pp. 4-16, 1995.
[23] M. Y. Hsu, A Simulation Model for Hierarchical Storage Systems of Video Servers, Master Thesis, Institute of Computer Science and Information Engineering, NCTU, 1996.
[24] A. Dan, M. Kienzle, and D. Sitaram, "A dynamic policy of segment replication for load-balancing in video-on-demand servers," Multimedia Systems, Vol. 3, No. 3, pp. 93-103, 1995.
[25] D. Rotem and J. L. Zhao, "Buffer management for video database systems," IEEE Trans. On Knowledge and Data Engineering, Vol. 5, No. 4, pp. 439-448, 1995.
[26] Muntz, R. R. and Lui, C. S. "Performance Analysis of Disk Arrays Under Failure," Proc. of the 16th Conference on Very Large Data Bases, pp. 162-173, 1990.
[27] Little and D. Venkatesh. "Popularity-based Assignment of Movies to Storage Devices in a Video-on-Demand System," Multimedia Systems, Vol. 2, No. 6, pp. 280-287, 1995.
[28] J. L. Wolf, P.S. Yu, and H. Shachnai, "DASD Dancing: a disk load balancing optimization scheme for video-on-demand computer systems", Proc. of the ACM SIGMETRICS'95, pp. 157-166, 1995.
[29] Y. Wang, C. L. Lie, H. C. Du, and J. Hsieh, "Efficient video file allocation schemes for video-on-demand services", ACM Multimedia Systems, Vol. 5, No 4, pp.283-296, 1997.
[30] Y. H. Chang et al., "An open-systems approach to video on demand", IEEE Communications Magazine, Vol.32, No. 5, pp. 68-80, 1994.