一種基于時(shí)移電視系統(tǒng)的副本放置策略*

韓國(guó)棟，朱一戈

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

時(shí)移電視[1](Time-Shifted Television)作為IPTV的一種，允許用戶進(jìn)行暫停、快進(jìn)和后退等操作，也可以選擇幾天前的電視節(jié)目，是一種極具吸引力的服務(wù)。不同于一般的網(wǎng)絡(luò)電視，時(shí)移電視需要對(duì)每個(gè)用戶分配一個(gè)信道，不能通過(guò)組播的方式將節(jié)目數(shù)據(jù)推送給用戶。同時(shí)，由于電視信道所需帶寬較高[2]，現(xiàn)有內(nèi)容分發(fā)網(wǎng) CDN(Content Distribution Networks)的體系結(jié)構(gòu)難以滿足業(yè)務(wù)要求，對(duì)服務(wù)提供者提出了挑戰(zhàn)。

P2P技術(shù)有效打破了CDN中代理服務(wù)器的C/S模式。網(wǎng)絡(luò)中的節(jié)點(diǎn)既是用戶又是服務(wù)器，使用戶能從最近的對(duì)等節(jié)點(diǎn)中下載相應(yīng)流式數(shù)據(jù)，從而有效避免熱點(diǎn)服務(wù)器過(guò)載,減少電視頻道切換響應(yīng)時(shí)延[3](Zap Response Time)。

副本放置技術(shù)常用來(lái)解決這種熱點(diǎn)問(wèn)題。通過(guò)對(duì)熱門副本進(jìn)行有策略的放置，減輕相關(guān)熱點(diǎn)資源節(jié)點(diǎn)的負(fù)載，縮短請(qǐng)求消息搜索路徑，提高消息搜索成功率，降低請(qǐng)求響應(yīng)時(shí)延。P2P網(wǎng)絡(luò)副本放置方法分為三種：服務(wù)端副本放置方法、客戶端副本放置方法和路徑放置方法。參考文獻(xiàn) [4]將純P2P網(wǎng)絡(luò)歸納為損失模型（loss network model），將文件按熱、中、冷三種類型放置到各個(gè)節(jié)點(diǎn)中，從而實(shí)現(xiàn)各節(jié)點(diǎn)上行帶寬使用率的最大化。參考文獻(xiàn)[5]在結(jié)構(gòu)化P2P網(wǎng)絡(luò)的基礎(chǔ)上，提出了一種最優(yōu)副本放置算法,有效平衡了性能與開(kāi)銷之間的關(guān)系。參考文獻(xiàn)[6]通過(guò)研究現(xiàn)有P2P網(wǎng)絡(luò)上運(yùn)行的IPTV業(yè)務(wù)的提高方法，指出了一系列緩存管理和副本放置方法。另外，參考文獻(xiàn)[7]也對(duì)P2P上的流媒體業(yè)務(wù)進(jìn)行了分析和建模。但是，現(xiàn)有的研究存在以下問(wèn)題：首先，現(xiàn)有算法大都是基于P2P存儲(chǔ)系統(tǒng)，以整個(gè)文件為基礎(chǔ)進(jìn)行處理，不符合流式傳輸?shù)臄?shù)據(jù)存儲(chǔ)方式；其次，沒(méi)有考慮到不同數(shù)據(jù)類型的差別，單純地將數(shù)據(jù)分為熱點(diǎn)數(shù)據(jù)和冰點(diǎn)數(shù)據(jù)，降低了冷門節(jié)目的服務(wù)質(zhì)量。

本文針對(duì)時(shí)移電視系統(tǒng)中的副本放置問(wèn)題，提出一種混合副本放置策略。通過(guò)分析IPTV編碼方式和流式數(shù)據(jù)傳輸特性,考慮網(wǎng)絡(luò)拓?fù)鋵?duì)放置策略的影響，以及負(fù)載均衡等要求,自適應(yīng)地將數(shù)據(jù)片放置在節(jié)點(diǎn)中,就近為用戶提供服務(wù),從而有效提高用戶體驗(yàn)度和系統(tǒng)性能。

1 問(wèn)題分析

1.1 系統(tǒng)模型

本文分析的時(shí)移電視系統(tǒng)的結(jié)構(gòu)中，源服務(wù)器RS(Resource Server)通過(guò)組播的方式將內(nèi)容推送到各地的代理服務(wù)器VHO(Video Hub Office)。本地各設(shè)備(如機(jī)頂盒、計(jì)算機(jī)和手機(jī)等）間通過(guò)無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)連接，分享節(jié)目數(shù)據(jù)。VHO中存儲(chǔ)著所有當(dāng)前電視節(jié)目?jī)?nèi)容數(shù)據(jù)，并通過(guò)分層編碼技術(shù)（Layered Encoding）和多描述編碼技術(shù) MDC(Multi-description Coding)，將不同質(zhì)量的視頻內(nèi)容傳送到不同用戶的設(shè)備中。

本文主要關(guān)注時(shí)移電視節(jié)目數(shù)據(jù)在系統(tǒng)中的放置問(wèn)題。由于所有電視數(shù)據(jù)都已存儲(chǔ)在VHO中，因此本文的數(shù)據(jù)放置問(wèn)題可進(jìn)一步簡(jiǎn)化成流式數(shù)據(jù)在P2P網(wǎng)絡(luò)中的管理問(wèn)題。

1.2 副本放置問(wèn)題分析

P2P網(wǎng)絡(luò)中的副本放置問(wèn)題是一個(gè)NP完全問(wèn)題（NP-Complete）[8]。為了協(xié)調(diào)全局負(fù)載均衡和請(qǐng)求的響應(yīng)時(shí)延最小化兩種優(yōu)化目標(biāo)，本文考察節(jié)點(diǎn)的能力（帶寬大小和存儲(chǔ)容量）以及節(jié)點(diǎn)之間的距離，提出近似最優(yōu)解決方案。

(1)負(fù)載均衡問(wèn)題

設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合由V表示,共計(jì)n個(gè)節(jié)點(diǎn)，其中節(jié)點(diǎn) i記作 Vi。

定義1：節(jié)點(diǎn)Vi的負(fù)載Li，表示節(jié)點(diǎn)響應(yīng)用戶請(qǐng)求，分享數(shù)據(jù)所帶來(lái)的帶寬使用代價(jià)等。設(shè)節(jié)點(diǎn)Vi中存儲(chǔ)著數(shù)據(jù)片集合 Xi，每個(gè)數(shù)據(jù)片的訪問(wèn)次數(shù)為 fx，則負(fù)載Li可表示為：

這樣，負(fù)載均衡度可以表示為：

目前，大多數(shù)P2P系統(tǒng)中的查詢消息都是通過(guò)流言機(jī)制查詢來(lái)實(shí)現(xiàn)的。因此，通過(guò)復(fù)制技術(shù)，有計(jì)劃地將副本放置在路由節(jié)點(diǎn)，能夠在提高消息搜索成功率的基礎(chǔ)上控制整個(gè)系統(tǒng)的流量，提高網(wǎng)絡(luò)利用效率。

(2)最小化響應(yīng)時(shí)延問(wèn)題

影響用戶請(qǐng)求響應(yīng)時(shí)延的因素包括消息搜索成功率以及節(jié)點(diǎn)之間的互協(xié)作性。好的副本放置方案能夠使用戶快速而成功地搜索到所需的數(shù)據(jù)，同時(shí)能夠就近獲取以實(shí)現(xiàn)最小化響應(yīng)時(shí)延。

定義 2：節(jié)點(diǎn) Vi與節(jié)點(diǎn) Vj的距離di,j。節(jié)點(diǎn) Vj中有數(shù)據(jù)片，而節(jié)點(diǎn) Vi上沒(méi)有相應(yīng)數(shù)據(jù)，則di,j表示節(jié)點(diǎn) Vi需要從節(jié)點(diǎn)Vj獲取相應(yīng)數(shù)據(jù)的跳數(shù)。則節(jié)點(diǎn)Vi需獲取為存儲(chǔ)數(shù)據(jù)的距離di為：

在查詢消息路由算法一定的情況下,節(jié)點(diǎn)Vi接收查詢消息的能力和兩方面有關(guān)系：(1)節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置。節(jié)點(diǎn)連接度越大其查詢消息接受的概率就越大[9]，轉(zhuǎn)發(fā)的通訊量就更多。這樣，節(jié)點(diǎn)獲得的信息就更加全面，能提高消息搜索成功率。(2)路由器周圍用戶節(jié)點(diǎn)的活躍程度，即區(qū)域用戶在線率。因?yàn)?，一旦詢?wèn)周圍用戶節(jié)點(diǎn)擁有所需數(shù)據(jù)，則該請(qǐng)求消息搜索成功。此時(shí)，節(jié)點(diǎn)Vi收到查詢消息的概率就較小。

2 混合副本放置方法

由于IPTV數(shù)據(jù)與一般的文件數(shù)據(jù)不同,流式數(shù)據(jù)在系統(tǒng)中有一定的存活時(shí)間，同時(shí)數(shù)據(jù)量較大。因此，其副本放置方法和普通P2P文件分享系統(tǒng)的副本放置方法有一定差別。

2.1 IPTV數(shù)據(jù)特性

一般說(shuō)來(lái)，一個(gè)通過(guò)數(shù)據(jù)壓縮過(guò)的視頻包含以下三類幀：I幀、P幀和B幀。其中，I幀包含視頻起始信息，用戶收到這種幀不要更多的信息就可以直接解碼出相關(guān)視頻信息。這類幀的好處在于能夠更快地完成電視頻道轉(zhuǎn)換（zapping）任務(wù)，因而有必要多復(fù)制此類幀來(lái)減少時(shí)延。然而，I幀的大小遠(yuǎn)遠(yuǎn)大于其他兩類幀，因而也需要更大的存儲(chǔ)空間和帶寬來(lái)實(shí)現(xiàn)傳輸通信。典型的視頻數(shù)據(jù)結(jié)構(gòu)如圖1所示?？梢钥吹?電視節(jié)目的傳送數(shù)據(jù)幀中，B幀所需開(kāi)銷最小，其傳輸?shù)念l率最高。

通過(guò)上述分析可以發(fā)現(xiàn)，對(duì)各個(gè)頻道及其節(jié)目的數(shù)據(jù)幀進(jìn)行合理的復(fù)制，進(jìn)而放置到靠近用戶的位置，是平衡用戶請(qǐng)求的消息搜索成功率和副本放置開(kāi)銷之間關(guān)系的一種有效途徑。

2.2 混合副本放置策略

在查詢消息路由算法一定的條件下，節(jié)點(diǎn)Vi收到的查詢消息數(shù)量由其覆蓋的節(jié)點(diǎn)數(shù)決定，即該節(jié)點(diǎn)通過(guò)泛洪，在TTL的限制下，轉(zhuǎn)發(fā)該節(jié)點(diǎn)查詢消息的節(jié)點(diǎn)數(shù)量。設(shè)網(wǎng)絡(luò)中平均連接度為K。當(dāng)K=1時(shí)，節(jié)點(diǎn)Vi接收的查詢消息轉(zhuǎn)發(fā)次數(shù)為：

其中，di為節(jié)點(diǎn)Vi的連接度。當(dāng)某一消息成功搜索到副本的位置，則響應(yīng)該消息。另外，當(dāng)連接度增大時(shí)，某一節(jié)點(diǎn)可能收到兩次節(jié)點(diǎn)Vi洪泛的查詢消息。這樣，該節(jié)點(diǎn)收到的第二次查詢消息會(huì)被丟棄。以此類推，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)一定，平均連接度越高，其查詢消息的能力就越弱。此時(shí)，當(dāng)K=k時(shí)，節(jié)點(diǎn)Vi所能收到的節(jié)點(diǎn)數(shù)為：

由此可見(jiàn)，節(jié)點(diǎn)Vi的連接度越大，其接受查詢消息的能力就越強(qiáng)。若將熱度較高的節(jié)目數(shù)據(jù)放置在該節(jié)點(diǎn)上，則消息搜索成功率較高，從而實(shí)現(xiàn)較低的請(qǐng)求響應(yīng)時(shí)延和較小的節(jié)目初始化時(shí)延。

以此為依據(jù)，并結(jié)合負(fù)載均衡、節(jié)點(diǎn)距離以及IPTV編碼的特點(diǎn)，本文提出一種針對(duì)時(shí)移IPTV系統(tǒng)的混合副本放置策略，將數(shù)據(jù)片分為兩類，并做不同的處理：

(1)實(shí)時(shí)數(shù)據(jù)片的放置。為了實(shí)現(xiàn)更小的初始化時(shí)延及頻道切換響應(yīng)時(shí)延，需要適當(dāng)增加I幀的副本數(shù)。同時(shí)，為了不使冷門節(jié)目初始化時(shí)延過(guò)長(zhǎng)，節(jié)目之間I幀的比例差值不應(yīng)過(guò)大。另外，對(duì)于B幀和P幀，可根據(jù)節(jié)目點(diǎn)播的熱點(diǎn)區(qū)域進(jìn)行區(qū)域性放置。具體流程如圖2所示，當(dāng)系統(tǒng)加入一個(gè)實(shí)時(shí)數(shù)據(jù)片時(shí)，首先判斷該數(shù)據(jù)片是否為I幀。若是I幀，則根據(jù)人工輸入的放置概率沿傳輸路徑放置，路由節(jié)點(diǎn)的連接度越大放置的概率越高。當(dāng)被放置節(jié)點(diǎn)的緩存空間已滿時(shí)，利用LRU為該副本騰出相應(yīng)空間。反之，若該數(shù)據(jù)片為B幀或P幀，則計(jì)算該幀在本節(jié)點(diǎn)被訪問(wèn)的并發(fā)數(shù)，若超出閾值OT，則發(fā)送一個(gè)副本放置到發(fā)送距離需要該內(nèi)容最多的熱點(diǎn)區(qū)域最近的路由器節(jié)點(diǎn)上。若此節(jié)點(diǎn)緩存空間已滿，則采用LRU為該副本騰出相應(yīng)空間。

圖2 實(shí)時(shí)數(shù)據(jù)片放置示意圖

(2)過(guò)期數(shù)據(jù)片的放置。鑒于實(shí)時(shí)數(shù)據(jù)片已經(jīng)占用了很大一部分緩存空間，過(guò)期數(shù)據(jù)片所能提供的緩存空間相對(duì)減小，因此選擇其放置策略更要慎重。首先要解決選擇哪一個(gè)數(shù)據(jù)片副本需要進(jìn)行放置，以及緩存空間已滿時(shí)應(yīng)該采取怎樣的緩存管理策略。用戶節(jié)點(diǎn)有兩個(gè)選擇查找到需要的過(guò)期數(shù)據(jù)片，以實(shí)現(xiàn)快進(jìn)、快退等操作。①通過(guò)洪泛的方式進(jìn)行搜索；②直接到代理服務(wù)器中查找相應(yīng)數(shù)據(jù)片。第一種方法雖然能夠分擔(dān)代理服務(wù)器的負(fù)載，減少請(qǐng)求時(shí)延，但是加重了網(wǎng)絡(luò)負(fù)擔(dān)，且存在消息搜索成功率低的問(wèn)題。因此，對(duì)于過(guò)期數(shù)據(jù)片，可通過(guò)代理服務(wù)器進(jìn)行查找。若該內(nèi)容在節(jié)點(diǎn)服務(wù)器中的并發(fā)數(shù)超過(guò)OL，且用戶節(jié)點(diǎn)搜索失敗，則將目標(biāo)數(shù)據(jù)片放置在沿路連接度最大的路由節(jié)點(diǎn)中。若此節(jié)點(diǎn)緩存空間已滿，則采用LRU為該副本騰出相應(yīng)空間。

(3)緩存數(shù)據(jù)管理。在時(shí)移IPTV系統(tǒng)中，每一個(gè)數(shù)據(jù)在一定時(shí)間后可用度就大大減少，需要對(duì)這些數(shù)據(jù)進(jìn)行定期處理，以提高緩存利用率。

設(shè)置數(shù)據(jù)片生存時(shí)間，使各類數(shù)據(jù)片的生存時(shí)間各有不同，其中實(shí)時(shí)數(shù)據(jù)片的生存時(shí)間應(yīng)該大于過(guò)期數(shù)據(jù)片的生存時(shí)間,以滿足用戶短時(shí)間暫?；蚩焱说男枰?。

3 仿真及結(jié)果分析

3.1 仿真環(huán)境

仿真采用Power law拓?fù)渥鳛槟M拓?fù)?。拓?fù)浒? 000個(gè)節(jié)點(diǎn)，其中包括一個(gè)代理服務(wù)器，100個(gè)路由器節(jié)點(diǎn),其余為用戶節(jié)點(diǎn)。每個(gè)路由節(jié)點(diǎn)緩存空間為36 GB，用戶節(jié)點(diǎn)通過(guò)洪泛的方式獲取所需節(jié)目的相關(guān)數(shù)據(jù)。網(wǎng)絡(luò)中節(jié)點(diǎn)平均連接度為4,設(shè)置150套電視節(jié)目，同一節(jié)點(diǎn)不存在同一數(shù)據(jù)片對(duì)象。用戶節(jié)點(diǎn)以相同的概率發(fā)起查詢消息獲取隨機(jī)的節(jié)目。

3.2 數(shù)據(jù)分析

圖3顯示了在IPTV系統(tǒng)中節(jié)點(diǎn)通過(guò)使用洪泛的查詢消息路由算法進(jìn)行搜索，各放置策略對(duì)數(shù)據(jù)片的搜索命中率的影響的比較。圖中橫坐標(biāo)為單個(gè)路由節(jié)點(diǎn)緩存空間與整個(gè)數(shù)據(jù)庫(kù)內(nèi)容大小的比值。TTL的值為2。數(shù)據(jù)表明，在同一網(wǎng)絡(luò)條件下，采用混合副本放置策略的消息搜索成功率較高。當(dāng)緩存空間增加時(shí)，隨機(jī)放置策略下的消息搜索成功率也有增加，但是由于其副本放置的隨機(jī)性，使得性能的提高不是很穩(wěn)定。

圖4顯示了各策略的路由節(jié)點(diǎn)緩存空間占用情況的比較?？梢钥吹剑S機(jī)副本放置策略作為一種貪婪策略，總是隨機(jī)地選擇數(shù)據(jù)內(nèi)容將緩存空間填滿。這樣的好處在于，搜索成功率隨著緩存空間的增大而提高。然而，隨機(jī)地選擇數(shù)據(jù)內(nèi)容不適合IPTV系統(tǒng)這樣數(shù)據(jù)更新較快的環(huán)境，且這種主動(dòng)而又周期性地盲目數(shù)據(jù)更新更加重了網(wǎng)絡(luò)開(kāi)銷。

時(shí)移電視具有數(shù)據(jù)量大，數(shù)據(jù)更新頻率高等特點(diǎn)。本文針對(duì)時(shí)移電視系統(tǒng)中的副本放置問(wèn)題，從IPTV數(shù)據(jù)流格式特點(diǎn)出發(fā)，提出了一種混合副本放置策略。通過(guò)分析傳輸時(shí)延以及消息搜索成功率與副本放置的關(guān)系，根據(jù)節(jié)點(diǎn)連接度放置數(shù)據(jù)片，達(dá)到提高熱點(diǎn)數(shù)據(jù)片搜索成功率的效果。同時(shí)，分析IPTV數(shù)據(jù)幀特點(diǎn)，合理分配放置概率，以減小節(jié)目初始化時(shí)延以及頻道切換時(shí)延。最后給出了混合副本放置策略。仿真表明，該策略能夠在較少的緩存空間下有效提高消息搜索成功率，降低請(qǐng)求時(shí)延，提高系統(tǒng)性能。

[1]Liu Yaning,SIMON G S.Distributed delivery system for time-shifted streaming systems[C].2010 IEEE 35th Conference on Local Computer Networks,Denver,CO,USA,2010:276-279.

[2]POPESCU A,KOUVATSOS D D,REMONDO D,et al.Content distribution over IP:developments and challenges[J].Network Performance Engineering,2011,5233:979-987.

[3]BEJERANO Y,KOPPOL P V.Improving zap response Time for IPTV[C].INFOCOM 2009,IEEE,Rio de Janeiro,2009:1971-1979.

[4]TAN B,MASSOULIE L,Optimal content placement for peer-to-peer video-on-demand systems[C].IEEE INFOCOM 2011,shanghai,2011:694-702.

[5]Rao Weixiong,Chen Lei,Fu Waichee,et al.Optimal resource placement in structured peer-to-peer networks[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(7):1011-1026.

[6]BIERACKI A.Methods of QoS improvement for P2P IPTV based on traffic modelling[C].2010 International Conference on Complex,Intelligent and Software Intensive Systems,2010:445-450.

[7]Gao Peng,Liu Tao,Chen Yanming,et al.The measurement and modeling of a P2P streaming video service[J].Networks for Grid Applications,2009,2:24-34.

[8]Li Zhe,SIMON G.Time-Shifted TV in content centric networks:the case for cooperative in-network caching[C].ICC2011:IEEE International Conference on Communications,Kyoto,Japan,2011:1-6.

[9]馮國(guó)富,張金城,顧慶,等.一種基于覆蓋網(wǎng)絡(luò)拓?fù)涞臒o(wú)結(jié)構(gòu)P2P主動(dòng)復(fù)制策略[J].軟件學(xué)報(bào),2007,18(9):2226-2234.