一種新型P2P應用層并行路徑選擇機制

劉 佳， 張 晨， 魏世民

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

0 引言

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

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

這里研究的目的是當網格業務網絡或P2P網絡在P2P層中使用并行路徑來實現文件傳輸業務時，僅依靠P2P層的技術來實現在多條可行的并行路徑間選擇恰當的并行路徑，切實提高業務的穩定性、可靠性和吞吐率。

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

1.1 定義

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

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

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

1.2 優化模型

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

在一個網格業務網絡或P2P網絡中存在由peer構成的多個源、目的節點對，每對源、目的節點之間存在有多條可行并行路徑。其中源、目的節點間在P2P層的直聯路徑，為必選路徑。這里的優化對象為在各源、目的節點間傳輸任務。對這些傳輸任務進行實時優化，也就是說僅對正在發生的傳輸任務或是即將發生的傳輸任務進行優化。這里的優化目標為每一對源、目的節點對選擇恰當的并行路徑，使得每一對源、目的節點對間的每一個傳輸任務的傳輸速率最大化；每一對源、目的節點對間的并行路徑間的相關性最小化。

在優化中，需要遵守如下約束條件：網絡任一節點流量守恒；任一路徑上的流量不小于0；任一路徑上是沒有閉環的。

1.3 路徑間相關性的測量機制

為了實現優化模型，需要對兩個子優化目標中的傳輸速率和路徑間的相關性進行監測。在這里，采用網絡測量中的被動測量方法對任一路徑上的任一業務的傳輸速率進行監測，進而可以得到業務的總的傳輸速率和并行路徑間的相關性[6-7]。

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

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

由目的節點發送相應的測試報告至源節點。

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

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

定義各時間點的加權后的有效測量值為：

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

計算相關性的公式：

對測量結果加權的目的在于考慮到網絡整體性能發生顯著變化的可能性，強化最后幾測量結果對于路徑相關性的影響。

測量公式2 由兩部分組成，前一次相關性的計算結果，這次的相關性的計算結果；這次相關性的計算結果，也是經過加權的相關性計算結果。

繼續測量公式1的假設，但是 k 1 =k 2 =…=kn=1。

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

如果使用此公式，建議n的取值應當比使用測量公式 1時的值小。

1.4 并行路徑間的選擇機制

規定任一對源、目的節點對間的P2P層的直連路徑是必選路徑，只要還有傳輸業務，該路徑就必須存在。根據優化目標和測量的結果，在源、目的節點對間選擇并行路徑的機制如下：

①在初始狀態下，當一對源、目的節點對間有新業務需要傳輸時，從可行的并行路徑集中，隨機選擇一到多條路徑（推薦選擇一條路徑）與直連路徑共同構成實際使用的并行路徑集；

②同時開始針對有業務傳輸的路徑的傳輸速率和路徑間的相關性的測量和統計；

③當達到相對穩定的狀態，對于已經正在傳輸的業務，要周期性的統計其使用的路徑間的相關性，作為經驗值不斷累計，一定時間以前的相關性數據可以被更新掉；

④對于新建的業務，根據積累的數據，選擇一條路徑，如果積累的數據，是在給定的時間內統計得到的，否則，隨機選擇一條；

⑤如果對于正在傳輸的業務的兩條路徑的相關性或是吞吐速率不滿意，則依照同樣的規則重新選擇路徑，但是把已選擇的路徑排除在外。

2 仿真分析

2.1 仿真步驟簡介

仿真采用的并行路徑傳輸機制簡稱PRTG, 采用部分副本技術，擁有完整數據的源服務器和轉發服務器（簡稱PRS）一起組成并行傳輸路徑將數據傳輸到目的服務器[5]。

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

仿真分兩步進行。①在隨機產生的任一拓撲下，同時發起多組業務。進行多次仿真傳輸。每次傳輸的同一大小的業務有相同的源和目的節點，但是不同的PRS，這樣多次以后可獲得不同路徑間的相關系數。從而獲得相關系數與業務傳輸周期之間的關系；②通過第一階段獲得的數據，采用路徑選擇機制選擇較好路徑進行傳輸，與隨機選擇路徑進行傳輸的PRTG進行對比分析。主要比較業務周期和鏈路利用率。

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

2.2 階段一

圖 1顯示采用不同相關性系數的并行路徑進行文件傳輸時，所用時間（即業務周期）對比。結果表明選擇相關系數小的并行路徑業務周期更短。

圖1 采用不同相關系數并行路徑的業務周期對比

2.3 階段二

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

圖2 業務周期對比

圖3 平均鏈路利用率對比

圖3中橫坐標軸時間需乘以50。結果表明在整個網絡內采用路徑選擇算法后，能夠增強網絡的業務容量,獲得更高的帶寬利用率和更短的業務周期。

3 結語

針對網格業務網絡或 P2P網絡中的并行路徑數據傳輸業務，提出了一種新的基于被動測量的 P2P并行路徑選擇算法與機制。該機制已經在中歐網格互聯（EC-GIN）項目中的PRTG中被實現并在有幾個自治系統的小的網絡中被驗證。仿真和真實結果都證明此算法和機制能夠對采用并行路徑的傳輸機制的性能進行優化。此機制主要是針對 P2P層并行路徑的選擇而設計的，但它也適用于解決開放式系統互聯(OSI)七層協議中其它層面協議所遇到的多路徑選擇問題。

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

[2] 聶榮，余建國，呂英華.國內對p2p網絡的相關研究[J].通信技術，2008,41（07）：130-132..

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

[4] 王偉，張利剛，呂彬.基于主動識別技術的網關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] 夏彪.端到端網絡瓶頸測量研究[D].武漢：武漢科技大學,2009.

[7] 姚遠程.網絡時延測量中的時間同步系統應用研究[J].通信技術,2008, 41(08)：149-153.

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