基于在線概率的P2P網(wǎng)絡(luò)系統(tǒng)動力學(xué)模型①

王繼奎,殷保群

(中國科學(xué)技術(shù)大學(xué) 自動化系,合肥 230027)

隨著計算機網(wǎng)絡(luò)的快速發(fā)展,人們對各種信息、服務(wù)以及資源獲取的要求變得越來越高.傳統(tǒng)基于C/S架構(gòu)的應(yīng)用由于采用的是集中式的結(jié)構(gòu),使客戶端承擔(dān)著網(wǎng)絡(luò)擁堵所產(chǎn)生的巨大風(fēng)險.為了改善這種問題,研究人員提出了P2P技術(shù),通過Internet網(wǎng)絡(luò),把加入到網(wǎng)絡(luò)中的各個節(jié)點連接起來,實現(xiàn)節(jié)點之間資源、服務(wù)和信息的共享.P2P文件共享系統(tǒng)中的節(jié)點不僅可以向其它節(jié)點請求文件,也可以在本地存儲文件并為其它節(jié)點提供相關(guān)服務(wù).從微觀的角度來看,系統(tǒng)中節(jié)點從其它節(jié)點獲取所需文件的過程就是該節(jié)點與其它節(jié)點的交互過程.P2P文件共享系統(tǒng)中影響節(jié)點之間交互過程的算法有很多,主要有節(jié)點選擇算法、帶寬分配算法、文件阻塞算法等.

以P2P文件共享系統(tǒng)和流媒體服務(wù)系統(tǒng)為代表的網(wǎng)絡(luò)服務(wù)系統(tǒng)的流行使得P2P網(wǎng)絡(luò)的研究工作越來越熱,針對P2P網(wǎng)絡(luò)的研究主要包括基于實際測量流量數(shù)據(jù)和用戶數(shù)據(jù)的研究方法和基于模型的研究方法.很多學(xué)者基于實際測量的網(wǎng)絡(luò)數(shù)據(jù)以及系統(tǒng)用戶日志等用戶數(shù)據(jù),對P2P文件共享系統(tǒng)中的用戶行為特征進行分析,建立基于用戶行為的系統(tǒng)模型.Feng QY等人通過分析MAZE系統(tǒng)的用戶日志,對加入系統(tǒng)中用戶節(jié)點的重下載、文件審查、文件刪除以及搭便車行為進行建模,并分析了用戶節(jié)點行為特征的統(tǒng)計規(guī)律[1].山秀明等人以P2P文件共享系統(tǒng)中用戶節(jié)點所擁有的共享文件數(shù)量為主要參數(shù),建立了用戶共享行為的復(fù)雜網(wǎng)絡(luò)演化模型,研究了P2P網(wǎng)絡(luò)中不同的用戶節(jié)點在文件共享行為上的差異[2].還有一些學(xué)者通過對系統(tǒng)演化過程的分析,建立系統(tǒng)的數(shù)學(xué)模型,進而對系統(tǒng)的演化規(guī)律進行研究.Qiu DY等人提出了一個BT系統(tǒng)的流體模型,從宏觀角度分析系統(tǒng)中節(jié)點數(shù)目的演化過程和不同因素對系統(tǒng)的影響,但沒有考慮系統(tǒng)中各個節(jié)點狀態(tài)的變化[3].Yin BQ等人提出了一個P2P媒體分發(fā)網(wǎng)絡(luò)的動力學(xué)模型,并且分析了節(jié)點選擇算法和帶寬分配算法對系統(tǒng)的影響[4,5].不同于文獻[3],文獻[4,5]是從微觀角度對P2P文件共享系統(tǒng)進行研究的.

這些研究工作大多是對系統(tǒng)中用戶日志和網(wǎng)絡(luò)測量數(shù)據(jù)進行總結(jié),分析用戶行為的統(tǒng)計規(guī)律,建立系統(tǒng)的用戶行為模型;或通過對系統(tǒng)演化過程進行分析,建立系統(tǒng)的動力學(xué)模型,并沒有將用戶行為的統(tǒng)計規(guī)律和系統(tǒng)演化統(tǒng)一起來,因此研究結(jié)果的適應(yīng)性較差.實際上,系統(tǒng)中用戶行為和系統(tǒng)演化過程是交互影響、不可分割的整體,應(yīng)該將兩者統(tǒng)一起來進行研究.本文將系統(tǒng)中用戶行為的統(tǒng)計規(guī)律和P2P文件共享系統(tǒng)的結(jié)構(gòu)以及相關(guān)的算法結(jié)合起來研究,提出了一種基于在線概率的動力學(xué)模型來研究P2P文件共享系統(tǒng)的演化過程.

由于系統(tǒng)中用戶行為的隨機性以及其它的隨機因素的影響,節(jié)點加入和退出網(wǎng)絡(luò)的行為同樣是隨機的,為了更好地刻畫節(jié)點行為的隨機性,本文引入了節(jié)點的在線概率,然后,從微觀的角度研究了系統(tǒng)中節(jié)點之間文件的傳輸過程,并以節(jié)點待發(fā)送的數(shù)據(jù)量為狀態(tài)變量,建立了基于在線概率的動力學(xué)模型.在此基礎(chǔ)上,分析了節(jié)點選擇算法、帶寬分配算法與節(jié)點阻塞算法的具體形式,并對算法進行改進,提出了基于在線概率的節(jié)點選擇算法、帶寬分配算法與節(jié)點阻塞算法.最后通過仿真實驗對模型的正確性進行了驗證,并分析了在線概率對系統(tǒng)演化過程的影響.

1 動力學(xué)模型

系統(tǒng)中節(jié)點通過P2P文件共享系統(tǒng)向其它節(jié)點發(fā)起文件下載請求.其它節(jié)點在收到該節(jié)點發(fā)出的請求之后,根據(jù)既定的策略為其分配上傳帶寬.系統(tǒng)中每個節(jié)點從其它節(jié)點下載所需文件的同時也為這些節(jié)點分配上傳帶寬.

為了增加模型的拓展性,簡化研究工作,我們對系統(tǒng)做了一些必要的假設(shè):節(jié)點上線和下線的流量變化過程持續(xù)的時間可以忽略不計;系統(tǒng)下載帶寬遠大于上傳帶寬,也就是影響節(jié)點下載速度的瓶頸為節(jié)點的上傳帶寬;忽略節(jié)點之間握手信息的流量以及時間延遲.模型中定義了以下參數(shù):

N表示系統(tǒng)中在線的用戶節(jié)點數(shù)目.由于我們引入了在線概率,所以系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是穩(wěn)定的;

pi(t)表示t時刻系統(tǒng)中用戶節(jié)點i的在線概率,其中,0≤pi(t)≤1;

xi(t)表示t時刻節(jié)點i收到請求但還沒有發(fā)送出去的數(shù)據(jù)量,為t時刻節(jié)點i的狀態(tài)量;

M表示系統(tǒng)中文件片的數(shù)目;

ci表示節(jié)點i的上傳帶寬;

Dm表示編號為m的文件片的大小;

pmi(t)表示t時刻節(jié)點i是否擁有第m個文件片,當(dāng)節(jié)點i存儲第m個文件片時,pmi(t)=1,否則pmi(t)=0;

P(t)表示t時刻系統(tǒng)的文件存儲矩陣,其中,P(t)=[pmi(t)];

qij(t)表示t時刻系統(tǒng)中節(jié)點i和節(jié)點j之間的連接關(guān)系.當(dāng)節(jié)點j向節(jié)點i發(fā)出下載請求,并且節(jié)點i還沒有發(fā)完節(jié)點j請求的文件時,qij(t)=1;當(dāng)節(jié)點i已經(jīng)將節(jié)點j請求的數(shù)據(jù)發(fā)送完成或者節(jié)點j沒有向節(jié)點i發(fā)出下載請求時,qij(t)=0;

Q(t)表示t時刻系統(tǒng)中節(jié)點之間的連接關(guān)系矩陣,Q(t)=[qij(t)];

Ncap表示系統(tǒng)中每個節(jié)點最多可以服務(wù)的節(jié)點數(shù)目;

Nreq表示單個節(jié)點單位時間內(nèi)可以向其它節(jié)點請求的文件片的最大數(shù)目.

下面介紹基于在線概率的P2P網(wǎng)絡(luò)系統(tǒng)的一般模型.

函數(shù)fij(x1,···,xn,Q,pi,ci)表示t時刻節(jié)點i分配給節(jié)點j的上傳帶寬,反映了節(jié)點的帶寬分配算法;

函數(shù)kij(x1,···,xn,Q)表示t時刻節(jié)點i對來自節(jié)點j的文件下載請求的態(tài)度,如果節(jié)點i不想為節(jié)點j分配上傳帶寬,則會拒絕來自節(jié)點j的文件下載請求,反映的是節(jié)點阻塞算法;

函數(shù)αim(P,Nreq)表示t時刻節(jié)點i對文件片m的請求情況;

函數(shù)fij(x1,···,xn,Q,pi,ci)×kij(x1,···,xn,Q)表示在考慮節(jié)點阻塞算法的情況下,t時刻節(jié)點i分配給節(jié)點j的上傳帶寬;

通過以上的分析,我們得到系統(tǒng)動力學(xué)模型微分方程的一般形式為:

通過上述方程可以知道節(jié)點的狀態(tài)演變過程是由節(jié)點的帶寬分配算法、節(jié)點選擇算法、節(jié)點阻塞算法共同決定的.當(dāng)我們確定了這些算法的具體形式,我們就得到了動力學(xué)方程的具體形式.然后通過對得到的具體的動力學(xué)模型進行實驗仿真,就可以分析P2P文件系統(tǒng)中相關(guān)參數(shù)的演變,驗證系統(tǒng)模型的正確性.

2 模型分析

根據(jù)上面的討論,我們得到了基于在線概率的P2P網(wǎng)絡(luò)系統(tǒng)動力學(xué)模型的一般形式,下面我們將根據(jù)具體的算法,對P2P文件共享系統(tǒng)進行分析,并給出基于在線概率的改進算法.

2.1 帶寬分配算法

帶寬分配算法就是源節(jié)點將上傳帶寬按照某種策略分配給那些向它請求文件的節(jié)點.

2.1.1 基準(zhǔn)算法

一種簡單地帶寬分配算法就是將源節(jié)點的上傳帶寬平均分配給所有向該節(jié)點發(fā)出文件請求的節(jié)點.此時,我們得到等概率的帶寬分配算法的表達式如式(2).

2.1.2 改進算法

我們考慮節(jié)點行為的隨機性,不同的用戶節(jié)點的在線概率是不同的.在線概率越大的用戶節(jié)點應(yīng)該分得更多的上傳帶寬.此時,我們得到基于在線概率的帶寬分配算法的表達式如式(3).

2.2 節(jié)點阻塞算法

節(jié)點阻塞算法就是當(dāng)向源節(jié)點發(fā)出文件請求的用戶節(jié)點數(shù)超出源節(jié)點服務(wù)能力的時候,源節(jié)點將按照某種策略為其中部分節(jié)點提供服務(wù),拒絕其它節(jié)點所發(fā)出的文件下載請求.

2.2.1 基準(zhǔn)算法

一種簡單的節(jié)點阻塞算法是每個發(fā)出請求的節(jié)點都有相同的概率獲得源節(jié)點提供的服務(wù).此時,我們得到等概率的節(jié)點阻塞算法的表達式如式(4).

2.2.2 改進算法

我們考慮節(jié)點行為的隨機性,源節(jié)點會對那些對自己價值更大的節(jié)點也就是在線概率大的節(jié)點更加積極,會優(yōu)先滿足這些節(jié)點的文件請求,而對于那些對自己價值小的節(jié)點,則會拒絕為其分配上傳帶寬.此時,我們得到基于在線概率的節(jié)點阻塞算法的表達式如式(5).

2.3 節(jié)點選擇算法

節(jié)點選擇算法就是節(jié)點會根據(jù)服務(wù)器所返回的擁有所需文件片的節(jié)點列表,按照某種策略選擇源節(jié)點發(fā)出文件片下載請求.

2.3.1 基準(zhǔn)算法

一種簡單地節(jié)點選擇算法就是有文件片下載需求的節(jié)點以相同的概率向返回列表中的所有節(jié)點發(fā)出文件請求.此時,我們得到等概率的節(jié)點選擇算法的表達式如式(6).

2.3.2 改進算法

節(jié)點在選擇源節(jié)點時會優(yōu)先選擇在線概率大的節(jié)點作為文件服務(wù)的提供者,這樣可以減少因源節(jié)點在文件傳輸過程中退出系統(tǒng)而導(dǎo)致傳輸中斷,減少用戶節(jié)點重新向其它節(jié)點發(fā)起文件請求所引起的網(wǎng)絡(luò)抖動.此時,我們得到基于在線概率的節(jié)點選擇算法的表達式如式(7).

根據(jù)文獻[6]中提出的同ISP節(jié)點優(yōu)先選擇算法,我們對上述算法做出改進,此時,算法的表達式如式(8).

其中,I(i,j)=1表示兩節(jié)點處于同一個ISP網(wǎng)絡(luò)中,I(i,j)=0表示兩個節(jié)點不處于同一個ISP網(wǎng)絡(luò)中.

3 實驗及分析

本節(jié)通過兩組仿真對基于節(jié)點在線概率的動力學(xué)模型進行分析.首先對采用等概率算法的動力學(xué)模型和在線概率算法的動力學(xué)模型進行仿真,通過對比節(jié)點狀態(tài)演化曲線來驗證基于在線概率的動力學(xué)模型正確性.然后對在線概率服從不同正態(tài)分布的系統(tǒng)動力學(xué)模型進行仿真,分析在線概率變化對系統(tǒng)演化過程的影響.

3.1 模型驗證

假設(shè)系統(tǒng)擁有10個節(jié)點,分別用PN1,…,PN10來表示;系統(tǒng)中有30個文件片,我們把這30個文件片均存儲在PN1上;文件片的大小為20 KB;節(jié)點的上傳帶寬均為100 KB/s;我們規(guī)定,每個節(jié)點每時刻只能向其它節(jié)點請求2個文件片.實驗一中采用等概率的算法,實驗二中采用基于在線概率的算法,并且節(jié)點的在線概率服從正態(tài)分布N(0,0.81),實驗中采用的算法如表1所示.

表1 實驗中采用的算法

圖1 實驗一中節(jié)點PN1狀態(tài)演化曲線

如圖1所示,實驗一中PN1的文件傳輸過程在16 s之前就已經(jīng)結(jié)束了,其余節(jié)點的文件傳輸也均在16 s之前完成(見圖2及圖3).從圖4至圖6中可以看出,在基于在線概率算法的動力學(xué)模型中,節(jié)點PN1的文件傳輸過程一直持續(xù)到仿真結(jié)束.節(jié)點PN2在仿真時間內(nèi)沒有完成文件的傳輸.因為實驗一中各節(jié)點是一直處于在線狀態(tài)的,也就是節(jié)點的在線概率均為1,而實驗二中各節(jié)點的在線概率是滿足正態(tài)分布的隨機數(shù),均小于1.所以,與實驗一相比,實驗二中的節(jié)點完成文件傳輸所需的時間更長.對比實驗一和實驗二中對應(yīng)狀態(tài)的演化曲線,可以看出與實驗一相比,實驗二中相應(yīng)節(jié)點的狀態(tài)演化曲線抖動更厲害.這是由于實驗二是基于在線概率的算法進行文件傳輸?shù)?當(dāng)系統(tǒng)中某一節(jié)點的在線概率較小時,該節(jié)點在線的時間就比較短,在該節(jié)點在線狀態(tài)結(jié)束后,向其發(fā)出文件片請求的節(jié)點需要

圖3 實驗一中節(jié)點PN3狀態(tài)演化曲線

重新尋找新的節(jié)點發(fā)起文件請求,這導(dǎo)致基于在線概率的動力學(xué)模型中各節(jié)點的狀態(tài)演化曲線抖動更厲害,從而我們驗證了基于在線概率動力學(xué)模型的正確性.

3.2 在線概率對系統(tǒng)演化的影響

在上面仿真的基礎(chǔ)上,我們通過對系統(tǒng)中節(jié)點在線概率服從不同正態(tài)分布所對應(yīng)的動力學(xué)模型進行仿真,得到文件傳輸過程中各節(jié)點的狀態(tài)演化曲線,通過對比得到的節(jié)點狀態(tài)演化曲線,分析在線概率大小對系統(tǒng)文件傳輸過程的影響.

圖4 實驗二中節(jié)點PN1狀態(tài)演化曲線

圖5 實驗二中節(jié)點PN2狀態(tài)演化曲線

假設(shè)實驗三中系統(tǒng)節(jié)點的在線概率服從正態(tài)分布N(0,0.64),其余參數(shù)同實驗二.仿真結(jié)果如圖7至圖9所示.從圖7至圖9中可以看出,實驗三中節(jié)點PN1,PN2,PN3,在仿真時間內(nèi)均沒有完成文件的傳輸.對比實驗二和實驗三中對應(yīng)節(jié)點的狀態(tài)演化曲線,可以看出實驗二中曲線的抖動頻次更大,因為實驗二和實驗三相比,系統(tǒng)中節(jié)點的在線概率更小,節(jié)點的在線時長更短,系統(tǒng)中節(jié)點重新向其它節(jié)點發(fā)起文件請求的頻率更高,系統(tǒng)中文件傳輸過程持續(xù)的時間更長.

圖7 實驗三中節(jié)點PN1狀態(tài)演化曲線

圖8 實驗三中節(jié)點PN2狀態(tài)演化曲線

圖9 實驗三中節(jié)點PN3狀態(tài)演化曲線

在文件傳輸?shù)倪^程中,節(jié)點在線概率越小,那么向這個節(jié)點發(fā)出文件請求的節(jié)點需要更換源節(jié)點的概率越大,對應(yīng)的節(jié)點狀態(tài)演化曲線的抖動越厲害,完成文件傳輸所需的時間越長.

4 結(jié)語

本文將P2P文件共享系統(tǒng)中用戶行為的統(tǒng)計規(guī)律和系統(tǒng)的結(jié)構(gòu)結(jié)合起來分析,并引入在線概率,建立了基于在線概率的動力學(xué)模型.該模型很好的刻畫了系統(tǒng)中節(jié)點行為的隨機性,對實際環(huán)境的描述更加準(zhǔn)確,更加接近實際系統(tǒng).本文對系統(tǒng)的節(jié)點選擇算法、帶寬分配算法以及節(jié)點阻塞算法進行研究,并提出了基于在線概率的節(jié)點選擇算法、帶寬分配算法以及節(jié)點阻塞算法.最后通過仿真實驗,驗證了基于在線概率動力學(xué)模型的正確性,并對比分析了在線概率大小對系統(tǒng)演化過程的影響.該模型為研究P2P系統(tǒng)提供了一個更為有效的方法.

1Feng QY,Wu Y,Sun Y,et al.User behavior modeling in peer-to-peer file sharing networks:Dissecting download and removal actions.IEEE International Conference on Acoustics,Speech and Signal Processing.Taipei,China.2009.3477-3480.

2山秀明,劉旸,張林,等.P2P應(yīng)用系統(tǒng)用戶共享行為的復(fù)雜網(wǎng)絡(luò)模型.計算機應(yīng)用研究,2008,25(6):1853-1855.

3Qiu DY,Srikant R.Modeling and performance analysis of BitTorrent-like peer-to-peer networks.ACM SIGCOMM Computer Communication,2004,34(4):367-378.[doi:10.1145/1030194]

4Yin BQ,Guo D,Huang J,et al.Modeling and analysis for the P2P-based media delivery network.Mathematical and Computer Modelling,2012,55(3-4):1529-1539.[doi:10.1016/j.mcm.2011.10.043]

5Zhang HP,Yin BQ,Lu XN.A dynamic model of BitTorrentlike P2P file-sharing system.2012 31st Chinese Control Conference (CCC).Hefei,China.2012.5513-5517.

6Bindal R,Cao P,Chan W,et al.Improving traffic locality in BitTorrent via biased neighbor selection.Proceedings 26th IEEE International Conference on Distributed Computing Systems.Lisboa,Portugal.2006.66-76.