大規(guī)模網絡的拓撲分割技術

郭艷來，崔益民，唐 洪，李 津

（北京系統(tǒng)工程研究所 信息系統(tǒng)安全技術重點實驗室，北京100101）

0 引 言

現如今，越來越多的方法被應用于減少硬件資源消耗，以高效準確地進行大規(guī)模網絡安全實驗：分布式計算和資源復用可以應用于模擬和仿真實驗［1］，以較少的物理資源來保證實驗的規(guī)模，例如離散事件模擬器［1，3］，生成的時間可以分布于多臺機器上來減少實驗時間以及對每臺機器的硬件資源的需求；仿真平臺以及測試床可以通過將虛擬資源映射到可用的物理資源來保證實驗規(guī)模，例如Emulab可以支持20倍于自身測試床的實驗規(guī)模［2］，但這種映射是一個NP難問題［3］，主要的難點在于物理資源過載導致實驗得不到準確可信的實驗結果。拓撲分割可以擴展網絡安全實驗規(guī)模，基于模擬退火算法的拓撲分割技術被應用于實驗的資源自動映射問題［4］。

解決此問題的另外一種思路是拓撲約簡［5］，即在保留原有拓撲圖主要特性的同時，采取減少不擁塞鏈路和流量抽樣［6］的方法減小實驗網絡的規(guī)模［7，8］。這類方法避免了拓撲分割這個NP難問題，但是由于不能完整地保留原網絡拓撲的特性，實驗結果的精確度不能保證，且實現起來有一定的難度。

本文提出了一種基于圖論的拓撲分割技術，來實現實驗資源動態(tài)均衡的動態(tài)映射，這種方法有效地降低了物理主機間的通信量，平衡了個物理主機的計算量，可以有效地支撐仿真實驗網絡的合理映射與部署。

1 拓撲分割問題描述

為了滿足網絡仿真實驗環(huán)境建設目標，需要構造大規(guī)模拓撲結構以仿真實際條件下的網絡場景［9］。通過研究拓撲分割技術，將生成的虛擬網絡映射到真實的實驗資源上，能夠為目標拓撲制定合理的映射方案，從而將欲仿真的實驗網絡分散部署到不同的物理主機上，將不便仿真的特殊設備映射到實物裝備上，以確保實驗場景能夠更加均衡地利用相對有限的物理資源。

在網絡仿真實驗中，由于服務及應用資源構建于計算資源之上，計算資源需要承擔高密度的計算任務。因此在實驗運行中，實驗任務通常要求計算資源能夠依據系統(tǒng)中計算節(jié)點的組成以及能力需求，動態(tài)分配并部署節(jié)點所需資源，包括處理器性能、內存空間、硬盤容量、I／O 類型、網絡接口等。在網絡仿真實驗場景構建的過程中，解決虛擬資源映射的網絡拓撲分割技術在實現后，需要保證虛擬資源裝載的動態(tài)均衡和最小化物理主機間的通信量［10］。

（1）負載均衡：仿真實驗網絡要均衡地部署于不同的物理主機。既要保證某臺機器不能承擔過多的運算任務，也要確保仿真物理環(huán)境中的所有運算資源都能得到充分利用。

（2）物理主機間通信量：要在負載均衡基礎上保證物理主機間通信量最小。分割部署在不同物理主機上的網絡間要進行交互通信，這就有了通信開銷。同時，單臺物理主機所能對外提供的網絡接口資源也是有限的。通過減少拓撲分割結果中分布于不同物理主機上的網絡子域之間的鏈路數，可以較好地解決這一問題。

針對仿真實驗環(huán)境中的計算資源分配問題，通過各計算基礎設施的節(jié)點之間的資源動態(tài)調度和協(xié)同操作來實現計算基礎設施的負載均衡，提高物理資源利用率，降低管理的復雜度，構建高效的資源分配策略和機制。多機環(huán)境計算基礎設施資源分配，采用的仿真計算資源重構模型如圖1所示。

圖1 多機環(huán)境下的仿真計算資源重構模型

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

2 基于圖論的拓撲分割

在進行大規(guī)模網絡仿真實驗時，根據實驗需求生成各種拓撲結構的實驗環(huán)境，首先需要解決實驗環(huán)境的拓撲結構中相關概念的定義。

2.1 虛擬網絡拓撲相關定義

針對網絡化信息系統(tǒng)，虛擬網絡拓撲描述用來表現網絡中的路由節(jié)點和端系統(tǒng)，以及它們之間的互聯(lián)關系。

在網絡拓撲研究中，一般的拓撲結構通?？梢杂脽o向圖來描述。無向圖定義如下：圖G＝ （V，E），其中V＝｛v｜v是G 中的節(jié)點｝，E＝｛（u，v）｜u∈V，v∈V 且u和v相鄰接｝，節(jié)點出度dv＝｜｛u｜（u，v）∈E｝｜；出度頻率fd＝｜｛v｜v∈V 且dv∈d｝｜。

無向圖G＝ （V，E），如果節(jié)點集V 代表路由器節(jié)點，邊集E代表路由器間物理連接鏈路，則稱之為路由器級網絡拓撲圖；如果節(jié)點集V 代表自治域節(jié)點，邊集E 代表自治域間物理連接鏈路，那么稱之為自治域級網絡拓撲圖。

用于刻畫用戶需求的虛擬網絡拓撲結構指實驗人員希望利用大規(guī)模網絡仿真實驗環(huán)境構造的網絡拓撲結構。該結構不但包括路由器級網絡拓撲，還包含端系統(tǒng)以及各類型節(jié)點和鏈路的屬性?；跓o向圖的定義，給出虛擬網絡拓撲結構定義：

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

2.2 物理網絡拓撲

實驗環(huán)境的物理拓撲結構可用無向圖G＝ （V，E）表示，其中V＝ ｛v｜v是G 中的節(jié)點｝，表示網絡中節(jié)點的集合，包括核心交換機S、仿真節(jié)點E以及真實網絡設備R這3種類型。各類型節(jié)點的屬性見表1。

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

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

為了滿足網絡安全實驗環(huán)境建設目標，需要構造大規(guī)模拓撲結構以仿真實際條件下的網絡運行場景。通過研究實驗資源的拓撲映射技術，能夠為目標拓撲制定合理的映射方案，從而將欲仿真的實驗網絡分散部署到不同的物理主機上，將不便仿真的特殊設備映射到實物裝備上，以確保實驗場景能夠更加均衡地利用相對有限的物理資源。

2.3 基于圖論的拓撲分割步驟

針對網絡仿真實驗實驗環(huán)境的實際需求，我們首先針對通信資源梳理了網絡拓撲分割技術所要解決的具體問題，然后基于圖論進一步提出了包括拓撲壓縮、初始劃分和拓撲恢復等多個步驟在內的拓撲分割方法，在滿足各物理節(jié)點負載均衡和物理主機間網絡通信量最小的前提下，將各個網絡子域映射到不同的物理主機上，從而得到虛擬拓撲與真實硬件間合理的分布式部署方案，從而實現了仿真網絡與物理資源間的合理映射。整體實現思路如圖2所示。

圖2 網絡拓撲映射技術實現思路

作為實現網絡虛擬資源映射問題的關鍵技術，本文提出了一種基于圖論的拓撲分割方法，該方法通過拓撲壓縮、初始劃分和拓撲恢復3個步驟實現虛擬資源的分割。其中，拓撲壓縮是預處理部分，主要是通過合并圖形元素來簡化圖結構、減少圖的復雜度，為拓撲分割的進行創(chuàng)造條件；初始劃分是在將網絡拓撲圖壓縮到一定程度之后，對其進行初次劃分，按照實驗所需劃分成數量不等的子圖；而拓撲恢復則是按照逆向壓縮次序，一層一層將拓撲恢復成原狀，并在恢復過程中進行逐次優(yōu)化，對每一層展開圖的分割線附近的點或整個圖中的點進行適當調整，保證劃分的子圖間鏈路數量最少，以獲得更優(yōu)的分割結果?；趫D論的拓撲分割方法具體實現步驟如圖3所示。

圖3 拓撲分割方法實現步驟

步驟1 拓撲壓縮：該步驟是對原始拓撲進行多次壓縮，得到一個高度簡化的、僅有少量反映原始拓撲整體結構的頂點和鏈路信息的拓撲圖。針對圖G＝ （V，E），其基本壓縮過程如下。

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

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

（3）在T 中隨機選擇下一個頂點，返回 （2）；若T 為空，則壓縮結束，得到Gm＝（Vm，Em）（m＝0，1，2，…）。

由于拓撲壓縮會不斷地循環(huán)進行，因此需對其設定結束條件。實驗人員可以通過配置 “理想節(jié)點數”或 “壓縮到原圖80%”等方式來進行控制。同時，需要在臨時文件中自動記錄壓縮過程，以便恢復拓撲時使用。

步驟2 初始劃分：在經過拓撲壓縮之后，欲劃分的原始拓撲圖已經縮減到一個足夠小的地步，此時將進行初始劃分操作，以得到原始拓撲的一個初步分割結果。

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

初始劃分僅是粗粒度的拓撲分割，主要是用來滿足負載均衡的目的，還需要通過下一步拓撲恢復操作中的結果優(yōu)化來調整拓撲子域間的分割線，以達到物理主機間通信量最小的目標。

步驟3 拓撲恢復：拓撲恢復分為拓撲還原和結果優(yōu)化兩個過程。拓撲還原根據拓撲劃分時保存的臨時信息，將劃分結果還原為初始規(guī)模的拓撲圖；結果優(yōu)化則是在拓撲還原的基礎上，優(yōu)化調整初始劃分結果，從而在負載均衡的條件下盡可能減少拓撲子域間的鏈路數量。結果優(yōu)化的基本思想是，對分割線兩端的頂點進行互換，如果通過交換這對頂點后，能夠減少子域間的鏈路數目，則調整分割線的位置，將這對頂點所屬的區(qū)域對換。如圖4 所示，通過將圖中分割線兩側的黑色節(jié)點進行互換，使得網絡子域間的鏈路數由6減少到了3。

圖4 結果優(yōu)化

基于圖論的拓撲分割方法歸納起來可分為壓縮、劃分、還原、以及優(yōu)化4個過程。壓縮減少原網絡拓撲模型的信息；劃分是根據可用的實驗設備，對壓縮后的拓撲進行一定數量上的分割；將分割后的拓撲還原為初始結構并優(yōu)化連接信息，最終得到的拓撲子域將分別映射到相應的物理主機上。由于該方法在開始階段進行了拓撲壓縮，所以具備處理大規(guī)模仿真實驗網絡的能力，能夠獲取到虛擬網絡與物理資源之間合理的映射關系，是解決大規(guī)模仿真實驗網絡映射部署問題的有效途徑。

3 實驗評估

3.1 實驗驗證環(huán)境

采用實驗室構建的實驗環(huán)境由管理控制網絡、實驗網絡兩部分構成，其拓撲結構如圖5所示。

圖5 實驗環(huán)境拓撲結構

其中，管理控制網絡由管理系統(tǒng)和鏡像服務器通過交換機連接構成，管理系統(tǒng)負責對實驗環(huán)境所需的軟、硬件資源進行統(tǒng)一的監(jiān)控與配置；鏡像服務器用于存儲實驗環(huán)境需要的各種操作系統(tǒng)鏡像文件。

3.2 拓撲分割技術驗證

為了滿足虛擬網絡拓撲與物理硬件資源間的合理映射，本文實現了拓撲分割方法，并通過實驗驗證了算法的性能和對實驗場景網絡結構劃分的有效支撐作用。

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

表2 單拓撲多子域劃分結果

由表2可知，經拓撲分割后得到的各子域的域內節(jié)點數量基本一致，保證了各子域所映射物理主機間的負載均衡。同時，隨著子域劃分數量的不斷提高，各子域間鏈路的平均值呈現出逐漸減少的趨勢，相應地降低了物理主機間的通信量。由此可知，本文提出的拓撲分割方法可以有效地支撐仿真實驗網絡的合理映射與部署。

考慮到仿真實驗對大規(guī)模網絡仿真以及場景切換所帶來拓撲重構的快速映射要求，在CPU 為2.3GHz、內存為1G 的仿真物理主機上對拓撲分割方法的性能進行了測試。通過虛擬網絡生成模塊得到節(jié)點規(guī)模從1000到10000共10個拓撲結構文件，分別將其劃分成10個子域，計算所用時間，每次計算10輪取平均值，結果如圖6所示。

圖6 運行時間隨節(jié)點規(guī)模變化情況

同時，對節(jié)點規(guī)模為10000的拓撲進行了多子域劃分，子域數量從10逐漸遞增到100，分別計算所用時間，每次計算10輪取平均值，結果如圖7所示。

圖7 運行時間隨子域數量變化情況

如圖7所示，在一般性能的仿真物理主機上進行拓撲分割，即使是將節(jié)點規(guī)模為10000 的網絡劃分成100 個子域，也僅需68.9ms，完全能夠滿足仿真實驗環(huán)境對快速性的要求。

4 結束語

本文提出了一種基于圖論的拓撲分割方法，通過拓撲壓縮、初始劃分以及拓撲恢復來簡化拓撲圖結構、對其進行初次劃分，再將拓撲恢復成原狀，并進行優(yōu)化。實驗結果表明，該方法有效地平衡了各主機的計算負載，減少了主機間的通信量，更好地將實驗的虛擬資源映射到物理主機上，在保證實驗規(guī)模的基礎上，降低了物理資源的需求，減少了實驗所需的時間，能夠有效地解決大規(guī)模仿真實驗網絡映射部署問題。其并未考慮網絡模型中存在的流量狀況以及真實網絡的層次結構等相關特性，今后將在本文提出的方法的基礎上，作上述處理，并結合其它啟發(fā)式方法來完善此拓撲分割方法。

［1］Bergero Federico，Ernesto Kofman，Francois 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，Fahmy 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ī)模網絡拓撲生成技術研究 ［J］.計算機工程與科學，2010，32（3）：11－13.］

［5］Yao W，Fahmy 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）.［況曉輝，黃敏桓.網絡蠕蟲實驗環(huán)境構建技術研究 ［J］.計算機科學，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.