（通信与信息系统专业论文）基于遗传算法的多约束ospf路由方法研究.pdf

大连理工大学硕士学位论文 摘要 随着宽带坤技术的发展，像视频会议这样的多媒体业务得到了越来越多的应用。 一方面在这些业务中，很适合用组播的方式一次性地将报文传送到多个接收者，以节省 网络资源：另一方面这些业务都是一些实时性很强的业务，需要提供q o s 保障，而这 与现有的传统的路由过程不同，难以用经典的最短路径优先算法求解。 本文研究了遗传算法在o s p f 网络路由规划选择中的应用，重点研究如何快速求得 全局最优解并有效改善网络局部拥塞的问题。在此基础上，结合o s p f 网络路由的参数 特性，运用约束条件以确定搜索的方向，解决o s p f 网络路由选择困难的问题。其目的 在于探索和应用遗传算法为o s p f 网络路由的选择开辟一条新的途径。 本文叙述了o s p f 网络在当前和今后的信息社会发展中的重要地位，介绍了o s p f 网络的性质和路由特性，以及对其进行研究的重要性和必要性。分析了当前流行的一些 搜索方法。阐述了有关遗传算法的基本概念，如：建模、编码、杂交、变异等，并在适 应度函数值的引导下对复杂的解空间进行有效地搜索，直到获得最优的解。提出了基于 遗传算法的路由选择的新方法，考虑网络路由选择过程中必需满足q o s 的要求，满足 实时陛的要求等解决方法。结合遗传算法，提出了改进延时参数的搜索策略。并且通过 仿真实验，验证了该方法在解决链路拥塞问题上的有效性。 本文利用网络仿真软件o p n e t 对改进的路由选择策略进行了建模和描述，首先构 建一个o s p f 的节点系统。在m o d e l e r 工作平台上，将此系统作为网络模型对改进的路 由选择策略进行仿真，说明改进算法可以有效地均衡链路中的业务流量。 本文的最后对o s p f 路由选择算法的进一步设计提出了设想，并对其应用前景及未 来发展进行了展望。 关键词：遗传算法；0 s p f ；路由选择；0 1 斗i e t 垄王鎏篮璺鲨箜童丝壅箜坚堕宣塑鎏堕塞 r e s e a r c ho fm u l t i c o n s t r a i n to s p f r o u t i n gm e t h o d b a s e do n g e n e t i ca l g o r i t h m 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 ti nt h eb r o a d b a n dp t e c h n o l o g y , t h e r ea r em o r ea n dm o l e m u l t i m e d i aa p p l i c a t i o ni nt h ei n t e r a c t ，s u c ha sv i d e om e e t i n g o nt h eo n eh a n d ，t h e s en e w s e r v i c e sr e q u i r et h es u p p o r to fm u l t i c a s tc o m m u n i c a t i o nt or e d u c et h et r a f f i ci nt h en e t w o r k o n t h eo t h e rh a n d ，t h e r em u s tb eao o s ( q u a l i t yo f s e r v i c e ) g u a r a n t e e dm e c h a n i s m f o rt h e s er e a l t r i n e s e r v i c e s ，t h e y a r ed i f f e r e n tf r o mt r a d i t i o n a l m u t i n gi ne x i s t e n c e ，a n ds o l v i n gt h e mi n c l a s s i c a ls p f a l g o r i t h m s i sv e r yh a r d i n st h e s i sf o c u s e so nt h ea p p l i c a t i o no f g e n e t i ca l g o r i t h m s i nt h em u t i n gs e a r c ho fo s p f n e t w o r ka n de m p h a s i z e so nh o wt oi m p r o v ep e r f o r m a n c ei nc o n g e s t i o ni no r d e rt oo b t a i nt h e o p t i m a lg l o b a lr e s u l t t h eg e n e t i ca l g o r i t h m sc o m b i n e dw i t ht h ep a r a m e t e r s o fo s p f n e t w o r k ， u s i n gt h ec o n s t r a i n t st oc o n f u m t h ed i r e c t i o no ft h e r o u t i n g s e a r c ho fo s p f n e t w o r k ，s o l v et h e d i f f i c u l t i e si nt h ec h o i c ep r o b l e mf o rt h em u t i n go fo s p fn e t w o r k t h ep u r p o s ei st oa p p l y i n g g e n e t i ca l g o r i t h m sf o rt h er o u t i n gs e a r c ho fo s p f n e t w o r ka n dt oo p e nu pan e w p a t hf o rt h e r o u t i n g o fo s p fn e t w o r k t h ei m p o r t a n tr o l eo fo s p fn e t w o r ki nn o w a d a y sa n dh e r e a f t e ri n f o r m a t i o ns o c i e t yi s p r e s e n t e d t h ec h a r a c t e r so ft h eo s p f n e t w o r ka n dt h er o u t i n g , a n dt h ei m p o r t a n c ea n dt h e n e c e s s i t y a r ei n t r o d u c e d t h e np o p u l a r s e a r c h i n gm e t h o d s a r ed e s c r i b e da n dt h eb a s i c c o n c e p t i o n s o f g e n e t i ca l g o d t h r n s a r ee l a b o r a t e d ，s u c h a s p r o b l e mf o r m u l a t i o n , c o d i n g , c l o s s o v e r , m u t a t i o na n ds oo n u n d e rt h el e a d i n go ff i t n e s sv a l u e ，i tm a k e sa n e f f i c i e n t s e a r c h i n g i nc o m p l e x s p a c e s u n t i la c q u i r i n gt h eb e s tr e s u l t 。t h en e wm e t h o d so fm u t i n gs e a r c h o ft h eo s p fn e t w o r ka r es u g g e s t e d ，w h i c ha r eb a s e do i lg e n e t i ca l g o r i t h m sa n dt a k ei n t o a c c o u n tt h er e q u i r e m e n to fq o s p a r a m e t e r si nt h em u t i n g s e a r c ha n dt h es a t i s f a c t i o no ft h er e a l t i m e c o m b i n i n gw i t ht h eg e n e t i ca l g o r i t h m s ，as e a r c hs t r a t e g y t od i m i n i s hd e l a yp a r a m e t e ri s p u tf o r w a r d t h er e s u l t sf r o me m u l a t i o n t e s t sd e m o n s t r a t et h ea d v a n c e m e n ta n dp r a c t i c a l i t yo f t h e1 1 c wm e t h o di nc o n g e s t i o n t h i st h e s i sm o d e l sa n dp r e d i c t sn e t w o r kp e r f o r m a n c et oi m p r o v e dr o u t i n gs t r a t e g yu s i n g n e t w o r ks i m u l a t i o nt o o lo p n e t i td e s i g n e dan o d es y s t e mb a s e do no s p f t h e n t h i sn o d e s y s t e m i ss i m u l a t e di ni m p r o v e dr o u t i n gs t r a t e g yo nm o d e l e rp l a t f o r m a t l a s t ，t h ef u t u r ed e v e l o p m e n t o ft h eo s p f r o u t i n ga l g o r i t h m i sp o i n t e do u t t h ef u t u r eo f i ta n di t sd e v e l o p m e n ta r ea l s od i s c u s s e d k e y w o r d s ：g e n e t i ca l g o r i t h m s ；o s p f ；r o u t i n g ；o p n e t 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均己在论文中做了明确的说明并表示了谢 意。 作者签名：番叁整日期：竺三：! ：! ! 大连理工大学硕士学位论文 引言 随着i n t e m e t 的迅速发展，人们对网络通信的各种要求也不断的增加。作为网络连 接中最关键的设各一路由器，它的软件部分承载了巨大的职能，直接影响到网络连接的 性能和效率。路由器的软件部分就是指各种路由协议。网络安全问题的日益严峻，使我 国必须有产权完全属于自己的网络路由产品。同时，各种新的应用不断产生，如高带宽 的多媒体应用，包括网络视频会议、网络音频视频广播、股市行情发布、多媒体远程 教育、大规模协同计算等。这些应用带来了带宽的急剧消耗和网络拥塞问题。为了缓解 网络瓶颈，人们提出各种方案，其中一种就是研究路由器的动态协议o s p f ( o p e n s h o r t e s tp a t hf i r s t ，开放式最短路径优先1 的实现和改进工作。相比较而言，这种改进有 其独特的优越性，不必大幅的增加我国现有网络的主干带宽，就可较好豹改善网络传输 的拥塞问题。 遗传算法( g a ，g e n e t i ca l g o r i t h m s ) 是近些年来提出的一种新型优化算法，它具有并 行搜索、群体寻优的特点，已广泛用于解决各种具有n p 难度( n p h a r d ) 问题。作为一种 功能强大的网络仿真工具，o p n e t 能够用来建立网络通信系统的模型并且可以描述网 络行为。它的准确性以及使用的简单性使它成为网络设计者和管理者很有价值的工具。 本文是在遗传算法的基础上引入自适应方法协调路由器的选路，利用该算法的并行 搜索、群体优化的特点，提高了以网络传输延时和链路代价为主要指标的网络传输性 能，解决了路由选择的局域最优问题，并改善网络在一个周期内的拥塞问题。改进协议 的流程会用o p n e t 来演示，最终得出所要的结论。 本论文分为五个部分： 第一章主要介绍通信网络的发展背景、趋势和我国网络通信的研究构想，并根据网 络通信的发展趋势阐述了现有路由技术的可行的发展方向。 第二章介绍了路由器的工作和发展方向，详细的阐述了o s p f 协议的概念和原理， 对已有的算法进行了描述，指出现有算法存在的问题。 第三章是论文的重点，介绍了遗传算法原理、基本思想和基本步骤，讲述遗传算法 对o s p f 路由问题的建模、具体实现步骤和方法，并且研究改进算法的参数对实验结果 的影响。最后改进网络模型，提出对固定网络模型随机改变的方法。 第四章利用o p n e t 仿真软件建立改进的o s p f 协议网络模型，查看改进的算法在 路由问题中的协调链路均衡方面的作用。 第五章对论文进行整体性总结，并对相近的他人成果加以介绍。 一1 - 一 至主堑墨鲨塑墨塑壅旦! 登堕鱼查鎏翌壅 1 路由技术概述 1 1 网络通信的发展 当前计算机网络获得了飞速的发展。二十年前，很少有人接触过网络。现在，计算 机通信已成为社会结构的一个基本组成部分。网络被用于工商业的各个方面，包括广告 宣传、生产、计划、报价和会计等。结果，绝大多数公司拥有了多个网络。从小学到研 究生教育的各级学校都使用计算机网络为教师和学生提供全球范围的联网图书信息的即 时检索。从中央到地方的各级政府使用网络，各种军事单位同样如此。简而言之，计算 机网络已遍布各个领域。 网络的发展也是一个经济上的冲击。数据网络使个人化的远程通信成为可能，并改 变了商业通信的模式。一个完整的用于发展网络技术、网络产品和网络服务的新兴工业 已经形成，计算机网络的普及性和重要性已经导致在不同岗位上对具有更多网络知识的 人才的大量需求。在2 1 世纪，信息领域的竞争成为世界经济竞争的交点，而信息领域 的竞争不仅取决于技术的掌握，更取决于信息网络的建设及应用水平，特别是路由技术 作为新一代网络的主要技术之一，将发挥着越来越重要的作用。 1 _ 2 路由技术的发展与趋势 所谓路由技术，简单而言就是采用一种或多种策略，为数据分组从源地址到目的地 址的转发选择一条或几条理想的路径。路由技术是通过在路由设备( 如路由器等) 运行路 由协议来实现的，协议是路由器的精髓。通过路由器相互间的通信，每个路由器都建立 一个路由表，存放网络的路由转发信息。当路由器转发数据分组时，首先根据数据分组 的目的地址查找路由表表项，然后按表项中提供的相应下一站的地址对该数据分组进行 转发。 路由技术是计算机和通信技术相结合的产物，它随着网络的迅速发展而发展。在各 种网络中，i n t e m e t 的发展对路由技术的革新起到了关键的作用。在i n t e m e t 发展的初 期，它是以a r p a n e t 为核心的核心系统结构，其他网络通过核- t s , 路由器与 a r p a n e t ，主干网相连。当时的路由协议比较单一，功能也比较简单，比较典型的路 由协议有r i p 一1 和e g p 。但随着网络数量的增长，仍然要求其它网络与核心系统相连， 这既不现实也不可能。于是非核心系统体系结构应运而生，并引入了自治系统( a s ， a u t o n o m o u ss y s t e 曲的概念。这种非核心系统体系结构将整个i n t e m e t 划分为许多a s ， 2 大连理工大学硕士学位论文 每个a s 由不同的机构运营管理，在其内部使用自己的路由协议，并且可以独立于其他 a s 所选用的路由协议，随之产主了r i p 一2 ，o s p f 和b g p 4 为代表的一批路由协议。 路由技术发展到现在，很好地实现了异种网络之间互连的目的。以t c p i p 协议簇 为基础，几乎可以进行任何异种网络间的互连。相对于r i p 1 、e g p 等早期路由协议， 以r i p 一2 、o s p f 和b g p 4 为代表的路由协议在安全性、灵活性、稳定性和可扩展性等 方面有了极大的改善。 路由器从静态路由到自治系统内部动态路由协议再到自治系统边界路由协议，使网 络互连中的路由调整不再仅仅依靠人工操作，而是一旦工作人员配置完成后，网络上的 路由可以根据链路的状况和优先条件自动调整最佳路由并随着网络的变化而动态变化。 对于一个世界范围的网络，要保持它的互通，动态路由协议是必不可少的。 网络通信不断地迅猛发展直接使i n t e m e t 上产生了许多新的应用。其中不少是高带 宽的多媒体应用，譬如网络视频会议、网络音频视频广播、股市行情发布、多媒体远 程教育、大规模协同计算等。这就带来了带宽的急剧消耗和网络拥挤问题。 为了缓解网络瓶颈，业界专家一方面在已有的网络技术和网络运营经验的基础上寻 求新的网络解决方案，另一方面采用方案对现有路由技术进行改进。其中一种方案是改 变网络的软件部分，也就是对现有网络协议的改进。 o s p f 协议是目前i n t e m e t 广域网和i n t r a n e t 企业网采用最多，应用最广泛的路由协 议之一【1 】o 由此，o s p f 协议的改进，将对整个路由优化问题来说是非常必要并可行 的。 1 3 本文所做的工作 o s p f 所采用的链路状态算法基于局域最优思想，每个路由器为其转发的包选择某 种距离测度下的最短路径，并一直沿着此条最短路径发送【2 1 。但是由于网络业务量具有 无特征尺度的突发性，带宽资源经常可能处于相对稀缺的临界状态。在这种情况下， 基于局域最优的路由策略通常并不对应于全局的最优。本文提出的改进策略在遗传算法 的基础上引入自适应方法协调路由器的选路，提高了以网络传输延时和链路代价为主要 指标的网络传输性能，解决了路由选择的局域最优问题。 本文所作的主要工作具体如下： 1 对现有的几种路由算法进行分析，总结出其优点以及局限。 2 对s p f 算法计算中获得的不够尽如人意的结果，提出一种基于遗传算法的多约 束路由算法模型。 3 基于遗传算法的多约束o s p f 路由方法研究 3 对提出的改进算法在典型的网络通信模型下进行仿真，分析算法的性能。 4 针对现行o s p f 路由算法在链路拥塞条件下不能满足最优路径搜索要求的缺 点，进一步提出一种基于改变网络延时参数的模型，并在相同的环境下进行仿真以验证 此模型的性能。 4 一一 查垄翌三查堂巫主兰壁堕塞 2 路由器与o s p f 路由选择算法 2 1 路由器的发展趋势 2 1 1 路由器硬件体系结构的发展 随着i n t e r a c t 的普及、网络带宽的迅速增加和用户对服务质量要求的不断提高，通 信网络的规模、速度都已发生巨大变化，这些网络系统本身的变化导致作为网络核心的 路由器体系结构也发生了巨大变化。这种变化集中体现在从基于软件工作的单总线单 c p u 结构路由器发展到现在的基于硬件工作的交换式高性能路由器。 ( 1 ) 单总线单c p u 结构路由器 最初的路由器采用了传统计算机体系结构，包括共享中央总线、c p u 、内存及挂在 共享总线上的多个网络物理接口。 ( 2 ) 单总线主从c p u 结构路由器 采用主从两个c p u 的结构代替了原来仅一个c p u 的结构，从而较大幅度地降 氐了 c p u 的负荷，提高了处理速度。 ( 3 ) 单总线对称式多c p u 结构路由器 这种路由器可以说克服了第二类体系结构中的主要限制，因为它开始采用简单的并 行处理技术，即做到在每个接口处都有一个独立c p u ，专门负责接收和发送本接口的数 据包，管理接收发送队列、查询路由表做出转发决定等，而主控c p u 仅完成路由器的 配置、控制和管理等非实时功能。 ( 4 ) 多总线多c p u 结构路由器 第四类路由器至少包括三类以上总线和三类以上的c p u 。显然，这种路由器的结构 非常复杂，性能和功能也非常强大。 ( 5 ) 交叉开关交换式体系结构路由器 在交叉开关体系结构路由器中，数据直接从输入端经过交叉开关流向输出端。它采 用交叉开关结构替代共享总线，这样就允许多个数据包同时通过不同的线路进行传送， 从而极大地提高了系统的吞吐量，使得系统性能得到了显著提高。系统的最终交换带宽 仅取决于中央交叉阵列和各模块地能力。而不是取决于互连线自身。 ( 6 ) 共享并行处理器和全光空分交换结构 尽管第五类路由器的结构使得路由器性能大幅度的提高，但它的问题是：一方面需 要专用的a s i c 芯片使成本增加；另一方面当今的i n t e m e t 不断发展和变化，协议的标 5 一 堇主垄堡簦堡盟兰塑枣竺! 堡堕鱼查塑! 塞 准和用户的需求可能随时发生变化，而a s i c 不能很好而及时跟上并适应这种变化，从 而使产品的生命周期减小。第六类路由器就采用了并行处理、光交叉连接和网络处理器 等技术，使路由器的包转发速率和吞吐量迸一步提高【3 。 2 1 2 路由器软件体系结构的发展 路由器通过路由来决定数据的转发。转发策略可以是人为指定，但人为指定工作量 大，而且灵活性差，于是动态路由协议应运而生，通过传播、分析、计算、挑选路由， 来实现路由选择、路由切换和负载分担等功能。i n t e m e t 上现在运行的大量路由协议有 路由信息协议( r 口，r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 、开放最短路径优先协议( o s e f ，o p e n s h o r t e s tp a t h f i r s t ) 等内部网关协议( i g p ，i n t e r i o rg a t e w a yp r o t o c 0 1 ) 和边界网关协议 f b g p ，b o r d e rg a t e w a yp r o t o c 0 1 ) 等外部网关协议伍g p ，e x t e r i o rg a t e w a y p r o t o c 0 1 ) 。 ( 1 ) 基于i p v 4 的传统路由协议 目前大量使用的口网络，主要是基于i p v 4 协议栈。基于l p v 4 的路由协议如 r i p v l 、r i p v 2 、o s p f v l 、o s p f v 2 以及b g p v 4 等也大量应用于全球的路由器中，成为 网络互联的核心。 ( 2 ) 基于i d v 6 的传统路由协议 i p v 4 网络取得了巨大的成功，但它也有与生俱来的缺陷。这些缺陷主要体现在：地 址字段仅为3 2 位、安全性差、移动性不强、服务质量不高等。随着网络的发展和市场 的需求，i ”6 协议出现了。它吸收了i p v 4 的优点并解决了许多i p v 4 的不足之处【3 ，”。 2 2 路由器的硬件组成和软件策略 2 2 1 路由器的基本组成 路由器的基本组成可以分为四个功能模块：输入端口、输出端口、包转发或者交换 结构部分( s w i t c h i n gf a b r i c ) 以及路由计算或处理部分。 输入端口实现数据链路层的封装去封装，并按一定的路由查询算法，根据输入分 组的目的地址等参数来决定转发的目的端口。新式的路由器的输入端口还要对数据进行 业务归类，以便提供q o s ( q u a l i t y o f s e r v i c e ) 担保。 对于包转发或交换结构部分，最常见的交换结构是总线、c r o s s - b a r 和共享内存。总 线结构最为简单，但必须为共享数据传输通道花费一定的代价；c r o s s - b a r 结构相当于多 条并行工作的总线，但需要为流经它的数据不断进行o n o f f 切换，这就限制了交换的 速率。而在共享内存结构中，分组的交换是通过指针调用实现的，它受限于内存访问的 一6 大连理工大学硕士学位论文 速度。为了提供q o s ，输出端口也将执行相应的调度算法以支持不同的优先级，同时进 行数据链路的封澍去封装。 路由器拥有一张全网一致的路由表，它可以根据路由表和所连接的负载情况为数据 包的转发选择一条最佳路径。此最佳路径可能是代价最小、延时最小、可靠性最高( 丢 包率最小) 或者最短路径等。另一方面，路由表还用来在源和目的节点之间提供多条路 径。这给网络增加了容错性、冗余能力和负载均摊等。有些情况下，当网络发生拥塞 时，路由器还提供流控。 为了提高路由查询的速度，可以采用某些硬件技术，如内容寻址存储a ( c a m ， c o n t e l l t - a d d r e s s a b l em e m o r i e s ) 和高速缓存，或将逻辑控制器和存储器集成于单一器件 中，以缩短存储器的访问时间；还可以采用路由表压缩技术将路由表压缩后存放在处理 器的高速缓存中，大大提高查询速度。另外，还可以对数据结构和某些协议的路由选择 算法进行优化，继续缩短路由查询周期和提高最优路由选择的精确率1 3 ，”。 2 2 2 路由器的软件策略 ( 1 ) 距离一向量路由 路由器有两种基本的动态路由协议类型，第一种是距离一向量路由。这种路由类型 基于距离一向量算法( b e l l m a n f o r d ) 。采用本算法的路由器会周期性地把自己的路由表 拷贝传给与其直接相连的网络邻居。每一个接收者加上一个距离向量，或把它自己的距 离“值”加到表上，并把这个相加后的结果转发给它的直接邻居。此过程无定向地发生 在真接相连的路由器之间。这个一步一步的过程导致每一个路由器得到了其他路由器的 信息，最终形成个网络“距离”的积累视图。积累表用于更新每个路由器的路由表。 当这个过程完成时，每个路由器就学习到了到网络资源的“距离”的模糊信息。它不学 习和其他路由器相关的任何信息或网络的实际拓扑。 通常来说，距离一向量协议是非常简单的协议，容易配置、维护和使用。但在一定 环境下会产生路由问题。比如，当网络失败或发生其他变化时，路由器需要一些时间才 能收敛到对网络拓扑的重新认识。在收敛过程中，网络可能是脆弱的，产生不一致的路 由，甚至路由环。有许多措施来防止这些情况发生，但在收敛过程中，网络的性能仍处 于危险之中。因此，旧的收敛馒的距离一向量协议不适合于大的、复杂的广域网。这 样，随之产生的链路一状态路由算法就显示出了极大的优越性。 ( 2 ) 链路一状态路由 一7 一 茔王型童兰鲨塑童竺塞塑! ! 堕蜜查塑墅壅 链路一状态路由和距离一向量路由这两种动态路由协议类型的基本区别在于二者发 现和计算到目的地新路由的方式不同。链路状态路由算法，也就是最短路径优先( s p f ) 协议，可以维护一个复杂的网络拓扑数据库。与距离一向量路由协议不同，链路一状态 协议形成和维护网络路由器的全部信息，以及它们是如何互联的。可以通过和网络中的 其他路由器交换链路一状态通告( l s a ) 来实现这一点。交换了l s a 的每一个路由器于是 使用收到的l s a 建造一个拓扑数据库。s p f 算法用于计算目的她的可达性。计算的信 息用于更新路由表。这个过程能发现由于组件失败或网络变大而导致的拓扑变化。 实际上，l s a 交换由网络中的事件驱动，而不是周期性地运行，这样能大大减小收 敛过程，因为在这种情况下路由器没有必要等一系列计时器超时后才开始汇聚。 链路一状态路由作为动态路由可以适合任何大小的网络，使网络可以经得起任何不 可预知的网络拓扑结构变化。使用事件( 如变化事件) 来驱动更新( 而不是固定时间间隔 的计时器) 能使收敛在拓扑变化之后更快地进行。但链路一状态路由也有不足之处，它 对存储器和处理器敏感，并且可能在在网络传输线路上进行泛洪( n 0 0 0 ，因此会大大 削弱网络传输数据的能力【6 】。 2 3o s p f 协议分析 2 3 1o s p f 的原理 因特网工程任务组r i e t f ，i n t e m e te n g i n e e r i n gt a s kf o r c e ) 为了满足建造越来越大基 于m 网络的需要，形成了一个工作组，专门用于开发开放式的、链路一状态路由协 议，其中就包括o s p f 在内。o s p f 是专门设计用于自治系统之内的口路由协议。它不 能传输其他可路由网络如i p x 或a p p l e t a l k 的报文。如果用户的网络必须适用多种可路 由协议，就要考虑使用别的路由协议而不是o s p f 。 ( 1 ) 相关概念 路由器d ：用于标识每个路由器的3 2 位的二进制编码。 邻居路由器：分别有接口到一公共网络的两个路由器。两个路由器的邻居关系 通过呼叫协议来发现并维持。 邻接：交换路由信息的两个邻居路由器。 非广播网络：支持多个路由器，但没有广播能力的网络。在非广播网上o s p f 以两种方式运行。一种是非广播多点访问( m a ，n o n b r o a d c a s tm u l t i a c c e s s ) ，这种方 式模拟广播网上o s p f 的运作。第二种是点到多点，把非广播网络看成点到点链接的集 合。 8 大连理工大学硕士学位论文 链路状态宣告( l s a l ：描述路由器或网络本地状态的数据单元。 泛洪( h o o d m g ) ：用于分布和同步路由器之间的链路状态数据库的协议。 指定路由器( d r ) ：为网络产生l s a 并向公共网络传播链路状态信息。 后援指定路由器( b d r ) ：在d r 故障时接替d r 的路由器。 虚拟链路：虚拟链路是设置在两个域边界路由器之间，这两个路由器都有一个 端口与同一个非骨干区域相连。虚拟链路是为了实现其它域与骨干域相连。 存根区域：在o s p f 路由协议的链路状态数据库中，可以包括a s 外部链路状态 信息，这些信息会通过f l o o d i n g 传递到a s 内的所有o s p f 路由器上。但是，在o s p f 路由协议中存在这样一种区域，称为存根区域，a s 外部信息不允许广播进t 出这个区 域。 ( 2 ) o s p f 工作流程 o s p f 路由协议的工作流程如图2 , 1 。 图2 1o s p f i 作流程图 n g 2 1o s p f w o r kf l o wg r a p h 9 基于遗传算法的多约束o s p f 路由方法研究 当一个路由器启动时，它首先初始化路由协议数据结构。然后使用呼叫协议获取邻 居。每个路由器向它的邻居发送呼叫协议包，并接受邻居发来的呼叫协议包。在广播和 点对点网络上，路由器通过发送呼叫协议包到多播地址址ls p f r o u t e r s ( 2 2 4 0 0 5 、来动 态地探测邻居路由器：在非广播网络上发现邻居需要一些配置信息。在广播和n b m a 网络上，呼叫协议包还用来选举网络中的d r 。路由器和其发现的部分邻居来建立邻接 关系，每个路由器的邻居可以在它的l s a 中反映出来，这样，可以及时地发现“死” 路由器。链路状态数据库是在邻接路由器间同步的。在广播和n b m a 网中，d r 和 b d r 与所有的路由器都有邻接关系。邻接控制路由信息的分布，路由更新包只在邻接 问发送和接受。路由器周期性地宣告它的链路状态。当路由器的状态发生变化时，它的 链路状态也要宣告到域中。各璐a 被泛洪到整个域。泛洪算法必须是可靠的，以保证 同一域内的所有路由器有相同的链路状态数据库。路由器根据此链路状态数据库以自己 为根来计算最短路径树，从而产生一个路由表。 2 3 2o s p f 的路由更新机制 o s p f 使用l s a 在o s p f 节点之中共享路由信息。这些广播信息会在整个区中进行 传播但不会超越一个区。 因此，区中的每一个路由器都知道本区的拓扑。然面，一个区的拓扑对区外是不可 知的。考虑到实际上有四种不同类型的o s p f 路由器：区内路由器、区边界路由器、自 治系统边界路由器、骨干路由器。很明显每种路由器类型有不同的对等实体集，路由器 与这些对等实体交换l s a 。 ( 1 ) 内部区路由器 内部的区路由器必须直接和区中的其他路由器交换l s a ，其中包括每一个区内部路 由器，电包括作为区成员的区边界路由器。图2 2 显示了一个o s p f 网络中，在整个区 1 中转发或泛洪l s a 的情形。需要重点注意的是相同区中的o s p f 路由器无需彼此直接 相连就能共享l s a 信息。o s p f 路由器直接把l s a 报文发送到区中每一个知道的路由 器，并且使用任何可用的链路来转发那些报文。 ，1 0 一 大连理工大学硕士学位论文 踏由器 8 图2 2 在自治系统1 内的泛洪 h g 2 2h o o d i nn o 1a s ( 2 ) 区边界路由器 区边界路由器( a s b r ，a u t o n o m o u ss y s t e mb o r d e rr o u t e 0 负责在数据库中为它们接口 所连的每个区维护拓扑信息。因此，如果一个区边界路由器互联了两个不同的区，它必 须和两个网络中的对等实体交换l s a 。和区内部路由器一样，这些l s a 直接寻址并传 输到区中的对等实体。图2 3 显示了这一点。 o s p f 加强性能的另一个特点是路由汇总。关于一个区的拓扑信息，并不和区外的 路由器共享。相反，区边界路由器汇总了所有与其相连的所有区中的地址。这个汇总的 路由数据通过l s a 报文与其相互联的每个区中的对等路由器实现共享。o s p f 使用几种 不同类型的l s a ，每种有不同的功能。用于共享汇总路由数据的l s a 为类型3 l s a 。 在图2 3 中，区边界路由器直接把汇总的数据广播给区o 中的所有路由器。o s p f 不允许大于或等于1 的区之间相互连接。所有这样的互联必须通过区o 。因此，其含义 是区边界路由器把一个非0 编号的区来与区0 互联。 路 ( 3 ) 骨干路由器 潞由瓣 图2 3 区边界路由器引起的自治系统内l s a 泛洪 f i g 2 3a s b rc a u s i n g l s af l o o di na s 1 1 藤翩路安憋 囊一胀 基歹献漱 基于遗传算法的多约束o s p f 路由方法研究 骨干路由器( f r ，f r a m e w o r kr o u t e r ) 负责维护骨干拓扑信息，并且为自治系统中的每 个其他区传播汇总的拓扑信息。图2 4 显示了由骨干路由器交换l s a 的情形。 虽然骨干路由器、区边界路由器和区内部路由器之间的差别看起来是清楚的，但由 于路由器能支持到其他路由器的多i o 端1 3 连接，三者还是会引起混淆。理论上讲，每 个端口可以连至一个不同的区。所以，路由器可以在其连接的不同区之间形成边界。 路由嚣 图2 4 骨干路由器引起的自治系统内l s a 泛洪 f i g 2 4 f i r c a u s i n g l s af l o o di na s 路由潞 2 4o s p f 中采用的路由计算方法 有关路由表的计算是o s p f 的核心内容，它是动态生成路由器内核路由表的基础。 在路由表条目中，包括有目标地址、目标地址类型、链路路由代价、链路存活时间、链 路类型以及下一跳等内容1 7 8 ，9 】。 o s p f 能使用下面两种相当简单的方法之一计算链路的路由代价： o s p f 能自动计算使用每个路由接口的代价。 非带宽敏感的缺省值可以用于每一个o s p f 接e l 。 不管使用哪种方法，任何一条路由的代价可以通过把路由上遇到的每个路由器接1 ：3 代价相加得到。在o s p f 的最短路径树中记录了每一个已知目的地的代价。 2 4 1 自动计算路由 o s p f 能自动计算一个接口的代价，这个算法以每个接口类型支持的带宽为基础。 一条路由上所有接口计算值的和( s u m ) 形成o s p f 路由决定的基础。基于冗余链路上可 获得的带宽，这些值能使o s p f 计算出最小代价的路由。如图2 5 中的网络显示了这一 点。 - 1 2 盔垄望三查塑圭堂篁墼 图2 5 自动计算的路由代价 h 叠2 5a u t o m a t i c a l l yc a l c u l a t i n gm u t i n g c o s t 在图2 5 中，位于网络1 9 3 1 。3 。0 中的主机与位于网络1 9 3 1 4 0 终端系统之间的广域 网路由代价为1 3 8 ( 图中开销即为代价) 。这个代价是这两个网络之间两条t 1 链路的代 价和( 每条6 4 ) ，再加上以太网接口至网络1 9 3 1 a 0 的代价。在起点和终点的以太网接口 代价不包含在o s p f 代价计算中，这是因为o s p f 只计算向外的路由器接口代价。表 2 1 汇总了图2 5 中每个被使用接口自动计算得出的代价值。 表2 1 每个接口类型的计算路由代价 ! 垒坠! ：! 壁! ! 坚坦坚旦g 曼唑堕翌g ! 竺12 11 兰竺z 鱼婪! 旦堕竺哑 接口类型代价 1 0 0 m b p s f d d i1 1 0 m b p s e t h e m e t1 0 1 5 4 4 m b p st 1 串行链路 6 4 5 6 k b p s 串行链路 1 7 6 8 2 4 2 使用缺省路由代价计算路由 有一些环境会接受使用缺省路由代价。比如，用户的网络由类似的传输线路组成， 那么缺省值将是可接受的。另外。管理员能手动地为某个特定接口修改代价度量。这样 会使网络管理员在主要仍使用缺省路由代价的前提下，对网络的流量模式进行合理地规 划。 ( 1 ) 同构网络 一1 3 至主鎏堡簦鲨塑墨丝塞鱼! 塑堕宴查鲨堑塞 在同构网络中，所有的传输线路是一样的。比如，所有的l a n 接口都是1 0 m b p s 的以太网，所有w a n 接口都是t l 。在这种情形下，使用缺省值不大会引起路由问 题。这一点在几乎没有或有很少路由冗余的情况下是非常正确的。 如图2 6 中的网络图就显示了这一点( 图中开销即为代价) 。 图2 6 使用o s p f 缺省路由代价值 f i g ，2 石u s i n go s p f d e f a u l t r o u t i n g c o s t 在图2 6 中，缺省值1 7 6 8 分配给每一个接口。然而所有的w a n 链路是t 1 。考虑 到所有的值都一样，那么分配值为1 1 2 8 、1 7 6 8 还是1 0 0 0 0 0 0 就没太大关系! 同构网络 中的路由决定变成简单计算和比较跳数，不管网络中有多少路由冗余，这一点都是正确 的。显然，在有相当多路由冗余并且使用不同的传输技术的网络中，缺省值将不会选出 到任何目的地的最优路由。 ( 2 ) 手动设置值 在一些网络中，希望接受o s p f 缺省路由，之后手动地设置那些不同于缺省链路的 特殊链路值。比如，用户网络的缺省代价值可能是1 7 6 8 5 6 k b p s 串行链路的计算值。 如果网络中只有一条或两条链路不提供相同的带宽，就能接受缺省值之后为那些特殊链 路设置其他值。是使用自动计算的路由代价，还是缺省代价，或是手动配置的代价对 o s p f 节点而言都是不重要的。它们会接受所有这样的代价值并计算得到网络的最短路 径树。 2 4 3 使用最短路径树计算路由 各种l s a 复制的目的是使路由器能构造网络拓扑视图。这个拓扑以树的方式安 排。o s p f 路由器形成树的根。这个树给出至日所知目的地地址的完整路径，虽然只有下 - 1 4 - 大连理工大学硕士学位论文 一跳用于转发报文。其中的原因是简单的，记录到目的地的完整路径使冗余路径的比较 和选择最好路径成为可能。如果有多条相同代价的路径，它们会被o s p f 发现并使用， 流量在这些可用链路中大致取得均衡。 图2 7 具有路由代价的o s p f 网络 h g 2 7o s p f n e t w o r kw 捌hm u t i n gc o s t 为了更好地理解最短路径树( s e t ，s h o r t e s tp a t ht r c e ) 的概念，考虑图2 7 中的网络 ( 图中开销即为代价) 。图中的简单网络是一个小型o s p f 网。网络管理员已经启动了路 由代价的自动计算。需要重点注意的是路由器5 和6 之间的以太网构成了网络1 9 3 1 5 0 和1 9 3 1 6 0 通过路由器2 的另一条路径，所以，o s p f 自动计算的代价为1 0 ，而相似的 代价没有分配到其它的以太网上。 这个网络的最短路径树会随路由器的不同而变化。图2 8 是从路由器3 的角度看到 的树。从图中可以明显地看出，树结构使至d 给定目的地路由代价的计算简化。根路由器 ( 路由器3 1 9 3 1 3 o ) 能很快地