（通信与信息系统专业论文）ospf协议软件的设计与实现—链路状态数据库与路由表计算.pdf

摘要 i e t f ( i n t e r n e t e n g i n e e r i n g t a s kf o r c e ) 于1 9 8 8 年提出的o s p f 是个基于链路 状态的动态路由1 力、议，协议的基本思路如下：在自治系统( a s ) 中每一台运行o s p f 的路由器收集各自的接! m l 令l l 接信息称为链路状态( l i n ks t a t e ) ，通过f l o o d i n g 算法在整个系统广播自己的链路状态，使得在整个系统内部维护一个同步的链路 状态数据库( l i n ks t a t ed a t a b a s e ) ，根据这一数据库，路由器计算出以自己为根， 其它网络节点为叶的一根最短的路径树，从而计算出自己到达系统内部可达的最 佳路由。o s p f 是一类内部网关协议( i n t e r i o rg a t e w a yp r o t o c o l ，i g p ) ，它处理在 一个自治系统中的路由信息。 本论文首先介绍了o s p f 协议的基本概念、一些协议用到的基本算法和一些 主要的报文结构。由于链路状态在o s p f 中非常重要，接着介绍了与链路状态相 关的一些知识，如各种链路状态的产生、发布、扩散、更新等等，以及非常重要 的s p f 算法的细节描述，和路由表计算。最后介绍本o s p f 协议软件的总体框架 和本人在其中所完成的工作，说明测试情况并做出相应的结论。 关键词 内部网关滋，堂( r o u t i n gi n f o r m a t i o np r 瓷7 0 c 0 1 ) ，孟( o p e n s h l o _ r t e s tp a t h 内部网关撇，旦生 ，鳗腿 f i r s t ) ，自治系统l 域。，邻居，链路状态数据库，链路状态广告，数据库描述， 指派路由器，备份指派路苫皓7 、，7 - 7 a b s t r a c t t h eo s p f p r o t o c o lw a sd e v e l o p e db yt h eo s p fw o r k i n gg r o u po f t h ei n t e r n e t e n g i n e e r i n g t a s kf o r c e i ti sad y n a m i cr o u t i n gp r o t o c o lb a s e do nl i n k s t a t e o s p f i sc l a s s i f i e da sa ni n t e r i o rg a t e w a yp r o t o c o l ( 1 g p ) ，i to n l yp r o c e s s e st h er o u t i n g i n f o r m a t i o ni na l la u t o n o m o u ss y s t e m t h eb a s i ct h e o r yo f t h e p r o t o c o li sa sf o l l o w s ： i na u t o n o m o u ss y s t e me a c hr u n n i n go s p fr o u t e rw i l la c c u m u l a t et h ei n f o r m a t i o no f r o u t e r su s a b l ei n t e r f a c e sa n dr e a c h a b l en e i g h b o r s w h i c hi sc a l l e dl i n k s t a t e t h e r o u t e rd i s t r i b u t e si t sl o c a ls t a t et h r o u g h o u tt h ea u t o n o m o u ss y s t e mb yf l o o d i n g ，s o e a c hr o u t e rm a i n t a i n sas a m ed a t a b a s ed e s c r i b i n gt h ea u t o n o m o u ss y s t e m st o p o l o g y ， a n df r o mt h et o p o l o g i c a ld a t a b a s e e a c hr o u t e rc o n s t r u c t sat r e eo fs h o r t e s tp a t h sw i t l l i t s e l fa sr o o t t 1 1 i s s h o r t e s t p a t h t r e e g i v e s t h er o u t et oe a c hd e s t i n a t i o ni nt h e a u t o n o m o u ss y s t e m e x t e r n a l l yd e r i v e dr o u t i n gi n f o r m a t i o na p p e a r so nt h et r e ea s l e a v e s f i r s to fa l lt h eb a s i ct h e o r yo fo s p f , s o m eb a s i ca l g o r i t h mu s e db yt h ep r o t o c o l 0 s p fa n ds o m ei m p o r t a n tp a c k e ts t r u c t u r ea r ed i s c u s s e di nt h i st h e s i s b e c a u s eo f t h e l i n k s t a t e si m p o r t a n tr o l ei n0 s p f t h ew h o l es e c o n ds e c t i o ni su s e dt oi n t r o d u c et h e k n o w l e d g eo fl i n k s t a t e ，s u c ha sg e n e r a t i n g ，a d v e r t i s i n g ，f l o o d i n g ，u p d a t i n ge t ca r e i n t r o d u c e d t h ed e t a i lo fs p fa l g o r i t h ma n dt h eg e n e r a t i n go fr o u t i n gt a b l ea r ea l s o m e n t i o n e di nt h i ss e c t i o n t h e nw ed i s c u s st h ea r c h i t e c t u r eo ft h eo s p fr o u t i n g p r o t o c o ls o f t w a r ea n dt h ep o r t i o n ih a v ed o n ei ni t ，w h i c hm a i n l yc o n t a i nt h em o d u l e o f a l g o r i t l n no fs p f , l i n k - s t a t ed a t a b a s ea n d t h eg e n e r a t i o no f r o u t et a b l e a tl a s t ，a t l a s t ，t h es o f t w a r eo ft h eo s p fr o u t i n gp r o t o c o l i st e s t e d ，a n dt h ec o n c l u s i o n sa r e d r a w n k e y w o r d i g p , r i p , o s p f , a u t o n o m o u ss y s t e m ( a s ) ，a r e a ，n e i g h b o r , l i n ks t a t e d a t a b a s e ( l s d b ) ，l i n k s t a t ea d v e r t i s e m e n t ( l s a ) ，d a t a b a s ed e s c r i p t i o n ( d d ) ，d e s i g n e d r o u t e r ( d r ) ，b a c k u pd e s i g n e dr o u t e r ( b d r ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致i 身j 的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 已在论文中作了明确的说明并表示谢意。 签名 辑 日期：矿z ，年石月矿日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复印手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲撇钏躲丝蜩 日期：弘刀2 ，年月o 日 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 第一章引言 随着i n t e m e t 技术在全球范围的飞速发展，o s p f 已成为目前i n t e r a c t 广域网 和i n t r a n e t 企业网采用最多、应用最广泛的路由协议之一。o s p f ( o p e n s h o r t e s t p a t hf i r s t ) 路由协议是由i e t f ( i n t e m e t e n g i n e e r i n g t a s kf o r c e ) i g p 工作小组提 出的，其规范是公开的，目前使用的o s p f 协议是其第二版，定义于r f c 2 3 2 8 。 o s p f 协议是基于链路状态和s p f 技术，是以传统使用的t c p i p 路由协议 b e l l m a n f o r d 为基础发展而来。它是为t c p i p 环境设计的，包括支持c i d r ， 带标记的外部路由信息。 o s p f 是内部网关协议，它被设计为运行在单个自治系统内，也就是说是在 一个自治系统内部各个路由器之间相互交换发布路由信息。 o s p f 协议是一种动态路由协议，它能迅速地检测到自治系统内网络拓扑的 变化( 比如某个网络端口不能工作) ，在一段网络路由信息汇聚的时间后，计算 出新的、正确的路由。路由信息的汇聚时间很短，并且引起的网络的开销很小。 o s p f 路由协议是一种典型的链路状态的路由协议，在一个自治系统中，所 有的o s p f 路由器都维护一个相同的描述这个自治系统结构的数据库，数据库描 述了整个自治系统的拓扑信息，也叫链路状态数据库。该数据库中存放的是路由 域中相应链路的状态信息，是由一个个链路状态广告( l i n k s t a t ea d v e r t i s e m e n t ， 我们简称为l s a ) 构成的。o s p f 路由器正是通过这个数据库计算出其o s p f 路由 表的。 在一个自治系统当中，所有的路由器并行的运行同样的算法。路由器以自己 为根节点，由链路状态数据库构造出最短路径生成树。这个最短路径生成树描述 了去自治系统内的每个目的地址的路由信息，自治系统外的地址以叶子的形式 出现在最短树上。当到同一个目的地址有多个等价开销的路径存在，o s p f 能作 到平衡负载。 o s p f 允许将网络汇聚成一个区域( a r e a ) ，区域的拓扑结构对于本区域外而 自治系统内的路由器是不可见的。这种隐藏能够极大的减少路由协议所造成的网 络流量。而且本区域的路由信息只由本区域的拓扑结构决定，保护了本区域不受 外部错误路由信息的影响。o s p f 使用扩散过程把l s a 的更新报文传给自治系统 第一章引言 内的路由器，任何路由信息的变化都扩散到整个自治系统，当网络很大时，就会 带来较大的网络开销。另外当网络很大时，链路状态数据库的大小，最短树的计 算时间，路由表的大小都会超出一定的限额：内存需求过于巨大，计算时间过于 漫长。对于这些问题的解决方式是作“分层路由”，即将网络分割成一个由“主 干”( b a c k b o n e ) 连接成的一组相互独立的部分。区域引入的其实就是一种分层 的概念，它细化了整个自治系统，上面所述的最短路径生成树其实是针对区域而 言的。路由器了解的拓扑结构其实也只是所属区域的拓扑结构，其使用的最短路 径优先( s p f ) 算法也只是计算区域内部的路由。而区域拓扑结构信息l s a ( r o u t e r l s aa n dn e t w o r k l s a ) 也只在该区域内部扩散，不会扩散到自治系统 其它区域。这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器是 将部分或全部的路由表传递给与其相邻的路由器。o s p f 还提供路由更新的鉴定， 而且在发送和接收改变信息时使用i p 组播( m u l t i c a s t ) 的方式。 区域分为主干区域和非主干区域，主干区域将自治系统内所有区域连接起 来，所有跨区域路由器( a r e ab o r d e rr o u t e r ，简称为a b r ) 都属于主干区域。 主干区域是专用的a r e a 0 ( 通常写成区域0 0 0 0 ，o s p f 的区域号通常写成i p 地 址的形式) 。主干区域负责在区域之间分发路由信息，包含所有的a b r 、非全 部属于某区域的网络及其相连的路由器。主干区域本身也是个o s p f 区域，所以 所有的主干路由器与其它区域路由器一样，使用相同的过程和算法来维护主干内 的路由信息，主干区域拓扑对所有的跨区域路由器都是可见的。主干区域必须是 相连的，但是不必是在物理上的相连，它可以通过配置虚链路( v i r t u a ll i n k ) 来 建立和维护。 对于区域外而自治系统内的路由信息，路由器是通过s u m m a r y l s a 来获得 的。s u m m a r y - l s a 是由区域边界路由器产生和分发的。 o s p f 发布的网络信息是由网络号和掩码构成的，所以支持i p 子网的划分。 两个网络号相同的网络可能有不同的大小，这称之为变长子网划分。路由器根据 最佳匹配选择选择目的地址。主机路由的子网掩码由全q 构成( o x 自旺i 疆) 自治系统外的a s e x t e m a l 。l s a 也在自治系统内部发布。a s - e x t e r n a l - l s a 由 单独的一条l s a 构成。 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 第一部分o s p f 协议的原理 第二章o s p f 协议概述 首先解释一下o s p f 协议的相关术语、概念，为后面的章节打下基础。 2 1 术语和基本概念 o s p f 路由协议： o p e n s h o r t e s tp a t hf i r s t 最短路径优先协议。 自治系统( a s ) ： 由一组路由器组成，路由器之间运行同一种路由协议来交换路由信息。 区域( a r e a ) ： 自治系统的划分单元，一个自治系统可以划分为多个区域。 主干区域( b a c k b o n ea r e a ) ： 所有区域边界路由器和它们之间的路由组成主干区域。 区域i d ( a r e a i d ) ： 自治系统内区域的3 2 b i t 标识。 点到点网络( p o i n t - t o p o i n t ) ： 只支持一对路由器的网络。一条6 4 k 的专线是点到点网络的典型例子。 广播型网络( b r o a d c a s t n e t w o r k ) ： 网络可以支持两个以上的路由器，并且网络可以支持广播地址。相邻路由器 通过o s p f 的h e l l o 协议动态的检测对方的存在。h e l l o 协议用了网络的广播功能， 如果网络支持组播，o s p f 协议可以利用网络的组播功能。以太网是广播网络的 一个例子。 非广播网( n o n b r o a d c a s tn e t w o r k ) ： 网络支持两个以上的路由器，但没有广播能力，邻结点也是通过o s p f h e l l o 报文来维持，但是由于设有广播能力一些邻居需要靠配置来发现，在邻居间， 第二章o s p f 协议概述 o s p f 协议报文也是互相传送的，x 2 5 网是非广播网络的一个例子。o s p f 可以 在两种非广播网上运行，一种是非广播多重访问( n b m a ) ，它类似于o s p f 在 广播网上的操作，第二种类型点到多点( p o i n t t o m u l t i p o i n t ) ，可看为多个点到 点的连接的集合。非广播网类型的判别依靠于对网络的操作模式。 s t u b 网络： 只有一个接口与外部相连的网络，如一个p p p 可视为一个s t u b 网络。 接口( 1 m e r f a c e ) ： 路由器和一个网络的接口。一个网络端口有不同的状态，状态的变化由下层 协议和o s p f 协议本身来控制。一个接口对应一个i p 地址和网络掩码( 除非网 络为一个u n n u m b e r e d 点到点网络) 。 邻居路由器( n e i g h b o r r o u t e r s ) ： 两个路由器在同一个网络上都有网络端口。相邻关系由o s p f 的h e l l o 协议 发现和维护。 邻接关系( a d j a c e n c y ) ： 为交换路由信息，特定的两个相邻路由器组成的关系。注：并不是同一个网 络上的每对路由器都可以组成邻接关系。 链路状态广告( l i n k s t a t ea d v e r t i s e m e n t ，l s a ) ： 描述路由器或网络的状态信息。对于一个路由器，它包括了路由器的网络端 口和邻接关系的状态。每一个链路状态广告扩散至整个路由区域。链路状态数据 库包含了同一区域中所有路由器所发布的链路状态广告，链路状态广告简称 l s a 。 链路状态数据库( l i n k s t a t ed a t a b a s e ，l s d b ) ： 所有的连接状态传送组成了链路状态数据库。 h e l l o 协议： 作为o s p f 协议的一部分。负责建立和维护邻居的关系。在广播型网络中， h e l l o 能够动态地发现相邻路由器。 扩散( f l o o d i n g ) 过程： 作为o s p f 协议的一部分。负责发布和同步o s p f 路由器的链路状态数据库。 内部路由器： 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 当一个o s p f 路由器上所有直连的链路都处于同一个区域时，我们称这种路 由器为内部路由器。内部路由器上仅仅运行其所属区域的o s p f 运算法则。 指派路由器( d e s i g n a t e d r o u t e r ，d r ) ： 每个至少有两个路由器的广播型网络都应有一个指派路由器。指派路由器为 该网络生成n e t w o r k l s a ，并负有其他职责。指派路由器由h e l l o 协议选举。指 派路由器的概念使得广播型网络中所需要的邻接关系的数量减少，网络中的非指 派路由器和非备份指派路由器不需要结成邻接关系，因此也减少了网络的开销和 链路状态数据库的大小。指派路由器和备份指派路由器同其他路由器之间都是邻 接关系，而指派路由器和备份指派路由器之间也是邻接关系。 备份指派路由器( b a c k u pd e s i g n a t e d r o u t e r ，b d r ) ： 选举指派路由器的算法保证备份指派路由器在指派路由器发生故障时能够 替代指派路由器。平时备份指派路由器并不为该网络生成n e t w o r k - l s a ，只是在 扩散过程中有不同与一般路由器的职责。 区域边界路由器( a r e a b o r d e r r o u t e r ，a b r ) ： 在不止一个o s p f 区域有接口的路由器。 自治系统边界路由器( a u t o n o m o u ss y s t e m b o r d e r r o u t e r ，a s b r ) ： 一个o s p f 路由器，它连接到另一个a s ，或者在同一个a s 的网络区域中， 但运行不同于o s p f 的i g p 。 路由器i d ( r o u t e r i d ) ： 运行o s p f 路由协议的每一个路由器都分配了一个3 2 比特数，自治系统内 的每一个路由器的i d 值都是唯一的。 区域内路由( i n t r a a r e a r o u t e s ) ： 在同一区域的网络之间的路由。这些路由仅依据一个区域内所接收的信息。 区域问路由( i n t e r a r e a r o u t e s ) ： 在两个不同的o s p f 非主干区域之间的路由。区域问路由是由三部分组成： 从区域中的路由器到该区域的a b r 的区域内路径，从该区域的a b r 到目标a b r 的主干路径，而最后是从目标a b r 到目标区域的路径。 外部路由( e x t e m a lr o u t e s ) ： 从另一个a s 或另一个路由协议得知的路由可作为外部路由放到o s p f 中。 第二章o s p f 协议概述 有两种类型的外部路由。类型1 的外部路由的代价为到a s b r 的最小代价加上从 a s b r 到网络的代价。类型2 外部路由的代价等于从a s b r 到外部网络的代价。 路由摘要( r o u t es u m m a r i z a t i o n ) ： 一个区域的路由，来自另个a s 的路由，以及从另一个路由协议得知的路 由，所有的这些路由可由o s p f 汇总成一个路由宣告。 虚链路( v i r t u a ll i n k ) ： 引入虚连接的概念，保证了主干区域的路由器的连通性，减少了区域拓扑结 构的限制。 2 1 1 区域及路由 前面已经提到过，在o s p f 路由协议的定义中，可以将一个路由域或者一个 自治系统a s 划分为几个区域。在o s p f 中，由按照一定的o s p f 路由法则组合 在一起的网络或路由器的集合称为区域( a r e a ) 。 在o s p f 路由协议中，每个区域中的路由器都按照该区域中定义的链路状 态算法来计算网络拓扑结构，这意味着每一个区域都有着该区域独立的网络拓扑 数据库及网络拓扑图。对于每一个区域，其网络拓扑结构在区域外是不可见的， 同样，在每一个区域中的路由器对其域外的其余网络结构也不了解。这意味着 o s p f 路由域中的网络链路状态数据广播被区域的边界挡住了。这样做有利于减 少网络中的链路状态数据报文在全网范围内的广播，也是o s p f 将其路由域或 个a s 划分成很多个区域的重要原因。 。 随着区域概念的引入，意味着不再是在同一个a s 内的所有路由器都有一个 相同的链路状态数据库，而是路由器具有与其相连的每一个区域的链路状态信 息，即该区域的结构数据库，当一个路由器与多个区域相连时，我们称之为区域 边界路由器。个区域边界路由器有自身相连的所有区域的网络结构数据。在同 一个区域中的两个路由器有着对该区域相同的结构数据库。 我们可以根据i p 数据包的目的地地址及源地址将o s p f 路由域中的路由分成 两类，当目的地与源地址处于同一个区域中时，称为区域内路由，当目的地与源 地址处于不同的区域，称为区域问路由。 21 2o s p f 的主千区域及虚拟链路( v ir t u a 卜i in k ) 在o s p f 路由协议中存在一个主干区域( b a c k b o n e ) ，该区域包括属于这个 区域的网络及相应的路由器，主干区域必须是连续的，同时也要求其余区域必须 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 与主干区域直接相连。主干区域般为区域0 ，其主要工作是在非主干区域间传 递路由信息。所有的区域，包括主干区域之问的网络结构情况是互不可见的，当 一个区域的路由信息对外广播时，其路由信息是先传递至区域o ( 主干区域) ，再 由区域0 将该路由信息向非主干区域作广播。主于区域与非主干区域的关系可以 用下图来说明。 图2 1 在实际网络中，可能会存在b a c k b o n e 不连续的或者某一个区域与主干区域物 理不相连的情况，在这两种情况下，系统管理员可以通过设置虚拟链路的方法来 解决。 虚拟链路是设置在两个路由器之间，这两个路由器都有一个端口与同一个非 主干区域相连。虚拟链路被认为是属于主干区域的，在o s p f 路由协议看来，虚 拟链路两端的两个路由器被一个点对点的链路连在一起。在o s p f 路由协议中， 通过虚拟链路的路由信息是作为域内路由来看待的。下面我们分两种情况来说明 虚拟链路在o s p f 路由协议中的作用。 ( 1 ) 当一个区域与a r e a o 没有物理链路相连时 前面已经提到，一个主干区域a r e a 0 必须位于所有区域的中心，其余所有区 域必须与主干区域直接相连。但是，也存在一个区域无法与主干区域建立物理链 路的可能性，在这种情况下，我们可以采用虚拟链路。虚拟链路使该区域与主干 区域问建立个逻辑联接点，该虚拟链路必须建立在两个区域边界路由器之间， 并且其中一个区域边界路由器必须属于主干区域。 ( 2 ) 当主干区域不连续时 o s p f 路由协议要求主干区域a r e a o 必须是连续的，但是，主干区域也会出 现不连续的情况，例如，当我们想把两个o s p f 路由域混合到起，并且想要使 用个主干区域时，或者当某些路由器出现故障引起主干区域不连续的情况，在 第二章0 s p f 协议概述 这些情况下，我们可以采用虚拟链路将两个不连续的区域o 连接到一起。这时， 虚拟链路的两端必须是两个区域0 的边界路由器，并且这两个路由器必须都有处 于同一个区域的端口。 另外，当一个非主干区域的区域分裂成两半时，不能采用虚拟链路的方法来 解决。 21 3s t i u ba r e a 在o s p f 路由协议的链路状态数据库中，可以包括a s 外部链路状态信息， 这些信息会通过f l o o d i n g 传递到a s 内的所有o s p f 路由器上。但是，在o s p f 路由协议中存在这样一种区域，我们把它称为s t u ba r e a ，a s 外部信息不允许广 播进，出这个区域。对于s t u ba r e a 来说，访问a s 外部的数据只能根据默认路由 ( d e f a u l t r o u t e ) 来寻址。这样做有利于减小s t u ba r e a 内部路由器上的链路状态 数据库的大小及存储器的使用，提高路由器计算路由表的速度。 当一个o s p f 的区域只存在一个区域出口点时，我们可以将该区域配置成一 个s t u ba r e a ，在这时，该区域的边界路由器会对域内广播默认路由信息。需要 注意的是，一个s t u ba r e a 中的所有路由器都必须知道自身属于该s t u ba r e a ，否 则s t u ba r e a 的设置没有作用。另外，针对s t u ba r e a 还有两点需要注意：一是 s t u ba r e a 中不允许存在虚拟链路：二是s t u ba r e a 中不允许存在a s 边界路由器。 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 第三章协议报文格式 本章主要是描述o s p f 中的相关报文格式以及报文中各个域的作用，只有对 各个域正确有正确的理解，才能很好的实现o s p f 软件。 3 1 o s p f 协议规定了五种类型的协议报文 o s p f 建立、更新、同步l s d b 都是通过交换协议报文来实现的。尤其是在 使用链路状态路由协议的路由域中要保证路由正确，必须保证l s d b 一致，也就 是说更新和同步必须要可靠。下面我们对协议报文作一个简要的介绍。 h e l l o 报文。 链路状态数据库描述报文( d a t a b a s ed e s c r i p t i o np a c k e t 我们简称d d ) a 链路状态请求报文( l i n ks t a t er e q u e s tp a c k e t ) 。 链路状态更新报文( l i n ks t a t eu p d a t ep a c k e t ) 。 链路状态响应报文( l i n ks t a t ea c k n o w l e d g m e n t p a c k e t ) o s p f 报文头格式：( 以 | i & 度濉位为b i t ) v e r s i o n # ( 8 ) t y p e ( 8 ) p a c k e tl e n g t h ( 1 6 ) 、 r o u t e ri d ( 3 2 ) ， a r e ai d ( 3 2 ) r c h e c k s u m ( 1 6 )a u t y p e ( 1 6 ) a u t h e n t i c a t i o n ( 3 2 ) a u t h e n t i c a t i o n ( 3 2 ) 其中各个域的值解释如下： v e r s i o n 撑为o s p f 版本号。 t y p e 指出报文类型为上述五种之一。 p a c k e tl e n g t h 为报文字节数，包含2 4 字节头部。 r o u t e ri d 为发送该报文路由器的r o u t e ri d 。 a r e ai d 指出报文所属区域的区域号，如报文在虚链路上发送，该值为0 ( b a c k b o n ei d ) 。 c h e c k s u m 校验和，包含整个报文( a u t h e n t i c a t i o n 域6 4 位除外) ，与i p 头 部校验和计算方式一致。 第三章协议报文格式 a u t y p e 认证类型。a u t h e n t i c a t i o n 则是认证类型所决定的认证参数。 ( 】) h e l l o 报文格式： o s p fp a c k e th e a d e r ( t y p e = 1 ) ( 1 9 2 ) n e t w o r km a s k ( 3 2 ) helloi n t e r v a ( 1 6 )o p t i o n s ( 8 ) r t rp r i ( 8 ) r o u t e rd e a di n t e r v a l ( 3 2 ) d e s i g n a t e dr o u t e r ( 3 2 ) b a c k u pd e s i g n a t e dr o u t e r ( 3 2 ) n e i g h b o rl ( n 3 2 ) n e i g h b o rn 其中各个域的值解释如下： n e t w o r k m a s k 为发送报文接口上的掩码。 h e l l oi n t e r v a l 为发送h e l l o 报文的时间间隔。 o p t i o n s 为路由器可选能力。 r t r p r i 为路由器优先级，其在d r 选举中使用。 r o u t e rd e a d i n t e r v a l 为宣告路由器死亡时间，在该期间内如未收到邻居h e l l o 报文则认为其已当掉，一般设为4 * h e l l oi n t e r v a l 。 d e s i g n a t e dr o u t e r 为路由器选中的d r ，如果路由器没有选中的d r ，该项值 设为0 ，表示d r 暂缺。 b a c k u pd e s i g n a t e dr o u t e r 为路由器选中的b d r ，如果路由器没有选中的 b d r ，该项值设为0 ，表示b d r 暂缺。 以下部分为路由器的邻居列表，表明在最近一个h e l l oi n t e r v a l 中收到过有效 h e l l o 报文的发送路由器的r o u t e ri d 。 ( 2 ) d d 报文格式： 0 s p fp a c k e th e a d e r ( t y p e = 2 ) ( 1 9 2 ) i n t e r f a c em t u ( 1 6 ) io p t i o n s ( 8 ) l imm s ( 8 ) d d s e q u e n c en u m b e r ( 3 2 ) l s a 头部( n * 1 6 0 ) 其中各个域的值解释如下： i n t e r f a c em t u 指出从该接口上不用分段能发出的最大i p 报文的字节数，注 意，在虚链路上，该项只能设为0 。 电子科技大学硕士学位论文：o s p f 协议软件的设计与实现 o p t i o n s 与h e l l o 报文中的相应域同义。 i 位置1 说明该报文为d d 交换的初始。m 位置l 表明还有后续的d d 报文 待发。m s 位置1 表明在d d 交换过程中本路由器作为m a s t e r 。 d d s e q u e n c e n u m b e r 为d d 交换过程中的报文序列号。 剩下的部分为一系列的l s a 头部，作为d d 交换的内容，以使交换双方比较 l s d b ，以便进行进一步的同步和更新。 ( 3 ) l s - r e q u e s t 报文格式 0 s p fp a c k e th e a d e r ( t y p e = 3 ) ( 1 9 2 ) l st y p e ( 3 2 ) l i n ks t a t ei d ( 3 2 ) a d v e r t i s i n gr o u t e r ( 3 2 ) 其中各个域的值解释如下： 在d d 报文中交换了双方的l s a 头部，路由器如果发现对方的l s a 比自己 l s d b 中对应的l s a 新或有自己没有的l s a 就会通过链路狭态请求报文请求对 方将该l s a 发送给自己。因此其在报文中带上了关于该l s a 的描述，l s t y p e 、 l i n ks t a t e1 d 、a d v e r t i s i n gr o u t e r 这三个域在一个l s d b 中就能唯一确定个l s a 了。如果对方没有用链路状态更新报文进行响应，路由器在经过r x m t i n t e r v a l 所 规定的时长后会重传该请求。 ( 4 ) l s - u p d a t e 报文格式： o s p fp a c k e th e a d e r ( t y p e = 4 ) ( 1 9 2 ) # l s a s ( 3 2 ) l i n ks t a t ea d v e r t i s e m e n t ( 3 2 ) 其中各个域的值解释如下： # l s a s 说明该报文所携带的l s a 数目，然后为所携带的各个l s a 。 链路状态更新报文完成对链路状态请求报文的响应，同时扩散过程也是通过 链路状态更新报文来实现的。为了保证扩散、更新过程的可靠性，链路状态更新 报文中的l s a 必须被分别确认( 直接的或者隐含的) ，否则未被确认的l s a 将 被重传。 ( 5 ) l s - a c k n o w l e d g e m e n t 报文格式： 第三章协议报文格式 其中各个域的值解释如下： 每个被确认的l s a 由它的头部唯一确定。可以将对多个l s a 的确认放入同 一个报文中。 对于上面所述的五种协议报文除了h e l l o 报文，其它四种报文都只能在建立 了相邻性的路由器之间传送。而不管是哪一种协议报文，其在网络上的传送距离 都为一跳( 虚链路上除外) 。 3 2 链路状态数据库包含五种类型的l s a r o u t e r l s a 描述路由器的选定信息，由被描述的路由器自身产生。 n e t w o r k l s a 在有广播能力或为非广播多重接入( 简称n b m a ) 的中转网 络( 中转英文原文为t r a n s i t ，指有两个或多个路由器接入的网络) 上由指派路由 器( d e s i g n a t e dr o u t e r 简称d r ) 产生，描述接入该网络的所有路由器。 t y p e3s u m m a r y - l s a 描述区域外面自治系统内网络的路由信息，由a b r 产生。 t y p e4s u m m a r y - l s a 描述区域外而自治系统内a s b r 的路由信息，由a b r 产生。 a s - e x t e r n a l l s a描述a s 外部的路由信息，由a s b r 产生。 所有l s a 都具有统一的头部，其头部格式如下图所示，对其中各个域在下 面进行解释。 连接状态数据报文的报文头： l sa g e ( 1 6 )o d t i o n s ( 8 )l st y p e ( 8 ) l i n ks t a t ei d ( 3 2 ) a d v e r t i s i n gr o u t e r ( 3 2 ) l ss e q u e n c en u m b e r ( 3 2 ) l sc h e c k s u m ( 1 6 )l e n g t h ( 1 6 ) 其中各个域的值解释如下： 链路状态生成时间( l sa g e ) 指l s a 生成的秒数，为一个1 6 位无符号短整。 选项域( o p t i o n s ) 是对路由器o s p f 协议可选能力的描述。 链路状态类型( l s t y p e ) 是对l s a 分类的描述，如上所述分为五种。 链路状态i d ( l i n k s t a t e i d ) 的内容依赖于l s a 的类型，其分别为： 1 2 屯子科技大学硕士学位论文：0 s p f 坍议软件的设计与实现 1生成该l s a 路由器的路由器i d ( r o u l e ri d ) 。 2d r 在该网络上接口的i p 地址。 3目的网络的i p 地址。 4 所描述的a s b r 的路由器i d 。 5目的网络的i p 地址。 声明路由器( a d v e r t i s i n gr o u t e r ) 为产生该l s a 的路由器r o u t e r i d 。 链路状态序列号( l s s e q u e n c en u m b e r ) 对同一l s a 不同版本的标识。 链路状态校验和( l sc h e c k s u m ) 对整个l s a ( 不包括l sa g e 域) 所计算的 校验和，其计算算法与i p 头部校验和算法一致。 长度( 1 e n g t h ) 为以字节为单位的l s a 整体长度，包括2 0 字节的头部长度。 ( 1 ) r o u t e r - l s a ： 所有的o s p f 路由器都要生成该l s a 。它描述了位于同一区域下路由器的接 口的状态，只在一个区域内扩散。报文格式如下( 不含头部) ： 0 l v l e l b i ( 8 ) o# 1 i n k s ( 1 6 ) l i n ki d ( 3 2 ) l i n kd a t a ( 3 2 ) t y p e ( 8 )# t o s ( 8 )m e t r i c ( 1 6 ) t o s ( 8 ) 0t o sm e t r i c ( 1 6 ) l i n ki d ( 3 2 ) l i n kd a t a ( 3 2 ) 其中各个域的值解释如下： v 位置位说明路由器为一个或多个已建立全邻接虚链路( f u l l ya d j a c e n tv i r t u a l l i n k s ) 的一端( 同时指出其所属区域为中转区域) 。而e 位景位说明路由器为一 a s b r ，b 位置位则指出路由器为一a b r 。# 1 i n k s 域为路由器在该区域内的链 路数且。 下面的域都是用于描述路由器在该区域内的每一条链路。其中l i n ki d 、l i n k d a t a 域的取值都是由t y p e 域决定的。 路由器的链路类型有以下四种： 到另一路由器的点到点连接。 第三章协议报文格式 到中转网络的连接。 到残余( 英文为s t u b ，因译法不一致，故以后都用英文) 网络的连接( 注意， 协议中将到主机的连接也作为s t u b 网络的一种特例) 。 虚链路。 而其相应的l i n ki d 分别为： 相邻路由器的r o u t e ri d 。 d r 在该网络上的i p 地址。 该网的网络号。 虚链路另一端路由器的r o u t e ri d 。 l i n kd a t a 域的值分别为： 该接口的m i b i ii f i n d e x 值( 对未命名的点到点连接，u n n u m b e r e d p o i n t t o p o i n t ) 。 路由器在该接口上的i p 地址。 该s t u b 网络的掩码。 路由器在该接口上的i p 地址。 # t o s 域指出路由器该链路上提供的