摘 要： 本文研究了流媒體傳輸領(lǐng)域的相關(guān)技術(shù)，并對其進行總結(jié)分類。對服務(wù)器流調(diào)度技術(shù)、代理緩存技術(shù)、節(jié)目替換算法等進行了詳細介紹。
關(guān)鍵詞： 流媒體傳輸 服務(wù)器流調(diào)度 代理緩存機制
近年來互聯(lián)網(wǎng)上基于視頻、音頻的流媒體應(yīng)用呈飛速發(fā)展的趨勢。流媒體有著廣闊的市場前景[1]。然而流媒體應(yīng)用不同于Web上普通的文本、圖片的瀏覽，有其獨特的一面。由于視頻文件巨大，持續(xù)時間長，且要求具有實時性，所以傳送視頻時需要很大的帶寬。
阻礙流媒體發(fā)展的因素主要是帶寬問題，包括服務(wù)器磁盤帶寬和網(wǎng)絡(luò)帶寬，二者中相對較小者決定了系統(tǒng)服務(wù)用戶的數(shù)目。流媒體傳輸技術(shù)面臨如此多的挑戰(zhàn)，從而吸引許多學(xué)者在這方面進行研究，并取得了一定的成果。本文針對這些技術(shù)進行了總結(jié)。
對流媒體傳輸技術(shù)的研究主要涉及：(1)服務(wù)器流調(diào)度技術(shù)。(2)代理緩存技術(shù)。(3)節(jié)目替換算法的研究。另外還有一些技術(shù)，它們采用分布式的系統(tǒng)結(jié)構(gòu)，把視頻服務(wù)器盡量推到離用戶較近的網(wǎng)絡(luò)末梢以節(jié)約主干網(wǎng)絡(luò)帶寬。
1 服務(wù)器流調(diào)度技術(shù)
在統(tǒng)計分析過程中，人們發(fā)現(xiàn)節(jié)目點播情況服從Zipf(齊夫)法則，即對N部電影按訪問概率從大到小進行排序為M1，M2，……Mn，第i部電影的訪問概率pi=P{X=Mi}(i=1，2，……n)滿足：
針對VOD的統(tǒng)計表明，大量用戶的點播往往集中在少數(shù)熱門節(jié)目上。當大量用戶點播相同節(jié)目時，可以把用戶的請求合并，通過組播通道傳輸媒體流，節(jié)約視頻服務(wù)器磁盤I/O帶寬和網(wǎng)絡(luò)帶寬。這種思想正是流媒體調(diào)度技術(shù)的基礎(chǔ)[3]。
流媒體調(diào)度算法分為兩類：(1)靜態(tài)調(diào)度算法是指服務(wù)器主動把節(jié)目在一系列組播通道中播放媒體流。(2)動態(tài)調(diào)度算法是指用戶點播驅(qū)動，服務(wù)器根據(jù)調(diào)度算法來為用戶調(diào)度媒體流。
1.1 靜態(tài)調(diào)度算法
流媒體靜態(tài)調(diào)度算法主要包括階段廣播算法、周期性廣播算法、金字塔(Pyramid)、Permutation Pyramid算法、摩天大樓(skyscraper)算法、磁盤盡力保留廣播(GDB)算法等。
在階段廣播和周期性廣播算法中，服務(wù)器在規(guī)定間隔后開始發(fā)送節(jié)目媒體流，它的延時取決于請求在間隔內(nèi)的到達點。其問題在于雖然提高了服務(wù)器帶寬利用率，但是它強迫用戶端增加延時。
分段廣播系統(tǒng)包括金字塔和摩天大樓算法等。這些系統(tǒng)不是在一個流中廣播一個節(jié)目，而是把節(jié)目分段，在每個流中廣播一個段。分段廣播與階段廣播相比可以降低客戶端延時，但客戶端更復(fù)雜，不能作到零延時，只適用于高點播率的節(jié)目。
GDB（Greedy Disk-conserving Broadcast）是基于周期性的廣播技術(shù)。這個策略中，節(jié)目對象分為段，每個段周期性在特定通道中廣播。這些段經(jīng)過精心選擇，保證客戶在觀看節(jié)目時能加入合適的通道以取得每個段的數(shù)據(jù)，并確保節(jié)目能連續(xù)回放。周期性廣播策略中關(guān)鍵的問題是設(shè)計一個合適的節(jié)目分段公式，以保證客戶端節(jié)目的連續(xù)回放。
1.2 動態(tài)調(diào)度算法
流媒體動態(tài)調(diào)度算法包括FCFS算法、Batching算法、Adaptive Piggybacking算法、Stream Tapping[4]、補丁算法(Patching)、受控組播算法、Catching and Selective Catching、BandWidth Skimming、分片融合、層次型組播流聚合等。
(1)最簡單的動態(tài)調(diào)度算法是FCFS算法，該算法按照用戶請求“先來先服務(wù)”的原則，可以實現(xiàn)簡單的TvoD系統(tǒng)，算法簡單實用，可以支持VCR功能，但是資源消耗過大。
(2)在Batching 算法中，當幾個用戶在相近的時間內(nèi)點播同一部節(jié)目時，服務(wù)器把他們的請求聚合在一起，綁定到一個組播流中。Batching 算法可以有效地利用系統(tǒng)資源。但是它增大了用戶的啟動延時，且該算法不能支持用戶VCR功能。
(3)Adaptive Piggybacking算法中，節(jié)目的播放速度調(diào)節(jié)為原來的正負5%以使兩個流能聚合成一個流。一旦兩個流到達節(jié)目的同一個點，其中一個流即被釋放，用戶切換到現(xiàn)存的流中。缺點是兩個流要經(jīng)過長時間才能聚合，需要服務(wù)器有足夠高的性能來改變節(jié)目播放速度。
(4)Stream Tapping算法中，利用客戶緩沖區(qū)使客戶加入服務(wù)器現(xiàn)存的流中，以便從多個流中取得數(shù)據(jù)。使用這種方法可以節(jié)約服務(wù)器帶寬資源，降低客戶延時，但是它要求客戶有足夠的接收帶寬來同時接收多個流。與Batching相比它能獲得較小的啟動延遲。
(5)補丁算法的基礎(chǔ)是Batching算法，它利用組播媒體流服務(wù)多個用戶。用戶可以利用本地緩沖同時從多個組播流中取得數(shù)據(jù)，用戶沒有啟動延時。同時系統(tǒng)可以盡可能地合并用戶請求來提高系統(tǒng)的效率。補丁算法明顯優(yōu)于其他動態(tài)調(diào)度算法，但是它受客戶緩沖區(qū)的限制，補丁流的大小不能大于緩沖區(qū)長度。
(6)受控組播技術(shù)與補丁算法相似，允許兩個點播同一節(jié)目的客戶共享同一通道。與補丁算法的區(qū)別是：它不會為了提高共享而延遲先到客戶的點播請求，而是通過允許后來的客戶共享先到的客戶的組播流，從而滿足客戶要求。然而受控組播技術(shù)并不是在任何可能的時候都允許客戶加入正在進行的組播會話。使用一個域值來控制何時開辟一個新的組播會話。優(yōu)化的域值可以最小化服務(wù)器的通道數(shù)目。受控組播在低點播率時提供較好的性能。然而，對熱播節(jié)目性能下降，特別在文件巨大時，它的服務(wù)器帶寬與節(jié)目長度和點播率的平方根成正比。
(7)分片融合是一個在補丁基礎(chǔ)上支持VCR功能的算法。當用戶執(zhí)行交互功能時，它將從組播通道中退出，系統(tǒng)重新為它分配單播通道來進行服務(wù)，直到它能和現(xiàn)有的組播流聚合。
(8)Catching技術(shù)比較適合熱播節(jié)目。該技術(shù)的高效性體現(xiàn)在它智能地結(jié)合了服務(wù)器和客戶端的發(fā)送功能。在此技術(shù)中，一個視頻節(jié)目在一些通道中循環(huán)組播。想要觀看該節(jié)目的用戶可以立即加入合適的組播通道，無須等待下一個廣播周期。同時客戶向服務(wù)器發(fā)送請求來取得錯過節(jié)目的開始部分的數(shù)據(jù)（前綴）。前綴通過單播通道發(fā)送，客戶可以馬上觀看。另一方面，從組播通道取得的數(shù)據(jù)暫時緩存在客戶端，直到回放結(jié)束。這樣通過客戶端和服務(wù)器的模式Catching策略可以最小化啟動延遲。為了能適合各種節(jié)目的點播分布，一種叫做Selective Catching的策略，結(jié)合了Catching和受控組播技術(shù)(Controlled Multicast)。受控組播技術(shù)采用客戶端的模式，比較適合冷門節(jié)目。Selective Catching能適用于各種系統(tǒng)負載和各種流行度的節(jié)目。Catching是一種基于參數(shù)的策略，它的通道需求為點播率和文件大小的對數(shù)。這種策略的主要缺點是需要預(yù)先知道點播率參數(shù)，在點播率變化時需要調(diào)整參數(shù)。
2 代理緩存技術(shù)
代理技術(shù)的研究主要包括：緩存策略、代理緩存結(jié)合服務(wù)器調(diào)度技術(shù)、分段分布式代理的研究。
2.1 緩存策略
視頻代理的緩存策略多種多樣，主要包括全部緩存、部分緩存(Prefix，Suffix or Selective)、滑動窗口技術(shù)和分層編碼視頻的緩存策略等。
(1)全部緩存策略：緩存整個流行度高的節(jié)目數(shù)據(jù)，這種方法效率不高，特別是在代理緩存空間有限時尤為突出，緩存需要頻繁的換入換出，緩存一個巨大的節(jié)目代價是昂貴的，所以很難提高點播的命中率，同時也很難降低代理-服務(wù)器之間的網(wǎng)絡(luò)流量。正在進行的流不能被刪除，這會使緩存替換算法替換掉本來不應(yīng)該被替換的節(jié)目，進而偏離優(yōu)化點。
(2)部分緩存策略：可以降低用戶點播的啟動延時，也可以利用緩存的前綴來做一些提前平滑及丟包重傳的處理。但是由于大量后綴數(shù)據(jù)要從服務(wù)器取得，所以不能從本質(zhì)上降低代理到中心服務(wù)器之間的網(wǎng)絡(luò)流量和服務(wù)器的負擔。該方法的側(cè)重點是解決服務(wù)延時，服務(wù)器負載巨大和網(wǎng)絡(luò)帶寬的問題，緩存空間需要非常巨大。
(3)滑動窗口策略：沒有用戶點播請求時，代理服務(wù)器不緩存任何數(shù)據(jù)。當?shù)谝粋€用戶請求到達時，代理服務(wù)器向中心服務(wù)器請求數(shù)據(jù)，代理服務(wù)器預(yù)測將來可能還有請求，緩存w分鐘的數(shù)據(jù)，數(shù)據(jù)的生命期就是窗口的大小。所以從第一個請求開始，w分鐘內(nèi)到達的請求都可以用這個窗口的數(shù)據(jù)來服務(wù)，這個窗口之外的請求將要再次啟動網(wǎng)絡(luò)傳輸。該策略在節(jié)目點播人數(shù)較多時可以節(jié)約一定的網(wǎng)絡(luò)傳輸，缺點是數(shù)據(jù)的生命期固定，它沒有充分利用代理的緩存資源，不能從根本上節(jié)約網(wǎng)絡(luò)帶寬，并且很難實現(xiàn)VCR等功能，同樣存在熱播問題。
(4)分層編碼視頻的緩存策略：針對分層編碼的流媒體來決定應(yīng)該緩存哪一個節(jié)目的哪一層，才能最小化傳輸代價。主要的挑戰(zhàn)是根據(jù)客戶所擁有的不同可用帶寬進行質(zhì)量調(diào)整后，用不同質(zhì)量的緩存流來響應(yīng)。該策略中的預(yù)取算法和適合分層編碼的細粒度的緩存替換算法，能根據(jù)節(jié)目的流行度對緩存狀態(tài)進行調(diào)整。模擬結(jié)果顯示緩存的流質(zhì)量與流行度成正比，質(zhì)量之間的變化與流行度成反比。它的目的主要是來調(diào)節(jié)網(wǎng)絡(luò)而不是為了最小化網(wǎng)絡(luò)帶寬利用[6]。
2.2 代理緩存結(jié)合服務(wù)器調(diào)度
典型的緩存前綴有許多優(yōu)點，例如：掩蓋代理與服務(wù)器之間的延時抖動、啟動延時、減少網(wǎng)絡(luò)傳輸，可以實現(xiàn)在線平滑。中心服務(wù)器使用組播和廣播技術(shù)可以降低服務(wù)器負載和網(wǎng)絡(luò)傳輸。
一種閉環(huán)(點播驅(qū)動)控制的方法被稱為Multicast with Caching(MCache)[7]。MCache的中心思想是利用Batching、Patching和代理前綴緩存技術(shù)。Batching補丁的請求是本策略的獨特特點。使用區(qū)域的緩存服務(wù)器來緩存前綴以降低啟動延遲。MCache的特點在于組播開始后的請求仍舊可以聚合起來，通過組播補丁來達到?jīng)]有啟動延遲。MCache高效地使用代理組播補丁來提供TRUE VOD服務(wù)，它的性能可達到一些著名的開環(huán)控制方法，在高點播率時，使用較少的帶寬。另外使用組播和緩存技術(shù)，克服了一些策略要預(yù)先知道客戶點播率和需要客戶端存儲空間的缺點。
另一種結(jié)合服務(wù)器調(diào)度和代理前綴緩存或部分緩存的策略是在給定緩存容量時，最小化主干網(wǎng)絡(luò)上的傳輸量。它不但存在一個選擇前綴集合的優(yōu)化算法，而且可以動態(tài)緩存補丁數(shù)據(jù)和RC（從頭至尾發(fā)送節(jié)目的通道）的數(shù)據(jù)。
結(jié)合代理前綴緩存和視頻后綴數(shù)據(jù)服務(wù)器周期廣播的調(diào)度策略。該策略的思想是不同代理可以根據(jù)用戶和節(jié)目流行情況采用合適的前綴傳輸策略。另一種方案是結(jié)合部分緩存和Batch Pathing 的策略。它不僅緩存前綴，而且可以有選擇地緩存Pathing數(shù)據(jù)，甚至RC的數(shù)據(jù)，進而可以進一步降低服務(wù)器的負載和代理到中心服務(wù)器的網(wǎng)絡(luò)傳輸。
2.3 分段分布式代理
以往對代理技術(shù)的研究主要是結(jié)合代理緩存和服務(wù)器調(diào)度。最近分段分布式代理技術(shù)是一個研究方向。
MiddleMan[8]是由局域網(wǎng)聯(lián)結(jié)起來的協(xié)同工作的代理服務(wù)器集合。MiddleMan由兩部分組成：代理服務(wù)器和協(xié)調(diào)器(Coordinators)。典型的配置包括一臺協(xié)調(diào)器和多臺代理服務(wù)器，它們通過LAN互聯(lián)。協(xié)調(diào)器跟蹤代理服務(wù)器上保存的內(nèi)容，做出緩存替換決定。MiddleMan存儲系統(tǒng)中把視頻文件平均分成大小相等的文件塊，把它們在所有代理之間分布，使視頻看起來是由一系列順序的文件塊組成。這樣可以極大地降低系統(tǒng)結(jié)構(gòu)的復(fù)雜度，也能提供很好的負載均衡，同樣也簡化了節(jié)目替換算法，并且也使設(shè)計更科學(xué)的節(jié)目替換算法成為可能。MiddleMan需要考慮的一個技術(shù)難題是從不同的代理服務(wù)器上取文件塊并把它們合并成一個連續(xù)的流。
MiddleMan提供和評估了基于分斷存儲大媒體流的代理管理方法。代理服務(wù)器接收到的媒體流塊數(shù)據(jù)按可變大小的段組織，緩存接納控制和替換策略為每個段添加不同的緩存值。這些緩存策略對開始段給予特別的考慮。把緩存空間分為兩部分，一部分用來緩存前綴，一部分用來緩存后綴。前綴只能替換原來緩存的前綴，后綴只能替換原來的后綴。結(jié)果表明：(1)基于分段緩存不但可以提高命中率(降低全部的網(wǎng)絡(luò)傳輸)，而且可以降低請求的開始延時；(2)基于分段緩存在緩存空間有限以及熱播節(jié)目變化頻繁、媒體文件巨大以及用戶經(jīng)常只觀看節(jié)目開始部分時具有特別的優(yōu)勢。
一些視頻服務(wù)器提供了VCR功能，但它需要經(jīng)歷很大的延時和大量的處理。另外用戶也不知道視頻的大致內(nèi)容以及感興趣部分的精確位置，同時也浪費了網(wǎng)絡(luò)資源。結(jié)合交互式視頻發(fā)送和緩存系統(tǒng)并使用視頻分析和抽象技術(shù)設(shè)計了一個視頻代理系統(tǒng)，可給用戶提供一個良好的觀看環(huán)境。視頻分析包括Shot Boundary Detection和Key-frame Selection。當用戶點播一個節(jié)目時，系統(tǒng)首先顯示一系列關(guān)鍵畫面，用戶可以選擇從關(guān)鍵畫面開始播放。視頻數(shù)據(jù)分段存儲在多個代理上來進行負載均衡，同時也允許實現(xiàn)細粒度的替換策略。前綴緩存是只緩存每個視頻段的前綴，所以預(yù)取也能減低延時。
3 節(jié)目替換算法
傳統(tǒng)的替換算法主要應(yīng)用于大小相等的對象、傳統(tǒng)的內(nèi)存以及Web應(yīng)用的替換算法不適用于流媒體領(lǐng)域。最經(jīng)典的替換算法包括LRU(Latest Recently Used)、LFU（Latest Frequently Used）等。LRU算法不能區(qū)別經(jīng)常和不經(jīng)常使用的對象。LFU緩存策略緩存當前具有高使用頻率的節(jié)目或片段[9]。
目前提出的RBC算法在緩存接納和替換時考慮了文件大小和所需的發(fā)送帶寬因素。Pooled RBC策略進一步提高了RBC算法的性能。它提供一個帶寬POOL，當一個點播請求到達時，從帶寬POOL中為該用戶分配流。發(fā)送完畢要收回已經(jīng)分配的帶寬歸還給帶寬POOL。如果點播請求不能分配足夠的帶寬，則POOL RBC把請求轉(zhuǎn)交給原始服務(wù)器，而不是簡單地替換實體來釋放帶寬。實驗結(jié)果表明，在大多數(shù)情況下這個策略明顯比RBC容易實現(xiàn)。而Hybrid LFU/Interval Caching策略的性能比Pooled RBC和LFU都優(yōu)越。LFU/IC是一個結(jié)合LFU和Interval Caching的技術(shù)。Interval Caching算法主要研究在內(nèi)存中緩存部分節(jié)目流。在這個策略中，如果點播同一個節(jié)目的請求相距足夠近，發(fā)送給第一個用戶的流將保存在內(nèi)存中直到給第二個用戶發(fā)送完畢。更一般的數(shù)據(jù)緩存在內(nèi)存中直到滿足幾個相近的點播請求。通過結(jié)合磁盤緩存和內(nèi)存緩存兩種技術(shù)，明顯提高了LFU的性能。
LRU算法不能區(qū)別經(jīng)常和不經(jīng)常使用的對象。LRU-K算法仔細檢查使用對象最近K次被引用的信息。本文使用考慮最近2次引用信息的算法叫作LRU-2，更一般的是LRU-K算法。典型的LRU算法相當于這里的LRU-1算法。LRU-K包含內(nèi)在的“老化”含義，考慮了對象的最近K次引用，然而LRU算法不能很好地處理不斷演化的引用模式。LRU-K算法有以下顯著的特點：①能很好地區(qū)分不同級別引用對象的集合。②可以通過自調(diào)節(jié)來適應(yīng)不同的引用模式。③產(chǎn)生很少的管理負擔。通過2Q算法可對LRU-K進行改進。它引進兩個管理隊列來簡化LRU-K的管理負擔。在大多數(shù)情況下，2Q算法性能比LRU高5%～10%，性能與LRU-K相近。2Q的復(fù)雜度為O(1)，LRU-K的復(fù)雜度為O(logn)。但是LRU-K（包括2Q）沒有統(tǒng)一考慮近期性和頻率。所以在K較大時LRU-K算法很難適應(yīng)不斷演化的工作模式。
LRU和LFU分別是考慮近期性和使用頻率的兩個極端。LRFU(Least Recently/Frequently Used)策略統(tǒng)一考慮頻率和近期性，在兩者之間進行折中。LRFU算法中為每個塊分配一個CRF(Combined Recency and Frequency)，這個CRF值代表該對象將來被點播的可能。過去的每次引用對該值的貢獻由一個權(quán)值函數(shù)F(x)來衡量。F(x)是一個單調(diào)降函數(shù)，x代表當前時刻。
Segmented LRU是基于頻率對基本LRU進行擴展，它是為頁緩存設(shè)計的，頁的大小均相等。Segmented LRU基于這樣的觀察：在很短一段時間內(nèi)使用兩次的對象比只使用一次的對象流行度高。在Segmented LRU中緩存空間分為兩部分：可能段和保護段。新對象（使用一次）首先進入可能段，使用兩次以上的段進入保護段。當整個緩存空間滿時，可能段中的最近最少使用的對象將被替換掉。保護段空間有限，當它滿時，從中溢出的段重新緩存在可能段中。因為保護段中的對象在被驅(qū)逐時要走相對長的路，所以流行的和使用次數(shù)多的對象能在緩存中保存較長的時間。
The Size-Adjusted LRU把緩存的所有對象按cost-to-size（1/(Si*ΔTit）)排序，這里Si是對象I的大小，ΔTit是自從上次使用以來經(jīng)歷的時間。它只是貪婪地把cost-to-size最小的對象刪除。實際應(yīng)用中對象按Si*ΔTit重新排序，具有較大索引的對象在替換時逐一被清除掉。
更進一步，為了避免計算所有對象的cost-to-size值，一個近似的算法叫做Pyramidal Selection Scheme(PSS)，對象按log2(size)分為有限的組，同一個組中對象大小相似。每個組中使用LRU機制。
4 小 結(jié)
本文歸納總結(jié)了當前流媒體傳輸領(lǐng)域的一些流行的技術(shù)，并對它們進行分類。目前看來，各種技術(shù)都只能解決部分問題，并且都有自己的缺陷。因此目前還沒有完善的流媒體傳輸解決方案。我們期待將來隨著計算機和通信技術(shù)及流媒體領(lǐng)域各種相關(guān)技術(shù)（視頻壓縮、傳輸協(xié)議等）的發(fā)展，會出現(xiàn)更好的流媒體解決方案，使流媒體得到更廣泛的應(yīng)用。
參考文獻
1 吳國勇，丘學(xué)剛，萬燕仔.網(wǎng)絡(luò)視頻：流媒體技術(shù)與應(yīng)用.北京：北京郵電大學(xué)出版社，2001
2 段渭軍，張永斌，王福豹.分布式視頻點播系統(tǒng)的設(shè)計與實現(xiàn).世界電信網(wǎng)絡(luò)，2002；10(4)：36
3 鐘玉琢，向哲，沈洪.流媒體和視頻服務(wù)器.北京：清華大學(xué)出版社，2003
4 Carter S W，Long D D E.Improving bandwidth efficiency of video-on-demand servers.Computer Networks and ISDN Systems，1999；31(1)：99
5 Rejaie R，Handley M，Yu H et al.Proxy caching mechanism for multimedia playback streams in the internet.In：Proceedings of the 4th International Web Caching Workshop，San Diego，CA.，March 1999
6 Rejaie R，Handley M，Yu H et al.Proxy caching mechanism for multimedia playback streams in the internet.In：Proceedings of the 4th International Web Caching Workshop，San Diego，CA.，March 1999
7 Ramesh S，Rhee I，Guo K.Multicast with Cache (Mcache)：An Adaptive Zero Delay Video-on-Demand Service.In：Proc.of IEEE Infocorn′01，Apr 2001
8 Acharya S，Smith B.MiddleMan:A Video Caching Proxy Server.In：proc.IEEE NOSSDAV，2000
9 Tewari R，Vin H，Dan A et al.Resource-Based Caching for Web Servers.In：Proceedings of SPIE/ACM Conference on Multimedia Computing，January 1998