（通信与信息系统专业论文）ospf协议软件的设计与实现.pdf

电子科技大学硕士论文：o s p f 协议软件的设计与实现 摘要 o s p f 是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 ) 于1 9 8 8 年提出的一种基于 链路状态算法的动态路由协议，它是用于自治系统内部的内部网关路由协议。本 课题是在v x w o r k s 操作系统上以软件实现o s p f 协议。整个o s p f 软件的实现是 以公司开发了的路由器软、硬件作为基本平台。 本文首先介绍了o s p f 的基本概念、原理和工作过程。通过对r f c 2 3 2 8 的 阅读和分析，讨论了o s p f 在v x w o r k s 操作系统上的软件实现，包括程序的总体 设计，o s p f 的注册和各个模块的实现。最后介绍了路由器通过达建不同的网络拓 扑结构对o s p f 进行测试，说明测试情况并作出相应的结论。 关键词：路卣表，指定丽由器，备份指定路由器，链路状悉广告，链路状态数据 ，t7 一 库，洪泛，广播，点对点，点对多点，n s m a ，虚链路，自治系统，邻居。 、t a d d r e s s ) ； s p l v a l u e 2 s p l n e t o ； i n a d d r t o i f p ( i p _ a d d r e s s ，p _ i n t e r f a c e ) ； s p l x ( s p lv a l u e ) ； 由于涉及到对描述下层接v i 信息的结构进行访问，s p i n e t ( ) 是将当前任务的 优先级提升为同网络层有相同的优先级。宏调用i n a d d r t o i f p ( i p _ a d d r e s s ， p _ i n t e r f a c e ) ；就是通过i p 地址去得到相应的下层接口的i f n e t 指针。s p l x ( s p lv a l u e ) 是恢复以前的任务优先级。 i f n e t 结构如下： s t r u c ti f n e t c h a r + i f _ n a m e ； p n a m e e g ”e n ”o r ”1 0 ”+ s t r u c ti f n e t+ i fn e x t ；7 + a l ls t r u c ti f n e t sa r ec h a i n e d + 7 s t r u c t i f a d d r i f _ a d d r l i s t ； i l i n k e dl i s to f a d d r e s s e s p e r i f 4 | i n ti fp c o u n t ；n u m b e r o f p r o m i s c u o u sl i s t e n e r s | c a d d r _ ti fb p f ； 7 p a c k e t f i l t e rs t r u c t u r e4 u s h o r t i fi n d e x ；| n u m e r i c a b b r e v i a t i o nf o rt h i si f | s h o r ti fu n i t ；净s u b ，u n i tf o rl o w e rl e v e ld r i v e r | s h o r t i u i m e r ； 户t i m e t i li fw a t c h d o gc a l l e d + 皇王型垫盔堂堡主笙奎! ! ! 翌塑望鏊堡塑堡生量塞望 ， s h o r t s t m c t s t r u c t i n t m t i f _ f l a g s ； i f _ d a t ai f _ d a t a ； m b l k + p l n m m b l k ( + i f j n i t ) ( i n tu n i t ) ； ( + i f _ o u t p u ( ) ( s t r u c ti f n e t s t r u c tr t e n t r y + ) ； + u p d o w n ，b r o a d c a s t ，e t c + ，+ s t a f f s t i c sa n do t h e rd a t aa b o u ti f4 + c h a i no f m u l t i c a s ta d d r e s s e s + + i n i tr o u t i n e + + ，s t r u c tm b u f + ，s t r u c ts o c k a d d r + ， o u t p u tr o u t i n e 4 | i n t ( + i f _ s t a r t ) ( s t r u c ti f n e t + ) ； + i n i t i a t eo u t p u tr o u t i n e + i n t ( + i f j o c t l ) ( s t r u c ti f n e t + ，i n tc m d ，c a d d ud a t a ) ； | i o c t lr o u t i n e4 | i n t ( + i f _ r e s e t ) ( i mu n i t ) ； l b u sr e s e tr o u t i n e | i m ( + i f _ r e s o l v e ) 0 ； | a r pr e s o l v ea td r i v e rl e v e l | v o i d ( + i f _ w a t c h d o g ) ( i n tu n i t ) ； | t i m e rr o u r i n e 女l s t n l c t i f q u e u ei fs n d ； o u t p u tq u e u e 4 v o i d + p c o o k i e ； | 4u s e dt or e f e r e n c et h es u b l a y e rs t r u c t u r e | ； 由于我们的路由器中下层协议注册不规范，h d l c ，帧中继和以太网的接口 标志都是注册的广播网类型，因此通过i 删a g s 来区别接口类型是不行的。p p p 的 接口标志注册的是点对点。当o s p f 要区分下层接口类型时，只能通过i fd a t a 下的i f i _ t y p e 来区别接口类型。若i u a t a i f i _ t y p e 是广播网，o s p f 的接口类型设 为o s p f _ b r o a d c a s t , 若i - d a t a i f i _ t y p e 是帧中继，设默认值为o s p t n b m a ， 若i f - - d a t a i f it y p e 是p p p 或h d l c 设为o s p f p o i n t t o p o i n t 。由此，o s p f 能根据下层的协议类型，设置在o s p f 中的接口类型。 3 7 电子科技大学硕士论文：0 s p f 协议软件的设计与实现 3 1 多播的支持 第三章部分模块的实现 o s p f 中需要下层对多播包的支持。所有的o s p f 路由器都应该支持多播地 址为2 2 4 0 0 5 和2 2 4 0 0 6 的接收和发送。对于多播地址2 2 4 0 0 5 ，除了n b m a 的h e l l o 包外，其他类型的h e l l o 包都是以该地址发送，洪泛过程期间某些 o s p f 协议包也是以该地址发送。对于多播地址2 2 4 0 0 6 ，o s p f 中的d r 和b d r 需要能够接收该目的地址的o s p f 包，在洪泛过程期间，某些o s p f 协议包是向 该地址发送的。 因此，需要考虑两点： 一是支持对目的地址是2 2 4 0 0 5 和2 2 4 0 0 6 的i p 包进行接收：对此v x w o r k s 提供相应的下层接口调用函数s t r u c tm b l k + i na d d m u l t i ( s t r u c ti na d d r ，s t r u c t i f n e t + ，s t r u c ti n p c b + ) 。该函数参数指明了所要加入的多播地址和相应的接口。当 下层接口是以太网口时，对所加入的多播地址会计算出相应的h a s h 值，对6 4 位h a s h 表置位。这样以来当以太网口在收到多播包时同样计算其h a s h 值， 并在h a s h 表中检查相应的位是否被置位了，若置位了则收此包，反之则将其 丢弃。i n还会在相应接口的 结构下维护一个多播地址列表。对于_ a d d m u l t i 0 i f n e t 串口，多播包的接收与据收不是由硬件来完成的，而是在收到多播包后检查相应 于该接口的i f n e t 结构所维护的多播地址列表中是否有该多播地址。总之，只要 调用函数i n _ a d d m u l t i ( ) ，不管是在哪一层最终都能完成对多播包接收的支持。在 我们调用函数i na d d m u l t i ( ) 时，发现当需要将某个地址加入多播组时，调用一次 i n a d d m u l t i ( ) 会申请2 0 8 0 字节的空间，但将相同的地址加入多播组则不用重 新申请。 二是支持对目的地址是2 2 4 0 0 5 和2 2 4 0 0 6 的i p 包进行发送：当o s p f 发多播包时，调用函数i eo u t p u t ( s t r u c tm b u f4 ，s t r u c tm b u f4 ，s t r u c tr o u t e ，i n t ， s t r u c t i p _ m o p t i o n s + ) ，在结构i pm o p t i o n s 的i m o _ m u l t i c a s t _ i f p 中指明了下层接1 3 ， 因此对多播地址的支持主要是看下层协议是否支持。 网络接1 ：3 层的各个协议( 包括以太网，帧中继，p p p , h d l c 等) 是以e n d 设备注册给m u x 层的，注册的接口函数之一是加多播地址。当i p 层发一多播 包时，网络接口层计算其硬件地址，并封装该i p 包将其发送出去。以太网拥有 加多播地址的函数，支持多播地址。p p p , h d l c ，帧中继注册时的加多播地址函数 都为n u l l ，不支持多播地址。当下层协议是p p p 和h d l c 时，只需按照一般 的单播包进行封装，当下层协议是帧中继时可将每一个多播i p 包在多条p v c 上 皇王型垫查堂堡主笙壅! ! ! 望垫：坚鏊笪塑堡生量壅墨 用不同的d l c i 来封装进行发送，达到多播的效果。 o s p f 对多播包的发送与单播包的发送虽然都是调用函数i p _ o u t p u t 0 ，但却 不同。对单播包，i p 层能根据目的地址查找路由，找到该i p 包应该从哪个接口 输出，从而交给相应的下层协议( p p p o h d l c ，帧中继) 进行封装处理。但是对于 多播包，由于目的地址是多播地址，因此i p 层不能知道到底该从哪个接口输出， 因此在o s p f 发送多播包调用i p时，需要设置选项，告诉ip层从哪个接_output() 口输出，同时将t t l 设为1 ，因为o s p f 多播包不需要转发。 3 2m d 5 子模块的实现 按照m d 5 的算法将任意长的包进行单向杂凑计算，所得的值是一个1 6 字 节( 1 2 8 位) 的固定长度值。 发送o s p f 包时，用m d 5 计算如下： o s p f 包 m d 5 计算 - i 发方r l k e y + o s p f 包 杂凑值1 图3 1 发送方m d 5 计算 当o s p f 要对包进行m d 5 认证时，将o s p f 包后附加一个用户配置的1 6 字节密钥，进行m d 5 计算，将所得的1 6 字节( 1 2 8 位) 结果附加到原来的o s p f 包后边，然后将其发送出去。 接收m d 5 加密的o s p f 包，进行校验如下： o s p f 包 杂凑值1 + o s p f 包 m d 5 计算 。i 收方r 1 k e y o s p f 包 收方 k e v 图3 - 2 接收方m d 5 计算 圈? 电子科技大学硕士论文：o s p f 协议软件的设计与实现 由于m d 5 算法是单向杂凑计算，因此在接收包时，通过上图所述进行m d 5 校验，若杂凑值2 等于杂凑值1 则认为m d 5 校验成功，否则m d 5 校验不成功， 丢弃该包。 需要注意的是o s p f 包并未被加密，它还是照样以明文的形式发送出去， 只是o s p f 包之后附加了一个杂凑值。 3 3 配置子模块的实现 o s p f 为用户提供了一些配置命令，用于实现用户与o s p f 的交互。由于要 使用户对o s p f 的数据结构配置和用户能了解当前o s p f 的运行状态，首先需要 对o s p f 进行初始化，但此时o s p f 中的两个任务不一定运行起来，因此提供两 条命令，r o u t e ro s p f ，对o s p f 进行初始化，然后等待一个标志被置为t r u e ， 该标志为t r u e 则产生前面所述的两个任务。另一条命令是s t a r t ，它将标志置为 t r u e ，表示可以启动o s p f 的两个任务。这一点与c i s c o 路由器不同。其他用 户输入的命令同c i s c o 路由器基本相同。o s p f 提供这些命令的接口函数，当用 户输入这些命令时，将其解析，然后调用相应的接口函数。 整个过程实现算法如下： 以空格为分界符，解析用户输入的字符串，从表中查找与用户输入的第一 个字符串匹配的字符串，若找到调用相应的函数，并以解析出的其他字符串和字 符串个数作为参数传入。 如上述的命令r o u t e ro s p f ，在解析后最终调用的函数是o s p f 提供的函数 k co s p f - s t a r t - p r o c e s s ( ) 3 4o s p f 路由表计算子模块的实现 如前所述，o s p f 路由表是独立于v x w o r k s 的路由表的，当o s p f 计算路由 时，是计算的o s p f 的路由表，当o s p f 路由表改变，调用系统函数m r o u t e a d d 0 和m r o u t e d e l e t e 0 修改v x w o r k s 路由表。o s p f 的路有表数据结构如下： t y p e d e f s t r u c to s p f _ r o u t i n g _ t a b l ee n t r y e n u l no s p f _ r o u t e _ d e s t i n a t i o n _ t y p ed e s t i n a t i o n _ t y p e ； u l o n g d e s t i n a t i o n _ i d ； u l o n g a d d r e s s _ m a s k ； # i fd e f i n e dl - n s s 6 l _ ) b y t e _ e n u m ( b o o l e a n ) t y p e _ 5 _ r o u t e _ o r i g i n a t e d ； # e n d i f | n s s a | 4 0 电子科技大学硕士论文：o s p f 协议软件的设计与实现 u n i o n _ o s p f _ o p t i o n so p t i o n a l _ c a p a b i l i t i e s ； u n i o ns e r v i c et y p eb i ts t r u c t u r e t y p e _ o fs e r v i c e ； s t r u c to s p f a r e a e n t r y + s p t r _ a r e a ； e n u l t lo s p e r o u t e _ p a t h _ t y p e p a t h _ t y p e ； u l o n g p a t h _ c o s t ； u l o n g t y p e 2：_cost u l o n gl i n ks t a t ei d ： u l o n g c a c h e di p a d _ d r e s s ； b y t e e n u m ( o s p f _ l s t y p e ) l i n kt y p e ； u n i o no s p fl i n ks t a t ea d v e r t i s e m e n t o s p 3 a e x l 旦o p b l o c k u l o n g + s p t r _ l i n k _ s t a t e _ o r i g i n + s p t r _ n e x t _ h o p ； a d v e r t i s i n g _ r o u t e r ； ) o s p f _ r o u t i n gt a b l e _ e n t r y ； 其中的目的类型定义如下： e n u m o s p f _ r o u t e _ d e s t i n a t i o n t y p e o s p f d e s t i n a t i o n t y p e n e t w o r k = 0 x 0 0 ， o s p fd e s t i n a t i o nt y p ea s b r = 0 x 0 1 o s p fd e s t i n a t i o nt y p ea b r = 0 x 0 2 ， o s p fd e s t i n a t i o nt y p ev i r l 、u a l = 0 x 0 3 o s p fd e s t i n a n o nt y p ea s e = 0 x 0 4 o s p f _ d e s t i n a t i o n _ t y p e _ w i l d c a r d = o x f f ) ； o s p f 将接收到的s u m m a r yl s a 分类，若是类型3 的s u m m a r yl s a o s p f 将其目的类型设为o s p f d e s t i n a t i o n t y p e _ n e t w o r k ，若是类型4 的 s u m m a r yl s a ，o s p f 将其目的类型设为o s p fd e s t i n a t i o nt y p ea s b r 。 o s p f 路由表的计算分三个部分： a 、 最短路径树的计算 b 、 计算区域间路由 c 、 计算外部路由 对于区域间路由的计算，通过s u m m a r yl s a 获得信息，而区域边界路由 器发送的类型为s u m m a r yl s a 的o s p f 包基本上已经对路由进行了描述，即已 经是一条描述好了的路由。 同样，类型为a se x t e r n a ll s a 的o s p f 包描述了外部路由的信息。因此此 4 电子科技大学硕士论文：o s p f 协议软件的设计与实现 处对区域间路由和外部路e h 的计算不予描述，只描述最短路径树的计算。 最短路径树的计算： a 、运行d i j k s t r a 算法，如下： 将本地路由器作为根节点加入最短树，记为v f o r ( ；) 将v 的链路中的t r a n s i t 节点加入c a n d i d a t el i s t ； i f ( c a n d i d a t el i s t = = n u l l 、 b r e a k ； c a n d i d a t el i s t 中找出距离根节点最短的节点w ，并从c a n d i d a t e l i s t 中删除； 将w 加入最短树，记为v 将w 加入路由表。 ) b 、将s t u b 节点添加到最短路径树上。 此处的t r a n s i t 节点是指t r a n s i t 网络和路由器节点的合称，s t u b 节点即s t u b 网络。 3 5 接口有限状态自动机的实现 一、引起接口状态变化的事件： i n t e r f a c e u p 是由下层协议来标明接口是否可用，若某接口加入o s p f ，当下层协议标明 该接口可用，就会触发该事件，它使接口离开状态d o w n 。 w a i t t i m e r 由w a i tt i m e r 触发，表示i n t e r f a c e 的等待时间结束，可以选举指定路由器和 备份指定路由器。 b a c k u p s e e n 路由器发现网络是否存在备份指定路由器，可以通过两种方式发现：从某 个邻居收到h e l l o 包，邻居声明自己是备份指定路由器。或者从某个邻居收到h e l l o 包，邻居声明自己是指定路由器，但是没有备份指定路由器。在任何一种情况下， 路由器都和邻居建立了双向通信，即路由器必须出现在邻居的h e l l o 包中， b a c k u p s e e n 标志w a i t i n g 状态的结束。 n e i g h b o r c h a n g e 此网络双向连接的邻居的成员有所变化。需要重新选举指定路由器和备份指 电子科技大学硕士论文：o s p f 协议软件的设计与实现 定路由器。下列邻居变化会导致n e i g h b o r c h a n g e 事件。 a 、与一个邻居建立双向连接，换句话说，邻居的状态已经达到2 一w a y 或 更高的状态，这通过检查邻居h e l l o 分组的邻居表可以查出。 b 、与一个邻居失去双向连接，这通过检查邻居，换句话说，邻居的状态 转换到i n i t 或更低的状态，这也可通过检查邻居h e l l o 分组的邻居表可以查出。 c 、某个双向连接的邻居新宣称自己为指定路由器或备份指定路由器。这 通过检查邻居h e l l o 分组可以查出。 d 、某个双向连接的邻居不再宣称自己为指定路由器或备份指定路由器。 这通过检查邻居h e l l o 分组可以查出。 e 、某个双向连接的邻居的优先级变化。这通过检查邻居的h e l l o 分组可以 查出。 l o o p l n d 指示i n t e r f a c el o o p b a c k 可以通过网管来实现，我们的路由器不支持环回接 口，因此没有这种事件。 u n l o o p l n d 指示i n t e r f a c e 不再是l o o p b a c k 。可以通过网管来实现，本路由器不支持环 回接口，因此也没有此事件。 i n t e r f a c e d o w n 当下层协议( p p p , h d l c ，帧中继) 将标志置为d o w n ，标明下层协议不可 用，o s p f 会在定时任务中检测到该标志从u p 变为d o w n ，从而执行 i n t e r f a c e d o w n 事件，无论当前的接口状态是什么，新的接口状态都将变为 d o w n 。 二、接口的状态 d o w n 接口的初始状态，下层协议将标志置为d o w n ，标明下层协议不可用，不 能用来发送和接收包，o s p f 检测到该d o w n 标志，会认为网络不可用，此时 接1 3 的参数被设为初始值，也没有邻接。 l o o p b a c k 将路由器的接口进行环回，可通过硬件或软件，但是我们的路由器不支持 环回接口，因此没有用此状态。 w a i t i n g 4 3 电子科技大学硕士论文：o s p f 协议软件的设计与实现 当网络接口可用时，状态从d o w n 变为w a i t i n g ，在此状态下路由器不能选 举指定路由器和备份指定路由器，只有经过规定的时间后，或者路由器在网络上 发现了指定路由器，才能选举，这就避免了指定路由器和备份指定路由器的不必 要的变化。 p o i n t t o ，p o i n t 此状态下表示网络接口是点到点或者虚链路，此状态下不涉及到指定路由 器和备份指定路由器的选举，因此路由器可以和邻居直接建立邻接关系。 d r o t h e r 表示网络与广播型网络相连，i n t e r f a c e 既不是指定路由器，也不是备份指定 路由器。此i n t e r f a c e 应与指定路由器和备份指定路由器建立邻居关系。 b a c k u p 此时路由器是备份指定路由器，当指定路由器出问题时，它被提升为指定 路由器。它应与网络中所有的路由器建立邻接关系。 d r 此时路由器自己是指定路由器，它应与网络中所有路由器建立邻接，它必 须能为网络产生一网络l s a 三、接口有限状态机变换图： u n l o o p l n d 3 - 3 接口有限状态机 电子科技大学硕士论文：o s p f 协议软件的设计与实现 四、接口状态机结构的部分数组表示 # d e f i n e o s p fn u m b e ro fi n t e r f a c ee v e n t s 7 # d e f i n e o s p f _ n u m b e r o f i n t e r f a c e s t a t e s 7 t y p e d e f s t r u c to s p f _ i n t e r f a c e s t a t e m a c h i n e v o i d ( + f p t ri n t e r f a c e _ t r a n s i t i o n _ f u n c t i o n ) ( o s p fi n t e r f a c e + s p t r _ i n t e r f a c e ) ； o s p f _ i n t e r f a c e _ s t a t e _ m a c h i n e ； t y p e d e f v o i d r i n t e r f a c et r a n s l t i o n f u n c t i o n ) ( o s p f _ i n t e r f a c e + s p t r _ i n t e r f a c e ) ； o s p f i n t e r f a c e _ s t a t e _ m a c h l n e o s p f _ i n t e r f a c ee v e n t _ p r o c e s s i n g _ t a b l e o s p f 奠u m b e r o f i n t e r f a c e _ e v e n t s o s p fn u m b e r o f i n t e r f a c e _ s t a t e s _ + o s p f _ i n t e r f a c e u p 0+ + o s p f i n t e r f a c e i s d o w n 4 ( i n t e r f a c e _ t r a n s i t i o n _ f u n c t i o n ) o s p fo r o c e s s i n t e r f a c e _ u pe v e n t ， + o s p f _ i n t e r f a c e _ l o o p b a c k + n u l l ， + o s p f _ i n t e r f a c e _ w a i t i n g + n u l l ， + o s p f _ i n t e r f a c ep o i n tt o p o i n t + n u l l ， + o s p f _ i n t e r f a c e _ d e s i g n a t e d r o u t e ro t h e r + n u l l ， + o s p f _ i n t e r f a c e _ b a c k u p _ d e s i g n a t e d r o u t e r + n u l l ， + o s p f _ i n t e r f a c e _ d e s i g n a t e d _ r o u t e r+ n u l l ) ) ， 产o s p fi n t ec ei sd+ 1_r f ao w n n u l l po s p fi n t e r f a c el o o p b a c k + f ( i n t e r f a c ef u n c t i o n ) o s p f - p r o c e s s i n t e r f a c e _ d o w ne v e n t ) po s p fi n t e r f a c ew a i t i n g+ ( i n t e r f a c e r a n f u n c t i o n l t s i t l o n 4 5 电子科技大学硕士论文：o s p f 协议软件的设计与实现 o s p fp r o c e s si n t e r f a c e _ d o w n _ e v e n t ， 沣o s p f i n t e r f a c e p o i n lj o p o i n t ( i n t e r f a c e _ t r a n s i t i o n _ f u n c t i o n ) + o s p f _ p r o c e s s _ i n t e r f a c e _ d o w n _ e v e n t ， 卜o s p f _ i n t e r f a c ed e s i g n a t e d _ r o u t e r o t h e r | ( i n t e r f a c e _ t r a n s i t l o n _ f u n c t i o n ) o s p f a ) r o c e s s _ i n t e r f a c e _ d o w n _ e v e n t ， po s p f _ i n t e r f a c e _ b a c k u p _ d e s i g n a t e d r o u t e r | ( i n t e r f a c e _ t r a n s i t i o n _ f u n c t i o n ) o s p f a 3 r o c e s s i n t e r f a c e _ d o w ne v e n t ， 挣o s p f _ i n t e r f a c e d e s i g n a t e d _ r o u t e r 4 | ( ( i n t e r f a c e _ t r a n s i t i o n f u n c t i o n ) o s p fp r o c e s s i n t e r f a c e _ d o w n _ e v e n t ) ) ) ； 二维数组o s p f _ i n t e r f a c e _ e v e n t s o r o c e s s i n g _ t a b l e 定义了接口状态机在不同的 状态和事件下的特定处理函数。 五、接口状态机的执行： 接口状态机调用的函数如下： v o i d o s p f _ e x e c u t e _ _ i n t e r f a c e _ s t a t e _ m a c h i n e ( e n u l t l o s p f _ i n t e r f a c e _ e v e n te v e n t ，e n u mo s p fi n t e r f a c es t a t e s t a t e ， o s p f i n t e r f a c e + s p t r i n t e r f a c e ) i f ( o s p f _ i n t e r f a c e _ e v e n t _ p r o c e s s i n g _ t a b l e e v e n t s t a t e f p t ri n t e r f a c e _ t r a n s i t i o n _ f u n c t i o n ! = n u l l ) ( + o s p fi n t e r f a c e e v e n t _ p r o c e s s i n g _ t a b l e e v e n t s t a t e f p t r _ i n t e r f a c et r a n s i t i o n _ f u n c t i o n ) ( s p t ri n t e r f a c e ) ； ) ) 当接口产生了某个事件，就调用函数o s p fe x e c u t e i n t e r f a c es t a t em a c h i n e ( ) ，将接1 ：3 当前的状态和事件及接口指针作为参数传入，函数 o s p f _ e x e c u t e _ i n t e r f a c e s t a t e m a c h i n e ( ) 通过传入的参数，找到对应的二维数组 的函数指针，只需在判断o s p f _ i n t e r f a c e _ e v e n t a g r o c e s s i n g _ t a b l e e v e n t s t a t e 电子科技大学硕士论文：o s p f 协议软件的设计与实现 r p t r不为空，即可调用该函数，从而执行接口状态机。i n t e r f a c e t r a n s i t i o nf u n c t i o n 3 6 邻居有限状态自动机的实现 o s p f 为每一个邻居都维护了一个状态，相应邻居状态的变化通过执行邻居 状态机来实现。 一、邻居状态 邻居状态共有九种，如下： d o w n 它表明最近没有从邻居收到信息，主要是没有从邻居收到h e l l o 包，在 n b m a 中h e l l o 包可能向处于“d o w n ”状态的邻居以递减的频率发送。 a t t e m p t 此状态只对n b m a 网络的邻居有用，它表明最近没有从邻居收到信息。 当接口是n b m a 网络接口类型时，接口u p 之后就达到该状态。 l n i t 此状态是收到邻居的h e l l o 包，标明邻居已经激活，但是此时双向通信 还没有建立，收到的邻居h e l l o 包中只看到邻居，并没有自己。路由器发送的 h e l l o 分组中的n e i g h b o r 列表要包括所有此状态或以上的n e i g h b o r 。 2 一w a y 此状态表明同邻居的双向通信已经建立，从邻居收到的h e l l o 包中发现 有自己。指定路由器和备份指定路由器必须从状态在双向连接或以上的 n e i g h b o r 中选取。 e x s t a r t 此状态是两个邻居路由器建立邻接的第一步，目的是决定哪个路由器是 m a s t e r 和初始序列号。 e x c h a n g e 路由器通过d d 分组将链路状态数据库的信息传递给n e i g h b o r ，每个 d d # n g n - + n y o n ，路由器得到发送的上一个d d 分组的确认才会发 送下一个。每次只能发送一个d d 分组。在这个状态下路由器可能发送l s a r e q u e s t 分组，向n e i g h b o r 请求新的l s a l o a d i n g 此状态下，路由器向n e i g h b o r 发送链路状态请求包，请求在e x c h a n g e 状态下发现但还没有收到的更近的l s a 。 f u l l 此状态下邻居路由器已经完全邻接了，邻接关系将出现在r o u t e rl s a 和 电子科技大学硕士论文：o s p f 协议软件的设计与实现 n e t w o r k l s a 中。 二、邻居事件 h e l l o r e c e i v e d 从邻居收到h e l l o 包。 s t a n 此状态表明现在要将h e l l o 包以h e l l o i n t e r v a l 的间隔发给邻居，此事件 只在n b m a 网络上产生。 2 - w a y r e c e i v e d 实现了两个邻居路由器之间的双向通信，路由器发现邻居的h e l l o 包 中有自己触发该事件。 n e g o t i a t i o n d o n e 主从关系的协商结束，d d 序列号交换完成，意味d d 包可以进行 交换了。 e x c h a n g e d o n e d d 分组的交换已经完成，彼此知道对方的链路状态数据库的内容。 b a d l s r e q 收到一个l s a r e q u e s t 包中请求的l s a 在本数据库中没有包含，意味着 d d 交换出现错误。 l o a d i n g d o n e 发送的l s a r e q u e s t 都得到满足。 a d j o k ? 判断是否应该与邻居建立和维护邻接关系。在广播网络和n b m a 网 络上，若自己是指定路由器或备份指定路由器，或者邻居是指定路由器或 备份指定路由器，可建立邻接。在点对点和点对多点以及虚链路上，可直 接建立邻接。 s e q n u m b e r m i s m a t c h 收到的d d 分组的序列号有误，或i n i t 位被置，或o p t i o n 域与前个d d 分组不一致。这表示邻接关系的建立过程出现问题。 l w a y 从邻居收到一h e l l o 包，但h e l l o 包中没有提到自己，表明双向通信还没 有建立。 k i l i n b r 指示断绝与邻居的通信，邻居的状态将返回到d o w n 。 i n a c t i v i t y t i m e r 皇王型垫查堂堡主丝奎! ! ! 坚塑望鏊壁堕垦盐量壅翌 触发i n a c t i v i t yt i m e r 表明最近没有收到该邻居的h e l l o 分组。邻居的状 态将返回到d o w n 。 l l d o w n 程序没有用到此事件。 三、邻居有限状态机变换图如下 图3 - 4 邻居有限状态机 四、邻居有限状态机的数组表示 # d e f i n e o s p f 舅u m b e r o 蕾舅e i g h b o r s t a t e s 8 # d e f i n e o s p f n u m b e r o f _ n e i g h b o r e v e n t s13 t y p e d e f s t m c t o s p f _ _ n e i g h b o r s t a t em a c h i n e v o i d ( * f p t r _ _ n e i g h b o r _ t r a n s i t i o n _ f u n c t i o n ) ( o s p f _ i n t e r f a c e + s p t r _ i n t e r f a c e ， 电子科技大学硕士论文：o s p f 协议软件的设计与实现 o s p f _ n e i g h b o r4 s p t r _ n e i g h b o r , e n u i no s p f _ n e i g h b o r _ e v e n t e v e n t ) ； ，o s p fn e i g h b o rs t a t em a c h l n e ； t y p e d e f v o i d ( + n e i g h b o r _ t r a n s i t i o n _ f u n c t i o n ) ( o s p f _ i n t e r f a c e + s p t r _ i n t e r f a c e ，o s p f _ _ n e i g h b o r + s p t r _ n e i g h b o r , e n u i no s p fn e i g h b o r _ e v e n t e v e n t ) ； o s p f - - n e i g h b o r s t a t e _ m a c h i n e o s p fn e i g h b o r _ e v e n t _ p r o c e s s i n g _ t a b l e o s p f _ n u m b e r o f n e i g h b o r e v e n t s o s p f _ n u m b e ro fn e i g h b o i l s n 汀e