基于可重構測量模型的網絡測量任務部署算法

王 晶 汪斌強 張校輝

1 引言

隨著網絡技術的飛速發展以及網絡應用的空前膨脹，網絡規模、網絡鏈路速率以及各種新興網絡應用都對網絡測量提出了新需求和新挑戰[1]。網絡測量不僅需要滿足更加多樣化的測量需求，提供更加準確、實時的測量結果，還需要支持并發測量任務的動態加載。網絡測量資源與多測量需求之間的矛盾日趨凸顯。

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

為了解決在有限測量資源上承載多樣化測量任務的問題，可重構的網絡測量模型NMRM[13]（Network Measurement Reconfiguration Model）通過分層方法，將測量資源與測量需求分離，實現靈活、可擴展的網絡測量功能。NMRM中的適配層依據測量任務和網絡測量資源狀況，為測量需求計算出最合適的任務部署方案。如何調度網絡測量資源，為測量任務分配合理的測量構件，在不同任務之間復用測量構件，會直接影響 NMRM 中的資源利用率以及對于多樣化并行測量任務支持的能力，因此測量任務部署問題是NMRM中的重要研究內容。

本文基于NMRM提出一種測量任務部署算法。首先對可重構測量模型中的任務部署問題進行抽象描述，并將問題轉換為網絡節點映射問題；然后給出問題的優化求解方法；最后通過實驗仿真對算法進行分析驗證。實驗結果表明在任務部署成功率和任務平均等待時間這兩個性能上，本文算法都比傳統的GCTS算法有更好的表現，并且當任務沖突率和任務規模數量增加時，算法的部署成功率都能保證在90%以上。

本文第2節對可重構網絡測量中的測量任務部署問題進行數學建模及轉換；第3節給出詳細的任務部署算法；第4節進行算法性能分析與仿真實驗；第5節進行總結。

2 問題描述

2.1 測量任務部署模型

基于可重構測量模型的網絡測量任務部署模型包括測量網絡、測量構件和測量任務這3個重要元素，首先對它們進行描述。

（1）測量網絡 測量網絡是指由包含測量資源的測量節點及節點間的鏈路組成的底層物理網絡，用無向圖 GM=（NM, EM）表示， NM是測量節點集合， EM是邊鏈路集合。在可重構的測量網絡中，測量網絡等價于實際的網絡。NM中第i個網絡節點ni上已配置的測量構件用集合 Ci表示，總計算資源和總存儲資源分別用和示；節點u, v間的邊鏈路 eu,v上的總傳輸帶寬資源用表示。

（2）測量構件 測量構件是組合構成測量算法的基本單元[13]，通過構件間的組合，能夠動態靈活地實現各種測量功能，從而支持各類測量任務。測量構件消耗的資源可用資源消耗函數來刻畫，本文中僅考慮測量構件的計算資源、存儲資源和帶寬資源消耗。計算資源消耗函數cj）和存儲資源消耗函數（i, cj），分別用于計算測量網絡節點 ni中測量構件 cj所消耗的計算資源和存儲資源。帶寬資源消耗函數（i, ck, j, cl）用于計算節點 ni中測量構件 ck和節點 nj中測量構件 cl通信所消耗的鏈路帶寬資源。不同構件的資源消耗函數不盡相同。節點剩余的計算資源、存儲資源分別用和表示，節點間鏈路剩余的帶寬資源用表示，計算公式分別

其中k表示節點 ni上配置的測量構件總數，costc）為節點上用于其它功能的計算資源開銷，costm（）為節點上用于其它功能的存儲資源開銷；n, m分別表示節點 nu和 nv上配置的測量構件總數量， c ostb（e ）為鏈路上的其它帶寬資源開銷。

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

對于一個測量任務，在 NMRM 模型中可能存在多個等價部署方案。因此 NMRM 模型中的測量任務部署問題可以描述為依據全網資源及任務狀態在多個等價部署方案中選擇最佳方案的問題。基于以上分析和描述，測量任務的部署問題可以抽象為測量任務優選配置網絡 GP到底層測量網絡 GM的滿足測量構件資源消耗約束等要求的映射問題, CT是底層測量網絡為測量任務分配的測量構件集合，M:GP? （GM, CT） 。

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

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

圖1 測量節點映過程射示意圖

圖2 測量路徑映射示意圖

u, v

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

2.2 測量任務部署原則

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

（1）測量資源均衡利用原則：在部署測量任務時，要盡量將測量任務均勻地部署到網絡節點上。

（2）部署代價最小化原則：通過將具有相同測量構件需求的測量任務映射到相同底層節點的方法，利用測量構件復用的特點，降低測量構件組合開銷；在進行鏈路映射時應盡可能減小測量節點構件間通信路徑的長度，以降低構件通信開銷。

（3）鏈路優先映射原則：在進行測量任務部署時，若存在鏈路映射，則優先考慮按優選部署網絡中的方案進行鏈路映射。

3 基于可重構測量模型的測量任務部署算法

3.1 評價指標

測量任務部署問題由節點映射和鏈路映射兩部分問題構成，因此分別對節點和路徑進行評價。

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

通過式（4）計算得到的γ，不僅考慮了節點資源的處理能力和節點上測量構件的類型，同時還考慮了當存在構件通信時應盡可能將優選節點映射到其節點本身。λ1和λ2的比值體現了在對節點的評價時，剩余資源與構件類型的比重。γ的值越大，說明節點的評價越高，越適合作為n'的映射目標。

u,v i,j i,j

算θ的前一個連乘項表示部署路徑是否與優選部署網絡中的鏈路相同，后一個連乘項的物理意義是部署路徑上每條鏈路的帶寬資源空閑率的乘積。θ＞1時，表示部署路徑與優選鏈路一致；θ＜1時，表示部署路徑與優選鏈路不一致。因此，θ值越大的部署路徑，越適合作為 pu,v的映射目標。

3.2 部署算法

測量任務部署算法劃分為兩個處理步驟：

步驟1 預處理過程。當測量任務T到達后，首先生成任務 T的優選配置網絡 GP和優選測量構件配置集合 CT，依據任務計算得到 GP中每個節點的等價節點集合；

步驟2 GP網絡映射過程。首先將 GP中的節點分為連接度為0的節點集合和連接度不為0的節點集合，然后先映射中的節點以及節點之間的鏈路，最后映射中的節點。

表1中的算法采用廣度優選搜索的方法遍歷進行描述，在實際的部署算法中可采用其他的遍歷算法。任務部署時，由于節點和鏈路的映射存在先后順序，可能會出現由于節點或鏈路的資源不能滿足映射要求的情況，從而導致映射失敗。為此，算法在選擇最優映射節點和鏈路時（算法的第 6, 13, 19,28步），還同時記錄一個次優的映射目標作為備選項，當在最優目標上映射失敗時，立刻選擇次優目標進行重新映射，從而提高測量任務部署的成功率。

3.3 算法性能理論分析

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

MTDANMRM 算法將測量任務部署問題轉換為優選部署網絡 GP到底層基礎網絡 GM的映射問題，雖然算法的時間復雜度為 O （ n2），但由于MTDANMRM通過測量等價測量節點替換以及測量構件配置加載等的方法，替代非重構模型下測量任務部署過程中測量任務延時等待的方法，使得測量任務在實際部署過程中的等待時間反而有所降低，具體仿真結果見4.2節。

表1 基于測量重構模型的測量任務部署算法

MTDANMRM 算法的收斂性表現為通過運算可得到在有限測量資源上部署多樣化的測量任務的優化方案，可用測量任務部署成功率對算法的收斂性進行描述。用4.1節中描述的仿真環境進行實驗，仿真測量任務的部署成功率。設置任務數量為1000，任務沖突概率為0.5，共進行1000次獨立實驗，統計任務部署成功率95%≥的情況，結果如表2。仿真結果表明，在1000次實驗中部署成功率超過95%的次數占總實驗次數的 98.3%，由此證明MTDANMRM算法具有較好的收斂性。

表2 算法部署成功率仿真結果

4 算法性能仿真與分析

4.1 模擬仿真環境及方法

仿真實驗在Pentium 4 CPU 2.8 GHz, 1.0 G內存的處理器上進行，測量任務的設置參考文獻[12]中的方法，底層測量網絡拓撲由 GT-ITM[14]生成，包含200個節點和1083條鏈路。實驗假設測量任務的存活時間在[11,100]單位時間上服從均勻分布，任務執行時間在[2,10]上服從均勻分布，測量任務到達事件服從均值為5的泊松分布。底層網絡包含200個節點和1125條鏈路，節點上的存儲資源和計算資源分別在[1,100]和[1,10]的區間上服從均勻分布，鏈路帶寬在[50,100]之間服從均勻分布。仿真實驗共支持10種測量構件組合，每種測量構件所需要的資源計算函數為確定函數。另外，假設每個測量構件的配置和組合時間不超過測量任務執行時間的1/β。每組仿真分別獨立進行100次實驗，仿真結果為實驗平均值。

假設每個測量任務將隨機轉換為一個優選配置網絡 GP, GP中的節點數服從[3, 8]區間上的均勻分布，節點位置按任務之間的沖突概率[14]隨機確定，每個節點所需要配置的測量構件數量在[1,5]區間上服從均勻分布，構件類型在10種構件間隨機產生，依據其產生的構件類型確定節點之間的鏈路。

4.2 仿真實驗結果分析

圖3 不同遍歷方法下測量任務部署成功率

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

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

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

圖5 不同任務沖突概率下的仿真結果

圖6 不同任務數量規模下的仿真結果

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

4.3 真實環境實驗分析

在模擬仿真基礎上，為進一步驗證算法性能，采用NetFPGA 搭建了包含6個網絡交換節點和1個控制節點的網絡流量測量實驗系統，圖7是網絡拓撲結構。圖7中的N1～N6節點是6個用NetFPGA實現的底層交換節點，每個交換節點上通過編程可實現均勻抽樣、關鍵字匹配、hash映射、計數器4種測量構件，C是控制節點 ，通過運行MTDANMRM算法對測量任務進行優化部署，并通過openflow協議接口對6個交換節點上的構件進行配置。每個交換節點上的TCAM, SRAM等資源以及每種測量構件的資源占用情況均通過編程進行設置，交換節點之間的流量通過測試儀注入。

圖7 不同任務數量規模下仿真結果

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

5 結束語

本文針對有限測量資源與多樣化測量需求之間的矛盾日趨激化的問題，基于可重構的網絡測量模型，設計了一種網絡測量任務部署算法MTDANMRM。該算法將測量任務轉換為測量優選配置網絡，利用測量構件的組合復用原理，通過網絡映射算法對問題進行求解，實現了全網范圍內的測量任務優化部署，從而達到高效利用網絡測量資源和支持測量任務動態并發部署的目的。

MTDANMRM 算法對于部署失敗的任務沒有給出合理的調度策略。如何將現有任務進行合理的遷移，對網絡測量資源進行重新整合，是有待進一步研究的問題。此外網絡測量任務到達特征、測量構件組合方法、測量構件資源消耗函數等都是后續研究的重點。

表3 測量任務內容

[1] 周愛平, 程光, 郭曉軍, 高速網絡流量測量方法[J]. 軟件學報，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] 曹爭, 何建斌, 基于虛擬化的網絡測量平臺[J]. 通信學報,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] 張瀟丹, 李俊. 一種基于云服務模式的網絡測量與分析架構[J]. 計算機應用研究, 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.