简化的NS2路由模拟策略

张 恬， 毛 力， 张兆心， 王晓锋

(1.江南大学信息工程学院，江苏无锡214122；2.哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨150001)

0 引 言

网络模拟软件是研究网络技术、评估网络设计方案以及诊断网络故障的有力工具。在新技术的研究过程中，实际网络系统的实现往往是代价较高或不现实的，为了减少投资风险，降低网络实现费用，模拟就成了最佳可供选择的测试、评估和验证手段之一。NS2(networksimulator，version2)[1-2]是其中一种比较具有代表性的模拟软件，由UCBerkeley等开发而成，应用了一些比较成熟的方法，并作为一款优秀的开源软件被广泛使用。

随着计算机网络的快速发展，网络规模逐步扩大，网络模拟中路由策略的计算开销与存储空间变得更大，网络路由模拟也成为了研究的热点问题之一[3]。目前网络路由模拟策略主要分为两类：一类是Flat策略，即静态路由模拟策略[4]，该策略中路由表的计算与存储涉及所有节点，使得路由模拟需要较大的计算与存储开销；另一类则是Nixvector策略[5]，该策略虽然只在路由需要的时候计算并不进行存储，减少了存储开销，但是由于同一条路由信息需要不断计算，又大大增加了计算开销。

针对当前路由策略存在的上述问题，本文分析了静态路由模拟策略的缺陷，提出了一种简化的NS2路由模拟策略。该策略首先将模拟节点分为路由器节点和终端节点两大类，进行路由计算时，只有计算频繁的路由器节点参与；进行地址分类器设置时，计算不频繁的终端节点选择性参与。与Flat策略相比，该策略只计算和存储路由器节点的路由信息，选择性存储与计算终端节点的路由信息，降低了路由模拟的计算和存储开销；与Nixvector策略相比，该策略将参与计算的路由信息进行静态存储，降低了路由模拟的计算开销。

1 NS2 静态路由模拟策略

1.1 静态路由模拟策略原理分析

NS2默认的路由策略是静态路由模拟策略，路由计算是由网络拓扑中的所有节点作为邻接矩阵和连接代价，采用Dijkstra的all-pairsSPF算法计算出每个节点的下一跳nh，通过存放下一跳nh的邻接矩阵，计算出完整的路由。地址分类器设置需要对所有节点的地址分类器进行设置，使分类器各个接口指向正确的出链路，根据加载到每个节点上的路由信息来选路。

在模拟静态路由模拟策略的过程中，路由的确定根据从终端节点发送的数据包选取一个合适的路由路径，并找到相应的下一跳节点。按照上述方法就可以完成所有数据包的接收，虽然不影响扩大模拟规模，但每次模拟一个新的数据包发送、接收过程都需要遍历全局拓扑以计算路由，其时间复杂度很大。

1.2 对静态路由模拟方法缺陷的分析

在模拟过程中，最重要且最耗时的地方有两处：① 建立和计算路由表，它需用到全部节点，但所有度为1的节点不具有路由功能；② 对所有节点的地址分类器进行设置，但并不是所有的节点都参与了分组的发送、接收或传递。

如果用n表示整个拓扑图中的节点数量，则路由计算的时间复杂度是O(n3)，同时需要维护n2的路由表；地址分类器设置的时间复杂度是O(n2)，需要对n个节点进行分类器设置。随着n的增加，运行时间和存储空间都将快速增长，这显然不适合大型网络事件的模拟。为此本文提出了一种简化的路由模拟策略。

2 NS2简化路由模拟策略

2.1 简化路由模拟策略原理

根据节点在网络拓扑中的作用进行分类[6]：

定义1 路由器节点：用于实现分组转发，一般不与代理及应用相连，主要功能类似实际网络中的路由器节点。

定义2 终端节点：度为1且只与路由器节点相连，通常与代理及应用相连，但不具有路由功能。

定义3 终端路由器节点：直接与终端节点相连的路由器节点。

针对上述定义，网络模拟拓扑模型中的节点可分为实现分组转发的路由器节点和网络应用的终端节点。Internet实际上是一个具有分层管理结构的系统，存在大量的终端节点，并且数量远远多于路由器节点。例如局域网系统，一系列终端节点通过一个终端路由器节点与外部网络进行通信[7]。考虑到路由器节点的路由信息计算复杂、使用频繁，终端节点和终端路由器之间的路由关系是固定的，终端路由器节点是终端节点发送和接收分组的必经之路，终端节点的路由信息计算简单、使用不频繁，本文提出了一种简化路由模拟策略，其具体思路是：针对计算复杂、使用频繁的路由信息采用静态存储的方法；针对计算简单、使用不频繁的路由信息则采用选择计算的方法，即只对参与分组发送、传递的终端节点和路由器节点进行分类器设置。下面对简化路由模拟策略做进一步阐释。

2.2 简化路由模拟策略实现

为了实现上述思路从以下4个方面对静态路由模拟策略进行简化：

(1)节点分类：在静态路由模拟策略中统一建立s个节点，在简化路由策略中s个节点分为m个终端节点(Trouter)，编号为0～m 1，n个路由器节点，编号为n～n+m 1，同时标记终端节点在OTcl和C++中的对象。

(2)减少邻接矩阵维数：对所有链路，若链路两端均不是终端节点，即为使用频繁的路由器节点时将链路代价插入到代价邻接矩阵中；若有一端为终端节点，将与终端节点相连的终端路由器节点设置为另一端节点。这样减少了静态模拟策略中代价邻接矩阵维数，维数由s×s变为n×n。

(3)简化查找下一跳：使用频繁的路由器节点对或发送与接收分组的终端节点对(i，j)查找路由表R(i，j)时，如果两端不是终端节点则下一跳nh=R(i，j)；如果i为终端节点则nh=node[i]->Trouter；如果j为终端节点，而i不是终端节点则nh=R(i，node[j]->Trouter)；如果j为终端节点，而i也是终端节点则nh=j；相比静态路由模拟策略减少了对路由表的查找时间，从而降低了时间复杂度和存储空间。

(4)去除未参加分组发送与接收的终端节点：为进一步减少模拟运行时间和存储空间，引入数组，用来记录参与分组发送与接收的终端节点的编号。对终端节点进行地址分类时，如果与数组中的编号匹配则进行计算，否则跳过寻找下一个相匹配的节点。

经过上述分析就形成了对静态路由模拟策略的简化，具体结构示意图如图1所示。

图1 简化路由模拟策略

2.3 简化路由模拟策略性能分析

(1)由于对计算复杂、使用频繁的路由信息是通过路由计算获得的，所以只需维护一个含有n个路由器节点的路由表，可以使时间复杂度由O((n+m)3)降低到O(n3)。整个路由计算的时间将会明显的减少，同时只需维护n2规模的路由表，相比原有(m+n)2的路由表，存储空间也有很大的下降。

(2)对地址分类器设置的简化，只对路由器节点和链路中参与分组发送与接收的终端节点进行分类器设置。如果网络中有p个终端节点参与了分组发送与接收，时间复杂度变为O((n+p)2)(p<=m)，与原有时间复杂度O((n+m)2)相比(实际链路中参与分组发送与接收的p比m少很多)，整个计算时间将会有显著的减少，同时由于只对n个路由器节点和链路中参与分组发送与接收的p个终端节点，进行分类器设置，存储空间也会有所下降。

静态的路由模拟与简化的路由模拟时间开销和存储开销对比表分别如表1和表2所示(n，m，p分别表示路由器节点数目，终端节点数目，参与分组发送或接收的终端节点数目)。

表1 时间开销对比

表2 存储开销对比

3 实验与结果分析

3.1 简单网络拓扑实验

采用简单网络拓扑实验来验证简化路由模拟策略的真实性。如图2所示，该拓扑结构共有9个节点，R1-R3为路由器节点，T1-T6为终端节点。分别采用静态路由模拟策略和简化路由模拟策略进行两次模拟。建立ftp连接，模拟时间为50S。查看自带记录文件(trace文件)发现，两次模拟实验的记录结果完全一致。由此可以说明简化路由模拟策略的真实性。

图2 简单网络拓扑

3.2 大规模网络模拟实验

实验运行环境为PC机一台，在NS2模拟器上实现了简化的路由模拟策略，并将其与静态路由模拟策略进行了比较。实验中的拓扑结构采用了流行的NEM拓扑生成器[8]产生。共生成3组数据：1000个节点(100个路由器节点和900个终端节点)，2000个节点(200个路由器节点和1800个终端节点)，3000个节点(400个路由器节点和2600个终端节点)。

路由策略的性能指标主要包括路由计算时间、地址分类器设置时间、模拟运行时间以及存储空间大小。图3至图6分别给出了不同节点规模条件下，上述4个指标在两种路由模拟策略下的变化曲线。在拓扑连接和模拟应用完全相同的前提下，两种路由模拟策略在4个指标下的差异主要缘于路由策略的区别。

图3显示的是不同节点规模下所需的路由计算时间。随着拓扑规模增大，采用静态路由模拟策略的路由计算时间快速增大，而采用简化的路由模拟策略的路由时间增大缓慢，比静态路由模拟策略的时间开销减少了约99%，相对于大规模复杂模拟运行所需时间，简化的路由模拟策略更合适。

图3 路由计算时间对比

图4 节点分类器设置时间对比

图5 模拟运行时间对比

图6 存储空间对比

图4和图5给出了不同节点规模下两种路由模拟策略的地址分类器设置时间及完成模拟所需时间的比较。根据图4和图5的结果，地址分类器设置时间和运行时间分别比静态路由模拟策略减少了75%和61%，也显示出了简化的路由模拟策略的优越性。

图6显示的是不同节点规模下所需的总存储空间大小，由路由计算部分和地址分类器设置部分的存储空间组成。随着节点数的增加，静态路由模拟策略的存储空间也急剧增大，而简化的路由模拟策略的存储空间缓慢增长。因此，简化的路由模拟策略相比静态路由模拟策略更能节约内存空间，这就意味着可以扩大模拟网络规模，从而提高NS2模拟器的效率。

4 结束语

当前静态路由模拟策略中大规模网络模拟需要相当长的运行时间和存储空间，为减少模拟运行所需的时间开销和存储开销，本文分析了静态路由模拟策略的缺陷及其形成原因，提出了简化的NS2路由模拟策略。该策略将网络模拟中的路由信息进行分类简化，改进了路由计算和地址分类器设置，从而避免大量终端节点的路由存储和遍历计算，有效提高了模拟运行效率。多组实验结果表明，相对于传统的静态路由模拟策略，该策略更适合大规模网络环境下复杂应用的模拟。

[1] The network simulator NS-2[EB/OL].http://www.isi.edu/nsnam/ns,2005.

[2] 徐雷鸣,赵耀.NS与网络模拟[M].北京:人民邮电出版社,2003.

[3] 郝志宇,云晓春,张宏莉.并行网络模拟中的远程路由计算和查找方法[J].通信学报,2007,28(6):66-72.

[4] Chen J,Gupta D,Vishwanath K,et al.Routing in an Internet scale network simulator[C].Proceedings of the IEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Washington DC,USA:IEEE Computer Society,2004.

[5] 郝志宇,云晓春,张宏莉.MTree_Nix网络模拟路由计算与查找策略[J].电子学报,2008,3(3):477-481.

[6] Hao Zhiyu,Yun Xiaochun,Zhang Hongli.Tnrm based simulation of Internet worm propagation[C].St.Thomas,US:Proceeding of the Fourth IASTED International Conference Communications,Internet,and Information Technology,2006:183-184.

[7] Yihua He,Georgos Siganos,Michalis Fal Outsos,et al.Lord of the links:A framework for discovering missing links in the Internet topology[J].IEEE/ACM Transactions on Networking,2009,17(2):391-404.

[8] Magoni D.Network topology analysis and internet modeling with Nem[J].International Journal of Computers and Applications,2005,27(4):252-259.