大规模网络的拓扑分割技术

郭艳来，崔益民，唐 洪，李 津

（北京系统工程研究所 信息系统安全技术重点实验室，北京100101）

0 引 言

现如今，越来越多的方法被应用于减少硬件资源消耗，以高效准确地进行大规模网络安全实验：分布式计算和资源复用可以应用于模拟和仿真实验［1］，以较少的物理资源来保证实验的规模，例如离散事件模拟器［1，3］，生成的时间可以分布于多台机器上来减少实验时间以及对每台机器的硬件资源的需求；仿真平台以及测试床可以通过将虚拟资源映射到可用的物理资源来保证实验规模，例如Emulab可以支持20倍于自身测试床的实验规模［2］，但这种映射是一个NP难问题［3］，主要的难点在于物理资源过载导致实验得不到准确可信的实验结果。拓扑分割可以扩展网络安全实验规模，基于模拟退火算法的拓扑分割技术被应用于实验的资源自动映射问题［4］。

解决此问题的另外一种思路是拓扑约简［5］，即在保留原有拓扑图主要特性的同时，采取减少不拥塞链路和流量抽样［6］的方法减小实验网络的规模［7，8］。这类方法避免了拓扑分割这个NP难问题，但是由于不能完整地保留原网络拓扑的特性，实验结果的精确度不能保证，且实现起来有一定的难度。

本文提出了一种基于图论的拓扑分割技术，来实现实验资源动态均衡的动态映射，这种方法有效地降低了物理主机间的通信量，平衡了个物理主机的计算量，可以有效地支撑仿真实验网络的合理映射与部署。

1 拓扑分割问题描述

为了满足网络仿真实验环境建设目标，需要构造大规模拓扑结构以仿真实际条件下的网络场景［9］。通过研究拓扑分割技术，将生成的虚拟网络映射到真实的实验资源上，能够为目标拓扑制定合理的映射方案，从而将欲仿真的实验网络分散部署到不同的物理主机上，将不便仿真的特殊设备映射到实物装备上，以确保实验场景能够更加均衡地利用相对有限的物理资源。

在网络仿真实验中，由于服务及应用资源构建于计算资源之上，计算资源需要承担高密度的计算任务。因此在实验运行中，实验任务通常要求计算资源能够依据系统中计算节点的组成以及能力需求，动态分配并部署节点所需资源，包括处理器性能、内存空间、硬盘容量、I／O 类型、网络接口等。在网络仿真实验场景构建的过程中，解决虚拟资源映射的网络拓扑分割技术在实现后，需要保证虚拟资源装载的动态均衡和最小化物理主机间的通信量［10］。

（1）负载均衡：仿真实验网络要均衡地部署于不同的物理主机。既要保证某台机器不能承担过多的运算任务，也要确保仿真物理环境中的所有运算资源都能得到充分利用。

（2）物理主机间通信量：要在负载均衡基础上保证物理主机间通信量最小。分割部署在不同物理主机上的网络间要进行交互通信，这就有了通信开销。同时，单台物理主机所能对外提供的网络接口资源也是有限的。通过减少拓扑分割结果中分布于不同物理主机上的网络子域之间的链路数，可以较好地解决这一问题。

针对仿真实验环境中的计算资源分配问题，通过各计算基础设施的节点之间的资源动态调度和协同操作来实现计算基础设施的负载均衡，提高物理资源利用率，降低管理的复杂度，构建高效的资源分配策略和机制。多机环境计算基础设施资源分配，采用的仿真计算资源重构模型如图1所示。

图1 多机环境下的仿真计算资源重构模型

其过程可分成两个阶段进行，根据实现目标的不同，两个阶段所采取的策略和规则以及操作也都不同。首先确定需要迁移的仿真节点，主要目的是对各仿真节点的计算能力进行监控，以及各仿真节点的宿主平台的仿真能力进行计算；然后对需要进行迁移的仿真节点进行全局的统筹，解决仿真节点迁移目的地的问题，确定迁移方案，实现各宿主平台的计算资源二次分配，实现负载平衡。

2 基于图论的拓扑分割

在进行大规模网络仿真实验时，根据实验需求生成各种拓扑结构的实验环境，首先需要解决实验环境的拓扑结构中相关概念的定义。

2.1 虚拟网络拓扑相关定义

针对网络化信息系统，虚拟网络拓扑描述用来表现网络中的路由节点和端系统，以及它们之间的互联关系。

在网络拓扑研究中，一般的拓扑结构通常可以用无向图来描述。无向图定义如下：图G＝ （V，E），其中V＝｛v｜v是G 中的节点｝，E＝｛（u，v）｜u∈V，v∈V 且u和v相邻接｝，节点出度dv＝｜｛u｜（u，v）∈E｝｜；出度频率fd＝｜｛v｜v∈V 且dv∈d｝｜。

无向图G＝ （V，E），如果节点集V 代表路由器节点，边集E代表路由器间物理连接链路，则称之为路由器级网络拓扑图；如果节点集V 代表自治域节点，边集E 代表自治域间物理连接链路，那么称之为自治域级网络拓扑图。

用于刻画用户需求的虚拟网络拓扑结构指实验人员希望利用大规模网络仿真实验环境构造的网络拓扑结构。该结构不但包括路由器级网络拓扑，还包含端系统以及各类型节点和链路的属性。基于无向图的定义，给出虚拟网络拓扑结构定义：

定义虚拟网络拓扑结构用无向图GV＝ （V，E）表示，其中V＝ ｛v｜v是G 中的一个节点｝表示网络中的节点，类型包括路由器、交换机以及端系统等；E＝｛（u，v）｜u∈V，v∈V且u和v相邻接｝表示节点间的连接关系，类型包括无线链路和有线链路等。每种类型的节点或链路均有各自的属性。

2.2 物理网络拓扑

实验环境的物理拓扑结构可用无向图G＝ （V，E）表示，其中V＝ ｛v｜v是G 中的节点｝，表示网络中节点的集合，包括核心交换机S、仿真节点E以及真实网络设备R这3种类型。各类型节点的属性见表1。

表1 物理节点类型

E＝ ｛（u，v）｜u∈V，v∈V 且u和v相邻接｝表示节点间链接的集合。链路属性用Eattr＝ ｛b，d，l｝，分别表示链路的带宽、延迟和丢包率。

为了满足网络安全实验环境建设目标，需要构造大规模拓扑结构以仿真实际条件下的网络运行场景。通过研究实验资源的拓扑映射技术，能够为目标拓扑制定合理的映射方案，从而将欲仿真的实验网络分散部署到不同的物理主机上，将不便仿真的特殊设备映射到实物装备上，以确保实验场景能够更加均衡地利用相对有限的物理资源。

2.3 基于图论的拓扑分割步骤

针对网络仿真实验实验环境的实际需求，我们首先针对通信资源梳理了网络拓扑分割技术所要解决的具体问题，然后基于图论进一步提出了包括拓扑压缩、初始划分和拓扑恢复等多个步骤在内的拓扑分割方法，在满足各物理节点负载均衡和物理主机间网络通信量最小的前提下，将各个网络子域映射到不同的物理主机上，从而得到虚拟拓扑与真实硬件间合理的分布式部署方案，从而实现了仿真网络与物理资源间的合理映射。整体实现思路如图2所示。

图2 网络拓扑映射技术实现思路

作为实现网络虚拟资源映射问题的关键技术，本文提出了一种基于图论的拓扑分割方法，该方法通过拓扑压缩、初始划分和拓扑恢复3个步骤实现虚拟资源的分割。其中，拓扑压缩是预处理部分，主要是通过合并图形元素来简化图结构、减少图的复杂度，为拓扑分割的进行创造条件；初始划分是在将网络拓扑图压缩到一定程度之后，对其进行初次划分，按照实验所需划分成数量不等的子图；而拓扑恢复则是按照逆向压缩次序，一层一层将拓扑恢复成原状，并在恢复过程中进行逐次优化，对每一层展开图的分割线附近的点或整个图中的点进行适当调整，保证划分的子图间链路数量最少，以获得更优的分割结果。基于图论的拓扑分割方法具体实现步骤如图3所示。

图3 拓扑分割方法实现步骤

步骤1 拓扑压缩：该步骤是对原始拓扑进行多次压缩，得到一个高度简化的、仅有少量反映原始拓扑整体结构的顶点和链路信息的拓扑图。针对图G＝ （V，E），其基本压缩过程如下。

（1）设S为匹配顶点集合，初始值为空；T 为剩余顶点集合，初始值为全部节点V；M 为不可再继续匹配顶点集合，初始值为空；

（2）在T 中随机选择一个顶点，记为Vi，然后在T 中查找并记录所有与Vi相邻的顶点的边权，其中边权最大的顶点，记为Vj，则顶点Vi、Vj均被置入集合S，并继续搜索过程；若不存在满足条件的Vj，则将Vi放入M，开始（3）；

（3）在T 中随机选择下一个顶点，返回 （2）；若T 为空，则压缩结束，得到Gm＝（Vm，Em）（m＝0，1，2，…）。

由于拓扑压缩会不断地循环进行，因此需对其设定结束条件。实验人员可以通过配置 “理想节点数”或 “压缩到原图80%”等方式来进行控制。同时，需要在临时文件中自动记录压缩过程，以便恢复拓扑时使用。

步骤2 初始划分：在经过拓扑压缩之后，欲划分的原始拓扑图已经缩减到一个足够小的地步，此时将进行初始划分操作，以得到原始拓扑的一个初步分割结果。

初始划分操作较为简单，其基本思想是随机选择一个顶点，并将与之相邻的顶点尽可能的放在一起，形成一个子域，直至所有邻接点都在此子域内，然后再选一个并未划分区域的顶点，重复上述过程，直至将图Gm＝ （Vm，Em）的顶点集Vm划分成大致相等的k个部分。

初始划分仅是粗粒度的拓扑分割，主要是用来满足负载均衡的目的，还需要通过下一步拓扑恢复操作中的结果优化来调整拓扑子域间的分割线，以达到物理主机间通信量最小的目标。

步骤3 拓扑恢复：拓扑恢复分为拓扑还原和结果优化两个过程。拓扑还原根据拓扑划分时保存的临时信息，将划分结果还原为初始规模的拓扑图；结果优化则是在拓扑还原的基础上，优化调整初始划分结果，从而在负载均衡的条件下尽可能减少拓扑子域间的链路数量。结果优化的基本思想是，对分割线两端的顶点进行互换，如果通过交换这对顶点后，能够减少子域间的链路数目，则调整分割线的位置，将这对顶点所属的区域对换。如图4 所示，通过将图中分割线两侧的黑色节点进行互换，使得网络子域间的链路数由6减少到了3。

图4 结果优化

基于图论的拓扑分割方法归纳起来可分为压缩、划分、还原、以及优化4个过程。压缩减少原网络拓扑模型的信息；划分是根据可用的实验设备，对压缩后的拓扑进行一定数量上的分割；将分割后的拓扑还原为初始结构并优化连接信息，最终得到的拓扑子域将分别映射到相应的物理主机上。由于该方法在开始阶段进行了拓扑压缩，所以具备处理大规模仿真实验网络的能力，能够获取到虚拟网络与物理资源之间合理的映射关系，是解决大规模仿真实验网络映射部署问题的有效途径。

3 实验评估

3.1 实验验证环境

采用实验室构建的实验环境由管理控制网络、实验网络两部分构成，其拓扑结构如图5所示。

图5 实验环境拓扑结构

其中，管理控制网络由管理系统和镜像服务器通过交换机连接构成，管理系统负责对实验环境所需的软、硬件资源进行统一的监控与配置；镜像服务器用于存储实验环境需要的各种操作系统镜像文件。

3.2 拓扑分割技术验证

为了满足虚拟网络拓扑与物理硬件资源间的合理映射，本文实现了拓扑分割方法，并通过实验验证了算法的性能和对实验场景网络结构划分的有效支撑作用。

表2给出了将同一拓扑结构划分为不同数量子域后所得到的统计结果。初始拓扑结构包含100个节点和215条边，划分的子域数量从6依次递增到10。每个表项所表达的意思为该子域包含多少个节点和多少条外联边；以序号10一行中的子域6为例，其表项内容为10／6，表示该子域有节点10个，与其它9个子域间的域间链路6条。

表2 单拓扑多子域划分结果

由表2可知，经拓扑分割后得到的各子域的域内节点数量基本一致，保证了各子域所映射物理主机间的负载均衡。同时，随着子域划分数量的不断提高，各子域间链路的平均值呈现出逐渐减少的趋势，相应地降低了物理主机间的通信量。由此可知，本文提出的拓扑分割方法可以有效地支撑仿真实验网络的合理映射与部署。

考虑到仿真实验对大规模网络仿真以及场景切换所带来拓扑重构的快速映射要求，在CPU 为2.3GHz、内存为1G 的仿真物理主机上对拓扑分割方法的性能进行了测试。通过虚拟网络生成模块得到节点规模从1000到10000共10个拓扑结构文件，分别将其划分成10个子域，计算所用时间，每次计算10轮取平均值，结果如图6所示。

图6 运行时间随节点规模变化情况

同时，对节点规模为10000的拓扑进行了多子域划分，子域数量从10逐渐递增到100，分别计算所用时间，每次计算10轮取平均值，结果如图7所示。

图7 运行时间随子域数量变化情况

如图7所示，在一般性能的仿真物理主机上进行拓扑分割，即使是将节点规模为10000 的网络划分成100 个子域，也仅需68.9ms，完全能够满足仿真实验环境对快速性的要求。

4 结束语

本文提出了一种基于图论的拓扑分割方法，通过拓扑压缩、初始划分以及拓扑恢复来简化拓扑图结构、对其进行初次划分，再将拓扑恢复成原状，并进行优化。实验结果表明，该方法有效地平衡了各主机的计算负载，减少了主机间的通信量，更好地将实验的虚拟资源映射到物理主机上，在保证实验规模的基础上，降低了物理资源的需求，减少了实验所需的时间，能够有效地解决大规模仿真实验网络映射部署问题。其并未考虑网络模型中存在的流量状况以及真实网络的层次结构等相关特性，今后将在本文提出的方法的基础上，作上述处理，并结合其它启发式方法来完善此拓扑分割方法。

［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）.［李津，黄敏桓.大规模网络拓扑生成技术研究 ［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）.［况晓辉，黄敏桓.网络蠕虫实验环境构建技术研究 ［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.