萬(wàn)成威，鄔江興，蘭巨龍

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

1 引言

流媒體服務(wù)對(duì)鏈路的傳輸帶寬、時(shí)延、時(shí)延抖動(dòng)等近乎苛刻的要求，使其在“盡力而為”提供服務(wù)的互聯(lián)網(wǎng)中大規(guī)模部署成為一項(xiàng)極具挑戰(zhàn)性的任務(wù)?；?IP多播[1]和內(nèi)容分發(fā)網(wǎng)絡(luò)[2,3]CDN(content delivery network)的解決方案都被應(yīng)用于流媒體傳輸，然而受限于服務(wù)器的性能瓶頸和高昂的部署成本，這些方案都未能大規(guī)模推廣。對(duì)等網(wǎng)絡(luò)P2P(peer-to-peer)技術(shù)改變了互聯(lián)網(wǎng)中傳統(tǒng)的基于客戶機(jī)/服務(wù)器的服務(wù)提供模式，對(duì)等節(jié)點(diǎn)(peer)不僅作為客戶機(jī)接受服務(wù)，同時(shí)也作為服務(wù)器為其他對(duì)等節(jié)點(diǎn)提供服務(wù)，相當(dāng)于在物理傳輸網(wǎng)絡(luò)之上建立了一個(gè)邏輯覆蓋網(wǎng)絡(luò)(overlay network)，覆蓋網(wǎng)中所有節(jié)點(diǎn)完全對(duì)等，共享覆蓋網(wǎng)中的資源并協(xié)作提供服務(wù)，由此擺脫了服務(wù)器性能對(duì)網(wǎng)絡(luò)應(yīng)用擴(kuò)展性的束縛，同時(shí)不需要特殊的網(wǎng)絡(luò)基礎(chǔ)設(shè)施(如多播路由器等)支持，具有極高的性價(jià)比且容易部署，因此被大量的用于流媒體服務(wù)[4,5]。

P2P流媒體利用網(wǎng)絡(luò)中具有相同興趣的對(duì)等節(jié)點(diǎn)作為服務(wù)器協(xié)助流媒體內(nèi)容的分發(fā)。對(duì)等節(jié)點(diǎn)從網(wǎng)絡(luò)中獲取到流媒體內(nèi)容后，繼續(xù)作為服務(wù)器為對(duì)外提供該流媒體內(nèi)容的分發(fā)服務(wù)。對(duì)相同內(nèi)容感興趣的節(jié)點(diǎn)越多，可提供內(nèi)容分發(fā)服務(wù)的分布式服務(wù)器也越多，使得整個(gè)流媒體分發(fā)網(wǎng)絡(luò)的擴(kuò)展性大大增強(qiáng)。然而，各個(gè)節(jié)點(diǎn)承擔(dān)著大量的流媒體分發(fā)任務(wù)，其行為必然對(duì)整個(gè)P2P流媒體網(wǎng)絡(luò)的性能產(chǎn)生著重要的影響。為了準(zhǔn)確分析和評(píng)估這種影響，研究人員分別從理論建模、仿真實(shí)驗(yàn)、流量測(cè)量等方面對(duì)節(jié)點(diǎn)行為進(jìn)行了研究。P2P流媒體理論建模研究主要采用隨機(jī)排隊(duì)理論、流體極限理論等對(duì)P2P流媒體網(wǎng)絡(luò)中的peer選擇策略[6,7]、chunk調(diào)度策略[8～10]、churn問(wèn)題[11,12](節(jié)點(diǎn)頻繁加入和退出P2P流媒體網(wǎng)絡(luò))、擴(kuò)展性等問(wèn)題[13]加以描述和分析；在網(wǎng)絡(luò)環(huán)境受限的條件下，根據(jù)最優(yōu)化理論設(shè)計(jì)流媒體分發(fā)策略，實(shí)現(xiàn)網(wǎng)絡(luò)利用率最大化目標(biāo)[14]。仿真實(shí)驗(yàn)研究作為理論分析的有效驗(yàn)證手段也一直受到研究人員的廣泛關(guān)注，目前，應(yīng)用較多的P2P仿真工具主要有P2PSim[15]、SSFnet[16]等。P2P流媒體流量測(cè)量研究主要通過(guò)主動(dòng)探測(cè)(active probing)或被動(dòng)監(jiān)視(passive monitoring)等方法從網(wǎng)絡(luò)流量中提取 peer行為的樣本信息，以此估計(jì)對(duì)等節(jié)點(diǎn)在P2P網(wǎng)絡(luò)中的逗留時(shí)間及其分布情況等[17]。

然而，現(xiàn)有理論模型和仿真實(shí)驗(yàn)主要集中在P2P覆蓋網(wǎng)中對(duì)等節(jié)點(diǎn)的行為研究，而并未深入分析這些行為對(duì)底層物理傳輸網(wǎng)絡(luò)的影響。覆蓋網(wǎng)中的研究對(duì)準(zhǔn)確理解P2P流媒體網(wǎng)絡(luò)具有重要的指導(dǎo)意義，但覆蓋網(wǎng)無(wú)法直接獲得底層物理承載網(wǎng)絡(luò)的信息，其中的結(jié)論在物理承載網(wǎng)絡(luò)中并不一定成立，如覆蓋網(wǎng)中的最短路徑在實(shí)際的物理網(wǎng)絡(luò)中可能完全不可達(dá)[18]。因此，有必要對(duì)P2P流媒體的傳輸特征展開(kāi)研究。流量測(cè)量盡管可以得到每個(gè)用戶的傳輸會(huì)話信息，但準(zhǔn)確判定P2P會(huì)話并關(guān)聯(lián)節(jié)點(diǎn)在覆蓋網(wǎng)中的行為目前仍然是一個(gè)開(kāi)放性的研究課題[17]。本文以P2P流媒體網(wǎng)絡(luò)中節(jié)點(diǎn)的播放緩存為研究對(duì)象，采用理論建模的方法對(duì)穩(wěn)態(tài)條件下的P2P流媒體傳輸行為加以研究，主要工作包括：

1) 應(yīng)用排隊(duì)理論證明了穩(wěn)態(tài)條件下 P2P流媒體系統(tǒng)可模擬為多個(gè) M/M/n排隊(duì)系統(tǒng)串聯(lián)形成的排隊(duì)鏈，給出了P2P流媒體穩(wěn)態(tài)傳輸模型建立的理論依據(jù)；

2) 分析了穩(wěn)態(tài)條件下節(jié)點(diǎn)播放緩存的占用率，并以此為基礎(chǔ)建立P2P流媒體系統(tǒng)的穩(wěn)態(tài)傳輸模型；

3) 考察了不同chunk調(diào)度策略的傳輸特性，以驗(yàn)證P2P流媒體穩(wěn)態(tài)傳輸模型的準(zhǔn)確性，并進(jìn)一步考察了系統(tǒng)中節(jié)點(diǎn)數(shù)量、節(jié)點(diǎn)緩存大小對(duì)傳輸特性的影響。

后續(xù)內(nèi)容安排如下：第2節(jié)分析了P2P流媒體在覆蓋網(wǎng)中的分發(fā)模型，建立了P2P流媒體穩(wěn)態(tài)傳輸模型；第3節(jié)考察了不同chunk調(diào)度策略的傳輸特性，節(jié)點(diǎn)數(shù)量、節(jié)點(diǎn)緩存大小對(duì)傳輸特性的影響；最后，第4節(jié)是結(jié)束語(yǔ)。

2 P2P流媒體穩(wěn)態(tài)傳輸模型

2.1 P2P流媒體分發(fā)模型

早期的P2P文件共享網(wǎng)絡(luò)中，對(duì)等節(jié)點(diǎn)在獲得整個(gè)原始文件之后才向外提供服務(wù)，這在本質(zhì)上屬于一種無(wú)流水線的存儲(chǔ)轉(zhuǎn)發(fā)工作模式，導(dǎo)致其在大文件傳輸時(shí)效率較低。為此，研究人員提出了基于chunk的 P2P傳輸機(jī)制，每個(gè)文件被分割為多個(gè)chunk，節(jié)點(diǎn)可同時(shí)下載所有的chunk，單個(gè)chunk下載完畢后即可對(duì)外提供服務(wù)，而無(wú)需等待整個(gè)文件下載完成，這與流媒體業(yè)務(wù)的流式傳輸思想一致。另一方面，流媒體業(yè)務(wù)的傳輸和播放具有嚴(yán)格的實(shí)時(shí)性、時(shí)序性以及連續(xù)性，且流式傳輸方式使得節(jié)點(diǎn)無(wú)需進(jìn)行大量的媒體內(nèi)容存儲(chǔ)，所有下載的chunk均暫存于一片空間有限的播放緩存中，隨著流媒體內(nèi)容的播放進(jìn)度，新下載的chunk會(huì)逐漸覆蓋過(guò)期的chunk。于是，在P2P流媒體系統(tǒng)中，單個(gè)節(jié)點(diǎn)的主要任務(wù)就是在任意時(shí)刻選擇合適的對(duì)等節(jié)點(diǎn)并下載合適的 chunk以保證流媒體內(nèi)容播放的連貫性，同時(shí)向其他對(duì)等節(jié)點(diǎn)提供chunk下載服務(wù)。

圖1 K個(gè)chunk的流媒體分發(fā)模型

假設(shè)P2P流媒體分發(fā)系統(tǒng)由一個(gè)流媒體服務(wù)器和自由加入和退出該系統(tǒng)的節(jié)點(diǎn)組成，其中待分發(fā)流媒體內(nèi)容的大小為K個(gè)chunk，每個(gè)節(jié)點(diǎn)播放緩存B大小為n個(gè)chunk，且可以根據(jù)給定chunk調(diào)度策略同時(shí)從流媒體服務(wù)器或其他對(duì)等節(jié)點(diǎn)下載所需的 chunk，下載完成后即可向外提供服務(wù)。從單個(gè)流媒體chunk的角度看，其分發(fā)過(guò)程可以模擬為一個(gè)G/G/ni的排隊(duì)系統(tǒng)，其中，排隊(duì)系統(tǒng)服務(wù)器由流媒體服務(wù)器和緩存有該 chunk的所有 peer組成。如圖1所示，整個(gè)流媒體內(nèi)容的分發(fā)過(guò)程可以由K個(gè)G/G/ni排隊(duì)系統(tǒng)串聯(lián)的排隊(duì)鏈很好地模擬，其中，ni為當(dāng)前時(shí)刻第i(i=1, 2, …, K)個(gè)隊(duì)列的服務(wù)器數(shù)量，λi為第 i個(gè)隊(duì)列的平均達(dá)到速率，其輸出速率為λi+1，也即下一個(gè)隊(duì)列的輸入速率。

當(dāng)P2P流媒體分發(fā)系統(tǒng)的節(jié)點(diǎn)到達(dá)速率服從泊松分布，每個(gè)chunk的下載速率服從指數(shù)分布時(shí)，可以得到如下定理1。

定理1 若進(jìn)入P2P流媒體分發(fā)系統(tǒng)的節(jié)點(diǎn)到達(dá)過(guò)程為泊松過(guò)程，且單個(gè)chunk的下載時(shí)間服從指數(shù)分布時(shí)，則K個(gè)chunk的流媒體分發(fā)系統(tǒng)穩(wěn)態(tài)過(guò)程可模擬為一條由K個(gè)M/M/n排隊(duì)系統(tǒng)串聯(lián)的排隊(duì)鏈。

證明 考慮第一個(gè)虛擬排隊(duì)系統(tǒng)，節(jié)點(diǎn)的到達(dá)過(guò)程為泊松過(guò)程，且到達(dá)速率為 λ，而單個(gè) chunk的服務(wù)時(shí)間服從參數(shù)為μ的指數(shù)分布，由此，第1個(gè)chunk的分發(fā)過(guò)程為M/M/n排隊(duì)系統(tǒng)。為了分析后續(xù)排隊(duì)系統(tǒng)，需要進(jìn)一步考察節(jié)點(diǎn)在第1個(gè)排隊(duì)系統(tǒng)中服務(wù)完畢的間隔時(shí)間。

假設(shè)在某個(gè)節(jié)點(diǎn)結(jié)束服務(wù)離開(kāi)第1個(gè)排隊(duì)系統(tǒng)時(shí)，系統(tǒng)中仍有h個(gè)peer在接受服務(wù)。由指數(shù)分布的無(wú)記憶特性，可以將此時(shí)刻看成h個(gè)peer剛剛開(kāi)始接受服務(wù)的零時(shí)刻。設(shè)每個(gè)peer的服務(wù)時(shí)間分別為Bj(j=1, 2, …, h)，于是，當(dāng)下一個(gè)節(jié)點(diǎn)服務(wù)完畢，即服務(wù)時(shí)間為

時(shí)，該節(jié)點(diǎn)離開(kāi)第1個(gè)排隊(duì)系統(tǒng)，此時(shí)系統(tǒng)中節(jié)點(diǎn)的服務(wù)時(shí)間再次置零。當(dāng)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，到達(dá)和離開(kāi)第1個(gè)排隊(duì)系統(tǒng)的節(jié)點(diǎn)數(shù)量相當(dāng)。于是，第1個(gè)排隊(duì)系統(tǒng)中 peer服務(wù)完成間隔時(shí)間為服從參數(shù)為μ·h的指數(shù)分布，即第2個(gè)排隊(duì)系統(tǒng)的到達(dá)過(guò)程為泊松過(guò)程。同理，后續(xù)排隊(duì)系統(tǒng)的輸入過(guò)程均為泊松過(guò)程。定理1得證。

上述排隊(duì)鏈達(dá)到穩(wěn)態(tài)時(shí)，到達(dá)和離開(kāi)每個(gè)排隊(duì)系統(tǒng)的節(jié)點(diǎn)數(shù)量相當(dāng)，即P2P流媒體分發(fā)系統(tǒng)中，每個(gè)流媒體chunk的分發(fā)速率保持穩(wěn)定。于是，P2P流媒體分發(fā)模型可進(jìn)一步簡(jiǎn)化為一個(gè)服務(wù)器與 M個(gè)節(jié)點(diǎn)組成，其中，每個(gè)節(jié)點(diǎn)播放緩存B大小為n個(gè)chunk，B(n)存儲(chǔ)即將播放的chunk，而B(niǎo)(1)存儲(chǔ)最新收到的chunk，初始狀態(tài)下，所有緩存均為空。本文接下來(lái)將基于該簡(jiǎn)化模型展開(kāi)討論。將時(shí)間離散化為單位時(shí)隙的離散序列，假設(shè)每個(gè)時(shí)隙內(nèi)節(jié)點(diǎn)最多可得到一個(gè) chunk服務(wù)(即播放緩存向后移動(dòng)一個(gè)chunk)。如圖2 所示，當(dāng)服務(wù)器分發(fā)第m個(gè)chunk時(shí)(t=m)，若 n-1≤m，則節(jié)點(diǎn)當(dāng)前正在播放第m-n+1個(gè)chunk；當(dāng)服務(wù)器分發(fā)第m+1個(gè)chunk時(shí)，第m-n+1個(gè)chunk被移出播放緩存，同時(shí)其他chunk依次向后移動(dòng)一個(gè)chunk，即播放緩存相當(dāng)于一個(gè)接受流媒體chunk的滑動(dòng)窗口，于是P2P流媒體分發(fā)系統(tǒng)的目標(biāo)即為保證B(n)在所有的時(shí)隙內(nèi)非空，以實(shí)現(xiàn)流媒體播放連續(xù)穩(wěn)定播放。

圖2 P2P流媒體節(jié)點(diǎn)播放緩存的滑動(dòng)窗口機(jī)制

令pk(i)表示穩(wěn)態(tài)時(shí)節(jié)點(diǎn)k的第i個(gè)緩存空間可向外提供服務(wù)的概率，即緩存 B(i)的占用率?？紤]傳統(tǒng)的客戶機(jī)/服務(wù)器模式，系統(tǒng)中僅有流媒體服務(wù)器提供服務(wù)，則pk(i)的分布[8]可表示為

其中，第1個(gè)等式表示節(jié)點(diǎn)被服務(wù)器選中接受服務(wù)的概率；第2個(gè)等式表示只有被服務(wù)器選中后，節(jié)點(diǎn)才可成功獲得服務(wù)。將p(1)=1/M視為歸一化的用戶到達(dá)速率，則對(duì)任意的 M＞1，均無(wú)法保證用戶100%得到服務(wù)，服務(wù)器性能瓶頸對(duì)流媒體分發(fā)性能的影響顯而易見(jiàn)。

在P2P流媒體分發(fā)模式下，每個(gè)節(jié)點(diǎn)可向服務(wù)器請(qǐng)求服務(wù)的同時(shí)也可向其他對(duì)等節(jié)點(diǎn)請(qǐng)求服務(wù)，即用戶獲得服務(wù)的概率與客戶機(jī)/服務(wù)器模式相比會(huì)產(chǎn)生一個(gè)增量qk(i)[8]，即P2P模式下，節(jié)點(diǎn)k的緩存占用率可表示為

其中，第1個(gè)等式表示初始狀態(tài)下，節(jié)點(diǎn)只能請(qǐng)求服務(wù)器得到服務(wù)；第2個(gè)等式表示在P2P模式下，節(jié)點(diǎn)除向服務(wù)器請(qǐng)求服務(wù)外，也可從其他對(duì)等節(jié)點(diǎn)處得到服務(wù)，其中，qk(i)與 peer選擇策略、chunk調(diào)度策略有關(guān)，當(dāng)系統(tǒng)中所有的節(jié)點(diǎn)采用相同的peer選擇策略、chunk調(diào)度策略時(shí)，穩(wěn)態(tài)條件下，qk(i)收斂于 q(i)。

給定節(jié)點(diǎn)k選擇節(jié)點(diǎn)h進(jìn)行P2P下載需要滿足以下條件：

1) 節(jié)點(diǎn)k的緩存中Bk(i)為空，將該事件表示為W(k, i)；

2) 節(jié)點(diǎn) h的緩存中 Bh(i)非空，將該事件表示為H(h, i)；

3) 根據(jù)peer選擇策略，節(jié)點(diǎn)k選中節(jié)點(diǎn)h，將該事件表示為S(k, h)；

4) 根據(jù) chunk調(diào)度策略，節(jié)點(diǎn) k在滿足條件W(k, i)、H(h, i)的所有chunk中，只能選擇第i個(gè)chunk下載，將該事件表示為R(k, h, i)。

于是，q(i)可表示為

在P2P理論模型分析的時(shí)候，同時(shí)考慮所peer選擇、chunk調(diào)度、負(fù)載均衡等問(wèn)題，往往使得模型過(guò)于復(fù)雜而無(wú)法求解[19]，為此，本文僅考慮完全隨機(jī)的 peer選擇策略，即peer選擇策略與其他事件獨(dú)立，Pr[S(k, h)]=1/(M－1)，于是

即q(i)的求解主要受2方面因素影響：1) 節(jié)點(diǎn)播放緩存穩(wěn)態(tài)時(shí)的占用率；2) chunk調(diào)度策略。為了簡(jiǎn)化處理，本文進(jìn)一步假設(shè)系統(tǒng)中各節(jié)點(diǎn)屬性完全相同，則在穩(wěn)態(tài)條件下，各節(jié)點(diǎn)的播放緩存占用率趨于一致，且當(dāng)系統(tǒng)中節(jié)點(diǎn)數(shù)目較大時(shí)，節(jié)點(diǎn)之間可近似認(rèn)為相互獨(dú)立[8]，在此基礎(chǔ)之上，有

chunk調(diào)度策略主要根據(jù)選定節(jié)點(diǎn)中播放緩存的占用情況選擇最合適的chunk下載，令 r(i)表示chunk調(diào)度策略下事件R(k, h, i)的概率，根據(jù)前面的假設(shè)，節(jié)點(diǎn)播放緩存的占用情況相互獨(dú)立且趨于一致，因此

將式(6)、式(7)、式(8)代入式(5)，得到 q(i)的分布情況為

于是，穩(wěn)態(tài)條件下，P2P流媒體分發(fā)模型為

2.2 P2P流媒體傳輸模型

上述P2P流媒體分發(fā)模型主要考察了P2P節(jié)點(diǎn)在覆蓋網(wǎng)中的行為，對(duì)正確理解P2P網(wǎng)絡(luò)特性具有重要的指意義；然而，P2P覆蓋網(wǎng)位于底層物理傳輸網(wǎng)絡(luò)之上，并不直接面向網(wǎng)絡(luò)資源，二者的信息可能具有不一致性，從而影響網(wǎng)絡(luò)中其他業(yè)務(wù)的正常傳輸。因此，有必要對(duì)P2P業(yè)務(wù)的傳輸特性展開(kāi)深入研究。本文接下來(lái)將重點(diǎn)考察P2P流媒體的傳輸會(huì)話、傳輸流量等特性。

P2P流媒體中節(jié)點(diǎn)在覆蓋網(wǎng)的交互行為必然觸發(fā)物理承載網(wǎng)絡(luò)中相應(yīng)的傳輸行為。假設(shè)2個(gè)對(duì)等節(jié)點(diǎn)間的每次交互過(guò)程由一個(gè)傳輸“會(huì)話”完成，本文將以P2P流媒體傳輸過(guò)程中的所有會(huì)話描述系統(tǒng)的傳輸行為。實(shí)際P2P流媒體分發(fā)系統(tǒng)中，節(jié)點(diǎn)交互時(shí)，可能還存在少量周期性的控制會(huì)話。為了降低模型的復(fù)雜度，本文在此做簡(jiǎn)化考慮節(jié)點(diǎn)間的整個(gè)交互過(guò)程均屬于同一個(gè)會(huì)話。

P2P流媒體分發(fā)系統(tǒng)中，根據(jù)peer選擇策略，節(jié)點(diǎn)k選擇從節(jié)點(diǎn)h請(qǐng)求服務(wù)，二者之間建立會(huì)話完成交互。根據(jù)是否得到所需的服務(wù)，可將會(huì)話進(jìn)一步分為成功型會(huì)話和失敗型會(huì)話，若節(jié)點(diǎn)k得到所需服務(wù)(成功下載到第i個(gè)chunk)，則此次會(huì)話為成功型會(huì)話；否則，為失敗型會(huì)話。

結(jié)合P2P流媒體分發(fā)模型中節(jié)點(diǎn)成功得到服務(wù)的4個(gè)條件和傳輸會(huì)話類型，有如下定理2成立。

定理2 P2P流媒體分發(fā)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，節(jié)點(diǎn)成功得到第i個(gè)chunk服務(wù)平均需要建立的傳輸會(huì)話數(shù)量Navg為

證明 根據(jù)P2P流媒體分發(fā)模型，只有節(jié)點(diǎn)k的第i個(gè)chunk緩存為空時(shí)，才需要向其他節(jié)點(diǎn)請(qǐng)求服務(wù)，將該事件表示為，而傳輸會(huì)話失敗主要來(lái)自于以下2個(gè)方面的原因：

1) 節(jié)點(diǎn)h的緩存不滿足上述條件2，即節(jié)點(diǎn)h的第i個(gè)chunk緩存為空，無(wú)法向外提供服務(wù)，將該事件表示為

2) 節(jié)點(diǎn)k和節(jié)點(diǎn)h的緩存不滿足上述條件4，即節(jié)點(diǎn)間的緩存不滿足chunk調(diào)度策略，導(dǎo)致傳輸會(huì)話失敗，將該事件表示為。

假設(shè)節(jié)點(diǎn)k向?qū)Φ裙?jié)點(diǎn)發(fā)起傳輸會(huì)話至成功下載到所需流媒體chunk止，共需建立k個(gè)傳輸會(huì)話，則該事件可表示為，其中，表示因?yàn)楣?jié)點(diǎn) 'h的緩存為空或節(jié)點(diǎn)k、 'h之間的緩存不滿足chunk調(diào)度策略而導(dǎo)致傳輸會(huì)話失敗，“[]∏·”表示k－1個(gè)相同事件同時(shí)發(fā)生。結(jié)合P2P流媒體分發(fā)模型中各事件發(fā)生的概率，可得

定理2得證。

由定理2可知，平均傳輸會(huì)話數(shù)量與穩(wěn)態(tài)時(shí)節(jié)點(diǎn)的緩存占有率p(i)以及chunk調(diào)度策略有關(guān)。如圖3所示，隨著緩存占用率的提高，節(jié)點(diǎn)需要向外請(qǐng)求服務(wù)的概率逐漸降低，當(dāng)緩存占用率為1時(shí)，節(jié)點(diǎn)不需要建立任何傳輸會(huì)話；隨著緩存調(diào)度策略成功概率的增加，節(jié)點(diǎn)單次傳輸會(huì)話即可獲得服務(wù)的概率也隨之升高，從而有效減少失敗型會(huì)話的發(fā)生，當(dāng)chunk調(diào)度策略r(i)=1時(shí)，可以得到平均會(huì)話數(shù)量的下限。

事實(shí)上，P2P覆蓋網(wǎng)與物理傳輸網(wǎng)之間信息的不一致也可導(dǎo)致P2P傳輸會(huì)話失敗，其主要原因是物理傳輸網(wǎng)絡(luò)中的路由協(xié)議僅保證自治域內(nèi)的最短傳輸路徑，而P2P覆蓋網(wǎng)中的peer選擇策略是基于整個(gè)互聯(lián)網(wǎng)的全局優(yōu)化目標(biāo)展開(kāi)，其結(jié)果可能導(dǎo)致對(duì)等節(jié)點(diǎn)分別屬于不同的自治域且域間路由不可達(dá)，使得P2P傳輸會(huì)話失敗，其效果相當(dāng)于在模型中的chunk調(diào)度策略中引入一個(gè)信息一致性因子γ(0＜γ＜1)，則節(jié)點(diǎn)的平均傳輸會(huì)話數(shù)量需修正為Navg=(1－p(i))/(p(i)r(i)γ)，其中，γ表示 P2P 覆蓋網(wǎng)中符合chunk調(diào)度策略的節(jié)點(diǎn)成功建立傳輸會(huì)話的概率，用來(lái)表征P2P覆蓋網(wǎng)與物理傳輸網(wǎng)之間節(jié)點(diǎn)信息的一致性。由于本文主要關(guān)注P2P流媒體中節(jié)點(diǎn)在覆蓋網(wǎng)中行為對(duì)物理傳輸網(wǎng)絡(luò)特性的影響，為了簡(jiǎn)化處理，本文仍以定理2的結(jié)論作為研究基礎(chǔ)。

圖3 不同緩存占有率及調(diào)度策略條件下節(jié)點(diǎn)的平均傳輸會(huì)話數(shù)量

根據(jù)定理2可得P2P流媒體系統(tǒng)處于穩(wěn)態(tài)時(shí)，peer節(jié)點(diǎn)傳輸會(huì)話模型為

網(wǎng)絡(luò)傳輸特性的另一個(gè)重要方面就是流量的變化規(guī)律。網(wǎng)絡(luò)測(cè)量和逆向工程研究結(jié)果表明，P2P流媒體中，節(jié)點(diǎn)在chunk數(shù)據(jù)傳輸前需要發(fā)送一定數(shù)量的控制報(bào)文(包含“握手”、端口協(xié)商等信息)，只有邏輯會(huì)話成功建立后，才可開(kāi)始數(shù)據(jù)傳輸過(guò)程。假設(shè)邏輯會(huì)話建立失敗時(shí)，每個(gè)節(jié)點(diǎn)的流量大小為Mf，邏輯會(huì)話建立成功時(shí)，每個(gè)節(jié)點(diǎn)的流量大小為 Ms，結(jié)合節(jié)點(diǎn)傳輸會(huì)話模型可得 P2P流媒體系統(tǒng)處于穩(wěn)態(tài)時(shí)，peer節(jié)點(diǎn)成功下載到所需chunk時(shí)的流量Mavg滿足如下定理3。

定理3 P2P流媒體分發(fā)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，節(jié)點(diǎn)成功得到第i個(gè)chunk服務(wù)時(shí)的平均流量為

證明 假設(shè)節(jié)點(diǎn)k向其他節(jié)點(diǎn)發(fā)起傳輸會(huì)話至成功下載到所需流媒體chunk止，共需建立k個(gè)傳輸會(huì)話，則前k-1次會(huì)話為失敗型會(huì)話，其流量為(k-1)Mf，最后一次會(huì)話為成功型會(huì)話，其流量為Ms，根據(jù)定理2 的證明過(guò)程有

定理2得證。

節(jié)點(diǎn)的平均流量實(shí)際上是傳輸會(huì)話加權(quán)平均后的結(jié)果，當(dāng)Mf=Ms=1時(shí)，節(jié)點(diǎn)的平均流量即為平均會(huì)話的數(shù)量。同理可得P2P流媒體系統(tǒng)處于穩(wěn)態(tài)時(shí)，節(jié)點(diǎn)的流量模型為

其中，Mf和 Ms分別為單個(gè)傳輸會(huì)話失敗和成功建立時(shí)節(jié)點(diǎn)的流量。

3 模型驗(yàn)證與分析

3.1 P2P流媒體chunk調(diào)度策略

由P2P流媒體模型可知，chunk調(diào)度策略在P2P流媒體傳輸過(guò)程中有著重要地位。本節(jié)主要根據(jù)P2P流媒體傳輸模型考察不同 chunk調(diào)度策略下P2P流媒體的傳輸特性，以此驗(yàn)證模型的準(zhǔn)確性。

現(xiàn)有的P2P流媒體chunk調(diào)度策略主要有2種：最大緊迫度優(yōu)先策略(most urgent first strategy)與最少數(shù)量?jī)?yōu)先策略(rarest first strategy)。最大緊迫度優(yōu)先策略主要根據(jù)流媒體播放的緊迫程度選擇優(yōu)先下載的 chunk，從緩存的角度看，B(n)為即將播放的 chunk，具有最大的緊迫度，B(n-1)次之，B(1)最??；節(jié)點(diǎn)k向節(jié)點(diǎn)h請(qǐng)求服務(wù)時(shí)，若節(jié)點(diǎn)h的緩存中B(n)非空，則節(jié)點(diǎn)k優(yōu)先下載B(n)，否則按照緩存狀態(tài)和播放緊迫程度順序選擇下載 B(n-1)至B(1)。最少數(shù)量?jī)?yōu)先策略主要根據(jù)系統(tǒng)中各 chunk的拷貝數(shù)量決定優(yōu)先下載的 chunk，從上述模型可以看到，節(jié)點(diǎn)緩存的占有率 p(i)隨 i逐漸遞增，即緩存B(1)的占有率最低，相應(yīng)的，系統(tǒng)中的拷貝數(shù)量最少，B(2)次之，B(n)拷貝數(shù)量最多；節(jié)點(diǎn)請(qǐng)求服務(wù)時(shí)，根據(jù)緩存狀態(tài)按照B(1), B(2),…, B(n)的先后順序下載各流媒體chunk。根據(jù)文獻(xiàn)[8]的分析結(jié)果，最大緊迫度優(yōu)先策略與最少數(shù)量?jī)?yōu)先策略分別可以用如下等式描述：

將式(13)、式(14)分別代入 P2P流媒體節(jié)點(diǎn)的傳輸會(huì)話模型與流量模型，得到不同chunk調(diào)度策略下，節(jié)點(diǎn)的傳輸會(huì)話與流量變化特征，其數(shù)值分析結(jié)果如圖4所示。

圖4 不同chunk調(diào)度策略下P2P流媒體傳輸特性

上述數(shù)值分析結(jié)果中，模型的各個(gè)參數(shù)分別為M=1 000，n=40，Mf=100，Ms=1 000?？梢钥吹剑S著chunk在節(jié)點(diǎn)中的位置逐漸升高，節(jié)點(diǎn)的傳輸會(huì)話數(shù)量、流量等屬性逐漸降低。同時(shí)，數(shù)值分析結(jié)果也反映出各種chunk調(diào)度算法的性能。當(dāng)r(i)=1時(shí)，節(jié)點(diǎn)的傳輸性能最優(yōu)，達(dá)到理論下限，可將實(shí)際chunk調(diào)度策略與該理論下限之間的差異作為chunk調(diào)度策略的評(píng)價(jià)指標(biāo)。從這個(gè)角度看，最少數(shù)量?jī)?yōu)先策略整體性能要明顯優(yōu)于最大緊迫度優(yōu)先策略，后者僅在即將播放的流媒體chunk下載性能上優(yōu)于前者，這與文獻(xiàn)[9]中給出的研究結(jié)論一致。最大緊迫度優(yōu)先策略過(guò)于強(qiáng)調(diào)單個(gè)節(jié)點(diǎn)播放的連貫性，導(dǎo)致系統(tǒng)中各個(gè)流媒體chunk的下載服務(wù)分布極不均勻，下載服務(wù)大量的偏重于即將播放的流媒體 chunk，從而導(dǎo)致系統(tǒng)整體傳輸性能的下降；最少數(shù)量?jī)?yōu)先策略以保證P2P流媒體系統(tǒng)中所有chunk下載服務(wù)的可用性為目標(biāo)，優(yōu)先下載系統(tǒng)中數(shù)量最少的chunk，提高其在系統(tǒng)中的拷貝數(shù)量，從而達(dá)到系統(tǒng)整體性能的提升。

另一方面，比較傳輸會(huì)話模型與流量模型的分析結(jié)果可以看到，二者的變化特征幾乎完全一致，僅在數(shù)值上相差大約 2個(gè)數(shù)量級(jí)，表明在P2P流媒體系統(tǒng)中存在著大量的失敗型傳輸會(huì)話，這些失敗會(huì)話占用了大量的網(wǎng)絡(luò)傳輸資源，極大地影響著 P2P流媒體系統(tǒng)以及整個(gè)網(wǎng)絡(luò)的傳輸效率。

3.2 節(jié)點(diǎn)數(shù)量對(duì)傳輸性能的影響

本節(jié)借助于P2P流媒體傳輸模型，考察了不同節(jié)點(diǎn)數(shù)量條件下系統(tǒng)的傳輸特性，數(shù)值分析結(jié)果如圖5所示，其中節(jié)點(diǎn)數(shù)量M的取值分別為100、500、1 000，節(jié)點(diǎn)緩存大小n=40。

可以看到，無(wú)論在何種chunk調(diào)度策略條件下，對(duì)于單個(gè)節(jié)點(diǎn)而言，系統(tǒng)中節(jié)點(diǎn)數(shù)量越多，其傳輸會(huì)話數(shù)量、傳輸流量也相應(yīng)增加。這是因?yàn)橄到y(tǒng)中節(jié)點(diǎn)數(shù)量越多，穩(wěn)態(tài)條件下單個(gè)節(jié)點(diǎn)緩存的占用率也越低，其向外提供服務(wù)的能力隨之下降，選擇這類節(jié)點(diǎn)請(qǐng)求服務(wù)傳輸會(huì)話失敗的可能性較大，在完全隨機(jī)的peer選擇策略條件下，最終導(dǎo)致整個(gè)P2P流媒體傳輸系統(tǒng)中失敗型傳輸會(huì)話的比例升高，這實(shí)際上是節(jié)點(diǎn)數(shù)量對(duì) chunk調(diào)度策略以及 peer選擇策略共同作用的結(jié)果。

圖5 不同節(jié)點(diǎn)數(shù)量下P2P流媒體傳輸特性

3.3 緩存大小對(duì)傳輸性能的影響

節(jié)點(diǎn)緩存大小體現(xiàn)了節(jié)點(diǎn)向外提供服務(wù)的能力。本節(jié)根據(jù)P2P流媒體傳輸模型分析了節(jié)點(diǎn)緩存大小對(duì)最大緊迫度優(yōu)先策略、最少數(shù)量?jī)?yōu)先策略傳輸特性的影響，數(shù)值分析結(jié)果如圖6所示，其中，緩存大小n分別為20、30、40，節(jié)點(diǎn)數(shù)量M=1 000。

不同的節(jié)點(diǎn)緩存大小對(duì)最少數(shù)量?jī)?yōu)先策略的傳輸特性幾乎沒(méi)有影響，但對(duì)最大緊迫度優(yōu)先策略的傳輸特性影響卻尤為明顯。究其原因，最少數(shù)量?jī)?yōu)先策略中，優(yōu)先下載系統(tǒng)中拷貝數(shù)量最少的chunk，使得所有chunk的服務(wù)提供能力分布比較均勻，保證單個(gè)節(jié)點(diǎn)的各chunk緩存占用率趨于一致，因此節(jié)點(diǎn)的傳輸會(huì)話數(shù)量、傳輸流量等受緩存大小影響較小；最大緊迫度優(yōu)先策略優(yōu)先下載即將播放的 chunk，導(dǎo)致單個(gè)節(jié)點(diǎn)緩存的占用率按照播放緊迫程度依次遞減，節(jié)點(diǎn)下載播放緊迫度最小的chunk時(shí)，會(huì)產(chǎn)生大量的失敗型傳輸會(huì)話，節(jié)點(diǎn)緩存越大，播放緊迫度最小的緩存占用率越低，失敗型傳輸會(huì)話的數(shù)量也相應(yīng)增大。

圖6 不同節(jié)點(diǎn)數(shù)量下P2P流媒體傳輸特性

4 結(jié)束語(yǔ)

P2P流媒體擺脫了服務(wù)器性能對(duì)系統(tǒng)擴(kuò)展性的束縛，具有廣泛的應(yīng)用前景。本文根據(jù)排隊(duì)理論分析了P2P流媒體分發(fā)模型，證明在穩(wěn)態(tài)條件下P2P流媒體分發(fā)系統(tǒng)可模擬為多個(gè)M/M/n排隊(duì)系統(tǒng)串聯(lián)形成的排隊(duì)鏈，并分析了節(jié)點(diǎn)播放緩存的占用率，以此為基礎(chǔ)建立了P2P流媒體系統(tǒng)的穩(wěn)態(tài)傳輸模型，本文還考察2類典型chunk調(diào)度算法的傳輸特性，得到與已有研究一致的結(jié)論，從而驗(yàn)證了模型的準(zhǔn)確性，并根據(jù)模型進(jìn)一步考察了節(jié)點(diǎn)數(shù)量、緩存大小對(duì)P2P流媒體傳輸特性的影響，無(wú)論在何種chunk調(diào)度策略，節(jié)點(diǎn)的傳輸會(huì)話數(shù)量、傳輸流量均會(huì)隨系統(tǒng)中節(jié)點(diǎn)數(shù)量的增加而增大，而最少數(shù)量?jī)?yōu)先chunk調(diào)度策略的傳輸特性受節(jié)點(diǎn)緩存大小的影響明顯小于最大緊迫度優(yōu)先策略。

進(jìn)一步的研究工作主要包括以下 2點(diǎn)。1)考察peer選擇策略對(duì)P2P流媒體系統(tǒng)傳輸特性的影響。當(dāng)節(jié)點(diǎn)的帶寬資源具有異構(gòu)性或節(jié)點(diǎn)的傳輸路徑上具有不同的瓶頸鏈路時(shí)，不同的peer選擇策略對(duì)充分利用網(wǎng)絡(luò)資源、減少網(wǎng)絡(luò)擁塞、降低失敗型傳輸會(huì)話的數(shù)量等具有重要意義。2)節(jié)點(diǎn)處理能力對(duì)P2P流媒體傳輸特性的影響。當(dāng)節(jié)點(diǎn)處理能力有限允許接入的傳輸會(huì)話數(shù)量有限時(shí)，系統(tǒng)中失敗型會(huì)話不可避免地需要增加，從而引起傳輸特性的改變，這種資源受限條件下的傳輸特性研究有利于準(zhǔn)確理解 P2P流媒體網(wǎng)絡(luò)、優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)、提升網(wǎng)絡(luò)整體性能。

[1] EL-SAYED A, ROCA V, MATHY L. A survey of proposals for an alternative group communication service[J]. IEEE Network, 2003,17(1): 46-51.

[2] NI J, TSANG H K. Large-scale cooperative caching and applicationlevel multicast in multimedia content delivery networks[J]. IEEE Communication Magazine, 2005, 43(5): 98-105.

[3] VAKALI A, PALLIS G. Content delivery networks: status and trends[J]. IEEE Internet Computing, 2003, 7(6): 68-74.

[4] PPStream website[EB/OL]. http://www.ppstream.com/, 2010.

[5] PPlive website[EB/OL]. http://www.pptv.com/, 2010.

[6] ZOU L, ZEGURA E W, AMMAR M H. The effect of peer selection and buffering strategies on performance of peer-to-peer file sharing systems[A]. Proc of Modeling, Analysis and Simulation of Computer and Telecommunications Systems[C]. Texas, USA, 2002. 63-70.

[7] GURSES E, KIM A N. Maximum utility peer selection for p2p streaming in wireless ad hoc networks[A]. Proc of IEEE Global Telecommunication Conference (GLOBECOM)[C]. New Orleans, LA,USA, 2008. 1-5.

[8] ZHOU Y, CHIU D, LUI J. A simple model for analyzing p2p streaming protocols[A]. Proc of IEEE International Conference on Network Protocols (ICNP)[C]. Beijng, China, 2007. 226-235.

[9] ZHOU Y, CHIU D, LUI J. A simple model for chunk-scheduling strategies in p2p streaming[J]. IEEE/ACM Transactions on Networking, 2011, 19(1):42-54.

[10] GUO Y, LIANG C, LIU Y. AQCS: adaptive queue-based chunk scheduling for p2p live streaming[A]. Proc of 7thIFIP Networking[C].Singapore, 2008.433-444.

[11] STUTZBACH S, REJAIE R. Understanding churn in peer-to-peer networks[A]. Proc of ACM SIGCOMM Conference on Internet Measurement (IMC)[C]. Rio de Janeiro, Brazil, 2006. 189-202.

[12] CUI Y, DAI L, XUE Y. Optimizing p2p streaming throughput under peer churning[A]. Proc of IEEE Global Telecommunication Confer-ence (GLOBECOM)[C]. Washington D C, USA, 2007. 231-235.

[13] SMALL T, LIANG B, LI B. Scaling laws and tradeoff in peer-to-peer live multimedia streaming[A]. Proc of ACM Multimedia[C]. Santa Barbara, CA, USA, 2006.539-548.

[14] WU D, LIU Y, ROSS K W. Queuing network models for multi-channel P2P live streaming systems[A]. Proc of IEEE Conference on Computer Communications (INFOCOM)[C]. Rio de Janeiro,Brazil, 2009. 73-81.

[15] Parallel & Distributed Operating Systems Group. P2P sim: a simulator for peer-to-peer protocols[EB/OL]. http://pdos. casil.mit.edu/p2psim/index.html.

[16] AGGARWAL V, AKONJANG O, FELDMANN A, et al. Reflecting p2p user behavior models in a simulation environment[A]. Proc of Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP)[C]. Toulouse, France, 2008. 516-523.

[17] WANG X, YAO Z, LOGUINOV D. Residual-based estimation of peer and link lifetimes in P2P networks[J]. IEEE/ACM Transactions on networking, 2009, 17(3):726-739.

[18] SEETHARAMAN S, AMMAR M. On the interaction between dynamic routing in the na?ve and overlay layers[A]. Proc of IEEE Conference on Computer Communications (INFOCOM)[C]. Barcelona,Spain, 2006. 1-12.

[19] BONALD T, MASSOULIE L, MATHIEU F. Epidemic live streaming:optimal performance trade-offs[A]. Proc of ACM SIGMETRICS[C].Annapolis, Maryland, USA, 2008. 325-336.