比特洪流協議網絡通信的主機分塊優化算法

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

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

0 引 言

端到端的應用(Peer to Peer, P2P) 正在逐步占據互聯網業務中重要的位置.BitTorrent簡稱BT，是由美國軟件工程師BramCohen用Python語言編寫的源代碼公開的P2P 軟件，用于文件的分發[1-4].BT由如下幾個部分組成：.torrent文件、種子提供站點、目錄服務器和內容發布者/下載者.

BT的基本工作原理是：首先上傳者把一個文件分成若干個部分(以下用A、B、C等英文字母表示)，甲在服務器隨機下載了第A部分，乙在服務器隨機下載了第B部分，這樣甲的BT就會根據情況到乙的電腦上去取乙已經下載好的B分，乙的BT就會根據情況到甲的電腦上去取甲已經下載好的A部分，交換文件的每個計算機都可以分攤文件傳輸的負荷，這樣不但減輕了服務器的負荷，而且加快了用戶的下載速度，提高了效率[5-6].

1 虛擬主機的定義

現實中的網絡錯綜復雜，無論是幾臺計算機之間形成的小型的網絡，還是各種類型的網絡之間組合而形成的大型網絡，BT系統總是盡可能的使種子文件的所有片段均勻的發布到網絡中去[7]，所以在進行BT下載時就要考慮到最佳虛擬主機的查找[5].

任何一個廣域網都是由許多局域網構成的，根據局域網原理，處于同一網段下的電腦之間傳輸數據不僅速度快，而且不會占用主干的帶寬，可以選擇局域網中的一臺計算機為節點作為邏輯上的唯一與外部網絡連接的計算機，就可以把這臺計算機稱作為虛擬主機.也可以就把整個局域網看作是由虛擬主機分支出來的網絡，其它的計算機只能通過虛擬主機上網[8].例如要從外部網絡下載一個文件，可以先用虛擬主機下載，然后別的計算機再從虛擬主機上下載，這樣下載的效率就會較高.所以首先要找出一臺最適合做虛擬主機的計算機.

同樣，假設某個比較小的局域網，它們都只有一臺主機與服務器相連，需要找出那臺主機.例如某局域網有7臺計算機，它們的連接如圖1如示.

圖1 網絡連接圖Fig.1 Network connection diagram

2 最佳虛擬主機查找

從圖1可以看出,3號計算機連接計算機數目最多，所以3號計算機是最佳虛擬主機.從連接矩陣上也可以清楚的識別出哪臺計算機最適合做虛擬主機.圖1對應的連接矩陣如下:

現在定義一個2維數組A[m][n]，遍歷矩陣的每一行(列)，統計出每一行(列)的1的個數，個數最多的那一行(列)即為虛擬主機代表的行(列).

算法描述如下：

算法1 FindOptimumVirtualMachine

輸入：網絡連接矩陣A[M][M]

輸出：最佳虛擬主機編號

步驟：

(1) 定義整形數組B[M]存放各虛擬主機的連接數

(2) 定義n記錄最佳虛擬主機編號

(3) 定義max記錄最大連接數

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

把上述矩陣輸入進去，輸出結果為3，則計算機3連接的計算機最多，所以計算機3最適合做虛擬主機.先用計算機3下載文件，然后再通過計算機3把文件傳到其它計算機上,這無疑也是最快最有效的一種方法.

2.1 連接矩陣分塊的實現與比較

在大型網絡中虛擬主機(對等節點)的查找和定位比較復雜，歷時久，使整個網絡變慢，并且隨著網絡規模的擴大，通過廣播方式定位對等節點的方法將造成網絡流量急劇增加，從而導致網絡擁塞，把網絡分解成若干個小型網絡是一種可行的辦法[9].約定連接計算機臺數大于3的計算機為虛擬主機，和虛擬主機相連的計算機如果不是其它分塊的虛擬主機那么就肯定和這臺虛擬主機在同一分塊內，如果是其它分塊的虛擬主機就劃入到其它分塊，這樣就能保證分塊之間不會有重復。下面介紹算法：

(1)通過2個循環遍歷連接矩陣A[M]，找出那些1的個數大于3的行的下標放在一個數組[M]上.

(2)只遍歷這些以C[i]為行標的行，如果在這一行中的某一個元素為1，則遍歷這一列元素，計算這一列的1的個數，存放在數組E[M]中.

(3)判斷數組E[M]的每一個元素，如果小于等于3，則相應元素能劃入以上的分塊.

網絡簡化圖如圖2所示.

圖2 大型網絡簡化圖Fig.2 Large network simplified diagram

圖2相應的連接矩陣如下：

算法描敘如下：

算法2 Partition

輸入：網絡連接矩陣A[M][M]

輸出：網絡分塊

步驟：

(1) 定義整形數組B[M]存放各虛擬主機的連接數

(2) 定義整形數組E[M][M]存放分塊

(3) 定義整形變量count記錄每列1的個數，初始值為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

把上述矩陣輸入，輸出結果如下：

4：0 1 2 3

5：6 7 8

結果表示矩陣分為兩塊，第一塊有0，1，2，3，4，其中4為虛擬主機；第2塊有5，6，7，8，其中5為虛擬主機.與預期的結果相符.

以上程序只能找到虛擬主機以及與虛擬主機相連的計算機，即第一種子，在有些情況下可能會導致分塊不全，或者有的塊無法分入.例子如圖3所示.

圖3 較復雜的大型網絡連接圖Fig.3 Complex large network simplified diagram

把圖3相應的連接矩陣輸入得到的結果為:

4：0 1 2 3

5：6 7 8

結果與圖2的結果一樣，但是圖3中的9號計算機就會“落空”，不屬于任何分塊，把這樣的計算機叫做第2種子.找到第2種子的方法為遍歷每個分塊矩陣的第1種子，把那些不屬于其它分塊的計算機劃入這個分塊以內，就像圖3中可以把9號計算機加入5號機為虛擬主機的分塊中.就可以找到第2種子，然后依此循環則能找到第3種子，第4種子……

這樣一直將全部的計算機遍歷完畢，直到所有的計算機都有自己的分塊.

整個網絡全部被劃分為小的局域網.

2.2 算法測試

測試算法：

算法3 Test

輸入：網絡連接矩陣A[M][M]

輸出：最佳虛擬主機編號與鄰接主機

步驟：

(1) 定義一個鄰接鏈表，存放各虛擬主機之間的鄰接關系

(2) 將矩陣A[M][M]轉換成鄰接鏈表表示List[N]，其中Link中存放了虛擬主機與其它主機之間的鄰接關系.List[N].Link.Num表示連接主機個數.

(3) 定義max記錄最大連接數

(4) 定義n保存最佳虛擬主機編號

(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

通過測試，證明算法是可行的.通過對BT網絡的分塊選擇策略的分析，虛擬主機在網絡中分布的越均勻網絡性能就越好，文獻[5]中的片段選擇算法和文獻[7]中的基于Seed的內容分發算法也是基于同樣的目的提出了改進的選擇算法.

3 結 語

在對BitTorrent的虛擬主機算法進行了分析后，發現虛擬主機在網絡節點中分布不均，影響了下載的效率.采用主機分塊算法，該算法的選擇策略可以讓虛擬主機在網絡中較為均勻分布.并從節點的物理位置分布和平均下載時間等幾個方面進行了仿真測試，結果證明加入主機分塊算法的系統降低了下載時間，提供了下載的整體效率.

參考文獻：

[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] 熊偉，謝冬青，劉潔.一種結構化P2P協議中的負載均衡方法[J].微電子學與計算機，2008(10)：76-79.

[5] 陸晨.對等式網絡模型的研究及應用[D].合肥：合肥工業大學，2003.

[6] 楊少軍，BT型的P2P網絡數據傳播的數理機制與優化管理[D].廣州:廣東工業大學，2012.

[7] 劉宏亮,BitTorrent核心算法研究與改進[D].北京：北京交通大學，2008.

[8] 楊祝林，BitTorrent系統中文件傳輸算法與優化[D].長沙：湖南大學，2008.

[9] 孫鵬.對等網絡集群下載模式的研究及應用[D].鄭州：鄭州大學，2004.