葛文堂，張兆心，李斌

(哈爾濱工業(yè)大學 網(wǎng)絡與信息安全研究中心，黑龍江 哈爾濱 150001)

1 引言

網(wǎng)絡模擬在研究網(wǎng)絡行為方面有著不可替代的優(yōu)勢，它可以抽象網(wǎng)絡行為特征，建立簡化模型，通過在計算機上運行該模型，得到所關心的網(wǎng)絡指標的輸出結果[1]，但是大規(guī)模網(wǎng)絡模擬需要大量的計算開銷。大多數(shù)網(wǎng)絡模擬器都采用并行離散事件模擬技術，實現(xiàn)模擬的并行化，提高模擬的規(guī)模和性能。

并行網(wǎng)絡模擬一般采用拓撲劃分的方法實現(xiàn)模擬任務的劃分[2]，即將需要模擬的網(wǎng)絡拓撲劃分為若干個子網(wǎng)，每個子網(wǎng)運行在不同的處理器上，不同子網(wǎng)之間通過消息傳遞來實現(xiàn)通信。拓撲劃分為2個階段：任務估計階段和任務劃分階段，即首先將所要模擬的網(wǎng)絡拓撲轉化為帶有權值的拓撲圖，再用流行拓撲圖劃分工具（如METIS工具集）進行劃分。YOCUM K[3]等把確定能通過節(jié)點和鏈路的最大流量作為節(jié)點和鏈路的權值；XU[4]等首先分析了影響模擬性能的拓撲劃分因素，然后根據(jù)拓撲信息和數(shù)據(jù)流對拓撲進行權值估計；王曉峰[5]等提出了基于負載估計的權值估計方法，該算法根據(jù)節(jié)點和鏈路在網(wǎng)絡拓撲圖中的核心程度對它們的權值進行估計；Liu[6]分析了METIS算法的時間復雜度和空間復雜度，改進了拓撲劃分的預處理過程，實現(xiàn)了遠程路由器的最小化和時間窗口的最大化。童琳[7]提出的基于安全事件的拓撲劃分，對DDoS和蠕蟲應用進行了權值估計，同時提出基于子網(wǎng)消減的拓撲劃分算法，降低了路由表規(guī)模，提高了模擬效率；張慈[8]對METIS進行了改進，提出了基于回退的拓撲劃分算法；張穎星[9]等提出了一個基于頂點交換的啟發(fā)式局部搜索近似劃分算法，實現(xiàn)了在計算負載均衡的前提下系統(tǒng)通信負載最優(yōu)化。Yang[10]等提出了一種基于鏈路粗化的拓撲劃分方法，該方法是一種層次聚類算法，減少了遠程鏈路的同時保證了同一區(qū)域的連通性。

現(xiàn)有的拓撲劃分算法在一定程度上提高了模擬效率，但缺少統(tǒng)一的評價方法對算法的優(yōu)劣進行衡量。因此，本文提出基于模擬運行時間的拓撲劃分評價模型，分析影響并行網(wǎng)絡模擬性能的各種因素并進行歸納分類，找出受拓撲劃分影響的因素集合，通過對并行網(wǎng)絡模擬性能的分析，建立拓撲劃分評價模型。本文在PDNS模擬環(huán)境中進行DDoS攻擊模擬，對比模型計算值與實驗結果，二者基本一致，驗證了模型的正確性；以METIS算法和子網(wǎng)消減劃分算法為例，針對不同的模擬任務對二者進行評價，發(fā)現(xiàn)METIS算法評價值比子網(wǎng)消減算法高約14%，運行DDoS模擬任務，前者運行時間比后者長，平均約為14%，實驗結果與預期評價相符，驗證了模型的有效性。

2 影響并行模擬性能因素分析

影響并行網(wǎng)絡模擬性能的主要因素包括：模擬運行環(huán)境、模擬應用、負載均衡、通信開銷與同步周期；運行環(huán)境包括模擬節(jié)點的硬件設備、模擬節(jié)點之間的網(wǎng)絡互連、模擬節(jié)點的路由機制、模擬節(jié)點的離散事件管理機制。下面重點分析與拓撲劃分有關的影響因素。

2.1 負載均衡因素

并行網(wǎng)絡模擬是由多個模擬節(jié)點相互協(xié)調來共同完成模擬，模擬運行時間是最后完成模擬任務的模擬節(jié)點的結束時間與最早開始模擬的模擬節(jié)點的開始時間之間的差值。顯然在總任務量一定的前提下，各模擬節(jié)點的任務均衡并在同一時刻開始模擬，才能使模擬時間降到最低。因此，將任務均勻地分配到不同的模擬節(jié)點上，能提高模擬性能，減少模擬運行時間。

2.2 通信開銷因素

通信開銷包含遠程通信開銷和同步通信開銷。遠程通信開銷主要是模擬過程中模擬應用發(fā)送的大量遠程數(shù)據(jù)分組需要的開銷，它們需要通過遠程鏈路發(fā)送到其他模擬節(jié)點上，涉及到真實網(wǎng)絡中的延時和帶寬。對于不同的模擬應用，不同鏈路上的數(shù)據(jù)流量大小不一，劃分要保證遠程通信量的總和最小。模擬節(jié)點之間的同步開銷與同步周期密切相關，同步周期越長，則同步次數(shù)越少，需要的同步開銷就越少。在PDNS模擬器中，同步周期一般是所有被劃分鏈路的延遲最小值。

2.3 模擬應用因素

模擬實驗中常用應用類型主要包括DDoS攻擊、蠕蟲感染，它們分別代表了目標攻擊類型和隨機感染類型的2類應用。在DDoS模擬時，確定了源地址和目的地址。根據(jù)攻擊參數(shù)，就可以計算出每條鏈路流經(jīng)數(shù)據(jù)量大小，依據(jù)這些流量來指導拓撲劃分，使其實際負載更加均勻分布在不同模擬節(jié)點之間。蠕蟲感染具有隨機性，需要利用隨機感染模型來估計負載。不同的模擬應用表現(xiàn)出不同的模擬行為，主要體現(xiàn)在數(shù)據(jù)分組的傳播路徑和數(shù)據(jù)分組的密度，因此在模擬中針對不同的模擬應用要選擇合適的劃分方法。

負載均衡和遠程通信開銷是并行模擬自身所固有的，在任何時候都要保證它們最優(yōu)。模擬過程中數(shù)據(jù)分組的分布情況將直接影響負載均衡和遠程通信開銷，體現(xiàn)了模擬應用對它們的影響。在模擬中要綜合考慮這些因素，來獲取較高的模擬性能。

3 拓撲劃分評價模型

并行網(wǎng)絡模擬的4個重要的性能指標是模擬運行時間、模擬真實度、模擬拓撲規(guī)模和模擬占用內存空間。

網(wǎng)絡模擬的實質在計算機中運行刻畫網(wǎng)絡行為的抽象模型，并對結果進行處理。顯然，模擬結果不可能與真實的網(wǎng)絡行為完全相同。模擬真實度是指模擬結果與實際網(wǎng)絡行為的吻合程度，抽象模型的準確性決定了模擬的真實度，因此，模擬真實度由模擬的抽象模型（即模擬軟件環(huán)境）所決定，不受拓撲劃分的影響。

模擬規(guī)模主要受到模擬環(huán)境存儲空間的影響，模擬軟件的抽象模型越具體，所占用的存儲空間越大，待模擬的網(wǎng)絡拓撲中的節(jié)點與鏈路越多，模擬占用內存空間越大；此外路由表也需要一定的存儲空間，模擬的應用所產(chǎn)生的數(shù)據(jù)分組在傳輸過程中需要大量的內存空間。因此，模擬規(guī)模和模擬占用空間主要受到模擬的軟硬件環(huán)境和模擬任務（包括所用的網(wǎng)絡拓撲和模擬應用）所決定，基本不會受到拓撲劃分的影響。

當確定了模擬環(huán)境和模擬任務后，拓撲劃分的結果對負載均衡、遠程通信開銷和同步周期都有影響，這3個因素影響了模擬運行時間，因此拓撲劃分對模擬運行時間的影響最大。

本文主要研究如何評價拓撲劃分，所以把模擬運行時間作為評價標準，同時把單位模擬運行時間內處理的數(shù)據(jù)分組轉發(fā)跳數(shù)作為網(wǎng)絡模擬性能的衡量標準。

3.1 模擬運行時間估計

模擬運行時間包括初始化時間Tinit、本地計算時間Tlocal、遠程通信時間Tremote和同步通信時間Tsyn，表示為

初始化時間主要包括拓撲模型建立時間。給定一個拓撲G，進行劃分后得到一系列子拓撲，令V、E分別表示最大子圖的頂點數(shù)和鏈路數(shù)。Node(V)表示建立V個節(jié)點所需的時間，Link(E)表示建立E條邊所需的時間。顯然如果劃分算法能夠使所有子圖大小一致，則可以保證初始化時間最短。則Tinit可以表示為

假設在第i個周期內共有Pi個事件需要模擬，其中，本地事件個數(shù)為PLi，遠程事件個數(shù)為PRi，顯然PLi+PRi=Pi，假設PLi=ai·Pi，則假設PRi=(1-a)Pi，ai稱為第i個周期的本地事件比率。PLi分布到N個模擬節(jié)點上，一個周期的本地計算時間由本地事件數(shù)最多的模擬節(jié)點決定。令PLmaxi=fbi·PLi=aifbiPi，根據(jù)抽屜原理，fbi∈[1/N,1]。fbi表示了負載均衡程度。令Glocal為本地計算開銷常數(shù)，即模擬節(jié)點處理一個本地事件需要的計算時間，整個模擬過程中的本地計算時間可以表示為

遠程通信開銷受遠程事件以及處理單個遠程事件的開銷影響，定義通信開銷常數(shù)Gremote為處理單個遠程事件需要的開銷。PRi個遠程數(shù)據(jù)分組，分布到N個模擬節(jié)點上，一個周期的遠程通信時間由遠程事件數(shù)最多的模擬節(jié)點決定。令當PRi≠0時，顯然rbi∈[1/N,1]。當rbi=1/N時，表示N個模擬節(jié)點處理的遠程事件數(shù)完全一致，為PRi/N；當rbi=1時，表示所有的遠程事件由一個模擬節(jié)點處理。rbi表示通信均衡程度。遠程通信時間可以表示為

同步通信開銷與通信次數(shù)、每次通信的固定開銷有關。模擬所需要的同步次數(shù)C可以表示為C=[Tsim/Tf]。Tsim表示模擬時間，Tf表示同步周期。每一次同步需要N個模擬節(jié)點相互通信，每次通信的固定開銷Gsyn稱為同步開銷常數(shù)。則GsynN表示為N個模擬節(jié)點每進行一次同步需要的時間開銷。模擬過程中的同步開銷可以表示為

3.2 拓撲劃分評價模型

定義本地事件數(shù)最大和為Plocal，表示各個周期中N個模擬節(jié)點本地事件數(shù)最大值之和，由如下公式表示。

定義遠程事件數(shù)最大和為Premote，表示各個周期中N個模擬節(jié)點遠程事件數(shù)最大值之和，由如下公式表示。

定義模擬性能E為模擬單個數(shù)據(jù)分組轉發(fā)所需的時間，即模擬運行時間除以數(shù)據(jù)分組轉發(fā)總數(shù)由如下公式表示。

定義本地負載不均衡比為Fb，越大表示越不均衡，越小表示越均衡。定義a為本地事件比重，顯然a∈(0,1]，實際模擬中a一般大于0.8。Fb∈[1,N]，由如下公式表示。

定義遠程通信因子為Fr。顯然Fr∈[0,N]，由于網(wǎng)絡模擬中遠程事件所占的比重相對較少，所以Fr的值都很小。Fr由如下公式表示。

定義數(shù)據(jù)分組轉發(fā)密度為psim，表示平均單位模擬時間的數(shù)據(jù)分組轉發(fā)數(shù)，它的大小與具體的模擬應用有關，由如下公式表示。

結合以上公式，E的計算方法如下

模擬性能主要受如下因素的影響：模擬節(jié)點個數(shù)、同步開銷常數(shù)、本地計算開銷常數(shù)、遠程開銷常數(shù)、數(shù)據(jù)分組轉發(fā)密度、本地負載不均衡比、遠程通信不均衡比、同步周期和本地事件比重、劃分后最大子拓撲的節(jié)點數(shù)與鏈路數(shù)。

依靠模擬運行環(huán)境、模擬應用以及模擬拓撲的劃分情況，該模型可以在模擬之前估計出模擬所需要的時間以及模擬性能。當確定了模擬環(huán)境和模擬應用，那么前5個因素可以作為常數(shù)使用，則模擬性能只受由拓撲劃分決定的4個因素影響，因此可以把該性能模型作為評價網(wǎng)絡拓撲劃分的一種評價模型。模型如下

4 實驗及結果分析

在拓撲劃分評價模型公式中包括了軟硬件環(huán)境因素、模擬的應用因素、網(wǎng)絡拓撲劃分的結果等。該模型只有在具體的模擬環(huán)境和模擬應用中才有意義。由于模擬環(huán)境的不同，用理論推導獲得的計算評價模型常數(shù)的方法難以來滿足各種模擬環(huán)境?；谏鲜鲈颍疚脑O計了一套通用的標準實驗方法，采用實驗測量的方式在具體的模擬環(huán)境中測量各種常數(shù)的數(shù)值。下面詳細介紹實驗方案。

本文實驗運行環(huán)境包括硬件環(huán)境與軟件環(huán)境。硬件環(huán)境包括2臺曙光服務器，配置為AMD雙路雙核3.0 GHz CPU、16 GB內存，節(jié)點機間采用局域網(wǎng)互聯(lián)。每個服務器上面安裝2個虛擬機，虛擬機采用Red Hat AS4系統(tǒng)，4 GB內存。在實驗中，首先建立一個拓撲模型，采用對稱啞鈴拓撲結構。拓撲的一部分如圖1所示。這種拓撲結構非常適合于對并行網(wǎng)絡模擬性能的主要影響因素進行實驗分析。主要因為負載的不均衡度容易在拓撲中控制；遠程通信開銷因素比例容易控制；同步周期容易控制；拓撲容易擴展。

圖1 實驗采用的拓撲結構

在實驗中，采用DDoS攻擊作為模擬應用，通過設置不同數(shù)量的源主機、目的主機、攻擊參數(shù)，可以方便地統(tǒng)計模型中各個參數(shù)的值。

4.1 評價模型正確性驗證

設置標準實驗測量給定環(huán)境的常數(shù)：Glocal、Gremote、Gsyn。設計一組實驗，僅Plocal不同運行這組模擬應用，得到一系列離散點(Pi,Ti)，對離散點進行直線擬合，

local得到T=KPlocal+b，斜率K即為Glocal。同樣方法測量其他參數(shù)。測量結果如下：Glocal=7.3×10-5、Gremote=1.18×10-4、Gsyn=9.38×10-4、Link(x)=8.79×10-7x2+2.98×10-4x、Node(x)=1.5×10-3x，發(fā)現(xiàn)鏈路的建立時間不是線性的。

下面運用實驗來驗證模型的正確性。實驗各個參數(shù)如表1所示。

表1 實驗參數(shù)設置

從圖2～圖4中可以發(fā)現(xiàn)，理論計算值與實驗值基本一致。因此，該模型可以比較準確地估計模擬性能。

圖2 Tf與模擬性能關系

圖3 Fb與模擬性能關系

圖4 Fr與模擬性能關系

從圖2中可以發(fā)現(xiàn)，隨著通信周期的增大，單個事件的計算開銷呈下降趨勢，說明模擬性能提高，與理論分析一致。

從圖3中可以看出，隨著負載不均衡比的增大，單個事件的計算開銷呈上升趨勢，說明模擬性能逐漸降低，表明負載均衡因素對模擬性能的影響。

從圖4中可以看出，隨著遠程通信因子的增大，單個事件的計算開銷呈上升趨勢，說明模擬性能逐漸降低，表明遠程通信因素對模擬性能的影響。

4.2 評價模型有效性驗證

拓撲劃分的目標是提高模擬性能，減少運行時間，該模型以模擬運行時間為基礎，把它作為評價拓撲劃分算法優(yōu)劣的標準是合理可行的。下面使用該模型對原始METIS劃分算法和基于子網(wǎng)消減的拓撲劃分算法進行評價。本文使用啟明星辰探測的全國路由器級的網(wǎng)絡拓撲結構，分別選擇國家骨干網(wǎng)、北京、廣東、黑龍江、江蘇、云南、重慶、浙江的網(wǎng)絡拓撲，設計了8組DDoS攻擊模擬任務，每次模擬中的數(shù)據(jù)分組轉發(fā)總數(shù)約為2 500萬。根據(jù)模擬環(huán)境、模擬任務和拓撲劃分結果，計算出評價TP值，然后在PDNS模擬器中運行各組模擬任務進行對比，結果如圖5和圖6所示。

圖5 TP值對比

圖6 模擬運行時間對比

從圖5的TP值對比可以發(fā)現(xiàn)，METIS算法的TP值比子網(wǎng)消減的TP值大約為14%。圖6是2種拓撲劃分算法的模擬運行時間對比圖，從圖中發(fā)現(xiàn)，使用METIS劃分結果的模擬運行時間比子網(wǎng)消減劃分算法的運行時間長，平均約為14%。子網(wǎng)消減算法以METIS算法為基礎，對METIS的劃分結果進行優(yōu)化，通過減少劃分后每個模擬區(qū)域的子網(wǎng)個數(shù)，間接減少了遠程事件個數(shù)，從而提高了模擬性能，實驗結果與模型評價一致，表明了模型的有效性。

5 結束語

本文分析了影響并行網(wǎng)絡模擬的各種因素，通過對各個因素進行歸納分類，找出了受拓撲劃分影響的因素，通過對并行網(wǎng)絡模擬性能的分析，在基于模擬運行時間的推導過程中，提出了基于模擬運行時間的拓撲劃分評價模型。在PDNS模擬環(huán)境中進行試驗，首先，通過對比模型計算值與實驗值表明，對于給定的模擬運行環(huán)境和模擬應用，該模型能夠較為準確地估計模擬性能，能夠描述各因素對模擬性能影響的程度與趨勢；使用該評價模型對METIS劃分算法和基于子網(wǎng)消減的拓撲劃分劃分算法進行了評價，發(fā)現(xiàn)METIS算法比子網(wǎng)消減算法性能低約為14%，結果表明，該模型可以對拓撲劃分算法的優(yōu)劣做出合理評價。

利用該評價模型可以不需要運行模擬過程，只需要進行拓撲劃分過程，就可以預先估計不同的拓撲劃分算法導致的模擬性能，對劃分算法進行評價，以選擇較優(yōu)的劃分算法。此外，還可以將該評價模型作為研究新劃分方法的目標函數(shù)。

[1] 雷擎, 王行剛. 計算機網(wǎng)絡模擬方法與工具[J]. 通信學報, 2001,22(9):84-90.LEI Q, WANG X G. Overview of the network simulation methodologies and tools[J]. Journal on Communications, 2001, 22(9):84-90.

[2] 尤洪濤, 姜小成, 陳左寧. 基于動態(tài)任務劃分的降級機制[J]. 微計算機信息, 2006, 22(30):72-75.YOU H T, JIANG X C, CHEN Z N. Design of degrade based on dynamic job assignment[J]. Control and Automation Publication Group,2006, 22(30):72-75.

[3] KEN Y, ETHAN E, JULIUS D. Toward scaling network emulation using topology partitioning[A]. Proc of the 11th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer Telecommunications Systems[C]. Orlando Florida, 2003. 242-245.

[4] XU D H, AMMAR M. BencHMAP: benchmark-based, hardware and model-aware partitioning for parallel and distributed network simulation[A].Proc of the 12th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems[C]. Volendam, 2004. 455-463.

[5] 王曉峰, 方濱興, 云曉春. 并行網(wǎng)絡模擬中的一種拓撲劃分方法[J].通信學報, 2006, 27(2):16-21.WANG X F, FANG B X, YUN X C. Approach for topology partitioning in parallel network simulation[J]. Journal on Communications, 2006,27(2):16-21.

[6] LIU Y, LI B, DONG K K. Reaching of topology partition for parallel network simulation[A]. Proc of 2009 2nd International Conference on Power Electronics and Intelligent Transportation System (PEITS)[C].Shenzhen, China, 2009. 18-21.

[7] 童琳. 并行網(wǎng)絡模擬中面向安全事件的拓撲劃分技術研究[D]. 哈爾濱: 哈爾濱工業(yè)大學, 2010. 13-43.TONG L. Research on Topology Partitioning Oriented for Security Incident in Parallel Network Simulation[D]. Harbin: Harbin Institute of Technology, 2010. 13-43.

[8] 張慈, 張兆心, 遲樂軍. 基于回退的并行網(wǎng)絡模擬拓撲劃分算法[J].微計算機信息, 2011, 27(4):150-151.ZHANG C, ZHANG Z X, CHI L J. Task partitioning algorithm based on rollback of parallel network simulation[J]. Control and Automation Publication Group, 2011, 27(4):150-151.

[9] 張穎星, 姚益平. 樂觀策略下并行離散事件仿真動態(tài)負載劃分優(yōu)化算法[J]. 計算機學報, 2010, 33(5):813-821.ZHANG Y X, YAO Y P. A dynamic partitioning algorithm based on approximate local search for optimistic parallel discrete event simulation[J]. Chinese Journal of Computers, 2010, 33(5):813-821.

[10] YANG X Q, HE H, ZHANG H L. A topology partition algorithm based on link coarsening in parallel network simulation[A]. Proc of 2009 Second International Symposium on Information Science and Engineering[C]. Shanghai, China, 2009. 514-518.