（计算机软件与理论专业论文）ospf路由协议安全性研究.pdf

o s p f 路由协议安全性研究 摘要 o s p f 是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 k f o r c e 提出的一种基于链路状态的内部网关路由协议。 o s p f 通过传递、交换路由器的链路状态来得到整个网络的信息，从而维护一张网络有向拓扑图， 利用最小生成树算法( s p f ) 得到路由表。o s p f 路由器之间通过各种报文来实现维护一个分布式的 链路状态数据库，其中存放链路状态信息。o s p f 的报文中链路状态更新报文( l i n k s t a t e u p d a l e p a c k e t , l s u ) 是携带路由信息的重要报文，它可将路由信息传递到目的路由器上，但是l s u 在网络间扩散 的过程极可能受到外来入侵者的篡改和恶意攻击。针对l s u 携带的链路状态通告( l i n ks t a t e a d v c r t i s e m e n ll s a ) 的最大年龄攻击、序列号攻击等都可使网绍的稳定性和安全性受到影响。 本文详细阐述了o s p f 路由协议的运行原理、特点和o s p f 安全性的意义。分析了o s p f 路由协 议网络类型、五种协议报文以及链路状态数据库的建立、同步，更新原理，并在此基础之上具体分 析了o s p f 路由协议的安全性，针对o s p f 路由协议存在的诸多漏洞和可能受到的攻击提出了具体、 实用的防范措施。然赢在前入的研究基础之上，提出了一种基于l s u 的数字签名o s p f 保护机制， 既减少了目前已经存在的l s a 数字签名方案的开销又能很好的保护o s p f 路由，并设计实现运行上 述方案的路由器仿真系统，很好的验证了上述方案的正确性和可行性。最后，对本文提出的方案的 安全性和效率进行了详尽的分析与验证。 o s p f 路由协议的安全性是两络安全中最重要的问题之一，对o s p f 路由协议的安全性研究在可 预见的很长一段时间里都将是网络安全研究的重要议题。对这方面的研究成果可大大增强网络的安 全特性，具有很高的实用价值。 关键词：路由协议；开发最短路径优先路由协议；链路状态通告；数字签名：指派路由器：自 治系统 区域；区域边界路由器 r e s e a r c ho no s p fr o u t i n gp r o t o c o l ss e c u r i t y a b s t r a c t o s p fi sam u t i n gp r o t o c o ld e v e l o p e db yi f r p ( 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 t sai n t e r i o r g a t e w a yp r o t o c o lb a s e do nt h el i n ks t a t e 0 s p fg e t st h ew h o l en e t w o r k si n f o r m a t i o nb ye x c h a n g et h el i n ks t a t ei n f o r m a t i o nw i t ha l lo t i l e r r o u t e r s i tk e e p sam a pw h i c hd e s c r i b e st h en e t w o r k st o p o l o g y , t h e nu s es p fa l g o r i t h mt og e tt h er o u t i n g t a b l e 0 s p fr o o t e r so s ef i v et y p e so ft h ep a c k e t st os t r u c ta n dm a i n t a i nal i n ks t a t ed a t a b l ew h i c hi s d i s t r i b u t e ds t r o c t e do f fa l ir o u t e r si na r e a i nt h e s ed a t a b a s e s 。r o u t e r ss a v et h es a m el i n ks t a t ei n f o r m a t i o n l s u ( l i n ks t a t eu p d a t ep a c k e t ) i st h em o s ti m p o r t a n tp a c k e ti nt h e0 s p f sp a c k e t s b e c a u s ei tt a k 娼t h e r o u t ei n f o r m a f t o nf r o mo n er o u t e rt oa n yo t h e rr o u t e r s b u t w h e nt h el s ut r a n s m i to nt h en e t w o r k , i tm a y b ea t t a c k e db ya n yf a u l t yr o n t e r so ri n t r u d e r s t h e s ea r a c k st ol s a 。l i k em a x a g ea t t a c k , s e r i a ln u m b e r a t t a c k , a n ds oo n ，c a na f f e c tt h en c t w o r k ss t a b i l i z a t i o na n ds e c u r i t y t h i sa r t i c l ee x p a t i a t et h eo s p fr o u t i n gp r o t o c o l sp r i n c i p l e t h ec h a r a c t e r i s t i ca n dt h es i g n i f i c a n c eo f o s p f ss e c u r i t y a n a l y z e dt h ep r i n c i p l eo fo s p f sn e t w o r kt y p e 。p r o t o c o lp a c k e t sa n dl s d b ss t r u c t u r e , s y n c h r o n i z e ，u p d a t e 。b a s e do nt h e s e ，a r t i c l ea n a l y z e do s p fr o u t i n gp r o t o c o l ss e c u r i t y f o rt h o s eh o l e s ， g i v es e v e r a ls c h e m e st of i xt h e p r o b l e m s i nt i l et h i r dc h a p t e ro ft h i sa r t i c l e , w ep r e s e n t e f n c i e n t s o l u t i o n ，o s p fr o u t i n gp r o t o c o lb a s e do nt h el s ud i 西t a ls i g n a t u r ep r o t e c t i o n , t or e s o l v et h el i n ks t a t e r o u t i n gu p d a t ea u t h e n t i c a t i o np r o b l e m a tt h el a s tc h a t e ro f t h i sp a p e r , i td i s c u s s e st h ei s s u eo f t h ee f f i c i e n t a n ds p e n d i n gf o rt h e0 s p fr o u t i n gp r o t o c 0 1 1 1 1 es e c u r i t yo fo s p fr o u t i n gp r o t o c o li so n eo ft h em o s ti m p o r t a n tp r o b l e m si nt h ei n t e r o e ts e c u r i t y , t h er e s e a r c ho i lt h eo s p fr o u t i n gp r o t o c o l ss e c u r i t yw i l lb et h ei m p o r t a n ti s s u e 彻t h en e t w o r ks e c u r i t y t h e s er e s u l l so f t h i ss t u d yc a ng r e a t l ye n h a n c et h en c t w o r k ss e c u r i t y k e y w o r d s ：r o u t i n gp r o t o c o l ；o s p f ；l s a ；d i g i t a ls i g n a t u r e ；d e s i g n a t e dr o u t e r , a u t o n o m o u ss y s t e m ； a r e a ；a b r i l l 学位论文独创性声明 本人所呈交的学位论文是我在指导教师的指导下进行的研究工作及取得的研究成 果据我所知，除文中巴经注明引用的内容外，本论文不包含其他个人已经发表或撰写 过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并 表示谢意 作者签名 学位论文使用授权声明 硼栅定矗葛笋箍吁言篓缀攀 日期：y 归7 年；舟脏吾1 日期：为刃易j 1 5 l 创新点摘要 本文主要研究了o s p f 路由协议的安全性，其创新点如下： 1 本文分析了o s p f 路由协议内置的安全机制，分别指出了o s p f 三种内置安全机制存在的诸 多漏洞。分析了可能对o s p f 进行韵漏漏攻击，如最大年龄攻击、序列号攻击等。并针对这些漏洞 和攻击威胁提出了相应的建议和措施。 2 提出了一种基于l s u 的数字签名o s p f 机制。该机制针对o s p f 存在的诸多漏洞和时刻存在 威胁，改进了基于l s a 的数字签名保护机制，在不降低效能的情况下很好的降低了系统的开销和网 络的负荷。该机制采用对l s u 首部信息进行散列值计算，然后对其签名覆盖。以此来保护其在网络 上传输时的完整性和来源可靠性。该机制经本文实现的基于该机制的系统验证证明是一个可靠、高 效的o s p f 安全解决机制。 3 以本文提出的基于l s u 的数字签名o s p f 机制作为契机，在运行l i n u x 的主机上很好的实现 了运行该机制的o s p f 路由器。本系统在详细分析了o s p f 路由机制的基础上，实现了o s p f 路由协 议的标准部分，如接口状态机、d d 报文交换、d r 和b d r 的选举等模块。并且将本文提出的基于 l s u 的数字签名o s p f 机制运用到系统中，设计实现了基于该机制的路由仿真系统。 l v 大庆石油学院硕十研究生学位论文 引言 o s p f 路由协议是一种内部网关协议( i g p ) ，目前有相当多的路由器采用或支持这种 路由协议，它具有简单、高效等优点。随着i n m e t 的快速发展，作为网络最为核心部 分的路由协议的安全越来越受到众多研究人员的关注。 o s p f 路由协议由于其规范制定较早，虽经修改，却仍然存在诸多的漏洞，攻击者 可利用这些漏洞危害到整个自治系统的安全。针对这些漏洞，攻击者可以发起诸如最大 年龄攻击、最大序列号攻击等危害网络安全的攻击行动，这都会影响到自治系统中路由 信息的正确传递和识别，从而影响到网络的稳定和安全。鉴于目前恶劣的网络安全环境， 有必要深入的研究o s p f 路由协议的安全性，并尽可能的解决其存在的漏洞和威胁。 早在上个世纪八十年代，互联网络还没有普及之前，国外的一些研究机构就开始了 关于路由安全相关的研究。gf i n n 的1 2 6 和r p e r l m a n 的 2 4 , 2 5 奠定了在动态路由和链 路状态路由安全性的基础。至于针对o s p f 路由协议，s m u r p h y 和m b a d g e r 的论文 ( d i g i t a ls i g n a t u r ep r o t e c t i o no f o s p fr o u t i n gp r o t o c 0 1 ) ) 提出了数字签名来保护o s p f 路 由协议的l s a 的方案，开创了o s p f 路由协议安全性研究的一个全新的领域。但是 m u r p h y 等人提出的数字签名方案也有一个致命的弱点，就是对每一个l s a 作签名并在 目的端作计算判断，这样的一个过程对硬件的运算能力要求非常的高，而且这一算法也 对网络的传输带宽要求更加的高，这并不符合o s p f 路由协议设计之初高效实现数据包 路由的初衷。因此，在此之后又有许多后续的研究对此或做修改，或提出全新的算法， 来解决o s p f 的安全性问题。s t e v e nc h e u n g 和rh a a s e r 分别在其各自的论5 c 9 ，2 7 1 q 1 提 出了一种基于h a s h 序列的算法，这种算法一定程度上降低了数字签名保护l s a 的开销。 国内在o s p f 路由协议安全性研究方面紧跟国际先进水平，众多的高校和科研机构 都将大批的人力物力投入到这方面的研究之中。论文8 ，1 0 l 等都对o s p f 路由协议的安 全性作了详细而深入的分析，对国内路由协议的安全性、特别是o s p f 路由协议的安全 性做出了贡献。在m u r p h y 提出方案后，论文【2 2 】j 艮好的实现了数字签名保护o s p f 路由 协议l s a 数据的方案，为数字签名保护l s a 的可行性提供了最直接的有力证据。电子 科技大学等一些国内知名高校在这方面的研究处于一种国内领先的态势。另外，国内众 多的网络设备厂商如华为、中兴等也在这方面投入巨资进行研发。 本论文致力于o s p f 路由协议的安全性研究，以使路由信息远离众多的威胁和攻击， 实现网络安全的更进一步的提高。本文主要研究了o s p f 路由协议的路由机制及其安全 性的相关理论与技术，研究分析了已有的o s p f 路由协议安全性解决方案，设计并实现 了基于l s u 的数字签名o s p f 路由协议系统。 本文主要研究的内容详细叙述如下： 1 o s p f 路由机制的研究 引言 该部分内容主要研究o s p f 的路由机制，包括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 的安全性得到了一定程度上的保证。但是，随着i n t e r a c t 的发展，这些机 制同样也被发现有许多漏洞的存在。如何弥补o s p f 的诸多漏洞，应对各种来自网络的 威胁和攻击? 这就需要对o s p f 路由协议的安全性做一个全面的、深入的研究，这有利 于更好的改进o s p f 的安全解决方案。 3 基于l s u 的数字签名o s p f 的设计与实现 本文主要研究的是o s p f 路由协议安全性的相关理论与技术，在分析了o s p f 路由 协议的安全性和前人提出的若干安全解决方案后，本文提出了一种更为高效的基于l s u 的数字签名o s p f 方案。并参考o s p fv 2 标准，实现了一个基于l s u 数字签名o s p f 路由协议的系统。具体实现的部分有：d d 报文交换模块、h e l l o 协议的实现、接口有限 状态自动机、指派路由器和备份指派路由器的选举模块，以及数字签名保护的l s u 生 成与泛洪等。这些模块组合成了一个完整的数字签名保护的o s p f 路由协议系统。 2 大庆石油学院硕七研究生学位论文 1 10 s p f 概述 1 1 1 路由器与路由协议 第i 章0 s p f 路由机制分析 i n t e m e t 是一个报文交换网络，它将各种用途的计算机连接起来，以便相互间交换 信息。这些信息编码成一定长度的比特串，即报文( p a c k e t ) 。这些报文穿过i n t e m e t 从 源端到达目的端必须作出路由选择：报文是从a 路径发出，还是走b 路径? 做出这种 选择的设备就是路由器( r o u t e r ) 。为做出这种选择而运行于各路由器上的分布式算法， 称作路由选择协议( r o u t i n gp r o t o c 0 1 ) 1 1 1 。 路由器的主要工作就是为经过该路由器的每个数据帧寻找一条最佳的传输路径，并 将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法是路由器 的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据路由 表( r o u t i n g t a b l e ) ，供路由选择时使用。路由表中保存着子网的标志信息、网上路由器 的个数和下一个路由器的名字等内容。路由表可以是由系统管理员固定设置好的，也可 以由系统动态修改，可以由路由器自动调整，也可以由主机控制【2 】。 路由器的主要功能如下： 1 在网络间截获发送到远地网段的报文，起转发的作用。 2 选择最为合理的路径，引导通信的进行。要实现这一功能，路由器就需要通过 查找路由表中存放的根据当前网络计算得到的路由信息，选择一条代价最低的路径。 3 路由器在转发报文的过程中可以将较大的报文分解成数个小型的报文以方便报 文的传输。 4 运行多种协议的路由器可以作为几个不同协议的网络的连接平台。 5 路由器的主要任务是把通信引导到目的地网络，然后到达特定的节点站地址。 后一个功能是通过网络地址分解完成的。例如，把网络地址部分的分配指定成网络、子 网和区域的一组节点，其余的用来指明子网中的特别站。分层寻址允许路由器对有很多 个节点站的网络存储寻址信息【2 】。 路由协议有静态路由协议与动态路由协议之分。静态路由协议不利用网络的信息来 选择路由，而是按照一个既定的规则来选择路由，比如手动的配置。这种路由协议在网 络拓扑变化不频繁且比较小的网络有一定的优势，它不能根据拓扑的变化对路由选择做 出反应，它的优点是简单、高效和可靠。与此相反，动态路由协议则能根据拓扑结构的 变化，在路由信息的汇总后得到一个更加正确的新路由，以适应流量和拓扑的变化【3 1 。 路由协议又可按照作用区域的不同可分为内部网关协议( i n t e r i o rg a t e w a yp r o t o c 0 1 第1 章0 s p f 路由机制研究 i g p ) 和外部网关协议( e x t e r n a lg a t e w a yp r o t o c o l ，e g p ) 4 1 。内部网关协议作用于自治 系统内部，反之，e g p 作用于自治系统外部。如：o s p f 、r i p 、i g r p 、e i g r p 等都属 于i g p ，常见的e g p 则有b g p 、b g p 4 等。 1 1 20 s p f 路由协议 o s p f ( 咖s h o r t e s tp a t hf i r s t ) 作为目前互联网络应用最为广泛的内部网关路由协 议( i n t e r i o rg a t e w a yp r o t o c o l ，i g p ) ，主要提供自治系统( a u t o n o m o u ss y s t e m ，a s ) p i j 的动 态选择路由。它是一种典型的链路状态协议，不同于距离向量协议( 如r i p 等) 。 i g p 作用范围与外部网关路由协议( e x t e n d e dg a t e w a yp r o t o c o l ，e g p ) 有所不同，e g p 用于自治系统外的网关之间交换可达性信息、寻找可达路径。i g p 则作用于自治系统内 部，自治系统内部的拓扑信息与路由信息并不为外部网关所知。自治系统对于外部网关 而言是透明的。本文主要讨论的是o s p f 路由协议，是目前互联网络应用最为广泛的内 部网关路由协议，主要提供自治系统( a u t o n o m o u s s y s t e m ，a s ) 内的动态选择路由。目前 互联网络应用最为广泛的内部网关路由协议之一。 o s p f 有以下特性【4 】： 适应范围广支持各种规模的网络，最大可支持数百台路由器。 快速收敛网络拓扑结构发生变化后立刻发送更新报文，使这一变化在自治系统 中同步。 无自环由于o s p f 根据收集到的链路状态用s p f 算法计算路由，从算法本身保 证了不会生成自环路由。 区域划分允许将自治系统划分成区域，区域间传送的路由信息被进一步抽象， 从而减少了占用的网络带宽。 等价路由支持到同一目的地的多条等价路由。 路由分级4 类不同的路由，按优先顺序来说分别是：区域内路由、区域间路由、 第一类外部路由和第二类外部路由。 支持验证支持基于接口的报文验证，以保证报文交互的安全性。 组播发送在某些类型的地址上以组播形式发送报文，以减少对其他设备的干 扰。 1 20 s p f 网络 1 2 10 s p f 的四种网络类型 o s p f 将网络作了详细的分类，并且o s p f 路由协议在不同的子网技术上运行的方 式有一定的差异性，如：邻居的发现与保持、链路状态数据库的同步和抽象。这些差异 4 大庆石油学院硕士研究生学位论文 使得在o s p f 路由协议上实现安全方案时需要全面考虑这些问题。本文第三章在实现基 于l s u 的数字签名保护的o s p f 路由协议方案时充分考虑到了这些差异性。为简化研究 内容，本文设计并实现的系统以广播型网络作为基本的网络类型，系统中涉及这些差异 性的地方都是针对广播型网络的。 o s p f 根据链路层协议类型将网络分为下列四种类型，现列举如下1 4 l ： 1 广播( b r o a d c a s t ) 类型：当链路层协议是e t l l e m e t 、f d d i 时，o s p f 缺省认为 网络类型是b r o a d c a s t 。在该类型的网络中，通常以组播形式( 2 2 4 0 0 5 和2 2 4 0 0 6 ) 发送协议报文。 2 n b m a ( n o n b r o a d e a s tm u l t i a c c e s s ) 类型：当链路层协议是帧中继或a t m 时， o s p f 缺省认为网络类型是n b m a 。在该类型的网络中，以单播形式发送协议报文。 3 点到多点p 2 m p ( p o i n t t o m u l t i p o i n t ) 类型：没有一种链路层协议会被缺省的 认为是p o i n t - t o m u l t i p o i n t 类型。点到多点必须是由其他的网络类型强制更改的。常用 做法是将非全连通的n b m a 改为点到多点的网络。在该类型的网络中，以组播形式 ( 2 2 4 0 0 5 ) 发送协议报文。 4 点到点p 2 p ( p o i n t - t o p o i m ) 类型：当链路层协议是p p p 或h d l c 时，o s p f 缺省认为网络类型是p 2 p 。在该类型的网络中，以组播形式( 2 2 4 0 0 5 ) 发送协议报文。 1 2 2 自治系统与区域的划分 早期的i n t e r a c t 是由a r p a n e t 及其伙伴网络的互联发展起来的 3 1 ，一直到8 0 年代初 期，它还是一个单一的网络。随着i n t e m e t 的发展，接入i n t e m e t 的路由器越来越多，路 由负载不断增加，路由表的大小也随着接入的网络数量的增加而增加【3 1 。将i n t e r n e t 划 分成一系列的自治系统( a u t o n o m o u ss y s t e m ，a s ) 可解决统一网络内路由器数目增加 带来的一系列问题。每一个自治系统由同一个机构管理下的一系列路由器和网络组成。 一个自治系统内的路由器交换网络拓扑信息，寻找最佳路径。自治系统内的网络拓扑信 息不为自治系统外的路由器所知道。自治系统之间通过专门的路由器进行连接，这些路 由器之间交换可达性信息，寻找可达路径。这样一来，可大大的减少路由表的条数，减 小网络的规模，让网络更加便于管理。 。 另外，在划分自治系统的基础之上，在o s p f 协议中，又将一个自治系统划分为若 干个集合，这样按照一定的o s p f 路由法则组合在一起的网络或路由器的集合被称作区 域( a r e a ) 睁】。区域的划分更迸一步细化了网络，更好的优化了o s p f 路由协议。 由于o s p f 划分了区域和自治系统，使得在区域和自治系统各个位置的路由器其任 务也不尽相同。不同的任务对应着不同的路由器，根据所在位置和任务的不同可将自治 系统内的路由器作如下细分1 6 ； 1 区域内路由器( i n t e r n a lr o u t e r s ) ，该类路由器的所有接口都属于同一个o s p f 区域。 5 第1 章0 s p f 路由机制研究 2 区域边界路由器a b r ( a r e ab o r d e rr o u t e r ) ，该类路由器可以同时属于两个以 上的区域，但其中一个必须是骨干区域。a b r 用来连接骨干区域和非骨干区域，它与 骨干区域之间既可以是物理连接，也可以是逻辑上的连接。 3 骨干路由器( b a c k b o n ep o u t e r s ) ，该类路由器至少有一个接口属于骨干区域。 因此，所有的a b r 和位于主干区域( b a c k b o l i e a r e a ) 的内部路由器都是骨干路由器。 4 自治系统边界路由器a s b r ( a u t o n o m o u ss y s t e mb o u n d a r yr o u t e r ) ，与其他a s 交换路由信息的路由器称为a s b r 。a s b r 并不一定位于a s 的边界，它有可能是区域 内路由器，也有可能是a b r 。只要一台o s p f 路由器引入了外部路由的信息，它就成 为a s b r 。 上述不同类型的路由器发送的l s a 所到达的目的地有所不同。因此一个路由嚣生 成的l s u 报文中可能包含多种类型的l s a 。本文实现的基于l s u 的数字签名o s p f 路 由协议系统放弃了l s a 的签名，因此l s u 中的l s a 类型并不会影响到系统的签名与验 证，更加不能影响到系统其它模块的运行。另外，为方便研究，本文所提出的基于l s u 的数字签名o s p f 系统只是针对区域内部路由器作了实现，但本系统也对其它几种路由 器类型的实现预留了接口，为系统的进一步完善留出了空间。 1 2 3 指派路由器与备份指派路由器 在广播网和n b m a 网络中，o s p f 路由协议为简化路由器之间所要传递的路由信息， 定义了指派路由器d r ( d e s i g n a t e dr o u t e r ) 和备份指派路由器b d r ( b a c k u pd e s i g n a t e d r o u t e r ) 。区域内的所有路由器只是与d r 或b d r 建立邻接关系，由d r 来实现路由信 息的广播，从而让区域内的路由器都能够同步链路状态数据库。一旦d r 失效，b d r 将 立刻担当原来d r 担当的角色。关于d r 与b d r 的选举过程，本文在后续的章节中将 详细介绍其实现过程。 1 3o s p f 协议报文及l s a 在o s p f 路由协议中，路由报文是用于传递路由信息的重要媒介，也是路由器之间 通信、建立邻接关系的重要工具。本文所实现的基于l s u 的数字签名o s p f 系统也是针 对o s p f 协议报文中链路状态更新报文所实现的。 1 3 10 s p f 的协议报文 o s p f 用m 报文直接封装协议报文，协议号为8 9 。一个比较完整的o s p f 报文如图 1 1 所示( 以l s u 报文为例) ： 6 大庆石油学院硕 研究生学位论文 图卜1o s p f 报文结构门 在o s p f 协议中，定义了五种协议报文。链路状态数据库的建立、更新、同步，路由器 邻接关系的建立等等都需要通过报文的传播、交换来实现。每一个o s p f 报文都是以一 个2 4 b i t 的o s p f 报文头开始，如图1 2 所示： 版本号类型包长度 路由器i d 区域i d 校验和验证类型 验证字段 验证字段 图1 - 2o s p f 协议报文头部川 0 s p f 协议的报文头部数据结构表示如下： t y p e d e f s t r u c t i n tv e r s i o n ； i n tt y p e ； i mp a c k e t l e n g t h ； p a d d r e s s1 h i s r o u t e r i d ； i n tt h i s a r e a l d ； i n tc h e e k s u m ； i n ta u t y p e ； d o u b l ea u t h e m i c a t i o n ； o s p f p a e k e t h d r ； 其中t y p e 变量是用来标识o s p f 的报文类型的，o s p f 共有五种报文，分别是： l 。h e l l o ；用于动态发现邻居、确认邻居阚的双向连接、维持邻接关系以及指派路 由器的选举等。h e l l o 报文数据结构表示如下： t y p e d e f s t r u c t o s p f p a c k e t h d ro s p f p k h e a d e r ； i n tt h i s n e t w o r k m a s k ； i n td e a d i n t ； i n th e l l o i n t ； i n tt h i s r t r p r i ； i p a d d r e s sd e s g r o u t e r ； i p a d d r e s sb a e k u p d e s g r o u t e r ； 7 第1 章o s p f 路由机制研究 i p a d d r e s sr t r s f r m w h i c h h e u o r e c 1 0 ； h e l l o p a c k c t ； 2 d a b b l ed e s e r i p t i ：两台路由器进行数据库同步时。用d d 报文来描述l s d b ， 内容包括l s d b 中每一个l s a 的头部( l s a h e a d e r 可以唯一标识一个l s a ) 。d d 报文 数据结构表示如下： t y p e d c f s t r u c t o s p f p a c k e t h d ro s p f p k h e a d e r ； i n ti b i t ； i n tm b i t ； i mm s b i t ； h a td d s e q n o ； d d l s a d vd d l s a d v 10 ； d d p k ； 3 l i n ks t a t er e q u e s t ：链路状态数据库交互进程结束后从路由器根据一个链路状态 数据库描述报文提供的信息确定要更新的l s a ，然后向主路由器发送链路状态请求报 文，请求主路由器向其提供较新的l s a 。l s r 报文的内容包括需要的l s a 的摘要。 r e q u e s t 报文数据结构表示如下： t y p e d e f s t r u c t o s p f p a c k e t h d ro s p f p k h e a d e r ； l s r e q p l d s a d vl s r e q p k l s a d v 1 0 ； l s r e q p k ； 4 l i r i l 【s t a t eu p d a t e ：路由器内外扩散其链路状态信息，将一个或多个l s a 封装到 l s u 中然后扩散出去。l s u 报文数据结构表示如下： t y p e d e fs t r u c t o s p f p a c k e t h d ro s p f p k i - i e a d e r ； 1 0 n gn o o f a d v s ； r e s l s a r e s l i n k s t a t e a d v ； r r a l s a r r a l i n k s t a t e a d v ； g r p m b r l s ag r p m b r l i n k s t a t e a d v ； r o u t e r l i n k a d v r o u t e r l i n k s t a t e a d v ； n e t w o r k l i n k a d vn e t w o r k l i n k s t a t e a d v ； s u m m a r y l i n k a d vs u m m a r y l i n k s t a t e a d v ； l s u p d a t e p k ； 5 l i n ks t a t ea c k n o w l e x t g m e n t ：用来对接收到的l s u 报文进行应答。内容是需要 确认的l s a 的头部，一个l s a c k 报文可以对多个l s a 进行应答。 t y p e d e f s t r u c t o s p f p a c k e t h d ro s p f p k h e a d e r ； r e s l s a h e a d e rr e s l s a h e a d e r , l s a c k p k ； 大庆石油学院硕i ：研究生学位论文 1 3 2 链路状态通告 l s a ( l i n ks t a t ea d v e r t i s e m e n t ，链路状态通告) ，路由器借此来向其它路由器通告 其链路状态和开销。每一个在自治系统内的路由器都产生一个、两个或更多的l s a ，多 个l s a 在目的路由器的组合便是链路状态数据库。 i e t f 将l s a 分为五种，它们分别是；r o u t e rl s a s ，n e t w o r kl s a s ，s u m m a r yl s a s ， a s e x t e r n a l l s a s 。 类型1 ：r o u t e rl s a s ，所有的路由器都要生成这种l s a ，用于描述位于同一区域下 路由器的接口状态，它只在本区域内扩散。 类型2 ：n e t w o r kl s a s ，由广播型网络和n b m a 网络中的指派路由器产生，用于描 述本网络的情况，记录了网络中路由器的情况，只在区域内部传播。 类型3 和4 ：s u m m a r yl s a s ，由区域边界路由器生成，只在与该边界路由器相应的 区域中扩散。每一个s u m m a r yl s a s 描述了一个a s 内其它区域的路由，类型3 描述的 目的地址是网络，而类型4 描述的目的地址是a s 边界路由器( a s r ) 。 类型5 ：a s e x t e r n a l l s a s ，由自治系统边界路由器产生，描述了自治系统外的路 由信息，可在整个自治系统内传播。 这五类l s a 都是由其对应的路由器产生。本文第四章所叙述的基于l s u 的数字签 名o s p f 路由协议系统以一个c l s a 的类来描述l s a 。各种类型的l s a 都是以该类作 为父类继承而来。 1 4 链路状态数据库及其形成与维护 在一个区域内，所有的o s p f 路由器都需要维护一个相同的链路状态数据库，这个 数据库其实是一张关于这个区域的网络拓扑图，图中的每一条边都有一个相应的权值， 表示向该方向传输数据的代价。在这张图的基础上路由器就可以通过d i j k s t r a 算法来计 算到每一个目的地的最短路径，从而生成路由表。从另一个方面讲，路由器上的链路状 态数据库也是一个l s a 的集合，链路状态数据库是路由器在综合其它路由器的l s a 后 生成的。 1 4 1 链路状态数据库的同步 在链路状态路由算法中，保持所有路由器的链路状态数据同步是一项重要的事情。 o s p f 通过要求邻接路由器保持同步来简化这一机制。所有的路由器的同步都是建立在 以下四个条件的基础之上的1 3 ： 9 第l 章0 s p f 路由机制研究 1 动态发现邻居 2 确认邻居问的双向链接关系 3 维持与邻居之间的邻接关系 4 。指派与备份指派路由器的选举产生 这四个条件的产生都是h e l l o 协议作用的结果，路由器发送h e l l o 报文让其它路由 器发现它的存在，然后通过双向发送h e l l o 报文来确立双向链接的邻居关系和保持邻接 关系。指派路由器和备份指派路由器的选举则需要前三者作为先行条件。 在路由器开始尝试邻接关系建立之时，链路状态数据便开始了同步的进程。每一个 数据库描述报文详细描述了该路由器链路状态数据库中的l s a 集合。如果邻居发现它 链路状态数据库中的l s a 较老，则路由器会将此l s a 作一标记以便l s u 来临时更新。 这一发送和接收数据库描述分组的过程被称作“数据库交换进程”。在这一进程中，两 个路由器是一个主从的关系。每一个数据库描述分组都有一个序列号。 在数据库交换进程结束后，路由器就知道了自己的数据库中哪些l s a 较旧需要更 新，路由器通过发送链路状态请求报文( l i n ks t a t er e q u e s t ，l s r ) 到对端路由器来请 求更新l s a ，l s r 报文中包含了需要更新的l s a 的摘要。 主路由器在收到l s r 报文后通过读取l s r 中l s a 摘要确定需要发送到从路由器的 l s a 。然后将l s a 封装到l s u 报文中发送到从路由器。 从路由器在收到l s u 报文后需要向主路由器发送一个应答信号，即发送一个l s a c k 报文。如果主路由器在一定的时间间隔内( r x m t i n t e r v a l ) 没有收到来自从路由器的确 认应答，则主路由器会重新发送链路状态描述报文。这就是路由器间同步数据库的过程。 两个基本的数据库操作添加一个l s a 到数据库和从数据库中删除一个l s a 的 基本流程如图1 3 所示： 1 0 图1 - 3 向( 从) 数据库中添加或删除l s a 大庆石油学院硕l 研究生学位论文 1 4 2 链路状态数据库例子 我们可以用有向图来描述一个自治系统。网络和路由器是这个图中的顶点。网络和 路由器之间以及路由器和路由器之间的关系则用图中的点和边来表示：如果表示两个路 由器的点用一条边连接起来，则表示这两个路由器通过一个点到点的网络相连；如果一 个表示路由器的点和一个表示网络的点用一条边连接起来，则表示这个路由器有一个接 口与这个网络相连。按照这样的规则，我们可以得出如图l - 4 这样的一个有向图用于表 示某一个网络。其中路由器r e ，r 瓦，r c 和n l 网络之间是双向连接的，因为n i 网络是 一个t r a n s i t 网络，其它的网络则为s t u b 网络，与路由器之间单向连接。所有属于该自治 系统的路由器都通过一定的方式来存放该拓扑图，这种方式便是链路状态数据库。图l - 4 所示的拓扑结构在链路状态数据库中可逻辑表示为表1 1 所示。在这个数据库的基础上， 就可以通过d i j k s t r a 算法得出到达目的地的最短路径。到达网络中各个节点的最短路径 可以用一最短树来表示。 图1 4 有向图表示的网络拓扑例子 第1 章0 s p f 路由机制研究 表l - i 链路状态数据库的逻辑表示 r 瓦r t r ir 乃 n i 1 0 2 0 5 2 0 5 5 5 0 0 o 1 5 最短树 每一个o s p f 路由器在形成链路状态数据库之后，都会运用d i j k s t r a 算法，计算得 到一个以自己为根节点的最短树p l 。一个路由器生成最短树的过程可以分为两个阶段。 在第一阶段，只有路由器与t r a n s i t 网之间的链路被添加到最短树中；第二阶段，路由器 才添加到达子网的链路到最短树中。最短树给出了去任何目的主机和网络的路径，但是 只有下一跳地址在口转发中使用p 】。以r l 为例，在其上运行d i j k s t r a 算法，得到最短 树，然后再根据这个最短树来计算出r 的路由表。由于这个链路状态数据库只是有关 本自治系统内的，所以，得到的路由表也只是本自治系统内的路由表。图1