网络模拟中高真实性拓扑折叠方法研究

杨国玲，王晓锋，毛 力

（江南大学 物联网工程学院，江苏 无锡214122）

0 引 言

当前，网络模拟已成为研究网络行为和评价网络协议的的重要手段［1，2］。但随着网络规模越来越大，结构越来越复杂，网络模拟的高资源消耗问题 （大量的计算及存储开销）也日益突出。目前针对该问题的研究主要集中于简化网络模拟模型，即通过提高网络模拟的抽象度，来降低计算及存储开销。其中，文献 ［3］提出一种基于local－area拓扑抽象算法，该方法首先把网络划分成多个本地域，然后对每一个本地域进行抽象来降低拓扑规模。文献 ［4］提出一种基于焦点区域折叠的拓扑抽象方法，这种方法把网络分成焦点区域和非焦点区域，通过对非焦点区域的树形收缩来降低网络规模。文献 ［5］提出一种基于主机删减的蠕虫模拟方法，该方法按比例对主机进行缩减来减少模拟开销。文献 ［6］提出一种基于聚合系数的拓扑抽象算法，通过树形抽象和权值估算抽象来缩小网络规模。文献 ［7］和文献 ［8］则分别通过删除全部主机节点和部分路由节点、删除部分主机节点来缩减网络拓扑。

上述文献中的抽象算法普遍存在抽象率低或模拟真实性无法保证的问题。其中，文献 ［3，4，6－8］有效地缩减了拓扑规模，提高了模拟效率，但其真实性无法保证；文献 ［5］为了保证模拟真实性，只删减了部分主机节点，抽象度较低。针对上述问题，本文提出了一种高真实性的拓扑折叠方法HFTF （high fidelity topology folding），该方法先通过对大规模网络拓扑进行路由删减和主机抽象来形成小规模的网络拓扑，然后在此基础上分析了抽象后模拟结果的失真情况，并进行了相应补偿，从而在有效提高模拟效率的同时，保证了模拟结果的真实性。

1 拓扑折叠算法

本文提出了一种基于拓扑折叠的抽象算法，该算法分为两步：第一步递归删除度为1的路由节点；第二步对主机节点进行抽象。相关定义如下 （其中V 表示路由节点，H 表示主机节点）：

定义1 L （Vi，Vj）表示在节点Vi和Vj之间的链路。

定义2 HostNumber （Vi）表示节点Vi所带的主机数。

定义3 Degree （Vi）表示节点Vi的度数。该算法采用无向路由拓扑，因此每个节点的度数就是与其相连的（不包括与主机相连的）链路的个数。

定义4 a表示主机抽象系数。

1.1 递归删除算法

算法具体描述如下：

（1）procedure router deletion

（2） for each Viinit Degree（Vi）＝0

（3） end for

（4） for each L（Vi，Vj）

（5） if L（Vi，Vj）exit do

（6） Degree（Vi）＋＋，Degree（Vj）＋＋；

（7） end if

（8） end for

（9） if exit Degree（Vi）＝1do

（10） for each Vi

（11） if Degree（Vi）＝1and L（Vi，Vj）exit do

（12） record Vi；

（13） HostNum（Vj）＝HostNum（Vi）＋HostNum（Vj）；

（14） delete Vi；

（15） delete L（Vi，Vj）；

（16） end if

（17） end for

（18） for each Viinit Degree（Vi）＝0

（19） end for

（20） for each L（Vi，Vj）

（21） if L（Vi，Vj）exit do

（22） Degree（Vi）＋＋，Degree（Vj）＋＋；

（23） end if

（24） end for

（25） end if

（26）end procedure

其中，（2）－（3）初始化路由节点度数为0；（4）－（8）计算路由节点度数；（9）－（25）递归删除拓扑中度为1的路由节点，并把其所带的主机节点归并到与之相连的另一个路由节点上，然后再重新计算度数，直到所有节点的度数都不为1。

通过图1进行举例说明，为描述方便，令每个路由器带4个主机，“□”代表路由节点，“○”代表主机节点。

图1 部分原始拓扑

经过递归删除算法，图1简化得到的结果如图2所示。

图2 递归删除算法之后的拓扑

1.2 主机抽象算法

算法具体描述如下：

（1）procedure host abstraction

（2） for each Vido

（3） HostNum （Vi）＝HostNum （Vi）／a

（4） end for

（5）end procedure

以上 （1）－（5）使每个路由器上的主机数按抽象系数（a）进行缩减。

针对图2，若取a 为4，则图2 经过主机抽象算法后，变为图3的拓扑。

图3 主机抽象之后的拓扑

2 拓扑折叠后链路的失真分析及补偿

由HFTF算法分析可知：经过第一步的路由删减，部分路由节点和链路会被删除，即和原始拓扑相比，同样的数据包传输经过路由节点和链路会变少，这必然会导致发送时延和传播时延的降低；经过第二步的主机抽象，使主机的数量变为原来的1／a，而这也会导致流入网络的流量速率降低、从而导致排队时延以及丢包率的降低。这两方面会对模拟结果的真实性造成影响，具体分析与补偿方法如下所示。

2.1 排队时延和丢包率的失真分析及补偿

基于经典的DropTail队列管理算法来分析。原始拓扑的相关变量定义如下：

F：路由器Vi上的出链路L 相对应的缓冲队列；

L（t）：F 在t时刻队列字节长度；

Q（t）：数据包的排队延迟；

B：链路L 的带宽，则Q（t）＝L（t）／B；

F（t）：t时刻流入队列F 的流量速率；

Lavg：缓冲队列数据包的平均字节长度；

Tmax：缓冲队列的最大长度。

同理定义拓扑折叠后的相关变量L′（t），B′，F′（t），Q′（t），T′max。由HFTF算法可知，拓扑折叠之后主机数量变为原来的1／a，这会导致流入拓扑的流量速率也变为原来的1／a，则流入每个路由器队列的流量速率也应为1／a，即

为了保证模拟结果的真实性，这里令拓扑折叠后的L的带宽、缓冲队列的最大长度均为原来的1／a （下面会分析在此条件下丢包率以及排队时延的真实性），即

原始拓扑的丢包率p（t）为

t时刻的队列长度与丢包率满足如下关系

其中，φ（x）的取值为：若x＞0，φ（x）＝1；若x≤0，φ（x）＝0。

拓扑折叠后的丢包率p′（t）为

拓扑折叠后的L′（t）和p′（t）的关系为

结合式 （2）、式 （5）得

结合式 （1）、式 （2）、式 （6）得

对比式（3）和式 （7）、式 （4）和式 （8），可以看出p（t）与p′（t），L （t）与aL′ （t）均满足同一组关系式，则有

由定义可知拓扑折叠前后的数据包的排队时延分别为：Q（t）＝L（t）／B、Q′（t）＝L′（t）／B′，结合式 （2）、式（10）可推出

由式 （9）、式 （11）可以看出，通过引入补偿方法（把链路的带宽及缓冲队列的最大长度均缩减为原来的1／a），即可保证网络拓扑中排队时延和丢包率的真实性。

2.2 传播时延和发送时延的失真分析及补偿

数据包时延包括排队时延，发送时延和传播时延。相关定义如下：

Lp：数据包的长度，则发送时延为Lp／B；

D：链路L的传播时延。

假设数据包从m 节点传到n节点，在原始拓扑中所经过的链路为L1，L2，…，Li，…，在拓扑折叠后的拓扑中所经过的链路为L1′，L2′，…，Lj′，…，则在原始拓扑中的数据包时延为

拓扑折叠后的数据包时延为 （D′为拓扑折叠后链路的传播时延）

因为拓扑折叠过后会导致数据包时延降低 （经过的节点和链路变少），此时要保证模拟结果的真实性，需在m 到n的链路上加上一个延迟补偿Δd，其值为

由2.1分析可知，在拓扑折叠前后

即在拓扑折叠后剩余节点的排队时延和在原始拓扑中的排队时延相等。由HFTF算法可知：删除的路由节点都是边缘节点，而边缘节点的拥塞程度通常不高，其排队时延可以忽略不计，则式 （14）可以写成

由式 （16）可知，要保证拓扑折叠后数据包从m 到n时延的真实性，需要加上一个延迟补偿Δd，其值为m 到n之间所有被删除链路的发送延迟和传播延迟总和。

3 实验验证

为了验证 HFTF 算法的有效性，本文采用基于NS2［9，10］的Slammer蠕虫进行模拟实验，网络拓扑采用3组分别有50，100，150个路由节点的拓扑模型 （把拓扑中度为1的路由节点设为边界路由器，每个边界路由器连接64个主机节点，并将这些主机全部设为弱点主机），抽象系数a的取值为4。

3.1 拓扑折叠前后的规模比较

由图4可以看出3组拓扑在拓扑折叠前后的规模对比：对50个路由节点，原始拓扑中节点数量是2290，折叠后为575，规模减少了74.89%；对100个路由节点，拓扑折叠前后的节点个数分别是4260和1071，减少了74.86%；对150个路由节点，折叠前后的节点个数分别为6870、1741，减少了74.66%。由此可以看出，此算法可以在很大程度上缩减网络拓扑的规模。

图4 拓扑在折叠前后规模比较

3.2 拓扑折叠前后模拟时间的比较

由图5可以看出，3 组拓扑在折叠前后运行时间的对比：对于50 个路由节点，折叠前后的模拟时间分别为578s、14s，降低了97.58%；对100 个路由节点，折叠前后的模拟时间分别是4171s、79s，降低了98.11%；对150个路由节点，折叠前后的模拟时间分别是5721s和124s，降低了97.83%。由此可以看出，此算法可以缩短模拟运行时间97%以上。

图5 拓扑在折叠前后模拟时间比较

3.3 模拟结果的真实性比较

为了更好的说明HFTF算法的真实性，每组实验中都采用3组数据来做比较，这3组数据分别是原始拓扑模拟结果、拓扑折叠但没有链路补偿的模拟结果和拓扑折叠并且加上链路补偿的模拟结果。比较结果如图6所示 （横坐标为时间t，竖坐标为t时刻感染的主机节点数量）。

通过图6 （a）－（c）可以看出，采用HFTF算法的蠕虫模拟感染曲线与原始拓扑的的感染曲线几乎完全一致，比不加链路补偿的拓扑折叠算法具有更高的真实性。由此可以看出本文提出的高真实性拓扑折叠算法在降低网络拓扑规模，减少模拟运行时间的前提下，仍可以保证结果的高真实性。

图6 蠕虫模拟在拓扑折叠前后的真实性比较

4 结束语

大规模网络模拟中的高资源消耗问题已受到越来越多的关注，针对大规模网络模拟中现有算法普遍存在的抽象率低或模拟真实性无法保证的问题，本文提出一种高真实性拓扑折叠模拟方法，该方法首先通过递归删除算法和主机抽象算法来降低网络拓扑规模，提高抽象率，然后通过链路参数补偿以及端到端延迟补偿来确保模拟结果的真实性。基于蠕虫模拟的实验验证了该方法可以降低网络规模74%以上，减少模拟运行时间97%以上，并且结果仍具有很高的真实性。

［1］WANG J，YU X，YAN J.Research on network simulation abstract technology based on simplicity theory ［C］／／Proceedings of International Conference on Wireless Networks and Information Systems.Shanghai，China：IEEE Computer Society，2009：186－192.

［2］WANG X，FANG B，ZHANG H，et al.A model for estimating the performance of synchronous parallel network simulation［J］.International Journal of Modelling and Simulation，2008，28 （1）：100－107.

［3］LI Qiao，ZHANG Zhaoxin.An Internet router－level topology aggregation algorithm based on local－area ［J］.Chinese High Technology Letters，2011，21 （9）：922－927 （in Chinese）.［李乔，张兆心.基于local－area的Internet路由级拓扑抽象算法 ［J］.高技术通讯，2011，21 （9）：922－927.］

［4］ZHANG Zhaoxin，DU Yuejin，WANG Ke，et al.Topology aggregation model based on focus folding for network simulation［J］.Journal on Communications，2012，33 （7）：9－21 （in Chinese）.［张兆心，杜跃进，王克，等.基于焦点折叠的网络模拟拓扑抽象模型 ［J］.通信学报，2012，33 （7）：9－21.］

［5］WANG Xiaofeng，GUAN Lu.Research on network worm simulation method based on host node reduction ［J］.Computer Engineering and Design，2012，33 （10）：3687－3691 （in Chinese）. ［王晓锋，关鹭.基于主机节点删减的网络蠕虫模拟方法研究 ［J］.计算机工程与设计，2012，33 （10）：3687－3691.］

［6］DING Zhenquan，DONG Kaikun.Topology aggregation algorithm based on polymerization coefficient［J］.Computer Engineering，2012，38 （6）：111－115 （in Chinese）. ［丁振全，董开坤.基于聚合系数的拓扑抽象算法 ［J］.计算机工程，2012，38 （6）：111－115.］

［7］WANG Meijun，ZHANG Zhaoxin，LI Bin.Topology abstraction algorithm for parallel network simulation ［J］.Microcomputer Information，2011，27 （9）：169－171 （in Chinese）.［王美君，张兆心，李斌.并行网络模拟中拓扑抽象算法的研究［J］.微计算机信息，2011，27 （9）：169－171.］

［8］Hwangnam K，Jennifer H，Hyuk L.TranSim：Accelerating simulation of large－scale IP networks through preserving network invariants［J］.Computer Networks，2008，52 （15）：2924－2946.

［9］WANG Bo，ZHOU Zhiwei.Comparative analysis on network simulation software NS2and OPNET ［J］.Computer System and Application，2010，19 （6）：90－95 （in Chinese）.［王波，周志伟.网络模拟软件NS2与OPNET 的剖析比较 ［J］.计算机系统应用，2010，19 （6）：90－95.］

［10］GAO Wenyu，WANG Jianxin，CHEN Songqiao.Extension of queue scheduling algorithm in NS2 ［J］.Journal of System Simulation，2006，18 （2）：521－525 （in Chinese）.［高文宇，王建新，陈松乔.网络仿真软件NS2中队列调度算法的扩展［J］.系统仿真学报，2006，18 （2）：521－525.］