| 摘要: | 在本論文中我們針對熱門電影發展了幾個隨傳視訊『循環式廣播演算法』，來改善觀看者的等待時間的問題。首先，在本論文的第一部份，我們提出了一個新的廣播方法叫做“遞迴式頻寬切割法”來縮短新進入系統者的等待時間﹐且我們證明了這是目前為止我們可以發現到以每個區塊大小為一樣前提下最好的廣播方法，從實驗結果的圖上我們可以說，本方法在針對一部電影的分析上相當接近於理論上的最佳值。 在本論文的第二部份﹐我們提出了一個“借出與歸還”的方法來解決整個隨傳視訊系統間若有某幾部電影的在前一段時間單位沒有觀看者到達﹐而照成系統資源浪費的問題。當我們發現一些電影在前一個時間單位沒有觀看者要看這一部電影時﹐我們利用『一部電影借給多部電影』及『多部電影借給多部電影』兩個方法來解決這個問題。 『一部電影借給多部電影』這方法是一但系統發現前一個時間單位有一部電影沒有人進來觀看﹐就會把這個頻道借給其他幾部電影來減少進入系統的人的等待時間。而哪些電影是符合借這頻道的標準﹐其中一項最重要的準則就是﹐必須在一個單位時間內用完這個頻道。若這些電影利用這個頻道服務完前一個單位時間內進來的觀看者﹐結果其使用時間還沒有到達一個單位時間﹐我們可以再將這頻道借出給下一組符合這規定的一群電影。『多部電影借給多部電影』這方法是一但系統會將多部沒有人進來觀看的電影﹐的第一個頻道借給其他幾部電影來減少進入系統的人的等待時間。若這些電影利用這個頻道服務完前一個單位時間內進來的觀看者﹐結果其使用時間還沒有到達一個單位時間﹐我們一樣可以再將這頻道借出給下一組符合這規定的一群電影。 在本論文的最後一個部份﹐在這裡我們提出一個可以在原來電影仍有人在觀看但我們可以在“電影播放的中途”將該部電影的一個頻道給另外一部電影。對原來那部電影的新進觀看者來說其等待時間就會變成原來的兩倍，而拿到該頻道的電影其新進觀看者的等待時間就會變成原來的1/2。若將該部電影的兩個頻道給另外一部電影。則對原來那部電影的新進觀看者來說其等待時間就會變成原來的四倍，而拿到該頻道的電影其新進觀看者的等待時間就會變成原來的1/4。為了應用的方便以及證明這方法在做頻道轉換時已經在觀看電影的人都不會受到影響。 One way to broadcast a popular video is to use a number of dedicated channels,each responsible for broadcasting a portion of the video periodically in a pre-defined way.Thus the stress on channels can be alleviated, and new viewers need not have to wait long to start their playback. Many approaches falling in this category have been proposed.Two representative approaches are the Fast Broadcasting scheme and the PAGODA scheme, which can broadcast a video using k channels and have new-coming viewers wait no longer than D/2^k and D/5^k/2 time,respectively, where D is the length of the video. This thesis consists of three parts.In the first part of the dissertation, we focus on broadcasting schemes that partition the video into a number of fixe and schemes that are scheduled to broadcast on one of the channels periodically(such as FB and PAGODA). We propose two new schemes, called Recursive Frequency-Splitting (RFS) and m-RFS.RFS tries to arrange one segment in each iteration,and m-RFS tries to arrange $m$ segments in each iteration. These two schemes significantly improve over existing schemes in terms of viewe waiting time. Some lower bounds on the waiting time are also developed. In the second part of the dissertation, we consider a set of videos.We focuses on several representative schemes (such as FB, PAGODA, and RFS), which all share a FSFC property by repeatedly broadcasting first segment of the video on the first channel. Here, we propose a general Borrow-and-Return model, which can be immediately applied to any scheme owning the FSFC property, to reduce the viewers' waiting time without increasing the number of channels required. Intuitively, considering a group of videos, we lend the free time slots of videos without viewers to those videos with viewers to speedup the latter's transmission. Later on, some bandwidth may be vacated by the latter videos to benefit others' transmission. Effectiveness of this model is analyzed by applying it to the FB scheme. In the third part of the dissertation, we propose a novel seamless channel transition enhancement on top of the FB scheme to dynamically change the number of channels assigned to a video on-the-fly. Clients currently viewing this video will not experience any disruption because of the transition. A channel allocation scheme is also proposed based on the arrival rates of videos to minimize the average waiting experienced by all viewers. From the system manager's point of view, the enhancement will make the FB scheme more attractive. |
