一种面向大规模网络仿真的自适应拓扑划分机制

戴宁赟 邢长友 王海涛 陈 鸣

中国人民解放军陆军工程大学 南京 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平台建立分布式的仿真环境，并在其上部署仿真系统对其性能做进一步的测试分析，以便优化仿真模型。