李 蕾，李 玲

?

請(qǐng)求下降鄰域疊加選取分布式P2P視頻點(diǎn)播調(diào)度

李 蕾1，李 玲2

(1. 山西傳媒學(xué)院傳媒工程系，山西 晉中 030619；2. 新余學(xué)院，江西 新余 338004)

為實(shí)現(xiàn)對(duì)等架構(gòu)的低成本視頻流傳輸和實(shí)時(shí)播放要求，提出基于請(qǐng)求下降疊加選取的分布式P2P視頻點(diǎn)播調(diào)度算法。首先，基于疊加技術(shù)構(gòu)建P2P視頻點(diǎn)播的技術(shù)指標(biāo)，充分考慮輸入鄰域節(jié)點(diǎn)、輸出鄰域節(jié)點(diǎn)和媒體服務(wù)器負(fù)載3組優(yōu)化指標(biāo)，構(gòu)建疊加架構(gòu)和分布式算法流程；其次，利用請(qǐng)求下降策略對(duì)發(fā)送節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)選取進(jìn)行改進(jìn)，解決可能出現(xiàn)的帶寬低利用率和無效的視頻播放問題；最后，通過BitTorrent視頻點(diǎn)播系統(tǒng)對(duì)所提算法的有效性進(jìn)行了驗(yàn)證。

請(qǐng)求下降；疊加選??；分布式；P2P視頻；點(diǎn)播

伴隨網(wǎng)絡(luò)科技的發(fā)展，網(wǎng)絡(luò)中的視頻消費(fèi)逐漸占據(jù)流量消費(fèi)的主要地位，據(jù)思科預(yù)測(cè)，到2017年左右，視頻流量消費(fèi)水平將達(dá)到全球流量交換總量的90%左右。其中最重要的是視頻點(diǎn)播服務(wù)，生成的總流量將會(huì)達(dá)到2014年時(shí)相關(guān)水平的3倍，這將給服務(wù)器和網(wǎng)絡(luò)帶來非常嚴(yán)重的數(shù)據(jù)處理負(fù)擔(dān)。同時(shí)，近年來用戶對(duì)視頻質(zhì)量的需求也越來越高。

P2P技術(shù)的一個(gè)很重要應(yīng)用是視頻點(diǎn)播，PPStream、UUSee、PPLive等公司都推出了這項(xiàng)業(yè)務(wù)，和傳統(tǒng)的基于服務(wù)器/客戶機(jī)結(jié)構(gòu)的視頻點(diǎn)播相比，P2P技術(shù)具有擴(kuò)展性好，成本低的優(yōu)點(diǎn)，但其也有一些不利的因素。如P2P網(wǎng)絡(luò)具有動(dòng)態(tài)性、不穩(wěn)定性；P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的差異性很大，這可能會(huì)導(dǎo)致播放不流暢。面對(duì)高帶寬、高存儲(chǔ)、高實(shí)時(shí)要求的VOD應(yīng)用，P2P網(wǎng)絡(luò)中有限的資源可用性的問題顯得非常突出[1]，這主要表現(xiàn)在以下方面：①播放1080P等格式還存在問題，因?yàn)椴糠謳捫∮? Mbps，上傳帶寬更小[2]再加上P2P資源分配不均，導(dǎo)致視頻播放不流暢。②P2P需大緩存空間，只有較大上傳帶寬才能滿足需要，且要求使用視頻的用戶擁有較大緩存容量，但用戶能提供空間是有限的，導(dǎo)致P2P資源分配不合理，影響點(diǎn)播質(zhì)量[3]。③文獻(xiàn)[4]指出P2P系統(tǒng)中，視頻點(diǎn)播容量上限受頻繁點(diǎn)播視頻影響，如果流量超出容量限制會(huì)產(chǎn)生帶寬饑餓現(xiàn)象。對(duì)節(jié)點(diǎn)帶寬進(jìn)行優(yōu)化配置，可有效提升P2P視頻系統(tǒng)容量，但系統(tǒng)內(nèi)部的視頻用戶在視頻點(diǎn)播過程中具有自私性[5]，很難通過節(jié)點(diǎn)資源的直接調(diào)度實(shí)現(xiàn)節(jié)點(diǎn)帶寬資源和視頻緩存能力的提升[6]。④由于節(jié)點(diǎn)硬件條件(帶寬、存儲(chǔ))的限制，能提供的資源是有限的。

本文基于疊加技術(shù)對(duì)P2P視頻點(diǎn)播進(jìn)行優(yōu)化，并構(gòu)建疊加架構(gòu)和分布式算法流程，同時(shí)為解決可能出現(xiàn)的帶寬低利用率和無效的視頻播放問題，利用請(qǐng)求下降策略對(duì)發(fā)送節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)選取過程進(jìn)行了改進(jìn)設(shè)計(jì)。最后，通過實(shí)驗(yàn)對(duì)算法的有效性進(jìn)行了驗(yàn)證。

1 P2P視頻點(diǎn)播疊加技術(shù)

疊加技術(shù)：P2P網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)都充當(dāng)路由器的角色，將收到的數(shù)據(jù)轉(zhuǎn)發(fā)給其他多個(gè)節(jié)點(diǎn)，這其實(shí)是在應(yīng)用層構(gòu)建了另一個(gè)“網(wǎng)絡(luò)層”或稱為Peer Overlay。利用疊加網(wǎng)絡(luò)的技術(shù)，可以提高網(wǎng)絡(luò)資源利用率。

1.1 技術(shù)指標(biāo)

技術(shù)目標(biāo)2. 根據(jù)上傳負(fù)載，按比例配置鄰域節(jié)點(diǎn)輸出。()為上傳帶寬，()為發(fā)送視頻塊集，|()|表示()基數(shù)。引入()和|()|比例

每個(gè)對(duì)等點(diǎn)的鄰域節(jié)點(diǎn)輸出可配置為

技術(shù)目標(biāo)3. 盡量減少由服務(wù)器維護(hù)所需的傳出連接數(shù)量和上傳帶寬。會(huì)出現(xiàn)兩種情形：①參與的對(duì)等節(jié)點(diǎn)總上傳帶寬小于即時(shí)傳輸所需帶寬；②對(duì)等節(jié)點(diǎn)相對(duì)于視頻對(duì)象數(shù)量不足。

1.2 對(duì)等節(jié)點(diǎn)發(fā)現(xiàn)

Gossip協(xié)議可實(shí)現(xiàn)在信息中進(jìn)行信息捎帶，從而實(shí)現(xiàn)開銷的降低。對(duì)對(duì)等節(jié)點(diǎn)集Cand(i)采用兩跳方式的原因是：兩跳技術(shù)在網(wǎng)絡(luò)處理中可有效實(shí)現(xiàn)路由協(xié)議復(fù)雜度的降低，并實(shí)現(xiàn)路由協(xié)議處理過程的簡化，同時(shí)可有效提升網(wǎng)絡(luò)的可擴(kuò)展性和覆蓋區(qū)間，因此本文著重對(duì)兩跳對(duì)等網(wǎng)絡(luò)進(jìn)行分析。以圖1為例，對(duì)于個(gè)節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)遍歷，發(fā)現(xiàn)的計(jì)算開銷為O(nlgn)。

1.3 算法描述

使用分布式算法求解，引入輸入鄰域節(jié)點(diǎn)定期評(píng)估，其會(huì)影響對(duì)等節(jié)點(diǎn)的屬于()和()的輸入和輸出鄰域節(jié)點(diǎn)疊加性能。結(jié)合式(1)和式(6)可得

對(duì)于屬于()和()的對(duì)等節(jié)點(diǎn)

對(duì)等點(diǎn)發(fā)現(xiàn)算法傳播具有輸出鄰域節(jié)點(diǎn)的對(duì)等信息，以滿足方程約束。當(dāng)且僅當(dāng)所提優(yōu)化問題是不可行的，便使用媒體服務(wù)器作為輸入鄰域節(jié)點(diǎn)。

分布式鄰域節(jié)點(diǎn)選取過程如下。其中，分布式算法見偽代碼1；大寫字母表示邏輯開頭；運(yùn)算符代表一組元素的加、減法運(yùn)算。

偽代碼1：分布式鄰域節(jié)點(diǎn)選取 1. 情形1：|in(i)|=N2. best_cand=index(maxf(j): j?cand(i))3. worst_in=index(minf(j): j?in(i))4. if server?|in(i)| then5. if then6. in(i)=in(i)-server+best_cand7. else if f(best_cand)>f(worst_in) then8. in(i)=in(i)-worst_in+best_cand9. end if10. else11. if f(best_cand)>f(worst_in)&≥m then12. in(i)=in(i)-worst_in+best_cand13. else if then14. in(i)=in(i)-worst_in+server15. end if16. end if 17. 情形2：|in(i)|

對(duì)于代碼中的情形1，對(duì)等點(diǎn)具有輸入鄰居節(jié)點(diǎn)，并搜索是否有一些候選對(duì)等體可能比其已經(jīng)擁有的更好。存在兩種情形：

(1) 對(duì)于屬于媒體服務(wù)器()[第4~9行]，如果從()中刪除服務(wù)器，并添加_，對(duì)等點(diǎn)的聚合傳入數(shù)據(jù)流大于[第5行]，則執(zhí)行交換過程[第6行]。如果對(duì)等點(diǎn)的總計(jì)傳入數(shù)據(jù)流小于[第7行]，然后移除_，并添加_，max(())減小，那么，就可以在不排除服務(wù)器的情況下進(jìn)行交換(第8行)。

(2) 對(duì)于不屬于媒體服務(wù)器() [第10~16行]，如果通過移除_并添加_[第11行]，max(())減小，同時(shí)如果對(duì)等點(diǎn)的總計(jì)傳入數(shù)據(jù)流大于等于，則執(zhí)行交換過程[第12行]。如果通過交換過程max(())數(shù)值不降低，但是融合的傳入數(shù)據(jù)流低于播放速率[第13行]，則可對(duì)媒體服務(wù)器()執(zhí)行交換過程，在最差的媒體服務(wù)器之間，可確保不間斷的視頻接收。

2 分布式塊傳輸調(diào)度

2.1 請(qǐng)求下降策略

基于服務(wù)質(zhì)量的順序選擇算法對(duì)隊(duì)列中的請(qǐng)求傳輸塊進(jìn)行順序排列，如圖2所示。

輸出隊(duì)列

請(qǐng)求期限請(qǐng)求到達(dá)估計(jì) 0.15請(qǐng)求A0.11 0.40請(qǐng)求B0.18 0.20請(qǐng)求C0.25 0.30請(qǐng)求D0.32

圖2中，如果發(fā)送節(jié)點(diǎn)的負(fù)載均衡，則表明該列表性能好。然而，如果發(fā)送節(jié)點(diǎn)服務(wù)請(qǐng)求多于其可承受負(fù)載，則該列表性能惡化。為避免這種情況，采取請(qǐng)求下降策略，判斷發(fā)送者請(qǐng)求是否能及時(shí)交付，如果不能則服務(wù)請(qǐng)求數(shù)量下降，如圖3所示。

輸出隊(duì)列

請(qǐng)求期限請(qǐng)求到達(dá)估計(jì) 0.15請(qǐng)求A0.18 0.20請(qǐng)求B0.25 0.30請(qǐng)求C0.32 0.35請(qǐng)求D0.39

2.2 發(fā)送節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)選取

發(fā)送節(jié)點(diǎn)選?。嚎紤]發(fā)送節(jié)點(diǎn)，其中，()=2 Mbps，()=3；發(fā)送節(jié)點(diǎn)，其中，()=0.4 Mbps，()=0。當(dāng)()=0表示無請(qǐng)求掛起，則保持空閑，不利于節(jié)點(diǎn)流量均衡。為減輕其影響，需對(duì)目標(biāo)式(12)進(jìn)行改進(jìn)

3 實(shí)驗(yàn)與分析

3.1 參數(shù)對(duì)比實(shí)驗(yàn)

利用OPNET進(jìn)行P2P視頻點(diǎn)播系統(tǒng)建模，所采用的視頻測(cè)試集包含4個(gè)視頻，每個(gè)時(shí)長12 min，如圖4所示。并選取Improving QoS、iPASS和Kangaroo算法做對(duì)比。平均對(duì)等上傳帶寬為avg=2000 Kbps，視頻播放速率等于平均對(duì)等上傳帶寬，即=avg=2000 Kbps。實(shí)驗(yàn)方案包括500個(gè)對(duì)等節(jié)點(diǎn)，并包含3個(gè)階段：①對(duì)等節(jié)點(diǎn)以統(tǒng)一速率進(jìn)入系統(tǒng)；②無對(duì)等節(jié)點(diǎn)到達(dá)和離開；③對(duì)等節(jié)點(diǎn)以統(tǒng)一離開率離開系統(tǒng)[9-10]。圖5(a)~(c)給出了在4種不同的情況下的視頻點(diǎn)播行為，節(jié)點(diǎn)以恒定比例離開：1，2，5，10節(jié)點(diǎn)/秒。

在圖5中，算法模擬需運(yùn)行至僅剩50個(gè)對(duì)等點(diǎn)留在系統(tǒng)中。根據(jù)圖4可知，即使對(duì)于非常高的對(duì)等節(jié)點(diǎn)離開率，例如10節(jié)點(diǎn)/秒，其剩余節(jié)點(diǎn)的空閑率仍然小于7%(平均為4%)，服務(wù)率小于20%(平均為10%)。在對(duì)等節(jié)點(diǎn)離開期間，服務(wù)器對(duì)系統(tǒng)的貢獻(xiàn)并沒有顯著增加。其有助于減少帶寬，這是因?yàn)橄到y(tǒng)中有較少對(duì)等節(jié)點(diǎn)。

圖4 模擬器操作界面

圖5 對(duì)等節(jié)點(diǎn)離開率對(duì)算法影響

圖6是6種參數(shù)對(duì)等節(jié)點(diǎn)到達(dá)率對(duì)算法影響圖。其中，空閑率(%)和服務(wù)率(%)是在500個(gè)節(jié)點(diǎn)以1，5，10個(gè)節(jié)點(diǎn)/秒速度進(jìn)入系統(tǒng)；標(biāo)準(zhǔn)偏差的正態(tài)分布為3，5，20，40。

根據(jù)圖6可知，空閑率(%)的增加和高比例帶寬(高達(dá)40%)是由服務(wù)器提供的。這種現(xiàn)象是不可避免的，因?yàn)槿魏蝺?yōu)化算法都需要一些適應(yīng)時(shí)間。當(dāng)所有的對(duì)等節(jié)點(diǎn)加入到系統(tǒng)中后，似乎達(dá)到穩(wěn)定的狀態(tài)，可觀測(cè)到空閑率(%)和服務(wù)率(%)處于穩(wěn)定狀態(tài)。兩個(gè)對(duì)等節(jié)點(diǎn)相距越近，其能夠提供輸出節(jié)點(diǎn)所需內(nèi)容的概率越低，因此需要由服務(wù)器進(jìn)行提供，從而增加服務(wù)器負(fù)擔(dān)。

3.2 算法性能對(duì)比

表1對(duì)比了選取的幾種算法在節(jié)點(diǎn)自適應(yīng)動(dòng)態(tài)行為、服務(wù)器支持、資源平衡性、對(duì)等節(jié)點(diǎn)異質(zhì)性開發(fā)等性能上的表現(xiàn)。

根據(jù)表1可知，本文算法相對(duì)于其他3種算法，具有更高的自適應(yīng)動(dòng)態(tài)行為，且具有服務(wù)支持性能、資源平衡性以及對(duì)等節(jié)點(diǎn)異質(zhì)開發(fā)能力。體現(xiàn)了本方法的有效性。

為實(shí)現(xiàn)算法橫向?qū)Ρ闰?yàn)證，選取Improving QoS、iPASS和Kangaroo 3種基于P2P的視頻點(diǎn)播算法進(jìn)行性能對(duì)比。實(shí)驗(yàn)參數(shù)：平均的視頻持續(xù)時(shí)間為=1/=90 min，視頻數(shù)據(jù)流的到達(dá)間隔為=1/=20 min。對(duì)比指標(biāo)選擇視頻流量效率和上述上行鏈路效率，見表2。

由表2可知，本文模型在上行鏈路效率和視頻流量效率兩項(xiàng)指標(biāo)均顯著優(yōu)于其他3種對(duì)比算法的相關(guān)指標(biāo)，說明本文模型在處理故障時(shí)具有優(yōu)勢(shì)。

(a) 到達(dá)率對(duì)空閑率影響

((1) 均勻分布，到達(dá)率10節(jié)點(diǎn)/秒；(2) 普通分布，到達(dá)偏差5 s；(3) 均勻分布，到達(dá)率5節(jié)點(diǎn)/秒；(4) 普通分布，到達(dá)偏差20 s；(5) 普通分布，到達(dá)偏差30 s；(6) 均勻分布，到達(dá)率1節(jié)點(diǎn)/秒)

(b) 到達(dá)率對(duì)服務(wù)率影響

((1) 普通分布，到達(dá)偏差5 s；(2) 普通分布，到達(dá)偏差20 s； (3) 均勻分布，到達(dá)率10節(jié)點(diǎn)/秒；(4) 均勻分布，到達(dá)率5節(jié)點(diǎn)/秒；(5) 普通分布，到達(dá)偏差30 s；(6) 均勻分布，到達(dá)率1節(jié)點(diǎn)/秒)

(c) 到達(dá)率對(duì)服務(wù)貢獻(xiàn)影響

表1 視頻點(diǎn)播系統(tǒng)對(duì)比

表2 模型指標(biāo)對(duì)比(%)

4 結(jié)束語

本文提出的一種基于請(qǐng)求下降疊加選取的分布式P2P視頻點(diǎn)播調(diào)度算法，充分考慮輸入鄰域節(jié)點(diǎn)、輸出鄰域節(jié)點(diǎn)和媒體服務(wù)器負(fù)載3組優(yōu)化指標(biāo)，構(gòu)建分布式算法流程，并利用請(qǐng)求下降策略解決可能出現(xiàn)的帶寬低利用率和無效的視頻播放問題，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的有效性。

[1] 沈時(shí)軍, 李三立. 基于P2P的視頻點(diǎn)播系統(tǒng)綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(4): 613-624.

[2] XU K, LIU X, MA Z, et al. Exploring the policy selection of the P2P VoD system: a simulation-based research [J]. Peer-to-Peer Networking and Applications, 2015, 8(3): 459-473.

[3] 聶華, 張敏, 郭敬榮,等. 基于內(nèi)容流行度差異性的CDN-P2P融合分發(fā)網(wǎng)絡(luò)緩存替換機(jī)制研究[J]. 通信學(xué)報(bào), 2015, 36(z1): 9-15.

[4] 何明, 張玉潔, 孟祥武. 面向用戶需求的非結(jié)構(gòu)化P2P資源定位泛洪策略[J]. 軟件學(xué)報(bào), 2015, 26(3): 640-662.

[5] CONG X, SHUANG K, SU S, et al. An efficient server bandwidth costs decreased mechanism towards mobile devices in cloud-assisted P2P-VoD system [J]. Peer-to- Peer Networking and Applications, 2014, 7(2): 175-187.

[6] GRAMATIKOV S, JAUREGUIZAR F. Modelling and analysis of non-cooperative peer-assisted VoD streaming in managed networks [J]. Multimedia Tools and Applications, 2016, 75(8): 4321-4348.

[7] 翟海濱, 張鴻, 劉欣然, 等. 最小化出口流量花費(fèi)的接入級(jí)P2P緩存容量設(shè)計(jì)方法[J]. 電子學(xué)報(bào), 2015, (5): 879-887.

[8] CHEN H Y, SUN Z G, YI F. Buffer Bank storage: an economic, scalable and universally usable in-network storage model for streaming data applications [J]. Science China Information Sciences, 2016, 59(1): 1-15.

[9] CHANG C L, CHEN W M, HUNG C H. Reliable consideration of P2P-based VoD system with interleaved video frame distribution [J]. IEEE Systems Journal, 2014, 8(1): 304-312.

[10] DUQUE J P U, GOMEZ N G. Throughput analysis of P2P video streaming on single-hop wireless networks [J]. IEEE Latin America Transactions, 2015, 13(11): 3684-3689.

Distributed P2P Video on Demand Scheduling Based on Request Drop Neighborhood Overlay

LI Lei1, LI Ling2

(1. Department of Communication Engineering, Communication University of Shanxi, Jinzhong Shanxi 030619, China; 2. Xinyu University, Xinyu Jiangxi 338004, China)

In order to achieve peer-to-peer architectures for low cost video stream transmission and real-time playback requirements, this paper proposes a distributed P2P video on demand scheduling algorithm based on request drop neighborhood overlay. Firstly, this paper constructs technical index of P2P VOD (video on demand) based on the superposition technique, considers the three parameters optimization index of the input neighborhood nodes, the output neighborhood nodes and the media server load, and then constructs the overlay structure and distributed algorithm flow. Secondly, this paper uses the request descent strategy to improve the selection of the sending nodes and service nodes, which can solve the problem of broadband low utilization ratio and invalid video playback. Finally, experimental results based on the BitTorrent VOD system verify the effectiveness of the proposed algorithm.

request drop; overlay selection; distributed; P2P video; on demand

TN 943

10.11996/JG.j.2095-302X.2018010030

A

2095-302X(2018)01-0030-06

2017-04-16；

2017-06-03

江西省教育廳科技項(xiàng)目(GJJ151205)

李 蕾(1982-)，女，山西長治人，講師，碩士。主要研究方向?yàn)閳D像處理及廣播電視技術(shù)。E-mail：sherry0790@163.com