基于可重構(gòu)測(cè)量模型的網(wǎng)絡(luò)測(cè)量任務(wù)部署算法

王 晶 汪斌強(qiáng) 張校輝

1 引言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展以及網(wǎng)絡(luò)應(yīng)用的空前膨脹，網(wǎng)絡(luò)規(guī)模、網(wǎng)絡(luò)鏈路速率以及各種新興網(wǎng)絡(luò)應(yīng)用都對(duì)網(wǎng)絡(luò)測(cè)量提出了新需求和新挑戰(zhàn)[1]。網(wǎng)絡(luò)測(cè)量不僅需要滿足更加多樣化的測(cè)量需求，提供更加準(zhǔn)確、實(shí)時(shí)的測(cè)量結(jié)果，還需要支持并發(fā)測(cè)量任務(wù)的動(dòng)態(tài)加載。網(wǎng)絡(luò)測(cè)量資源與多測(cè)量需求之間的矛盾日趨凸顯。

針對(duì)測(cè)量資源與測(cè)量需求之間的矛盾，現(xiàn)有主流的研究方法可分為兩類。一類從測(cè)量體系結(jié)構(gòu)著手，設(shè)計(jì)新型測(cè)量模型和算法，從根本上提高網(wǎng)絡(luò)測(cè)量技術(shù)的靈活性和可擴(kuò)展性。此類研究的代表成果包括美國(guó)加利福尼亞大學(xué)Yuan等人[2]提出的可編程測(cè)量，文獻(xiàn)[3, 4]提出的軟件定義網(wǎng)絡(luò)測(cè)量（Software Defined Measurement, SDM）、東南大學(xué)研制的虛擬化網(wǎng)絡(luò)測(cè)量平臺(tái)[5]以及中科院的研究團(tuán)隊(duì)提出的云服務(wù)網(wǎng)絡(luò)測(cè)量與分析架構(gòu)[6]等。另外一類研究更加關(guān)注測(cè)量任務(wù)部署、網(wǎng)絡(luò)測(cè)量資源分配與測(cè)量準(zhǔn)確性之間的關(guān)系[712]-，從測(cè)量任務(wù)和資源部署及調(diào)度算法著手解決上述問題，認(rèn)為提高網(wǎng)絡(luò)測(cè)量資源的利用率是解決該問題的根本途徑。其中Qin等人[12]提出了一種基于無向圖著色的測(cè)量任務(wù)調(diào)度算法 GCTS，分析由于測(cè)量資源爭(zhēng)用而導(dǎo)致的任務(wù)沖突問題，并給出解決方案。美國(guó)南加州大學(xué)的研究團(tuán)隊(duì)在文獻(xiàn)[3, 4]中分析討論了在SDM中測(cè)量資源與測(cè)量準(zhǔn)確性之間的關(guān)系，明確指出測(cè)量資源的分配和調(diào)度是 SDM 的重要研究?jī)?nèi)容，并且針對(duì)測(cè)量任務(wù)之間的 TCAM 資源分配問題給出一種啟發(fā)式的算法。

為了解決在有限測(cè)量資源上承載多樣化測(cè)量任務(wù)的問題，可重構(gòu)的網(wǎng)絡(luò)測(cè)量模型NMRM[13]（Network Measurement Reconfiguration Model）通過分層方法，將測(cè)量資源與測(cè)量需求分離，實(shí)現(xiàn)靈活、可擴(kuò)展的網(wǎng)絡(luò)測(cè)量功能。NMRM中的適配層依據(jù)測(cè)量任務(wù)和網(wǎng)絡(luò)測(cè)量資源狀況，為測(cè)量需求計(jì)算出最合適的任務(wù)部署方案。如何調(diào)度網(wǎng)絡(luò)測(cè)量資源，為測(cè)量任務(wù)分配合理的測(cè)量構(gòu)件，在不同任務(wù)之間復(fù)用測(cè)量構(gòu)件，會(huì)直接影響 NMRM 中的資源利用率以及對(duì)于多樣化并行測(cè)量任務(wù)支持的能力，因此測(cè)量任務(wù)部署問題是NMRM中的重要研究?jī)?nèi)容。

本文基于NMRM提出一種測(cè)量任務(wù)部署算法。首先對(duì)可重構(gòu)測(cè)量模型中的任務(wù)部署問題進(jìn)行抽象描述，并將問題轉(zhuǎn)換為網(wǎng)絡(luò)節(jié)點(diǎn)映射問題；然后給出問題的優(yōu)化求解方法；最后通過實(shí)驗(yàn)仿真對(duì)算法進(jìn)行分析驗(yàn)證。實(shí)驗(yàn)結(jié)果表明在任務(wù)部署成功率和任務(wù)平均等待時(shí)間這兩個(gè)性能上，本文算法都比傳統(tǒng)的GCTS算法有更好的表現(xiàn)，并且當(dāng)任務(wù)沖突率和任務(wù)規(guī)模數(shù)量增加時(shí)，算法的部署成功率都能保證在90%以上。

本文第2節(jié)對(duì)可重構(gòu)網(wǎng)絡(luò)測(cè)量中的測(cè)量任務(wù)部署問題進(jìn)行數(shù)學(xué)建模及轉(zhuǎn)換；第3節(jié)給出詳細(xì)的任務(wù)部署算法；第4節(jié)進(jìn)行算法性能分析與仿真實(shí)驗(yàn)；第5節(jié)進(jìn)行總結(jié)。

2 問題描述

2.1 測(cè)量任務(wù)部署模型

基于可重構(gòu)測(cè)量模型的網(wǎng)絡(luò)測(cè)量任務(wù)部署模型包括測(cè)量網(wǎng)絡(luò)、測(cè)量構(gòu)件和測(cè)量任務(wù)這3個(gè)重要元素，首先對(duì)它們進(jìn)行描述。

（1）測(cè)量網(wǎng)絡(luò) 測(cè)量網(wǎng)絡(luò)是指由包含測(cè)量資源的測(cè)量節(jié)點(diǎn)及節(jié)點(diǎn)間的鏈路組成的底層物理網(wǎng)絡(luò)，用無向圖 GM=（NM, EM）表示， NM是測(cè)量節(jié)點(diǎn)集合， EM是邊鏈路集合。在可重構(gòu)的測(cè)量網(wǎng)絡(luò)中，測(cè)量網(wǎng)絡(luò)等價(jià)于實(shí)際的網(wǎng)絡(luò)。NM中第i個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)ni上已配置的測(cè)量構(gòu)件用集合 Ci表示，總計(jì)算資源和總存儲(chǔ)資源分別用和示；節(jié)點(diǎn)u, v間的邊鏈路 eu,v上的總傳輸帶寬資源用表示。

（2）測(cè)量構(gòu)件 測(cè)量構(gòu)件是組合構(gòu)成測(cè)量算法的基本單元[13]，通過構(gòu)件間的組合，能夠動(dòng)態(tài)靈活地實(shí)現(xiàn)各種測(cè)量功能，從而支持各類測(cè)量任務(wù)。測(cè)量構(gòu)件消耗的資源可用資源消耗函數(shù)來刻畫，本文中僅考慮測(cè)量構(gòu)件的計(jì)算資源、存儲(chǔ)資源和帶寬資源消耗。計(jì)算資源消耗函數(shù)cj）和存儲(chǔ)資源消耗函數(shù)（i, cj），分別用于計(jì)算測(cè)量網(wǎng)絡(luò)節(jié)點(diǎn) ni中測(cè)量構(gòu)件 cj所消耗的計(jì)算資源和存儲(chǔ)資源。帶寬資源消耗函數(shù)（i, ck, j, cl）用于計(jì)算節(jié)點(diǎn) ni中測(cè)量構(gòu)件 ck和節(jié)點(diǎn) nj中測(cè)量構(gòu)件 cl通信所消耗的鏈路帶寬資源。不同構(gòu)件的資源消耗函數(shù)不盡相同。節(jié)點(diǎn)剩余的計(jì)算資源、存儲(chǔ)資源分別用和表示，節(jié)點(diǎn)間鏈路剩余的帶寬資源用表示，計(jì)算公式分別

其中k表示節(jié)點(diǎn) ni上配置的測(cè)量構(gòu)件總數(shù)，costc）為節(jié)點(diǎn)上用于其它功能的計(jì)算資源開銷，costm（）為節(jié)點(diǎn)上用于其它功能的存儲(chǔ)資源開銷；n, m分別表示節(jié)點(diǎn) nu和 nv上配置的測(cè)量構(gòu)件總數(shù)量， c ostb（e ）為鏈路上的其它帶寬資源開銷。

u, v（3）測(cè)量任務(wù)測(cè)量任務(wù)是對(duì)測(cè)量對(duì)象、測(cè)量?jī)?nèi)容等要求的綜合描述。測(cè)量對(duì)象拓?fù)?GT是測(cè)量網(wǎng)絡(luò)GM的子圖，用 GT=（NT, ET） 表示，且 NT?NM,ET?EM。測(cè)量?jī)?nèi)容包括網(wǎng)絡(luò)流量特征、帶寬、傳輸時(shí)延、拓?fù)浣Y(jié)構(gòu)等。依據(jù)測(cè)量?jī)?nèi)容和測(cè)量拓?fù)?，結(jié)合測(cè)量工具和方法可直接計(jì)算得到測(cè)量任務(wù)的優(yōu)選測(cè)量構(gòu)件配置集合 CT。 CT是在不考慮網(wǎng)絡(luò)整體測(cè)量資源分布情況下，為完成測(cè)量任務(wù)，在網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)上所需配置的測(cè)量構(gòu)件集合的最優(yōu)方案。CT中測(cè)量構(gòu)件所部署節(jié)點(diǎn)以及構(gòu)件間通信的鏈路構(gòu)成測(cè)量構(gòu)件優(yōu)選配置網(wǎng)絡(luò)，由無向加權(quán)圖GP=（NP, EP）表示，對(duì)于 ? n '∈ NP，滿足 n '∈NM,∈ EP，滿足∈EM。優(yōu)選配置網(wǎng)絡(luò)和優(yōu)選測(cè)量構(gòu)件配置集合構(gòu)成測(cè)量任務(wù)的優(yōu)選部署方案。而在實(shí)際測(cè)量任務(wù)部署時(shí)，由于任務(wù)間存在資源競(jìng)爭(zhēng)和沖突，因此測(cè)量?jī)?yōu)選部署方案并不一定是全網(wǎng)最優(yōu)的部署方案。

對(duì)于一個(gè)測(cè)量任務(wù)，在 NMRM 模型中可能存在多個(gè)等價(jià)部署方案。因此 NMRM 模型中的測(cè)量任務(wù)部署問題可以描述為依據(jù)全網(wǎng)資源及任務(wù)狀態(tài)在多個(gè)等價(jià)部署方案中選擇最佳方案的問題?；谝陨戏治龊兔枋觯瑴y(cè)量任務(wù)的部署問題可以抽象為測(cè)量任務(wù)優(yōu)選配置網(wǎng)絡(luò) GP到底層測(cè)量網(wǎng)絡(luò) GM的滿足測(cè)量構(gòu)件資源消耗約束等要求的映射問題, CT是底層測(cè)量網(wǎng)絡(luò)為測(cè)量任務(wù)分配的測(cè)量構(gòu)件集合，M:GP? （GM, CT） 。

測(cè)量任務(wù)優(yōu)選配置網(wǎng)絡(luò)到底層測(cè)量網(wǎng)絡(luò)的映射可以分解為節(jié)點(diǎn)映射和鏈路映射。節(jié)點(diǎn)映射是指在底層網(wǎng)絡(luò)中為 GP的節(jié)點(diǎn)選擇合適的部署位置。為提高映射效率，只在等價(jià)測(cè)量節(jié)點(diǎn)中為 GP中的節(jié)點(diǎn)尋找映射點(diǎn)。等價(jià)測(cè)量節(jié)點(diǎn)是指能夠完成與已知優(yōu)選部署節(jié)點(diǎn)相同測(cè)量功能、滿足相同測(cè)量性能的測(cè)量節(jié)點(diǎn)，用EQ）表示優(yōu)選網(wǎng)絡(luò)節(jié)點(diǎn)的等價(jià)節(jié)點(diǎn)集合。節(jié)點(diǎn)的映射過程可形式化描述為 Mn:NP?EQ（NP）。在可重構(gòu)的網(wǎng)絡(luò)測(cè)量模型中，等價(jià)節(jié)點(diǎn)與優(yōu)選網(wǎng)絡(luò)節(jié)點(diǎn)上的測(cè)量構(gòu)件配置并不一定相同，不同的構(gòu)件配置通過組合關(guān)系后可達(dá)到等效的測(cè)量能力。但由于網(wǎng)絡(luò)測(cè)量結(jié)果的準(zhǔn)確性和實(shí)時(shí)性會(huì)受到測(cè)量點(diǎn)物理位置的影響，因此等價(jià)節(jié)點(diǎn)間的網(wǎng)絡(luò)距離會(huì)受到測(cè)量任務(wù)的制約。EQ）中的節(jié)點(diǎn)滿其中，dis（ni）是節(jié)點(diǎn)距離的跳數(shù)， DT是由測(cè)量任務(wù)T確定的等價(jià)節(jié)點(diǎn)半徑，描述了節(jié)點(diǎn)與其等價(jià)節(jié)點(diǎn)之間的最遠(yuǎn)距離。圖1為測(cè)量節(jié)點(diǎn)的映射示意圖。假設(shè)圖1中，對(duì)于節(jié)點(diǎn)A存在兩個(gè)等價(jià)節(jié)點(diǎn)E和F，可以通過在E和F上配置不同的測(cè)量構(gòu)件完成相同的測(cè)量任務(wù)。

鏈路映射是指在底層網(wǎng)絡(luò)中為 GP中的鏈路選擇部署路徑Path= l1,l2,…,lk, li是部署路徑上的一條鏈路。測(cè)量鏈路的映射依賴于通信測(cè)量構(gòu)件部署節(jié)點(diǎn)之間的路徑連接情況，用 P H）表示在節(jié)點(diǎn)和之間可用于任務(wù) T的測(cè)量鏈路部署路徑集合。圖2是測(cè)量路徑與部署路徑集合之間的映射關(guān)系示意圖。GP中的鏈路用于部署主動(dòng)測(cè)量任務(wù)時(shí)測(cè)量構(gòu)件間通信。在進(jìn)行鏈路映射時(shí)，應(yīng)確保鏈路部署路徑上瓶頸鏈路的剩余帶寬與用于任務(wù)T的測(cè)量構(gòu)件間通信所消耗的傳輸帶寬率比值大于α，即 P H）中的路徑滿足：。其中，公式中的分母部分是節(jié)點(diǎn) nu和 nv之間用于任務(wù) T的測(cè)量構(gòu)件間通信所消耗的傳輸帶寬資源， Rb是

圖1 測(cè)量節(jié)點(diǎn)映過程射示意圖

圖2 測(cè)量路徑映射示意圖

u, v

該部署路徑上的瓶頸鏈路的剩余傳輸資源，α是預(yù)先設(shè)定的一個(gè)閾值，它代表主動(dòng)測(cè)量任務(wù)對(duì)于鏈路帶寬剩余比例的要求水平。鏈路的映射過程可形式化描述為： Me: EP? P H（EP）。

2.2 測(cè)量任務(wù)部署原則

基于合理利用網(wǎng)絡(luò)有限資源，降低測(cè)量任務(wù)部署成本，使底層網(wǎng)絡(luò)能夠盡可能多地承載測(cè)量任務(wù)，提高測(cè)量任務(wù)部署成功率，本文提出3條測(cè)量任務(wù)部署原則。

（1）測(cè)量資源均衡利用原則：在部署測(cè)量任務(wù)時(shí)，要盡量將測(cè)量任務(wù)均勻地部署到網(wǎng)絡(luò)節(jié)點(diǎn)上。

（2）部署代價(jià)最小化原則：通過將具有相同測(cè)量構(gòu)件需求的測(cè)量任務(wù)映射到相同底層節(jié)點(diǎn)的方法，利用測(cè)量構(gòu)件復(fù)用的特點(diǎn)，降低測(cè)量構(gòu)件組合開銷；在進(jìn)行鏈路映射時(shí)應(yīng)盡可能減小測(cè)量節(jié)點(diǎn)構(gòu)件間通信路徑的長(zhǎng)度，以降低構(gòu)件通信開銷。

（3）鏈路優(yōu)先映射原則：在進(jìn)行測(cè)量任務(wù)部署時(shí)，若存在鏈路映射，則優(yōu)先考慮按優(yōu)選部署網(wǎng)絡(luò)中的方案進(jìn)行鏈路映射。

3 基于可重構(gòu)測(cè)量模型的測(cè)量任務(wù)部署算法

3.1 評(píng)價(jià)指標(biāo)

測(cè)量任務(wù)部署問題由節(jié)點(diǎn)映射和鏈路映射兩部分問題構(gòu)成，因此分別對(duì)節(jié)點(diǎn)和路徑進(jìn)行評(píng)價(jià)。

首先定義節(jié)點(diǎn)的測(cè)量任務(wù)適合度γ（n',n），描述底層測(cè)量節(jié)點(diǎn)n對(duì)于測(cè)量任務(wù)優(yōu)選部署節(jié)點(diǎn)n'的適合度。式（7）是節(jié)點(diǎn)測(cè)量任務(wù)適合度的計(jì)算公式，其中K是測(cè)量任務(wù)在優(yōu)選配置節(jié)點(diǎn)n'上部署的測(cè)量構(gòu)件總數(shù)； xk∈ { 0,1}，當(dāng) ck∈Cn,xk= 1 ，否則xk=0; λ1, λ2為權(quán)重因子，且λ1+λ2=1。在式（4）中，與λ1相乘的部分描述了n上的剩余計(jì)算資源和存儲(chǔ)資源能力，與λ2相乘的部分表示在nM已配置的測(cè)量構(gòu)件在 nP所需配置測(cè)量構(gòu)件中占有的比例。σ是一個(gè)極小正數(shù)，用于避免當(dāng)n中沒有配置優(yōu)選測(cè)量構(gòu)件時(shí)，λ2的加權(quán)部分為0。φ（n',n）是節(jié)點(diǎn)作為鏈路映射的一個(gè)端點(diǎn)時(shí)，它對(duì)于優(yōu)選部署節(jié)點(diǎn)的適宜度。當(dāng)優(yōu)選部署節(jié)點(diǎn)n'的連接度大于0且n' = n時(shí)，即n'就是n，且是鏈路映射的一個(gè)端點(diǎn)，那么φ（n',n）=D（ n'）；否則若節(jié)點(diǎn)n'的連接度等于0，即n'不是鏈路映射的端點(diǎn)時(shí)，φ（n',n）=0。D（ n'）是節(jié)點(diǎn)n'的連接度。其中和的計(jì)算公式為式（1），式（2）。

通過式（4）計(jì)算得到的γ，不僅考慮了節(jié)點(diǎn)資源的處理能力和節(jié)點(diǎn)上測(cè)量構(gòu)件的類型，同時(shí)還考慮了當(dāng)存在構(gòu)件通信時(shí)應(yīng)盡可能將優(yōu)選節(jié)點(diǎn)映射到其節(jié)點(diǎn)本身。λ1和λ2的比值體現(xiàn)了在對(duì)節(jié)點(diǎn)的評(píng)價(jià)時(shí)，剩余資源與構(gòu)件類型的比重。γ的值越大，說明節(jié)點(diǎn)的評(píng)價(jià)越高，越適合作為n'的映射目標(biāo)。

u,v i,j i,j

算θ的前一個(gè)連乘項(xiàng)表示部署路徑是否與優(yōu)選部署網(wǎng)絡(luò)中的鏈路相同，后一個(gè)連乘項(xiàng)的物理意義是部署路徑上每條鏈路的帶寬資源空閑率的乘積。θ＞1時(shí)，表示部署路徑與優(yōu)選鏈路一致；θ＜1時(shí)，表示部署路徑與優(yōu)選鏈路不一致。因此，θ值越大的部署路徑，越適合作為 pu,v的映射目標(biāo)。

3.2 部署算法

測(cè)量任務(wù)部署算法劃分為兩個(gè)處理步驟：

步驟1 預(yù)處理過程。當(dāng)測(cè)量任務(wù)T到達(dá)后，首先生成任務(wù) T的優(yōu)選配置網(wǎng)絡(luò) GP和優(yōu)選測(cè)量構(gòu)件配置集合 CT，依據(jù)任務(wù)計(jì)算得到 GP中每個(gè)節(jié)點(diǎn)的等價(jià)節(jié)點(diǎn)集合；

步驟2 GP網(wǎng)絡(luò)映射過程。首先將 GP中的節(jié)點(diǎn)分為連接度為0的節(jié)點(diǎn)集合和連接度不為0的節(jié)點(diǎn)集合，然后先映射中的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的鏈路，最后映射中的節(jié)點(diǎn)。

表1中的算法采用廣度優(yōu)選搜索的方法遍歷進(jìn)行描述，在實(shí)際的部署算法中可采用其他的遍歷算法。任務(wù)部署時(shí)，由于節(jié)點(diǎn)和鏈路的映射存在先后順序，可能會(huì)出現(xiàn)由于節(jié)點(diǎn)或鏈路的資源不能滿足映射要求的情況，從而導(dǎo)致映射失敗。為此，算法在選擇最優(yōu)映射節(jié)點(diǎn)和鏈路時(shí)（算法的第 6, 13, 19,28步），還同時(shí)記錄一個(gè)次優(yōu)的映射目標(biāo)作為備選項(xiàng)，當(dāng)在最優(yōu)目標(biāo)上映射失敗時(shí)，立刻選擇次優(yōu)目標(biāo)進(jìn)行重新映射，從而提高測(cè)量任務(wù)部署的成功率。

3.3 算法性能理論分析

首先對(duì)MTDANMRM算法的最壞時(shí)間復(fù)雜度進(jìn)行分析。由于算法中的1, 2兩步不涉及映射過程，這部分的時(shí)間開銷可假設(shè)為一個(gè)常量κ，轉(zhuǎn)換得到的 GP中的節(jié)點(diǎn)數(shù)量為n。算法的最壞執(zhí)行情況為優(yōu)選部署網(wǎng)絡(luò) GP是一個(gè)全連通圖，在這種情況下算法每次在對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行映射后映射完一個(gè)節(jié)點(diǎn)，需要為其相鄰的所有邊進(jìn)行映射。映射每條邊的時(shí)間是尋找K條最短路徑的時(shí)間，該值與底層網(wǎng)絡(luò) GM規(guī)模相關(guān)，在分析算法間復(fù)雜度時(shí)可假設(shè)底層網(wǎng)絡(luò)規(guī)模固定，該部分開銷用常數(shù)η表示。那么，MTDANMRM 算法的最壞時(shí)間復(fù)雜度的計(jì)算公式就為

MTDANMRM 算法將測(cè)量任務(wù)部署問題轉(zhuǎn)換為優(yōu)選部署網(wǎng)絡(luò) GP到底層基礎(chǔ)網(wǎng)絡(luò) GM的映射問題，雖然算法的時(shí)間復(fù)雜度為 O （ n2），但由于MTDANMRM通過測(cè)量等價(jià)測(cè)量節(jié)點(diǎn)替換以及測(cè)量構(gòu)件配置加載等的方法，替代非重構(gòu)模型下測(cè)量任務(wù)部署過程中測(cè)量任務(wù)延時(shí)等待的方法，使得測(cè)量任務(wù)在實(shí)際部署過程中的等待時(shí)間反而有所降低，具體仿真結(jié)果見4.2節(jié)。

表1 基于測(cè)量重構(gòu)模型的測(cè)量任務(wù)部署算法

MTDANMRM 算法的收斂性表現(xiàn)為通過運(yùn)算可得到在有限測(cè)量資源上部署多樣化的測(cè)量任務(wù)的優(yōu)化方案，可用測(cè)量任務(wù)部署成功率對(duì)算法的收斂性進(jìn)行描述。用4.1節(jié)中描述的仿真環(huán)境進(jìn)行實(shí)驗(yàn)，仿真測(cè)量任務(wù)的部署成功率。設(shè)置任務(wù)數(shù)量為1000，任務(wù)沖突概率為0.5，共進(jìn)行1000次獨(dú)立實(shí)驗(yàn)，統(tǒng)計(jì)任務(wù)部署成功率95%≥的情況，結(jié)果如表2。仿真結(jié)果表明，在1000次實(shí)驗(yàn)中部署成功率超過95%的次數(shù)占總實(shí)驗(yàn)次數(shù)的 98.3%，由此證明MTDANMRM算法具有較好的收斂性。

表2 算法部署成功率仿真結(jié)果

4 算法性能仿真與分析

4.1 模擬仿真環(huán)境及方法

仿真實(shí)驗(yàn)在Pentium 4 CPU 2.8 GHz, 1.0 G內(nèi)存的處理器上進(jìn)行，測(cè)量任務(wù)的設(shè)置參考文獻(xiàn)[12]中的方法，底層測(cè)量網(wǎng)絡(luò)拓?fù)溆?GT-ITM[14]生成，包含200個(gè)節(jié)點(diǎn)和1083條鏈路。實(shí)驗(yàn)假設(shè)測(cè)量任務(wù)的存活時(shí)間在[11,100]單位時(shí)間上服從均勻分布，任務(wù)執(zhí)行時(shí)間在[2,10]上服從均勻分布，測(cè)量任務(wù)到達(dá)事件服從均值為5的泊松分布。底層網(wǎng)絡(luò)包含200個(gè)節(jié)點(diǎn)和1125條鏈路，節(jié)點(diǎn)上的存儲(chǔ)資源和計(jì)算資源分別在[1,100]和[1,10]的區(qū)間上服從均勻分布，鏈路帶寬在[50,100]之間服從均勻分布。仿真實(shí)驗(yàn)共支持10種測(cè)量構(gòu)件組合，每種測(cè)量構(gòu)件所需要的資源計(jì)算函數(shù)為確定函數(shù)。另外，假設(shè)每個(gè)測(cè)量構(gòu)件的配置和組合時(shí)間不超過測(cè)量任務(wù)執(zhí)行時(shí)間的1/β。每組仿真分別獨(dú)立進(jìn)行100次實(shí)驗(yàn)，仿真結(jié)果為實(shí)驗(yàn)平均值。

假設(shè)每個(gè)測(cè)量任務(wù)將隨機(jī)轉(zhuǎn)換為一個(gè)優(yōu)選配置網(wǎng)絡(luò) GP, GP中的節(jié)點(diǎn)數(shù)服從[3, 8]區(qū)間上的均勻分布，節(jié)點(diǎn)位置按任務(wù)之間的沖突概率[14]隨機(jī)確定，每個(gè)節(jié)點(diǎn)所需要配置的測(cè)量構(gòu)件數(shù)量在[1,5]區(qū)間上服從均勻分布，構(gòu)件類型在10種構(gòu)件間隨機(jī)產(chǎn)生，依據(jù)其產(chǎn)生的構(gòu)件類型確定節(jié)點(diǎn)之間的鏈路。

4.2 仿真實(shí)驗(yàn)結(jié)果分析

圖3 不同遍歷方法下測(cè)量任務(wù)部署成功率

分別用廣度優(yōu)先搜索和深度優(yōu)先搜索方法對(duì)算法進(jìn)行仿真，通過實(shí)驗(yàn)結(jié)果來分析不同遍歷方法對(duì)于MTDANMRM性能的影響，設(shè)定參數(shù) λ1= 0 .5,λ2= 0 .5。我們觀察了在不同任務(wù)沖突概率下測(cè)量任務(wù)的部署成功率，在100個(gè)測(cè)量任務(wù)和500個(gè)測(cè)量任務(wù)的情況下分別進(jìn)行仿真實(shí)驗(yàn)。圖3為不同遍歷方法下算法的部署成功率。圖中的兩條曲線基本吻合，說明圖的遍歷算法對(duì)于MTDANMRM算法性能的影響不大。后續(xù)的仿真實(shí)驗(yàn)均選用廣度優(yōu)先搜索方法。λ1, λ2是算法中兩個(gè)重要的參數(shù)，直接影響算法對(duì)于等價(jià)節(jié)點(diǎn)的選擇。通過仿真實(shí)驗(yàn)，觀察參數(shù)λ1,λ2對(duì)算法性能的影響。實(shí)驗(yàn)分別仿真了不同λ取值情況下，測(cè)量任務(wù)部署成功率、測(cè)量任務(wù)平均等待時(shí)間、測(cè)量節(jié)點(diǎn)資源利用均衡性這3個(gè)性能指標(biāo)，其中節(jié)點(diǎn)資源利用均衡性用節(jié)點(diǎn)資源利用率的均方差來刻畫。實(shí)驗(yàn)設(shè)定任務(wù)沖突概率為0.5，任務(wù)數(shù)量為100，圖4是實(shí)驗(yàn)仿真的結(jié)果。結(jié)果表明，λ值的變化對(duì)于算法的任務(wù)部署成功率影響不大，但其對(duì)于任務(wù)平均等待時(shí)間和測(cè)量節(jié)點(diǎn)資源利用率均方差這兩個(gè)指標(biāo)的影響較大。隨著2λ取值的增加，任務(wù)的平均等待時(shí)間減小，而測(cè)量節(jié)點(diǎn)的資源利用率均方差增大。這是由于1λ的值越大，算法在進(jìn)行節(jié)點(diǎn)映射時(shí)越趨向于選擇資源剩余多的節(jié)點(diǎn)，這樣會(huì)導(dǎo)致節(jié)點(diǎn)資源利用率越趨于均衡；而2λ的值越大，算法越趨向于選擇具有同類型測(cè)量構(gòu)件的節(jié)點(diǎn)，這樣在進(jìn)行測(cè)量任務(wù)部署時(shí)會(huì)減少新測(cè)量構(gòu)件配置和組合的時(shí)間。

圖4不同λ取值下算法性能仿真

圖5 是在任務(wù)數(shù)量為100時(shí)，不同任務(wù)沖突概率情況下算法性能仿真結(jié)果。圖 5（a）中的數(shù)據(jù)說明在任務(wù)部署成功率方面， MTDANMRM算法明顯高于 GCTS，并且隨著任務(wù)沖突概率的增加，兩個(gè)算法之間的差異越大，即在任務(wù)沖突概率較大的情況下，本文的MTDANMRM算法具更高的部署成功率。從仿真數(shù)據(jù)上看，任務(wù)部署成率不低于90%。這是由于MTDANMRM算法基于可重構(gòu)的網(wǎng)絡(luò)測(cè)量模型，當(dāng)測(cè)量任務(wù)發(fā)生沖突時(shí)，若任務(wù)所需的測(cè)量構(gòu)件相同，可通過復(fù)用構(gòu)件的方式提高任務(wù)部署成功率。圖 5（b）是任務(wù)平均等待時(shí)間的仿真結(jié)果，圖中下方的3條曲線分別為MTDANMRM算法在不同的β取值下的仿真結(jié)果。實(shí)驗(yàn)結(jié)果證明，MTDANMRM 算法的任務(wù)平均等待時(shí)間遠(yuǎn)小于GCTS算法，任務(wù)沖突概率對(duì)于任務(wù)平均等待時(shí)間的影響不明顯，這是由于兩種算法導(dǎo)致任務(wù)等待時(shí)間不同的原因，MTDANMRM算法中導(dǎo)致任務(wù)等待的時(shí)間主要來源于測(cè)量構(gòu)件的配置和組合，若測(cè)量構(gòu)件不需要重新配置，那么將不會(huì)引入等待時(shí)間。此外，β會(huì)對(duì) MTDANMRM算法的任務(wù)等待時(shí)間造成影響，β值越小，那么測(cè)量構(gòu)件的配置和組合時(shí)間將越長(zhǎng)，導(dǎo)致任務(wù)平均等待時(shí)間越長(zhǎng)。

圖5 不同任務(wù)沖突概率下的仿真結(jié)果

圖6 不同任務(wù)數(shù)量規(guī)模下的仿真結(jié)果

圖6 是當(dāng)任務(wù)沖突概率為0.5時(shí)，不同任務(wù)數(shù)量下算法性能仿真結(jié)果。圖6（a）中的實(shí)驗(yàn)結(jié)果說明，隨著測(cè)量任務(wù)數(shù)量的增加，GCTS的任務(wù)部署成功率會(huì)明顯下降，而MTDANMRM算法的任務(wù)部署成功率受任務(wù)數(shù)量的影響較小，在任務(wù)數(shù)量為1000時(shí)，其部署成功率仍可達(dá)92.21%。在任務(wù)平均等待時(shí)間上，兩種算法的仿真結(jié)果均會(huì)隨著部署任務(wù)數(shù)量的增加而增加，但MTDANMRM較GCTS的平均等待時(shí)間有顯著下降，并且隨著β值的增加，任務(wù)平均等待時(shí)間會(huì)有所降低。

4.3 真實(shí)環(huán)境實(shí)驗(yàn)分析

在模擬仿真基礎(chǔ)上，為進(jìn)一步驗(yàn)證算法性能，采用NetFPGA 搭建了包含6個(gè)網(wǎng)絡(luò)交換節(jié)點(diǎn)和1個(gè)控制節(jié)點(diǎn)的網(wǎng)絡(luò)流量測(cè)量實(shí)驗(yàn)系統(tǒng)，圖7是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。圖7中的N1～N6節(jié)點(diǎn)是6個(gè)用NetFPGA實(shí)現(xiàn)的底層交換節(jié)點(diǎn)，每個(gè)交換節(jié)點(diǎn)上通過編程可實(shí)現(xiàn)均勻抽樣、關(guān)鍵字匹配、hash映射、計(jì)數(shù)器4種測(cè)量構(gòu)件，C是控制節(jié)點(diǎn) ，通過運(yùn)行MTDANMRM算法對(duì)測(cè)量任務(wù)進(jìn)行優(yōu)化部署，并通過openflow協(xié)議接口對(duì)6個(gè)交換節(jié)點(diǎn)上的構(gòu)件進(jìn)行配置。每個(gè)交換節(jié)點(diǎn)上的TCAM, SRAM等資源以及每種測(cè)量構(gòu)件的資源占用情況均通過編程進(jìn)行設(shè)置，交換節(jié)點(diǎn)之間的流量通過測(cè)試儀注入。

圖7 不同任務(wù)數(shù)量規(guī)模下仿真結(jié)果

在實(shí)驗(yàn)網(wǎng)絡(luò)中部署 10個(gè)獨(dú)立的測(cè)量任務(wù)來測(cè)試算法在資源利用均衡性、任務(wù)部署成功率方面的性能。用于測(cè)試的測(cè)量任務(wù)屬于最大流識(shí)別、可用帶寬測(cè)量以及流量分布統(tǒng)計(jì)這3個(gè)類型，每種測(cè)量任務(wù)需要通過在節(jié)點(diǎn)上部署不同的測(cè)量構(gòu)件來完成，表3是具體的測(cè)量任務(wù)。MTDANMRM算法中的參數(shù)設(shè)置為 λ1= 0 .5, λ2= 0 .5。實(shí)驗(yàn)結(jié)果顯示，通過MTDANMRM算法，任務(wù)部署成功率達(dá)100%，網(wǎng)絡(luò)節(jié)點(diǎn)資源利用率均方差為0.153。此外，對(duì)任務(wù)1,4,7,10的測(cè)量結(jié)果進(jìn)行統(tǒng)計(jì)分析，它們對(duì)最大流的識(shí)別率均超過 98.2%。真實(shí)環(huán)境的實(shí)驗(yàn)結(jié)果與仿真數(shù)據(jù)實(shí)驗(yàn)結(jié)果一致說明，MTDANMRM算法在進(jìn)行多樣化測(cè)量任務(wù)部署時(shí)，能夠有效提高任務(wù)部署成功率，改善測(cè)量資源利用不均衡的問題。

5 結(jié)束語(yǔ)

本文針對(duì)有限測(cè)量資源與多樣化測(cè)量需求之間的矛盾日趨激化的問題，基于可重構(gòu)的網(wǎng)絡(luò)測(cè)量模型，設(shè)計(jì)了一種網(wǎng)絡(luò)測(cè)量任務(wù)部署算法MTDANMRM。該算法將測(cè)量任務(wù)轉(zhuǎn)換為測(cè)量?jī)?yōu)選配置網(wǎng)絡(luò)，利用測(cè)量構(gòu)件的組合復(fù)用原理，通過網(wǎng)絡(luò)映射算法對(duì)問題進(jìn)行求解，實(shí)現(xiàn)了全網(wǎng)范圍內(nèi)的測(cè)量任務(wù)優(yōu)化部署，從而達(dá)到高效利用網(wǎng)絡(luò)測(cè)量資源和支持測(cè)量任務(wù)動(dòng)態(tài)并發(fā)部署的目的。

MTDANMRM 算法對(duì)于部署失敗的任務(wù)沒有給出合理的調(diào)度策略。如何將現(xiàn)有任務(wù)進(jìn)行合理的遷移，對(duì)網(wǎng)絡(luò)測(cè)量資源進(jìn)行重新整合，是有待進(jìn)一步研究的問題。此外網(wǎng)絡(luò)測(cè)量任務(wù)到達(dá)特征、測(cè)量構(gòu)件組合方法、測(cè)量構(gòu)件資源消耗函數(shù)等都是后續(xù)研究的重點(diǎn)。

表3 測(cè)量任務(wù)內(nèi)容

[1] 周愛平, 程光, 郭曉軍, 高速網(wǎng)絡(luò)流量測(cè)量方法[J]. 軟件學(xué)報(bào)，2014, 25（1）: 135-153.Zhou A P, Cheng G, and Guo X J. High-Speed network traffic measurement method[J]. Journal of Software, 2014, 25（1）:135-153

[2] Yuan L, Chuah C N, and Mohapatra. ProgME: towards programmable network measurement[J]. IEEE/ACM Transactions on Networking, 2011, 19（1）: 115-128.

[3] Masoud M, Minlan Y, and Ramesh G. Resource/accuracy tradeoffs in Software-defined measurement[C]. HotSDN 2013- Proceedings of the 2013 ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, China,2013: 73-78.

[4] Minlan Y, Jose L, and Rui M. Software defined traffic measurement with opensketch[C]. 10th USENIX Symposium on Networked Systems Design and Implementation, Lombard,IL, USA, 2013: 29-42.

[5] 曹爭(zhēng), 何建斌, 基于虛擬化的網(wǎng)絡(luò)測(cè)量平臺(tái)[J]. 通信學(xué)報(bào),2013, 34（Sppl. 2）, 84-89.Cao Zheng, and He Jian-bin. Virtualization based network measurement platform[J]. Journal on Communications, 2013,34（Sppl. 2）: 84-89.

[6] 張瀟丹, 李俊. 一種基于云服務(wù)模式的網(wǎng)絡(luò)測(cè)量與分析架構(gòu)[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29（2）: 725-729.Zhang Xiao-dan and Li Jun. Network measurement and analysis architecture of cloud service[J]. Application Research of Computer, 2012, 29（2）: 725-729.

[7] Masoud M and Minlan Y. DREAM: dynamic resource allocation for software-defined measurement[C]. Proceedings of the 2014 ACM Conference on Special Interest Group on Data Communication, Chigaco, IL, USA, 2014: 419-430.

[8] Yu C and Lumezanu C. FlowSense: monitoring network utilization with zero measurement cost[C]. Proceedings of Passive and Active Measurement 14th International Conference, Hong Kong, China, 2013: 31-41.

[9] Chowdhury S R and Bari M F. PayLess: a low cost network monitoring framework for software Defined Networks[C].2014 IEEE/IFIP Network Operations and Management Symposium, Krakow, Poland, 2014: 1-9.

[10] Tootoonchian A and Ghobadi M. OpenTM: traffic matrix estimator for openflow networks[C]. Proceedings of Passive and Active Measurement 11th International Conference,Zurich, Switzerland, 2010: 201-210.

[11] Yu Y and Qian C. Distributed collaborative monitoring in software defined networks[C]. Proceedings of the ACM SIGCOMM 2014 Workshop on Hot Topics in Software Defined Networking, Chigaco, IL, USA, 2014: 85-90.

[12] Qin Zhen, Cessa R R, and Ansari N. Task-execution scheduling schemes for network measurement and monitoring[J]. Computer Communications, 2010, 33（2）:124-135.

[13] Wan Jing, Wang B Q, and Zhu Ke. How to support the diversity of network measurement requirements[C]. The 2014 3rd of the International Conference On Sensor, Measurement And Intelligent Meterials, Zhuhai, China, Dec 5-7, 2014.

[14] Zegura E, Calvert K, and Bhattacharjee S. How to model an Internetwork[C]. Proceedings of the IEEE INFOCOM, San Francisco, CA, USA, 1996: 594-602.