基于在線概率的P2P網絡系統動力學模型①

王繼奎,殷保群

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

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

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

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

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

1 動力學模型

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

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

N表示系統中在線的用戶節點數目.由于我們引入了在線概率,所以系統的拓撲結構是穩定的;

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

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

M表示系統中文件片的數目;

ci表示節點i的上傳帶寬;

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

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

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

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

Q(t)表示t時刻系統中節點之間的連接關系矩陣,Q(t)=[qij(t)];

Ncap表示系統中每個節點最多可以服務的節點數目;

Nreq表示單個節點單位時間內可以向其它節點請求的文件片的最大數目.

下面介紹基于在線概率的P2P網絡系統的一般模型.

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

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

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

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

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

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

2 模型分析

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

2.1 帶寬分配算法

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

2.1.1 基準算法

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

2.1.2 改進算法

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

2.2 節點阻塞算法

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

2.2.1 基準算法

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

2.2.2 改進算法

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

2.3 節點選擇算法

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

2.3.1 基準算法

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

2.3.2 改進算法

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

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

其中,I(i,j)=1表示兩節點處于同一個ISP網絡中,I(i,j)=0表示兩個節點不處于同一個ISP網絡中.

3 實驗及分析

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

3.1 模型驗證

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

表1 實驗中采用的算法

圖1 實驗一中節點PN1狀態演化曲線

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

圖3 實驗一中節點PN3狀態演化曲線

重新尋找新的節點發起文件請求,這導致基于在線概率的動力學模型中各節點的狀態演化曲線抖動更厲害,從而我們驗證了基于在線概率動力學模型的正確性.

3.2 在線概率對系統演化的影響

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

圖4 實驗二中節點PN1狀態演化曲線

圖5 實驗二中節點PN2狀態演化曲線

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

圖7 實驗三中節點PN1狀態演化曲線

圖8 實驗三中節點PN2狀態演化曲線

圖9 實驗三中節點PN3狀態演化曲線

在文件傳輸的過程中,節點在線概率越小,那么向這個節點發出文件請求的節點需要更換源節點的概率越大,對應的節點狀態演化曲線的抖動越厲害,完成文件傳輸所需的時間越長.

4 結語

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

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應用系統用戶共享行為的復雜網絡模型.計算機應用研究,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.