P2P流媒體數(shù)據(jù)調(diào)度策略研究

韓亞峰（河南科技學(xué)院,河南新鄉(xiāng),453003）

P2P流媒體數(shù)據(jù)調(diào)度策略研究

韓亞峰
（河南科技學(xué)院,河南新鄉(xiāng),453003）

數(shù)據(jù)調(diào)度算法是P2P研究的熱點(diǎn)問題.算法性能的優(yōu)劣會直接影響到P2P系統(tǒng)的服務(wù)質(zhì)量.通過分析P2P流媒體直播系統(tǒng)中節(jié)點(diǎn)能力和數(shù)據(jù)分片的優(yōu)先級,提出了最少最小優(yōu)先調(diào)度算法（LRFA）.算法結(jié)合了現(xiàn)有的最少優(yōu)先策略,將數(shù)據(jù)的稀缺性和時(shí)間特性作為重要因素,對節(jié)點(diǎn)能力進(jìn)行了動(dòng)態(tài)估算,最終實(shí)現(xiàn)了節(jié)點(diǎn)資源的充分利用.

P2P網(wǎng)絡(luò)；數(shù)據(jù)調(diào)度；數(shù)據(jù)優(yōu)先級；稀缺優(yōu)先；節(jié)點(diǎn)能力

近年來基于P2P技術(shù)的流媒體應(yīng)用已成為研究熱點(diǎn)[1].P2P流媒體系統(tǒng)中普通主機(jī)節(jié)點(diǎn)（對等節(jié)點(diǎn),簡稱Peer節(jié)點(diǎn)）從其他Peer節(jié)點(diǎn)獲取流媒體數(shù)據(jù)的同時(shí),也承擔(dān)起為其他Peer節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的任務(wù),充分利用了空閑的網(wǎng)絡(luò)、計(jì)算、存儲等資源,從而使服務(wù)器上網(wǎng)絡(luò)帶寬資源消耗大大減少,局部網(wǎng)絡(luò)的擁塞也相應(yīng)減少,使系統(tǒng)可擴(kuò)展性提高,性價(jià)比增強(qiáng).視頻直播系統(tǒng)中Peer節(jié)點(diǎn)存在帶寬、處理能力等方面的差異性,而其作為普通主機(jī)節(jié)點(diǎn),服務(wù)能力有限,卻要承擔(dān)大量、長時(shí)間的流媒體數(shù)據(jù)處理轉(zhuǎn)發(fā)任務(wù),需要面對諸多的困難和挑戰(zhàn).合理的數(shù)據(jù)調(diào)度策略可以解決這些問題,為用戶提供高質(zhì)量的流媒體服務(wù)[2].

目前P2P數(shù)據(jù)調(diào)度策略已有一些成熟的研究成果.傳統(tǒng)的數(shù)據(jù)調(diào)度策略主要有稀缺優(yōu)先策略（Local Rarest-firststrategy）、隨機(jī)策略（pure random strategy）和循環(huán)魯棒策略（Round-robin strategy）.在CoolStreaming中采用的稀缺優(yōu)先策略,時(shí)間響應(yīng)速度快,但是時(shí)間相關(guān)的計(jì)算依賴于節(jié)點(diǎn)之間的帶寬的計(jì)算.Chinasaw采用隨機(jī)策略,但這種策略在異構(gòu)的網(wǎng)絡(luò)環(huán)境中效果差,性能不穩(wěn)定,不適合用于基于DONet的系統(tǒng)[3].在分層流媒體系統(tǒng)PALS中采用了循環(huán)魯棒策略,較好地實(shí)現(xiàn)了節(jié)點(diǎn)的負(fù)載平衡,但是節(jié)點(diǎn)之間帶寬的計(jì)算復(fù)雜,不易實(shí)現(xiàn).為了解決傳統(tǒng)算法中存在的問題,本文設(shè)計(jì)了一種基于DONet系統(tǒng)的數(shù)據(jù)調(diào)度算法,能夠適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)性和異構(gòu)性,易于實(shí)現(xiàn).

1 P2P流媒體數(shù)據(jù)調(diào)度算法

1.1 數(shù)據(jù)的表示

流媒體系統(tǒng)中將數(shù)據(jù)按播放時(shí)間進(jìn)行分片,使得每個(gè)數(shù)據(jù)分片大小相同,為每個(gè)數(shù)據(jù)分片分配一個(gè)唯一遞增的序號,每個(gè)數(shù)據(jù)分片代表T/ms的數(shù)據(jù).系統(tǒng)中用一個(gè)滑動(dòng)窗口來表示緩沖區(qū),緩沖區(qū)中是否擁有某個(gè)分片的數(shù)據(jù)可以用緩存映射BM（Buffer Map）來表示[4].緩沖區(qū)中數(shù)據(jù)當(dāng)前播放位置tp可以分為已播放數(shù)據(jù)和未播放數(shù)據(jù)兩部分.為了給伙伴節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),已播放數(shù)據(jù)沒有被立即丟掉,而是在緩存中保存一段時(shí)間；為了本節(jié)點(diǎn)流媒體的正常播放,需要在緩存中保存接收到的即將要播放的數(shù)據(jù)分片,即未播放數(shù)據(jù)部分.用播放生存期（playback deadline）來表示當(dāng)前時(shí)刻距離播放該數(shù)據(jù)分片的時(shí)間長短,所以當(dāng)前時(shí)刻正在播放的數(shù)據(jù)分片的播放生存期為0.緩沖區(qū)每隔一段時(shí)間就會發(fā)出一次數(shù)據(jù)請求,請求的數(shù)據(jù)范圍為滑動(dòng)窗口的滑動(dòng)步長,將此區(qū)域的數(shù)據(jù)稱為交換窗口,每次只向鄰居請求交換窗口中缺少的數(shù)據(jù)分片.假設(shè)從鄰居節(jié)點(diǎn)請求并獲得數(shù)據(jù)分片的時(shí)延R很小（R＜＜T）,那么下一個(gè)時(shí)間間隔請求調(diào)度的數(shù)據(jù)分片范圍為tp時(shí)刻后的數(shù)據(jù),為了反映交換窗口中不同位置的數(shù)據(jù)分片對時(shí)間的要求不同,將其分成兩部分：緊急區(qū)域和非緊急區(qū)域,前者指位于交換窗口中播放位置附近的數(shù)據(jù)部分,后者是指相當(dāng)長一段時(shí)間后才會播放的數(shù)據(jù)區(qū)域,緩沖區(qū)中數(shù)據(jù)的結(jié)構(gòu)如圖1所示.理想的數(shù)據(jù)調(diào)度過程,每次只需請求非緊急區(qū)域中的數(shù)據(jù)分片,保證使該區(qū)域數(shù)據(jù)在進(jìn)入緊急區(qū)域時(shí),已經(jīng)全部到達(dá)緩沖區(qū).

圖1 緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)Fig.1 Bufferdata structure

1.2 數(shù)據(jù)的優(yōu)先級

在P2P系統(tǒng)中,不同的數(shù)據(jù)分片的重要性是不一樣的,一些分片僅有少數(shù)的鄰居節(jié)點(diǎn)擁有,相對稀缺,為了快速增加這些分片的副本,必須優(yōu)先請求調(diào)度.BT文件下載過程,為了提高整體的下載速率,就是采用這樣的算法（RarestFirst）.我們可以根據(jù)分片的重要性為它定義不同的優(yōu)先級,用優(yōu)先級的高低來表示對應(yīng)分片的重要程度,該數(shù)值越大,說明該分片越重要,在調(diào)度過程中必須優(yōu)先調(diào)度[5].把稀缺性（Rarest）作為優(yōu)先級定義的一個(gè)重要考慮因素.其次流媒體系統(tǒng)的一個(gè)重要特征是對數(shù)據(jù)有嚴(yán)格的實(shí)時(shí)性要求,用播放生存期（playback deadline）來反映數(shù)據(jù)分片時(shí)間上的緊急程度,播放生存期數(shù)值越小,表明該數(shù)據(jù)越緊急,相應(yīng)的優(yōu)先級也應(yīng)越高.最終把稀缺性和實(shí)時(shí)性作為決定數(shù)據(jù)分片優(yōu)先級的因素,定義數(shù)據(jù)分片優(yōu)先級的計(jì)算公式為：

其中s=（sreq-smin）/size,系數(shù)α的取值范圍[0,1],α具體的值在1.4中給出.PR（*）表示數(shù)據(jù)分片的稀缺性,是一個(gè)單調(diào)遞減的函數(shù),當(dāng)r=1,…,5時(shí),PR（r）=106-r,否則PR（r）=1.Σhkj表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中持有數(shù)據(jù)分片j的節(jié)點(diǎn)的個(gè)數(shù)；第二項(xiàng)PE（*）表示數(shù)據(jù)分片的實(shí)時(shí)性,也是一個(gè)單調(diào)遞減的函數(shù),當(dāng)0≤s≤1時(shí),PE（s）=101-s,否則PE（s）=1.參數(shù)的含義如表1所示,假設(shè)調(diào)度窗口大小為15 s,每個(gè)數(shù)據(jù)分片為500 ms,那么size=30.

表1 數(shù)據(jù)分片相關(guān)參數(shù)Tab.1 data segmentrelated parameters

1.3 節(jié)點(diǎn)能力的計(jì)算

流媒體系統(tǒng)中每隔一個(gè)調(diào)度周期,Peer節(jié)點(diǎn)就會向鄰居節(jié)點(diǎn)請求一次數(shù)據(jù).為了在最短的時(shí)間里正確完整地接收到請求的數(shù)據(jù),應(yīng)該選擇鄰居節(jié)點(diǎn)中能量強(qiáng)的進(jìn)行數(shù)據(jù)請求.Peer節(jié)點(diǎn)并不能完全占用鄰居節(jié)點(diǎn)的資源,因?yàn)猷従庸?jié)點(diǎn)可能同時(shí)要給多個(gè)請求節(jié)點(diǎn)發(fā)送數(shù)據(jù),所以它只能分配部分能力給每個(gè)請求的Peer節(jié)點(diǎn).系統(tǒng)中Peer節(jié)點(diǎn)請求的數(shù)據(jù)分片可能被多個(gè)鄰居節(jié)點(diǎn)同時(shí)擁有,此時(shí)Peer節(jié)點(diǎn)可以通過計(jì)算分配給自己的能力（簡稱節(jié)點(diǎn)能力）,然后選擇節(jié)點(diǎn)能力大的進(jìn)行請求.這個(gè)能力是個(gè)動(dòng)態(tài)變化的值,受多方面因素的影響,包括請求節(jié)點(diǎn)的下載帶寬、鄰居節(jié)點(diǎn)的上傳帶寬、請求節(jié)點(diǎn)個(gè)數(shù)、鏈路瓶頸等.用傳統(tǒng)的方法實(shí)時(shí)測量開銷太大,所以可以依據(jù)最近的數(shù)據(jù)傳輸情況對節(jié)點(diǎn)能力進(jìn)行實(shí)時(shí)估算.計(jì)算節(jié)點(diǎn)能力用到的參數(shù)如表2所示.

表2 節(jié)點(diǎn)能力相關(guān)參數(shù)Tab.2 node capability related parameters

初始化CapaAB為Min（OutBandA/num,InBandB,LinkA-B）,可以利用節(jié)點(diǎn)B在每個(gè)調(diào)度周期,都會向鄰居節(jié)點(diǎn)請求一次數(shù)據(jù)信息的機(jī)會,對鄰居節(jié)點(diǎn)的能力進(jìn)行估算.用數(shù)據(jù)分片的個(gè)數(shù)作為節(jié)點(diǎn)能力的計(jì)量單位,因?yàn)榱髅襟w系統(tǒng)中數(shù)據(jù)分片的大小基本相等.節(jié)點(diǎn)能力的計(jì)算函數(shù)如下所示：

CalculateCapa（）

{dataReqNum；

dataRecNum；

if（dataReqNum==0）//第一次向該鄰居請求數(shù)據(jù)分片

CapaAB=Min（OutBandA/num,InBandB,LinkA-B）；

return；

if（dataReqNum==CapaAB）CapaAB=dataRecNum；

}

算法中用dataReqNum保存上次請求的數(shù)據(jù)分片的數(shù)目,因?yàn)槊看握埱髷?shù)據(jù)分片的數(shù)量肯定小于節(jié)點(diǎn)的能力,所以這個(gè)數(shù)值一定小于上次估算的該節(jié)點(diǎn)的能力.用變量dataRecNum保存上次數(shù)據(jù)請求發(fā)出后,實(shí)際接收到的數(shù)據(jù)分片數(shù)量,該算法通過比較dataReqNum與鄰居節(jié)點(diǎn)能力之間的數(shù)量關(guān)系,如果小于,估算鄰居節(jié)點(diǎn)的能力不變,如果相等,那么接收到的數(shù)據(jù)分片的數(shù)量dataRecNum就是此次估算的鄰居節(jié)點(diǎn)的能力.

1.4 LRFA（LeastRarestFirstScheduling Algorithm）調(diào)度算法

系統(tǒng)中一些數(shù)據(jù)分片副本數(shù)量少[6],主要有以下兩種情況：①該數(shù)據(jù)分片在當(dāng)前節(jié)點(diǎn)中接近播放位置,序號較小,在一些鄰居節(jié)點(diǎn)的緩沖區(qū)中已被丟棄；②該數(shù)據(jù)分片在當(dāng)前節(jié)點(diǎn)中距離播放時(shí)刻還有較長時(shí)間,序號較大,是一個(gè)相對較新的數(shù)據(jù)分片.只有數(shù)據(jù)源節(jié)點(diǎn)和與源節(jié)點(diǎn)直接相連的少數(shù)伙伴節(jié)點(diǎn)持有這個(gè)數(shù)據(jù)分片,在很多鄰居節(jié)點(diǎn)的緩沖區(qū)中都沒有該分片,在帶寬有限的情況下,應(yīng)該首先請求第一種情況,否則可能會導(dǎo)致緊急區(qū)域的數(shù)據(jù)分片在播放以前不能到達(dá).而第二種情況,隨著播放時(shí)間的推移,這些新的數(shù)據(jù)分片會被廣泛傳播.

為了反映節(jié)點(diǎn)當(dāng)前的數(shù)據(jù)傳輸任務(wù),避免節(jié)點(diǎn)負(fù)載過重,為每個(gè)節(jié)點(diǎn)定義了接受請求數(shù)aep_num.接受請求數(shù)的值隨著數(shù)據(jù)請求數(shù)量的增加而增加,之后每完成一個(gè)數(shù)據(jù)傳輸任務(wù)就減1.算法還考慮到緩沖區(qū)緊急區(qū)域中數(shù)據(jù)分片的實(shí)時(shí)性要求高,優(yōu)先放入請求隊(duì)列.具體算法如下：

（1）計(jì)算緊急區(qū)域中空缺的數(shù)據(jù)分片的優(yōu)先級,公式中α=1/2,稀缺性和實(shí)時(shí)性并重.將數(shù)據(jù)分片按照優(yōu)先級數(shù)值由高到低排序,之后放入數(shù)據(jù)請求集合ReqCollection中；

（2）計(jì)算非緊急區(qū)域中空缺的數(shù)據(jù)分片的優(yōu)先級,置α=1,只考慮稀缺性.按照優(yōu)先級由高到低,放到請求集合ReqCollection中.若請求集合ReqCollection中的數(shù)據(jù)分片的數(shù)量大于設(shè)定值,則結(jié)束第2步；

（3）調(diào)用函數(shù)CalculateCapa（）,計(jì)算每個(gè)鄰居節(jié)點(diǎn)能力；

（4）按順序從請求隊(duì)列中取出數(shù)據(jù)分片,向擁有該數(shù)據(jù)分片并且aep_num最小的鄰居節(jié)點(diǎn)發(fā)出數(shù)據(jù)請求.若aep_num相等,向能力最大的鄰居節(jié)點(diǎn)請求.將該數(shù)據(jù)分片的序號放入該鄰居節(jié)點(diǎn)的請求隊(duì)列ReqQueue中；

（5）繼續(xù)第（4）步,直到請求集合ReqCollection中的數(shù)據(jù)都處理完畢,將數(shù)據(jù)請求集合ReqCollection清空；

（6）將節(jié)點(diǎn)的請求ReqQueue轉(zhuǎn)化成消息發(fā)送給鄰居,記錄該節(jié)點(diǎn)本次請求的數(shù)據(jù)分片數(shù)dataRequestNum.

2 實(shí)驗(yàn)分析

2.1 問題描述

為了驗(yàn)證數(shù)據(jù)調(diào)度算法的性能,通過改變系統(tǒng)的規(guī)模、節(jié)點(diǎn)播放速率和系統(tǒng)的運(yùn)行時(shí)間,利用仿真方法進(jìn)行了模擬實(shí)驗(yàn).算法環(huán)境設(shè)置：緩存大小為1 min數(shù)據(jù)量,數(shù)據(jù)調(diào)度周期為1 ms,交換窗口大小為10 ms數(shù)據(jù)量.

為了評估算法的優(yōu)劣,主要考慮了3個(gè)關(guān)鍵的參數(shù)：

參數(shù)1：播放停頓頻率（playback freeze frequency）,為節(jié)點(diǎn)播放視頻過程中,單位時(shí)間內(nèi)停頓的次數(shù),即播放停頓的總次數(shù)與節(jié)點(diǎn)生存時(shí)間的比值.

參數(shù)2：傳輸時(shí)延（packetlatency）,是從發(fā)出數(shù)據(jù)請求開始計(jì)時(shí),到接收到該數(shù)據(jù)分片的時(shí)間,即節(jié)點(diǎn)接收數(shù)據(jù)的等待時(shí)間.

參數(shù)3：傳輸率（delivery ratio）,為播放生存期內(nèi)到達(dá)的數(shù)據(jù)分片的數(shù)量與接收的總數(shù)據(jù)分片數(shù)量的比值,反映數(shù)據(jù)分片有效到達(dá)的情況.

將LRFA算法和LRF、Random、Round-Robin算法進(jìn)行了對比實(shí)驗(yàn),通過改變運(yùn)行時(shí)間、系統(tǒng)規(guī)模和播放速率,分別測得系統(tǒng)的播放停頓頻率、傳輸時(shí)延和傳輸率.實(shí)驗(yàn)節(jié)點(diǎn)300個(gè),播放時(shí)長1 h,多次運(yùn)行,得到的參數(shù)平均值見表3.

表3 4種調(diào)度算法比較Tab.3 Fourscheduling algorithms comparison

由表3可知,LRFA算法與其余3種算法相比,在播放停頓頻率、傳輸時(shí)延、傳輸率參數(shù)方面,均表現(xiàn)出了更好的性能.

3 結(jié)論

本文提出了一種最小最少優(yōu)先的數(shù)據(jù)調(diào)度算法LRFA,解決了當(dāng)前數(shù)據(jù)調(diào)度算法中不能適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)性和異構(gòu)性的問題.算法中對緩沖區(qū)緊急區(qū)域和非緊急區(qū)域中數(shù)據(jù)分片進(jìn)行優(yōu)先級的計(jì)算,按照數(shù)據(jù)分片優(yōu)先級由高到低的次序進(jìn)行請求.為了節(jié)點(diǎn)負(fù)載平衡,選擇傳輸任務(wù)小并且能力強(qiáng)的鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)請求.經(jīng)仿真驗(yàn)證,該算法能為用戶提供高質(zhì)量的流媒體服務(wù),具有實(shí)用價(jià)值.

[1]許建真,許密畫,張福炎,等.基于優(yōu)先級的應(yīng)用層組播的分層結(jié)構(gòu)模型[J].計(jì)算機(jī)應(yīng)用研究,2008,25（5）：12-15.

[2]羅建光,張萌,趙黎,等.基于P2P網(wǎng)絡(luò)的大規(guī)模視頻直播系統(tǒng)[J].JournalofSoftware,2007,18（2）：391-399.

[3]Pai V,Kumar K.Chainsaw：Eliminating trees from overlay multicast[C/OL].（2007-09-01）[2012-10-12].http：//mnl.cs.sunysb. edu/home/vinay/papers/chainsaw-iptps.pdf.

[4]吳桂芳.高性能P2P Streaming分發(fā)系統(tǒng)模型的研究[J].計(jì)算機(jī)工程,2007（8）：51-53.

[5]Zhang M,Xiong Y,Zhang Q,et al.Optimizing the Throughput of Data-Driven Peer-to-Peer Streaming[J].IEEE transactions on paralleland distributed systems,2009（1）：97-109.

[6]孫名松,周紅敏,唐亮.一種自適應(yīng)的P2P流媒體數(shù)據(jù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2008（3）：558-567.

（責(zé)任編輯：盧奇）

Research on data scheduling strategy for P2P media streaming

Han Yafeng
（Henan Institute ofScience and Technology,Xinxiang 453003,China）

Data scheduling algorithm is a very important issue in P2P research,which affects the quality of P2P media streaming．By means of analyzing node capability and data's priority in system,combined with Local Rarest First strategy,the Least Rarest First scheduling algorithm is given that used in P2P live media streaming．The data' rarest and emergence were considered as main factors,estimated the node'upload capability and realized efficiency utilization for node resources．

P2P network；data scheduling；data's priority；rarest first；peer's capability

TP393

A

1008-7516（2013）01-0086-05

10．3969/j．issn．1008-7516．2013．01．021

2012-12-10

韓亞峰（1984-）,女,河南洛陽人,碩士,助教．主要從事P2P技術(shù)應(yīng)用和多媒體技術(shù)研究．