基于模拟运行时间的拓扑划分评价模型

葛文堂，张兆心，李斌

(哈尔滨工业大学 网络与信息安全研究中心，黑龙江 哈尔滨 150001)

1 引言

网络模拟在研究网络行为方面有着不可替代的优势，它可以抽象网络行为特征，建立简化模型，通过在计算机上运行该模型，得到所关心的网络指标的输出结果[1]，但是大规模网络模拟需要大量的计算开销。大多数网络模拟器都采用并行离散事件模拟技术，实现模拟的并行化，提高模拟的规模和性能。

并行网络模拟一般采用拓扑划分的方法实现模拟任务的划分[2]，即将需要模拟的网络拓扑划分为若干个子网，每个子网运行在不同的处理器上，不同子网之间通过消息传递来实现通信。拓扑划分为2个阶段：任务估计阶段和任务划分阶段，即首先将所要模拟的网络拓扑转化为带有权值的拓扑图，再用流行拓扑图划分工具（如METIS工具集）进行划分。YOCUM K[3]等把确定能通过节点和链路的最大流量作为节点和链路的权值；XU[4]等首先分析了影响模拟性能的拓扑划分因素，然后根据拓扑信息和数据流对拓扑进行权值估计；王晓峰[5]等提出了基于负载估计的权值估计方法，该算法根据节点和链路在网络拓扑图中的核心程度对它们的权值进行估计；Liu[6]分析了METIS算法的时间复杂度和空间复杂度，改进了拓扑划分的预处理过程，实现了远程路由器的最小化和时间窗口的最大化。童琳[7]提出的基于安全事件的拓扑划分，对DDoS和蠕虫应用进行了权值估计，同时提出基于子网消减的拓扑划分算法，降低了路由表规模，提高了模拟效率；张慈[8]对METIS进行了改进，提出了基于回退的拓扑划分算法；张颖星[9]等提出了一个基于顶点交换的启发式局部搜索近似划分算法，实现了在计算负载均衡的前提下系统通信负载最优化。Yang[10]等提出了一种基于链路粗化的拓扑划分方法，该方法是一种层次聚类算法，减少了远程链路的同时保证了同一区域的连通性。

现有的拓扑划分算法在一定程度上提高了模拟效率，但缺少统一的评价方法对算法的优劣进行衡量。因此，本文提出基于模拟运行时间的拓扑划分评价模型，分析影响并行网络模拟性能的各种因素并进行归纳分类，找出受拓扑划分影响的因素集合，通过对并行网络模拟性能的分析，建立拓扑划分评价模型。本文在PDNS模拟环境中进行DDoS攻击模拟，对比模型计算值与实验结果，二者基本一致，验证了模型的正确性；以METIS算法和子网消减划分算法为例，针对不同的模拟任务对二者进行评价，发现METIS算法评价值比子网消减算法高约14%，运行DDoS模拟任务，前者运行时间比后者长，平均约为14%，实验结果与预期评价相符，验证了模型的有效性。

2 影响并行模拟性能因素分析

影响并行网络模拟性能的主要因素包括：模拟运行环境、模拟应用、负载均衡、通信开销与同步周期；运行环境包括模拟节点的硬件设备、模拟节点之间的网络互连、模拟节点的路由机制、模拟节点的离散事件管理机制。下面重点分析与拓扑划分有关的影响因素。

2.1 负载均衡因素

并行网络模拟是由多个模拟节点相互协调来共同完成模拟，模拟运行时间是最后完成模拟任务的模拟节点的结束时间与最早开始模拟的模拟节点的开始时间之间的差值。显然在总任务量一定的前提下，各模拟节点的任务均衡并在同一时刻开始模拟，才能使模拟时间降到最低。因此，将任务均匀地分配到不同的模拟节点上，能提高模拟性能，减少模拟运行时间。

2.2 通信开销因素

通信开销包含远程通信开销和同步通信开销。远程通信开销主要是模拟过程中模拟应用发送的大量远程数据分组需要的开销，它们需要通过远程链路发送到其他模拟节点上，涉及到真实网络中的延时和带宽。对于不同的模拟应用，不同链路上的数据流量大小不一，划分要保证远程通信量的总和最小。模拟节点之间的同步开销与同步周期密切相关，同步周期越长，则同步次数越少，需要的同步开销就越少。在PDNS模拟器中，同步周期一般是所有被划分链路的延迟最小值。

2.3 模拟应用因素

模拟实验中常用应用类型主要包括DDoS攻击、蠕虫感染，它们分别代表了目标攻击类型和随机感染类型的2类应用。在DDoS模拟时，确定了源地址和目的地址。根据攻击参数，就可以计算出每条链路流经数据量大小，依据这些流量来指导拓扑划分，使其实际负载更加均匀分布在不同模拟节点之间。蠕虫感染具有随机性，需要利用随机感染模型来估计负载。不同的模拟应用表现出不同的模拟行为，主要体现在数据分组的传播路径和数据分组的密度，因此在模拟中针对不同的模拟应用要选择合适的划分方法。

负载均衡和远程通信开销是并行模拟自身所固有的，在任何时候都要保证它们最优。模拟过程中数据分组的分布情况将直接影响负载均衡和远程通信开销，体现了模拟应用对它们的影响。在模拟中要综合考虑这些因素，来获取较高的模拟性能。

3 拓扑划分评价模型

并行网络模拟的4个重要的性能指标是模拟运行时间、模拟真实度、模拟拓扑规模和模拟占用内存空间。

网络模拟的实质在计算机中运行刻画网络行为的抽象模型，并对结果进行处理。显然，模拟结果不可能与真实的网络行为完全相同。模拟真实度是指模拟结果与实际网络行为的吻合程度，抽象模型的准确性决定了模拟的真实度，因此，模拟真实度由模拟的抽象模型（即模拟软件环境）所决定，不受拓扑划分的影响。

模拟规模主要受到模拟环境存储空间的影响，模拟软件的抽象模型越具体，所占用的存储空间越大，待模拟的网络拓扑中的节点与链路越多，模拟占用内存空间越大；此外路由表也需要一定的存储空间，模拟的应用所产生的数据分组在传输过程中需要大量的内存空间。因此，模拟规模和模拟占用空间主要受到模拟的软硬件环境和模拟任务（包括所用的网络拓扑和模拟应用）所决定，基本不会受到拓扑划分的影响。

当确定了模拟环境和模拟任务后，拓扑划分的结果对负载均衡、远程通信开销和同步周期都有影响，这3个因素影响了模拟运行时间，因此拓扑划分对模拟运行时间的影响最大。

本文主要研究如何评价拓扑划分，所以把模拟运行时间作为评价标准，同时把单位模拟运行时间内处理的数据分组转发跳数作为网络模拟性能的衡量标准。

3.1 模拟运行时间估计

模拟运行时间包括初始化时间Tinit、本地计算时间Tlocal、远程通信时间Tremote和同步通信时间Tsyn，表示为

初始化时间主要包括拓扑模型建立时间。给定一个拓扑G，进行划分后得到一系列子拓扑，令V、E分别表示最大子图的顶点数和链路数。Node(V)表示建立V个节点所需的时间，Link(E)表示建立E条边所需的时间。显然如果划分算法能够使所有子图大小一致，则可以保证初始化时间最短。则Tinit可以表示为

假设在第i个周期内共有Pi个事件需要模拟，其中，本地事件个数为PLi，远程事件个数为PRi，显然PLi+PRi=Pi，假设PLi=ai·Pi，则假设PRi=(1-a)Pi，ai称为第i个周期的本地事件比率。PLi分布到N个模拟节点上，一个周期的本地计算时间由本地事件数最多的模拟节点决定。令PLmaxi=fbi·PLi=aifbiPi，根据抽屉原理，fbi∈[1/N,1]。fbi表示了负载均衡程度。令Glocal为本地计算开销常数，即模拟节点处理一个本地事件需要的计算时间，整个模拟过程中的本地计算时间可以表示为

远程通信开销受远程事件以及处理单个远程事件的开销影响，定义通信开销常数Gremote为处理单个远程事件需要的开销。PRi个远程数据分组，分布到N个模拟节点上，一个周期的远程通信时间由远程事件数最多的模拟节点决定。令当PRi≠0时，显然rbi∈[1/N,1]。当rbi=1/N时，表示N个模拟节点处理的远程事件数完全一致，为PRi/N；当rbi=1时，表示所有的远程事件由一个模拟节点处理。rbi表示通信均衡程度。远程通信时间可以表示为

同步通信开销与通信次数、每次通信的固定开销有关。模拟所需要的同步次数C可以表示为C=[Tsim/Tf]。Tsim表示模拟时间，Tf表示同步周期。每一次同步需要N个模拟节点相互通信，每次通信的固定开销Gsyn称为同步开销常数。则GsynN表示为N个模拟节点每进行一次同步需要的时间开销。模拟过程中的同步开销可以表示为

3.2 拓扑划分评价模型

定义本地事件数最大和为Plocal，表示各个周期中N个模拟节点本地事件数最大值之和，由如下公式表示。

定义远程事件数最大和为Premote，表示各个周期中N个模拟节点远程事件数最大值之和，由如下公式表示。

定义模拟性能E为模拟单个数据分组转发所需的时间，即模拟运行时间除以数据分组转发总数由如下公式表示。

定义本地负载不均衡比为Fb，越大表示越不均衡，越小表示越均衡。定义a为本地事件比重，显然a∈(0,1]，实际模拟中a一般大于0.8。Fb∈[1,N]，由如下公式表示。

定义远程通信因子为Fr。显然Fr∈[0,N]，由于网络模拟中远程事件所占的比重相对较少，所以Fr的值都很小。Fr由如下公式表示。

定义数据分组转发密度为psim，表示平均单位模拟时间的数据分组转发数，它的大小与具体的模拟应用有关，由如下公式表示。

结合以上公式，E的计算方法如下

模拟性能主要受如下因素的影响：模拟节点个数、同步开销常数、本地计算开销常数、远程开销常数、数据分组转发密度、本地负载不均衡比、远程通信不均衡比、同步周期和本地事件比重、划分后最大子拓扑的节点数与链路数。

依靠模拟运行环境、模拟应用以及模拟拓扑的划分情况，该模型可以在模拟之前估计出模拟所需要的时间以及模拟性能。当确定了模拟环境和模拟应用，那么前5个因素可以作为常数使用，则模拟性能只受由拓扑划分决定的4个因素影响，因此可以把该性能模型作为评价网络拓扑划分的一种评价模型。模型如下

4 实验及结果分析

在拓扑划分评价模型公式中包括了软硬件环境因素、模拟的应用因素、网络拓扑划分的结果等。该模型只有在具体的模拟环境和模拟应用中才有意义。由于模拟环境的不同，用理论推导获得的计算评价模型常数的方法难以来满足各种模拟环境。基于上述原因，本文设计了一套通用的标准实验方法，采用实验测量的方式在具体的模拟环境中测量各种常数的数值。下面详细介绍实验方案。

本文实验运行环境包括硬件环境与软件环境。硬件环境包括2台曙光服务器，配置为AMD双路双核3.0 GHz CPU、16 GB内存，节点机间采用局域网互联。每个服务器上面安装2个虚拟机，虚拟机采用Red Hat AS4系统，4 GB内存。在实验中，首先建立一个拓扑模型，采用对称哑铃拓扑结构。拓扑的一部分如图1所示。这种拓扑结构非常适合于对并行网络模拟性能的主要影响因素进行实验分析。主要因为负载的不均衡度容易在拓扑中控制；远程通信开销因素比例容易控制；同步周期容易控制；拓扑容易扩展。

图1 实验采用的拓扑结构

在实验中，采用DDoS攻击作为模拟应用，通过设置不同数量的源主机、目的主机、攻击参数，可以方便地统计模型中各个参数的值。

4.1 评价模型正确性验证

设置标准实验测量给定环境的常数：Glocal、Gremote、Gsyn。设计一组实验，仅Plocal不同运行这组模拟应用，得到一系列离散点(Pi,Ti)，对离散点进行直线拟合，

local得到T=KPlocal+b，斜率K即为Glocal。同样方法测量其他参数。测量结果如下：Glocal=7.3×10-5、Gremote=1.18×10-4、Gsyn=9.38×10-4、Link(x)=8.79×10-7x2+2.98×10-4x、Node(x)=1.5×10-3x，发现链路的建立时间不是线性的。

下面运用实验来验证模型的正确性。实验各个参数如表1所示。

表1 实验参数设置

从图2～图4中可以发现，理论计算值与实验值基本一致。因此，该模型可以比较准确地估计模拟性能。

图2 Tf与模拟性能关系

图3 Fb与模拟性能关系

图4 Fr与模拟性能关系

从图2中可以发现，随着通信周期的增大，单个事件的计算开销呈下降趋势，说明模拟性能提高，与理论分析一致。

从图3中可以看出，随着负载不均衡比的增大，单个事件的计算开销呈上升趋势，说明模拟性能逐渐降低，表明负载均衡因素对模拟性能的影响。

从图4中可以看出，随着远程通信因子的增大，单个事件的计算开销呈上升趋势，说明模拟性能逐渐降低，表明远程通信因素对模拟性能的影响。

4.2 评价模型有效性验证

拓扑划分的目标是提高模拟性能，减少运行时间，该模型以模拟运行时间为基础，把它作为评价拓扑划分算法优劣的标准是合理可行的。下面使用该模型对原始METIS划分算法和基于子网消减的拓扑划分算法进行评价。本文使用启明星辰探测的全国路由器级的网络拓扑结构，分别选择国家骨干网、北京、广东、黑龙江、江苏、云南、重庆、浙江的网络拓扑，设计了8组DDoS攻击模拟任务，每次模拟中的数据分组转发总数约为2 500万。根据模拟环境、模拟任务和拓扑划分结果，计算出评价TP值，然后在PDNS模拟器中运行各组模拟任务进行对比，结果如图5和图6所示。

图5 TP值对比

图6 模拟运行时间对比

从图5的TP值对比可以发现，METIS算法的TP值比子网消减的TP值大约为14%。图6是2种拓扑划分算法的模拟运行时间对比图，从图中发现，使用METIS划分结果的模拟运行时间比子网消减划分算法的运行时间长，平均约为14%。子网消减算法以METIS算法为基础，对METIS的划分结果进行优化，通过减少划分后每个模拟区域的子网个数，间接减少了远程事件个数，从而提高了模拟性能，实验结果与模型评价一致，表明了模型的有效性。

5 结束语

本文分析了影响并行网络模拟的各种因素，通过对各个因素进行归纳分类，找出了受拓扑划分影响的因素，通过对并行网络模拟性能的分析，在基于模拟运行时间的推导过程中，提出了基于模拟运行时间的拓扑划分评价模型。在PDNS模拟环境中进行试验，首先，通过对比模型计算值与实验值表明，对于给定的模拟运行环境和模拟应用，该模型能够较为准确地估计模拟性能，能够描述各因素对模拟性能影响的程度与趋势；使用该评价模型对METIS划分算法和基于子网消减的拓扑划分划分算法进行了评价，发现METIS算法比子网消减算法性能低约为14%，结果表明，该模型可以对拓扑划分算法的优劣做出合理评价。

利用该评价模型可以不需要运行模拟过程，只需要进行拓扑划分过程，就可以预先估计不同的拓扑划分算法导致的模拟性能，对划分算法进行评价，以选择较优的划分算法。此外，还可以将该评价模型作为研究新划分方法的目标函数。

[1] 雷擎, 王行刚. 计算机网络模拟方法与工具[J]. 通信学报, 2001,22(9):84-90.LEI Q, WANG X G. Overview of the network simulation methodologies and tools[J]. Journal on Communications, 2001, 22(9):84-90.

[2] 尤洪涛, 姜小成, 陈左宁. 基于动态任务划分的降级机制[J]. 微计算机信息, 2006, 22(30):72-75.YOU H T, JIANG X C, CHEN Z N. Design of degrade based on dynamic job assignment[J]. Control and Automation Publication Group,2006, 22(30):72-75.

[3] KEN Y, ETHAN E, JULIUS D. Toward scaling network emulation using topology partitioning[A]. Proc of the 11th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer Telecommunications Systems[C]. Orlando Florida, 2003. 242-245.

[4] XU D H, AMMAR M. BencHMAP: benchmark-based, hardware and model-aware partitioning for parallel and distributed network simulation[A].Proc of the 12th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems[C]. Volendam, 2004. 455-463.

[5] 王晓峰, 方滨兴, 云晓春. 并行网络模拟中的一种拓扑划分方法[J].通信学报, 2006, 27(2):16-21.WANG X F, FANG B X, YUN X C. Approach for topology partitioning in parallel network simulation[J]. Journal on Communications, 2006,27(2):16-21.

[6] LIU Y, LI B, DONG K K. Reaching of topology partition for parallel network simulation[A]. Proc of 2009 2nd International Conference on Power Electronics and Intelligent Transportation System (PEITS)[C].Shenzhen, China, 2009. 18-21.

[7] 童琳. 并行网络模拟中面向安全事件的拓扑划分技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2010. 13-43.TONG L. Research on Topology Partitioning Oriented for Security Incident in Parallel Network Simulation[D]. Harbin: Harbin Institute of Technology, 2010. 13-43.

[8] 张慈, 张兆心, 迟乐军. 基于回退的并行网络模拟拓扑划分算法[J].微计算机信息, 2011, 27(4):150-151.ZHANG C, ZHANG Z X, CHI L J. Task partitioning algorithm based on rollback of parallel network simulation[J]. Control and Automation Publication Group, 2011, 27(4):150-151.

[9] 张颖星, 姚益平. 乐观策略下并行离散事件仿真动态负载划分优化算法[J]. 计算机学报, 2010, 33(5):813-821.ZHANG Y X, YAO Y P. A dynamic partitioning algorithm based on approximate local search for optimistic parallel discrete event simulation[J]. Chinese Journal of Computers, 2010, 33(5):813-821.

[10] YANG X Q, HE H, ZHANG H L. A topology partition algorithm based on link coarsening in parallel network simulation[A]. Proc of 2009 Second International Symposium on Information Science and Engineering[C]. Shanghai, China, 2009. 514-518.