一種基于ＢｉｔＴｏｒｒｅｎｔ的節點選擇改進算法

摘要：當前P2P業務占據了大量的互聯網流量，在一定程度上對其他網絡業務造成了巨大的沖擊，該文主要以P2P典型軟件BitTorrent下載為例設計一個改進的節點選擇算法，有效降低節點對出口下載帶寬占用率。

關鍵詞：BitTorrent；出口下載帶寬；節點選擇算法

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)29-0389-02

An Improved Peer Selection Algorithm Based on the BitTorrent

LIU Zhi-dan1，WANG Guo-an2，MA Shi-ling1

(1.Department of Computer Science，Henan University，Kaifeng 475004，China;2.Network Center，Henan University，Kaifeng 475001，China)

Abstract: Currently， P2P business occupies a lot of Internet traffic and cause a tremendous impact to other network. This article mainly design a improved Peer Selection Algorithm Based on the BitTorrent download which is a typical example of P2P software.This algorithm can be proved Effective by Analysis in deducing download bandwidth.

Key words: BitTorrent; download bandwidth; peer selection algorithm

1 引言

隨著計算機和網絡技術的迅速發展， 文件共享的需求使得P2P技術脫穎而出。P2P技術以其能夠充分利用閑置的網絡資源， 實現有效的負載均衡的優勢，成為文件共享的熱門選擇。但是據德國互聯網調研機構ipoque稱，P2P已經徹底統治了當今的互聯網，其中50-90％的總流量都來自P2P程序。P2P共享給我們帶來便利的同時，其實也給不同網絡之間的路由交換帶來了壓力，影響到網絡上的其它服務[1]。本文主要以BitTorrent下載為例設計一個改進的節點選擇算法，有效降低節點對出口下載帶寬占用率。

2 BitTorrent技術分析

2.1 BitTorrent原理

普通的HTTP/FTP下載使用TCP/IP協議，BitTorrent協議是架構于TCP/IP協議之上的一個P2P文件傳輸協議，處于TCP/IP結構的應用層。 BitTorrent協議本身也包含了很多具體的內容協議和擴展協議，并在不斷擴充中。根據BitTorrent協議，文件發布者會根據要發布的文件生成提供一個.torrent文件，即種子文件，也簡稱為“種子”。.torrent文件本質上是文本文件，包含Tracker信息和文件信息兩部分[2]。Tracker信息主要是BT下載中需要用到的Tracker服務器的地址和針對Tracker服務器的設置，文件信息是根據對目標文件的計算生成的，計算結果根據BitTorrent協議內的B編碼規則進行編碼。它的主要原理是需要把提供下載的文件虛擬分成大小相等的塊，塊大小必須為2k的整數次方（由于是虛擬分塊，硬盤上并不產生各個塊文件），并把每個塊的索引信息和Hash驗證碼寫入.torrent文件中；所以，.torrent文件就是被下載文件的“索引”[3]。下載者要下載文件內容，需要先得到相應的.torrent文件，然后使用BT客戶端軟件進行下載。

下載時，BT客戶端首先解析.torrent文件得到Tracker地址，然后連接Tracker服務器。Tracker服務器回應下載者的請求，提供下載者其他下載者（包括發布者）的IP。下載者再連接其他下載者，根據.torrent文件，兩者分別對方告知自己已經有的塊，然后交換對方沒有的數據。此時不需要其他服務器參與，分散了單個線路上的數據流量，因此減輕了服務器負擔。下載者每得到一個塊，需要算出下載塊的Hash驗證碼與.torrent文件中的對比，如果一樣則說明塊正確，不一樣則需要重新下載這個塊。這種規定是為了解決下載內容準確性的問題[4]。

2.2下行帶寬計算

假設節點是穩定的，即下載過程不中斷。由于節點的到達看作是一種泊松過程，假設進入系統的節點流是參數為λ的泊松流，節點到達率為λ，以t=0 為初始時刻，則在任意時刻t系統的節點數為λt。通常把一個局域網、校園網等網絡看作是內網，那些信息交換需要跨越兩個局域網邊界路由器的看作是外網。假設對于資源R的共享中，內網的節點所占的比例為p，則外網的節點所占的比例為1-p。在時刻t，內網的節點數為： N1 =pλt，外網的節點數為： N2= (1-p)λt。

假設每個節點都達到了它的最大下載量，且它們的最大下載連接數都相同且為D。由于Tracker服務器在分發peer列表時是隨機的，可以把網內的各個peer看作有相同的比例（設定比例為q）的內網下載連接。以內網某個節點的下載連接列表的下載源來看，屬于內網節點數為D1= q*D，屬于外網peer 數為D2 =（1-q）*D 。再假設對內網中每個節點，它下載內網某節點資源的平均速率相同且均為b1 ；它下載外網某節點資源的平均速率相同且均為b2 。

設ta為目標節點完成下載所需要的時間，則，R1表示從內網下載的資源數據量；R2表示從外網下載的資源數據量。每個節點占用的出口下載帶寬，即單個節點占用的出口下行帶寬可以計算為b2*D2* ta。而整個內網所有peer 占用的總出口下載帶寬為。如圖1處于BitTorrent下載系統中的兩個局域網所示。

peerA和peer3都擁有目標節點peerT需要的文件片斷，peer3的have信息先于peerA到達目標節點，由于BT算法不考慮物理因素，目標節點peerT會選擇peer3優先下載，片斷下載會出現以下舍近求遠的場景。顯然，這是因為該算法以效率為優先考慮因素，并不考慮信息傳遞給邊界路由器帶來的傳輸壓力[5]。

3 改進的P2P算法模型

3.1 改進的P2P算法描述

鑒于此我們需要一個改進的用以降低路由壓力的方案，主要措施是建立一種可以考慮到物理因素的算法，在不影響下載效果的前提下讓節點選擇偏向于內網節點。令每個節點需要固定維護一些數據表：等待表是用來存放未下載資源標識的列表，進行表是用來存放正在下載片斷標識的列表；完成表是用來存放已下載片斷標識的列表。子片斷等待表和子片斷完成表是用來存放正在下載片斷的子片斷信息，實時記錄片斷下載的完成情況。最優排序表存放資源片斷標示以及與之對應的下載源的列表。對每個片斷的下載源，以內網節點下載源優先，外網節點下載源在后，各自按照連通性進行降序排列。鄰居節點發送來的擁有某個片斷的信息都會添加到等待表和最優排序表。最優排序表如表2所示。

Tracker服務器隨機向各個需要下載資源的節點分發peer列表， 節點又會向鄰居節點告知自己擁有的片段信息。各個節點會按照優先選擇連接數最少的文件片斷的最少優先法則進行下載，并且一旦開始下載某個片斷Q時，優先下載Q的子片斷。節點接收到鄰居節點發送而來的擁有片斷的信息建立列表，根據以上法則進行下載。

改進后的算法流程如下：

1) 目標節點取出等待表里排在第一位的片斷標識，如果等待表為空，則下載完成，否則繼續。等待表中的片斷以最少優先排序，從而盡量保證文件共享的完整性。假定取出的片斷標識為a。

2) 將片斷標識a寫入進行表，并從最優排序表讀取片斷標識a對應的前D個下載源寫入進行表。可以肯定的是，存在D個以上內網下載源的情況將不會占用出口的下行帶寬。片斷標識a的子片斷寫入子片斷等待表。

3) 目標節點向選擇的下載源發出子片斷請求，完成的子片斷寫入子片斷完成表。循環發出下載請求，記錄下載完成的子片斷并刪除子片斷等待表的相應項，循環此步直到子片斷等待表的數據為空，表明片斷a下載完畢。

4) 片斷a寫入完成表，目標節點向鄰居節點發出擁有片斷a的信息。將子片斷等待表和子片斷完成表清空。返回第一步。

3.2下行帶寬計算

存在D個以上內網下載源的情況將不會占用出口的下行帶寬。在內網下載源不足D個的情況下，片段將有一部分來源于外網，文件片段的到達近似于一個泊松過程。λp為文件片段的到達率，可知λp= b2D3， D3為同時從外網下載不同片段的內網peer 數。

設tb為目標節點完成下載所需要的時間，則tb=R/λp，R1表示從內網下載的資源數據量；R2表示從外網下載的資源數據量。每個節點占用的出口下載帶寬，即占用的出口下行帶寬可以計算為b2D2 *tb。而整個內網所有peer 占用的總出口下載帶寬為B2=b2*D2*tb*N1 。

現在來綜合比較，一般bt算法中整個內網所有peer 占用的總出口下載帶寬

可知比值y反映了改進后的算法占用的出口下行帶寬與原算法的比例關系。假設目標節點下載一個大小為512MB的文件，內網的節點數量占所有節點的為40%；它從內網節點下載連接的平均速率為80 Kb/s，從外網節點下載連接的平均速率為50 Kb/s， 在使用BT下載完成后，目標節點從內網、外網下載到的片段數比例為2：3；從外網同時下載不同片段的peer 數為100，peer的最大下載連結數為80， p變化區間為[0.4， 0.9]。根據以上條件和式（3）建立y值與p函數關系y=f(p)=。有y與p的變化曲線如圖3 y=f（p）函數關系曲線所示。

從圖3可以看出，y<0.67。也就是說，改進后的算法，路由器的出口下載帶寬下降到原算法的67%以下。而且隨著peer 下載列表的下載源中內網peer比例的提高，相對于原算法，局域網的出口下載帶寬將進一步降低。

4 性能與總結

該文在BT基礎上提出一種改進算法，優先選擇局域網內網下載源以降低出口下載帶寬的方案。在這種算法中，p2p系統中的每個節點需要維護一系列信息表，主要措施是建立一種可以考慮到物理因素的算法，在不影響下載效果的前提下讓節點選擇偏向于內網節點。并通過算法計算結果進行了效率比較，給出了該改進算法中各個參數對降低出口下載帶寬的影響，試驗結果表明，本文基于BT的P2P改進算法是一種可以有效降低邊界路由工作量的高效、可行的節點選擇算法。

參考文獻：

[1] 汪燕，柳斌.BitTorrent協議分析及控制策略[J].實驗技術與管理，2006(6):54-57.

[2] 丁林，程學旗.基于Bittorrent網絡的快速搜索策略[J].計算機工程，2007(2):111-113.

[3] 柳斌，李芝棠.基于訪問控制列表的BitTorrent流量控制策略[J].計算機應用與軟件，2006(5):19-34.

[4] 錢鳴，陳永生.基于規則的BitTorrent流量探測[J].計算機工程與設計，2008(1):357-359.

[5] 張增斌，陳陽.基于鄰近原則的BitTorrent實驗研究[J].廈門大學學報，2007(11):213-215.