P2P網絡中自適應節點選擇策略

王 城，陳興蜀，楊鄧奇，劉莉偉

（四川大學 計算機學院網絡與可信計算研究所，四川 成都610065）

0 引 言

P2P系統中節點選擇是影響系統服務性能的關鍵因素之一，實施一個好的節點選擇策略對整個系統性能的提高尤為重要。之前的研究工作已使得系統的性能在很大程度上提高，節約了大量的網絡帶寬資源。文獻 ［1］中X.Yang等人通過建立數學模型分析系統的服務性能，但是卻忽略系統中文件分布的特性。文獻 ［2－5］中提出了一種基于tracker端的鄰居節點選擇算法，考慮了節點地理位置的分布。文獻 ［6］提出了基于速率的節點選擇策略（TFT策略），采用阻塞算法（choking）中融入樂觀不阻塞算法（optimistic－unchoking，OU）的策略，以10s為阻塞算法周期，選擇4個上傳速度較快的節點作為自己上傳的對象，以30s為OU算法周期，隨機的選擇節點進行上傳，這樣能保證新加入節點獲取文件塊的機會，并且能更好的發現資源交互對象。但是這種節點選擇策略存在兩方面的不足：①雖然在tracker端實施鄰居節點選擇算法，但并未從本質上解決非tracker來源的節點，造成大量的跨網段、跨地域的帶寬流量，浪費帶寬資源。②傳統的節點選擇策略中，并不能根據具體網絡狀況，自調節節點選擇策略，以靈活的節點選擇策略充分適應網絡環境，保障各節點高效的分發性能。

針對以上問題，本文設計并實現P2P系統中自適應的節點選擇策略，該策略通過以鄰近節點優先連接與基于上傳帶寬利用率的節點選擇算法相結合，以實現P2P網絡高效、自適應的節點選擇。

1 自適應節點選擇機制

本文是在基于以C＋＋為開發語言，開發的SecBT平臺上進行的開發研究工作，以下簡稱自適應機制。

1.1 總體設計

自適應機制主要分為三大模塊（如圖1所示）：節點預處理模塊、節點選擇模塊和自適應更新與維護模塊。

圖1 自適應節點選擇機制框架

（1）節點預處理模塊主要是處理收到的來自于Tracker、DHT、PEX的節點列表信息，包括節點過濾和鄰近優先兩個子模塊。

節點過濾：在節點池1中查詢節點列表，過濾IP、Port異?；蛘咭呀⑦B接的節點。

鄰近優先：根據鄰近優先算法，計算出各個節點與本節點的距離，并且優先連接距離本節點較近的節點。將建立連接的節點存放到節點池2。

（2）節點選擇模塊是負責從已經建立連接的節點中選擇一部分節點與之進行數據交互，包括服務性節點選擇模塊、公平性節點選擇模塊、空閑帶寬節點選擇模塊。

服務性節點選擇：選擇周期為10s，每個選擇周期統計各節點為本節點提供的上傳數據量，在上一個選擇周期提供較多上傳的節點，就是為本節點提供較多服務的節點，此類節點會被選作為上傳對象（系統默認為4個節點）。

公平性節點選擇：選擇周期為30s，本節點從已建立連接的各節點中隨機的選擇一個節點為其提供上傳，這樣既保證了新加入網絡沒有任何數據的節點被選擇的機會，也有利于了本節點發現更好的節點資源（系統默認為1個節點）。

空閑帶寬節點選擇：選擇周期為10s，根據自適應更新階段系統分配的上傳連接數以及統計的空閑帶寬隊列，在本節點上傳帶寬利用率較低的情況下，選擇具有較大空閑帶寬的節點為其提供上傳。

（3）自適應更新與維護。統計本節點上傳帶寬利用率，分配系統上傳連接數，統計各節點空閑帶寬。

1.2 鄰近優先機制

為了選擇較近的節點進行連接，首先需要探測本節點與各節點之間的鄰近性，在P2P網絡中，可以通過RTT（round－trip－time）值和路由跳數值反映兩個節點的距離，但由于RTT值會根據當前網絡擁塞程度而頻繁的變化，在該機制中主要以路由跳數作為鄰近節點選擇標準。在搜索候選連接節點時采迭代加深搜索的思想：在迭代搜索中，每次迭代深度限制遞增。當查詢的節點數目滿足要求或者已經達到最大的深度限制，迭代過程結束。在迭代過程中，隨著深度的增加，節點個數迅速增長。因此，在最大深度限制的深度找到滿意的結果和直接以最大深度進行搜索比較起來，節約大量資源消耗。鄰近節點優先策略如圖2所示。

圖2 鄰近節點優先策略

策略實施過程如下：

（1）計算本節點與節點池1中各個節點的距離dis＝［hop＿count，RTT］。并按hop＿count由小到大存入臨時備選連接列表（當節點hop－count值相等時，對相同的節點按RTT值由小到大排序），初始化閾值threshold＝0。

（2）連接hop＿count在閾值范圍內的節點（threshold＝0，表示優先搜索同網段內的節點）。如果連接成功則將此節點存放入節點池2。

（3）無論連接成功或者失敗，刪除臨時備選連接列表中的此節點信息。

（4）系統擴大閾值threshold值，由近及遠進行連接。跳至過程（2）、（3）。

1.3 節點選擇機制

節點選擇機制是在節點自適應更新階段基于自身上傳帶寬利用率和對等節點的空閑帶寬的情況觸發的。當本節點帶寬利用率較低，并且當前連接對等節點有空閑的帶寬，那么系統分配上傳連接數用于提供上傳。

節點選擇機制有描述如下：在節點選擇階段中，N＿all為系統總的上傳連接數，由服務性選擇的節點數目為N＿service，由公平性節點選擇的節點數目為N＿fairness，由空閑帶寬節點選擇的節點數目為N＿free。

上傳連接數分配：N＿all＝N＿service＋N＿fairness＋N＿free，在自適應節點選擇機制中，系統默認N＿service＝4，N＿fairness＝1，N＿free＝0。系統總的上傳連接數N＿all由自適應更新階段自動分配。某時刻t時，可以定義上傳帶寬利用率utilization＿rate，上傳字節量為upload＿byte；用戶（系統分配上傳字節量/s）為upload＿limit則utilization＿rate＝upload＿byte/upload＿limit；

當utilization＿rate值偏小時說明本節點的上傳帶寬利用率較低。系統自增加上傳連接數N＿free，同時從統計的節點空閑帶寬列表中選擇節點為其提供上傳。在節點選擇更新方面，每10s更新一次，這樣能保證當自身帶寬利用率不高的情況下，每10s檢測一次帶寬利用率以及統計節點的空閑帶寬，并將自增的上傳連接數目用于上傳給擁有較大空閑帶寬的節點，達到充分利用帶寬的目的。

2 實驗與結果分析

2.1 鄰近性距離測量

為了驗證自適應節點選擇機制中鄰近優先模塊的有效性，本實驗對穩定連接階段的節點進行了測量分析。在P2P網絡中，兩個節點的距離可以通過往返時延RTT和路由跳數Hop－count來測量，RTT為兩節點網絡時延，Hopcount為兩節點路由跳數。利用基于tracert的方法可以獲得到達其他節點的網絡時延和路由跳數。發送端通過發送一個UDP包，tracert程序可以跟蹤發射包整個的路由過程和計算網絡時延。小數量的包可以產生一個較好的簡單的網絡預測，從而得到所需要到達節點的RTT和Hop－count。在Internet中，兩節點的路由跳數一般低于30。

圖3是從穩定連接階段所連接節點中選擇50個節點進行的測量分析，由圖統計的RTT和Hop－count值，分析可得隨著RTT值增加，Hop－count值也隨之增加，但是并不成線性關系?？梢缘贸鲈趥鹘y機制中由于對節點的連接都是隨機的選擇，所連接節點的RTT值主要分布于50ms—90ms、Hop－count值主要分布于13跳—27跳。在實施自適應機制中，RTT值主要分布于30ms—70ms，并且有一部分同網段的節點被發現的，路由跳數值主要分布于6跳—14跳。圖4為平均往返時間隨節點數目變化圖。通過對比試驗說明，自適應節點選擇機制下本節點優先選擇距離本節點較近的節點進行連接。

作為評價鄰近優先模塊的一個參考標準，平均網絡時延較小的節點被認為距離本節點較近，在傳統機制之中，對于節點連接存在著隨機性，而在改進之后由于會優先連接距離本節點較近的節點，所以平均網絡時延較小，但隨著連接范圍的擴大，逐漸會連接那些距離本節點較遠的節點，因此隨著節點規模的擴大，平均網絡時延逐漸變大。同樣的如圖5所示，鄰近優先機制中總是優先連接距離本節點較近的節點（同網段中若有節點，則優先連接同網段節點）。正如路由跳數反映的情況，距離本節點較近的節點擁有較小的路由跳數，但隨著連接范圍擴大，連接的節點距離越來越遠，路由跳數成上升趨勢。

圖5 平均路由跳數隨節點數目變化

2.2 上傳帶寬利用率

在以C＋＋實現的SecBT進行實驗中，下載文件大小為588MB的文件，經過多次實驗，傳統機制中平均下載完成總耗時2006.1秒。自適應機制中平均下載完成總耗1871.3s。如圖6所示，文件在整個下載過程上傳帶寬利用率曲線圖。

圖6 上傳寬利用率隨時間變化

傳統節點選擇機制中，上傳帶寬利用受網絡中節點的加入和退出或者是對等節點被阻塞而導致上傳帶寬使用情況波動較大，并且平均帶寬利用率僅為86.4%，文件平均完成總耗時2006.1s。

在自適應機制中，平均上傳帶寬利用率為93.7%，與傳統節點選擇機制相比提高了8.45%，完成文件下載平均總耗時為1871.3s，在下載總耗時方面較傳統機制縮短了6.7%，當文件越大改進的效果越明顯，這是因為由自適應機制選擇的節點會彌補節點因退出、被阻塞情況而出現減少服務對象，從而保證在上傳帶寬的正常合理使用，同時自適應機制根據網絡中節點的空閑下載帶寬大小，選擇節點提供服務，這樣在提高自身上傳帶寬利用的同時能充分的利用網絡中空閑的下載帶寬，從整體上提高網絡的下載性能以及文件分發的能力。

2.3 文件第一塊下載影響

對于新加入的網絡節點，由于自身沒有數據塊，不能為其他節點提供上傳。因此新加入節點往往需要等待一定的時間，直到自己被其他節點選擇作為上傳對象。因此對新加入節點第一個文件分片下載有很大影響，在自適應機制中由于新加入節點具有較大的上傳和下載帶寬，因此自適應機制大大增加了新節點被選中的概率，使新節點較快的擁有數據塊快速的進入穩定下載階段，縮短了新加入網絡的節點下載第一個文件分片的時間，也促進了整個系統的運行。第一塊平均下載完成時間隨機節點數目變化如圖7所示。

圖7 第一塊平均下載完成時間隨節點數目變化

2.4 BT系統文件分發效力

BT文件分發效力是衡量改進后節點選擇機制對整個系統性能提高情況的主要標準?？梢杂媚硶r間段內節點下載文件的完成度或者節點下載完成所需用時來評價。設t時刻網絡中需要下載某共享文件M的節點為N個，標記為N1，N2…Ni，需要分發的文件大小一共有m個數據分片，每一個節點在下載過程中擁有的數據分片標記為X1，X2…Xi。則t時刻節點Ni的M 文件下載完成度可以表示為

系統的文件分發效力E可由整個系統的關于M 文件完成度即為來表示，得

圖8對100個節點規模的下載情況進行了分析，分析其中t＝30mins時刻的情況，在下載進行30分鐘時，傳統機制中完成下載的節點數目是36個，由于36個節點已經擁有所有的分片即完成度D＝1，假設剩余的64個節點獲得的數據分片數目為1—m－1片，即完成度在0到100%隨機分布，則文件的分發效力，在自適應機制下，完成下載的節點數目為47個，文件分發效力，容易證明E2＞E1。

圖8 節點完成數目隨時間變化

圖9 不同節點規模下節點平均下載完成時間

由圖9可見，就下載完成時間而言，自適應機制較傳統節點選擇機制平均提高36.6%。平均縮短下載時間13.6分鐘。

實驗表明，自適應節點選擇機制的實施對于文件在系統的分發有較好的促進作用，其文件分發效力明顯優于傳統機制。

2.5 系統公平性

在自適應節點選擇機制中，由于系統在上傳帶寬利用率不高的情況下自增上傳連接數選擇并未向本節點提供上傳的節點作為自己的上傳對象，這對系統的公平性會產生一定影響。

對于公平性的評價，通過對該節點的分享率f所對應的隨機變量ξ的標準差σ（ξ）進行分析 ，在有n個下載節點的系統中節點i的上傳文件分片數，下載文件分片數，其分享率定義如下：同時有：σ（ξ）＝為系統的平均分享率。其中節點i作為單獨的離散點存在，則p（fi）＝1/n，在整個系統中有總的上傳分片書等于總的下載分片數，因此E（ξ）＝1，由此可得：代入統計數據可得傳統機制中σ（ξ）＝0.57113，自適應機制中σ（ξ）＝0.570752，由此可見，自適應機制對系統公平性有較小的影響。這是由于在自適應機制被觸發之后，在較短時間會恢復到穩定的 “4＋1”狀態，對系統中的公平性影響比較小。

3 結束語

本文以P2P的主流應用BitTorrent為協議背景，結合節點選擇的3個階段：節點獲取階段、節點選擇階段、節點維護階段的特點，考慮了除Tracker以外的DHT、PEX節點獲取情況以及網絡中各節點空閑帶寬情況，從減少跨網段帶寬資源浪費、提高節點帶寬資源利用率出發。設計并實現了基于帶寬利用的自適應節點選擇機制，通過與傳統節點選擇機制的對比實驗，驗證了自適應機制的有效性和優越性。對于減少網絡中不必要的流量浪費，使各節點帶寬利用率有較大的改善，從而在整體使得P2P交互性能得以提高。

［1］YANG Xiangying，Gustavo de Veciana.Service capacity of peer to peer networks［C］.INFOCOM Twenty－third AnnualJoint Conference of the IEEE Computer and Communications Societies，2004.

［2］TANG Hong，ZHANG Yunlong.Scheme of BitTorrent traffic control ［J］.Journal of Computer Applications，2011，31（2）：304－307（in Chinese）. ［唐紅，張云龍.Bittorrent流量控制方案 ［J］.計算機應用，2011，31（2）：304－307.］

［3］LIU Weidong.Enhancing tit－for－tat for incentive in BitTorrent networks ［J］.Peer－to－Peer Networks，2010，3（1）：27－35.

［4］CHEN Xingshu，LIN Dayun，WANG Wenxian.Research and implementation of intelligent selection mechanism in P2P ［J］.Journal of Computer Applications，2011，31（2）：293－297（in Chinese）.［陳興蜀，林大云，王文賢.P2P節點智能選擇機制的研究與實現 ［J］.計算機應用，2011，31（2）：293－297.］

［5］QiAO Zhiwei，XU Tingrong.Design and implementation of simulation platform for neighbor selection algorithm in BT system ［J］.Computer Engineering and Design，2010，31（12）：2914－2917（in Chinese）.［喬志偉，徐汀榮.BT鄰居結點算法驗證平臺的設計與實現 ［J］.計算機工程與設計，2010，31（12）：2914－2917.］

［6］Ruchir B，CAN P，William C.Improving traffic locality in Bit－Torrent via biased neighbor selection ［C］.Lisboa，Portugal：26th IEEE International Conference on Distributed Computing Systems，2006：66－76.

［7］David Erman，Daniel Saavedra.Validating.BitTorrent models［J］.Telecommunication Systems，2008；39（2）：103－116.

［8］Thanasis G，Papaioannou，George D，et al.A mechanism that provides incentives for truthful feedback in peer－to－peer systems ［J］.Electronic Commerce Research，2010，10（3）：331－337.

［9］YU Jiadi.Research on key technique of BitTorrent－like peer－topeer file sharing system ［D］.Shanghai：Shanghai Jiaotong U－niversity，2007：82－85（in Chinese）.［俞嘉地.BitTorrent對等網文件共享系統關鍵技術研究 ［D］.上海：上海交通大學，2007：82－85.］

［10］LI Jin.On peer－to－peer（P2P）content delivery ［J］.Peer－to－Peer Networking and Applications，2008，1（1）：45－63.

［11］CHEN Zhide，ZHENG Jinhua，XU Li.Network service incentive mechanism based on competitive game ［J］.Communica－tions in Computer and Information Science，2009，60（1）：46－53.

［12］QIU Dongyu，SANG Weiqian，MA Zuhui.On the efficiency of peer－to－peer file sharing ［J］.Journal of Signal Processing Systems，2010，59（3）：347－353.

［13］QIU D，Srikant S.Modeling and performance analysis of BitTorrent－like peer－to－peer networks ［C］.Barcelona，Spain：Proc of IEEE INFOCOM，2006：524－529.

［14］TIAN Y，WU D，NG K W.Modeling analysis and improvement for BitTorrent－like file sharing networks ［C］.Barcelona，Spain：Proc of IEEE INFOCOM，2006：641－647.

［15］CHAN Ho－Leung，LAM Tak－Wah，Prudence W H Wong.Efficiency of data distribution in BitTorrent－like systems ［J］.Computer Science，2007，45（2）：378－388.