ＢｉｔＴｏｒｒｅｎｔ系統中一種近似全局最少優先的文件塊選擇策略

摘要：提出了一種近似全局最優的文件塊選擇策略——種子覆蓋網。在BitTorrent系統中，所有種子自組成一個應用層覆蓋網，每個種子保存已上傳文件塊信息；種子響應請求時通過種子覆蓋網查找下載者感興趣且上傳數目最少的文件塊上傳。模擬實驗表明，與純局部最少優先策略和SmartSeed策略相比較，在采用種子覆蓋網策略的BT系統中，節點平均下載時間縮短了25%~35%，并且下載第一塊和最后一塊的平均等待時間縮短了40%~60%。

關鍵詞：對等網絡； 文件塊選擇； 近似全局最少優先； 局部最少優先

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)05-1419-03

BitTorrent[1]系統是一種非常流行的P2P（peer－to－peer）內容分發系統，它已成為Internet上最重要的應用之一。BitTorrent流量已占整個Internet流量的35%，超過其他對等網絡及其應用流量的總和[2]。與傳統的P2P內容分發系統（如Gnutella、KaZaa和eMule等）不同，BitTorrent系統將興趣相同的節點組建成一個對等網絡，文件被分割成大小相同的文件塊（chunk/block），每個節點可以并行下載多個文件塊，節點之間以協作的方式快速和高效地分發文件塊。

文件塊選擇策略是BitTorrent系統性能的關鍵。文件塊選擇策略是節點的請求服務策略，即如何請求文件塊和節點。BitTorrent系統采用局部最少優先算法[3]作為文件塊選擇策略，即每個節點選擇本身所缺少的且鄰居節點上數量最少的文件塊優先下載。局部最少優先算法的目的是保證每個文件塊均勻地分布在BitTorrent系統中，避免最后一塊問題（last block problem），即快完成節點在最后階段花費過長的時間下載最后幾個文件塊。但BitTorrent系統在節點選擇策略方面仍面臨一些挑戰：文獻[4]指出，由于LRF策略僅僅基于局部信息，該策略僅在低帶寬并且鄰居度數多時平均上傳帶寬利用率高于隨機策略；在低帶寬并且鄰居度數少時，LRF策略的平均上傳利用率反而低于隨機策略；在高帶寬時，隨機策略與LRF策略的平均上傳利用率基本持平。針對上述問題，本文從全局最優的角度考慮，提出構建一種近似全局最少優先上傳的文件塊選擇策略——種子覆蓋網的全新方案，由種子根據近似全局信息決定上傳文件塊，以確保文件塊的均勻分發，有效提高帶寬上傳利用率。

1相關工作

BitTorrent系統是目前實際部署最成功的大規模P2P內容分發系統之一，已受到越來越多的研究者關注。文獻[4~8]通過實際仿真實驗數據統計分析和基于模擬器的模擬實驗，指出BitTorrent分發文件的高效性、良好的可擴充性、對于污染的魯棒性等優良性能；同時也存在不能有效緩解第一塊和最后一塊長時間等待問題、不能有效防止不公平性、抗自私節點攻擊能力弱等缺點。文獻[4]提出了以犧牲資源利用率來消除節點之間的上傳/下載文件塊的不公平性的成雙成對（pairwise block－level）TFT的折中算法；同時還提出SmartSeed策略來節約種子節點的帶寬資源和減少BitTorrent中重復文件塊數量。文獻[8]提出一種新的Tit－For－Tat節點選擇策略，將下載速度和服務有效性折中以延長系統生命期。文獻[9]分析了Bit-Torrent性能的局限性，并提出采用基于圖的多洪流模型（mul-titorrent model）來研究BitTorrent中洪流之間的協作。

與已有研究工作不同，本文用模擬分析的方法研究以負載換取效率，提出搭建種子覆蓋網策略，以極少的種子之間的信息交換換取系統全局文件塊狀態，降低種子上傳文件塊的重復率，縮短最后一塊的等待時間，提高系統資源利用率。

2文件塊選擇策略

2．1局部最少優先的文件塊選擇策略

BT系統中有兩類節點：種子（seed），已經下載到全部文件塊的節點；下載者（leecher），還沒有下載完全的節點。BT系統中，一個共享文件分成很多個文件塊，每個節點在下載時除了自身已經擁有的文件塊之外，其他的文件塊都可以下載。優先選擇哪一塊文件塊下載是由LRF的文件塊選擇策略決定的；下載者根據鄰居所擁有的文件塊副本數目（局部信息）作決定，選擇自己感興趣的文件塊中鄰居副本數目最少的文件塊（局部最少）優先下載(圖1)。

圖1中，節點A有五個鄰居節點B，C，D，E，F。為簡化示例，設總文件塊數為5，文件塊編號為0~4；節點A的鄰居中，節點E為種子，其他節點均為下載者。各節點擁有文件塊數如圖1所示，下載者A擁有文件塊1、3，感興趣的文件塊有0、2、4，所有鄰居擁有的文件塊副本數目分別為2、4、3；下載者A采用局部最少優先的文件塊選擇策略，0號文件塊的副本數目局部最少，應優先下載文件塊0。而擁有0號文件塊的鄰居只有節點E、F，節點A則同時向E和F發出請求，申請下載0號文件塊，但只從響應最快的鄰居處下載該文件塊。假設此時E和F對于A均處于激活狀態[3]，則響應請求上傳0號文件塊。

2．2SmartSeed文件塊選擇策略

針對局部最少優先策略中存在的問題，Bharambe等人[4]提出一種SmartSeed文件塊選擇策略，對種子節點的上傳文件塊操作有所改進，即增加種子節點統計自身上傳的文件塊副本數目功能。在請求節點所缺少的文件塊中優先選擇自身已上傳的文件塊副本數目最少的文件塊上傳，以保證系統中分發文件塊的多樣性。但這種策略往往只適用于單種子系統。然而絕大多數時間，BitTorrent中是有多個種子并存的，包括初始種子和參與節點下載完成轉變的新種子。在多種子系統中，由于SmartSeed策略中的種子節點之間不能交互數據，不能相互協調，這樣可能造成在這個種子節點上傳較少的文件塊而在其他種子節點卻上傳較多文件塊，或者造成多個種子節點同時上傳相同的文件塊，尤其在種子節點數目較多的時候，反而增加了上傳文件塊的重復度，不能保證文件塊的均勻分發。

3種子覆蓋網 

種子覆蓋網主要適用于多種子系統。在搭建初始網時，初始種子向tracker服務器索要其他種子的信息，并采用結構化P2P網絡的方式自適應組建應用層種子覆蓋網。種子覆蓋網中種子之間可以交互信息。由于絕大部分文件塊上傳服務都是由種子來提供的，并且每個新種子在加入種子覆蓋網時，把自己在下載節點階段上傳的文件塊副本信息也提供給種子覆蓋網，可以說種子覆蓋網中的文件塊副本信息近似為全局信息。系統中當有節點完成文件下載即角色轉變為種子時，若其鄰居中有種子則聯系該鄰居并加入種子覆蓋網；若其鄰居中沒有種子，則向tracker請求其他種子信息以加入種子覆蓋網。所有種子以友好方式離開，通知所有相關鄰居。

3．1近似全局最少優先的文件塊選擇策略

針對局部最少優先策略以及SmartSeed策略存在的局部限制，本文提出從全局角度來解決問題，有效協調種子節點之間的文件塊上傳，確保系統中文件塊的均勻分發。種子通過種子覆蓋網可獲取所有種子上傳的文件塊副本總數目，即近似全局信息；下載者向種子申請下載時，由種子決定上傳哪一個文件塊，優先選擇發出申請的下載者感興趣的文件塊中上傳副本總數目最少的文件塊上傳，即近似全局最少優先。本文把這種上傳策略稱做近似全局最少優先的文件塊選擇策略。

如圖2所示，節點的鄰居狀況以及各節點擁有的文件塊數與圖1相同。惟一不同的是此處的種子上傳時采用近似全局最少優先上傳的文件塊選擇策略，由種子決定上傳的文件塊。由圖1分析可知，下載者A采用LRF策略不變，優先向種子E申請下載0號文件塊。但此時種子E并不一定為下載者A上傳0號文件塊，而是根據種子覆蓋網中各文件塊上傳的副本數目，即近似全局信息來決定。現假設種子E通過種子覆蓋網獲取各文件的上傳副本總數目分別為10、16、9、21、5；種子E先篩選出下載者A感興趣的文件塊副本數目有10、9、5。此時，在下載者A所缺少的文件塊中4號文件塊的上傳副本數目是最少的，則種子E認為此刻優先上傳的文件塊應為4號文件塊（即近似全局最少優先上傳），則種子E響應節點A的請求時，上傳的是4號文件塊而不是節點A所請求的0號文件塊。

3．2種子覆蓋網

1）種子覆蓋網的特點

種子功能擴充，具有以下功能：a）根據近似全局最少優先上傳的文件塊選擇策略，由種子決定應上傳哪一塊為當前最優的文件塊。b）統計種子自身上傳的各文件塊副本數目，并動態更新種子覆蓋網中各文件塊的總副本數目。c）可通過種子覆蓋網中查找負載輕或符合其他條件的非鄰居種子。

2）負載平衡

種子之間可以相互協調負載，若種子負載過重則可以通過種子覆蓋網查找負載較輕的種子，并推薦給下載者。此時下載者可視具體情況作如下處理：a）被推薦的種子已經在下載者的鄰居列表中，則請求重新推薦。b）被推薦的種子不在下載者的鄰居列表中，有兩種情況：若下載者鄰居度數已達到最大限度，則下載者主動刪除該負載過重的種子，并把被推薦的種子加為鄰居，然后申請下載；若下載者鄰居度數沒有達到最大限度，則直接把被推薦的種子加為鄰居并申請下載。

4實驗評估

這部分主要通過BT系統模擬器來研究采用種子覆蓋網策略的BT系統的性能，并與采用LRF策略以及采用Smart-Seed策略的BT系統性能作比較。

4．1實驗步驟

本文用C/C++設計和實現了BT系統模擬器。本文的模擬實驗均在該模擬器上進行。

為了能夠很好地評估系統的性能，本文考慮下載者完成下載的平均時間、等待第一塊以及最后一塊的平均時間。本文模擬器的很多條件不是很貼近實際，如節點的到達應服從泊松分布等。但本文實驗的目的并不是要構建一個完美的現實的模擬器，只是為了驗證采用種子覆蓋網策略的BT系統在多種子情況下比其他BT系統更優越。模擬器中使用的物理拓撲結構由Brite拓撲產生器產生。本文BT模擬器實現了BT的所有相關性能：Tit－for－Tat、樂觀激活等。實驗參數設置如表1所示。

4．2實驗結果

實驗內容為在100個節點組成的初始網基礎上，近1 000個節點在1 h內隨機加入系統；上傳/下載帶寬均為共享平分[4，10]；節點之間按照協議交互下載，直至全部下載完成結束。

a)通過截取20個時刻記錄4個初始種子負載情況，以考察采用種子覆蓋網策略的BT系統中負載平衡情況。

圖3中數據表明，在flash crowd階段，當大量節點蜂擁加入BT系統時，在采用LRF策略與SmartSeed 策略的BT系統中，各種子的負載分布很不均衡，部分種子連接數為5，而部分種子連接數為1或2，致使部分下載者死等而部分種子帶寬資源空閑浪費。在采用種子覆蓋網策略的BT系統中，各種子負載均衡，均為2~3連接數。由于種子覆蓋網自身的負載平衡功能，而且該策略分發文件塊副本數目均衡，大量下載者之間可以相互提供服務，減輕了種子負擔。

b)統計所有節點獲取第一塊與最后一塊的等待時間，以考察解決第一塊與最后一塊問題的效果。

圖4、5的實驗數據顯示：采用種子覆蓋網策略的BT系統中各下載者下載第一塊、最后一塊的等待時間曲線平滑，等待時間比較均衡，第一塊平均等待時間為84．71 s，最后一塊的平均等待時間為78．03 s；采用LRF策略的BT系統中各下載者的等待時間則波動比較大，第一塊平均等待時間為139．44 s，最后一塊的平均等待時間為215．04 s；采用SmartSeed策略的BT系統中各下載者的等待時間相對平緩，第一塊平均等待時間為145．75 s，最后一塊的平均等待時間為193．98 s。實驗數據表明，采用種子覆蓋網策略的BT系統中，獲取第一塊的平均等待時間比采用LRF策略的系統縮短了32．8%，比采用SmartSeed策略的系統縮短了41．8%；獲取最后一塊的平均等待時間比采用LRF策略的BT系統縮短了63．7%，比采用SmartSeed策略的BT系統縮短了59．3%。

c)統計所有節點從加入系統到下載完成的文件下載時間，以考察各BT系統的帶寬利用率情況。

圖6數據顯示，采用種子覆蓋網策略的BT系統中，下載者從加入系統到完成文件下載的平均時間從采用LRF策略的BT系統平均需要11 659．65 s以及采用SmartSeed策略的BT系統平均需要8 352．36 s縮短到只需要6 290．35 s，比采用LRF策略的BT系統縮短了37．7%，比采用SmartSeed策略的BT系統縮短了24．2%。實驗結果表明，采用種子覆蓋網策略的BT系統更充分地利用了網絡帶寬資源，提高了網絡吞吐率。

5結束語

本文提出了一種近似全局最少優先的文件塊選擇策略——種子覆蓋網，即在BitTorrent系統中，種子自組成一個應用層覆蓋網；當響應下載者的文件塊請求時，種子通過種子覆蓋網選擇下載者感興趣的且近似全局上傳數目最少的文件塊優先上傳，以保證各文件塊在系統中均勻分發。實驗結果表明，與LRF策略相比，種子覆蓋網策略在文件下載平均時間上縮短了37．7%；與SmartSeed策略相比，種子覆蓋網策略縮短了24.2%的文件下載平均時間；種子覆蓋網策略縮短了40%~60%的第一塊和最后一塊平均等待時間。但是，種子覆蓋網策略還存在一些問題，如種子覆蓋網的攪動問題，即種子快速且連續地加入和退出種子覆蓋網，這是本文的進一步研究工作。

參考文獻：

［1］BitTorrent[EB/OL].http://bittorrent.com.

[2]STEPHANOS A T，DIOMIDIS S.A survey of peer－to－peer content distribution technologies[J].ACM Computing Surveys，2004，36(4): 335-371.

[3]Bram Cohen.Incentives build robustness in BitTorrent[EB/OL].(2003-05-22)[2006-09-20].http://www.bittorrent.org/bittorrentecon.pdf.

[4]BHARAMBE A，HERLEY C，PADMANABHAN V.Analyzing and improving a BitTorrent network’s performance mechanisms[C]//Proc of IEEE INFOCOM.Barcelona:[s.n.]，2006.

[5]IZAL M，URVOY－KELLER G，BIERSACK E W，et al. Dissecting BitTorrent: five months in a torrent’s lifetime[C]//Proc of Passive Active Measurement Workshop (PAM’04). France:[s.n.]， 2004.

[6]POUWELSE J，GARBACKI P，EPEMA D，et al.The BitTorrent P2P file－sharing system: measurements and analysis[C]//Proc of the 4th International Workshop on Peer－to－Peer Systems(IPTPS’05). Ithaca， New York: Cornell University，2005.

[7]QIU D，SRIKANT S.Modeling and performance analysis of BitTorrent－Like peer－to－peer networks[J].ACM SIGCOMM Computer Communication Review Archive，2004，34(4):367-378.

[8]TIAN Ye， WU Di， NG K W.Modeling analysis and improvement for BitTorrent－Like file sharing networks[C]//Proc of IEEE Conference on Computer Communications(IEEE INFOCOM’06).Barcelona:[s.n.]， 2006.

[9]GUO L，CHEN S，XIAO Z，et al.Measurements analysis and modeling of BitTorrent－Like systems[C]//Proc of IMC 2005.Berkeley，CA:[s.n.]，2005.

[10]BHARAMBE A，HERLEY C，PADMANABHAN V.Some observations on BitTorrent[C]//Proc of ACM SigMetrics 2005.Banff: Association for Computing Machinery，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”