比特洪流協(xié)議網(wǎng)絡(luò)通信的主機(jī)分塊優(yōu)化算法

高 峰，陳金剛，陳 燈，朱 紅

(1.武漢工程大學(xué)校辦，湖北 武漢430205； 2.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢430074； 3.武漢工程大學(xué)法商學(xué)院,湖北 武漢430205)

0 引 言

端到端的應(yīng)用(Peer to Peer, P2P) 正在逐步占據(jù)互聯(lián)網(wǎng)業(yè)務(wù)中重要的位置.BitTorrent簡稱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].

1 虛擬主機(jī)的定義

現(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

2 最佳虛擬主機(jī)查找

從圖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ī)上,這無疑也是最快最有效的一種方法.

2.1 連接矩陣分塊的實(shí)現(xiàn)與比較

在大型網(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ò)簡化圖如圖2所示.

圖2 大型網(wǎng)絡(luò)簡化圖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).

2.2 算法測試

測試算法：

算法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

通過測試，證明算法是可行的.通過對(duì)BT網(wǎng)絡(luò)的分塊選擇策略的分析，虛擬主機(jī)在網(wǎng)絡(luò)中分布的越均勻網(wǎng)絡(luò)性能就越好，文獻(xiàn)[5]中的片段選擇算法和文獻(xiàn)[7]中的基于Seed的內(nèi)容分發(fā)算法也是基于同樣的目的提出了改進(jìn)的選擇算法.

3 結(jié) 語

在對(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)行了仿真測試，結(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].長沙：湖南大學(xué)，2008.

[9] 孫鵬.對(duì)等網(wǎng)絡(luò)集群下載模式的研究及應(yīng)用[D].鄭州：鄭州大學(xué)，2004.