臺灣博碩士論文加值系統

隨選視訊 (VOD: Video-On-Demand) 系統，即使用者可透過網路隨意選擇系統中自己想要的歌曲或電影，使用者只需坐在家中，便可享受現代化多媒體的享受。隨選視訊系統有多方面的應用，如互動式電視 (Interactive TV)、遠距教學 (Distance Learning)、電子購物 (Electronic Shopping)等。
VOD System 有兩大特性：(1) Server端利用許多高容量的裝置(如磁碟陣列)，儲存了大量的資訊，如影片、多媒體資料等；(2) 使用者透過通訊媒介(如網際網路)，向系統提出服務要求，與系統達成互動，完成要求。
目前的隨選視訊系統大多只考慮到提供使用者線上觀看的機制：使用者透過網路，藉著與系統的『互動』，享受系統所提供的資訊服務。但是這樣的作法，並不能讓系統發揮最大效能、將系統資源做最大利用。因為如果線上使用者不多，系統大部分的時間只是等待，什麼事都不做、浪費資源使用。因為這樣，所以考慮在系統額外加入『預約服務』功能，希望可以大幅增加系統的資源利用，減少系統空等的時間，進而讓系統能達到最大效益。
在本篇論文中，我們提出在隨選視訊系統上，提供『預約服務』的機制；更加以定義、評估在預約服務的排程中可能會遭遇到的問題及困難，也提出了幾種排程的方法。在『隨選視訊系統的預約排程問題』上，必須考慮到系統當時本身狀態(如系統本身服務上限、目前總工作量、隨時可能加進來的線上觀看使用者及系統目前資源使用等)、網路狀態改變(如服務頻寬限制、網路傳輸品質等)、已經被加入排程、等待服務的預約要求卻被取消、以及線上觀看機制與預約服務機制的資源分配等種種問題對預約要求排程的影響，及如果系統發生問題、執行環境突然發生改變時，對於目前系統內已經排定等待完成的預約要求，系統又該如何應對處理。

第一章 介紹 ------------------------------------------------------------------------ 6
第一節 隨選視訊系統 --------------------------------------------------------------- 6
第二節 預約服務 --------------------------------------------------------------------- 7
第三節 預約服務排程 --------------------------------------------------------------- 8
第四節 應用 --------------------------------------------------------------------------- 8
第二章 預約排程問題 ------------------------------------------------------------ 9
第一節 網路狀態改變 --------------------------------------------------------------- 9
第二節 取消預約要求 --------------------------------------------------------------- 9
第三節 線上觀看與預約服務的資源配置 --------------------------------------- 10
第四節 問題 ----------------------------------------------------------------------------10
第三章 系統模型與預約要求格式 ----------------------------------------------11
第一節 系統模型 ----------------------------------------------------------------------11
第二節 預約要求格式 ----------------------------------------------------------------12
第四章 方法評量標準 ------------------------------------------------------------ 15
第五章 預約排程考量 ------------------------------------------------------------ 17
第一節 設計考慮 --------------------------------------------------------------------- 17
第二節 排程基本單位 --------------------------------------------------------------- 18
第六章 預約排程問題 ------------------------------------------------------------ 19
第一節 k = 1 ---------------------------------------------------------------------------- 19
第二節 k > 1 ---------------------------------------------------------------------------- 21
1. Lightest Load First ----------------------------------------------------------- 22
2. Heaviest Load First ---------------------------------------------------------- 25
第七章 受害者選擇問題 --------------------------------------------------------- 28
第一節 Variant of LLF ---------------------------------------------------- 29
第二節 Variant of HLF ---------------------------------------------------- 31
第八章 結論及未來展望 --------------------------------------------------------- 35
Reference ------------------------------------------------------------------------------ 36

[1] Thomas M. Parks and Edward A. Lee, “Nonpreemptive real-time scheduling of Dataflow systems,” IEEE International Conference on Acoustics, Speech, and Signal Processing ─
May 1995.
[2] Vladda Limic*, “On the behavior of lifo preemptive resume queues in heavy traffic”, Elect. Comm. in Probab. 4 (1999) 13-27.
[3] Bj¨orn Andersson and Jan Jonsson, “Fixed-Priority Preemptive Multiprocessor Scheduling:
To Partition or not to Partition”, in Proceedings of the Int’l Conf. on Real-Time Computing Systems and Applications, December 12—14, 2000,
[4] Valery S. Gordon1, F. Werner2 and O.A. Yanushkevich1, “Single machine preemptive scheduling to minimize the weighted number of late jobs with deadline and nested release/due date intervals”, RAIRO Oper. Res. 35 (2001) 71-83
[5] Greg N. Frederickson, “A data structure for dynamically maintaining rooted trees”, Journal of Algorithms 24, 37-65 (1997)
[6] C.T.Ng, T.C.E. Cheng, A. Bachman, A. Janiak, “Three scheduling problems with deteriorating jobs to minimize the total completion time”, Information Processing Letters 81, 327-333, (2002)
[7] Gilad Koren and Dennis Shasha, “Dover: An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems”, SIAM J. Comput. Vol 24, No. 2, pp.318-339, April 1995
[8] Edwin Naroska, Uwe Schwiegelshohn, “On an on-line scheduling problem for parallel jobs”, Information Processing Letters 81, 297-304, (2002)
[9] N.C. Audsley, “On priority assignment in fixed priority scheduling”, Information Processing Letters 79, 39-44, (2001)
[10] Houssine Chetto and Maryline Chetto, “Some Results of the Earliest Deadline Scheduling Algorithm”, IEEE transaction on software engineering. Vol. 15. No. 10. October 1989
[11] Valery S. Gordon, F. Werner and O.A. Yanushkevich, “Single Machine preemptive scheduling to minimize the weighted number of late jobs with deadlines and nested release/due date intervals”, Rairo Oper. Res. 35, 71-83, (2001)
[12] Kevin Jeffay, Donald F. Stanat, Charles U. Martel, “Non-preemptive scheduling of periodic and sporadic tasks”, Proceedings of the 12th IEEE Real-Time Systems Symposium, San Antonio, Texas, December 1991, IEEE Computer Society Press, pp.129-139
[13] Yair Bartal, Setfano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, and Leen Stougie, “Multiprocessor scheduling with rejection”, SIAM J. Discrete Math. Vol.13, No. 1, pp64-78