| 摘要: | 隨著寬頻網路技術的進步與處理器及儲存空間的成長，隨選視訊 (video-on-demand) 服務越來越受使用者歡迎。然而，建立一個有成本效益、健全且擴充性強的隨選視訊串流系統仍然有許多挑戰。例如：目前流行的高畫質影片，其龐大的檔案容量與高速的頻寬需求，還有影片即時性的需求都會增加系統建置的成本。因此，許多基於影片區塊切割的廣播法 (segment based broadcasting schemes) 被提出來解決此問題。大多數這類演算法都注重在減少使用者的等待時間，而這些演算法通常都需要使用者端同時從所有的頻道接收影片區塊，造成使用者端需要大量的頻寬需求以及大量的暫存空間，因而讓使用者端的成本增加。 為了解決此問題，我們首先在此論文中提出一個基本的階梯和諧廣播法 (staircase-harmonic broadcasting scheme)，此演算法整合了階梯與和諧兩個演算法的特性達到較短使用者等待時間與較低使用者暫存空間的需求。接者，此論文更進一步提出調適性階梯和諧廣播法 (adaptive staircase-harmonic broadcasting scheme)，在保證某個使用者等待時間情形下，能夠有效率的協調利用伺服器頻寬、使用者暫存空間及使用者頻寬三項資源。當使用者端的暫存空間與頻寬不做額外限制時，此演算法只需使用者端有25%影片大小的暫存空間，並且使用者的等待時間只會比和諧廣播法較長一些，其中和諧廣播法已被證明為需求最短使用者的等待時間。跟快速廣播法 (fast broadcasting)、遞迴頻率切割廣播法 (recursive frequency splitting) 與和諧廣播法比較，此演算法能夠分別降低使用者暫存空間50%、33%與33%的需求量。當使用者端的暫存空間與頻寬有限制時，此演算法需求使用者的等待時間會比使用者為中心考量演算法 (client-centric approach)、貪婪節省磁碟廣播法 (greedy disk-conserving broadcasting) 與階梯廣播法還要短。例如：伺服器端的頻寬為十倍影片傳送速度、使用者頻寬需求為三倍影片傳送速度以及使用者暫存空間需求為25%影片大小，則所提演算法所需使用者的等待時間會分別比這些演算法低87%、87%與20%。 此論文還提出調適性有效率和諧廣播法 (adaptive efficient harmonic broadcasting scheme) 來說明如何調整和諧廣播法的影片區塊切割與分配，以做到符合使用者端頻寬與暫存空間的限制條件。此演算法能更有效率的協調利用伺服器頻寬、使用者暫存空間及使用者頻寬三項資源，並進一步地需求較短的使用者等待時間。由於使用者等待時間即為一個影片區塊的存取時間，如果一個影片能夠切割越多的區塊，則能夠有越短的使用者等待時間需求。當伺服器端的頻寬為十倍影片傳送速度、使用者頻寬需求為三倍影片傳送速度以及使用者暫存空間需求為25%影片大小，此演算法能夠切割成6485個區塊。相對的，調適性階梯和諧廣播法、限制使用者資源演算法 (limited client capability broadcasting)、使用者為中心考量演算法與貪婪節省磁碟廣播法只能切割成1151、364、169與161個區塊。由此可知，調適性有效率和諧廣播法能比這些演算法大大的提升效能。 調適性階梯和諧廣播法以及調適性有效率和諧廣播法的不同處為：調適性有效率和諧廣播法有較好的效能，但是調適性階梯和諧廣播法較為簡單容易計算，能夠快速的獲得影片所需要的廣播排程方式。 With the advancement of broadband networking technology, and the growth of processor speed and storage capacity, Video-on-Demand (VoD) service is getting increasingly popular among users. However, there are still many challenges towards building cost-effective, robust and scalable VoD streaming systems due to the huge size, high bandwidth and delay requirements for video streaming. Hence, segment based broadcasting schemes are proposed to solve the problems. Many significant broadcasting schemes are proposed to reduce the client waiting time. However, these schemes usually require clients to receive video segments altogether from all channels. This disregard not only needs a lot of client bandwidth, but also incurs more client buffer space. To escape from these constraints, in this dissertation, we first propose the basic staircase-harmonic broadcasting (SHB) scheme, which integrates harmonic broadcasting (HB) and staircase broadcasting (SB) schemes to obtain the strengths of small client waiting time and low client buffer space. Furthermore, this dissertation proposes adaptive staircase-harmonic broadcasting (ASHB) scheme, which goal is to guarantee a maximum client waiting time and effectively utilize other three resources: the number of dedicated server bandwidth, the client buffer space and the client bandwidth. When client buffer space and bandwidth are not constrained, the scheme requires a client to buffer only 25% of a playing video and the maximum waiting time is slightly higher than that of HB scheme, which provides a theoretical lower bound. In comparison with fast broadcasting (FB), recursive frequency splitting (RFS), and HB schemes, ASHB scheme saves the buffer space by 50%, 33%, and 33%. If client buffer space and bandwidth are constrained, ASHB scheme has the smallest client waiting time than client-centric approach (CCA), greedy disk-conserving broadcasting (GDB) and SB schemes. For example, at a server bandwidth of ten times the video playback rate, a client bandwidth of triple the playback rate, and a client buffer of 25% of the video size, ASHB has 87%, 87%, and 20% lower waiting time than CCA, GDB, and SB. Furthermore, this dissertation propose a broadcasting scheme, called adaptive efficient harmonic broadcasting (AEHB) scheme, to show how to adjust the division and assignment of segments for HB scheme to meet the constraints of client bandwidth and client buffer space. AEHB scheme can effectively offers a tradeoff among three resources: the number of dedicated server bandwidth, the client buffer space and the client bandwidth, and further gives a smaller maximum client waiting time. Since the maximum client waiting time is equal to the access time of a segment, the larger number of segments a video program can divide can lead to a smaller client waiting time. Given server bandwidth of ten times the video playback rate, client bandwidth of triple the video playback rate, and a client buffer 25% of the video size, AEHB scheme can divide the video program into 6485 segments, while ASHB, limited client capability broadcasting (LCCB), CCA and GDB schemes can divide the video program into 1151, 364, 169 and 161 segments respectively. AEHB scheme can great outperforms than other schemes. The difference between ASHB and AEHB schemes is: AEHB scheme has better performance than ASHB scheme, but ASHB scheme is much simpler to compute, so that it can easily get the broadcast schedule. |
