劉 佳， 張 晨， 魏世民

(①北京郵電大學(xué) 自動(dòng)化學(xué)院，北京 100876; ②中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司研究所，北京 100080)

0 引言

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

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

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

1 并行路徑選擇算法與機(jī)制

1.1 定義

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

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

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

1.2 優(yōu)化模型

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

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

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

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

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

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

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

由目的節(jié)點(diǎn)發(fā)送相應(yīng)的測(cè)試報(bào)告至源節(jié)點(diǎn)。

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

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

定義各時(shí)間點(diǎn)的加權(quán)后的有效測(cè)量值為：

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

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

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

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

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

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

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

1.4 并行路徑間的選擇機(jī)制

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

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

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

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

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

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

2 仿真分析

2.1 仿真步驟簡(jiǎn)介

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

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

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

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

2.2 階段一

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

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

2.3 階段二

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

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

圖3 平均鏈路利用率對(duì)比

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

3 結(jié)語

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

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

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

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

[4] 王偉，張利剛，呂彬.基于主動(dòng)識(shí)別技術(shù)的網(wǎng)關(guān)p2p流量檢測(cè)[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ò)瓶頸測(cè)量研究[D].武漢：武漢科技大學(xué),2009.

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

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