基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略

何智聰，谷光昭，王新，趙進(jìn)，薛向陽

(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 智能信息處理上海市重點(diǎn)實(shí)驗(yàn)室，上海 201203)

1 引言

流媒體業(yè)務(wù)依靠互聯(lián)網(wǎng)的高速發(fā)展給自身提供了強(qiáng)大的市場動(dòng)力，流媒體業(yè)務(wù)正變得日益流行。然而網(wǎng)絡(luò)流媒體爆炸式的發(fā)展給傳統(tǒng)互聯(lián)網(wǎng)帶來巨大的壓力，視頻服務(wù)耗費(fèi)了大量的帶寬。目前視頻下載已經(jīng)成為占用公眾互聯(lián)網(wǎng)帶寬資源的主要業(yè)務(wù)之一，但是網(wǎng)絡(luò)運(yùn)營商從中獲益不多，他們不可能不計(jì)成本地?cái)U(kuò)展公眾互聯(lián)網(wǎng)的帶寬，因此網(wǎng)絡(luò)帶寬也制約著網(wǎng)絡(luò)視頻的發(fā)展。

事實(shí)上，多年來網(wǎng)絡(luò)一直沿著面向業(yè)務(wù)支撐的技術(shù)體系發(fā)展。為了滿足特性差異日益擴(kuò)大的用戶業(yè)務(wù)承載需求以及大量差異化業(yè)務(wù)的規(guī)?；瘧?yīng)用，面向服務(wù)提供的新型網(wǎng)絡(luò)技術(shù)體系也就是可重構(gòu)網(wǎng)絡(luò)[1,2]開始被越來越多的人關(guān)注。路由器作為關(guān)鍵網(wǎng)絡(luò)設(shè)備，已經(jīng)不能單純的追求提高設(shè)備性能，而是需要同步研究提高性能和擴(kuò)展功能，這是實(shí)現(xiàn)多網(wǎng)融合、業(yè)務(wù)融合的迫切需要?；诳芍貥?gòu)網(wǎng)絡(luò)的思想，劉強(qiáng)[3]等人提出了面向服務(wù)提供的可重構(gòu)路由器。而為了緩解流媒體高帶寬、低延遲的要求，本文提出一種新穎的基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略，該策略利用邊緣路由器的計(jì)算和存儲(chǔ)資源對熱點(diǎn)視頻對象進(jìn)行緩存與合作分發(fā)，從而減輕骨干網(wǎng)和服務(wù)器的負(fù)載，同時(shí)提高用戶的觀看體驗(yàn)。

現(xiàn)有2種最主要的流媒體分發(fā)加速方法分別為CDN(content delivery network)分布式緩存[4,5]和P2P(peer-to-peer)客戶端緩存[6～8]。CDN分布式緩存方法通過在網(wǎng)絡(luò)邊緣部署大量服務(wù)器來提高系統(tǒng)的服務(wù)能力，然而部署大量服務(wù)器花費(fèi)的代價(jià)很大，因此可擴(kuò)展性受到限制；P2P緩存技術(shù)充分利用客戶端的資源協(xié)同合作來減輕服務(wù)器的負(fù)載，但它給ISP帶來巨大的負(fù)擔(dān)。CDN和P2P技術(shù)分別從服務(wù)器和客戶端的角度來加速流媒體的分發(fā)，而被忽略的路由器如今性能與功能也越來越強(qiáng)大，不僅僅滿足于傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)，而是開始支持高層的業(yè)務(wù)處理。Cisco集成服務(wù)路由器上的應(yīng)用擴(kuò)展平臺(tái)(AXP, application extension platform)就提供了接口來實(shí)現(xiàn)分組分析、事件通知、網(wǎng)絡(luò)管理等托管應(yīng)用程序。另外路由器上配備的內(nèi)存容量也越來越大。

國內(nèi)外學(xué)者對利用網(wǎng)絡(luò)中間設(shè)備來改善網(wǎng)絡(luò)性能的方法也有一定的研究。HUA K等[8]提出一種緩存多播協(xié)議（CMP），CMP利用路由器的磁盤空間提供一小段滑動(dòng)窗口的視頻緩存來為接下來一段時(shí)間內(nèi)到達(dá)的同一視頻請求直接提供服務(wù)，從而減輕服務(wù)器的負(fù)載。CMP主要用于直播系統(tǒng)中的多播技術(shù)，在視頻點(diǎn)播中的使用效率不高。文獻(xiàn)[9]中描述了本文的前期工作，僅僅提出使用路由器緩存為流媒體分發(fā)服務(wù)的思想；本文中對路由器加速流媒體分發(fā)的策略進(jìn)行了延伸和具體闡述，從單個(gè)路由器擴(kuò)展到多個(gè)路由器合作的方式，并且提出了路由器上適合流媒體應(yīng)用的緩存算法以及多個(gè)路由器合作下的數(shù)據(jù)調(diào)度策略，最后還實(shí)現(xiàn)一個(gè)真實(shí)的原型系統(tǒng)，通過實(shí)驗(yàn)證明文中提出策略的有效性。

本文第2節(jié)介紹基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略；第3節(jié)對關(guān)鍵算法以及調(diào)度策略進(jìn)行研究；第4節(jié)給出原型系統(tǒng)測試結(jié)果并且進(jìn)行性能評價(jià)；最后對本文的內(nèi)容進(jìn)行歸納并對未來的工作進(jìn)行展望。

2 基于路由器緩存的流媒體協(xié)作分發(fā)

2.1 緩存架構(gòu)

傳統(tǒng)CDN網(wǎng)絡(luò)用于流媒體分發(fā)主要通過CDN服務(wù)器集群緩存熱門視頻以滿足大量的用戶請求。不管怎樣，部署服務(wù)器集群的代價(jià)實(shí)在太高。而在基于路由器的流媒體緩存新架構(gòu)中，本文增加一層路由器緩存。如圖1所示，CDN服務(wù)器和客戶端之間的多個(gè)路由器形成不同的本地緩存組，在 CDN服務(wù)器覆蓋下處于同一個(gè)自治域(AS)內(nèi)的路由器會(huì)被劃分在同一個(gè)本地緩存組中。路由器緩存層會(huì)對本地?zé)衢T的視頻數(shù)據(jù)進(jìn)行緩存，這樣局部大量訪問都集中在路由器緩存的熱門視頻上，從而數(shù)據(jù)在骨干網(wǎng)的傳輸量得到減少并且服務(wù)器的負(fù)載也得到減輕。當(dāng)然不是所有路由器都參與流媒體的協(xié)作分發(fā)，只有那些處在網(wǎng)絡(luò)邊緣的路由器才可能被選中。一方面是因?yàn)楹诵穆酚善餍枰幚矶嗵巺R聚過來的大量數(shù)據(jù)分組，沒有剩余的存儲(chǔ)以及計(jì)算能力去處理額外的應(yīng)用。而邊緣路由器的性能盡管比不上核心路由器，但是邊緣路由器承受的存儲(chǔ)轉(zhuǎn)發(fā)壓力會(huì)小很多，它擁有空閑的資源來存儲(chǔ)和分發(fā)流媒體數(shù)據(jù)。而且本文主要的目標(biāo)之一是減輕骨干網(wǎng)絡(luò)的負(fù)載，如果在核心路由器上進(jìn)行存儲(chǔ)，當(dāng)多個(gè)核心路由器協(xié)作分發(fā)的時(shí)候不可避免地會(huì)造成數(shù)據(jù)在骨干網(wǎng)絡(luò)中的大量傳輸，這與本文的優(yōu)化目標(biāo)是背道而馳的。另一方面，核心路由器一般與用戶有一定的距離，而邊緣路由器離用戶最近，只有一跳或者兩跳的距離，因此在這些距離用戶最近的邊緣路由器上存儲(chǔ)分發(fā)流媒體，可以極大地降低用戶響應(yīng)延遲以及數(shù)據(jù)傳輸延遲，從而提高用戶體驗(yàn)。

圖1 基于路由器的流媒體緩存架構(gòu)

2.2 分發(fā)方法

圖2 傳統(tǒng)CDN分發(fā)與基于路由器的分發(fā)

在傳統(tǒng)CDN分發(fā)方法中，用戶請求會(huì)被重定向到CDN服務(wù)器，然后由該CDN服務(wù)器提供服務(wù)，如圖2(a)所示。而在基于路由器緩存的協(xié)作分發(fā)策略中，緩存路由器距離用戶更近并且路由器之間不需要重定向。如圖2(b)所示，用戶請求會(huì)被距離該客戶端最近的邊緣路由器截取，該邊緣路由器稱為此客戶端的家路由器。家路由器截取用戶請求后，在緩存中查找用戶請求的視頻段，同時(shí)家路由器會(huì)向同一個(gè)本地緩存組中的合作路由器發(fā)送資源查詢命令，合作路由器接收到資源查詢命令后，會(huì)在自己的緩存列表中查找該視頻段的數(shù)據(jù)；隨后合作路由器會(huì)將查詢結(jié)果反饋給家路由器，同時(shí)向客戶端推送緩存命中的數(shù)據(jù)。對于家路由器來說，它不僅需要向客戶端推送數(shù)據(jù)，還需要收集合作路由器的反饋信息，根據(jù)這些反饋信息以及自身的存儲(chǔ)情況做出判斷，以決定是否需要向 CDN服務(wù)器請求額外的數(shù)據(jù)。如果整個(gè)本地緩存組中緩存的數(shù)據(jù)足以還原客戶端所需的視頻數(shù)據(jù)，則家路由器不會(huì)向 CDN服務(wù)器請求額外的數(shù)據(jù)；如果整個(gè)本地緩存組中緩存的數(shù)據(jù)不足以還原出客戶端請求的視頻數(shù)據(jù)，則家路由器會(huì)將請求轉(zhuǎn)發(fā)到 CDN管理中心，此時(shí)就像是家路由器代替客戶端向服務(wù)器發(fā)起了一個(gè)請求，以后的過程和一個(gè)普通客戶端請求服務(wù)沒有區(qū)別，首先該請求會(huì)被轉(zhuǎn)發(fā)到CDN管理中心，然后由CDN管理中心把該請求重定向到某個(gè)最合適的 CDN服務(wù)器，最后由該 CDN服務(wù)器協(xié)助視頻段的數(shù)據(jù)分發(fā)。與傳統(tǒng) CDN分發(fā)不同的是，家路由器會(huì)根據(jù)自身的緩存策略對 CDN服務(wù)器分發(fā)的數(shù)據(jù)進(jìn)行緩存，以便對該視頻段的同一請求提供服務(wù)。在CDN服務(wù)器和客戶端之間增加路由器緩存并且采用合適的緩存算法對熱門視頻數(shù)據(jù)進(jìn)行緩存后，根據(jù)80/20原則（即80%的用戶訪問都集中于20%的熱門視頻），大部分的用戶訪問都不需要重定向到CDN服務(wù)器，而是直接由本地的緩存路由器組來提供服務(wù)，這極大地提高了用戶體驗(yàn)。

在統(tǒng)計(jì)本地緩存組中所有緩存路由器上的數(shù)據(jù)時(shí)，家路由器只需要統(tǒng)計(jì)屬于該視頻段的塊數(shù)是否足夠，而不用考慮從哪個(gè)路由器節(jié)點(diǎn)獲取不同的數(shù)據(jù)，這主要得益于網(wǎng)絡(luò)編碼[10]的引入。通過對原始視頻數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)編碼得到不同的數(shù)據(jù)塊，這些不同的數(shù)據(jù)塊內(nèi)容不相同，但是它們存儲(chǔ)的信息量是相當(dāng)?shù)亩业匚皇峭戎匾?。換言之，只需要足夠數(shù)量的任意塊編碼過的數(shù)據(jù)即可還原出原始視頻段，而不必關(guān)心具體是哪些數(shù)據(jù)塊。因此家路由器僅僅需要統(tǒng)計(jì)塊數(shù)是否足夠，而緩存路由器也只要向客戶端不斷推送該視頻段的數(shù)據(jù)塊直到客戶端不再需要數(shù)據(jù)向路由器發(fā)送剎車消息為止，這樣的策略大大簡化路由器上的處理以及數(shù)據(jù)的調(diào)度，關(guān)于如何對原始視頻段的數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)編碼將會(huì)在下一節(jié)詳細(xì)介紹。

3 關(guān)鍵算法與調(diào)度策略研究

為了能實(shí)現(xiàn)路由器參與流媒體的分發(fā)，本文設(shè)計(jì)了路由器鄰居節(jié)點(diǎn)選擇算法，路由器上的分組處理算法，并且研究討論路由器上合適的緩存替換算法來提高路由器緩存的利用率以及網(wǎng)絡(luò)編碼簡化數(shù)據(jù)調(diào)度的方法。

3.1 鄰居節(jié)點(diǎn)選擇算法

為了提高緩存路由器之間協(xié)作的性能，只有處在同一個(gè)本地緩存組中即同一個(gè)AS域內(nèi)的路由器才會(huì)相互協(xié)作共同為用戶提供服務(wù)，而不是任意的緩存路由器之間都可以互相合作。如何為路由器選擇合適的鄰居節(jié)點(diǎn)將直接影響路由器之間緩存協(xié)作的性能。

一般情況下，同一個(gè)自治域內(nèi)2個(gè)節(jié)點(diǎn)之間的傳輸延遲相對比較小，因此可以快速查詢到所需的視頻資源，然后為用戶提供服務(wù)，從而降低用戶的響應(yīng)時(shí)間以及數(shù)據(jù)的平均傳輸時(shí)間。緩存路由器是根據(jù)其所在自治域的ASN（自治域號(hào)）來獲得鄰居節(jié)點(diǎn)列表的。當(dāng)緩存路由器加入一個(gè)流媒體分發(fā)組中時(shí)，它首先向服務(wù)器進(jìn)行注冊。在注冊過程中該路由器擁有的ASN會(huì)被記錄在服務(wù)器上，而服務(wù)器會(huì)將已經(jīng)在該服務(wù)器上登記過擁有相同ASN的路由器節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)告知新加入的緩存路由器，同時(shí)更新原有組中所有路由器的鄰居列表。由于路由器一般不會(huì)宕機(jī)也不會(huì)頻繁加入退出，因此不同的本地緩存組一旦形成以后就很少會(huì)發(fā)生變化。

3.2 路由器上分組處理算法

緩存路由器除了正常的存儲(chǔ)轉(zhuǎn)發(fā)功能之外，還需要處理的額外數(shù)據(jù)分組可以劃分為如表1所示的幾種類型。

表1 路由器上處理的數(shù)據(jù)分組類型

根據(jù)表1中數(shù)據(jù)分組的不同類型，緩存路由器只需要在接收到分組后做出相應(yīng)的處理即可。比如路由器接收到BRAKING類型的數(shù)據(jù)分組后就停止向該客戶端推送緩存的數(shù)據(jù)。路由器上的分組處理如圖3所示。其中，PT表示數(shù)據(jù)分組的類型，Q表示數(shù)據(jù)分組隊(duì)列，N表示本地緩存組中存儲(chǔ)的當(dāng)前請求視頻的總塊數(shù)，Threshold表示能夠還原出原始數(shù)據(jù)最少需要的編碼塊數(shù)。該算法實(shí)現(xiàn)后作為一個(gè)托管應(yīng)用程序嵌入到每個(gè)緩存路由器中，因此路由器能夠輕松完成流媒體的分發(fā)。

圖3 路由器上分組處理算法

3.3 緩存替換算法

路由器上緩存是有限的，當(dāng)緩存滿的時(shí)候，就需要根據(jù)一定的規(guī)則對緩存內(nèi)容進(jìn)行替換。這里需要說明的是緩存路由器本身運(yùn)行系統(tǒng)以及完成路由等功能與流媒體數(shù)據(jù)緩存是共享內(nèi)存的。而路由器上引入流媒體緩存不能影響路由器原有功能的運(yùn)行，因此，在本方案中僅僅使用路由器上剩余的緩存資源（之前已經(jīng)提及目前的路由器存儲(chǔ)容量可以很大，有能力完成除傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)之外的一些功能），本文以后提到的緩存都指路由器上運(yùn)行原有功能后剩余的緩存資源。

目前比較流行的流媒體緩存算法是基于流行度的流媒體段緩存算法[11]，該算法通過分析視頻流行度分布，按照流行度從高到低依次緩存，如圖4(a)的一級(jí)隊(duì)列緩存所示。但是在緩存十分有限的情況下，僅僅存儲(chǔ)最熱門的幾部視頻并不能明顯提高流媒體系統(tǒng)的整體性能；而且據(jù)相關(guān)研究[12]用戶開始觀看的一段時(shí)間內(nèi)最容易離開，因此存儲(chǔ)視頻開始部分的數(shù)據(jù)顯得更有意義。將傳統(tǒng)的一級(jí)隊(duì)列改進(jìn)為兩級(jí)緩存隊(duì)列，分別為hot隊(duì)列和cold隊(duì)列，如圖 4(b)所示。hot隊(duì)列中存儲(chǔ)流行度最高的完整視頻數(shù)據(jù)并且hot隊(duì)列中存儲(chǔ)的視頻都必須達(dá)到一個(gè)訪問次數(shù)門限值，只有訪問次數(shù)達(dá)到該門限值的視頻才能存儲(chǔ)在hot隊(duì)列中；而cold隊(duì)列中存儲(chǔ)流行度次之的視頻開始部分?jǐn)?shù)據(jù)，它們沒有訪問次數(shù)的限制，目的是為了能夠擴(kuò)大路由器上存儲(chǔ)的視頻數(shù)范圍，從而降低用戶的平均初始響應(yīng)延遲。

圖4 緩存算法改進(jìn)

當(dāng)路由器上接收到視頻數(shù)據(jù)并且需要進(jìn)行緩存時(shí)，路由器首先會(huì)在2個(gè)隊(duì)列中查找，隊(duì)列中存儲(chǔ)的僅僅是緩存視頻內(nèi)容的索引，而不是真正的數(shù)據(jù)。如果緩存命中，判斷該視頻是在哪個(gè)隊(duì)列中，如果是在hot隊(duì)列中，則只需要將該視頻訪問次數(shù)加1即可；如果該視頻在cold隊(duì)列命中，則需要判斷該視頻的訪問次數(shù)是否達(dá)到hot隊(duì)列的訪問次數(shù)門限值，如果訪問次數(shù)達(dá)到該門限值，則用該視頻替換hot隊(duì)列中效率值P最低的視頻，hot隊(duì)列中被替換的視頻并不會(huì)丟棄而是會(huì)被替換到 cold隊(duì)列中。其中，P=訪問次數(shù)/最久未被訪問時(shí)間，P值越高，視頻越不可能被替換。如果訪問次數(shù)未達(dá)到門限值，則該視頻僅僅存儲(chǔ)在cold隊(duì)列中并且只存儲(chǔ)開始的部分?jǐn)?shù)據(jù)。如果緩存沒有命中，則按照hot到cold的順序查詢空位置進(jìn)行插入操作，如果2個(gè)隊(duì)列都已滿則替換 cold隊(duì)列中最久未被訪問的視頻。該緩存算法結(jié)合了傳統(tǒng)基于流行度的緩存方法與用戶觀看行為的特點(diǎn)，能夠很好地提升整個(gè)訪問群體的用戶體驗(yàn)。

3.4 調(diào)度算法

在流媒體數(shù)據(jù)調(diào)度中，網(wǎng)絡(luò)編碼被用于簡化調(diào)度。網(wǎng)絡(luò)編碼是一種融合了路由和編碼的信息交換技術(shù)，它是R.Ahlswede[10]等人在2000年提出的理論，它的核心思想是在網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)上對多條信道上收到的信息進(jìn)行線性或者非線性的處理，將多個(gè)數(shù)據(jù)分組做編碼“融合”在一起，然后轉(zhuǎn)發(fā)給下游節(jié)點(diǎn)，這樣就能夠提升整個(gè)網(wǎng)絡(luò)的吞吐率。本文的調(diào)度策略中引入隨機(jī)線性網(wǎng)絡(luò)編碼[13,14]后，所有編碼以后的數(shù)據(jù)塊將被一視同仁地對待，這樣可以簡單地實(shí)現(xiàn)基于push[15]策略的路由器協(xié)作傳輸，從而提升數(shù)據(jù)傳輸?shù)男剩煌瑫r(shí)，網(wǎng)絡(luò)編碼可以降低路由器協(xié)作的調(diào)度復(fù)雜度。引入網(wǎng)絡(luò)編碼后的數(shù)據(jù)調(diào)度如圖5所示，首先在服務(wù)器上將視頻段進(jìn)行分塊，假設(shè)每個(gè)視頻段分為k個(gè)數(shù)據(jù)塊，然后在有限域上隨機(jī)選取 N個(gè)線性無關(guān)的編碼向量（通常N>k），將N個(gè)編碼向量與k個(gè)數(shù)據(jù)塊通過有限域上的乘法得到N個(gè)新的編碼塊，然后這些編碼塊在第一次經(jīng)過緩存路由器時(shí)會(huì)被緩存下來。當(dāng)有用戶再次請求該視頻段的數(shù)據(jù)時(shí)，這些緩存路由器會(huì)直接向用戶push屬于該視頻段的編碼塊，而用戶只要收足任意k個(gè)編碼塊就可以解碼恢復(fù)出原始的k個(gè)數(shù)據(jù)塊。

圖5 網(wǎng)絡(luò)編碼簡化數(shù)據(jù)調(diào)度方法

引入網(wǎng)絡(luò)編碼后，不同緩存路由器上存儲(chǔ)的數(shù)據(jù)本質(zhì)上都是相同的，而客戶端只需要得到足夠的編碼塊數(shù)就可以還原出原始的視頻數(shù)據(jù)，因此緩存路由器在向客戶端提供數(shù)據(jù)的時(shí)候只需要簡單地向客戶端push屬于該視頻段的編碼塊即可，從而簡化了路由器協(xié)作時(shí)的數(shù)據(jù)調(diào)度，降低了系統(tǒng)實(shí)現(xiàn)的復(fù)雜度。

4 性能評價(jià)

4.1 實(shí)驗(yàn)環(huán)境初始化

為了評價(jià)基于路由器上緩存的流媒體協(xié)作分發(fā)策略的性能，本文實(shí)現(xiàn)了一個(gè)原型系統(tǒng)。在該原型系統(tǒng)中，路由器上緩存算法、分組處理等關(guān)鍵算法得以實(shí)現(xiàn)。另外，網(wǎng)絡(luò)編碼也被引入來簡化系統(tǒng)的復(fù)雜度。實(shí)驗(yàn)環(huán)境為1臺(tái)源服務(wù)器和 1臺(tái)CDN服務(wù)器、3臺(tái)緩存路由器以及若干臺(tái)PC客戶端組成的原型系統(tǒng)。實(shí)驗(yàn)的初始化設(shè)置以及部分參數(shù)如表2所示，實(shí)驗(yàn)中共有20套視頻節(jié)目，這些視頻的熱門度分布服從θ=0.27的Zipf分布。原型系統(tǒng)中使用的路由器內(nèi)存大小為8GB，而邊緣路由器的內(nèi)存大小一般都不超過4GB，因此，在實(shí)驗(yàn)中使用3GB的內(nèi)存容量用于緩存視頻數(shù)據(jù)是可行的，即在保證不影響路由器處理傳統(tǒng)業(yè)務(wù)的基礎(chǔ)上使用剩余的內(nèi)存來緩存視頻數(shù)據(jù)。實(shí)際上，除了使用內(nèi)存來緩存視頻數(shù)據(jù)，路由器上也可以連接外部的大容量存儲(chǔ)器來擴(kuò)展整個(gè)存儲(chǔ)空間，不過必然會(huì)帶來一定量的延遲。參數(shù)緩存比例R表示所有緩存路由器上的緩存大小之和占服務(wù)器上所有視頻內(nèi)容總和的比例（本實(shí)驗(yàn)中3個(gè)路由器上緩存總和占服務(wù)器上所有視頻總和的比例即為緩存比例R）。實(shí)驗(yàn)中R從0變化到0.5，意味著每個(gè)路由器用于緩存視頻數(shù)據(jù)的內(nèi)存容量從0增加到3GB，因?yàn)槁酚善髦g是相互合作緩存的，所以整個(gè)本地緩存組的緩存大小將從0增加到9GB。其中，R=0表示沒有引入路由器緩存策略，為傳統(tǒng)普通CDN分發(fā)策略。

表2 實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 服務(wù)器帶寬

圖6描述了路由器上的緩存大小對服務(wù)器帶寬的影響，實(shí)際上該服務(wù)器可以是內(nèi)容提供商的內(nèi)容服務(wù)器也可以是 CDN服務(wù)器，本文方案中的路由器位于網(wǎng)絡(luò)的邊緣，因此不管是內(nèi)容提供商自己的服務(wù)器還是 CDN服務(wù)器都可以使用邊緣路由器對其減負(fù)。圖6中，隨著緩存比例R的增大(本地緩存組緩存從0到緩存50%)，很顯然服務(wù)器帶寬消耗呈現(xiàn)下降的趨勢。但并不是緩存越大越好，一方面路由器上的緩存空間有限，另一方面隨著緩存的增加，服務(wù)器帶寬消耗會(huì)趨向于一個(gè)穩(wěn)定的值，因?yàn)榧词谷恳曨l都存儲(chǔ)在路由器上，服務(wù)器還是需要消耗一定的帶寬來處理客戶端的連接、路由器的流量統(tǒng)計(jì)、數(shù)據(jù)重傳等事務(wù)。從圖6中用戶數(shù)N=500的曲線可以看出，當(dāng)緩存比例R達(dá)到0.3的時(shí)候，服務(wù)器帶寬消耗(60Mbit/s)比不使用路由器緩存的傳統(tǒng) CDN分發(fā)方案（服務(wù)器帶寬消耗 240Mbit/s)減少 75%左右，因此沒有必要無限增加緩存的大小，只需要緩存30%左右的數(shù)據(jù)即可。圖6中3條曲線分別描述了不同并發(fā)用戶數(shù)的情況下緩存大小對服務(wù)器帶寬消耗的影響。很明顯可以看到，當(dāng)用戶數(shù)從100增加到500的過程中，在沒有路由器緩存即采用傳統(tǒng) CDN分發(fā)方案的情況下，服務(wù)器帶寬消耗增加接近 200Mbit/s；而在緩存比例 R僅為0.1的情況下，服務(wù)器帶寬消耗只增加了115Mbit/s左右，比傳統(tǒng)方案增加的帶寬消耗要少的多。因此基于路由器上緩存的流媒體協(xié)作分發(fā)策略對流媒體系統(tǒng)的可擴(kuò)展性有非常大的幫助，而且有利于開展大規(guī)模流媒體的分發(fā)服務(wù)。

圖6 緩存大小對服務(wù)器帶寬消耗的影響

4.2.2 平均初始響應(yīng)時(shí)間

初始響應(yīng)延遲是用戶體驗(yàn)的一個(gè)重要指標(biāo)之一。初始響應(yīng)延遲為用戶點(diǎn)擊視頻請求到用戶可以觀看該視頻的一段緩沖時(shí)間。實(shí)驗(yàn)中設(shè)置緩沖 60s的視頻數(shù)據(jù)。圖7分別描述了緩存大小和緩存策略對平均初始響應(yīng)延遲的影響。如圖7(a)所示，隨著并發(fā)用戶從100增加到300再到500，在有路由器緩存策略的情況下，平均初始響應(yīng)延遲都降低了至少50%，用戶體驗(yàn)得到很大的提升。另外隨著并發(fā)用戶數(shù)的增加，在沒有路由器緩存的傳統(tǒng) CDN分發(fā)策略下，平均初始響應(yīng)時(shí)間增加的非?？?，從22s增加到超過50s，增幅達(dá)到100%以上；而在有路由器緩存的情況，平均初始響應(yīng)延遲增加的速度顯然要慢的多。因此，引入路由器緩存將會(huì)極大地提升用戶體驗(yàn)，一方面得益于緩存路由器都位于網(wǎng)絡(luò)的邊緣，距離用戶非常近，在用戶請求后可以快速地給用戶提供服務(wù)；另一方面路由器上使用的是內(nèi)存而且存儲(chǔ)的是編碼以后的數(shù)據(jù)塊，不像服務(wù)器需要從磁盤中讀出原始數(shù)據(jù)并且進(jìn)行編碼。

圖7 不同緩存大小以及策略下平均響應(yīng)延遲的變化

圖7(b)描述了改進(jìn)后的緩存算法對平均初始響應(yīng)延遲的影響。當(dāng)緩存策略從一級(jí)隊(duì)列改進(jìn)為hot、cold 兩級(jí)隊(duì)列緩存后，平均初始響應(yīng)延遲得到很大的改善，原因在于 hot、cold兩級(jí)隊(duì)列緩存策略合理地運(yùn)用了路由器上的有限緩存空間。通過cold隊(duì)列對次流行視頻開始部分的數(shù)據(jù)進(jìn)行緩存，擴(kuò)展了視頻存儲(chǔ)的范圍，增加了路由器上有限緩存服務(wù)的用戶數(shù)。

4.2.3 平均數(shù)據(jù)傳輸時(shí)間

數(shù)據(jù)傳輸延遲為數(shù)據(jù)從服務(wù)器(這里的服務(wù)器可能是緩存路由器，而客戶端是不知道的，路由器提供的是透明服務(wù))傳輸?shù)娇蛻舳怂玫臅r(shí)間。圖 8(a)描述了不同并發(fā)用戶數(shù)下路由器上的緩存大小對平均數(shù)據(jù)傳輸延遲的影響。整體上來看，隨著并發(fā)用戶數(shù)的增加，在無路由器緩存的傳統(tǒng)CDN分發(fā)策略下(R=0.0)，平均數(shù)據(jù)傳輸延遲在用戶數(shù)從300到500的時(shí)候有一個(gè)明顯的增加，說明用戶數(shù)達(dá)到 500的時(shí)候服務(wù)器和客戶端之間的鏈路存在一定的擁堵，導(dǎo)致數(shù)據(jù)傳輸時(shí)間的增加；而在有緩存的情況下(R=0.1或 R=0.2)，平均數(shù)據(jù)傳輸延遲都沒有出現(xiàn)明顯的增加，說明引入路由器緩存后，整個(gè)系統(tǒng)的性能以及服務(wù)能力均得到了提升。當(dāng)并發(fā)用戶數(shù)相同的時(shí)候，可以明顯看出有緩存比沒有緩存的情況平均數(shù)據(jù)傳輸延遲降低了至少 50%，主要原因在于緩存路由器距離用戶比服務(wù)器更近，數(shù)據(jù)在本地緩存組中的路由器上緩存后，可以很快地分發(fā)給用戶而不需要較遠(yuǎn)的服務(wù)器來分發(fā)。

圖8(b)描述了不同緩存策略對平均數(shù)據(jù)傳輸延遲的影響。與一級(jí)隊(duì)列緩存策略相比，盡管兩級(jí)隊(duì)列緩存策略中 cold隊(duì)列存儲(chǔ)了一些次熱門視頻的開始部分?jǐn)?shù)據(jù)，而不是最熱門視頻數(shù)據(jù)，但是平均數(shù)據(jù)傳輸延遲并沒有太多的變化，說明 hot、cold兩級(jí)隊(duì)列緩存策略的引入不會(huì)帶來平均數(shù)據(jù)傳輸延遲的增加。

圖8 不同緩存大小以及策略下平均數(shù)據(jù)傳輸延遲的變化

4.2.4 存儲(chǔ)與計(jì)算開銷

迄今為止，本文只關(guān)注路由器上緩存所帶來的好處。不管怎樣，引入路由器緩存來加速流媒體的分發(fā)必然會(huì)給路由器帶來一定的開銷，主要包括存儲(chǔ)資源和計(jì)算資源的開銷。存儲(chǔ)資源消耗是顯而易見的，而計(jì)算資源的消耗如圖9所示。當(dāng)并發(fā)用戶數(shù)增加的時(shí)候，路由器上的 CPU額外開銷也隨之增大，但增加的并不是很多，對于路由器來說5%以下的額外 CPU開銷完全是可以接受的。當(dāng)并發(fā)用戶數(shù)相同時(shí)，路由器上緩存的增加并沒有帶來很多額外的 CPU資源消耗?？偟膩碚f，利用路由器上緩存協(xié)作分發(fā)流媒體的策略并沒有消耗路由器上太多的計(jì)算資源，完全在可接受范圍之內(nèi)，而且該策略還對路由器上的剩余存儲(chǔ)資源進(jìn)行了高效的利用。

圖9 引入緩存后路由器上額外的計(jì)算開銷

5 結(jié)束語

本文提出了一種基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略，通過將邊緣路由器組織成本地緩存組，本地緩存組中的路由器對熱門視頻數(shù)據(jù)進(jìn)行主動(dòng)緩存，在用戶進(jìn)行請求時(shí)可以直接提供服務(wù)。通過對原型系統(tǒng)的實(shí)驗(yàn)結(jié)果分析表明，邊緣路由器上緩存的方法可以明顯地減輕服務(wù)器負(fù)載，降低用戶的平均初始響應(yīng)時(shí)間和數(shù)據(jù)傳輸時(shí)間，可以極大地提升用戶體驗(yàn)。該基于路由器上緩存的流媒體協(xié)作分發(fā)策略可以適用于大規(guī)模流媒體的分發(fā)，對于構(gòu)建下一代網(wǎng)絡(luò)有著積極的意義。

路由器上業(yè)務(wù)感知的方法以及對更多業(yè)務(wù)流的加速策略研究將是下一步工作的內(nèi)容。通過對路由器上業(yè)務(wù)感知方法的深入研究來使得路由器可以支持更多的業(yè)務(wù)加速；另外雖然P2P給ISP帶來巨大的流量負(fù)載，但是P2P技術(shù)對服務(wù)器帶寬需求的降低做出了巨大的貢獻(xiàn)，利用邊緣路由器對P2P資源進(jìn)行合理的整合以及優(yōu)化，從而更好地改善網(wǎng)絡(luò)環(huán)境將是下一步工作的另一個(gè)思路。

[1]李鵬, 蘭巨龍.一種新型的可重構(gòu)路由交換通用平臺(tái)[J].計(jì)算機(jī)應(yīng)用研究，2009，26(6):2016-2019.LI P, LAN J L.New reconfigurable general platform for routing/switching nodes[J].Application Research of Computers, 2009,26(6):2016-2019.

[2]李黎,管曉宏,蔡忠閩等.可重構(gòu)網(wǎng)絡(luò)系統(tǒng)的模型及體系結(jié)構(gòu)[J].小型微型計(jì)算機(jī)系統(tǒng)，2009, 30(4):637-641.LI L, GUANG X H, CAI Z M, et al Reconfigurable network model and architecture[J].Journal of Chinese Computer Systems, 2009,30(4):637-641.

[3]劉強(qiáng), 汪斌強(qiáng), 徐恪.面向服務(wù)提供的可重構(gòu)路由器[J].中國教育網(wǎng)絡(luò), 2010, (7):49-51.LIU Q, WANG B Q, XU K.Service-oriented reconfigurable routers[J].China Education Network, 2010, (7):49-51.

[4]BORST S, GUPTA V, A WALID.Distributed caching algorithms for content distribution networks[A].INFOCOM, 2010 Proceedings IEEE 2010[C].2010.

[5]WEE S, APOSTOLOPOULOS J, TAN W, et al.Research and design of a mobile streaming media content delivery network[A].IEEE International Multimedia Conference and Expo (ICME)[C].Baltimore,MD, 2003.

[6]HUANG Y, TOM F, et al.Challenges, design and analysis of a large-scale P2P-vod system[A].Proceedings of the ACM SIGCOMM[C].2008.

[7]YU H L, ZHENG D D, et al.Understanding user behavior in large-scale video-on-demand systems[A].ACM SIGOPS Operating System Review[C].2006.

[8]K.HUA，D.TRAN, R.VILLAFANE.Caching multicast protocol for on-demand video delivery[A].Proceedings of S&T/SPIE Conference on Multimedia Computing and Networking (MMCN)[C].Citeseer,2000.

[9]ZHONG J W, HE Z C, et al.Router caching for video streaming systems[A].Proceedings of USENIX Conference on File and Storage Technologies[C].2010.

[10]R.AHLSWEDE, CAI N, LI S Y.Network information flow[J].IEEE Trans Information Theory, 2000, 46(4):1204-1216.

[11]WU K L, YU S P, WOLF J L.Segment-based proxy caching of multi media streams[A].Proceedings of the 10th international conference on World Wide Web[C].May 2001.

[12]CHENG X, LIU J.NetTube:Exploring social networks for peer-to-peer short video sharing[A].INFOCOM 2009[C].2009.

[13]LI S Y, CAI N.Linear network coding[J].IEEE Trans Information Theory, 2003, 49(2):371-381.

[14]CHRISTOS G, PABLO R.Network coding for large scale content Distribution[A].INFOCOM[C].2005.

[15]SUH K, DIOT C, KIROSE J.Push-to-peer video-on-demand system design and evaluation[J].IEEE Journal on Selected Areas in Communications, Special on Advances in Peer-to-Peer Streaming Systems,2007, 25(9):1706-1716.