（通信与信息系统专业论文）骨干通信网络的计算机并行仿真平台研制.pdf

摘要 摘要 随着互联网技术和应用的快速发展，网络仿真已经成为解决开展计算机网络 相关研究重要途径之一，大规模通信网络的仿真常常需要面对两个难题：其一是 执行一次仿真所消耗的c p u 周期会随着流量的增大而增加，其二是仿真软件在仿 真过程中消耗的内存容量会随着节点和链路等网络元素数量的上升而以线性甚至 更高的增长率增加。将仿真的计算量和内存消耗分布到多个处理器上是解决大规 模仿真的问题一个有效的解决办法，一种实现分布式仿真系统的“传统 方法是 “从零开始创建一个全新的仿真软件。另一种方法是“联合现有的仿真软件， 重用他们的仿真功能，并将他们通过某种方式将他们有机的结合在一起，以此来 构建能够分布运行的并行仿真系统。就理论和初步的研究结果而言，使用“联合” 的方法确实能够为实现高效、大规模的并行网络仿真提供一种可行的方法。 本文参考“联合 的开发方法，以m p i 程序库作为并行计算和进程间通信的 支持，利用网络仿真软件n s 现有提供的网络仿真功能，设计和实现了一种并行仿 真系统，完成了以下工作： ( 1 ) 在仿真系统的设计中，我们将网络模型按照网络节点划分为多个网络子模 型，并将这些网络子模型分别分配给并行仿真系统的各个仿真进程；制定 了各个仿真进程之间相互通信与协作的机制；为并行仿真系统设计了一种 分层结构，将并行仿真系统的各项功能与模块分别划分到不同的相互独立 的层次，在层内部保持高内聚性、在层之间保持低耦合性，降低并行仿真 系统的开发和维护难度。 ( 2 ) 在仿真系统的具体实现中，采用一系列方法技术，解决了系统实现的一些 关键技术问题，如设计并实现了以p r o c e s s t a b l e 模块为中心的一系列模块， 负责初始化仿真数据和并行参数、控制每个进程的执行流程和计算任务： 确定了仿真进程之间的同步机制，设计并实现了u n i f o r m s c h e d u l e r 类在仿 真进程之间同步仿真时间和保持仿真时间的一致性，避免出现网络事件乱 序的现象；在进程之间传递数据的流程中插入了序列化模块，使n s 各种 结构复杂的包数据能够在进程之问顺利的传递。 ( 3 ) 为增强系统的可扩展性，我们向并行仿真系统加入了启动算法进程的功 摘要 能、定义了算法进程的编程接口、并设计了算法的管理模块。并行仿真系 统能够在网络仿真的过程中实时的执行链路流量分析等多种算法。用户可 以通过编程接口向并行仿真系统添加自定义的算法代码。 ( 4 ) 使用从i n t e m e t 2 网络的流量数据对并行仿真系统进行了仿真实验，仿真实 验的结果表明：本文研制的并行仿真系统能够启动多个进程以并行的方式 完成网络仿真，并减轻每个进程对运行时间的需求和对内存的消耗等负 担；算法进程能够实时、正确的执行多种算法；并行仿真系统的主要功能 达到了预期目标。 关键词：大规模网络仿真，分布式，并行仿真，n s ，m p i i i a b s l r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g i e sa n d a p p l i c a t i o n s ，n e t w o r k s i m u l a t i o nh a sb e c o m et h em e t h o do fc h o i c ef o rm a n yc o m p u t e rn e t w o r ka n a l y s i s p r o b l e m s w h i l ec a r r y i n go u tl a r g es c a l en e t w o r ks i m u l a t i o no n eq u i c k l yr a i l si n t ot w o d i f f i c u l t i e s ：f i r s t ，t h es i m u l a t i o no fa n yr e a s o n a b l es i z en e t w o r kc a nt a k ee x c e s s i v e a m o u n t so fc p ut i m et oe x e c u t e ；s e c o n d ，t h em e m o r yu t i l i z e db yan e t w o r ks i m u l a t i o n w i l lg r o wa tl e a s tl i n e a r l yw i 也t h es i z eo ft h en e t w o r k d i s t r i b u t i n gt h ee x e c u t i o no ft h e s i m u l a t i o no v e rm u l t i p l ep r o c e s s o r so f f e r so n es o l u t i o nt oa l l e v i a t i n gt h e s ep r o b l e m s t h e r ea r eg e n e r a l l yt w oa p p r o a c h e st od e v e l o pap a r a l l e ls i m u l a t o r t h et r a d i t i o n a l a p p r o a c hi s t o d e v e l o pas i m u l a t o r “f r o ms c r a t c h ”，w h i l e t h e o t h e ri n v o l v e s i n t e r c o n n e c t i n ge x i s t i n g n e t w o r ks i m u l a t o r sa n d r e u s i n g t l l e i r e s t a b l i s h e d f u n c t i o n a l i t i e s i nt h i sp a p e r , w ed e s i g n e da n ds t a r t e dd e v e l o p i n gap a r a l l e ln e t w o r ks i m u l a t o r f o l l o w i n gt h el a t t e ra p p r o a c h w ei n t e r c o n n e c ts e v e r a ln sp r o c e s s e su s i n gm p il i b r a r y f o rp a r a l l e le x e c u t i o na n di n t e r - p r o c e s sc o m m u n i c a t i o n o u rw o r ki n c l u d e s ： ( 1 ) w h e nd e s i g n i n gt h ep a r a l l e ls i m u l a t o r , w ed i v i d ean e t w o r km o d e li n t os e v e r a l s u bm o d e l s ，w h i c hw i l lb ed i s t r i b u t e do ne a c hp r o c e s s e so ft h es i m u l a t o r w e a l s od e f i n e dt h em e c h a n i s mf o ri n t e r - p r o c e s sc o m m u n i c a t i o na n dc o o p e r a t i o n w ed e s i g n e dam u l t i l a y e rs t r u c t u r ef o re a c hp r o c e s so ft h ep a r a l l e ls i m u l a t o r e a c hl a y e rc o n t a i n sas e to fm o d u l e so ft h es i m u l a t o ra n di sr e l a t i v e l y i n d e p e n d e n tw i t ho t h e rl a y e r s ，s ot h a tt h ec o m p l e x i t yo fd e v e l o p i n ga n d m a i n t a i n i n gc a nb ec o n t r o l l e d ( 2 ) w h i l ei m p l e m e n t i n gt h ep a r a l l e ls i m u l a t o r , w eu t i l i z e ds e v e r a ls k i l l sa n d m e t h o d sa n ds o l v e ds o m ek e yp r o b l e m s w ei m p l e m e n t e dp r o c e s s t a b l e m o d u l ea n das e to fc o r r e s p o n d i n gm o d u l e st oi n i t i a l i z ep a r a l l e lp a r a m e t e r sa n d t oc o n t r o le x e c u t i o nf l o w w ed e f i n e da i l i n t e r - p r o c e s ss y n c h r o n i z a t i o n m e c h a n i s m ， a n di m p l e m e n t e du n i f o r m s c h e d u l e rc l a s s w ei n s e r t e da s e r i a l i z a t i o nm o d u l ei nt h ep a c k e td a t at r a n s m i s s i o np r o c e s s ，w h i c ha l l o w s i i i v a r i o u sp a c k e td a t aw i t hc o m p l i c a t e ds t r u c l = u r et ob et r a n s f e r r e db e t w e e n p r o c e s s e s ( 3 ) t oo r d e rt oa l l o wf u n c t i o n a l i t ye x t e n s i b i l i t y , w ei n t r o d u c e da l g o r i t h mp r o c e s s 硒w e l l 嬲i t sm a n a g e m e n tm o d u l ei n t ot h ep a r a l l e ls i m u l a t o ra n dd e f i n e dt h e p r o g r a m m i n gi n t e r f a c ef o ra l g o r i t h mp r o c e s s e s s e l f - d e f i n e da l g o r i t h m ss u c h 嬲n e t w o r kf l o wa n a l y s i sa l g o r i t h mc a l lb ea d d e di n t ot h ep a r a l l e ls i m u l a t o r ( 4 ) w ec a r r i e do u ts e v e r a ls i m u l a t i o ne x p e r i r n e n t su s i n gi n t e m e t 2n e t w o r km o d e l a n df l o wd a t a t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r i m a r yf u n c t i o n a l i t i e so f t h ep a r a l l e ls i m u l a t o rh a v er e a c h e do u r e x p e c t e dg o a l s k e y w o r d s ：l a r g es c a l en e t w o r ks i m u l a t i o n ，p a r a l l e ls i m u l a t o r , n s ，m p i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：逊1 日期：叫年彳月， 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：j 啤导师签名：兰牲 日期：州罗年月1 日 第一章绪论 第一章绪论 1 1 网络仿真的研究背景与意义 互联网的飞速发展带来了对各种网络技术的不断需求，例如安全、数据的多 播传输、移动无线网络、网络策略和网络服务质量( q o s ) 等等，这些需求则刺 激了新的网络协议和算法的出现和发展。网络仿真【l 】是一个很有用的网络研究工具， 它以系统理论、形式化理论、随机过程和统计学理论、优化理论为基础。在设计 阶段，仿真方法可提供一个虚拟模型来预测并比较各种方案的性能；运行阶段， 通过对不同环境和工作负荷的分析和比较，来优化系统的性能。 如今，网络仿真已经成为、而且会在很长时间内都将一直是解决关于计算机 网络的诸多问题的首选研究途径之一。在此之前，通过建立数学模型来对网络进 行分析一直是解决大量计算机网络领域问题的最佳方法。建立数学模型需要首先 对被模拟的对象进行很多假设、降低模型的复杂度，但是随着网络模型复杂度的 上升，数学建模的方法越来越受到自身的限制，面对大量研究单纯的数学方法逐 渐显得捉襟见肘。仿真方法的抽象化程度比数学分析方法低，耗费的时间比测量 技术少，其低成本和有效性是其他传统方法不可替代的。现在尽管数学建模的方 法仍然被应用于很多研究当中，但是通过数学方法建立的模型仍然需要通过进行 仿真来验证其正确性、准确性等等。仿真的手段常常被用于深入的观察或验证某 些特定协议后或者机制在多种网络环境中的作用或性能。在某些情况下，仿真是 唯一可行的方法和技术。随着网络新技术的不断出现和数据网络的日趋复杂，对 网络仿真技术的需求必将越来越迫切，网络仿真的应用也将越来越广泛，网络仿 真技术已成为研究、规划、设计网络不可缺少的工具。 从2 0 世纪8 0 年代开始，在美国等发达国家就一直致力于丌发商业和非商业 用途的网络仿真产品。近年来，我国的网络仿真研究和应用得以发展。1 9 9 7 年， c e r n e t 网络中心开始开发自己的网络仿真软件；1 9 9 8 年后，我国多家单位陆续 引进o p n e t 网络仿真软件，用于网络协议开发、网络规划设计和应用的研究。 电子科技大学硕士学位论文 1 2 大规模网络仿真所面临的困难 大量针对计算机网络的仿真软件都是基于“离散事件，【2 】的仿真技术，这是因 为“离散事件 技术特别适合用来建立计算机网络模型和分析网络性能。我们可 以将在网络中流动的所有数据包看作在离散时间点上的一系列离散事件。例如， 一个数据包在t 时间从一条链路的一端发送出去，然后会在链路上传输，最后于 时间t + t 到达这条链路的另一端；类似的，一个包到达连接到一条链路的输出 端的等待队列的事件，可以通过在时间t q 建立一个对应的离散事件来模拟，而这 个数据包离开队列的行为则可以设置为发生在时间t q + t q 事件；最终，当数据 包被传送到其目的地后，对应的协议实体可以对“接收到数据包 的时间做出反 应，根据实际情况产生一个回复包，并将回复包发送到适当的目的地。本身就是 计算机程序的网络协议的各种行为对于仿真软件来说是很容易模拟的，而且协议 以外的网络行为，比如数据包的传输事件等，可以通过离散事件的方法进行模拟， 所以基于离散事件的仿真软件能够以最接近真实的程度模拟网络环境以及各种网 络行为，进一步的成为了进行针对网络的各种研究的重要工具之一。 基于离散事件的仿真软件会在运行期间建立并维持一个时间轴的模型，并以 这个模型为基础来模拟待研究的真实网络的各种行为。仿真软件在其内部建立的 时间轴模型所表示的时间叫做仿真时间。对所有等待模拟的各种网络事件加上仿 真时间的时间戳，然后将这些事件的时间戳记录到一个有序的集合中，最后这些 记录到有序集合中的记录会被仿真软件用来对网络的主要行为进行建模。一个事 件的时间戳指明了该事件应该发生或者应该被模拟的仿真时间。记录所有待模拟 事件的时间戳的有序集合应该按照仿真时间的逻辑递增的组织其数据。一般来说， 基于离散事件的仿真软件会从待模拟事件的集合的头部直接取出一份记录，( 根 据集合数据的组织方式可以断言这份记录的时间戳一定不大于集合中剩下的所有 记录，) 然后推进仿真时间，最后对这份记录所包含的事件进行模拟。完成一个 事件的模拟之后，往往会改变某些对象的状态，创建更多的待模拟事件并加入到 有序集合中，或者将某些事件从待处理事件的集合中取消掉。仿真软件会在下面 两个条件中的任意一个得到满足的时候结束仿真：其一是仿真软件已经处理了所 有待处理的事件以致没有剩下的事件需要模拟了，其二是仿真时间已经到达了某 一个实现预定的结束点。 基于离散事件的仿真软件除了需要管理仿真时问以外，还需要提供一种描述 2 第一章绪论 和建立网络拓扑模型的途径，和一种用来描述各种网络元素在仿真时的具体行为 的方法，需要实现一个用来管理和处理所有待模拟事件的仿真引擎，以及一套用 来观测仿真过程的接口。这些功能和模块是构建一个离散事件仿真软件的一种常 用方法，然后为了实现这些功能并以这种方法建立仿真软件，就不得不面对下面 的难题。 ( 1 ) 当被模拟的网络达到一定( 节点和链路的数量以及流量的大小的) 规模的 时候，执行一次仿真将会消耗大量的c p u 周期。例如对一条2 4 g b s 的链 路进行模拟，假设平均一个包的长度为1 0 0 0 字节，那么这条链路上会产 生的待仿真事件的数量可能会达到每秒6 0 0 0 0 0 0 件之多；假如我们对1 0 0 0 条这样的链路进行模拟，仿真软件可能需要一个小时的时间来完成仿真时 间中一秒所需要的计算量。使用n s 或者其他同类型的仿真软件进行这样 的实验得到类似的结果。对于这样规模庞大的网络，为了得到仅仅一分钟 的仿真结果，我们可能需要持续进行数天的仿真。 ( 2 ) 进行一次网络仿真会消耗的存储器容量一般至少会随着网络节点和链路 数量的上升而线性增长，有时存储器消耗量的增长速度可能会更快。有些 仿真软件的内存消耗量的增长甚至会随着被模拟的网络元素数量的上升 以二次方的比例增长，这是由于这些仿真软件在每个网络节点内部都保存 了一份路由表，极大程度的增加了仿真软件的空间复杂度。尽管运行仿真 软件的系统平台可以配置大量的内存( 例如2 g b ) ，以n s 为代表的一类 仿真软件在这样的系统中可以模拟的网络节点数量很难超过四位数。对于 像对整个i n t e m e t 的核心网络进行建模并对其中的路由器在处理大量并发 流量时的状态进行模拟等等这样的问题，仿真建立的模型中包含的节点和 链路数量可能远不止四位数。 往往仅仅对小规模或中等规模的网络进行仿真就能获得研究者所需要的关键 数据。而对于某些协议、机制、或具体应用等等，需要研究它们在大规模网络中 会有怎样的表现。对于这些问题，在较小规模网络进行仿真常常难以获得有价值 的甚至准确性较高的参考数据；只在各种大网络、大流量背景下的仿真结果，才 能成为理解它们在实际网络( 例如i n t e r n e t ) 中所能产生的实际效果的重要参考。 进行大规模网络的仿真的必要性由此可见。然而进行大规模网络仿真就必须要首 先解决仿真软件受到的各种限制的问题。 电子科技大学硕士学位论文 1 3 并行仿真系统与分布式网络仿真 1 3 1 分布式网络仿真的发展现状 将仿真的计算量和内存消耗分布到多个处理器上为解决大规模仿真的问题提 供了一个解决办法。进行仿真所需要的内存量的会随着处理器的数量线性的增长， 从而使在仿真中模拟较大规模的网络模型成为可能。如果以在每一秒真实时间中 仿真软件可以处理的仿真事件的数量还衡量仿真软件的计算速度，那么在理论上 仿真软件的计算速度也可以随着处理器数量的增加线性的提升，从而使仿真软件 能够在相同给定时间内模拟更多更大的网络流量。 一种实现能够进行分布式仿真的并行仿真软件的“传统 方法是“从零开始 创建一个全新的仿真软件 3 1 。有不少仿真软件都是以这种方法实现的，其中具有代 表性的有t e d 4 1 、s s f n e t 5 1 、g l o m o s i m 6 1 、t a s k i 函t 7 1 、r o s s n e t 8 】等。 s s f n e t 是一个i n t e m e t 网络协议的仿真和建模软件，以基于j a v a 和c + + 的s s f ( s c a l a b l es i m u l a t i o nf r a m e w o r k ) 的软件框架所组成。作为教育和科学研究用途的 s s f n e t 是开放软件，允许用户按需要进行补充和修改。开放源码提供面向对象的 可扩展仿真建模的并行运算环境，主要支持i p 包级别以上的细粒度仿真，链路层 和物理层的协议模型以独立的组件方式提供。s s f n e t 模型是一种自配置的仿真软 件，每一个s s f n e t 类能通过询问本地的配置数据库或者通过网络进行自主配置。 网络配置文件是用d m l ( d o m a i nm o d e ll a n g u a g e ) 来编写配置的，它被用来描述 一个完整的网络模型。在s s f n e t 软件中，被用作模拟主机和操作系统，特别是协 议的软件框架叫做s s f o s ；被用作模拟网络的连通性，建立主机结点和链路配置 的软件框架叫做s s f n e t 。s s f n e t 提供的协议支持包括： i p , t c p , u d p , s o c k e t , o s p f , b g p 4 ，h t t p 等等。 目前，s s f n e t 网络仿真软件可以支持的操作系统是w i n d o w s 2 0 0 0 及以上系列， u n i x 操作系统，l i n u x 操作系统等，对于追求实验的性能来讲推荐使用l i n u x 或 u n i x 操作系统。另外，d m l 语言配置方便，灵活；可以很好的定义所需的网络拓 扑结构。目前s s f n e t 也支持大多数网络协议，可以实现运行网络模型的功能。 s s f n e t 具有灵活的可扩展性，其配置语言d m l 具有自己的语法结构，用户 可以按照需要自己编写d m l 配置文件，设计网络拓扑结构模型。另外，用户可按 照s s f n e t 的a p i 自行定义编写所需要的新的网络模型或者协议。如：s s f o s i p 4 第一章绪论 就是被定义好的口协议类库。所定义的协议类库能够被d m l 调用，使得用户可 以自己扩展s s f n e t 仿真运行的结构环境，d m l 就是被定义在这些类库之上的。 s s f a p p w o r m 是可以被d m l 调用的蠕虫包，它是由美国依利诺州俄尔班纳香槟 城市大学的m i c h a e ll i l j e n s t a m 博士编写；由于它是开放代码，所以用户仍然可以 自行修改相关代码，设计蠕虫传播模型。 g l o m o s i m 是一种可调节的针对无线网络的仿真软件。g l o m o s i m 是以 p a r s e c 环境为基础而实现的。p a r s e c ( p a r a l l e ls i m u l a t i o nf o rc o m p l e xs y s t e m s 即面向复杂系统的并行环境) 是一种用c 语言编写的用于支持顺序和并行离散事 件的仿真模型。它也可以用作并行程序设计工具。p a r s e c 能够在多种系统平台 下运行，包括最新的u n i x 、l i n u x 和w i n d o w s 等。 与大多数网络仿真软件类似，g l o m o s i m 在设计上同样采用了类似于o s i 七层 模型的分层结构体系。g l o m o s i m 为层与层之间提供了简单的a p i ( 应用程序编程 接口) ，使由不同开发者开发的、处于不同层次的网络与协议模型能够快速的集 成到一起。从真实网络中提取的操作性的代码也能够很容易的按照层次结构继承 到g l o m o s i m 中，便于直接对真实网络环境进行模拟而不需要进行过多的抽象化 处理。例如，可以直接从f r e e b s d 系统提取代码来实现用于g l o m o s i m 的t c p 协 议模型。 g l o m o s i m 能够支持两种移动节点的模型。一种是按照随机选择的移动终点逐 步移动。这种节点会首先在被模拟场地内随机选择一个目的地，然后按照一定的 速度向其移动，当到达目的地以后则在短暂的停顿以后继续选择下一个目的地。 另一种是节点周期性的从与当前位置相邻的区域中随机选择一点作为下一周期所 处的位置。变换位置的周期可以通过配置文件设定。 使用“传统 方法开发仿真软件最大的好处就是仿真软件的每一个部分、每 一个功能都可以为并行计算而量身定做，分布式的设计可以融入到软件设计和实 现的每一个细节，通常能够获得极高的计算效率。然而这种开发方法也存在一个 明显的缺陷，那就是仿真软件的开发难度很大，开发过程需要的时间很长。在仿 真软件开发的过程中，除了需要实现仿真引擎、网络建模功能、以及其他相关工 具以外，还需要进行大量验证的工作。以这样的方式开发一个全新的仿真软件可 能需要很多人力花费多年的时间才能完成开发工作。 电子科技大学硕士学位论文 1 3 2 本文主要研究思路 开发分布式网络仿真软件的方法在“传统方法之后，近年来有人提出了一 种“联合 的开发方法，它是以现有的不具有分布能力的仿真软件为基础，重用 他们的仿真功能，并将他们通过某种方式将他们有机的结合在一起，以此来实现 能够分布运行的并行仿真系统。并行的仿真系统可以首先将一个完整的网络模型 分解为一组子模型，其中每个子模型包含原始网络中的一部分元素；然后启动一 个或多个现有的仿真软件，并将这些子模型分配给他们分别实例化后进行每个子 模型的仿真；最后，仿真系统会使用某些技术将分散到各个仿真软件实例的子模 型所产生的仿真结果收集和综合起来并集成为一个统一的仿真结果。这种“联合 的开发方法的优势之一是，可以把投入到和将继续投入到顺序执行的、不具有分 布功能的仿真软件的开发中的人力、物力和时间利用起来，而不会将已经投入了 的努力浪费掉，也不需要放弃并中止向处于开发中的仿真软件投入更多精力。此 外，利用多种不同的仿真软件集成构建仿真模型的方法，使得仿真系统可以取众 家之长，相互补充，例如可以充分发挥某些仿真软件的优势和具有的功能来代替 其他仿真软件的缺陷或者没有实现的功能，从而能够更加全面的构建网络模型。 按照“联合 的方法实现并行仿真系统的主要难点之一就是实现后的仿真系统是 否具有足够强大的仿真性能。就理论和初步的研究结果而言，使用“联合 的方 法确实能够为实现高效、大规模的并行网络仿真提供一种可行的方法。 使用“联合”方法最理想的效果是，仿真系统的使用者可以根据需要模拟的 网络模型和进行仿真的系统环境，从构成仿真系统的大量组件中选择和抽取某些 需要的组件，对这些抽取出来的组件进行自动的配置，然后应用组合在一起的组 件来构建大规模的网络模型。我们希望这样的仿真系统能够在各种系统平台上， 大到超级计算机、小到通过网络互联的工作站，都能够以高效率运行仿真。 本文参考“联合”的开发方法，以m p i 程序库作为并行计算和进程间通信的 支持，利用网络仿真软件n s 现有提供的网络仿真功能，设计和实现了一种并行仿 真系统。 1 4 本文的主要工作与章节安排 进行网络仿真是现今研究网络问题最有效的手段之一。一般进行小规模的网 6 第一章绪论 络仿真就能够获得关于网络问题的重要数据，但是对于某些问题却不得不针对大 规模网络进行仿真。由于传统仿真软件受到的各种限制，它们往往难以进行大规 模的网络仿真。开发分布式的仿真系统是解决大规模网络仿真问题的途径之一。 本文参考“联合 的开发方法，设计并实现了一种并行仿真系统。本文完成 的主要工作有： ( 1 ) 设计了并行仿真系统的总体框架，确定了将网络模型和网络仿真划分到各 个进程以及进程之间分工与协作的机制与策略，其中包括确立将网络模型 按照网络节点分割为多个网络子模型以及为每一个进程描述网络子模型 的方法、定义每一个进程描述网络子模型与配置仿真参数的接口、设计各 个进程之间相互通信与协作的机制。 ( 2 ) 为并行仿真系统设计了一种分层结构，将并行仿真系统的各项功能与模块 划分为网络子模型的仿真、进程分工与协作与数据分布的管理、并行计算 与进程间通信的底层支持等多个层次。层与层之间定义了一些接口，允许 相邻的层次通过这些接口相互访问。各个层次在功能上有明确的划分，在 实现上保持高独立性和低依赖性。 ( 3 ) 以m p i 为基础，对开源网络仿真软件n s 进行修改，使不具有并行计算功 能的n s 能够进行并行网络仿真。本文为并行仿真系统设计并实现了 p r o c e s s t a b l e 模块，在网络仿真开始之前对仿真数据与并行参数等进行初 始化，在初始化阶段控制每个进程的执行流程，在初始化结束后根据每个 进程的分工执行不同的任务。本文以p r o c e s s t a b l e 模块为核心，实现了用 来存储网络子模型以及关于进程间协作的各种数据的一系列模块。 ( 4 ) 确定了仿真进程之间的同步机制。本文对n s 的结构和原理进行了分析， 设计并实现了u n i f o r m s c h e d u l e r 类在仿真进程之间同步仿真时间，保持仿 真时间的一致性，保证被模拟的网络事件在仿真进程之间不会出现乱序的 现象。 ( 5 ) 在进程之间传递数据的流程中插入了序列化模块。各个进程在协作的过程 中需要相互通信，包括流程控制信息和n s 包数据传递等，其中包的数据 结构十分复杂，不能直接在进程问传递。序列化模块的功能是传递包数据 之前将结构复杂的包数据转换为能够直接在进程间传递的字节流、以及在 接收到字节流后将其还原为n s 定义的数掘结构。本文为序列化模块定义 了统一的接口并针对各种类型的包数据( 例如各种应用层数据) 实现了各 自的序列器。 7 电子科技大学硕士学位论文 ( 6 ) 向并行仿真系统加入了算法进程的功能，并定义了算法的编程接口。并行 仿真系统允许将所有进程划分为仿真进程、算法进程和中间进程等三组， 其中算法进程的功能是在仿真的同时实时的执行包括流量分析等在内的 各种算法。用户可以指定并行仿真系统在仿真的同时是否启动算法进程。 本文定义了算法进程的编程和配置的接口，允许用户选择需要执行的算 法、配置算法的参数以及按照接口的约定实现并添加自定义的新算法。本 文还设计了算法进程的管理模块，负责记录为每个算法进程指定的算法、 在仿真开始后执行预先指定的算法代码等。本文通过在仿真进程与算法进 程之间插入中间进程设置了汇聚仿真进程的仿真数据以及向算法进程提 供数据的接口。 本文后续章节的内容安排如下：第二章首先介绍为本文并行仿真系统提供并 行计算支持和进程间通信接口的m p i 程序库、以及网络仿真软件n s ，然后阐述并 行仿真系统的主要结构和框架；第三章涉及并行仿真系统使用的关键技术和实现 细节，首先介绍并行仿真系统进程分工的机制，引入算法进程的功能，然后阐述 仿真进程之间同步的方法和仿真数据的分布和传递方法，其次介绍并行仿真系统 管理算法进程的实现，最后介绍并行仿真系统中几个关键的辅助功能模块；第四 章在介绍了用于仿真的网络模型的背景和来源以后，使用本文的并行仿真系统进 行实际的网络仿真实验，通过仿真实验测试和验证并行仿真系统的功能和性能； 第五章首先阐述网络仿真的现状，然后对本文的工作进行总结，最后对网络仿真 进行展望，阐述今后我们还需要在网络仿真方面继续做出的努力。 第二章并行仿真系统的设计 2 1 引言 第二章并行仿真系统的设计 时至今日，仿真已经被广泛认为是分析网络行为的重要方法。尽管理论分析 的方法仍然能够应用于一些情况，但是由于需要进行诸多简化问题的假设，对于 越来越复杂的现代网络，纯粹的理论分析已经逐渐失效，最坏的情况甚至会导致 错误的结果。对于某些仍然使用理论分析手段的场合，仿真便成了验证分析正误 的重要方法。 仿真常常用于观察或验证某些特定协议或机制在多种网络环境中的作用或性 能。往往对小规模或中等规模的网络进行仿真就能获得研究者所需要的关键数据。 而对于某些协议、机制、或应用等，需要研究它们在大规模网络中真实表现。对 较小规模网络进行仿真常常难以获得有价值的或者正确的参考数据；只在各种大 流量背景下的仿真结果，才能成为理解它们在实际网络( 例如互联网) 中所能发 挥的实际效果的重要参考。例如，某大型网络服务提供者想了解使用广播会对网 络找出什么样的影响，那么就需要对足够大且包含足够规模的流量的网络进行仿 真，才能获得足够作为参考依据的数据。 我们的焦点主要放在基于包的网络仿真，对每个包或分组在网络中的传输过 程以及在节点等处的进出、队列情况进行建模。包层次的网络仿真被广泛的用于 协议的设计和评估。很多网络仿真软件都是针对包层次的仿真工具，其中包括本 文所涉及的n s 。 在实际的仿真应用中，仿真的网络规模( 网络节点和链路的数量或者流量的 大小) 主要受到两个因素的限制，其一是完成一次仿真所需要的内存容量，其二 则是完成所有计算量所需的时间。完成仿真所需的时间一般与需要仿真的流量成 j 下比。一般基于包的仿真软件都是以离散事件的方式来实现的，这些软件进行仿 真的过程就是处理一系列离散事件的过程。如果假设这些软件在仿真时处理每个 事件的平均时间是一个常数，那么仿真的时间消耗就会随着需要处理的事件数量 的增长而线性增大。在基于包的仿真软件中，需要处理的事件往往都是跟包相关 的计算，包括包在链路中的发送、接收、和进入缓冲区队列等事件。由此可见， 基于包的仿真软件完成一次仿真所需要的时间一般跟仿真过程中需要处理的包的 9 电子科技大学硕十学位论文 数量成正比。 对于某些协议、机制、或具体应用等，需要研究它们在大规模网络中会有怎 样的表现。对于这些问题，在较小规模网络进行仿真常常难以获得有价值的甚至 足够准确的参考数据；只在大网络或者大流量的背景下的仿真结果，才能成为理 解它们在实际网络( 例如i n t e r n e t ) 中能产生的实际效果的分析依据。进行大规模 网络的仿真的必要性由此可见。然而进行大规模网络仿真就必须要首先解决仿真 软件受到的各种限制的问题。 针对大规模网络仿真的问题，本章将重点介绍我们研究和开发并行仿真系统 ( 以下简称仿真系统) 的一种方法，该仿真系统的设计思路以及系统框架。 2 2 并行计算的底层支持 随着多处理器机或多计算机的生产和使用，为并行计算带来的潜在的加速比。 一台并行计算机( p a r a l l e lc o m p u t e r ，通常指专门设计的部件) 可以是一台具有多 个内部处理器的单计算机，也可以是多个互联的计算机构成一个一体的搞性能计 算平台。并行计算机主要有两种基本类型：共享存储器多处理机和分布式存储器 多计算机。其中分布式存储器多计算机是指通过计算机网络将多台完整的计算机 连接起来构成一个统一的系统，系统中的网络是用来在处理器之间传递消息和数 据的，这类系统通常简称为多计算机( m u l t i c o m p u t e r ) 。 针对并行计算机的消息传递机制，从上个世纪就有几种用于工作站网络的并 行程序开发包。其中第一个被广泛接受的将工作站网络作为多计算机平台的并行 程序丌发包是p v m ( 并行虚拟机) ，它是由美国o a kr i d g e 国家实验室在2 0 世纪 8 0 年代后期开发并在2 0 世纪9 0 年代被广泛使用。 为了促进更广泛的使用和并行程序的可移植性，学术界和产业界的合作伙伴 组决定联合研发一种他们希望成为“标准 的并行程序开发包和消息传递系统， 他们称其为m p i ( m e s s a g ep a s s i n gi n t e r f a c e ，消息传递接口) 【9 】。m p i 为消息传递 和相关操作提供库函数。m p i 的基本特征是，它定义了一个“标准”，但没有规 定具体实现。m p i 有超过1 2 0 个例程，而这个数量还在增长，一般并行程序经常 使用的接口仅仅是其中的一个子集。m p i 版本1 o 是在1 9 9 4 年5 月最后确定的， 版本1 2 是版本1 0 的增强版；1 9 9 7 年又推出了版本2 0 ( m p i 2 ) ，增加了动念进 程创建、单边操作和并行i o 。m p i 的函数可以被c 语言和f o r t r a n 语言调用，面 l o 第二章并行仿真系统的设计 向不同语言的接口具有相似的使用方法。所有的m p i 例程都已m p i 为前缀，而且 下划线后面的第一个字母都是大写的。这些例程的返回信息可以用来表示调用的 成功或失败。 m p i 标准已经有好几种免费的实现，其中典型的实现包括美国础印衄e 国家 实验室和密西西比州立大学的m p i c h ，俄亥俄超级计算机中心开发、n o t r ed a m e 大学维护的l a m 。此外还有h p 、i b m 、s g i 、s u n 等供应商提供的实现。现在已 经有了面向w i n d o w s 机群的实现。 在调用任何m p i 的其他函数以前，并行程序必须首先调用m p i “t o 对并行环 境进行初始化；而在所有的m p i 函数调用后，并行程序必须调用m p i _ f i n a l i z e 0 结束并行计算。开始时，所有进程将进入一个称为m p ic o m mw o r l d 的全局 通信空间，而且为每一个进程指定一个独有的序号，假设有p 个进程，则序号的 范围是从o 到p 1 。在m p i 术语中，m p ic o m mw o r l d 是一个通信子 ( c o m m u n i c a t o r ) ，它定义了一个通信操作的作用域。进程的序号是和通信子是 相对应的。m p ic o m mw o r l d 是所有进程在初始化时的默认通信子，然而通信 子的概念允许程序动态的创建其他的独立通信子和通信作用域。针对不同的应用 将通信的全局作用域划分若干子作用域，可以为用户带来通信环境的安全性，避 免不同作用域的通信操作相互干扰。 m p i 用来消息传递的函数以相互通信的进程数量可以分为点对点通信和集合 通信两种类型。点对点通信只涉及一个源进程和一个目的进程，这些进程分别通 过同属于一个通信子的进程序号指定。点对点通信函数提供了用于发送、接收、 等待和测试等操作的函数，并且定义了四种发送接收协议：标准、缓冲、同步 和就绪。这四种发送接收协议都可以用于阻塞和非阻塞的发送和接收例程。与 点对点通信相反，集合通信( c o l l e c t i v ec o m m u n i c a t i o n ) 的通信双方涉及一组进程。 这些进程是指同属于一个通信子的所有进程。进程集合通信时不需要指定进程序 号。集合通信中具有代表性的有： ( 1 ) 用于广播的m p ib c a s t o ； ( 2 ) 将数据汇聚的m p i _ g a t h e r ( ) ； ( 3 ) 将数据分散到各个进程的m p is c a r e r ( ) ； ( 4 ) 所有进程相互发送数据的m p ia l l t o a l l 0 ； ( 5 ) 将所有进程的数据合并为一个的m p ir e d u c e ( ) ； ( 6 ) 对所有进程进行同步的m p ib a r n e r ( ) ，等等。 电子科技大学硕士学位论文 2 3 网络仿真软件n s 2 3 1n s 简介 网络仿真对网络的设计人员有十分重要的意义。网络设计人员可以利用网络 仿真需要设计的复杂网络进行模拟的测试，然后根据测试仿真的结果决定当前的 设计是否可行以及需要进行哪些修改等等，进而避免由于设计的缺点而使网络在 铺设完毕并投入使用后发生不必要的问题。新开发的网络设备同样可以在实际架 设到真实网络之前通过仿真进行模拟运行的测试。类似的，网络的设计人员可以 通过仿真来测试将在网络中应用的各种机制，从而提高网络带宽的使用效率和数 据的传输速率等等。除了将仿真用于针对网络的设计和开发的辅助工具，还可以 作为面向网络工程的教学工具，使网络的各种行为可以通过仿真模型形象而直接 的反映出来。以o s i ( o p e ns y s t e mi n t e r f a c e ，即开放系统接口) 参考模型为原型 来实现其数据结构的仿真软件n s ( n e t w o r ks i m u l a