一種面向大規模網絡仿真的自適應拓撲劃分機制

戴寧赟 邢長友 王海濤 陳 鳴

中國人民解放軍陸軍工程大學 南京 210007

引言

近年來，隨著網絡空間安全技術的發展，網絡空間靶場的建設得到了廣泛關注。網絡空間靶場有助于全面衡量各種信息系統是否安全、安全防御裝備是否管用好用等，對創新和發展網絡空間防御的理論、技術和裝備能力具有重要作用[1-2]。在網絡空間靶場的建設過程中，為了避免對現有網絡和各種業務產生影響，必須要將其獨立于現有網絡環境進行建設。若采用物理設備來構建網絡空間靶場的基礎網絡環境，則存在成本過高、調整維護復雜等問題。在此情況下，構建具有高逼真度的網絡仿真平臺，進而為網絡靶場建設提供基礎網絡環境支持就成為應對上述挑戰的有效手段。

為了反映真實的網絡狀況，網絡仿真平臺需要能夠支持大規模網絡仿真、具有良好的擴展性、對上層業務透明以及仿真結果高保真等。由于保真性差等問題，諸如NS2、OPNET等傳統的網絡模擬方法已經無法滿足需要。近年來，隨著Linux容器(LXC)等輕量級虛擬化技術的發展，建立支持虛實結合功能的輕量級虛擬化網絡仿真平臺得到了廣泛的關注。這些仿真平臺基于虛擬化技術、在通用的硬件平臺上仿真各種網絡設備和網絡鏈路，進而建立大規模的網絡仿真場景。并且，與傳統的模擬工具不同，這些仿真平臺上面運行的業務和協議都是真實的，并可以通過物理接口與平臺外的真實網絡設備(如路由器、交換機、服務器、主機等)實現虛實互聯。

由于網絡仿真的本質是利用物理主機的資源模擬大量虛擬網絡設備工作，隨著網絡規模的增大，所占用的CPU和內存開銷可能成為仿真網絡規模的瓶頸，導致單個物理設備無法實現整個大規模網絡拓撲的仿真，需要通過引入更多的計算資源，把單節點的網絡仿真分布到并行計算環境中，從而提高網絡仿真的規模。然而，分布式仿真所面臨的一個關鍵問題就是如何進行合理的網絡拓撲分割，從而確定將哪些節點部署到哪些服務器上進行仿真。該問題本質上是一個圖的拓撲劃分問題，即對一個大型網絡劃分為幾個子網絡，并部署到不同的物理服務器上。在這樣的分布式仿真模型中，不同服務器之間的負載均衡程度以及服務器之間通信量的規模，均對仿真效率具有重要影響。如何保持服務器之間的負載均衡性，以及降低物理通信量，是提高分布式網絡仿真效率的關鍵。

針對上述問題，本文提出了一種面向大規模網絡仿真的自適應拓撲劃分機制，該機制針對大型網絡拓撲，首先根據物理服務器的資源約束估算所需仿真物理機的數目，隨后根據估算結果進行自適應的拓撲劃分，最后根據劃分結果實現分布式的大規模網絡仿真。

1 相關工作

網絡仿真本質上是在一個受控的環境中構建實驗平臺，為進行協議測試、應用性能測試等提供基礎環境。相對于NS2等網絡模擬技術，網絡仿真具有保真度高、支持虛實互聯等優勢，近年來得到了廣泛關注。尤其是隨著網絡靶場等技術的推進，大規模網絡的高逼真仿真成為近年來的一個研究熱點。目前典型的網絡仿真工具包括CORE[3]、IMUNES[4]、Mininet[5]等，它們均是利用虛擬化技術，在一臺或者多臺物理主機上仿真出具有多個節點的網絡場景，因此仿真規模取決于物理承載主機的性能約束。

為了支持大規模的網絡仿真，消除單臺主機的性能約束，近年來大規模網絡的拓撲分解問題得到了廣泛的關注。由于大規模網絡拓撲結構的復雜性，求解拓撲分割最優解屬于NP難問題。當前，并行網絡拓撲的劃分方法一般利用圖論中的算法，采用成熟的圖劃分工具實現，即將所要模擬的網絡轉化成帶有點權值和邊權值的拓撲圖，然后采用圖劃分工具(如METIS[6])進行劃分。針對不同的應用，以及該算法本身的不足，國內外對該算法的研究主要分為兩個方向：算法的應用和算法的改進。文獻[7]將拓撲劃分問題應用于電路劃分問題當中，基于METIS圖劃分算法，提出了改進的多權值約束的劃分算法。在劃分前對多權值進行融合，并在劃分后評估劃分效果以改進融合參數，提高各個部分的平衡度。文獻[8]通過分析影響并行網絡仿真性能的因素，對METIS進行改進，實現了并行網絡模擬拓撲的優化劃分方法。文獻[9]針對METIS算法的還原過程進行優化，以提升網絡模擬拓撲劃分的有效性。

然而這些方法并沒有解決METIS劃分時需要提前指定劃分數目的不足，同時也沒有考慮模擬節點的承載能力限制。因此本文提出了一種面向模擬節點物理性能約束的自適應劃分模型，可以根據模擬節點的性能約束估算出仿真整個拓撲所需的模擬節點數目，并得到劃分結果。

2 面向主機性能約束的自適應拓撲劃分模型

2.1 虛擬化網絡仿真平臺體系結構模型

圖1給出了虛擬化網絡仿真平臺的基本體系結構模型，包括兩大部分：虛擬化平臺功能和定制虛擬化網絡功能組件。其中虛擬化平臺功能包括虛擬化硬件平臺、虛擬化軟件平臺、虛擬機和網絡功能軟件等部分；定制虛擬化網絡組件需要運行在虛擬化平臺功能組件之上，包括虛擬化網絡性能組件、虛擬化終端設備、虛擬化路由組件、以及虛擬交換機組件等。其中虛擬化網絡性能組件主要利用NetEm等工具，模擬各種網絡鏈路，虛擬化終端設備則基于LXC技術構建各種主機、服務器等終端，虛擬化路由組件則基于LXC技術和Quagga來構建能夠運行各種路由協議的虛擬化路由器，虛擬交換機組件則直接基于Linux Bridge等技術構建虛擬交換機，并用于互聯不同的網絡設備。

圖1 虛擬化網絡仿真平臺體系結構模型

在各種虛擬化網絡仿真平臺中，通用開放網絡仿真器CORE是非常有代表性的一種[10]。CORE采用了LXC虛擬化技術，可以在虛擬化容器中運行Quagga等各種應用程序，從而將其配置為路由器、交換機、服務器等各種相應的虛擬化組件。這里各個虛擬化節點之上所運行的協議均為真實的網絡協議，可以確保仿真系統的高保真度。

由于CORE中每個網絡資源都對應一個或一組虛擬化容器，隨著網絡規模的增大，所占用的CPU和內存開銷可能成為仿真網絡規模的瓶頸。其次，CORE采用內存交換的方式仿真分組在不同節點間的傳輸，隨著仿真流量規模的增大，必然會導致數據交換速率無法滿足仿真網絡帶寬要求的情況。在這種情況下，單個物理設備無法實現整個大規模網絡拓撲的仿真，需要通過引入更多的計算資源，把單節點的網絡仿真分布到并行計算環境中，從而提高網絡仿真的規模。

事實上，很多網絡仿真平臺都提供了搭建大規模網絡的功能，但對于分布式部署方案并未涉及。如何合理利用METIS劃分算法，實現對大規模網絡的合理劃分，是需要解決的問題。不同于傳統的拓撲劃分，網絡的分布式部署受到物理主機性能、拓撲規模、物理主機之間連通性等多種因素的制約。同時，采用多少臺物理主機進行搭建，可以達到實現較好仿真效果的同時，節約主機資源，是我們在進行拓撲劃分之前需要考慮的問題。因此本文根據物理主機性能，提出了一種自適應的網絡拓撲劃分模型，該模型根據物理主機的資源對網絡拓撲進行劃分數目的估算，獲得較為合理的劃分方案。

2.2 自適應網絡拓撲劃分模型

如前所述，分布式仿真的關鍵在于確定哪些仿真節點應當運行在哪些物理仿真服務器上，其本質為網絡拓撲劃分問題。在網絡仿真實驗場景的構建中，拓撲劃分需要保證物理服務器間的負載均衡和跨區域通信量最小化兩個基本目標。前者保證每臺物理主機不能承擔過多的運算任務，也要確保仿真物理環境中所有的運算資源都能得到充分利用。后者盡量降低跨服務器的通信量，以盡可能減少使用有限的物理通信設施。

假設需將一個規模為m的網絡拓撲圖G(N，E)劃分為n個子網，分別對應模擬節點1,2,...,n。如上節所述，點權wi表示節點的權重，邊權uj表示鏈路的權重。令表示兩個不同的劃分和之間切邊之和，代表兩個仿真節點之間的總流量。

因此，第j個劃分中節點的總權重則為

為了滿足劃分后各個塊之間的負載均衡性、以及不同塊之間通信量最小化的原則，我們可以將優化目標表示如下。

其中，存在的約束為

公式(1)表示最小化不同劃分塊之間的通信量，公式(2)表示最小化不同物理仿真主機的歸一化負載偏差情況，即盡可能按照各個物理仿真主機的承載能力進行仿真拓撲的劃分。約束條件中，公式(3)表示每臺物理仿真主機所分配的負載應當小于其承載能力，公式(4)表示不同劃分塊之間的通信量需要小于物理主機之間相應的帶寬約束，公式(5)表示每個節點只能夠被分配到1個塊中。

上述問題是一個NP完全問題，無法在多項式時間內進行準確求解。目前，圍繞圖劃分問題有多種求解工具，其中METIS是一種功能強大的圖劃分工具，但必須在進行劃分之前指定需要將該拓撲劃分為多少個部分，無法根據待劃分的網絡拓撲進行動態預估。在實際仿真過程中，由于物理設備具有一定的容量限制，難以預先指明將其劃分為多少個部分，若劃分塊數偏小，則可能超出物理設備承載能力范圍；偏大，則不能有效利用設備資源，造成資源浪費。針對上述問題，我們在METIS拓撲劃分的基礎上，結合物理仿真主機的性能約束提出了一種面向主機性能約束的自適應拓撲劃分模型，通過“預估—劃分—調整”動態迭代的方式確定大規模仿真網絡拓撲的最優劃分方案。

在仿真規模預估階段，其主要目標就是在進行拓撲劃分之前，根據網絡仿真需求和物理主機性能約束下判斷需要將網絡拓撲劃分為多少塊，以便為后面的劃分提供基礎。該過程包括權重分配和規模預估兩個階段。

在權重分配階段，首先將網絡拓撲抽象為一個帶有權值的圖G。每個節點代表網絡設備，邊e則代表鏈路，其中點權wi代表節點vi的權重，邊權uj表示鏈路ej的權重，并根據物理主機的性能狀況設置每臺主機的容量C1,C2,C3…。

其次，計算拓撲圖中的點權值和邊權值。如前所述，保真性是進行網絡仿真的一個主要指標，為了滿足這一指標的要求，就必須要保證每個仿真節點和每條仿真鏈路均能夠按照設置的速率進行數據轉發，即滿足各條仿真鏈路的帶寬要求。我們以鏈路帶寬代表其權重，而在計算節點的權重時，采用與該節點相連接的鏈路帶寬之和代表節點的權重，即

完成網絡拓撲中節點和鏈路的權重分配之后，我們結合物理主機的性能約束，實現仿真規模的預估，算法1給出了基本過程。

算法1：仿真規模預估機制

輸入：原始網絡拓撲G(V, E)，鏈路權重ui，物理主機容量Ci

輸出：劃分子圖數目k

1：根據仿真拓撲計算各個節點的權重，

2：k=1

9：label cand as visited

10：if there exists an unvisited node vj in vi's neighbor

11：cand=vj

12：else

13：vi=an random neighbor ofvi

14：cand= NULL

15：end if

16：end while

17：if there exists unvisited nodes in N

18：k=k+1

19：goto 3

20：end if

21：return k

在算法1中，第1～2行首先根據所連接的鏈路情況計算各個節點的權重，并設置初始劃分數目為1。隨后第3～5行初始化擬劃分的子圖，并從原始拓撲中選擇一個未被標記的節點vi作為初始備選節點。在第6～16行中，當子圖Pk的總權重未超過物理主機的容量Ck時，采用廣度優先的機制不斷向子圖Pk中增加節點，直至總權重超過閾值Ck，則完成本子圖的構造。在17～21行中，若原始拓撲N中還有未劃分的節點，則開始生成新的子塊，否則返回當前所預估的劃分結果。

完成仿真規模預估之后，即可在現有拓撲劃分工具METIS的基礎上進行細粒度的拓撲劃分。在這一過程中，為了保證劃分結果符合物理仿真主機的性能約束，我們在現有METIS拓撲劃分的基礎上，進一步實現了性能約束的拓撲劃分機制，避免為某些主機分配的仿真節點權重超過其處理能力。

3 性能評估

在實驗測試中，本文利用拓撲生成器BRITE按照Waxman模型部署網絡節點，按指數分布設置鏈路帶寬，范圍為10～1024，節點位置服從重尾分布。通過設置節點個數，生成18種不同規模的網絡拓撲。

本文將拓撲生成器獲得的拓撲數據，作為改進后METIS的劃分對象。假設每臺物理仿真主機的容量均為C=20000，首先進行預估操作，按照承載能力限制計算出該網絡拓撲需要的物理仿真主機數量，然后根據預估得到的結果，對拓撲圖進行物理仿真主機性能約束下的劃分。

在實驗中，利用本文所提出的機制對多種規模的網絡拓撲進行測試，并利用權重均值和權重變異系數兩個典型參數對劃分結果進行分析對比。其中權重均值代表各個劃分塊中平均負載情況，若則表明本次劃分結果符合實際的物理資源約束。權重變異系數表示權重值的標準差與期望之間的比值，若與分別表示劃分結果中各個子塊的標準差與期望，則

圖2 劃分子塊的權重均值

圖3 劃分子塊的權重變異系數

圖2表明對于不同規模的網絡拓撲，劃分結果中權重均值都小于物理仿真主機的容量限制，表明了劃分結果的有效性。圖3計算了不同劃分塊之間權重值的變異系數。由實驗結果可以發現，該值在0.1處波動，表明不同子塊之間的權重具有很好的負載均衡特性。

進一步，為驗證本文提出的劃分模型對資源利用的高效性，我們進一步將擬劃分的子塊數目降低1，判斷在這種情況下的劃分結果是否還能夠滿足物理主機性能約束，圖4與圖5描述了相應的劃分結果，其中計算值代表本文算法所得到的劃分結果，而對比值則為將本文劃分子塊數目減小1之后得到的結果。

圖4 劃分子塊的權重均值

由圖4可以看出，將拓撲劃分的子塊數目減小1時，劃分子塊的權重均值顯著增加，同時會頻繁越過物理仿真主機的承載能力，使得劃分結果無法應用到實際的物理仿真環境中。因此，實驗結果證明了本模型所得到的結果已經難以再進行進一步優化。在圖5中，當拓撲規模超1000時，對比值的測量數據中劃分子塊的權重變異系數明顯高于通過模型獲得的計算值。綜上，通過本文提出的劃分模型，可以得到一個滿足物理性能約束，且均衡度較好的劃分結果。

圖5 劃分子塊的權重變異系數

4 結束語

隨著網絡安全形勢日益嚴峻，網絡空間靶場等建設任務不斷推進，對大規模網絡仿真的需求越來越迫切。如何合理地將大規模網絡的仿真在多臺主機上部署，成為影響仿真效率的關鍵因素。針對這一問題，本文重點研究了在主機性能受限情況下的大規模網絡分布式仿真的問題。首先，對一種典型的虛擬化網絡仿真平臺CORE進行了性能測量，總結了其仿真規模瓶頸及影響仿真性能的主要因素。隨后，提出了基于物理仿真主機性能約束的自適應拓撲劃分模型，并在典型拓撲劃分工具METIS的基礎上實現了相應的劃分算法。該算法通過仿真規模預估和拓撲劃分調整兩個步驟，首先根據所需仿真的網絡拓撲規模和實際物理主機資源約束估算出所需的物理主機數目，即需要劃分的子塊數目。隨后，據此根據物理主機性能約束進行拓撲的劃分和調整。實驗測試結果表明該機制能夠有效針對大規模網絡的仿真需求進行拓撲劃分，并保證劃分結果滿足物理主機性能約束和子塊間負載均衡等目標。在下一步的工作中，我們將依據劃分結果，利用CORE平臺建立分布式的仿真環境，并在其上部署仿真系統對其性能做進一步的測試分析，以便優化仿真模型。