P2P網(wǎng)絡中自適應節(jié)點選擇策略

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

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

0 引 言

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

針對以上問題，本文設計并實現(xiàn)P2P系統(tǒng)中自適應的節(jié)點選擇策略，該策略通過以鄰近節(jié)點優(yōu)先連接與基于上傳帶寬利用率的節(jié)點選擇算法相結(jié)合，以實現(xiàn)P2P網(wǎng)絡高效、自適應的節(jié)點選擇。

1 自適應節(jié)點選擇機制

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

1.1 總體設計

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

圖1 自適應節(jié)點選擇機制框架

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

節(jié)點過濾：在節(jié)點池1中查詢節(jié)點列表，過濾IP、Port異常或者已建立連接的節(jié)點。

鄰近優(yōu)先：根據(jù)鄰近優(yōu)先算法，計算出各個節(jié)點與本節(jié)點的距離，并且優(yōu)先連接距離本節(jié)點較近的節(jié)點。將建立連接的節(jié)點存放到節(jié)點池2。

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

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

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

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

（3）自適應更新與維護。統(tǒng)計本節(jié)點上傳帶寬利用率，分配系統(tǒng)上傳連接數(shù)，統(tǒng)計各節(jié)點空閑帶寬。

1.2 鄰近優(yōu)先機制

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

圖2 鄰近節(jié)點優(yōu)先策略

策略實施過程如下：

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

（2）連接hop＿count在閾值范圍內(nèi)的節(jié)點（threshold＝0，表示優(yōu)先搜索同網(wǎng)段內(nèi)的節(jié)點）。如果連接成功則將此節(jié)點存放入節(jié)點池2。

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

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

1.3 節(jié)點選擇機制

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

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

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

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

2 實驗與結(jié)果分析

2.1 鄰近性距離測量

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

圖3是從穩(wěn)定連接階段所連接節(jié)點中選擇50個節(jié)點進行的測量分析，由圖統(tǒng)計的RTT和Hop－count值，分析可得隨著RTT值增加，Hop－count值也隨之增加，但是并不成線性關系。可以得出在傳統(tǒng)機制中由于對節(jié)點的連接都是隨機的選擇，所連接節(jié)點的RTT值主要分布于50ms—90ms、Hop－count值主要分布于13跳—27跳。在實施自適應機制中，RTT值主要分布于30ms—70ms，并且有一部分同網(wǎng)段的節(jié)點被發(fā)現(xiàn)的，路由跳數(shù)值主要分布于6跳—14跳。圖4為平均往返時間隨節(jié)點數(shù)目變化圖。通過對比試驗說明，自適應節(jié)點選擇機制下本節(jié)點優(yōu)先選擇距離本節(jié)點較近的節(jié)點進行連接。

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

圖5 平均路由跳數(shù)隨節(jié)點數(shù)目變化

2.2 上傳帶寬利用率

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

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

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

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

2.3 文件第一塊下載影響

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

圖7 第一塊平均下載完成時間隨節(jié)點數(shù)目變化

2.4 BT系統(tǒng)文件分發(fā)效力

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

系統(tǒng)的文件分發(fā)效力E可由整個系統(tǒng)的關于M 文件完成度即為來表示，得

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

圖8 節(jié)點完成數(shù)目隨時間變化

圖9 不同節(jié)點規(guī)模下節(jié)點平均下載完成時間

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

實驗表明，自適應節(jié)點選擇機制的實施對于文件在系統(tǒng)的分發(fā)有較好的促進作用，其文件分發(fā)效力明顯優(yōu)于傳統(tǒng)機制。

2.5 系統(tǒng)公平性

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

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

3 結(jié)束語

本文以P2P的主流應用BitTorrent為協(xié)議背景，結(jié)合節(jié)點選擇的3個階段：節(jié)點獲取階段、節(jié)點選擇階段、節(jié)點維護階段的特點，考慮了除Tracker以外的DHT、PEX節(jié)點獲取情況以及網(wǎng)絡中各節(jié)點空閑帶寬情況，從減少跨網(wǎng)段帶寬資源浪費、提高節(jié)點帶寬資源利用率出發(fā)。設計并實現(xiàn)了基于帶寬利用的自適應節(jié)點選擇機制，通過與傳統(tǒng)節(jié)點選擇機制的對比實驗，驗證了自適應機制的有效性和優(yōu)越性。對于減少網(wǎng)絡中不必要的流量浪費，使各節(jié)點帶寬利用率有較大的改善，從而在整體使得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節(jié)點智能選擇機制的研究與實現(xiàn) ［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鄰居結(jié)點算法驗證平臺的設計與實現(xiàn) ［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對等網(wǎng)文件共享系統(tǒng)關鍵技術研究 ［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.