郭艷來(lái)，崔益民，唐 洪，李 津

（北京系統(tǒng)工程研究所 信息系統(tǒng)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100101）

0 引 言

現(xiàn)如今，越來(lái)越多的方法被應(yīng)用于減少硬件資源消耗，以高效準(zhǔn)確地進(jìn)行大規(guī)模網(wǎng)絡(luò)安全實(shí)驗(yàn)：分布式計(jì)算和資源復(fù)用可以應(yīng)用于模擬和仿真實(shí)驗(yàn)［1］，以較少的物理資源來(lái)保證實(shí)驗(yàn)的規(guī)模，例如離散事件模擬器［1，3］，生成的時(shí)間可以分布于多臺(tái)機(jī)器上來(lái)減少實(shí)驗(yàn)時(shí)間以及對(duì)每臺(tái)機(jī)器的硬件資源的需求；仿真平臺(tái)以及測(cè)試床可以通過(guò)將虛擬資源映射到可用的物理資源來(lái)保證實(shí)驗(yàn)規(guī)模，例如Emulab可以支持20倍于自身測(cè)試床的實(shí)驗(yàn)規(guī)模［2］，但這種映射是一個(gè)NP難問(wèn)題［3］，主要的難點(diǎn)在于物理資源過(guò)載導(dǎo)致實(shí)驗(yàn)得不到準(zhǔn)確可信的實(shí)驗(yàn)結(jié)果。拓?fù)浞指羁梢詳U(kuò)展網(wǎng)絡(luò)安全實(shí)驗(yàn)規(guī)模，基于模擬退火算法的拓?fù)浞指罴夹g(shù)被應(yīng)用于實(shí)驗(yàn)的資源自動(dòng)映射問(wèn)題［4］。

解決此問(wèn)題的另外一種思路是拓?fù)浼s簡(jiǎn)［5］，即在保留原有拓?fù)鋱D主要特性的同時(shí)，采取減少不擁塞鏈路和流量抽樣［6］的方法減小實(shí)驗(yàn)網(wǎng)絡(luò)的規(guī)模［7，8］。這類方法避免了拓?fù)浞指钸@個(gè)NP難問(wèn)題，但是由于不能完整地保留原網(wǎng)絡(luò)拓?fù)涞奶匦?，?shí)驗(yàn)結(jié)果的精確度不能保證，且實(shí)現(xiàn)起來(lái)有一定的難度。

本文提出了一種基于圖論的拓?fù)浞指罴夹g(shù)，來(lái)實(shí)現(xiàn)實(shí)驗(yàn)資源動(dòng)態(tài)均衡的動(dòng)態(tài)映射，這種方法有效地降低了物理主機(jī)間的通信量，平衡了個(gè)物理主機(jī)的計(jì)算量，可以有效地支撐仿真實(shí)驗(yàn)網(wǎng)絡(luò)的合理映射與部署。

1 拓?fù)浞指顔?wèn)題描述

為了滿足網(wǎng)絡(luò)仿真實(shí)驗(yàn)環(huán)境建設(shè)目標(biāo)，需要構(gòu)造大規(guī)模拓?fù)浣Y(jié)構(gòu)以仿真實(shí)際條件下的網(wǎng)絡(luò)場(chǎng)景［9］。通過(guò)研究拓?fù)浞指罴夹g(shù)，將生成的虛擬網(wǎng)絡(luò)映射到真實(shí)的實(shí)驗(yàn)資源上，能夠?yàn)槟繕?biāo)拓?fù)渲贫ê侠淼挠成浞桨?，從而將欲仿真的?shí)驗(yàn)網(wǎng)絡(luò)分散部署到不同的物理主機(jī)上，將不便仿真的特殊設(shè)備映射到實(shí)物裝備上，以確保實(shí)驗(yàn)場(chǎng)景能夠更加均衡地利用相對(duì)有限的物理資源。

在網(wǎng)絡(luò)仿真實(shí)驗(yàn)中，由于服務(wù)及應(yīng)用資源構(gòu)建于計(jì)算資源之上，計(jì)算資源需要承擔(dān)高密度的計(jì)算任務(wù)。因此在實(shí)驗(yàn)運(yùn)行中，實(shí)驗(yàn)任務(wù)通常要求計(jì)算資源能夠依據(jù)系統(tǒng)中計(jì)算節(jié)點(diǎn)的組成以及能力需求，動(dòng)態(tài)分配并部署節(jié)點(diǎn)所需資源，包括處理器性能、內(nèi)存空間、硬盤容量、I／O 類型、網(wǎng)絡(luò)接口等。在網(wǎng)絡(luò)仿真實(shí)驗(yàn)場(chǎng)景構(gòu)建的過(guò)程中，解決虛擬資源映射的網(wǎng)絡(luò)拓?fù)浞指罴夹g(shù)在實(shí)現(xiàn)后，需要保證虛擬資源裝載的動(dòng)態(tài)均衡和最小化物理主機(jī)間的通信量［10］。

（1）負(fù)載均衡：仿真實(shí)驗(yàn)網(wǎng)絡(luò)要均衡地部署于不同的物理主機(jī)。既要保證某臺(tái)機(jī)器不能承擔(dān)過(guò)多的運(yùn)算任務(wù)，也要確保仿真物理環(huán)境中的所有運(yùn)算資源都能得到充分利用。

（2）物理主機(jī)間通信量：要在負(fù)載均衡基礎(chǔ)上保證物理主機(jī)間通信量最小。分割部署在不同物理主機(jī)上的網(wǎng)絡(luò)間要進(jìn)行交互通信，這就有了通信開(kāi)銷。同時(shí)，單臺(tái)物理主機(jī)所能對(duì)外提供的網(wǎng)絡(luò)接口資源也是有限的。通過(guò)減少拓?fù)浞指罱Y(jié)果中分布于不同物理主機(jī)上的網(wǎng)絡(luò)子域之間的鏈路數(shù)，可以較好地解決這一問(wèn)題。

針對(duì)仿真實(shí)驗(yàn)環(huán)境中的計(jì)算資源分配問(wèn)題，通過(guò)各計(jì)算基礎(chǔ)設(shè)施的節(jié)點(diǎn)之間的資源動(dòng)態(tài)調(diào)度和協(xié)同操作來(lái)實(shí)現(xiàn)計(jì)算基礎(chǔ)設(shè)施的負(fù)載均衡，提高物理資源利用率，降低管理的復(fù)雜度，構(gòu)建高效的資源分配策略和機(jī)制。多機(jī)環(huán)境計(jì)算基礎(chǔ)設(shè)施資源分配，采用的仿真計(jì)算資源重構(gòu)模型如圖1所示。

圖1 多機(jī)環(huán)境下的仿真計(jì)算資源重構(gòu)模型

其過(guò)程可分成兩個(gè)階段進(jìn)行，根據(jù)實(shí)現(xiàn)目標(biāo)的不同，兩個(gè)階段所采取的策略和規(guī)則以及操作也都不同。首先確定需要遷移的仿真節(jié)點(diǎn)，主要目的是對(duì)各仿真節(jié)點(diǎn)的計(jì)算能力進(jìn)行監(jiān)控，以及各仿真節(jié)點(diǎn)的宿主平臺(tái)的仿真能力進(jìn)行計(jì)算；然后對(duì)需要進(jìn)行遷移的仿真節(jié)點(diǎn)進(jìn)行全局的統(tǒng)籌，解決仿真節(jié)點(diǎn)遷移目的地的問(wèn)題，確定遷移方案，實(shí)現(xiàn)各宿主平臺(tái)的計(jì)算資源二次分配，實(shí)現(xiàn)負(fù)載平衡。

2 基于圖論的拓?fù)浞指?/h2>

在進(jìn)行大規(guī)模網(wǎng)絡(luò)仿真實(shí)驗(yàn)時(shí)，根據(jù)實(shí)驗(yàn)需求生成各種拓?fù)浣Y(jié)構(gòu)的實(shí)驗(yàn)環(huán)境，首先需要解決實(shí)驗(yàn)環(huán)境的拓?fù)浣Y(jié)構(gòu)中相關(guān)概念的定義。

2.1 虛擬網(wǎng)絡(luò)拓?fù)湎嚓P(guān)定義

針對(duì)網(wǎng)絡(luò)化信息系統(tǒng)，虛擬網(wǎng)絡(luò)拓?fù)涿枋鲇脕?lái)表現(xiàn)網(wǎng)絡(luò)中的路由節(jié)點(diǎn)和端系統(tǒng)，以及它們之間的互聯(lián)關(guān)系。

在網(wǎng)絡(luò)拓?fù)溲芯恐?，一般的拓?fù)浣Y(jié)構(gòu)通常可以用無(wú)向圖來(lái)描述。無(wú)向圖定義如下：圖G＝ （V，E），其中V＝｛v｜v是G 中的節(jié)點(diǎn)｝，E＝｛（u，v）｜u∈V，v∈V 且u和v相鄰接｝，節(jié)點(diǎn)出度dv＝｜｛u｜（u，v）∈E｝｜；出度頻率fd＝｜｛v｜v∈V 且dv∈d｝｜。

無(wú)向圖G＝ （V，E），如果節(jié)點(diǎn)集V 代表路由器節(jié)點(diǎn)，邊集E代表路由器間物理連接鏈路，則稱之為路由器級(jí)網(wǎng)絡(luò)拓?fù)鋱D；如果節(jié)點(diǎn)集V 代表自治域節(jié)點(diǎn)，邊集E 代表自治域間物理連接鏈路，那么稱之為自治域級(jí)網(wǎng)絡(luò)拓?fù)鋱D。

用于刻畫用戶需求的虛擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)指實(shí)驗(yàn)人員希望利用大規(guī)模網(wǎng)絡(luò)仿真實(shí)驗(yàn)環(huán)境構(gòu)造的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。該結(jié)構(gòu)不但包括路由器級(jí)網(wǎng)絡(luò)拓?fù)?，還包含端系統(tǒng)以及各類型節(jié)點(diǎn)和鏈路的屬性。基于無(wú)向圖的定義，給出虛擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)定義：

定義虛擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)用無(wú)向圖GV＝ （V，E）表示，其中V＝ ｛v｜v是G 中的一個(gè)節(jié)點(diǎn)｝表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，類型包括路由器、交換機(jī)以及端系統(tǒng)等；E＝｛（u，v）｜u∈V，v∈V且u和v相鄰接｝表示節(jié)點(diǎn)間的連接關(guān)系，類型包括無(wú)線鏈路和有線鏈路等。每種類型的節(jié)點(diǎn)或鏈路均有各自的屬性。

2.2 物理網(wǎng)絡(luò)拓?fù)?/h3>

實(shí)驗(yàn)環(huán)境的物理拓?fù)浣Y(jié)構(gòu)可用無(wú)向圖G＝ （V，E）表示，其中V＝ ｛v｜v是G 中的節(jié)點(diǎn)｝，表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，包括核心交換機(jī)S、仿真節(jié)點(diǎn)E以及真實(shí)網(wǎng)絡(luò)設(shè)備R這3種類型。各類型節(jié)點(diǎn)的屬性見(jiàn)表1。

表1 物理節(jié)點(diǎn)類型

E＝ ｛（u，v）｜u∈V，v∈V 且u和v相鄰接｝表示節(jié)點(diǎn)間鏈接的集合。鏈路屬性用Eattr＝ ｛b，d，l｝，分別表示鏈路的帶寬、延遲和丟包率。

為了滿足網(wǎng)絡(luò)安全實(shí)驗(yàn)環(huán)境建設(shè)目標(biāo)，需要構(gòu)造大規(guī)模拓?fù)浣Y(jié)構(gòu)以仿真實(shí)際條件下的網(wǎng)絡(luò)運(yùn)行場(chǎng)景。通過(guò)研究實(shí)驗(yàn)資源的拓?fù)溆成浼夹g(shù)，能夠?yàn)槟繕?biāo)拓?fù)渲贫ê侠淼挠成浞桨?，從而將欲仿真的?shí)驗(yàn)網(wǎng)絡(luò)分散部署到不同的物理主機(jī)上，將不便仿真的特殊設(shè)備映射到實(shí)物裝備上，以確保實(shí)驗(yàn)場(chǎng)景能夠更加均衡地利用相對(duì)有限的物理資源。

2.3 基于圖論的拓?fù)浞指畈襟E

針對(duì)網(wǎng)絡(luò)仿真實(shí)驗(yàn)實(shí)驗(yàn)環(huán)境的實(shí)際需求，我們首先針對(duì)通信資源梳理了網(wǎng)絡(luò)拓?fù)浞指罴夹g(shù)所要解決的具體問(wèn)題，然后基于圖論進(jìn)一步提出了包括拓?fù)鋲嚎s、初始劃分和拓?fù)浠謴?fù)等多個(gè)步驟在內(nèi)的拓?fù)浞指罘椒ǎ跐M足各物理節(jié)點(diǎn)負(fù)載均衡和物理主機(jī)間網(wǎng)絡(luò)通信量最小的前提下，將各個(gè)網(wǎng)絡(luò)子域映射到不同的物理主機(jī)上，從而得到虛擬拓?fù)渑c真實(shí)硬件間合理的分布式部署方案，從而實(shí)現(xiàn)了仿真網(wǎng)絡(luò)與物理資源間的合理映射。整體實(shí)現(xiàn)思路如圖2所示。

圖2 網(wǎng)絡(luò)拓?fù)溆成浼夹g(shù)實(shí)現(xiàn)思路

作為實(shí)現(xiàn)網(wǎng)絡(luò)虛擬資源映射問(wèn)題的關(guān)鍵技術(shù)，本文提出了一種基于圖論的拓?fù)浞指罘椒ǎ摲椒ㄍㄟ^(guò)拓?fù)鋲嚎s、初始劃分和拓?fù)浠謴?fù)3個(gè)步驟實(shí)現(xiàn)虛擬資源的分割。其中，拓?fù)鋲嚎s是預(yù)處理部分，主要是通過(guò)合并圖形元素來(lái)簡(jiǎn)化圖結(jié)構(gòu)、減少圖的復(fù)雜度，為拓?fù)浞指畹倪M(jìn)行創(chuàng)造條件；初始劃分是在將網(wǎng)絡(luò)拓?fù)鋱D壓縮到一定程度之后，對(duì)其進(jìn)行初次劃分，按照實(shí)驗(yàn)所需劃分成數(shù)量不等的子圖；而拓?fù)浠謴?fù)則是按照逆向壓縮次序，一層一層將拓?fù)浠謴?fù)成原狀，并在恢復(fù)過(guò)程中進(jìn)行逐次優(yōu)化，對(duì)每一層展開(kāi)圖的分割線附近的點(diǎn)或整個(gè)圖中的點(diǎn)進(jìn)行適當(dāng)調(diào)整，保證劃分的子圖間鏈路數(shù)量最少，以獲得更優(yōu)的分割結(jié)果?；趫D論的拓?fù)浞指罘椒ň唧w實(shí)現(xiàn)步驟如圖3所示。

圖3 拓?fù)浞指罘椒▽?shí)現(xiàn)步驟

步驟1 拓?fù)鋲嚎s：該步驟是對(duì)原始拓?fù)溥M(jìn)行多次壓縮，得到一個(gè)高度簡(jiǎn)化的、僅有少量反映原始拓?fù)湔w結(jié)構(gòu)的頂點(diǎn)和鏈路信息的拓?fù)鋱D。針對(duì)圖G＝ （V，E），其基本壓縮過(guò)程如下。

（1）設(shè)S為匹配頂點(diǎn)集合，初始值為空；T 為剩余頂點(diǎn)集合，初始值為全部節(jié)點(diǎn)V；M 為不可再繼續(xù)匹配頂點(diǎn)集合，初始值為空；

（2）在T 中隨機(jī)選擇一個(gè)頂點(diǎn)，記為Vi，然后在T 中查找并記錄所有與Vi相鄰的頂點(diǎn)的邊權(quán)，其中邊權(quán)最大的頂點(diǎn)，記為Vj，則頂點(diǎn)Vi、Vj均被置入集合S，并繼續(xù)搜索過(guò)程；若不存在滿足條件的Vj，則將Vi放入M，開(kāi)始（3）；

（3）在T 中隨機(jī)選擇下一個(gè)頂點(diǎn)，返回 （2）；若T 為空，則壓縮結(jié)束，得到Gm＝（Vm，Em）（m＝0，1，2，…）。

由于拓?fù)鋲嚎s會(huì)不斷地循環(huán)進(jìn)行，因此需對(duì)其設(shè)定結(jié)束條件。實(shí)驗(yàn)人員可以通過(guò)配置 “理想節(jié)點(diǎn)數(shù)”或 “壓縮到原圖80%”等方式來(lái)進(jìn)行控制。同時(shí)，需要在臨時(shí)文件中自動(dòng)記錄壓縮過(guò)程，以便恢復(fù)拓?fù)鋾r(shí)使用。

步驟2 初始劃分：在經(jīng)過(guò)拓?fù)鋲嚎s之后，欲劃分的原始拓?fù)鋱D已經(jīng)縮減到一個(gè)足夠小的地步，此時(shí)將進(jìn)行初始劃分操作，以得到原始拓?fù)涞囊粋€(gè)初步分割結(jié)果。

初始劃分操作較為簡(jiǎn)單，其基本思想是隨機(jī)選擇一個(gè)頂點(diǎn)，并將與之相鄰的頂點(diǎn)盡可能的放在一起，形成一個(gè)子域，直至所有鄰接點(diǎn)都在此子域內(nèi)，然后再選一個(gè)并未劃分區(qū)域的頂點(diǎn)，重復(fù)上述過(guò)程，直至將圖Gm＝ （Vm，Em）的頂點(diǎn)集Vm劃分成大致相等的k個(gè)部分。

初始劃分僅是粗粒度的拓?fù)浞指?，主要是用?lái)滿足負(fù)載均衡的目的，還需要通過(guò)下一步拓?fù)浠謴?fù)操作中的結(jié)果優(yōu)化來(lái)調(diào)整拓?fù)渥佑蜷g的分割線，以達(dá)到物理主機(jī)間通信量最小的目標(biāo)。

步驟3 拓?fù)浠謴?fù)：拓?fù)浠謴?fù)分為拓?fù)溥€原和結(jié)果優(yōu)化兩個(gè)過(guò)程。拓?fù)溥€原根據(jù)拓?fù)鋭澐謺r(shí)保存的臨時(shí)信息，將劃分結(jié)果還原為初始規(guī)模的拓?fù)鋱D；結(jié)果優(yōu)化則是在拓?fù)溥€原的基礎(chǔ)上，優(yōu)化調(diào)整初始劃分結(jié)果，從而在負(fù)載均衡的條件下盡可能減少拓?fù)渥佑蜷g的鏈路數(shù)量。結(jié)果優(yōu)化的基本思想是，對(duì)分割線兩端的頂點(diǎn)進(jìn)行互換，如果通過(guò)交換這對(duì)頂點(diǎn)后，能夠減少子域間的鏈路數(shù)目，則調(diào)整分割線的位置，將這對(duì)頂點(diǎn)所屬的區(qū)域?qū)Q。如圖4 所示，通過(guò)將圖中分割線兩側(cè)的黑色節(jié)點(diǎn)進(jìn)行互換，使得網(wǎng)絡(luò)子域間的鏈路數(shù)由6減少到了3。

圖4 結(jié)果優(yōu)化

基于圖論的拓?fù)浞指罘椒w納起來(lái)可分為壓縮、劃分、還原、以及優(yōu)化4個(gè)過(guò)程。壓縮減少原網(wǎng)絡(luò)拓?fù)淠Ｐ偷男畔?；劃分是根?jù)可用的實(shí)驗(yàn)設(shè)備，對(duì)壓縮后的拓?fù)溥M(jìn)行一定數(shù)量上的分割；將分割后的拓?fù)溥€原為初始結(jié)構(gòu)并優(yōu)化連接信息，最終得到的拓?fù)渥佑驅(qū)⒎謩e映射到相應(yīng)的物理主機(jī)上。由于該方法在開(kāi)始階段進(jìn)行了拓?fù)鋲嚎s，所以具備處理大規(guī)模仿真實(shí)驗(yàn)網(wǎng)絡(luò)的能力，能夠獲取到虛擬網(wǎng)絡(luò)與物理資源之間合理的映射關(guān)系，是解決大規(guī)模仿真實(shí)驗(yàn)網(wǎng)絡(luò)映射部署問(wèn)題的有效途徑。

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)驗(yàn)證環(huán)境

采用實(shí)驗(yàn)室構(gòu)建的實(shí)驗(yàn)環(huán)境由管理控制網(wǎng)絡(luò)、實(shí)驗(yàn)網(wǎng)絡(luò)兩部分構(gòu)成，其拓?fù)浣Y(jié)構(gòu)如圖5所示。

圖5 實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)

其中，管理控制網(wǎng)絡(luò)由管理系統(tǒng)和鏡像服務(wù)器通過(guò)交換機(jī)連接構(gòu)成，管理系統(tǒng)負(fù)責(zé)對(duì)實(shí)驗(yàn)環(huán)境所需的軟、硬件資源進(jìn)行統(tǒng)一的監(jiān)控與配置；鏡像服務(wù)器用于存儲(chǔ)實(shí)驗(yàn)環(huán)境需要的各種操作系統(tǒng)鏡像文件。

3.2 拓?fù)浞指罴夹g(shù)驗(yàn)證

為了滿足虛擬網(wǎng)絡(luò)拓?fù)渑c物理硬件資源間的合理映射，本文實(shí)現(xiàn)了拓?fù)浞指罘椒?，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的性能和對(duì)實(shí)驗(yàn)場(chǎng)景網(wǎng)絡(luò)結(jié)構(gòu)劃分的有效支撐作用。

表2給出了將同一拓?fù)浣Y(jié)構(gòu)劃分為不同數(shù)量子域后所得到的統(tǒng)計(jì)結(jié)果。初始拓?fù)浣Y(jié)構(gòu)包含100個(gè)節(jié)點(diǎn)和215條邊，劃分的子域數(shù)量從6依次遞增到10。每個(gè)表項(xiàng)所表達(dá)的意思為該子域包含多少個(gè)節(jié)點(diǎn)和多少條外聯(lián)邊；以序號(hào)10一行中的子域6為例，其表項(xiàng)內(nèi)容為10／6，表示該子域有節(jié)點(diǎn)10個(gè)，與其它9個(gè)子域間的域間鏈路6條。

表2 單拓?fù)涠嘧佑騽澐纸Y(jié)果

由表2可知，經(jīng)拓?fù)浞指詈蟮玫降母髯佑虻挠騼?nèi)節(jié)點(diǎn)數(shù)量基本一致，保證了各子域所映射物理主機(jī)間的負(fù)載均衡。同時(shí)，隨著子域劃分?jǐn)?shù)量的不斷提高，各子域間鏈路的平均值呈現(xiàn)出逐漸減少的趨勢(shì)，相應(yīng)地降低了物理主機(jī)間的通信量。由此可知，本文提出的拓?fù)浞指罘椒梢杂行У刂畏抡鎸?shí)驗(yàn)網(wǎng)絡(luò)的合理映射與部署。

考慮到仿真實(shí)驗(yàn)對(duì)大規(guī)模網(wǎng)絡(luò)仿真以及場(chǎng)景切換所帶來(lái)拓?fù)渲貥?gòu)的快速映射要求，在CPU 為2.3GHz、內(nèi)存為1G 的仿真物理主機(jī)上對(duì)拓?fù)浞指罘椒ǖ男阅苓M(jìn)行了測(cè)試。通過(guò)虛擬網(wǎng)絡(luò)生成模塊得到節(jié)點(diǎn)規(guī)模從1000到10000共10個(gè)拓?fù)浣Y(jié)構(gòu)文件，分別將其劃分成10個(gè)子域，計(jì)算所用時(shí)間，每次計(jì)算10輪取平均值，結(jié)果如圖6所示。

圖6 運(yùn)行時(shí)間隨節(jié)點(diǎn)規(guī)模變化情況

同時(shí)，對(duì)節(jié)點(diǎn)規(guī)模為10000的拓?fù)溥M(jìn)行了多子域劃分，子域數(shù)量從10逐漸遞增到100，分別計(jì)算所用時(shí)間，每次計(jì)算10輪取平均值，結(jié)果如圖7所示。

圖7 運(yùn)行時(shí)間隨子域數(shù)量變化情況

如圖7所示，在一般性能的仿真物理主機(jī)上進(jìn)行拓?fù)浞指?，即使是將?jié)點(diǎn)規(guī)模為10000 的網(wǎng)絡(luò)劃分成100 個(gè)子域，也僅需68.9ms，完全能夠滿足仿真實(shí)驗(yàn)環(huán)境對(duì)快速性的要求。

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

本文提出了一種基于圖論的拓?fù)浞指罘椒ǎㄟ^(guò)拓?fù)鋲嚎s、初始劃分以及拓?fù)浠謴?fù)來(lái)簡(jiǎn)化拓?fù)鋱D結(jié)構(gòu)、對(duì)其進(jìn)行初次劃分，再將拓?fù)浠謴?fù)成原狀，并進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，該方法有效地平衡了各主機(jī)的計(jì)算負(fù)載，減少了主機(jī)間的通信量，更好地將實(shí)驗(yàn)的虛擬資源映射到物理主機(jī)上，在保證實(shí)驗(yàn)規(guī)模的基礎(chǔ)上，降低了物理資源的需求，減少了實(shí)驗(yàn)所需的時(shí)間，能夠有效地解決大規(guī)模仿真實(shí)驗(yàn)網(wǎng)絡(luò)映射部署問(wèn)題。其并未考慮網(wǎng)絡(luò)模型中存在的流量狀況以及真實(shí)網(wǎng)絡(luò)的層次結(jié)構(gòu)等相關(guān)特性，今后將在本文提出的方法的基礎(chǔ)上，作上述處理，并結(jié)合其它啟發(fā)式方法來(lái)完善此拓?fù)浞指罘椒ā?/p>

［1］Bergero Federico，Ernesto Kofman，F(xiàn)rancois Cellier.A novel parallelization technique for DEVS simulation of continuous and hybrid systems［J］.Transactions of the Society for Modeling and Simulation International，2013，89 （11）：1291－1292.

［2］Hibler M，Ricci R，Stoller L，et al.Large－scale virtualization in the Emulab network testbed ［C］／／In Proceedings of the USENIX Annual Technical Conference，2008：113－128.

［3］Chertov R，F(xiàn)ahmy S.Forwarding devices：From measurements to simulation ［J］.ACM Transactions on Modeling and Computer Simulation，2011，21 （2）：1－23.

［4］LI Jin，HUANG Minhuan.Research on large－scale network topology generation ［J］.Computer Engineering ＆ Science，2010，32 （3）：11－13 （in Chinese）.［李津，黃敏桓.大規(guī)模網(wǎng)絡(luò)拓?fù)渖杉夹g(shù)研究 ［J］.計(jì)算機(jī)工程與科學(xué)，2010，32（3）：11－13.］

［5］Yao W，F(xiàn)ahmy S.Downscaling network scenarios with denial of service attacks［C］／／Proc of Sarnoff Symposium，2008.

［6］Walker B，Seastrom J，Lee G，et al.Addressing scalability in a laboratory－based multihop wireless testbed ［J］.Mobile Networks and Applications，2010，15 （3）：435－445.

［7］Gupta D，Vishwanath KV，Mcnett M，et al.DieCast：Testing distributed systems with an accurate scale model ［J］.ACM Transactions on Computer Systems，2011，29 （2）1－15.

［8］Carl G，Kesidis G.Large－scale testing of the Internet’s border gateway protocol via topological scale－down ［J］. ACM Transactions on Modeling and Computer Simulation，2008，18（3）：1－30.

［9］KUANG Xiaohui，HUANG Minhuan.Research on network worm testbed ［J］.Computer Science，2010，37 （7）：54－56（in Chinese）.［況曉輝，黃敏桓.網(wǎng)絡(luò)蠕蟲(chóng)實(shí)驗(yàn)環(huán)境構(gòu)建技術(shù)研究 ［J］.計(jì)算機(jī)科學(xué)，2010，37 （7）：54－56.］

［10］Arjun Roy，Kenneth Yocum，Alex C Snoeren.Challenges in the emulation of large scale software defined networks［C］／／APSYs，ACM，2013.