（计算机软件与理论专业论文）ospf剖析及其链路状态数据库的实现.pdf

y s 3 2 s 6 7 o 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 ，开放最短路径优先) 是i n t e r n e t 路由 选择协议的一种，最初是为替代r i p 协议开发的，目前已成为构建大型网络最 常用的路由选择协议。 本文较细致、全面地讨论了i n t e r n e t 路由选择的内部工作机制，包括路由 器的工作原理、i p 编址、路由表、i n t e r n e t 路由选择体系结构，以及两种主要 的路由选择技术一距离矢量与链路状态算法。此外，重点剖析了o s p f 的组成要 素，如l s a 、链路状态数据库以及用这些链路状态数据库进行路由选择计算等 等。并且，以c + + 代码形式实现了o s p f 中的链路状态数据库操作，并且在迈普 m i ，3 6 0 0 路由器中得到应用。最后，简要介绍了o s p f 的几种扩展机制，且对目 前单播路由选择协议进行了比较和总结。 关键词：o s p f ，l s a ，链路状态，数据库，路由 o s p f a n a t o m y a n dl i n k s t a t ed a t a b a s er e a l i z a t i o n m a j o r ：c o m p u t e r s o f t w a r ea n dt h e o r y g r a d u a t e ：q i n q i a n gl i ns u p e r v i s o r ：l i n s h e n o p e ns h o r t e s tp a t hf i r s t ( o s p f ) i so n eo ft h er o u t i n gp r o t o c o lo fi n t e r n e t o r i g i n a l l y , i tw a sd e v e l o p e dt ob et h es u b s t i t u t ef o rr o m i n gi n f o r m a t i o np r o t o c o l ( r i p ) a n dn o w i th a sb e c o m et h em o s tu s e f u lr o u t i n gp r o t o c o li nt h ec o n s t r u c t i o n o f g r e a t n e t w o r k r e l a t i v e l y , t h ep a p e rd i s c u s s e s t h ei n t e r n a lm e c h a n i s mo fi n t e r a c t r o u t i n g p a r t i c u l a r l ya n dr o u n d l y , w h i c h i n v o l v e dr o u t e rm e c h a n i s m ，i pa d d r e s s ，m u t i n gt a b l e ， r o u t i n gf r a m e w o r ka n dt h et w om o s tf a m i l i a rr o u t i n ga l g o r i t h m 一- - d i s t a n c e - v e c t o r a n dl i n k s t a t e o nt h eo t h e rh a n d ，i tp a r t i c u l a r l yd i s c u s s e st h ee l e m e n t so fo s p f s u c ha sl s a ，l i n k s t a t ed a t a b a s e ，a n dr o u t i n gc a l c u l a t i o nb a s e do nt h ed a t a b a s e ，a n d s oo n f u r t h e r m o r e ，i th a sb e e np r o g r a m m e dt or e a l i z et h el i n k - s t a t ed a t a b a s e o p e r a t i o nu s i n gc + + a n da p p l i e d i nr o u t e r m p 3 6 0 0 f i n a l l y , i td i s c u s s e s t h e e x t e n d e dm e c h a n i s mo fo s p fa n dc o m p a r et h es e v e r a lm u t i n gp r o t o c o li n s i n g l e b r o a d c a s t i n gm o d e k e y w o r d s ：o s p f , l s a ，l i n k s t a t e ，d a t a b a s e ，r o u t e 2 四川i 大学硕士学位论文 第一章in t e r n e t 上路由器的作用 1 1 路由选择简介 i n t e r n e t 是一个全球性的通信网络。它己将一百多个国家联系起来，数千 万人利用它来实现商业、教育和娱乐目的。近年来，电子商务作为一种推销产 品与服务的商业联系手段，开始在i n t e r n e t 上出现。人们可以通过交换电子邮 件来进行学术交流。另外，人们还可以利用网络来打电话、发送传真、聊天、 上b b s 、玩多人联网游戏等等。 i n t e r n e t 由一种称作路由器的专用计算机连接。当数据从i n t e r n e t 某一 地点向另一个地点转发时，要由路由器来决定从哪条路径转发以及如何转发。 这些告知路由器如何选择数据传输路径的协议，称为路由选择协议。这些协议 必须对i n t e r n e t 组织结构的变化作出迅速的反应，包括传输线路的中断与恢 复、路由器的崩溃、网络规则的改变等等。 路由选择是i n t e r n e t 得以持续运转的关键所在。虽然许多i n t e r n e t 和w w w 的用户不知道网络实现的底层机制，但路由选择却是一个极其有趣且复杂的课 题。路由选择协议是一些像i n t e r n e t 这样的大型的非集中式网络平稳运行的健 壮的分布式算法。 1 2i n t e r n e t 协议组 为了在连接到i n t e m e t 的计算机与构成i n t e m e t 的路由器之间传递分组，必 须制定一些规则来规范分组格式和处理过程。这些规则就叫作协议( p r o t o c 0 1 ) 。 应用于i m e m e t 的协议组称为t c p f i p 协议。 为简化协议设计，i n t e r n e t 协议分成若干层。图1 1 以广为人知的o s i 七层 参考模型为例，显示了i n t e r n e t 协议的层次结构。 四川大学硕l 学位论文 物理层 应_ ；| j 层s m t p 表示层 f t p 会话层 t e n l n e t 传输层 t c p ，u d p 网络层i c m pr i p o s p f i p 数据链路层 a r pp p p 物理层 v 3 5 图1 1o s i 七层参考模型与t c p h p 等价模型比较 物理层( p h y s i e a ll a y e r ) 指定分组比特流在给定的链路上传输和接收时如何 进行物理编码。一般来说，将比特编码成电或光脉冲信号，并将其组织起来以 便能检测传输过程中的错误。例如，电话线路的物理层协议由不同的调制解调 器标准来定义，如v 3 4 。 数据链路层 数据链路层( d a t a - l i n kl a y e r ) 指定分组如何在给定的链路上进行传输与接 收。该层提供的服务包括链路上终端的识别、最大分组大小规范( 最大传输单 兀m a x i m u mt r a n s m i s s i o n u n i t ，m t u ) 以及传输优先级的设置。例如，p p p ( 点 到点协议，p o i n t t o - p o i n t p r o t o c 0 1 ) ，是在i n t e m e t 上应用电话线路的数据链路层 协议。数据链路层协议经常与物理层协议一起指定。例如在以太网中，1 4 字节 的以太网数据链路层首部提供6 字节的源地址( i e e em a c 地址) ，6 字节的目 的地址以及2 个字节的用于分组多路复用的以太网类型。 叫川大学硕士学位论文 网络层 当源端与目的端处于不同的链路或网段上时，由网络层( n e t w o r kl a y e r ) 负 责通过多条链路转发分组( 也就是说，通过一个或多个路由器转发) 。通常必须 提供一个网路层的寻址方案，使得路由器能够推断出目的端属于哪个网段。有 时还必须提供分段与重组功能，以使网路层能够适应支持不同最大分组大小的 链路。动态路由选择协议允许路由器自动寻找到达网络目的端的路径，通常也 被看作是网络层的一部分。 i n t e r n e t 的网络层被称作i p ( i n t e m e tp r o t o c o l ，i n t e m e t 协议) 。网路层分组称 为i p 分组，或者i p 数据报( d a t a g r a m ) 。包含在i p 分组中的i p 地址长度为3 2 位。每个网段都被指定了一个i p 地址范围，用一个地址前缀来表示。i n t e m e t 路由器根据地址前缀来转发分组，而不是根据单个的主机地址来转发。当一台 主机加入到一个网段，或与一个网段有接口时，就分配给它一个处于该网段地 址范围内的唯一的i p 地址。与多个网段相连的主机会有多个i p 地址。i p 包括 许多路由选择协议，如o s p f 、r i p 及b g p 。i c m p ( i n t e m e tc o n t r o lm e s s a g e p r o t o c o l ，i n t e m e t 控制消息协议) 帮助主机寻找连接在它们所处网段上的路由 器，并在路由器不能向指定地址的目的端发送分组时，为主机提供诊断功能。 传输层 传输层( t r a n s p o r tl a y e r ) 为源端与目的端主机的应用程序提供端到端的连 接。该层的服务通常包括检测、纠错和数据排序。t c p i p 协议组有两个传输层 协议。其中，t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l ，传输控制协议) 提供了一种应 用程序间可靠的字节流服务。t c p 在拥塞控制与避免方面取得的进展，保证了 i n t e m e t 在近年得以持续发展。而u d p ( u s e rd a t a g r a mp r o t o c o l ，用户数据报协 议) 由于提供的连接无可靠保证，常用于相对无状态的应用，如s u n 公司的 n f s ( n e t w o r kf i l es y s t e m ，网络文件系统) 。 会话层 会话层( s e s s i o nl a y e r ) 提供了一种启动和中止传输连接的机制。 叫川大学硕士学位论文 表示层 表示层( p r e s e n t a t i o nl a y e r ) 为应用层的数据类型指定了编码和表示方法。 大致上，i n t e m e t 没有显示的会话层和表示层协议，而这些功能通常直接内置在 应用层里。然而，也有一些例外。如i n t e r n e t 的r p c ( r e m o t e p r o c e d u r ec a l l ，远 程过程调用) 协议对应着会话层，而一些i n t e m e t 应用中用到的x d r ( e x t e r n a l d a t ar e p r e s e n t a t i o n 外部数据表示) 协议，正好对应着表示层协议。 应用层 应用层( a p p l i c a t i o nl a y e r ) 可以被看作实现你期望的从任何计算机操作系统 中获得的、各种类型的网络服务的协议。在i n t e m e t 中，应用层协议包括s m t p ( s i m p l em a i lt r a n s f e rp r o t o c o l ，简单邮件传输协议) 、文件传输协议f t p 和 t f t p 以及远程登陆协议t e l n e t 。i n t e m e t 的d n s ( d o m a i nn a m es y s t e m ，域 名系统) 也对应于应用层。正是d n s ，州s i n a c o i n 转化为目的端的i p 地址， 1 3 转发i p 数据报 将人们易于识别、记忆的主机名如 从而为路由器确定路由作准备。 目的端m a c 地址 源端m a c 地址 以太网类型- - o x 8 0 0 ( i p ) 版本一4i h l 一5t o s 长度 标识 分段 t t l 协议一6 ( t c p ) 首部校验和 源端i p 地址 四川大学硕上学位论文 目的端i p 地址 源端l 目的端口- - 2 3 ( t e l n e t 服务器) 序列号 应答号 偏移 li 标志 窗口 校验和 紧急指示符 t e l n e t 数据 图1 2 在传输到以太冈阿段前，艘加到从客户端到厦务端的t e l n e t 数据的首部 路由器把i n t e r n e t 的各个网段连接起来。路由器从某个接口接收到i p 分 组之后，依据i p 首部提供的内容，通过另一个接口转发出去( t a 果是组播分组， 通过多个接口同时转发) 。当分组从跳向下一跳转发时，其网络层首部( i p 首部) 保持相对不变，它始终包含有如何转发分组的指示信息。然而，数据链 路层首部和物理传输方案可能会因为每一跳传输介质的不同而发生极大的变 化。让我们仔细分析一个i p 数据报的转发过程。 假定路由器收到了一个来自于以太网的分组，这个分组的格式如图1 2 所 示。路由器首先查看分组的数据链路层首部。在此例中，该首部指示为以太网 类型。如果以太网类型为o x 8 0 0 ，表示是一个i p 分组，则先剥离以太网首部， 然后检验其l p 首部。路由器通过检验版本( v e r s i o n ) 、i h l ( i n t e r n e th e a d e r l e n g t h ，i n t e r n e t 首部长度) 、首部校验和来验证i p 首部的内容。而后路由器 检验t t l 字段是否大于1 。设t t l 字段的目的是防止路由选择过程中发生死循 环。主机没置t t l 字段大于或等于某个所经路径中路由器个数的最大值。每个 路由器都将该值减1 后进行转发。当t t l 字段减为0 时，这个分组就被丢弃， 发送个i c m p t t l 溢出消息给主机a 在对t t l 作减法时，路由器必须调整分组 的首部校验和。 路由器查看目的端的i p 地址。这个地址指示一个目的端主机( 单播情况 四川大学硕士学位论文 下) ，或一组主机( 组播情况下) ，或指定网段上的所有主机( 广播情况下) 。以 单播方式进行转发时，目的端的i p 地址用作路由表查找的关键字。如果分组太 大以至无法转发的话，路由器会试图把分组分割成较小的部分，称为分段 ( f r a g m e n t ) 。分段会使网络性能下降。 路由器随后为外发接口附加一个相应的数据链路层首部。利用a r p 协议或 a r p 协议的变体( 如帧中继子网中的反转a r p ，i n v e r s ea r p ) 把下一跳的i p 地址转化为链路层地址。然后路由器把分组发送给下一跳，然后在下一跳重复 上以过程。 i p 地址 路由器是根据一个i p 分组首部中的3 2 位目的端i p 地址来选择路由的。i p 地址通常用带点的十迸制表示法表示：地址的每个字节都用一个十进制数表示， 期间用圆点分隔。例如，一个十六迸制形式为0 x c 0 0 9 0 1 0 2 的i p 地址可以写成 1 9 2 9 1 2 。 依据表1 1 所示的规则，路由器根据i p 地址的形式可以迅速判断该地址是 单播、组播或广播地址。 i p 地址空间按功能分类 地址范围地址功能 1 o o 0 2 2 3 2 5 5 2 5 5 2 5 5i p 单播地址 2 2 4 0o o 2 3 9 2 5 5 2 5 5 2 5 5 i p 组播地址 2 2 0 0 0 0 2 5 5 2 5 5 2 5 5 2 5 4 保留地址 0 0o 0表示未知i p 地址 2 5 5 2 5 5 2 5 5 2 5 5 本地网段广播地址 无类域问路由选择c i d r ( c l a s s l e s si n t e r d o m a i nr o u t i n g ) t c p i p 路由器根据网段来选择路由。当转发一个分组时，路由器先查看路 由表，寻找分组目的地址所属的网段，然后向该网段转发。然而，更确切的说 是根据网段地址前缀选择路由。路由器不可能跟踪记录i n t e r n e t 上的每个网 段。网段地址信息在i n t e r n e t 的某些节点上被聚集成较短的地址前缀。从最初 四川大学硕十学位论文 的网段前缀开始，可能经过三此或四次聚集，形成叫短的地址前缀，保留在路 由器的路由表中。 图1 3 是地址前缀聚集的例子。路由器g 聚集来自右边4 个网段 ( 1 2 8 1 1 2 4 ，1 2 8 1 3 2 4 ，1 2 8 1 4 2 4 以及1 2 8 1 6 2 2 4 ) 的地址前缀，向 左边的路由器通告地址前缀1 2 8 1 1 6 。这就意味着路由器a f 并不知道路由 器g 的右边有4 个网段，而只在各自的路由表表项中记录一个地址前缀 1 2 8 t 1 6 指向路由器g 。 1 9 9 3 年以前，前缀依据地址类型不同被限定在一个小的固定长度内。当这 些限制被消除后，允许有任意长度的前缀，许许多多的地址聚集出现了。允许 保留更多的i p 地址空间，放慢了i n t e r n e t 核心路由器路由表的增长速率。依 据任意长度前缀进行的路由选择叫做c i d r 。前缀长度表示法如 1 2 8 1 8 6 1 0 2 4 ，以c i d r 表示法而著称。 1 2 8 3 7 ，2 41 2 82 2 ，2 4 四川大学硕卜学位论文 1 4 i p v 6 图1 3t c p i p 网络中地址前缀聚集示例 由于担心i n t e r n e t 地址空间用尽，1 9 9 3 年设计者们开始研究带有更大地址 空阃的新版i p 协议。这纠一事情在1 9 9 6 年结束，并公布了t p v 6 的全套的网络层 协议规范( 协议的其它层保持不变) ，同时把当前使用的i p 协议称为i p v 4 。 i p v 6 与i p v 4 并没有太大的不同，i p v 6 在i p v 4 的基础之上所作的大量改进 可以概括为“带1 2 8 位地址的i p v 4 ”。特别是i p 路由选择与寻址基本保持不变。 一个i p v 6 路由器基于类似c i d r 的地址前缀路由表做出路由选择。 i p v 6 还没有广泛应用，可能有以下原因。首先，先前对i p v 4 地址空间不久 将要用尽的担心似乎是反应过度。c i d r 的发展已经提高了地址空间的利用率， 现在这种担心已经转向了路出表的扩展将导致i n t e m e t 的核心路由器不堪重负 的问题，这个问题在i p v 6 中也没有解决。其次，利用私有i n t e m e t 地址空间然 后通过n a t ( n e t w o r ka d d r e s st r a n s f o t l n ) 将其连接到i n t e m e t 的方法减少了对 i n t e r n e t 地址空间的需求。既然i p v 6 不能为新的网络应用提供便利，对数量庞 大的运行i p v 4 的路由器和主机进行转换看来可能会推迟到i p v 4 地址即将用完 之日。 塑型查兰婴主兰些鲨奎一 2 1 路由表 第二章i n t e r n e t 路由选择协议 所有的t c p h p 路由选择协议都有方法来发现i p 地址前缀的可达性，以及 对于每个可达性前缀发往该前缀的业务流所要经过的下一跳路由器。当网络发 生变化( 租用线路失效、新租的线路开始工作、路由器崩溃等等) 时，路由选 择协议持续不断的重新计算前缀的可达性以及通往可达前缀的可用的下一跳路 由器。在网络发生变化时重新寻找下一跳的过程，称为收敛。我们总是喜欢那 种寻找下一跳路由器速度快的协议，也就是说我们喜欢收敛时间短的协议。然 而，对任何路由选择协议来说，随着网络规模与复杂性的不断增长，其收敛时 间也会不断增长。 路由器的路由表告诉路由器如何转发分组。给定一个分组，路由器先用目 的端i p 地址作为关键字查询其路由表。查询结果返回了最佳匹配的路由表表 项，这个表项告诉路由器应该把分组发往哪个接口以及下一跳路由器的i p 地 址。路由器知道的每个地址前缀都对应一个独立的路由表表项。路由表的每个 表项都被看作一个路由。例如，图1 3 中路由器c 的路由表如表2 1 所示。对 于前缀1 2 8 5 2 2 4 以路由器c 本身作为下一跳，表明了路由器c 直接连接在该 网段上。c 发往该前缀的分组可以直接向其目的端发送。 图1 3 中路由器c 的路由表 前缀下跳 1 2 8 1 1 6路由器g 1 2 8 2 1 6 路由器d 1 2 8 2 4 2 4路由器a 1 2 8 3 7 2 4路由器d 1 2 8 5 2 2 4自身 1 2 8 5 6 2 4路由器b 在表2 1 中，目的端1 2 8 2 4 5 与两个表项相匹配：1 2 8 2 1 6 和1 2 8 2 4 2 4 。 这种现象并不少见。在这种情况下，较长的表项1 2 8 2 4 2 4 被选为最佳匹配。 四川大学硕士学位论文 2 2i n t e r n e t 路由选择体系结构 i n t e m e t 被划分为不同的区域，即自治系统a s ( a u t o n o m o u ss y s t e m ) 。每 个a s 包含一组处于单一管理实体控制下的路由器，例如，a s 中的所有路由器 都属于特定的i s p ( i n t e r a c ts e r v i c ep r o v i d e r ) 、公司或大学。 a s 是按粗略的分层模式来划分的。越靠近分层体系的高层i n t e m e t 核 心的a s 中路由器越多，同时在路由器的路由表中单独的地址前缀就越短。 i n t e m e t 核心的a s 带有完整的路由表，它不采用默认路由。所有其它a s 都采 用默认路由指向上一层次。图2 1 绘出了i n t e m e t 中a s 的划分。 图2 1 把i n t e r n e t 划分为a s 实线表示对等关系箭头表示默认路由的指向 i n t e r n e t 核心网络中a s 本身也逐年在变。最初，a r p a n e t 网络处于i n t e m e t 的核心。然后，在1 9 8 5 年国家科学基金会提交建立了一个新的i n t e m e t 核心， 称为n s f n e t 。而n s f n e t 于1 9 9 5 年退出历史舞台。现在的i n t e m e t 核心网络 由五六个商业性i s p 组成，它们包括u u n e t 、m c i 以及s p r i n t 。 最初，a s 内的路由器通过单一的路由选择协议i g p ( i n t e r i o rg a t e w a y u g 川大学硕士掌位论文 p r o t o c 0 1 ) 来交换路山选择信息，而另外的路由选择协议e g p ( e x t e r i o r g a t e w a y p r o t o c 0 1 ) 用来交换a s 间的路由选择信息。然而后来，单一的i g p 规则很快就 被打破了，学多a s 同时运行了多个i g p 协议侈畸如r i p 和o s p f 。运行相 同的i g p 协议的一组路由器被称作路由选择域。而在这种情况下，一个a s 可 以由多个路由选择域组成。 2 3 距离矢量算法 在距离矢量协议中，路由器协作完成分布式计算任务。距离矢量算法分别 计算达到每个目的前缀的最佳路径，它通常采用一个简单的度量值( 如路由器 跳步数) 来衡量路径的优劣，尽量寻找度量值最小的路径。在算法的每个中间 步骤，路由器都有其当前最佳的到达每个目的前缀的路径。路由器把当前路径 通知给它的所有邻居，同时它的邻居也把他们的最佳路径通知给它们各自的邻 居。这样，个路由器在得到其邻居正采用的路径之后，如果发现一条通过某 个邻居的更好的( 代价更低) 的路径，路由器就更新到达某个目的端的代价与 下一跳，并把自己的新选择通知所有邻居。这就完成了一次迭代。在经过多轮 这样的迭代之后，路由选择将达到稳定，每个路由器将会找到个通往其目的 端的最佳路径。 距离矢量算法的主要优势就在于简单。这个算法适合于路由聚集，而且， 相对简单的路崮选择策略较容易实现。 距离矢量协议的一个经典实例就是r i p ( r o u t i n gi n f o r m a t i o np r o t o c o l ，路由 选择信息协议) 。下面以r i p 协议和图2 2 所示的网络为例，更详细的分析距离 矢量算法的分布式计算。 婴型查兰堡主兰竺堡兰 距离矢量的收敛性 图2 2 描述距离矢量协议行为的网络拓扑示例 r i p 路由器在其路由表表项中增加了m e t r i c ( 度量值) 字段。度量值表示 到达某个目的端的路径中最小的路由器跳步数。直接连接到网段上的地址前缀 总是把度量值设为l 。每隔3 0 秒，每个r i p 路由器就把融p 更新列表向其邻居 的r i p 路由器广播。r i p 更新列表列出了路由器路由表的地址前缀和它们当前 的度量值。当一个r i p 路由器从其邻居x 那里收到r i p 更新列表之后，它就开 始检查更新列表中的所有前缀。如果通过x 达到某个前缀的跳步数( 从x 到这 个前缀的路由度量值再加1 ) 比当前路由器到该前缀的路由度量值要小，那么 路由器就更新其路由表。更新后的表项中，对应该地址前缀的下一跳设为x ， 其路由度量值设为x 路由器中对应该前缀的路由度量值加l 。 表2 2 所示的例子中，假定在t 1 时刻路由器i 与网段1 9 2 1 4 2 4 的接口开 四川大学颤：i ：学位论文 始工作。在t i 到t 4 的这段时间内，路由器a i 都同时向其邻居发送路由更新 信息。表2 2 中a 所在那列显示了路由器a 中对应1 9 2 1 4 2 4 的路由表项随时 间变化的情况。在t 4 时刻，路由表表项保持稳定，r j p 收敛结束。 轰2 2当子网1 9 2 1 4 2 4 被加到图2 2 中时，r i p 的收敛过程 时问abc defgh【 t il t 2 2 ，i2 ，i l t 3 3 ，g 3 ，g3 h2 ，i2 ，i t t 4 4 。c4 ，c3 ，g 3 g 4 ，d3 ，h2 , i2 , 1 l 往：龉辔表变饱两黑体字表示每个瘦量值都甩代债与下一跳的维合表示。 表2 2 显示了当到达某个目的前缀的新的更短的路径被发现时，路由选择 信息的收敛过程。然而，有时由于链路和路由器失效，当前的最优路径可能不 存在了，路由选择必须恢复为一条较长的路径。路由器可以通过两种方式发现 这种失效。种情况是，由路由器当前最优下一跳路由器发送一条路由更新消 息，通知路由器最优路径不复存在了。另一情况是，收不到来自于当前下一跳 路由器的任何更新信息，路由器就判断下一跳路由器可能不能工作了，所以就 选择一个新的下一跳路由器，并通告这条与原路径相等或较长的路径。在这些 失效的情况下，距离矢量协议的收敛行为显示出了它的弱势。 计数到无穷 当网络发生变化或各个路由器未能同步发送路由更新信息时，甚至在各个路 由器采用不同的更新间隔时间的情况下，距离矢量协议分布式计算是十分健壮 的，可以快速完成收敛。然而，当出现某些网络失效问题时，距离矢量协议要 花相当氏的时间才能收敛。例如，假定图2 - 2 中路由器i 与1 9 2 1 4 2 4 网段的接 口不能正常工作。表2 3 显示了r i p 更新过程，同时人为地假定路由器a i 在 t l 坷5 时刻同步发送更新信息。 四川i 大学硕上学位论文 表2 3图2 2 中1 9 2 1 4 2 4 子网删除之后的距离矢量收敛过程 时问a bcdefgi i t l 4 ，c4 ，c3 g 3 g4 d3 h2 i 2 ，1 t 2 4 ，c4 ，c 3 g3 ，g 4 ，d 3 i 3 ，h3 ，g3 ，g t 3 4 ，c4 ，c4 ，g4 ，g 4 d 4 ，h 4 h4 g 4 ，g t 4 5 ，c5 ，c5 ，g5 ，g5 ，d5 h5 ，h5 ，g5 ，g t 5 6 ，c6 ，c6 ，g6 ，g 6 d6 h6 h 6 ，g6 ，g t 67 c7 c 7 g7 g7 d7 h7 h7 g7 g t 7 t 1 3 t 1 41 5 c1 5 c1 5 g1 5 g1 s d 1 5 h1 5 h1 5 g1 5 g t 1 5 洼：路由表变化甩黑体字表示每个度量值都霸代赞s 下一跳的组合表示。 从上表中可看出，路由器要花相当长的时间确认前缀1 9 2 1 4 2 4 是不可达 的。在这段时间内，可能会形成转发循环。在我们所举的例子中，从t 2 到t 4 这段时间内，在路由器g 与h 间形成了转发循环。对于任意给定的路由器，到 前缀1 9 2 1 4 2 4 的代价持续增长，直到它到达r i p 协议的极限值1 6 。这种现象 称为“计数到无穷”，这也是距离矢量协议中最大路径代价值通常设为一个较小 值的原因，计数的过程越长，所耗费的网络、路由器c p u 和带宽资源就越多。 当网络失效时，距离矢量协议，如r i p 显示出相似的特征：延长其通往目的端 的路径的长度。 提高收敛性能 为t j j n 快距离矢量协议的收敛速度，有人提出了如下建议。 i 、为了减少收敛时间，当其路由表发生变化时，运行距离矢量协议的路由 器立即发送路由更新而不再受3 0 秒的间隔的限制。这种更新被称作触发 更新。 2 、为了防止在收敛中形成转发循环，距离矢量协议经常采用水平分割处理 方法。根据水平分割方法，一个路由器向接口x 发送一个路由选择更新 之后，该路由器会忽略掉外发接口为x 的更新中所列的路由。例如，表 2 2 中的t l 时刻，路由器g 不会向h 、i 路由器广播到达1 9 2 1 4 1 2 4 的 四川大学硕士学位论文 路由更新。水平分割算法的另一种变形，称作无限水平分割或毒性逆转 水平分割算法，在发往x 接口的更新中，把外发接口设为不可达( 即把 代价设为1 6 ) 。无限水平分割算法比普通的水平分割算法效率更高。因 为它减少了转发循环，事实上它完全消除了由两个路由器构成的循环圈。 然而，由于无限水平分割算法使更新增长，普通的水平分割算法用得较 多。 3 、距离矢量算法的另一种变形，被称作抑制算法。在一条路由被宣布无效 后，路由器拒绝接受这条路由的更新。例如，表2 2 中的路由器i 若执行 抑制算法，它会在t 1 之后的若千周期内拒绝接受来自于邻居路由器的路 由选择更新。在某种情形下，抑制算法能防止形成转发循环，然而有时 它会延长收敛时间。基于这个原因，在诸如r i p 等协议中并不经常使用。 但是，在其它的距离矢量协议，如i g r p ( i n t e r - g a t e w a yr o u t i n g p r o t o c 0 1 ) 中该算法仍然被采用。 这些用来提高r i p 协议收敛性能的改进方法并不能完全消除收敛过程中和 “计数到无穷”过程中的路由环。目前有两种方法可以解决距离矢量协议中的 问题。第一个方法已经被b g p 协议采用了，它通告到达每个地址前缀的完整路 径而不是前缀的度量值。而第二中方法也在e i g r p ( c i s e o 公司开发的一种i g p 协议) 中实现了，它严格控制节点间路由选择更新的次序。后一种方法能够保 证不会出现路由循环，但它使协议明显复杂起来，并事实上造成了收敛时间的 延长。 2 4 链路状态算法 与距离矢量算法所采用的递增的分布式计算不同，链路状态路由选择算法 采用了- - f , t t 冗余分布式数据库方法。按照链路状态算法，数据库提供关于每个 路出器的局部环境信息：该路由器与局部i p 网段和邻居路由器之间的链路，以 及每条链路被赋予的代价。链路状态算法不用通告到达每个目的端的路径的代 价，而是通过链路状态算法通告局部的网络链路和状态。这些链路状态通告被 发送给其它所有的路由器。最后的结果是所有的路由器都能获得相同的由收集 到的通告组成的数据库，这个数据库描述了当前的网络地图。网络中每条路径 叫川人学硕士学位论文 的代价设为其各条链路代价之和。根据网络地图，每个路由器可以运行最短路 径算法，生成到达每个目的地的前缀的最短路径( 一般采用d i j k s t r a 算法，有 时也采用其它算法，如b e l l m a n f o r d 算法) 。 本文接下来的部分将会详细介绍- - 0 e 特殊的链路状态路由选择协议： o s p f 。最初，链路状态算法是为解决距离矢量协议的性能问题设计的。然而， 距离矢量与链路状态算法的相对优缺点至今仍在争论中。链路状态算法一般被 认为具有较好的收敛性：当网络发生变化时，寻找新路由更快速，而且所需的 开销较小。因为链路状态协议比距离矢量协议拥有更多的数据( 也即有一个完 整的网络描述) ，它们可以较容易地计算出带复杂特征的路径，而距离矢量协议 只能计算出带最低代价的简单路径。例如，已经设计了这样的链路状态协议， 它可以计算出针对不同的i p 服务类型的路径，也可以计算遵从诸多策略限制的 路径，或者计算出保证一定的服务质量的路径。 e g p i g p 的分离，使得i n t e r n e t 具有两个路由选择协议技术的最佳特性。例 如，采用o s p f 作为i g p 可以获得快速的局部收敛，而a s 之间运行b g p 可以 使路由聚集和基于策略的路由选择更便利。 叫j i l 大学硕士学位论文 第三章o s p f 基本要素 3 1 一个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 m ) 中描述其局部的路由拓 扑。然后，这些l s a 通过一个“可靠的泛洪过程”分发到路由选择域的其它路 由器上。所有路由器产生的l s a 形成的集合被称为链路状态数据库。这个链路 状态路由选择协议的泛洪算法确保除了短暂的收敛时间外，每个路由器有同一 个链路状态数据库。采用链路状态数据库作为输入，每个路由器可计算出其自 身的i p 路由表，从而可以正确的转发i p 数据报。 下面我们以图3 1 中点到点链路相连的路由器为例子，来说明o s p f 的基本 概念。 图3 1点到点的网络拓扑 假定网络已经建立并运行了一段时间。图中所画的每个路由器都将有一个 相同的链路状态数据库，用来描述一个完整的网络地图。通过查看这个数据库， 六个路由器的任何一个都能判断出网络中还有多少各路由器( 5 个) 、路由器 1 0 1 - 1 4 有多少个接口( 3 个) 、1 0 1 1 2 和1 0 1 1 4 之间是否有相连的链路( 有) 凹川大学硕：1 二学位论文 等等。这个数据库同时给出每条链路的代价，我们假定每条链路有相同的代价 1 。 根据这个数据库，每个路由器都可以计算出到达其它路由器的最短路径。 例如，路由器1 0 1 1 1 可以计算出有两条到达1 0 1 1 6 的最短路径，其中一条通 过l o 1 1 2 和1 0 1 1 4 ，而另一条通过1 0 1 1 3 和1 0 1 1 5 。 当网络处于稳定状态日寸，也就是说没有路由器和链路进入或退出服务的时 候，唯一的o s p f 路由业务流就是相邻的路由器之间周期性的h e l l o 分组以及 偶然的链路状态数据库的刷新。h e l l o 分组每1 0 秒钟发送一次，如果不能及时 从邻居那接收到h e l l o 分组就说明该邻居路由器或者与之相连的链路出了问题。 每3 0 分钟，路由器就把链路状态数据库的所有内容重新泛洪一次，以免出现数 据库中有的片段丢失或某个路由器的数据库发生了错误的情况。 现在假定路由器l o 1 1 2 和l o 1 1 4 之间的链路出现了故障。路由器l o 1 1 2 的物理层或数据链路层可能在几秒内检测出错误。在4 0 秒内不能通过该链路接 收到o s p f 的h e l l o 分组将最终表明链路失效。一旦检测到失效，路由器1 0 1 1 2 通过产生自身的r o u t e r l s a 来更新链路状态数据库。这个新的r o u t e r - l s a 告诉 其它路由器：路由器1 0 1 1 2 有到1 0 1 1 1 和1 0 1 1 3 的链路，但没有到1 0 1 1 4 的链路。路由器1 0 1 1 2 将发起新的泛洪过程，把l s a 向1 0 1 1 1 和l o 1 1 3 发送。路由器1 0 1 1 3 将继续这个泛洪过程，把l s a 向1 0 1 1 5 发送，如此下 去。一旦每个路由器收到了路由器1 0 1 1 2 的新的r o u t e r l s a ，路由器就开始 重新计算其最短路径。例如路由器1 0 1 1 1 将计算出它只有一条到达1 0 1 1 6 的最短路径，且该路径经过l o 1 1 3 和1 0 1 1 5 。 每个o s p f 路由器都有一个o s p f 路由器i d 。这个i d 是一个3 2 位的数字， 可以唯一标识o s p f 域内的路由器。实际当中，o s p f 路由器i d 设置为这个路 由器多个i p 地址中的一个。 3 2l s a ( 链路状态通告) 每个o s p f 路由器生成一个或多个l s a ，以描述路由选择域的局部情况。 综合所有的l s a ，就可以形成一个链路状态数据库，该链路状态数据库可以作 为路由选择计算的输入。所有的o s p f 的l s a 都以2 0 字节的普通首部开始， 蹦川大学硕上学位论文 如图4 2 所示 3 2 1 标识l s a l s 年龄 选项l s 类型 链路状态i d 发送通告的路由器 l s 序列号 l s 校验和 长度 图3 2l s a 首部 一个o s p f 链路状态数据库可能包含几千个l s a 。在泛洪过程和各种路由 选择计算过程中，必须标识单个的l s a 。可以根据l s a 首部的三个字段来标 识o s p f 的l s a ：l s 类型、链路状态i d 和发出通告的路由器。 l s 类型宇段 l s 类型值l s a 类型 l r o u t e r - l s a 2 n e t w o r k - l s a 3 n e t w o r k - s u m m a r y - l s a 4 a s b r - s u m m a r y - l s a 5 a s e x t e r n a l - l s a 6 g r o u p 。m e m b e r s h i p - l s a 7 t y p e 一7 l s a 8 e x t e m a i a t t r i b u t e s l s a 表3 1 l s a 类型表 每个路由器发出单个r o u t e r - l s a 以描述它自己有效的端口与邻居。在一个 由点到点链路连接的路由器组成的路由选择域中，链路状态数据库仅仅由 r o u t e r - l s a 组成。每个n e t w o r k l s a 描述了一个网段，如广播网络，以及当前 四川i 大学硕士学位论文 与该网段相连的路由器的标识。n e t w o r k s u m m a r y l s a 、a s b r s u m m a r y - l s a 和a s e x t e r n a l l s a 可以用来在o s p f 内部实现层次化路由些选择。 g r o u p m e m b e r s h i p l s a 用于在m o s p f ( m u l t i c a s to s p f ) 中标识组播组成员。 t v p e 一7 l s a 用于在o s p fn s s a 区中引进一个有限的外部信息集合。 e x t e r n a l a t t r i b u t e s l s a 用于代替内部的b g p 承载跨越o s p f 路由选择域的b g p 路径信息。 o s p f 路由器不需要存储或转发不认识的l s 类型的l s a 。每当增加新的 l s 类型以扩展o s p f 类型时