延遲敏感視訊伺服器之動態緩衝配置

Abstract

由於寬頻網路（broadband network）的出現，使得視訊點播（ Video-on-demand）服務不再是夢想而已並且也逐漸開始受到人們的重視 。視訊伺服器（Video Server）是視訊點播中是否能夠成功的關鍵，也由 於視訊資料是屬於對延遲敏感（delay-sensitive）的資料，如何將視訊 資料穩定送至訂戶的設備中是視訊伺服器中最重要的一部份。磁性媒體（ 如磁碟機）將資料讀出時，由於會受到轉速、搜尋、定位等機械動作的影 響，資料的輸出是間歇性的，如此會對延遲敏感的視訊資料產生間斷的影 響，因此伺服器必需利用緩衝記憶體的方法來避免造成視訊延遲。如何有 效率地使用這些緩衝記憶體，可以左右視訊伺服器的效能。 1994年 Banu (zden等人提出Phase-constrained Allocation（PCA）的資料安置 方式，將視訊資料以行為主（column-major）的方式在儲存媒體上安置成 矩陣型式，其主要目的在於利用循序讀取的方式來降低緩衝記憶體的使用 量，這種將視訊資料以矩陣方式安置的策略使得儲存媒體在不移動讀寫頭 的方式下，可以同時讀取不同時段的影片資料，因此磁頭以行的順序循序 讀取，每次回到第一行時便可增加新的視訊要求，這中間的間隔時間便為 batch interval，利用batching的特性，可以利用multicast的方式增加 同時可容納的最大訂戶端個數，同時這種方法也利用到循序讀取的特性， 使得它比其他的資料安置策略會有較低的磁頭搜尋時間。 在本文中， 我們將改進Phase-constrained Allocation的視訊資料安置方式使之成為 PCA-n的設計，由於在原來的方法中，並未實際去考慮到硬體設計上的配 合，因此若將這個方法直接應用在現今的硬體架構上，可能會有batch interval過長或是使用效能（utilization）不高的缺點，而在PCA-n的方 法之中，我們將不同的視訊資料以交替的方式安置在儲存媒體上同時服務 不同的訂戶端，除了原來PCA循序的優點外，更可以更進一步地增加儲存 媒體的使用效能，由於資料以交替的方式安置，因此緩衝計算的方式也與 原來的方法不同。我們並且在這個方法之上，利用動態的方式來配置緩衝 記憶體，使得使用此種架構的視訊伺服器可以更有效地管理及運用記憶體 ，然而一但以動態的方式來管理配置緩衝記憶體，我們便必需考慮到緩衝 大小增減時所造成的影響，本文也針對這個問題提出解決的方案。 緩 衝記憶體的運用分成兩種型態，一種是讀取緩衝（reading buffer），另 一種是歸位緩衝（repositioning buffer）。視訊緩衝主要用在避免當磁 頭讀取資料的間歇性所造成視訊資料輸出的延遲；歸位緩衝有兩個目的， 第一是用在當磁頭要自最後一行（column）歸位到第一行時所造成較長的 延遲時間，而讀取緩衝卻不足夠避免掉這段延遲，另一個目的是因為這些 緩衝的大小是依當時的需求去計算的，因此將會需要額外的時間來讓緩衝 的大小自小變大，歸位緩衝也將同時提供這段額外的需求。 讀取緩衝 的計算方式，主要依據儲存媒體的傳輸率（transfer rate）以及行與行 之間移動時的間格時間為計算依據；歸位緩衝依據最後一行至第一行的移 動時間以及視訊緩衝與歸位緩衝本身擴張時所造成的延遲做計算。由於每 次增加的視訊數無法事先知道，然而可增加的數量是有限的，因此緩衝擴 張的計算可以採用最差狀況（worst-case）演算法的模式找出最大值，也 可以依據所剩餘的緩衝容量，算出可以再增加的視訊數。 論文中也將 建立模擬來比較PCA與PCA-n的優劣，我們發現，PCA-n比PCA對儲存媒體的 運用（空間與輸出能力）以及緩衝記憶體的消耗上擁有更好的效能。 With the advent of the broadband Asynchronous Transfer Mode( ATM) network, Video-On-Demand(VOD) as a new type of network service is no longer a dream andis gaining lots of attention. Video server is the key to the success of VOD. Because video stream is delay-sensitive, how to transmit video data to the customer premise in real time is an important design issue of a video server. Retrieving video data from a magnetic storage, like disk, is affected by its mechanical movements, such as rotation, seek, and settlement, which will cause the output jittery. To overcome this problem, video server uses the random access memory(RAM) buffer to prevent the video stream from jittering. Therefore, to efficiently and effectively use the RAM buffer so as to support as many as on-line customers as possible is essential to the performance of a video server. In 1994, Banu (zden, et al., proposed a storage allocation scheme calledphase-constrained allocation(PCA). In this scheme, video data is placed inmajor-column as a matrix on storage. The benefit of PCA is that it reduces the usage of the RAM buffers by reading data sequentially. Most important of all,this placement strategy has the lowest seek time as comparing to other schemes.The major-column strategy also allows the storage to output data of differentparts of a video at the same time without moving the reading heads. Because video data are read sequentially in column-major, video server can accept new requests only when reading heads return to the first column. The interval between the reading of the first column and the last one is called the batch interval. With the batch interval, video server can support more than one customer by using the multicast technology. The major flaw of PCA is that it does not take into consideration the design of the existing storage. To implement PCA on the existing hardwares will cause both long batch interval andlow storage utilization. In this thesis, based on PCA, we suggest a new video data placement strategy, called PCA- n, where n is the number of different videos to be placed on the same storage. In PCA-n, videos are intermixed one after another on the storage. However, the intermission of videos requires a different RAM buffer allocation scheme. A dynamic buffer allocation scheme is proposed. Two types of buffers, reading and repositioning, are used. The reading buffer is used to prevent video stream from jittering during the reading period. The purposes of having the repositioning buffer are two folds. First, it is served as the backup to the stream buffer for the long delay incurred by moving the reading head from the last column to the first one. Second, it is used during the reading buffer expansion. Sometimes, the reading buffer needs to be expanded so as to accommodate more user requests. To fill those additional buffers, extra time is needed. In this case, the repositioning buffer is used to avoid jittering. The size of the reading buffer depends on the transfer rate and the latency time of the storage. The size of the repositioning buffer is determined both by the delay of moving the reading head from the last column to the first one and by the extra time needed to fill the additional buffers allocated during the expansion of the reading buffer. Because it is not possible to know in advance the number of video streams requested, the size of the expanded buffer is calculated by the worst-case algorithm. A simulation model is built to compare PCA-n to PCA. From the simulation results, we notice that PCA-n has a much better performance than PCA in terms of storage utilization (space and output capacity) and buffer consumption, while still keeping the same seek time as PCA.