高 峰,陳金剛,陳 燈,朱 紅
(1.武漢工程大學(xué)校辦,湖北 武漢430205; 2.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢430074; 3.武漢工程大學(xué)法商學(xué)院,湖北 武漢430205)
端到端的應(yīng)用(Peer to Peer, P2P) 正在逐步占據(jù)互聯(lián)網(wǎng)業(yè)務(wù)中重要的位置.BitTorrent簡(jiǎn)稱BT,是由美國軟件工程師BramCohen用Python語言編寫的源代碼公開的P2P 軟件,用于文件的分發(fā)[1-4].BT由如下幾個(gè)部分組成:.torrent文件、種子提供站點(diǎn)、目錄服務(wù)器和內(nèi)容發(fā)布者/下載者.
BT的基本工作原理是:首先上傳者把一個(gè)文件分成若干個(gè)部分(以下用A、B、C等英文字母表示),甲在服務(wù)器隨機(jī)下載了第A部分,乙在服務(wù)器隨機(jī)下載了第B部分,這樣甲的BT就會(huì)根據(jù)情況到乙的電腦上去取乙已經(jīng)下載好的B分,乙的BT就會(huì)根據(jù)情況到甲的電腦上去取甲已經(jīng)下載好的A部分,交換文件的每個(gè)計(jì)算機(jī)都可以分?jǐn)偽募鬏數(shù)呢?fù)荷,這樣不但減輕了服務(wù)器的負(fù)荷,而且加快了用戶的下載速度,提高了效率[5-6].
現(xiàn)實(shí)中的網(wǎng)絡(luò)錯(cuò)綜復(fù)雜,無論是幾臺(tái)計(jì)算機(jī)之間形成的小型的網(wǎng)絡(luò),還是各種類型的網(wǎng)絡(luò)之間組合而形成的大型網(wǎng)絡(luò),BT系統(tǒng)總是盡可能的使種子文件的所有片段均勻的發(fā)布到網(wǎng)絡(luò)中去[7],所以在進(jìn)行BT下載時(shí)就要考慮到最佳虛擬主機(jī)的查找[5].
任何一個(gè)廣域網(wǎng)都是由許多局域網(wǎng)構(gòu)成的,根據(jù)局域網(wǎng)原理,處于同一網(wǎng)段下的電腦之間傳輸數(shù)據(jù)不僅速度快,而且不會(huì)占用主干的帶寬,可以選擇局域網(wǎng)中的一臺(tái)計(jì)算機(jī)為節(jié)點(diǎn)作為邏輯上的唯一與外部網(wǎng)絡(luò)連接的計(jì)算機(jī),就可以把這臺(tái)計(jì)算機(jī)稱作為虛擬主機(jī).也可以就把整個(gè)局域網(wǎng)看作是由虛擬主機(jī)分支出來的網(wǎng)絡(luò),其它的計(jì)算機(jī)只能通過虛擬主機(jī)上網(wǎng)[8].例如要從外部網(wǎng)絡(luò)下載一個(gè)文件,可以先用虛擬主機(jī)下載,然后別的計(jì)算機(jī)再從虛擬主機(jī)上下載,這樣下載的效率就會(huì)較高.所以首先要找出一臺(tái)最適合做虛擬主機(jī)的計(jì)算機(jī).
同樣,假設(shè)某個(gè)比較小的局域網(wǎng),它們都只有一臺(tái)主機(jī)與服務(wù)器相連,需要找出那臺(tái)主機(jī).例如某局域網(wǎng)有7臺(tái)計(jì)算機(jī),它們的連接如圖1如示.
圖1 網(wǎng)絡(luò)連接圖Fig.1 Network connection diagram
從圖1可以看出,3號(hào)計(jì)算機(jī)連接計(jì)算機(jī)數(shù)目最多,所以3號(hào)計(jì)算機(jī)是最佳虛擬主機(jī).從連接矩陣上也可以清楚的識(shí)別出哪臺(tái)計(jì)算機(jī)最適合做虛擬主機(jī).圖1對(duì)應(yīng)的連接矩陣如下:
現(xiàn)在定義一個(gè)2維數(shù)組A[m][n],遍歷矩陣的每一行(列),統(tǒng)計(jì)出每一行(列)的1的個(gè)數(shù),個(gè)數(shù)最多的那一行(列)即為虛擬主機(jī)代表的行(列).
算法描述如下:
算法1 FindOptimumVirtualMachine
輸入:網(wǎng)絡(luò)連接矩陣A[M][M]
輸出:最佳虛擬主機(jī)編號(hào)
步驟:
(1) 定義整形數(shù)組B[M]存放各虛擬主機(jī)的連接數(shù)
(2) 定義n記錄最佳虛擬主機(jī)編號(hào)
(3) 定義max記錄最大連接數(shù)
(4) For each element inBdo
(5) element = 0;
(6) End for
(7) For each row inAdo
(8) For each col inAdo
(9)B[row] =B[row] +A[row][col];
(10) End for
(11) End for
(12)n= 0;
(13) max =B[n];
(14) For each element inBdo
(15) if element > max then
(16) max = element;
(17)n= index of element;
(18) End if
(19) End for
(20)Outputn;
把上述矩陣輸入進(jìn)去,輸出結(jié)果為3,則計(jì)算機(jī)3連接的計(jì)算機(jī)最多,所以計(jì)算機(jī)3最適合做虛擬主機(jī).先用計(jì)算機(jī)3下載文件,然后再通過計(jì)算機(jī)3把文件傳到其它計(jì)算機(jī)上,這無疑也是最快最有效的一種方法.
在大型網(wǎng)絡(luò)中虛擬主機(jī)(對(duì)等節(jié)點(diǎn))的查找和定位比較復(fù)雜,歷時(shí)久,使整個(gè)網(wǎng)絡(luò)變慢,并且隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,通過廣播方式定位對(duì)等節(jié)點(diǎn)的方法將造成網(wǎng)絡(luò)流量急劇增加,從而導(dǎo)致網(wǎng)絡(luò)擁塞,把網(wǎng)絡(luò)分解成若干個(gè)小型網(wǎng)絡(luò)是一種可行的辦法[9].約定連接計(jì)算機(jī)臺(tái)數(shù)大于3的計(jì)算機(jī)為虛擬主機(jī),和虛擬主機(jī)相連的計(jì)算機(jī)如果不是其它分塊的虛擬主機(jī)那么就肯定和這臺(tái)虛擬主機(jī)在同一分塊內(nèi),如果是其它分塊的虛擬主機(jī)就劃入到其它分塊,這樣就能保證分塊之間不會(huì)有重復(fù)。下面介紹算法:
(1)通過2個(gè)循環(huán)遍歷連接矩陣A[M],找出那些1的個(gè)數(shù)大于3的行的下標(biāo)放在一個(gè)數(shù)組[M]上.
(2)只遍歷這些以C[i]為行標(biāo)的行,如果在這一行中的某一個(gè)元素為1,則遍歷這一列元素,計(jì)算這一列的1的個(gè)數(shù),存放在數(shù)組E[M]中.
(3)判斷數(shù)組E[M]的每一個(gè)元素,如果小于等于3,則相應(yīng)元素能劃入以上的分塊.
網(wǎng)絡(luò)簡(jiǎn)化圖如圖2所示.
圖2 大型網(wǎng)絡(luò)簡(jiǎn)化圖Fig.2 Large network simplified diagram
圖2相應(yīng)的連接矩陣如下:
算法描敘如下:
算法2 Partition
輸入:網(wǎng)絡(luò)連接矩陣A[M][M]
輸出:網(wǎng)絡(luò)分塊
步驟:
(1) 定義整形數(shù)組B[M]存放各虛擬主機(jī)的連接數(shù)
(2) 定義整形數(shù)組E[M][M]存放分塊
(3) 定義整形變量count記錄每列1的個(gè)數(shù),初始值為0
(4) For each element inBdo
(5) element = 0;
(6) End for
(7) For each row inAdo
(8) For each col inAdo
(9)B[row] =B[row] +A[row][col];
(10) End for
(11)End for
(12)For each element inBdo
(13) if element > 2 then
(14) 定義i= index of element
(15) For each e inA[i] do
(16) ife= 1 then
(17) 定義j= column of e;
(18) For each row inAdo
(19) Count +=A[row][j];
(20) End for
(21) if count < 3 then
(22)E[i][j] = 1;
(23) End if
(24) End if
(25) End for
(26) End if
(27) End for
(28)OutputE
把上述矩陣輸入,輸出結(jié)果如下:
4:0 1 2 3
5:6 7 8
結(jié)果表示矩陣分為兩塊,第一塊有0,1,2,3,4,其中4為虛擬主機(jī);第2塊有5,6,7,8,其中5為虛擬主機(jī).與預(yù)期的結(jié)果相符.
以上程序只能找到虛擬主機(jī)以及與虛擬主機(jī)相連的計(jì)算機(jī),即第一種子,在有些情況下可能會(huì)導(dǎo)致分塊不全,或者有的塊無法分入.例子如圖3所示.
圖3 較復(fù)雜的大型網(wǎng)絡(luò)連接圖Fig.3 Complex large network simplified diagram
把圖3相應(yīng)的連接矩陣輸入得到的結(jié)果為:
4:0 1 2 3
5:6 7 8
結(jié)果與圖2的結(jié)果一樣,但是圖3中的9號(hào)計(jì)算機(jī)就會(huì)“落空”,不屬于任何分塊,把這樣的計(jì)算機(jī)叫做第2種子.找到第2種子的方法為遍歷每個(gè)分塊矩陣的第1種子,把那些不屬于其它分塊的計(jì)算機(jī)劃入這個(gè)分塊以內(nèi),就像圖3中可以把9號(hào)計(jì)算機(jī)加入5號(hào)機(jī)為虛擬主機(jī)的分塊中.就可以找到第2種子,然后依此循環(huán)則能找到第3種子,第4種子……
這樣一直將全部的計(jì)算機(jī)遍歷完畢,直到所有的計(jì)算機(jī)都有自己的分塊.
整個(gè)網(wǎng)絡(luò)全部被劃分為小的局域網(wǎng).
測(cè)試算法:
算法3 Test
輸入:網(wǎng)絡(luò)連接矩陣A[M][M]
輸出:最佳虛擬主機(jī)編號(hào)與鄰接主機(jī)
步驟:
(1) 定義一個(gè)鄰接鏈表,存放各虛擬主機(jī)之間的鄰接關(guān)系
(2) 將矩陣A[M][M]轉(zhuǎn)換成鄰接鏈表表示List[N],其中Link中存放了虛擬主機(jī)與其它主機(jī)之間的鄰接關(guān)系.List[N].Link.Num表示連接主機(jī)個(gè)數(shù).
(3) 定義max記錄最大連接數(shù)
(4) 定義n保存最佳虛擬主機(jī)編號(hào)
(5) For each element in list do
(6) If List[N] .Link.Num > max then
(7) Max=List[N].Link.Num
(8)n=N
(9) End if
(10) Output List[N]
(11) For each element in List[N].Link do
(12) Output element(13) End for
通過測(cè)試,證明算法是可行的.通過對(duì)BT網(wǎng)絡(luò)的分塊選擇策略的分析,虛擬主機(jī)在網(wǎng)絡(luò)中分布的越均勻網(wǎng)絡(luò)性能就越好,文獻(xiàn)[5]中的片段選擇算法和文獻(xiàn)[7]中的基于Seed的內(nèi)容分發(fā)算法也是基于同樣的目的提出了改進(jìn)的選擇算法.
在對(duì)BitTorrent的虛擬主機(jī)算法進(jìn)行了分析后,發(fā)現(xiàn)虛擬主機(jī)在網(wǎng)絡(luò)節(jié)點(diǎn)中分布不均,影響了下載的效率.采用主機(jī)分塊算法,該算法的選擇策略可以讓虛擬主機(jī)在網(wǎng)絡(luò)中較為均勻分布.并從節(jié)點(diǎn)的物理位置分布和平均下載時(shí)間等幾個(gè)方面進(jìn)行了仿真測(cè)試,結(jié)果證明加入主機(jī)分塊算法的系統(tǒng)降低了下載時(shí)間,提供了下載的整體效率.
參考文獻(xiàn):
[1] Handurukande S B, Kermarrec A M, Fessant L F, et al. Peer sharing behavior in the eDonkey network, and implications for the design of server-less file sharing systems[J]. SIGOPS Oper Syst Rev, 2006, 40(4):359-371.
[2] Bram Cohen.Incentives Build Robustness in BitTorr-ent[EB/OL].http://bitconjurer.org/ BitTorrent/ bittorrentecon.pdf/2003-05-22.
[3] Karzonov A.Determining the maximal flow in a net-work by the method of preflows[J].Soviet Math Doklady, 1974(15):434-437.
[4] 熊偉,謝冬青,劉潔.一種結(jié)構(gòu)化P2P協(xié)議中的負(fù)載均衡方法[J].微電子學(xué)與計(jì)算機(jī),2008(10):76-79.
[5] 陸晨.對(duì)等式網(wǎng)絡(luò)模型的研究及應(yīng)用[D].合肥:合肥工業(yè)大學(xué),2003.
[6] 楊少軍,BT型的P2P網(wǎng)絡(luò)數(shù)據(jù)傳播的數(shù)理機(jī)制與優(yōu)化管理[D].廣州:廣東工業(yè)大學(xué),2012.
[7] 劉宏亮,BitTorrent核心算法研究與改進(jìn)[D].北京:北京交通大學(xué),2008.
[8] 楊祝林,BitTorrent系統(tǒng)中文件傳輸算法與優(yōu)化[D].長(zhǎng)沙:湖南大學(xué),2008.
[9] 孫鵬.對(duì)等網(wǎng)絡(luò)集群下載模式的研究及應(yīng)用[D].鄭州:鄭州大學(xué),2004.