近年來互聯網上基于視頻、音頻的流媒體應用呈飛速發展的趨勢。互聯網，即廣域網、局域網及單機按照一定的通訊協議組成的國際計算機網絡?；ヂ摼W是指將兩臺計算機或者是兩臺以上的計算機終端、客戶端、服務端通過計算機信息技術的手段互相聯系起來的結果，人們可以與遠在千里之外的朋友相互發送郵件、共同完成一項工作、共同娛樂。計算機與網絡是繼造紙和印刷術發明以來，人類又一個信息存儲與傳播的偉大創造，稱為第五次信息革命。 通常，網絡與網絡之間所串連成的龐大網絡，則可譯為“網際”網絡，又音譯因特網或者英特網，在1990年代發展初期，因其跨國際性連接之特性，在***亦有人稱其為國際網絡，或國際電腦網絡。是指在ARPA網基礎上發展出的世界上最大的全球性互聯網絡。而互聯網（英語：international network或internet），在***譯作網際網路，或稱互連網，即是“連接網絡的網絡”，可以是任何分離的實體網絡之集合，這些網絡以一組通用的協定相連，形成邏輯上的單一網絡。這種將計算機網絡互相聯接在一起的方法稱為“網絡互聯”。

阻礙流媒體發展的因素主要是帶寬問題，包括服務器磁盤帶寬和網絡帶寬，二者中相對較小者決定了系統服務用戶的數目。流媒體傳輸技術面臨如此多的挑戰，從而吸引許多學者在這方面進行研究，并取得了一定的成果。

對流媒體傳輸技術的研究主要涉及：（1）服務器流調度技術。（2）代理緩存技術。（3）節目替換算法的研究。

1 服務器流調度技術

在統計分析過程中，人們發現節目點播情況服從Zipf（齊夫）法則，即對N部電影按訪問概率從大到小進行排序為M1，M2，……Mn，第i部電影的訪問概率pi=P{X=Mi}（i=1，2，……n）滿足：

針對VOD的統計表明，大量用戶的點播往往集中在少數熱門節目上。當大量用戶點播相同節目時，可以把用戶的請求合并，通過組播通道傳輸媒體流，節約視頻服務器磁盤I/O帶寬和網絡帶寬。這種思想正是流媒體調度技術的基礎[3]。

流媒體調度算法分為兩類：（1）靜態調度算法是指服務器主動把節目在一系列組播通道中播放媒體流。（2）動態調度算法是指用戶點播驅動，服務器根據調度算法來為用戶調度媒體流。

1.1 靜態調度算法

在階段廣播和周期性廣播算法中，服務器在規定間隔后開始發送節目媒體流，它的延時取決于請求在間隔內的到達點。其問題在于雖然提高了服務器帶寬利用率，但是它強迫用戶端增加延時。

分段廣播系統包括金字塔和摩天大樓算法等。這些系統不是在一個流中廣播一個節目，而是把節目分段，在每個流中廣播一個段。

GDB是GNU開源組織發布的一個強大的UNIX下的程序調試工具。或許，各位比較喜歡那種圖形界面方式的，像VC、BCB等IDE的調試，但如果你是在 UNIX平臺下做軟件，你會發現GDB這個調試工具有比VC、BCB的圖形化調試器更強大的功能。所謂“寸有所長，尺有所短”就是這個道理。要想運行準備調試的程序，可使用run命令，在它后面可以跟隨發給該程序的任何參數，包括標準輸入和標準輸出說明符（<和> ）和shell通配符（*、？、[、]）在內。如果你使用不帶參數的run命令，gdb就再次使用你給予前一條run命令的參數，這是很有用的。利用set args 命令就可以修改發送給程序的參數，而使用show args 命令就可以查看其缺省參數的列表。

1.2 動態調度算法

流媒體動態調度算法包括FCFS算法、Batching算法、Adaptive Piggybacking算法、Stream Tapping、補丁算法（Patching）、受控組播算法、Catching and Selective Catching、BandWidth Skimming、分片融合、層次型組播流聚合等。

（1）最簡單的動態調度算法是FCFS算法，該算法按照用戶請求“先來先服務”的原則，可以實現簡單的TvoD系統，算法簡單實用，可以支持VCR功能，但是資源消耗過大。

（2）在Batching 算法中，當幾個用戶在相近的時間內點播同一部節目時，服務器把他們的請求聚合在一起，綁定到一個組播流中。Batching 算法可以有效地利用系統資源。但是它增大了用戶的啟動延時，且該算法不能支持用戶VCR功能。

（3）Adaptive Piggybacking算法中，節目的播放速度調節為原來的正負5%以使兩個流能聚合成一個流。一旦兩個流到達節目的同一個點，其中一個流即被釋放，用戶切換到現存的流中。

（4）Stream Tapping算法中，利用客戶緩沖區使客戶加入服務器現存的流中，以便從多個流中取得數據。使用這種方法可以節約服務器帶寬資源，降低客戶延時，但是它要求客戶有足夠的接收帶寬來同時接收多個流。

（5）補丁算法的基礎是Batching算法，它利用組播媒體流服務多個用戶。用戶可以利用本地緩沖同時從多個組播流中取得數據，用戶沒有啟動延時。同時系統可以盡可能地合并用戶請求來提高系統的效率。

（6）受控組播技術與補丁算法相似，允許兩個點播同一節目的客戶共享同一通道。與補丁算法的區別是：它不會為了提高共享而延遲先到客戶的點播請求，而是通過允許后來的客戶共享先到的客戶的組播流，從而滿足客戶要求。然而受控組播技術并不是在任何可能的時候都允許客戶加入正在進行的組播會話。使用一個域值來控制何時開辟一個新的組播會話。優化的域值可以最小化服務器的通道數目。受控組播在低點播率時提供較好的性能。

（7）分片融合是一個在補丁基礎上支持VCR功能的算法。當用戶執行交互功能時，它將從組播通道中退出，系統重新為它分配單播通道來進行服務，直到它能和現有的組播流聚合。

（8）Catching技術比較適合熱播節目。該技術的高效性體現在它智能地結合了服務器和客戶端的發送功能。在此技術中，一個視頻節目在一些通道中循環組播。想要觀看該節目的用戶可以立即加入合適的組播通道，無須等待下一個廣播周期。同時客戶向服務器發送請求來取得錯過節目的開始部分的數據（前綴）。前綴通過單播通道發送，客戶可以馬上觀看。另一方面，從組播通道取得的數據暫時緩存在客戶端，直到回放結束。這樣通過客戶端和服務器的模式Catching策略可以最小化啟動延遲。受控組播技術采用客戶端的模式，比較適合冷門節目。Catching是一種基于參數的策略，它的通道需求為點播率和文件大小的對數。

2 代理緩存技術

代理技術的研究主要包括：緩存策略、代理緩存結合服務器調度技術、分段分布式代理的研究。

2.1 緩存策略

（1）全部緩存策略：緩存整個流行度高的節目數據，這種方法效率不高，特別是在代理緩存空間有限時尤為突出，緩存需要頻繁的換入換出，緩存一個巨大的節目代價是昂貴的，所以很難提高點播的命中率，同時也很難降低代理-服務器之間的網絡流量。正在進行的流不能被刪除，這會使緩存替換算法替換掉本來不應該被替換的節目，進而偏離優化點。

（2）部分緩存策略：可以降低用戶點播的啟動延時，也可以利用緩存的前綴來做一些提前平滑及丟包重傳的處理。但是由于大量后綴數據要從服務器取得，所以不能從本質上降低代理到中心服務器之間的網絡流量和服務器的負擔。該方法的側重點是解決服務延時，服務器負載巨大和網絡帶寬的問題，緩存空間需要非常巨大。

（3）滑動窗口策略：沒有用戶點播請求時，代理服務器不緩存任何數據。當第一個用戶請求到達時，代理服務器向中心服務器請求數據，代理服務器預測將來可能還有請求，緩存w分鐘的數據，數據的生命期就是窗口的大小。所以從第一個請求開始，w分鐘內到達的請求都可以用這個窗口的數據來服務，這個窗口之外的請求將要再次啟動網絡傳輸。

（4）分層編碼視頻的緩存策略：針對分層編碼的流媒體來決定應該緩存哪一個節目的哪一層，才能最小化傳輸代價。主要的挑戰是根據客戶所擁有的不同可用帶寬進行質量調整后，用不同質量的緩存流來響應。該策略中的預取算法和適合分層編碼的細粒度的緩存替換算法，能根據節目的流行度對緩存狀態進行調整。

2.2 代理緩存結合服務器調度

典型的緩存前綴有許多優點，例如：掩蓋代理與服務器之間的延時抖動、啟動延時、減少網絡傳輸，可以實現在線平滑。中心服務器使用組播和廣播技術可以降低服務器負載和網絡傳輸。

一種閉環（點播驅動）控制的方法被稱為Multicast with Caching（MCache）。MCache的中心思想是利用Batching、Patching和代理前綴緩存技術。Batching補丁的請求是本策略的獨特特點。使用區域的緩存服務器來緩存前綴以降低啟動延遲。MCache的特點在于組播開始后的請求仍舊可以聚合起來，通過組播補丁來達到沒有啟動延遲。

另一種結合服務器調度和代理前綴緩存或部分緩存的策略是在給定緩存容量時，最小化主干網絡上的傳輸量。它不但存在一個選擇前綴集合的優化算法，而且可以動態緩存補丁數據和RC的數據。

結合代理前綴緩存和視頻后綴數據服務器周期廣播的調度策略。該策略的思想是不同代理可以根據用戶和節目流行情況采用合適的前綴傳輸策略。另一種方案是結合部分緩存和Batch Pathing 的策略。

2.3 分段分布式代理

MiddleMan是由局域網聯結起來的協同工作的代理服務器集合。MiddleMan由兩部分組成：代理服務器和協調器（Coordinators）。典型的配置包括一臺協調器和多臺代理服務器，它們通過LAN互聯。協調器跟蹤代理服務器上保存的內容，做出緩存替換決定。MiddleMan存儲系統中把視頻文件平均分成大小相等的文件塊，把它們在所有代理之間分布，使視頻看起來是由一系列順序的文件塊組成。

MiddleMan提供和評估了基于分斷存儲大媒體流的代理管理方法。代理服務器接收到的媒體流塊數據按可變大小的段組織，緩存接納控制和替換策略為每個段添加不同的緩存值。前綴只能替換原來緩存的前綴，后綴只能替換原來的后綴。結果表明：（1）基于分段緩存不但可以提高命中率（降低全部的網絡傳輸），而且可以降低請求的開始延時；（2）基于分段緩存在緩存空間有限以及熱播節目變化頻繁、媒體文件巨大以及用戶經常只觀看節目開始部分時具有特別的優勢。

一些視頻服務器提供了VCR功能，但它需要經歷很大的延時和大量的處理。另外用戶也不知道視頻的大致內容以及感興趣部分的精確位置，同時也浪費了網絡資源。結合交互式視頻發送和緩存系統并使用視頻分析和抽象技術設計了一個視頻代理系統，可給用戶提供一個良好的觀看環境。視頻數據分段存儲在多個代理上來進行負載均衡，同時也允許實現細粒度的替換策略。前綴緩存是只緩存每個視頻段的前綴，所以預取也能減低延時。

3 節目替換算法

傳統的替換算法主要應用于大小相等的對象、傳統的內存以及Web應用的替換算法不適用于流媒體領域。LRU是Least Recently Used最近最少使用算法。Oracle系統使用的一種算法，對于在內存中但最近又不用的數據塊（內存塊）叫做LRU，Oracle會根據那些數據屬于LRU而將其移出內存而騰出空間來加載另外的數據。關于操作系統的內存管理，如何節省利用容量不大的內存為最多的進程提供資源，一直是研究的重要方向。而內存的虛擬存儲管理，是現在最通用，最成功的方式—— 在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用得到信息。這無疑極大地擴充了內存的功能，極大地提高了計算機的并發度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其余頁面放入外存的管理方式。然而，有利就有弊，虛擬頁式存儲管理減少了進程所需的內存空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和內存中已有的進行交換，由于外存的低速，這一步驟所花費的時間不可忽略。因而，采取盡量好的算法以減少讀取外存的次數，也是相當有意義的事情。

目前提出的RBC算法在緩存接納和替換時考慮了文件大小和所需的發送帶寬因素。Pooled RBC策略進一步提高了RBC算法的性能。它提供一個帶寬POOL，當一個點播請求到達時，從帶寬POOL中為該用戶分配流。發送完畢要收回已經分配的帶寬歸還給帶寬POOL。如果點播請求不能分配足夠的帶寬，則POOL RBC把請求轉交給原始服務器，而不是簡單地替換實體來釋放帶寬。實驗結果表明，在大多數情況下這個策略明顯比RBC容易實現。而Hybrid LFU/Interval Caching策略的性能比Pooled RBC和LFU都優越。LFU/IC是一個結合LFU和Interval Caching的技術。Interval Caching算法主要研究在內存中緩存部分節目流。

LRU算法不能區別經常和不經常使用的對象。LRU-K算法仔細檢查使用對象最近K次被引用的信息。本文使用考慮最近2次引用信息的算法叫作LRU-2，更一般的是LRU-K算法。典型的LRU算法相當于這里的LRU-1算法。LRU-K包含內在的“老化”含義，考慮了對象的最近K次引用，然而LRU算法不能很好地處理不斷演化的引用模式。LRU-K算法有以下顯著的特點：①能很好地區分不同級別引用對象的集合。②可以通過自調節來適應不同的引用模式。③產生很少的管理負擔。通過2Q算法可對LRU-K進行改進。它引進兩個管理隊列來簡化LRU-K的管理負擔。

LRU和LFU分別是考慮近期性和使用頻率的兩個極端。LRFU（Least Recently/Frequently Used）策略統一考慮頻率和近期性，在兩者之間進行折中。LRFU算法中為每個塊分配一個CRF（Combined Recency and Frequency），這個CRF值代表該對象將來被點播的可能。過去的每次引用對該值的貢獻由一個權值函數F（x）來衡量。F（x）是一個單調降函數，x代表當前時刻。

Segmented LRU是基于頻率對基本LRU進行擴展，它是為頁緩存設計的，頁的大小均相等。Segmented LRU基于這樣的觀察：在很短一段時間內使用兩次的對象比只使用一次的對象流行度高。在Segmented LRU中緩存空間分為兩部分：可能段和保護段。新對象（使用一次）首先進入可能段，使用兩次以上的段進入保護段。當整個緩存空間滿時，可能段中的最近最少使用的對象將被替換掉。為了盡量減少與理想算法的差距，產生了各種精妙的算法，最近最少使用頁面置換算法便是其中一個。LRU算法的提出，是基于這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理 ——比內存速度還要快的cache，也是基于同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。

The Size-Adjusted LRU把緩存的所有對象按cost-to-size（1/（Si*ΔTit））排序，這里Si是對象I的大小，ΔTit是自從上次使用以來經歷的時間。它只是貪婪地把cost-to-size最小的對象刪除。實際應用中對象按Si*ΔTit重新排序，具有較大索引的對象在替換時逐一被清除掉。

更進一步，為了避免計算所有對象的cost-to-size值，一個近似的算法叫做Pyramidal Selection Scheme（PSS），對象按log2（size）分為有限的組，同一個組中對象大小相似。每個組中使用LRU機制。

4 小 結

本文歸納總結了當前流媒體傳輸領域的一些流行的技術，并對它們進行分類。目前看來，各種技術都只能解決部分問題，并且都有自己的缺陷。因此目前還沒有完善的流媒體傳輸解決方案。我們期待將來隨著計算機和通信技術及流媒體領域各種相關技術（視頻壓縮、傳輸協議等）的發展，會出現更好的流媒體解決方案，使流媒體得到更廣泛的應用。