（计算机软件与理论专业论文）基于遗传算法的ospfv3路由算法研究.pdf

东北大学硕士学位论文摘要 基于遗传算法的o s p f v 3 路由算法研究 摘要 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 是i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r o e ) 于 1 9 8 8 年提出的一种基于链路状态算法的动态路由协议，它是用于i p v 4 网络自治系 统内部的内部网关协议。随着i p v 6 协议的发展和使用，出现了o s p f v 3 。它主要用 于解决i p v 6 数据包的路由问题而提出的新版本路由协议，它仍然沿用s p f 算法来 生成组播树。s p f 算法没有考虑所选路径的带宽、时延、时延抖动、丢包率等参数 ； 是否满足实际应用的需要，又由于搜索的局限性，没有充分利用全网可用路径，所 以s p f 算法没能更好的平衡网络流量。 本文主要利用遗传算法来解决s p f 算法的上述缺点。首先介绍了路由器及路由 选择协议的基本原理。接下来分析了o s p f 路由协议的工作原理和o s p f 采用的路 由计算方法。阐述了有关遗传算法的基本概念，如：建模、编码、杂交、变异等， 并在适应度函数值的引导下对复杂的解空间进行有效地搜索，直到获得最优的解。 最后对基于遗传算法的o s p f v 3 路由算法进行了设计、实现、分析与仿真。 灏键词：遗传算法，o s p f v 3 ，路由选择，s p f ，o p n e t i i 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho fo s p f v 3r o u t i n gm e t h o db a s eo ng e n e t i c a l g o r i t h m a b s t r a c t o s p f ( o p e ns h o r t e s t p a t hf i r s t ) i sad y n a m i cr o u t i n gp r o t o c o lp u tf o r w a r db y i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) i n1 9 8 8 ，i sb a s e do nl i n ks t a t ea r i t h m e t i c a n d u s e da sa ni g p ( i n t e r i o rg a t e w a yp r o t o c 0 1 ) r o u t i n gp r o t o c o lf o ri p v 4n e t w o r k 。w i t ht h e d e v e l o p m e n ta n de m p l o y m e n to fi p v 6p r o t o c o l ，o s p f v 3c o m e sf o r t ht os u p p o r tt h ei p v 6 n e tw o r k 。i ti san c wv e r s i o no fd y n a m i cr o u t i n gp r o t o c o l ，w h i c hi sr o o ti no s p ei ti s m a i n l yu s e dt os o l v et h ep r o b l e mo fi p v 6d a t ap a c k a g er o u t i n ga san e wv e r s i o nr o u t e p r o t o c o l ，a n di ts t i l lu s e st h es p fa r i t h m e t i ct oc r e a t em u l t i c a s tt r e e b u ts p fa r i t h m e t i c d on o tc o n s i d e re n o u g hw h e t h e rb a n d w i d t h ，t i m e - d e l a y , t i m e d e l a y , m i s s i n gp a c k a g er a t e c a ns a t i s f yt h ep r a c t i c a ld e m a n d a n db e c a u s eo fs e a r c hl i m i t ，t h e r ei sn o te n o u g hn e t r e s o u r c e ；t h es p fc a nn o tb e t t e rb a l a n c et h en e t w o r kf l o w t h ep a p e r m a i n l y s o l v e sh o wt ou s et h eg e n e t i ca r i t h m e t i ct os o l v et h e d i s a d v a n t a g eo fs p et h ef i r s tp a r ti n t r o d u c e st h et h e o r yo fr o u t e ra n dr o u t i n gp r o t o c 0 1 t h es e c o n dp a r ta n a l y s e so s p fr o u t i n gp r o t o c o lw o r kp r i n c i p l ea n da r i t h m e t i c , a n d d e p i c t st h eb a s ec o n c e p t i o no fg e n e t i ca r i t h m e t i c ，s u c ha sm o d e l i n g ，c o d i n g ，c r o s s i n g ， a b e r r a n c ea n ds oo i l u n d e rt h eg u i d eo ft h ea d a p t i n gf u n c t i o n ，g e n e t i ca r i t h m e t i cc a n p r o c e s se f f e c t u a ls e a r c h i n gi nc o m p l i c a t e ds o l u t i o ns p a c e ，u n t i li tc a nf i n dao p t i m i z e d s o l u t i o n t h el a s tp a r ti n t r o d u c e st h ed e s i g n ，i m p l e m e n t ，a n a l y s i s ，a n de m u l a t i n go ft h e o s p f v 3r o u t i n gp r o t o c o lb a s e do ng e n e t i ca r i t h m e t i c k e yw o r d s ：g e n e t i ca r i t h m e t i c ，o s p f v 3 ，r o u t i n gp r o t o c o l ，s p f ，o p n e t i l l 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名：王彖擘 签字日期： 7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名： 互东肇 导师签名：鸣酰写 签字日期： 伽7 - f - 签字日期： 2 一叼q - 矿 东北大学硕士学位论文 第一章绪论 第一章绪论 1 1 研究背景 传统的互联网是基于i p v 4 协议的网络，该协议的成功运用使得互联网的用户呈 高速增长。但是，随着用户的不断增加，以及各种新业务的出现，网络地址匮乏成 为制约互联网发展的瓶颈。此外，随着互联网应用要求的提高，i p v 4 在服务质量、 移动性和安全性等方面的支持也突显乏力。为了解决i p v 4 存在的诸多问题，1 e t f 在9 0 年代中期提出了拥有1 2 8 位地址的i p v 6 互联网协议，并在1 9 9 8 年进行了进一 步的标准化工作。除了对地址空间的扩展以外，i p v 6 还提供了自动配置以及对移动 性和安全性的更好支持。 为普及i p v 6 ，世界知名的设备制造商、运营商和研究机构联合发起成立了i p v 6 论坛，并从1 9 9 9 年开始，每年举行2 3 届i p v 6 全球峰会，还与u m t s 论坛：3 g p p e 以及欧洲通信标准委员会建立了合作关系。同时，i e t f 于1 9 9 6 年建立全球范围的 试验床6 b o n e ，对1 1 6 协议特性进行了研究并积累了i p v 6 组网经验。1 9 9 8 年底， 面向实用的全球性i p v 6 研究和教育网6 r e n 开始启动。所有的这些努力极大地推动 了i p v 6 的商用化进程。 我国不是互联网的发源地，i p 地址资源匮乏更显突出，加上人口稠密，以及近 年来经济和信息技术的快速发展，对地址不足的压力比较敏感，为此，我国政府对 基于i p v 6 技术的下一代互联网的研究和应用非常关注和重视，启动了一系列的研究 项目。1 9 9 9 年底中国教育和科研网c e r n e t 与诺基亚公司合作启动了i p v 6 互联网 i n t e m e t 计划，形成一个大规模的i p v 6 研究和试验网络，开展了许多开拓性的研究。 在8 6 3 计划中，迸一步提出了有关高性能i p v 6 路由器关键技术及系统开发的课题。 高性能的路由器可能应用于各种环境，它必须提供多种路由协议，包括r i p , o s p f ，i s i s 以及b g p 等内部和外部网关路由协议。其中o s p f 协议是为t c p i p 网络设计的自治系统内的路由协议，目前其版本为3 。随着网络拓扑的日趋复杂自 治系统通信内的要求越来越高，o s p f 协议己经成为i n t e r a c t 路由体系结构的基础。 为了能够很好支持未来多媒体业务的需要，充分研究多种约束条件下o s p f v 3 是很 有必要的，为此，本文提出了基于遗传算法的o s p f v 3 路由算法研究。 东北大学硕士学位论文第一章绪论 1 2 选题意义 o s p f v 3 是在o s p f v 2 的基础上随着i p v 6 发展而来的。由于i p v 4 和i p v 6 的协 议的不同，使得o s p f v 3 在o s p f v 2 的基础上做了许多改动。但o s p f v 3 与o s p f v 2 一样，也是使用s p f 算法来产生从源到目的节点的最短路径。随着多媒体业务的广 泛应用，传统的s p f 算法己不能很好适应多媒体发展的需求，这种不适应主要体现 在s p f 算法不能完全在多种约束条件下产生最短路径以及更好的均衡网络流量。因 此本文尝试用遗传算法来产生在满足多种约束条件下的最短路径。 1 3 本论文研究内容及结构安排 本论文共分六章。其内容大致如下： 第一章：绪论，讲述了课题的提出及研究背景 第二章：主要讲述了路由器的工作原理，并简单介绍了各种常见的路由协议 第三章：详细分析了o s p f 路由协议的工作原理、路由更新机制以及所采用的 路由计算方法，并简要介绍了最短路径优先算法和q o s 问题 第四章：介绍了基本遗传算法的特点及解决问题的基本步骤 第五章：进行了基于遗传算法的o s p f 路由数学描述，构建了o s p f v 3 路由问 题的网络模型及网络拓扑图的数据结构 第六章：实现具体的算法并进行仿真验证所得出的结论 最后进行总结。 东北大学硕士学位论文 第二章路由器与路由选择协议 第二章路由器与路由选择协议 2 1i p v 6 协议简介 i n t e r n e t 工程任务委员会( i e t f ) 于1 9 9 1 年开始致力于新协议的研究工作，欢 迎所有对新协议有兴趣的团体、个人来参加标准的制定，并将新协议初步命名为“新 一代i p 协议”i p n g ( i p - t h en e x tg e n e r a t i o n ) 。到1 9 9 2 年2 月为止，共提出了 三种主要的i p n g 候选方案，它们是“i n t e r n e t 通用体系结构”( c a t n i p ) 、“简单增 强i p ”( s i p p , s i m p l ei pp l u s ) 和“大地址空间上的t c p 和u d p ”( t u b a ) 。由 于三种提案都各有优缺点。最后，i e t f 建议融合和修改s i p p 与t u b a 以形成新一 代的i p 协议基础。该协议以s i p p 为主，加入了t u b a 的自动配置与过渡特性。因 为目前使用的i p 协议版本号为4 ，而版本号5 已被指派给了一个名为s t 的试验性 协议( s t 是与i p 并行使用，传输实时服务数据流的协议) ，故i p n g 就被正式命名 为i p v 6 。 作为新一代的网络协议，i p v 6 有许多前所未有的特点【1 l ： ( 1 ) 地址空间巨大：i p v 6 具有长达1 2 8 位的地址空间，有2 1 2 8 个地址，相当 在地球表面每平方米有6 7 万亿个地址。 ( 2 ) i p v 6 对流和资源预留的支持：i p v 6 报头的格式里，有2 0 位b “的流标记 域。主机发送报文时，如果需要把报文放到流中传输，只需在流标记里填入相应的 流编号否则在流标记里填零就作为一般的报文处理。路由器收到流的第一个报文 时，以流编号为索引建立处理上下文，流中的后续报文都按上下文处理i p v 6 的资源 预留协议( r s v p ) ，使用流标记来申请资源和相当的优先级，实现口网中的o o s 传输以及对于实时业务的支持，使得各种应用能够为其数据包选择服务等级。 ( 3 ) i p v 6 可靠的安全性：由于i p v 4 在安全方面的脆弱性，i p v 6 提供的安全特 性将是i p v 4 向i p v 6 迁移的重要刺激因素。i p v 6 针对通信中容易受到的以下几种类 型的攻击，提供防范措施： ( a ) 获取数据包。非接收方从网络上获取发送方发的数据包。 ( b ) i p 地址欺骗。冒充别人的i p 地址。 ( c ) 连接截获。发方和收方通信时，在中闯冒充发方或收方，或者修改截获的 包。 一3 东北大学硕士学位论文第二章路由器与路由选择协议 ( d ) 重发。攻击者获取数据包后，不断重发该包。 ( 4 ) i p v 6 对移动性的支持：利用移动i p v 6 和h o m e a g e n t 端可以在保持已有 的通信连接不被中断的情况下，移动终端在不同的网络间进行漫游，同时还能保持 自身的可达性。移动i p v 6 与移动i p v 4 相比有如下特点：更大的地址空间、取消了 外地代理、路由优化、新的路由报头、取消了a r p 、增加了家乡地址选项，具有更 好的安全性、家乡代理搜索、双向检测、增加了宣告间隔选项。利用扩展报头，取 消了“隧道软状态”机制，取消了多重绑定。 ( 5 ) 易管理性：结构化的地址加上主杌的自动配置，使得网络和路由器的网络 重编号得以轻松实现。对i s p 和网络管理员而言，这大大减轻了网络管理和用户支 持的工作量，地址的自动配置使得主机可以自动获得i p v 6 连接而无需人工干预。 2 2 路由原理及路由选择协议 当i p 子网中的一台主机发送i p 分组给同一i p 子网的另一台主机时，它将直接 把i p 分组送到网络上，对方就能收到。而要送给不同i p 子网上的主机时，它要选 择一个能到达目的子网上的路由器，把i p 分组送给该路由器，由路由器负责把i p 分组送到目的地。 路由器转发驴分组时，只根据王p 分组的目的i p 地址的网络号部分，选择合适 的端口，把口分组送出去。同主机一样，路由器也要判定端口所接的是否是目的子 网，如果是，就直接把分组通过端口送到网络上，否则，也要选择下一个路由器来 传送分组。路由器有它的缺省网关，用来传送不知道往哪儿送的口分组。这样，通 过路由器把知道如何传送的i p 分组正确转发出去，不知道的i p 分组送给“缺省网 关”路由器，这样一级一级地传送，i p 分组最终将送到目的地，送不到目的地的i p 分组则被网络丢弃了。 目前t c p ，i p 网络，全部是通过路由器互连起来的，i n t e r n e t 就是成干上万个伸 子网通过路由器互连起来的国际性网络。这种网络称为以路由器为基础的网络 ( r o u t e r b a s e d n e t w o r k ) ，形成了以路由器为节点的“网间网”。在“网间网”中，路 由器不仅负责对i p 分组的转发，还要负责与别的路由器进行联络，共同确定“网间 网”的路由选择和维护路由表。 路由动作包括两项基本内容f 2 】：寻径和转发。寻径即判定到达目的地的最佳路 径，由路由选择算法来实现。由于涉及到不同的路由选择协议和路由选择算法，要 一4 东北大学硕士学位论文g _ - 章路由器与路由选择协议 相对复杂一些。为了判定最佳路径，路由选择算法必须启动并维护包含路由信息的 路由表，其中路由信息依赖于所用的路由选择算法而不尽相同。路由选择算祛将收 集到的不同信息填入路由表中，根据路由表可将目的网络与下一跳( n e x ti - f 0 p ) 的 关系告诉路由器。路由器间互通信息进行路由更新，更新维护路由表使之正确反映 网络的拓扑变化，并由硌由器根据量度来决定最佳路径。这就是路由选择协议 ( r o u t i n gp r o t o c 0 1 ) ，例如路由信息协议( r i p ) 、开放式最短路径优先协议( o s p f ) 和边界网关协议( b g p ) 等。 转发即沿寻径好的最佳路径传送信息分组。路由器首先在路由表中查找，判明 是否知道如何将分组发送到下一个站点( 路由器或主机) ，如果路由器不知道如何发 送分组，通常将该分组丢弃；否则就根据路由表的相应表项将分组发送到下一个站 点，如果目的网络直接与路由器相连，路由器就把分组直接送到相应的端口上。这 就是路由转发协议( r o u t e dp r o t o c 0 1 ) 。 路由转发协议和路由选择协议是相互配合又相互独立的概念，前者使用后者维 护的路由表，同时后者要利用前者提供的功能来发布路由协议数据分组。 骺 典型的路由选择方式有两种：静态路由和动态路由【3 1 。 静态路由是在路由器中设置的固定的路由表。除非网络管理员干预，否则静态 路由不会发生变化。由于静态路由不能对网络的改变做出反映，一般用于网络规模 不大、拓扑结构固定的网络中。静态路由的优点是简单、高效、可靠。在所有的路 由中，静态路由优先级最高。当动态路由与静态路由发生冲突时，以静态路由为准。 动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的路由信 息更新路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明 发生了网络变化，路由选择软件就会重新计算路由，并发出新的路由更新信息。这 些信息通过各个网络，引起各路由器重新启动其路由算法，并更新各自的路由表以 动态地反映网络拓扑变化。动态路由适用于网络规模大、网络拓扑复杂的网络。当 然，各种动态路由协议会不同程度地占用网络带宽和c p u 资源。 静态路由和动态路由有各自的特点和适用范围，因此在网络中动态路由通常作 为静态路由的补充。当一个分组在路由器中进行寻径时，路由器首先查找静态路由， 如果查到则根据相应的静态路由转发分组；否则再查找动态路由。 根据是否在一个自治系统内部使用，动态路由协议分为内部网关协议( i g p ) 和外部网关协议( e g p ) 。这里的自治系统是指一个具有统一管理机构和统一路由策 5 一 东北大学硕士学位论文第二章路由器与路由选择协议 略的网络。自治系统内部采用的路由选择协议称为内部网关协议，常用的有r i p ， o s p f ；外部网关协议主要用于多个自治域之间的路由选择，常用的是b g p 。 2 2 1r i p 路由选择协议 r i p 协议最初是为x e r o x 网络系统的x e r o xp a r c 通用协议而设计的，是i n t e r a c t 中常用的路由协议。r i p 采用距离向量算法，即路由器根据距离选择路由，所以也 称为距离向量协议。路由器收集所有可到达目的地的不同路径，并且保存有关到达 每个目的地的最少站点数的路径信息，除到达目的地的最佳路径外，任何其它信息 均予以丢弃。同时路由器也把所收集的路由信息用r i p 协议通知相邻的其它路由器。 这样，正确的路由信息逐渐扩散到了全网。 r i p 使用非常广泛，它简单、可靠，便于配置。但是r i p 只适用于小型的同构 网络，因为它允许的最大站点数为1 5 ，任何超过1 5 个站点的目的地均被标记为不 可达。而且r i p 每隔3 0 秒一次的路由信息广播也是造成网络的广播风暴的重要原 因之一。 r i p 目前有3 个版本，支持i p v 4 的r i p v l 和r i p v 2 以及支持i p v 6 的r i p n g 。 2 2 2o s p f 路由选择协议 8 0 年代中期，r i p 己不能适应大规模异构网络的互连，o s p f 随之产生。它是 i e t f 的内部网关协议工作组为i p 网络而开发的一种路由协议。 o s p l d 4 】是一种基于链路状态的路由协议，需要每个路由器向其同一管理域的所 有其它路由器发送链路状态广播信息。在o s p f 的链路状态广播中包括所有接口信 息、所有的量度和其它一些变量。利用o s p f 的路由器首先必须收集有关的链路状 态信息，并根据一定的算法计算出到每个节点的最短路径。而基于距离向量的路由 协议仅向其邻接路由器发送有关路由更新信息。 与r i p 不同，o s p f 将一个自治系统再划分为斟5 1 ，相应地有两种类型的路由选 择方式：当源和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时， 则采用区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。当一个 区内的路由器出了故障时并不影响自治域内其它区路由器的正常工作，这也给网络 的管理、维护带来方便。o s p f 目前正在使用的有2 个版本，支持i p v 4 的o s p f v 2 以及支持i p v 6 的o s p f v 3 。 一6 一 东北大学硕士学位论文g _ - 章路由器与路由选择协议 2 2 3b g p 路由选择协议 b g p 是为t c p i p 互联网设计的外部网关协议，用于多个自治域之间1 6 l 。瓷既不 基于纯粹的链路状态算法，也不是基于纯粹的距离向量算法。它的主要功能是与其 它自治系统的b g p 交换网络层可达信息( n u t i ) 。各个自治系统可以运行不同的内 部网关协议。b g p 更新信息包括网络前缀和自治域路径的成对信息。自治系统路径 包括到达某个特定网络须经过的自治系统串，这些更新信息通过t c p 传送出去，以 保证传输的可靠性。 b g p 目前有最常使用的支持i p v 4 的b g p 4 以及在此基础上形成的支持i p v 6 的 b g p 4 + 。 2 2 4 路由器原理 路由器工作在o s i 模型中的第三层，即网络层。路由器利用网络层定义的“逻 辑”上的网络地址( 即m 地址) 来区别不同的网络，实现网络的互连和隔离，保持 各个网络的独立性。路由器不转发广播消息，而把广播消息限制在各自的网络内部。 发送到其他网络的数据则先被送到路由器，再由路由器转发出去。 m 路由器只转发i p 分组，把其余的部分挡在网内( 包括广播) ，从而保持各个 网络具有相对的独立性，这样可以组成具有许多网络( 子网) 互连的大型的网络。 由于是在网络层的互连，路由器可方便地连接不同类型的网络，只要网络层运行的 是i p 协议，通过路由器就可互连起来。 网络中的设备用它们的网络地址( t c p ，l p 网络中为口地址) 互相通信。i p 地 址是与硬件地址无关的“逻辑”地址。路由器只根据i p 地址来转发数据。i p 地址 的结构有两部分，一部分定义网络号，另一部分定义网络内的主机号。目前，在 i n t e r n e t 网络中采用子网掩码来确定i p 地址中网络地址和主机地址。子网掩码与i p 地址一样也是3 2 b i t ，并且两者是一一对应的，并规定，子网掩码中数字为“1 ”所 对应的i p 地址中的部分为网络号，为“0 ”所对应的则为主机号。网络号和主机号 合起来，才构成一个完整的i p 地址。同一个网络中的主机i p 地址，其网络号必须 是相同的，这个网络称为i p 子网。 通信只能在具有相同网络号的i p 地址之间进行，要与其它i p 子网的主机进行 通信，则必须经过同一网络上的某个路由器或网关( g a t e w a y ) 出去。不同网络号的 i p 地址不能直接通信，即使它们接在一起，也不能通信。 东北大学硕士学位论文 第二章路由器与路由选择协议 路由器有多个端口，用于连接多个i p 子网。每个端口的i p 地址的网络号要求 与所连接的i p 子网的网络号相同。不同的端口为不同的网络号，对应不同的i p 子 网，这样才能使各子网中的主机通过自己子网的i p 地址把要求出去的i p 分组送到 路由器上。 2 3i p v 6 路由原理 2 3 1i p v 6 路由术语介绍 。 了解i p v 6 路由术语可以使我们能更好的理解i p v 6 路由原理，下面介绍一下i p v 6 常用的一些路由术语。 ( 1 ) 节点( n o d e ) ：可以实现i p v 6 协议的设备。 ( 2 ) 主机( h o s t ) ：不是路由器的节点。 ( 3 ) 路由器( r o u t e r ) ：可以根据i p v 6 数据包的地址转发数据的节点。 ( 4 ) 上层( u p p e rl a y e r ) ：i p v 6 之上的协议层。例如t c p 和u d p 这样的传输 协议、i c m p v 6 这样的控制协议等。 ( 5 ) 链路( l i n k ) ：通信设备或者媒介。通过此设备或者媒介，节点可以在数 据链路层进行通信。链路例子如e t h e r n e t 、p p p 、x 2 5 、a t m 或者其他协议( 如i p v 4 和i p v 6 本身) 上面的通道。 ( 6 ) 接口( i n t e r f a c e ) ：节点和链路的网络接口。 ( 7 ) 邻居( n e i g h b o r s ) ：和同一个链路相连的节点。 ( 8 ) 地址( a d d r e s s ) ：接口或者一系列接口的i p v 6 标识。 ( 9 ) 数据报( d a t a g r a m ) ：信息包的同义词。 ( 1 0 ) 信息包( p a c k e t ) ：i p v 6 层p d u ( p r o t o c o ld a t au n i t ，协议数据单元) ， 即i p v 6 报头加上有效载荷。 ( 1 1 ) 链路m t u ( m a x i m u mt r a n s m i s s i o nu n i t ，最大传输单元) ：某连路的最 大传输单元，以字节表示，能通过链路完整传输的信息包的最大尺寸。 ( 1 2 ) 路径m t u ：源节点和且的节点之间的路径上所有链路的最小链路m t u 。 2 3 2 路由表与包转发原理 、 对于路由器本身可以达到的子网，i p v 6 路由器的路由表只包含它的一个条目。 路由器的组织结构如表2 1 所示，路由表可以使用适当的协议，如r i p 、o s p f 和 东北大学硕士学住论文第二章路由器与路由选择协议 b g p 等，进行手工或者自动地写入。 下面对表2 1 的例子中路由表的内容做进一步解释： 簿 ( 1 ) 子网：子网是一个名称，而不是网络的扩展地址。例如，在i p v 6 荦一个 地址如下所示；a b d c ：f f 8 7 ：0 ：0 ：0 ：0 ：0 ：0 8 0 ，这是一个子网的地址，有8 0 位前缀。 ( 2 ) 下一个路程字段( n e x th o p ) ：例如，路由器3 的地址是 a b c d ：f f 8 7 ：0 ：0 ：0 ：0 8 0 0 ：2 8 3 c ：5 d 6 2 。 ( 3 ) 类型( t y p e ) ：指明和子网相关的使用类型。“直接”表示路由器具有和子 网直接相连的接口；“静态”表示到达子网路由规则是手工写入的；r i p 和o s p f 表 明路由器通过相应的路由选择协议来获得子网的使用特性。 ( 4 ) 期限( a g e ) ：指剩余的有效性时间，单位为秒。它仅仅对那些和子网相 关的条目来说是重要的。这些子网的使用信息是通过协议得到的，目的是自动计算 路由表。实际上，动态条目必须定期更新。 ( 5 ) 状态( s t a t u s ) ：表明条目的状态。在我们的例子中，和子网2 相连的路由 器接口处于关机状态，因此，相关的可靠性信息是没有的。 表2 1 路由表的示例 t a b 2 1e x a m p l eo fr o u t i n gt a b l e 通常，路由器转发进程使用每个i p 包的路由表，首先在路由表的一系列子网中 查找目标地址所属的子网，然后把i p 包路由到相关的下一路程段。类型为“直接” 的条目没有下一个路程段，这是因为路由器具有直接和子网相连的接口，从而可以 通过数据链路层传输i p v 6 数据包直接到达子网节点。 需要指出的是，本文所指的是1 2 8 位的i p v 6 地址和i s o o s i 参考模型的3 层或 者网络层地址之间的对应关系。但是，当一个信息包必须在子网上进行路由时，传 输过程必须在2 层完成，也就是链路层。因此，还要必须了解和使用2 层地址。 一。一 东北大学硕士学位论文第二章路由器与路由选择协议 现对两种类型地址的使用说明如下： ( 1 ) 第2 层地址用来标识物理网络( w 子网) 中信息包的最终目标。 ( 2 ) 第3 层地址用来标识整个网络中i p 信息包的最终目标。 解释这两种类型地址的转发过程如图2 1 所示。假设想把一个信息包从主机b 传输到主机a 。传输过程分为下面4 个阶段，共涉及3 个标识为a 、b 、c 的不同信 息包。 链路源地址 n 6 目的地 i 6 源地址 rtt bab信息包l 3 一l 3 信息包 一 l 2 信息包 。 回丑亚画 i j 4 j 子m y j 图2 1w v 6 地址转发过程 f i g 2 1t r a n s m i t t i n gp r o c e s so fi p v 6a d d r e s s ( 1 ) 主机b 产生一个i f v 6 信息包，目标地址为主机，a ，发送地址为主机b 。 这个信息包在到达目的地之前不会发生任何改变。b 检查a 是否在同一个l a n 。如 果不是，b 把w v 6 信息包放入2 层封装中，目标链路地址等于r 2 ，发送链路地址 等于b ( 信息包a ) ，从而向r 2 发送一个信息。 ( 2 ) 路由器r 2 接收到信息包，然后使用它的路由表来确定在点对点w a n 上 传输信息包。在这个例子中，由于两路由器之间具有点对点通道，信息包b 中不需 要链路层地址。 ( 3 ) 路由器r 1 接收到信息包b ，然后决定通过l a n 把它传输到a 。运用邻居 发现算法，它发现a 的链路层地址及其i p v 6 层地址，然后它执行信息包c 的传输 过程。 ( 4 ) 主机a 接收到信息包，由于i p v 6 的目标地址等于它的3 层地址，它不再 一 东北大学硕士学位论文第二章路由器与路由选择协议 在网络中进一步传输信息包，而是把它送到上面的层中。 以上是i p v 6 数据包的转发过程，在i p v 4 网络中路由器是通过a r p 协议来发现 m a c 地址，以此来完成网内数据包的转发。而在i p v 6 网络中，由于i p v 6 具有链路 层地址，所以i p v 6 路由器通过邻居发现协议来获取这些链路层地址，从而可以将 i p v 6 数据包传输到目的地。了解1 p v 6 路由原理对于理解后面的内容有很大帮助， 因此本文在此专门介绍了i p v 6 路由原理。 东北大学硕士学位论文第三章o s p f 路由选择协议分析 第三章o s p f 路由选择协议分析 3 1o s p f 协议概论 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 最开始是由j o h nm o y 开发，接下来p r o t e o n 加入了进来，p r o t e o n 使得这个内部开发的路由协议在i e t f 内得到了标准化。第一 个o s p f 的r f c 出版于1 9 8 9 年1 0 月，最后的一个完整的i n t e r n e t 标准版本r f c 2 3 2 8 出版于1 9 9 8 年4 月。 i e t f 为了响应建设越来越大型基于i p 网络的需求，成立了专门工作组，负责 开发用在大型的、混合的i p 网络中一个开放的链路状态路由选择协议。这个新的路 由选择协议基于比较成功的一系列专有、特定厂商的最短路径优先路由选择协议， 而且这些协议产品已经在市场上出现。包括i e t f 的o s p f 在内，所有的s p f 路由 选择协议都是直接基于d i j k s t r a 算法。该算法支持基于链路状态的路由选择，而不 是距离适量。 o s p f 就是一个s p f 类路由选择协议的开放版本，所谓的s p f 是指e w d i j k s t r a 提出的用来计算在一个图中从一个源节点到所有其他节点的最短路径的算法，即 d i j k s t r a 算法。r f c 1 1 3 1 定义了最早的o s p f 。这个版本很快被r f c 1 2 4 7 所代替。 r f c 1 2 4 7 版的o s p f 被命名为o s p f 版本2 。版本2 在稳定性和功能上都有本质的 提高，有了大量的改进。每个改进都由i e t f 把它们描述为一个开放标准。这些说 明分别记录在r f c 1 5 8 3 、r f c 2 1 7 8 和r f c 2 3 2 8 中。现在i p v 4 网络中使用的o s p f 版本2 一般遵从r f c - 2 3 2 8 。1 9 9 9 年1 2 月i e t f 工作小组发布了基于i p v 6 的o s p f 路由协议标准r f c 2 7 4 0 。在该协议中，将这种基于i p v 6 的o s p f 路由协议称为 o s p f v 3 ，即o s p f 版本3 。 3 1 1o s p f 的工作原理 o s p f 是用于自治系统内，专门为i p 路由选择协议而设计的。因此，它不能够 传送别的一些可选路由网络协议数据包。o s p f 基于i p 数据包头中的目标i p 地址来 计算路由，而且，它不能够计算到非职目标的路由。另外，各种o s p f 消息都是直 接塞入i p 中的，而不需要使用别的协议( t c p 、u d p 等等) 进行传送。 o s p f 协议的基本思路如下在自治系统中每一台运行o s p f 的路由器收集各 自的接口、邻接信息称为链路状态，通过f l o o d i n g 算法在整个系统广播自己的链路 一1 3 东北大学硕士学位论文 。 第三章o s p f 路由选择协议分析 状态，使得在整个系统内部维护一个同步的链路状态数据库，根据这一数据库，路 由器计算出以自己为根，其它网络节点为叶的一根最短的路径树，从而计算出自己 到达系统内部各可达的最佳路由。它处理在一个自治系统中，路由器的网络的路由 表信息。 o s p f 路由协议是种典型的链路状态( l i n k s t a t e ) 的路由协议，一般用于同 一个路由域内。在这里，路由域是指一个自治系统( a u t o n o m o u ss y s t e m ) ，即a s ， 它是指一组通过统一的路由策略或路由协议互相交换路由信息的网络。在这个a s 中，所有的o s p f 路由器都维护一个相同的描述这个a s 结构的数据库，该数据库 中存放的是路由域中相应链路的状态信息，o s p f 路由器正是通过这个数据库计算 出其o s p f 路由表的。 作为一种链路状态的路由协议，o s p f 将链路状态通告数据包l s a ( l i n ks t a t e a d v e r t i s e m e n t ) 传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不 同。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路 由器。 o s p f 工作流程： o s p f 路由选择协议工作流程如图3 1 厅司 1 _ j 发送呼叫包发现邻居，在广播和n b m a 网络中还需选出d r 和b d r 路由器 墨 医蔬 i 生成路由表 匮堕堕堕垂亘困 图3 1 0 s p f 丁= 作流程 f i g 3 1w o r k i n gp r o c e s so fo s p f 东北大学硕士学位论文第三章o s p f 路选择协议分析 3 1 2o s p f 的路由更新机制 o s p f 使用l s a 在o s p f 节点之中共享路由信息。这些链路状态信息会在整个 区中进行传播但不会超越一个区。 因此，区中的每一个路由器都知道本区的拓扑。然而，一个区的拓扑对区外是 不可知的。考虑到实际上有四种不同类型的o s p f 路由器：区内路由器、区边界路 由器、自治系统边界路由器、骨干路由器。很明显每种路由器类型有不同的对等实 体集，路由器与这些对等实体交换l s 九 ( 1 ) 内部区路由器 内部的区路由器必须直接和区中的其他路由器交换l s a ，其中包括每一个区内 部路由器，也包括作为区成员的区边界路由器。图3 2 显示了一个o s p f 网络中， 在整个区1 中转发或泛洪l s a 的情形。需要重点注意的是相同区中的o s p f 路由器 无需彼此直接相连就能共享l s a 信息。o s p f 路由器直接把l s a 报文发送到区中每 一个知道的路由器，并且使用任何可用的链路来转发那些报文。 路由器路由器 图3 2 在自治系统1 内的泛洪 f i g 3 2f l o o d i n gi 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 rm u t e r ) 负责在数据库中为它 们接口所连的每个区维护拓扑信息。因此，如果一个区边界路由器互联了两个不同 的区，它必须和两个网络中的对等实体交换i s a 。和区内部路由器一样，这些i s a 直接寻址并传输到区中的对等实体。图3 3 显示了这一点。 o s p f 加强性能的另一个特点是路由汇总1 8 1 。关于一个区的拓扑信息，并不和区 外的路由器共享。相反，区边界路由器汇总了所有与其相连的所有区中的地址。这 个汇总的路由数据通过l s a 报文与其相互联的每个区中的对等路由器实现共享。 一1 5 东北大学硕士学位论文第三章o s p f 路由选择协议分析 o s p f 使用几种不同类型的i s a ，每种有不同的功能。用于共享汇总路由数据的l s a 为类型3 l s a 。 在图3 3 中，区边界路由器直接把汇总的数据广播给区0 中的所有路由器。o s p f 不允许大于或等于1 的区之间相互连接。所有这样的互联必须通过区0 。因此，其 含义是区边晃路由器把一个非0 编号的区来与区o 互联。 路由罂 路由器 图3 3 区边界路由器引起的自治系统内l s a 泛洪 f i g 3 3a s b rc a u s i n gl s a f l o o di na s 。 ( 3 ) 骨干路由器 骨干路由器( f r f r a m e w o r kr o u t e r ) 负责维护骨干拓扑信息，并且为自治系统 中的每个其他区传播汇总的拓扑信息。图3 4 显示了由骨干路由器交换l s a 的情形。 路由器 路由器 图3 4 骨干路由器引起的自治系统内l s a 泛洪 f i g 3 4f rc a u s i n gl s a f l o o di na s 虽然骨干路由器、区边界路由器和区内部路由器之间的差别看起来是清楚的， 但由于路由器能支持到其他路由器的多i o 端口连接，三者还是会引起混淆。理论 东北大学硕士肇位论文 第三章o s p f 路由选择协议分析 上讲，每个端口可以连至一个不同的区。所以，路由器可以在其连接的不同区之间 形成边界。 3 1 3o s p f 的特点 o s p f 是内部路由协议，它是基于链路状态来计算到目的节点的最短路径，它 只依靠“呼叫”协议和“可靠泛洪”来完成路由表的动态维护。o s p f 是专门为1 p 设计的一种路由协议，它直接使用i p 。也就是说，o s p f 直接封装在l p 包内，它有 自己的协议类型号8 9 ，如图