（计算机科学与技术专业论文）多故障网络环境下路由协议性能的计算机仿真分析.pdf

北京邮电大学硕士研究生学位论文 多故障网络环境下路由协议性能的计算机仿真分析 摘要 随着信息技术的不断发展以及对人类生活各个方面影响力的日 益加深，社会各部门、各领域对互联网的依赖程度也空前提高，在这 种情况下，对提高网络的生存、抗毁和自愈能力以及更加灵活的业务 分级转发策略展开研究具有重大的战略价值与现实意义。 抗毁路由项目的目标是在已有路由协议的基础上，设计一种新的 路由协议，它能够在极端网络环境，既故障频繁的情况下实现自适应 网络环境能力的业务分级服务和优先级控制，以及快速保护倒换，因 此需要研究o s p f 路由协议的原理和特点作为以后工作的基础；同时， 项目实现的协议要移植到仿真平台上进行演示和验证，因此需要比较 各个常用的仿真软件，为项目选择合适的仿真平台，并了解其上路由 协议的运行机制，为以后的移植做准备；分析s s f n e t 中o s p f 路由协 议在极端环境下的性能是为了给项目以后做环路避免和快速收敛等 工作提供参考依据。 本文首先对o s p f 路由协议的工作原理进行了详细分析。其次， 对各种仿真工具进行了分析、比较，通过对几种主流仿真工具在结构、 性能以及对各种协议支持方面的细致分析比较，完成了仿真平台选 型。最后，详细分析了s s f n e t 中o s p f 路由协议的的实现机制和工作 流程，并对o s p f 的路由收敛进行分析。 对路由收敛的分析主要包括故障类型对路由收敛时间和控制消 息带宽消耗量的影响；收敛过程中临时环路的生成情况；定时器设置 对临时环路和路由收敛时间的影响。通过仿真实验可以看出故障类型 对控制消息带宽消耗量的影响可以忽略不计。减小各个定时器的值可 以加快路由收敛的速度，减小收敛时间。本文的工作主要体现在两个 方面：第一，将多种类型网络故障对协议性能的影响纳入研究范围； 第二，对路由收敛速度与路由环路数量、持续时间之间的关系进行了 深入分析。 关键词：仿真o s p f 路由协议s s f n e t 性能分析 北京邮电大学硕士研究生学位论文 s i m u l a t i o na n aiy s eo fr o u t i n g p r o t o c o lp e r f o r m a c eu n d e r m u 皿一r u i tn e t w o r ke n v i r o n m e n t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g yo nh u m a nl i f e a l l s e c t o r so fs o c i e t yb e c o m em o r ea n dm o r er e l i a n c eo nt h ei n t e r n e t t h e f a i l t u r eo rb r e a k d o w no ft h en e t w o r kc a np r o d u c en e g a t i v ei m p a c to no u r l i f e i nt h i sc a s e t h er e s e a r c ho fi m p r o v i n gt h es u r v i v a b l ea n d s e l f - r e c o v e r ya b i l i t yo fn e t w o r ka n dm o r ef l e x i b l et r a n s m i ts t r a t e g yo f s e r v i c ec l a s s i f i c a t i o nh a st h es i g n i f i c a n ts t r a t e g i cv a l u e 1 h ea i mo ft h i sp r o j e c ti st od e s i g nan e wp r o t o c o lb a s e do ne x i s t i n g r o u t i n gp r o t o c 0 1 t h en e wp r o t o c o lw i l li m p l e m e n ts e v e i c ec l a s s i f i c a t i o n ， p r i o r i t yc o n t r o la n df a s tp r o t e c tr o t a t ew h e nt h e r ei sm u c hf a i l t u r ei n n e t w o r k ，s oa u t h o rn e e dt or e a s e r c ht h ep r i n c i p l eo fo s p et h en e w p r o t o c o ls h o u l di m p l e m e n to ns i m u l a t o rt ov a l i d a t ea n dd e m o n s t r a t e s o a u t h o rn e e dt oc o m p a r et h ee x i s t i n gn e t w o r ks i m u l a t o ra n dk n o w nt h e m e c h a n i s mo fr o u t i n gp r o t o c o lo ns i m u l a t o rt oc h o s et h es u i t a b l eo n ef o r p r o j e c t f i n a l l y , a u t h o rn e e dt oa n a l y s et h ep e r f o r m e n c eo fo s p e 1 h ew o r ko ft h i s p a p e ri s a sf e l l o w s t a t e f i r s t l y , a n a l y s et h e p r i n c i p l e ，i n t e r f a c es t a t em a c h i n e ，n e i g h b o rs t a t em e c h i n ea n dt i m e ro f 0 s p es e c o n d l y , c o m p a r et h ed i f f e r e n c eo fs o m ee x i s t i n gs i m u l a t o ra n d c h o o s et h es s f n e ti nt h e e n d f i n a l l y , a n a l y s e t h ei m p l e m e n t i o n m e c h a n i s mo fo s p fi ns s f n e t i nt h i sp a p e r , a u t h o ra n a l y s eh o wt h et y p eo ff a i l t u r ea f f e c tt h e c o n v e r g e n tt i m ea n db a n d w i d t hw a s t a g eo fo s p fc o n t r o li m f o r m a t i o n ， a n dt h et e m p o r a r yr i n g - p a t hi nt h ep r o c e s so fc o n v e r g e n c e ，a n dh o wt i m e r a f f e c tt h e t h e t e m p o r a r yr i n g p a t h a n d c o n v e r g e n tt i m e t h r o u g h s i m u l a t i o ne x p e r i m e n t ，a u t h o rc a n sc o n c l u dt h a tt h et y p eo ff a i l t u r ed o e s i i i 北京邮电大学硕士研究生学位论文 n o th a v et h ei n f l u e n c et ot h eb a n d w i d t hw a s t a g eo fo s p fc o n t r o l i m f o r m a t i o n a n dr e d u c i n gt i m e r sv a l u et ob ep o s s i b l et or e d u c et h e c o n v e r g e n tt i m e t h ew o r ko ft h i sp a p e ri sa sf e l l o ws t a t e f i r s t l y , a u t h o r c o n s i d e r st h ei n f l u e n c eo fn e t w o r kf a i l t u r e t y p et op r o t o c 0 1p e r f o r m a n c e s e c o n d l y , a u t h o ra n a l y s et h er e l a t i o n s h i pb e t w e e nr o u t i n gc o n v e r g e n c e s p e e da n dt h en u m b e ra n dd u r a t i o nt i m eo ft e m p o r a r yr i n g p a t h k e yw o r d s ：s i m u l a t i o n ，o s p fr o u t i n g p r o t o c o l ， s s f n e t ， p e r f o r m a n c ea n a l y z e i v 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：么壅日期： 力孵7 玎 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：圣塑：主垒 日期：迦墨：主：丕 北京邮电大学硕七研究生学位论文 1 1 研究背景 第一章绪论 随着信息技术的不断发展以及对人类生活各个方面影响力的日益加深，社会 各部门、各领域对互联网的依赖程度也空前提高，而这种趋势仍然在以惊人的速 度发展。网络基础设施已经成为关系国计民生的重要战略资源，网络中发生的故 障或损毁，都会在不同程度上对生产和生活产生负面影响。在自然灾害、战争等 极端环境下，网络设施受到大规模破坏，可用网络资源的总量会被极大削弱，救 灾、指控等业务的重要性急剧上升，对服务质量提出了更高的要求。如何保障重 要业务、数据的顺畅传递是提高网络资源利用率的另一个重要方面。现有业务分 级转发策略的基本思想，是在网络资源总量以及各种业务相对优先级稳定的前提 下，根据业务等级制定固定的资源分配策略。但在极端环境下，救援、抢险、指 挥调度等业务的相对重要性会大大高于平时，仍然沿用传统的分级转发策略将很 难为此类业务提供可靠的保障。 网络生存能力的核心是具备快速抗毁自愈能力的路由技术，而提高极端环境 下重要业务服务质量得关键是建立自适应网络环境变化的资源配置策略。因此， 对提高网络的生存、抗毁和自愈能力以及更加灵活的业务分级转发策略展开研究 具有重大的战略价值与现实意义。 抗毁路由项目的目标是在已有路由协议的基础上，设计一种新的路由协议， 它能够在极端网络环境，既故障频繁的情况下实现自适应网络环境能力的业务分 级服务和优先级控制，以及快速保护倒换。协议不仅要在l i n u x 平台上实现，而 且要移植到仿真平台上进行演示和验证，因此需要为项目选择合适的仿真平台， 并了解其上路由协议的运行机制，为以后的移植做准备。 网络仿真也被称为网络模拟，就是用计算机程序对通信网络进行模型化，通 过程序的运行模仿通信网络的运行过程。网络仿真软件通过在计算机上建立一个 虚拟的网络平台，来实现真实网络环境的模拟，网络技术开发人员在这个平台上 不仅能对网络通信、网络设备、协议、以及网络应用进行设计研究，还能对网络 的性能进行分析和评价。另外，仿真软件提供的仿真运行和结果分析功能使开发 人员能快速、直观的得到网络性能参数，为优化设计或做出决策提供更便捷、有 效的手段。在仿真分析中，计算机可追踪网络设计方案中的每一个细节，显示各 细节变动所带来的结果，同其他形式的分析相比仿真分析更加现实和便捷，仿真 结果也更直观和易于理解。 第1 页 北京邮电大学硕士研究生学位论文 不同的仿真工具适用的范围都是不同的，例如有的仿真软件适用于大规模仿 真，有的适合用于a dh o c 网络仿真，还有的适用于传感器网络。我们应根据需 要选择合适的仿真工具，扩展其功能、开发新的网络仿真模块。本文的研究和分 析工作主要基于计算机仿真结果，目的是根据对多种主流仿真软件性能评测结果 的分析来选取适用于抗毁路由项目的仿真工具，了解其上路由协议的运行机制。 1 2 本文的研究工作 论文是本人在参加了项目组的研发工作的基础上，根据本人对项目的前期调 研和分析总结而成，论文主要对o s p f 路由协议的原理，各个仿真软件的特性和 s s f n e t 上o s p f 的实现等方面进行了研究，主要包括以下几点： ( 1 ) 本文在收集、翻译和阅读了国内外大量有关o s p f 路由协议和各种仿 真软件的文献资料的基础上，对现有使用人数较多的几种仿真软件进行了详细分 析； ( 2 ) 通过实验挑选适用于项目的仿真工具。 ( 3 ) 详细分析了s s f n e t 中o s p f 路由协议的的实现机制和工作流程，并对 o s p f 的性能进行测试，包括控制消息带宽消耗量，路由收敛时间，以及链路发 生故障，网络重新收敛时，临时环路的生成情况以及影响其生成的因素。 1 3 论文的组织结构 本论文的内容安排如下： 第一章是研究背景和论文的组织机构。 第二章对o s p f 路由协议进行了概述，包括它的工作原理和特点。 第三章讨论和分析了使用人数较多的几种仿真软件，包括它们各自的结构特 点，还包括了对仿真工具的定性和定量的比较。 第四章分析了o s p f 在s s f n e t 中的实现机制，包括实现了哪些功能以及具体 的函数代码。 第五章对s s f n e t 中的o s p f 进行性能测试。分析了链路发生故障，网络重新 收敛时，临时环路的生成情况和故障类型对路由收敛的影响。最后总结了得出的 结论。 第六章对整篇文章进行总结。 第2 页 北京邮电大学硕士研究生学位论文 第二章o s p f 路由协议研究 o s p f 路由协议是项目涉及的一个重要协议，所以首先要了解它的特性，本 章主要介绍了o s p f 的工作原理，协议包的结构和类型等方面。 2 1o s p f 概述 o s p f 协议是一种为口网络开发的内部网关路由选择协议，由i e t f 开发并 推荐使用。o s p f 协议由三个子协议组成：h e l l o 协议、交换协议和扩散协议。 其中h e l l o 协议负责检查链路是否可用，并完成指定路由器及备份指定路由器； 交换协议完成“主 、“从 路由器的指定并交换各自的路由数据库信息；扩散协 议完成各路由器中路由数据库的同步维护。 o s p f 是一种基于链路状态的路由协议，需要每个路由器向其同一管理域的 所有其他路由器发送链路状态广播信息。在o s p f 的链路状态广播中包括所有接 口信息、所有的量度和其他一些变量。利用o s p f 的路由器，首先必须收集有关 的链路状态信息，然后根据此信息建立一个链路状态数据库( 即全网的拓扑结构 图) ，最后根据一定的算法计算出到每个节点的最短路径，构造出自己的路由表。 o s p f 启动 i j 一 i 发送h e l l 。包发现邻居，在广播和n b m a 网络中还需选出d r 和b d r 否， 交换链路状态数据库信息，并泛洪出去 j 根据链路状态数据库信息生成最短路径树 上 生成路由表 上 根据链路状态的变化动态维护路由表 图2 - 1o s p f 工作流程图 o s p f 将一个自治域再划分为区，相应地即有两种类型的路由选择方式：当 第3 页 北京邮电大学硕十研究生学位论文 源和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时，则采用 区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。当一个区内 的路由器出了故障时并不影响自治域内其他区路由器的正常工作，这也给网络的 管理、维护带来方便。 o s p f 有四种路由器：( 1 ) 内部路由器：所有端口在同一区域的路由器，维 护一个链路状态数据库；( 2 ) 骨干路由器：具有连接主干区域端口的路由器；( 3 ) 区域边界路由器( a b r ) ：具有连接多区域端口的路由器，一般作为一个区域的出 口。a b r 为每一个所连接的区域建立链路状态数据库，负责将所连接区域的路 由摘要信息发送到主干区域，主干区域上的a b r 则负责将这些信息发送到各个 区域；( 4 ) 自治域系统边界路由器( a s b r ) ：至少拥有一个连接外部自治域网络 ( 如非o s p f 的网络) 端口的路由器，负责将非o s p f 网络信息传入o s p f 网络。 o s p f 有五种分组类型：( 1 ) 类型1 ：问候( h e l l o ) 分组用于建立和维护邻 站的可达性；( 2 ) 类型2 ：数据库描述( d a t a b a s ed e s c r i p t i o n ) 分组，向邻站提供 自己的链路状态数据库中的所有链路状态项目的摘要信息；( 3 ) 类型3 ：链路状 态请求( 1 i n ks t a t er e q u e s t ) 分组，向对发请求发送某些链路状态项目的详细信息； ( 4 ) 类型4 ：链路状态更新( 1 i n ks t a t eu p d a t e ) 分组，用洪泛法对全网更新链路 状态；( 5 ) 类型5 ：链路状态确认( 1 i n ks t a t ea c k n o w l e d g e m e n t ) 分组，对链路更 新分组的确认。 o s p f 常用的l s a 有六种：( 1 ) 类型1 ：路由器l s a ，r o u t e rl s a 描述了路 由器物理接口所连接的链路或接口，指明了链路的状态，代价等。每个o s p f 区 域内的路由器均会产生此l s a 。它只在产生的区域内泛洪；( 2 ) 类型2 ：网络 l s a ，n e t w o r kl s a 是由d r 或b d r 发送的，它描述了o s p f 区域中的路由器， 只在产生的区域内泛洪；( 3 ) 类型3 ：网络汇总l s a ，n n e t w o r ks u m m a r yl s a 是由a b r 发出的，它将某个区域的汇总告知其他区域；( 4 ) 类型4 ：a s b r 汇 总l s a ，用来通告a s b r 所处的位置；( 5 ) 类型5 ：自主系统外部l s a ，a u t o n o m o u s s y s t e me x t e r n a ll s a 由a s b r 产生，用来通告自治系统外部的路由，它在整个 o s p f 自治系统内泛洪；( 6 ) 类型7 ：n s s a 外部l s a ，和类型5 的l s a 作用一 样，只是出现在n s s a 区域中。 2 2o s p f 状态机 2 2 1 接口状态机 下图是接口状态机( i n t e r f a c es t a t em a c h i n e ) 的状态转移图，它描述的是 个接口从接入o s p f 域，到发现邻居，最后和邻居建立邻接关系，并竞选d r b d r 的过程。 第4 页 北京邮电大学硕士研究生学位论文 图2 2 0 s p f 接口状态机 ( 1 ) d o w n ：这是接口的初始状态，这时下层协议指出接口为断开，接口上 没有协议流量的收发。这时，接口上的所有参数都被设为初始值，关闭所有的接 口记时器，该接口上也没有相关联的邻接。 ( 2 ) l o o p b a c k ：这时，路由器到网络的接口处于回环( l o o p b a c k ) ，回环可 能以硬件或软件的方式实现。回环接口不能用于正常的数据传输，但仍能通过 i c m pp i n g 或位错误检测来收集接e l 信息。口包仍需要被发往回环接e l 。为此， 要在r o u t e r - l s a 中宣告此接口为接口i p 地址的主机路径。 ( 3 ) w a i t i n g ：在此状态时，路由器试图判定网络上d r 和b d r 。为此，路 由器对其接收到的h e l l o 包进行监听。在结束等待前，路由器不能被选举为d r 或b d r 。这可以避免不必要地改变d r 和b d r 。 ( 4 ) p o i n t t o p o i n t ：这时，连接到物理点对点网络或虚拟通道的接口开始 工作。进入此状态之后，路由器试图与邻居路由器形成邻接。并按h e u o i n t e r v a l 的间隔发送h e l l o 包。 ( 5 ) d r o t h e r ：广播或n b m a 网络上的其他路由器被选举为d r ，其自身 也没有被选为b d r 。路由器开始与d r 和b d r ( 如果存在的话) 形成邻接。 ( 6 ) b a c k u p ：在此状态时，路由器是所接入网络的b d r 。并将在当前的 d r 失效时成为d r 。该路由器与接入该网络的所有其他路由器形成邻接。在洪 泛过程中，b d r 的工作与d r 稍有不同。 ( 7 ) d r ：在此状态时，路由器是所接入网络的d r 。该路由器与接入该网 络的所有其他路由器形成邻接。路由器必须为网络节点生成一个n e t w o r k l s a 。 该n e t w o r k l s a 包含了所有接入该网络的路由器( 包括d r 自身) 。 2 2 2 邻居状态机 o s p f 路由协议通过建立交互关系来交换路由信息，但是并不是所有相邻的 路由器会建立o s p f 交互关系。下面将o s p f 建立a d j a c e n c y 的过程简要介绍一 下。 第5 页 北京邮电大学硕士研究生学位论文 o s p f 协议是通过h e l l o 协议数据包来建立及维护相邻关系的，同时也用其 来保证相邻路由器之间的双向通信。o s p f 路由器会周期性地发送h e l l o 数据包， 当这个路由器看到自身被列于其它路由器的h e l l o 数据包里时，这两个路由器之 间会建立起双向通信。在多接入的环境中，h e l l o 数据包还用于发现指定路由器 d r ，通过d r 来控制与哪些路由器建立交互关系。 两个o s p f 路由器建立双向通信后的第二个步骤是进行数据库的同步，数据 库同步是所有链路状态路由协议的最大的共性。在o s p f 路由协议中，数据库同 步关系仅仅在建立交互关系的路由器之间保持。 o s p f 的数据库同步是通过o s p f 数据库描述数据包( d a t a b a s ed e s c r i p t i o n p a c k e t s ) 来进行的。o s p f 路由器周期性地产生数据库描述数据包，该数据包是 有序的，即附带有序列号，并将这些数据包对相邻路由器广播。相邻路由器可以 根据数据库描述数据包的序列号与自身数据库的数据作比较，若发现接收到的数 据比数据库内的数据序列号大，则相邻路由器会针对序列号较大的数据发出请 求，并用请求得到的数据来更新其链路状态数据库。 o s p f 相邻路由器从发送h e l l o 数据包，建立数据库同步至建立完全的o s p f 交互关系的过程分成几个不同的状态，分别为： ( 1 ) d o w n ：这是o s p f 建立交互关系的初始化状态，表示在一定时间之内 没有接收到从某一相邻路由器发送来的信息。在非广播性的网络环境内，o s p f 路由器还可能对处于d o w n 状态的路由器发送h e l l o 数据包。 ( 2 ) a t t e m p t ：该状态仅在n b m a 环境，例如帧中继、x 2 5 或a t m 环境 中有效，表示在一定时间内没有接收到某一相邻路由器的信息，但是o s p f 路由 器仍必须通过以一个较低的频率向该相邻路由器发送h e l l o 数据包来保持联系。 ( 3 ) i n i t ：在该状态时，o s p f 路由器已经接收到相邻路由器发送来的h e l l o 数据包，但自身的i p 地址并没有出现在该h e l l o 数据包内，也就是说，双方的 双向通信还没有建立起来。 ( 4 ) 2 - w a y ：这个状态可以说是建立交互方式真正的开始步骤。在这个状 态，路由器看到自身已经处于相邻路由器的h e l l o 数据包内，双向通信已经建立。 指定路由器及备份指定路由器的选择正是在这个状态完成的。在这个状态，o s p f 路由器还可以根据其中的一个路由器是否指定路由器或是根据链路是否点对点 或虚拟链路来决定是否建立交互关系。 ( 5 ) e x s t a r t ：这个状态是建立交互状态的第一个步骤。在这个状态，路由 器要决定用于数据交换的初始的数据库描述数据包的序列号，以保证路由器得到 的永远是最新的链路状态信息。同时，在这个状态路由器还必须决定路由器之间 的主备关系，处于主控地位的路由器会向处于备份地位的路由器请求链路状态信 第6 页 北京邮电大学硕士研究生学位论文 息。 ( 6 ) e x c h a n g e ：在这个状态，路由器向相邻的o s p f 路由器发送数据库描 述数据包来交换链路状态信息，每一个数据包都有一个数据包序列号。在这个状 态，路由器还有可能向相邻路由器发送链路状态请求数据包来请求其相应数据。 从这个状态开始，我们说o s p f 处于f l o o d 状态。 ( 7 ) l o a d i n g ：在l o a d i n g 状态，o s p f 路由器会就其发现的相邻路由器的新 的链路状态数据及自身的已经过期的数据向相邻路由器提出请求，并等待相邻路 由器的回答。 ( 8 ) f u l l ：这是两个o s p f 路由器建立交互关系的最后一个状态，在这时， 建立起交互关系的路由器之间已经完成了数据库同步的工作，它们的链路状态数 据库已经一致。 灰色是稳定状态， 2 3o s p f 协议工作过程 图2 - 3o s p f 邻居状态机【6 】 o s p f 有三种通信类型：域内路由域问路由外部路由。 s p f 路由协议针对每一个区域分别运行一套独立的计算法则，对于a b r 来 说，由于一个区域边界路由器同时与几个区域相联，因此一个区域边界路由器上 会同时运行几套o s p f 计算方法，每一个方法针对一个o s p f 区域。下面对o s p f 协议运算的全过程作一概括性的描述。 ( 1 ) 区域内部路由 当一个o s p f 路由器初始化时，首先初始化路由器自身的协议数据库，然后 等待低层次协议( 数据链路层) 提示端口是否处于工作状态。 如果低层协议得知一个端口处于工作状态时，o s p f 会通过其h e l l o 协议数 据包与其余的o s p f 路由器建立交互关系。一个o s p f 路由器向其相邻路由器发 送h e l l o 数据包，如果接收到某一路由器返回的h e l l o 数据包，则在这两个o s p f 路由器之间建立起o s p f 交互关系，这个过程在o s p f 中被称为a d j a c e n c y 。在广 第7 页 北京邮电大学硕士研究生学位论文 播性网络或是在点对点的网络环境中，o s p f 协议通过h e l l o 数据包自动地发现 其相邻路由器，在这时，o s p f 路由器将h e l l o 数据包发送至一特殊的多点广播 地址，该多点广播地址为a l l s p f r o u t e r s 。在一些非广播性的网络环境中，我们 需要经过某些设置来发现o s p f 相邻路由器。在多接入的环境中，例如以太网的 环境，h e l l o 协议数据包还可以用于选择该网络中的指定路由器d r 。 一个o s p f 路由器会与其新发现的相邻路由器建立o s p f 的a d j a c e n c y ，并且 在一对o s p f 路由器之间作链路状态数据库的同步。在多接入的网络环境中，非 d r 的o s p f 路由器只会与指定路由器d r 建立a d j a c e n c y ，并且作数据库的同步。 o s p f 协议数据包的接收及发送正是在一对o s p f 的a d j a c e n c y 间进行的。 o s p f 路由器周期性地产生与其相联的所有链路的状态信息，有时这些信息 也被称为链路状态广播l s a ( l i n ks t a t ea d v e r t i s e m e n t ) 。当路由器相联接的链路 状态发生改变时，路由器也会产生链路状态广播信息，所有这些广播数据是通过 f l o o d 的方式在某一个o s p f 区域内进行的。f l o o d i n g 算法是一个非常可靠的计 算过程，它保证在同一个o s p f 区域内的所有路由器都具有一个相同的o s p f 数 据库。根据这个数据库，o s p f 路由器会将自身作为根，计算出一个最短路径树， 然后，该路由器会根据最短路径树产生自己的o s p f 路由表。 ( 2 ) 域问路由 前面描述了o s p f 路由协议的单个区域中的计算过程。在单个o s p f 区域中， o s p f 路由协议不会产生更多的路由信息。为了与其余区域中的o s p f 路由器通 讯，该区域的边界路由器会产生一些其它的信息对域内广播，这些附加信息描绘 了在同一个a s 中的其它区域的路由信息。具体路由信息交换过程如下： 在o s p f 的定义中，所有的区域都必须与区域o 相联，因此每一个区域都必 须有一个区域边界路由器与区域0 相联，这一个区域边界路由器会将其相联接的 区域内部结构数据通过s u m m a r y l i n k 广播至区域0 ，也就是广播至所有其它区域 的边界路由器。在这时，与区域0 相联的边界路由器上有区域0 及其它所有区域 的链路状态信息，通过这些信息，这些边界路由器能够计算出至相应目的地的路 由，并将这些路由信息广播至与其相联接的区域，以便让该区域内部的路由器找 到与区域外部通信的最佳路由。 ( 3 ) a s 外部路由 一个自治域a s 的边界路由器会将a s 外部路由信息广播至整个a s 中除了 残域的所有区域。为了使这些a s 外部路由信息生效，a s 内部的所有的路由器 ( 除残域内的路由器) 都必须知道a s 边界路由器的位置，该路由信息是由非残 域的区域边界路由器对域内广播的，其链路广播数据包的类型为类型4 。 第8 页 北京邮电大学硕士研究生学位论文 第三章网络仿真软件的介绍 仿真工作是基础性工作，路由项目的根基。在仿真之前，首先要选取适合项 目的仿真工具。仿真软件按照发行渠道划分，可以分为商业软件和科研用软件， 前者代表有o p n e t ，c o m n e ti i i ，后者有n s 2 ，j - s i r e ，p a r s e c ，o m n e t + + 等。商业软件价格昂贵，不具有开放性，但提供了比较全面的建模和协议支持。 科研用软件是一些具有开放性的软件包，既作为网络建模和仿真工具研究开发的 一部分，又作为网络研究的共享资源，为网络研究者提供了研究的平台和工具， 但功能不如商用软件完善。因为目前大多数人使用的都是免费的科研用软件，所 以本章将主要介绍使用人数较多的几种仿真软件n s 2 ，j - s i m ，s s f n e t 和 o m n e t + + 。 3 1 n s 2 n s 2 ( n e t w o r ks i m u l a t o r ，v e r s i o n2 ) 是一种面向对象的，开源的离散事件模拟 器。其本身有一个虚拟时钟，所有的仿真都是由离散事件驱动的。n s 2 的功能强 大，模块丰富，是目前网络研究领域应用最广泛，使用人数最多的仿真软件之一。 有调查显示，使用n s 2 的人数约占使用仿真工具的人数的8 8 8 。n s 2 可以用 于仿真各种不同的i p 网，已经实现的一些仿真有：网络传输协议，比如t c p 和 u d p ：业务源流量产生器，比如f i t 、t e l n e t 、w e bc b r 和v b r ；路由队列管理 机制，比如d r o p t a i 、r e d 和c b q ；路由算法，比如d i j k s t r a 等。n s 2 也为进行局 域网的仿真而实现了多播以及一些m a c 子层协议。n s 2 为包级仿真，只研究链 路层及以上协议。它提供对协议的多级抽象，以满足对不同协议层的研究。n s 2 更注重低级协议仿真，监视和分析包踪迹和队列行为。 3 1 1n s 2 的结构 n s 2 使用的是分裂对象模型，即采用系统编程语言( c + + ) 和脚本编程语言 ( o t c l ) 共同开发，其软件体系结构如下图所示在此模型中，n s 2 作为o t c l 脚 本解释器，由事件调度器、网络组件对象和网络组装模块库组成其中，事件调 度器和网络组件，即协议的详细化实现由c + + 完成，从而可以高效地管理字节和 包头，并实现在大量数据集合上的算法：仿真配置由t c l 实现，以便迅速改变配 置参数和设置场景，使性能和灵活性得到均衡。 第9 页 北京邮电大学硕士研究生学位论文 事件调度器 n s 2 t e l d网络组件 。他l 1 1 8 o 图3 - 1n s 2 的体系结构 3 1 2n s 2 的组件 n s 2 的每一次模拟均需要用类s i m u l a t o r 的一个简单实例来控制和执行模拟。 这个类提供了一套接口用于配置一次模拟和为这次模拟选择一个时问调度方案。 一个模拟脚本通常以创建这个类的实例开始，然后调用各种方法创建节点，管理 拓扑结构和设置模拟的其他方面【。 当一个新的模拟对象在t c l 脚本中创建时，初始化过程将执行以下操作： 1 ) 初始化包格式： 2 ) 创建一个事件调度器； 3 ) 创建一个空代理； n s 2 是一个事件驱动的模拟器。它支持四种调度器，每种都是由不同的数据 结构实现的：一个简单的链表( as i m p l el i n k e d 1 i s t ) ，堆( h e a p ) ，时间队列( c a l e n d a r q u e u e ) ，和一种叫做“实时( r e a l t i m e ) 的特殊类型。调度器的工作方式是：选 择下一个最早事件，执行完它，然后返回继续执行下一个事件。如果在同一个时 刻有多个事件需要执行，那么他们的执行将按照先调度先分配的原则执行。同时 发生的事件将不被调度器重新排序，所有的调度器对应同一输入应该产生相同的 分派顺序。 在n s 2 中，一个“包 是由一个报头( h e a d e r ) 堆栈( s t a c k ) 和一个可选 择的数据空间构成。报头的格式，在模拟器对象( s i m u l a t o r ) 创建的过程中创建 好，同时，所有注册过的报头，比如一般的属性说明、i p 报头，t c p 报头，r t p 报头，都在包的报头堆栈中存储。通过不同报头在包的报头堆栈中的偏移量 ( o f f s e t ) ，网络组件可以根据需要，来访问包中的不同报头。在报头格式创建的 时候，无论这个注册过的报头是否需要，都被加到报头堆栈中。通常，一个包只 含有报头堆栈部分，而没有数据空间。这是因为，在模拟的环境中，传输实际的 数据是没有意义的。 n s 2 的网络组件分为基本网络组件和复合网络组件。n s o b j e c t 是所有基本网 络组件的父类，而它本身的父类是t c l o b j e c t 类。这个类的对象有一个基本的功 能，就是处理数据包( p a c k e t ) 。所有的基本网络组件可以划分为2 类，分类器 第1 0 页 北京邮电大学硕士研究生学位论文 ( c l a s s i f i e r ) 和连接器( c o n n e c t o r ) 。它们都是n s o b j e c t 的直接子类，也是所有 基本网络组建的父类。分类器属于“交换设备 。当接受到一个分组时，节点需 要检查分组的某些域( 通常是它的目的地址，有时也可能是它的源地址) ，然后 寻找与这个域的值相匹配的接受者。在n s 2 中，这个工作是由c l a s s i f i e r 对象完 成的，n s 2 中有各种不同的c l a s s i f i e r 对象，分别负责检查分组的不同部分，来 完成不同的匹配，筛选工作，c l a s s i f i e r 是节点( n o d e ) 的重要组成部分。分类器 的功能是从逻辑上匹配一个分组，并基于匹配的结果把该分组传递到相应的对 象，每个c l a s s i f i e r 都包括一个由s l o tn u m b e r 作索引的对象表。c l a s s i f i e r 的工作 就是检查收到的分组的s l o tn u m b e r ，然后把分组转发给由该s l o tn u m b e r 索引的 对象。分类器的派生类组件对象包括地址分类器( a d d r c l a s s i f i e r ) 和多播分类器 ( m c a s t c l a s s i f i e r ) 等。连接器的工作过程是：收到一个分组，对分组做相应的 处理，然后将分组递交给t a r g e t 对象，或者将分组丢弃。它是一个单进单出的“管 道。n s 2 中有很多不同种类的c o n n e c t o r 类的派生类，每种完成不同的功能， 它们通过重载c o n n e c t o r 类的r e e v 0 函数来完成自己的功能。连接器的派生类组 件对象包括队列( q u e u e ) ，延迟( d e l a y ) ，各种代理( a g e n t ) ，和追踪对象类( t r a c e ) 等。连接器的特点是：基于连接器的基本网络组件只有一个可能数据输出的路径， 即( 单进单出的管道，所以叫c o n n e c t o r ) ，和分类器有1 个或多个可能的数据输 出路径( s w i t c h ) 是不同的。复合组件( 如n o d e 和l i n k ) 不是t c l o b j e c t 类的派 生类，而是在n s 2 中独立的类。 从协议的层次上看，n s 2 与o s i7 层模型以及t c p i p 模型的对应关系如下： a p p l i c a t i o n t c p 1 l j d p i p n e t w o r k a c c e s s a p p l i c a t i o n a g e n t n o d e l i n k a p p l i c a t i o n p r e n s e n t a t s e s s i o n t r a n s p o r t n e t w o r k d a t e l i n k p h y s i c a l 图3 - 2n s 2 与o s i7 层模型以及t c p i p 模型的对应关系 ( 1 ) a p p l i c a t i o n 是对建立在传输代理层上的应用程序的模拟。n s 2 中有两 种类型的“应用程序”，数据源发生器( t r a f f i cg e n e r a t o r ) 和模拟的应用程序 ( s i m u l a t e da p p l i c a t i o n s ) 。 ( 2 ) a g e n t 代表了网络层分组的产生和接收，以及各协议的实现。 第1 1 页 北京邮电大学硕上研究生学位论文 ( 3 ) 节点( n o d e ) 和链路( 1 i n k ) 是组成网络拓扑的两部分。n o d e 是由一 个结点入口对象和若干个分类器组成的一个复合组件。它通过多个分类器实现了 对所有接收到的数据包进行判断是否进行转发或传送到a g e n t 的功能。l i n k 是由 一系列的连接器逐步构成。它实现了队列、时延、记录t r a c e 等一系列的仿真问 题。 3 2 j s i m j - s i m ( 也叫做j a v a s i m ) 是开源的，基于组件的复合仿真环境，它建立在自 治构件体系结构( a u t o n o m o u sc o m p o n e n ta r c h i t e c t u r ea c a ) 的概念上，其基本组 成单元是自治构件( a u t o n o m o u sc o m p o n e n t s ) 。j - s i m 支持多种脚本语言，如p e d ， t c l 和p y t h o n