一種新型P2P應(yīng)用層并行路徑選擇機制

劉 佳， 張 晨， 魏世民

(①北京郵電大學(xué) 自動化學(xué)院，北京 100876; ②中國移動通信集團設(shè)計院有限公司研究所，北京 100080)

0 引言

文件和數(shù)據(jù)傳輸是網(wǎng)格業(yè)務(wù)網(wǎng)絡(luò)或 P2P網(wǎng)絡(luò)最主要的業(yè)務(wù)類型之一。對于數(shù)據(jù)量巨大的文件和數(shù)據(jù)傳輸業(yè)務(wù)，業(yè)務(wù)本身的穩(wěn)定性，吞吐量和可靠性變得非常重要。對于這兩種網(wǎng)絡(luò)，特別是跨自治域的時候，獲知 IP層或者是更低層的網(wǎng)絡(luò)拓撲是非常困難的，在這種情況下，可以選擇在P2P層建立多條并行路徑來實現(xiàn)并行路徑的傳輸，也就是由一組對等體（peer）來組成多條傳輸路徑，實現(xiàn)兩個peer之間的文件傳輸[1-4]。

但是P2P層的并行路徑可能在IP層或是更低的層面共享一到多條鏈路，以至于擁有相同的擁塞點，路徑性能的變化規(guī)律趨同，使得并行路徑難以實際達到提高文件傳輸性能的要求，還有可能加劇網(wǎng)絡(luò)性能的波動[5]。

這里研究的目的是當(dāng)網(wǎng)格業(yè)務(wù)網(wǎng)絡(luò)或P2P網(wǎng)絡(luò)在P2P層中使用并行路徑來實現(xiàn)文件傳輸業(yè)務(wù)時，僅依靠P2P層的技術(shù)來實現(xiàn)在多條可行的并行路徑間選擇恰當(dāng)?shù)牟⑿新窂?，切實提高業(yè)務(wù)的穩(wěn)定性、可靠性和吞吐率。

1 并行路徑選擇算法與機制

1.1 定義

路徑間的相關(guān)性：選定一個或一組影響傳輸路徑的參數(shù)作為測量值，經(jīng)過一段時間的觀測后，在時間上，計算不同并行路徑間的參數(shù)值的相關(guān)性為ρ，稱為路徑間的相關(guān)性。傳輸路徑參數(shù)即業(yè)務(wù)在路徑上的傳輸速率、抖動、延遲等參數(shù)。這里將以傳輸速率為例來說明相應(yīng)的算法和機制是如何設(shè)計的。

弱相關(guān)路徑：不同路徑間的相關(guān)性，如果低于某一個閾值T，則認為這些路徑彼此之間屬于弱相關(guān)路徑。

較優(yōu)路徑：假定路徑a、b、c有相同的源、目的點，且為a與b為弱相關(guān)路徑，相關(guān)系數(shù)值為ρab，a與c弱相關(guān)路徑，值為ρab，以下條件中的任一條被滿足時，則稱b相對于c是a的較優(yōu)路徑：，或者但

1.2 優(yōu)化模型

假設(shè)在路徑間相關(guān)性的計算中，所使用的參數(shù)僅為業(yè)務(wù)在路徑的傳輸速率。也可以使用其它可以反映路徑性能的參數(shù)，如抖動和延遲，所遵循的算法和機制是相同的。下面給出這里的優(yōu)化模型。

在一個網(wǎng)格業(yè)務(wù)網(wǎng)絡(luò)或P2P網(wǎng)絡(luò)中存在由peer構(gòu)成的多個源、目的節(jié)點對，每對源、目的節(jié)點之間存在有多條可行并行路徑。其中源、目的節(jié)點間在P2P層的直聯(lián)路徑，為必選路徑。這里的優(yōu)化對象為在各源、目的節(jié)點間傳輸任務(wù)。對這些傳輸任務(wù)進行實時優(yōu)化，也就是說僅對正在發(fā)生的傳輸任務(wù)或是即將發(fā)生的傳輸任務(wù)進行優(yōu)化。這里的優(yōu)化目標(biāo)為每一對源、目的節(jié)點對選擇恰當(dāng)?shù)牟⑿新窂剑沟妹恳粚υ?、目的?jié)點對間的每一個傳輸任務(wù)的傳輸速率最大化；每一對源、目的節(jié)點對間的并行路徑間的相關(guān)性最小化。

在優(yōu)化中，需要遵守如下約束條件：網(wǎng)絡(luò)任一節(jié)點流量守恒；任一路徑上的流量不小于0；任一路徑上是沒有閉環(huán)的。

1.3 路徑間相關(guān)性的測量機制

為了實現(xiàn)優(yōu)化模型，需要對兩個子優(yōu)化目標(biāo)中的傳輸速率和路徑間的相關(guān)性進行監(jiān)測。在這里，采用網(wǎng)絡(luò)測量中的被動測量方法對任一路徑上的任一業(yè)務(wù)的傳輸速率進行監(jiān)測，進而可以得到業(yè)務(wù)的總的傳輸速率和并行路徑間的相關(guān)性[6-7]。

下面為屬于同一源、目的之間任兩條并行路徑間相關(guān)性的測試量機制：

在目的節(jié)點根據(jù)單位時間內(nèi)接收到的來自源節(jié)點的有效包的大小，測算不同路徑的吞吐率，每x秒測量一次，經(jīng)過周期t后，計算來同一源節(jié)點的任兩條路徑間的相關(guān)性各一次。

由目的節(jié)點發(fā)送相應(yīng)的測試報告至源節(jié)點。

在路徑間的相關(guān)性的計算公式，有如下兩種可供選擇：

測量公式 1 設(shè)兩條路徑p和o的任一時刻的吞吐率分別為隨機變量 tp和 to，則在每一個測量周期內(nèi)有n次測量值分別為 tp 1 , t p 2 ,… ,tpn 和to1 ,to 2 ,…,ton,其中1代表最早測量時間點，n代表最晚的時間測試量點。

定義各時間點的加權(quán)后的有效測量值為：

則兩條路徑間在第T周期的協(xié)方差為：

計算相關(guān)性的公式：

對測量結(jié)果加權(quán)的目的在于考慮到網(wǎng)絡(luò)整體性能發(fā)生顯著變化的可能性，強化最后幾測量結(jié)果對于路徑相關(guān)性的影響。

測量公式2 由兩部分組成，前一次相關(guān)性的計算結(jié)果，這次的相關(guān)性的計算結(jié)果；這次相關(guān)性的計算結(jié)果，也是經(jīng)過加權(quán)的相關(guān)性計算結(jié)果。

繼續(xù)測量公式1的假設(shè)，但是 k 1 =k 2 =…=kn=1。

令兩條路徑間在第T周期的相關(guān)性為ρpoT，在第T-1周期的相關(guān)性為 ρ p o( T -1)，則記兩條路徑在第T周期的實際相關(guān)性為具體的參數(shù)是可以再調(diào)整的。

如果使用此公式，建議n的取值應(yīng)當(dāng)比使用測量公式 1時的值小。

1.4 并行路徑間的選擇機制

規(guī)定任一對源、目的節(jié)點對間的P2P層的直連路徑是必選路徑，只要還有傳輸業(yè)務(wù)，該路徑就必須存在。根據(jù)優(yōu)化目標(biāo)和測量的結(jié)果，在源、目的節(jié)點對間選擇并行路徑的機制如下：

①在初始狀態(tài)下，當(dāng)一對源、目的節(jié)點對間有新業(yè)務(wù)需要傳輸時，從可行的并行路徑集中，隨機選擇一到多條路徑（推薦選擇一條路徑）與直連路徑共同構(gòu)成實際使用的并行路徑集；

②同時開始針對有業(yè)務(wù)傳輸?shù)穆窂降膫鬏斔俾屎吐窂介g的相關(guān)性的測量和統(tǒng)計；

③當(dāng)達到相對穩(wěn)定的狀態(tài)，對于已經(jīng)正在傳輸?shù)臉I(yè)務(wù)，要周期性的統(tǒng)計其使用的路徑間的相關(guān)性，作為經(jīng)驗值不斷累計，一定時間以前的相關(guān)性數(shù)據(jù)可以被更新掉；

④對于新建的業(yè)務(wù)，根據(jù)積累的數(shù)據(jù)，選擇一條路徑，如果積累的數(shù)據(jù)，是在給定的時間內(nèi)統(tǒng)計得到的，否則，隨機選擇一條；

⑤如果對于正在傳輸?shù)臉I(yè)務(wù)的兩條路徑的相關(guān)性或是吞吐速率不滿意，則依照同樣的規(guī)則重新選擇路徑，但是把已選擇的路徑排除在外。

2 仿真分析

2.1 仿真步驟簡介

仿真采用的并行路徑傳輸機制簡稱PRTG, 采用部分副本技術(shù)，擁有完整數(shù)據(jù)的源服務(wù)器和轉(zhuǎn)發(fā)服務(wù)器（簡稱PRS）一起組成并行傳輸路徑將數(shù)據(jù)傳輸?shù)侥康姆?wù)器[5]。

仿真工具采用網(wǎng)絡(luò)模擬器NS-2[8]，對采用路徑選擇機制后的PRTG和未采用路徑選擇機制的PRTG進行對比分析。

仿真分兩步進行。①在隨機產(chǎn)生的任一拓撲下，同時發(fā)起多組業(yè)務(wù)。進行多次仿真?zhèn)鬏敗Ｃ看蝹鬏數(shù)耐淮笮〉臉I(yè)務(wù)有相同的源和目的節(jié)點，但是不同的PRS，這樣多次以后可獲得不同路徑間的相關(guān)系數(shù)。從而獲得相關(guān)系數(shù)與業(yè)務(wù)傳輸周期之間的關(guān)系；②通過第一階段獲得的數(shù)據(jù)，采用路徑選擇機制選擇較好路徑進行傳輸，與隨機選擇路徑進行傳輸?shù)腜RTG進行對比分析。主要比較業(yè)務(wù)周期和鏈路利用率。

圖1、圖2、圖3都是在相同拓撲結(jié)構(gòu)下的仿真結(jié)果。這種拓撲結(jié)構(gòu)有18個節(jié)點（6個路由器和12個peer）和28條鏈路（10 kb/s 到 40 kb/s之間）。

2.2 階段一

圖 1顯示采用不同相關(guān)性系數(shù)的并行路徑進行文件傳輸時，所用時間（即業(yè)務(wù)周期）對比。結(jié)果表明選擇相關(guān)系數(shù)小的并行路徑業(yè)務(wù)周期更短。

圖1 采用不同相關(guān)系數(shù)并行路徑的業(yè)務(wù)周期對比

2.3 階段二

圖2和圖3分別顯示PRTG在采用新的路徑選擇算法前與采用新的路徑選擇算法后的業(yè)務(wù)周期和平均鏈路利用率對比。

圖2 業(yè)務(wù)周期對比

圖3 平均鏈路利用率對比

圖3中橫坐標(biāo)軸時間需乘以50。結(jié)果表明在整個網(wǎng)絡(luò)內(nèi)采用路徑選擇算法后，能夠增強網(wǎng)絡(luò)的業(yè)務(wù)容量,獲得更高的帶寬利用率和更短的業(yè)務(wù)周期。

3 結(jié)語

針對網(wǎng)格業(yè)務(wù)網(wǎng)絡(luò)或 P2P網(wǎng)絡(luò)中的并行路徑數(shù)據(jù)傳輸業(yè)務(wù)，提出了一種新的基于被動測量的 P2P并行路徑選擇算法與機制。該機制已經(jīng)在中歐網(wǎng)格互聯(lián)（EC-GIN）項目中的PRTG中被實現(xiàn)并在有幾個自治系統(tǒng)的小的網(wǎng)絡(luò)中被驗證。仿真和真實結(jié)果都證明此算法和機制能夠?qū)Σ捎貌⑿新窂降膫鬏敊C制的性能進行優(yōu)化。此機制主要是針對 P2P層并行路徑的選擇而設(shè)計的，但它也適用于解決開放式系統(tǒng)互聯(lián)(OSI)七層協(xié)議中其它層面協(xié)議所遇到的多路徑選擇問題。

[1] LI M.The Grid： Core Technologies[M]. Wiltshire：Antony Bowe Ltd.2005：1-77.

[2] 聶榮，余建國，呂英華.國內(nèi)對p2p網(wǎng)絡(luò)的相關(guān)研究[J].通信技術(shù)，2008,41（07）：130-132..

[3] 韓桂華，李法冰. 網(wǎng)格計算安全性研究[J].信息安全與通信保密，2007(03)：116-117.

[4] 王偉，張利剛，呂彬.基于主動識別技術(shù)的網(wǎng)關(guān)p2p流量檢測[J].信息安全與通信保密,2009(12)：91-92.

[5] ZHANG CHEN, GAO PENG, LIU TAO, et al. A Novel Bulk Data Transfer Mechanism on Partial Replica[C]. Beijing： Institute of Electrical and Electronics Engineers, 2009：766-770.

[6] 夏彪.端到端網(wǎng)絡(luò)瓶頸測量研究[D].武漢：武漢科技大學(xué),2009.

[7] 姚遠程.網(wǎng)絡(luò)時延測量中的時間同步系統(tǒng)應(yīng)用研究[J].通信技術(shù),2008, 41(08)：149-153.

[8] 包斌，詹自熬.ns2深度探索及在網(wǎng)絡(luò)傳輸性能分析中的作用[J].通信技術(shù),2009,42(05)：155-160.