P2PCenter節(jié)點選擇機制的分析及改進

莊 雷，郭永平，孔 燕，孫一瀟

(鄭州大學信息工程學院，河南鄭州450001)

0 引言

隨著寬帶互聯(lián)網(wǎng)的迅速發(fā)展，P2P流媒體技術逐漸成為流媒體應用領域的研究熱點，節(jié)點選擇更是P2P流媒體系統(tǒng)中的一項關鍵技術，在節(jié)點選擇方面筆者已做過相關研究［1-2］.為了深入研究P2P流媒體技術，筆者選取國內(nèi)的一個P2P流媒體開源項目——P2PCenter為研究對象.P2PCenter在節(jié)點選擇方面運用簡單的隨機選擇策略，協(xié)議簡單且健壯性好，但卻容易造成拓撲失配問題，并且不能保證系統(tǒng)的服務質(zhì)量.筆者在對P2PCenter流媒體系統(tǒng)分析研究的基礎上，針對該系統(tǒng)在節(jié)點選擇機制上的不足進行改進，提出了基于IP地址庫及節(jié)點能力的節(jié)點選擇機制.該機制在保證系統(tǒng)健壯性的基礎上，較好地解決了拓撲失配問題，并且能為用戶提供更好的服務質(zhì)量.

1 節(jié)點選擇機制與分析

在P2P流媒體系統(tǒng)中，請求節(jié)點獲取資源的過程大致分為三步：資源搜索定位、節(jié)點選擇與資源獲取.筆者的主要工作在第二步.

當前P2P流媒體系統(tǒng)的節(jié)點選擇機制主要有以下3種.

(1)簡單的隨機選擇策略［3］：該方法對候選的源節(jié)點進行隨機選擇，其特點是協(xié)議簡單，能夠保持系統(tǒng)的網(wǎng)絡負載均衡性和健壯性.

(2)針對節(jié)點能力的節(jié)點選擇策略［4］：該方法主要為提高流媒體軟件的服務質(zhì)量，在節(jié)點能力方面用到的主要參數(shù)有帶寬、延遲、丟包率等.

(3)基于位置信息的節(jié)點選擇策略［5］：該方法主要用于解決P2P網(wǎng)絡中的拓撲失配問題.北京大學的Maze系統(tǒng)［6］在節(jié)點選擇方面就采用該方法.

以上3種節(jié)點選擇方法的缺點是針對系統(tǒng)某一方面的優(yōu)化，不能達到整體優(yōu)化.因此，筆者通過對P2PCenter在節(jié)點選擇方面的研究，并綜合已有節(jié)點選擇機制提出一種改進的節(jié)點選擇機制.

2 改進的節(jié)點選擇機制與分析

在改進的節(jié)點選擇機制中，綜合運用基于位置信息的節(jié)點選擇策略和針對節(jié)點能力的節(jié)點選擇策略兩種方法，在服務器端主要采用類似Maze系統(tǒng)的基于IP地址庫的節(jié)點選擇機制，并作適當?shù)母倪M，在請求節(jié)點端采用針對節(jié)點能力的節(jié)點選擇機制.

2.1 服務器端節(jié)點選擇機制的實現(xiàn)

服務器端采用基于IP地址庫的節(jié)點選擇策略，目標是對候選節(jié)點進行選擇篩選后，將節(jié)點返回給請求節(jié)點端，在返回節(jié)點的數(shù)目上根據(jù)文獻［7］返回20個以滿足請求節(jié)點端的需求.

IP地址庫包含了IP地址段及與之對應的地域信息和運營商信息，地域信息可以用來估算網(wǎng)絡距離，而運營商信息本身就是一種網(wǎng)絡拓撲信息.從IP地址段的地域信息選出底層網(wǎng)絡臨近的節(jié)點作為鄰居，而且盡量選擇在同一運營商網(wǎng)絡內(nèi)的節(jié)點作為請求節(jié)點的鄰居節(jié)點，以方便為用戶提供更高的QOS保證.服務器端改進的節(jié)點選擇機制如下：

(1)請求節(jié)目的客戶端向服務器發(fā)送請求包，其中包含所請求節(jié)目的ID以及客戶端IP;

(2)服務器接到請求包并對該包解析，從中提取節(jié)目ID和客戶端IP;

(3)查詢存放在服務器上的IP地址庫(格式如表1)，確定該客戶端所屬的網(wǎng)絡運營商和所處地域信息，將該客戶端連同網(wǎng)絡運營商和所處地域信息放入所請求節(jié)目的源節(jié)點列表當中.IPStart和IPEnd表單中的數(shù)據(jù)分別代表經(jīng)過編碼轉換的一個IP段的起止IP.IPIsp表單中的數(shù)據(jù)代表IP段所屬的網(wǎng)絡運營商編碼，如1代表電信，2代表網(wǎng)通.IPAddress是IP段所在省市編碼，例如：福建省廈門市用(52;0851)來表示，上海市用21來表示等.

表1 IP地址庫中部分IP段Tab.1 IP database

(4)計算該請求客戶端與候選節(jié)點列表中所有節(jié)點之間的舒適度，把舒適度較小的節(jié)點作為更合適的節(jié)點.候選節(jié)點列表中的節(jié)點B與請求節(jié)點A之間的舒適度C(A，B)計算公式如式(1)：

式中：Cn(A，B)表示兩個節(jié)點之間網(wǎng)絡類型的舒適度，A，B處在同一網(wǎng)絡取0，否則取1;Cp(A，B)表示兩個節(jié)點之間省/州的舒適度，A，B處在同一省/自治區(qū)/直轄市取0，否則取1;Cc(A，B)表示兩個節(jié)點之間城市的舒適度，A，B處在同一城市取0，否則取1.Cn(A，B)也可根據(jù)特殊網(wǎng)絡運營商情況而定，比如中國聯(lián)通的網(wǎng)絡與教育網(wǎng)之間的接口帶寬，比中國電信與教育網(wǎng)之間的大，這種情況下，規(guī)定教育網(wǎng)與聯(lián)通網(wǎng)之間的網(wǎng)絡類型距離為 0.8.wn、wp、wc、wpr分別表示 Cn(A，B)、Cp(A，B)、Cc(A，B)、Cpr(A，B)在求取 C(A，B)時所占的比例，四者相加等于1.在中國，由于不同網(wǎng)絡運營商之間的網(wǎng)絡帶寬都較窄，相較于地理位置，相同的網(wǎng)絡運營商之間的節(jié)點更容易實現(xiàn)良好的網(wǎng)絡連接，在改進的機制中規(guī)定 wn=55%，wp=20%，wc=10%，wpr=15% .

與Maze系統(tǒng)中的公式比較，本公式主要添加了省間距離Cpr(A，B)，表2是部分省/自治區(qū)的省間距離的取值.表中取值主要參考兩省/自治區(qū)之間的實際的物理距離和網(wǎng)絡運營商.

表2 部分省/自治區(qū)的省間距離CprTab.2 Cprof converted distance between provinces

具體取值時，同省之間的省間距離值為0.不同省之間取值時分兩步：第一步，用兩省之間所隔的省數(shù)乘以0.1得到第一步結果;第二步，若兩省間網(wǎng)絡運營商相同，則直接以第一步結果作為省間距離值，若不同則在第一步結果的基礎上再加上0.1作為最終的省間距離值.

添加Cpr(A，B)能夠進一步的減少覆蓋網(wǎng)的壓力，選擇臨近節(jié)點.比如當前觀看節(jié)目的分別有3 個節(jié)點是：A(河南，聯(lián)通)、B(黑龍江，聯(lián)通)、C(河北，聯(lián)通).其中節(jié)點A作為請求節(jié)點，如果不添加 Cpr(A，B)，通過計算得知 C(A，B)=C(A，C)，即節(jié)點B和C對于節(jié)點A來說舒適度相等，而實際上，節(jié)點C在物理位置上要更加接近節(jié)點A.添加 Cpr(A，B)后可以計算得知 C(A，B)＜C(A，C)，從而選擇節(jié)點C作為節(jié)點A的鄰居節(jié)點進行流媒體數(shù)據(jù)傳輸.

(5)將計算所得的舒適度用快速排序法作升序排序，然后選取舒適度較小的前20個節(jié)點作為候選節(jié)點發(fā)給請求節(jié)點，如果當前觀看該節(jié)目的節(jié)點不夠20個，在排序后就全部返還給請求節(jié)點.

2.2 請求節(jié)點端節(jié)點選擇機制的實現(xiàn)

請求節(jié)點端接收經(jīng)過服務器篩選后的節(jié)點，在請求節(jié)點端主要通過比較節(jié)點能力來進一步對這些節(jié)點進行優(yōu)化選擇，最終挑選出一組最優(yōu)的服務節(jié)點.在節(jié)點能力方面主要參考節(jié)點可用帶寬B(即當前候選節(jié)點可上傳的速率)、候選節(jié)點在數(shù)據(jù)傳輸中的丟包率L以及候選節(jié)點與請求節(jié)點間的網(wǎng)絡延遲T.為了綜合運用這3個度量，定義候選節(jié)點j對請求節(jié)點i的優(yōu)良度Hi(j)為：

此外，為了盡量避免單點失效問題以及盡量保證最大的網(wǎng)絡傳輸率，系統(tǒng)采取并行傳輸策略，從備選的20個節(jié)點中選出m個節(jié)點使其優(yōu)良度之和最大.假定流媒體播放速率為v0，m的選取可由公式(3)來確定，從而保證流媒體的播放流暢性.

3 可行性分析

在理論方面，由于對P2PCenter系統(tǒng)在節(jié)點選擇上的一個改進，且節(jié)點選擇在該系統(tǒng)中是一個獨立的代碼模塊，因此筆者所提出的改進的節(jié)點選擇機制完全可以在源代碼基礎上添加新的代碼來實現(xiàn).

在具體實現(xiàn)方面，該算法在服務器端主要需要計算出請求節(jié)點與源節(jié)點之間的舒適度并進行快速排序.時間復雜度方面，假設源節(jié)點列表中節(jié)點個數(shù)為n，運用快速排序該算法的時間復雜度為o(nlog2n)，因此該機制的時間復雜度相對較小.在空間復雜度方面，只需添加節(jié)點的運營商信息和地域信息，對系統(tǒng)原來的空間復雜度影響很小.在請求節(jié)點端，求出可用帶寬B、丟包率L及延遲T以得到節(jié)點優(yōu)良度，因此該算法在請求節(jié)點端也是可行的.

4 結論

通過研究P2PCenter源代碼，針對該流媒體系統(tǒng)在節(jié)點選擇方面的不足提出了基于IP地址庫和節(jié)點能力的雙重節(jié)點選擇機制.該機制的實現(xiàn)主要分兩步：首先，在服務器端，根據(jù)請求節(jié)點的IP查詢IP地址庫，確定該節(jié)點的物理信息，然后根據(jù)該物理信息求出節(jié)點舒適度，利用該舒適度從候選節(jié)點中選出一組在物理距離上與請求節(jié)點臨近的節(jié)點.其次，在請求節(jié)點端，利用候選節(jié)點與請求節(jié)點間的優(yōu)良度進行進一步篩選得出最終所需要的服務節(jié)點.

該節(jié)點選擇機制從整體上解決了該系統(tǒng)在網(wǎng)絡拓撲中的失配問題，可極大的降低系統(tǒng)網(wǎng)絡延遲，保證了系統(tǒng)的健壯性.從服務質(zhì)量上，減少了請求節(jié)點端與服務節(jié)點端的網(wǎng)絡時延，使得請求節(jié)點端能夠更快的得到想要的數(shù)據(jù)，同時由于考慮到了服務節(jié)點的服務能力，選擇出一組節(jié)點能力強的節(jié)點，可以讓用戶得到更為穩(wěn)定的服務.

［1］莊雷，陳鴻昶，黃建華，等.基于超級點劃分區(qū)域的對等網(wǎng)絡模型［J］.計算機應用與軟件，2005，3(9)：10-11.

［2］侯得果，莊雷.基于隨機性和文件塊相似性的結點選擇策略［J］.計算機工程與設計，2010，59(6)：1376-1378.

［3］鄭潔，張松，齊潔，等.P2P流媒體節(jié)點選擇機制的研究與仿真［J］.計算機工程與設計，2007，28(22)：5396-5399.

［4］MOHAMED H，AHSAN H，BOYAN B.PROMISS：peer-to-peer media streaming using Collectcast［C］∥Proceedings of MM Berkeley，California，USA，2003：45-54.

［5］XIAO Li，LIU Yun-hao.Improving unstructurdpeerto-peer systems by adaptive connection establishment［J］.IEEE Trans on Computers，2005，54(9)：1091-1103.

［6］楊志超.Maze中基于位置感知的鄰居網(wǎng)絡構造算法和P2P鄰居搜索［D］.北京大學信息科學技術學院，2004.

［7］MOHAMED H，AHSAN H，XU Dong-yan.Collectcast：a peer-to-peer serveice for mediastreaming ［J］.Mutimedia Systems，2005，11(1)：68-81.