基于代理的流媒體動態共享緩存算法研究

摘要：研究了代理服務器在流媒體傳輸和緩存方面對于網絡帶寬的消耗以及在緩存過程中內存分配和管理等方面存在的問題；在分析了現有的流媒體代理緩存技術的基礎上，提出了基于代理服務器的流媒體動態共享緩存（DSB）算法。分析和實驗結果表明，與現有的緩存技術相比，DSB算法能夠有效地提高緩沖區的利用率，節省代理服務器的內存資源，節省網絡帶寬，同時能夠為更多的客戶端請求提供服務，并且可以有效地縮短請求延時。關鍵詞：流媒體；代理緩存；補丁預取；調度算法

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)05－0262－04

0引言

在互聯網上的各種流媒體應用（如視頻點播、遠程教學、視頻會議等）隨著各種寬帶接入技術的廣泛使用，已經將帶寬瓶頸上移到骨干網，致使骨干網帶寬難以支撐大規模流媒體應用的普及。互聯網內容傳輸的基礎架構為客戶端—代理服務器—內容服務器模式，代理服務器承擔著內容緩存的任務。然而傳統代理協議只提供基于靜態文本和圖像的緩存技術，因此基于代理服務器的流媒體緩存技術近年來成為了該領域的研究重點。

流媒體內容傳輸所提出的挑戰一方面是流媒體的數據量遠遠大于傳統的文本內容；另一方面流媒體對象傳輸對于連續性和實時性的要求也大大超過文本對象。目前已經提出了很多流調度算法和代理緩存算法，如金字塔算法（Pyramid）[1]、批處理技術（Batching）[2]、補丁算法（Patching）、緩存算法（Caching）等。補丁算法[3，4]是利用客戶端的存儲資源，并且建立多條通道來獲取和緩存數據；前綴緩存（Prefix Caching）[5]和分段緩存（Segment－Based Caching）[6~8]是利用代理服務器的磁盤存儲空間來實現緩存，固定大小緩存（Fixed－Sized Ca－ching）[9]和間隔緩存（Interval Caching）[10，11]是兩種基于內存運行緩沖區的緩存技術，共享緩沖區（Shared Running Buffers，SRB）緩存[12]是為提高緩沖區利用率而提出的另一種緩沖區緩存算法。

基于內存的緩存技術，可以有效緩解對于內容服務器的數據請求而節省網絡帶寬和改善啟動延時，然而現有技術在緩沖區共享以及內存調度等方面尚存在不足。本文提出的動態共享緩沖算法在分析和試驗結果中表明:它可以在節省網絡帶寬的同時有效地利用代理服務器的內存資源，使代理服務器能夠為更多的客戶端請求提供服務并且進一步縮短請求延時。

1相關算法分析

固定大小緩存、間隔緩存以及共享緩沖區緩存算法都是在內存當中申請緩沖區用來緩存部分流媒體數據，為后續到達的客戶端請求提供服務，避免直接從內容服務器獲取數據，同時可以提高請求的反應速度。

1．1固定大小緩存

固定大小緩存的基本原理是：當一個請求到達時，在內存中分配一塊事先預定義長度的緩沖區用來緩存數據，期望為后續的請求提供服務。

在圖1中，兩條條紋帶分別表示代理服務器為同一個流媒體對象申請的兩個緩沖區B1和B2，橫坐標為訪問時間，縱坐標為緩沖區中的數據對應媒體對象的時間位置，R1~R5分別表示不同時刻客戶端對該媒體對象發出的請求。

當R1請求到達時，B1緩沖區被申請用來保存從內容服務器獲取的數據，并且為后續的請求R2和R3提供服務，即R2和R3可以直接從緩沖區中讀取媒體對象數據而不必再從內容服務器獲取，實現了緩存的功能。由于緩沖區的大小是事先定義好的固定尺寸，當請求R4到達時，B1緩沖區當中的數據已經偏離了媒體對象的起始位置，需要重新分配緩沖區B2，為后續的請求R5提供服務。

從圖1中可以看出，固定大小緩存技術是由于緩沖區的大小是固定的。就圖1情況而言，緩沖區B1和B2的大小都分別大于R1~R3以及R4和R5最小所需的緩沖區大小，從而造成內存資源的浪費。

1．2間隔緩存

間隔緩存的基本原理是：以兩個相鄰的請求定義為一個請求對，根據請求對之間的時間差來動態調整緩沖區的大小，從而提高內存的利用率。

在圖2中，當R2請求到達時，R1和R2形成一個請求對，以時間間隔的大小申請一個緩沖區B1（如圖2中R1和R2之間的條紋帶）；R1從內容服務器直接獲取到的數據將保存到B1中，因此R2只需從內容服務器獲取在此之前的部分數據，而余下的數據就可以直接從B1當中獲取。當請求R3到達時，B1緩沖區的大小擴充至R3和R1之間的時間間隔大小；此后R2直接從服務器獲取的數據也將放入擴充后的緩沖區B1當中。當請求R5到達時，因為R4與R5之間的時間間隔較R3與R4之間的間隔小，這時為請求對R4和R5重新分配緩沖區B2，同時縮減B1緩沖區的大小到R3請求線的位置。

間隔緩存技術盡管考慮了用戶的訪問模式，并且做到了動態調整緩沖區的大小，但是仍然沒有考慮到不同緩沖區之間的共享，即如果B1能夠共享的話，B2就不需要運行到流媒體對象的尾部。

1．3共享緩沖區緩存

共享緩沖區緩存在綜合考慮前兩種技術的優點和不足之后提出了一種提高已有緩沖區利用率的方法。它定義了緩沖區的三種狀態，即構造狀態、運行狀態和空閑狀態，并且實現了緩沖區大小的動態調整，同時給出了緩沖區共享的公式化的方式方法。但是它所提出的公式和圖解在個別之處存在著錯誤和不足。

例如其中對于緩沖區運行距離的定義[6]為

對于緩沖區結束時間的定義也存在相關錯誤。

2動態共享緩沖區緩存算法

考慮現有緩存技術存在的局限性和不足，提出了一種動態共享緩沖區（Dynamic Shared Buffers，DSB）緩存算法。其目的是在對流媒體對象提供緩存服務的同時最大化地提升內存緩沖區的利用率。

本文當中的算法和圖例都是以假設客戶端從流媒體對象首部開始請求為前提的，但是實際上對于從非固定位置開始的請求本算法同樣適用。

2．1相關概念

借鑒于共享緩沖區（SRB）緩存所提出的幾項基本概念，對本文所提出算法的相關基本概念定義如下：

定義1請求間隔。對于同一個流媒體對象，將兩個相鄰請求在到達時間上的差定義為請求間隔[6]。

圖3中的三條垂直粗線段分別對應三個緩沖區到達停止狀態的時間。

定義5空閑狀態。

當緩沖區到達停止時間時，緩沖區的狀態由停止狀態改變為空閑狀態；之后該緩沖區可以被回收或者再次利用（為新到達的請求再次提供服務）。

在一個緩沖區進入空閑狀態之后，為了能夠為后續新到達的請求提供服務，它需要保持這一狀態直至新緩沖區運行到它的尾部。這種情況下，需要根據最新請求的到達時間動態修改這些空閑緩沖區的停止時間為

2．2算法

當對于流媒體對象i的請求到達時，首先判斷為該流媒體對象申請的最后一塊緩沖區中是否包含前綴信息。如果包含則直接用它來提供服務；如果最后一塊緩沖區已經離開流媒體的首部則視內存使用情況新申請一塊緩沖區或直接從內容服務器獲取而不提供緩存。

2．2．1構造狀態時緩沖區大小的凍結算法

當緩沖區最初被申請時，大小由事先預定義的T來確定，緩沖區的狀態標志為構造狀態。當到達T時刻的尾部時：

2．2．2運行狀態時緩沖區大小的動態調整算法

在運行狀態下，請求的提前終止會導致緩沖區大小的調整。調整算法分為以下三種情況：

(1)提前終止的請求是緩沖區上的第一個請求。由于緩沖區的數據是依靠第一個請求從服務器獲取內容來填充的，當第一個請求提前終止時，緩沖區的填寫任務將由第二個請求來完成。由于第二個請求與第一個請求之間存在一個請求間隔I1i，緩沖區中第二個請求讀取位置的前面還保留著第一個請求遺留下的部分媒體內容，第二個請求在這個時間差內仍然可以從緩沖區內獲取數據；之后再直接從服務器獲取，并將緩沖區的大小縮減至第二個請求到最后一個請求之間的距離。如果不存在第二個請求則緩沖區進入空閑狀態。

(2)提前終止的請求位于請求隊列的中間（Rji，1

(3)提前終止的請求位于請求隊列的尾部。如果存在后續緩沖區則保持狀態不變；否則縮減緩沖區大小至R j-1i的位置。

3性能評估及實驗結果

首先比較幾種緩沖算法的緩沖效率。實驗采用的機器內存為1 GB，實驗數據為10個大小在120 MB（30 min）左右的視頻文件；預設定的緩沖區大小分別從文件自身大小至它的1/32。隨后再比較不同的訪問頻率情況下客戶端的請求延時。試驗結果數據如圖5所示。

圖5（a）顯示了不同算法下代理服務器對于網絡帶寬的需求。可以看出，動態共享緩沖區緩存算法對于降低帶寬需求取得了明顯的效果。預定義緩沖區的大小對于DSB算法的緩存效率具有明顯的影響。盡管大的緩沖區能夠為更多的請求提供服務，但是由于客戶請求目標和間隔的不確定性，在內存再次申請或者回收、調整過程中大緩沖區的服務效率會降低，從而較小的緩沖區模式取得了較好的緩存效果。

圖5（b）顯示了在以流媒體對象長度的1/16為初始緩沖區大小情況下，不同算法對于客戶端請求延時產生的影響。同樣可以看出，動態共享緩存算法同樣可以有效降低客戶端的請求延時。

4結束語

本文提出了一種新的代理緩存算法，并且定義了緩沖區的幾種不同狀態，以及緩沖區大小的凍結和運行過程當中動態調整的算法。比較與固定大小緩存、間隔緩存以及共享緩存三種緩存算法。試驗結果表明，動態共享緩存算法在內存分配管理以及對帶寬需求的降低等方面均收到了明顯的效果。

參考文獻：

［1］VISWANAT H S， IMIELINSKI T. Pyramid broadcasting for video on demand service：proceedings of IEEE Multimedia Computing and Networking Conference[C].San Jose:[s.n.]，1995: 66－77.

［2］DAN A， SITARAM D，SHAHABUDDIN P.Scheduling policies for an on－demand video server with batching:proceedings of ACM Multi－media[C]. San Francisco:[s.n.]，1994:15－23.

［3］HUA K A， CAI Ying， SHEU S. Patching: a multicast technique for true video－on－demand services: proceedings of ACM Multimedia[C].New York:ACM Press，1998.

［4］SEN S， GAO Lixin， TOWSLEY D. Optimal patching schemes for efficient multimedia streaming: proceedings of ACM Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV)[C].Basking Ridge:IEEE Computer Society Press，1999.

［5］SEN S， REXFORD K，TOWSLEY D. Proxy prefix caching for multimedia streams: proc.of IEEE INFOCOM’99[C]. New York:[s.n.]，1999.

［6］CHEN Songqing， SHEN Bo， ZHANG Xiaodong. Adaptive and lazy segmentation based proxy caching for streaming media delivery: proceedings of ACM NOSSDAV[C]. Monterey:[s.n.]，2003.

［7］REJAIE R， HANDLEY M， ESTRIN D. Proxy caching mechanism for multimedia playback streams in the Internet: proc. of the 4th International WWW Caching Worshop[C].San Diego:[s.n.]，1999.

［8］WU Kunlang，YU P S，WOLF J L. Segment－based proxy caching of multimedia streams: proc. of the 10th International WWW Conference[C].Hongkong:[s.n.]，2001:36－44.

［9］BOMMAIAH E， GUO K， HOFMANN M，et al. Design and implementation of a caching system for streaming media over the Internet: proceedings of IEEE Real－time Technology and Applications Sympo－sium[C].[S.l.]:[s.n.]，2000.

［10］DAN A，SITARAM D.Buffer management policy for an on－demand video server， IBM Research Report 19347[R].[S.l.]:[s.n.]，1993.

［11］DAN S，SITARAM D.A generalized interval caching policy for mixed interactive and long video workloads: proceedings of Multimedia Computing and Networking[C].San Jose:[s.n.]，1996.

［12］CHEN Songqing， SHEN Bo， BASU S， et al. SRB:the shared running buffer based proxy caching of streaming sessions，Hewlett－Packard Laboratories Tech. Report[R].[S.l.]:[s.n.]，2003.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”