OSPF算法相关内容

[TOC]

OSPF [Open Shortest Path First，开放式最短路径优先] 具有扩展性强，收敛速度快等特点，作为优秀的内部网关协议被广泛使用

链路状态路由协议——实现过程

第一步 LSA泛洪:建立相邻路由器之间的邻居关系

链路状态路由协议通告的的是链路状态

运行链路状态路由协议的路由器之间首先会建立一个协议的邻居关系，然后彼此之间开始交互LSA [Link State Advertisement，链路状态通告]

第二步 LSDB组建:交互链路状态信息和同步LSDB

每台路由器都会产生LSAs，路由器将接收到的LSAs放入自己的 LSDB[Link State DataBase，链路状态数据库]，路由器通过对LSDB中所存储的LSA进行解析，进而了解全网拓扑

• LSDB汇总了网络中路由器对于自己接口的描述
• LSDB包含全网拓扑的描述

第三步 SPF计算:进行优选路径计算

每台路由器基于LSDB，使用SPF [最短路径优先] 算法进行计算。每台路由器都计算出一棵以自己为根的、无环的、拥有最短路径的树

第四步 路由表生成:根据最短路径树生成路由表项加载到路由表

最后，路由器将计算出来的优选路径，加载进自己的路由表 [Routing Table]

OSPF协议概述

OSPF是IETF定义的一种基于链路状态的内部网关路由协议

目前针对IPv4协议使用的是OSPF Version 2 [RFC2328]；针对IPv6协议使用OSPF Version 3 [RFC2740]

OSPF 基础术语

OSPF Area

OSPF Area用于标识一个OSPF的区域

OSPF Area 区域是从逻辑上将设备划分为不同的组，每个组用区域号 [Area ID] 来标识

Router-ID

Router-ID [Router Identifier，路由器标识符]，用于在一个OSPF域中唯一地标识一台路由器

Router ID选举规则如下：

1. 手动配置OSPF路由器的Router ID
2. 如果没有手动配置Router ID，则路由器使用Loopback接口中最大的IP地址作为Router ID
3. 如果没有配置Loopback接口，则路由器使用物理接口中最大的IP地址作为Router ID

• Router ID一旦选定，之后如果要更改的话就需要重启OSPF进程
• 在实际工程中，推荐手工指定OSPF路由设备的Router ID

Cost 度量值

OSPF使用Cost [开销] 作为路由的度量值

• 每一个激活了OSPF的接口都会维护一个接口Cost值，缺省时接口Cost值=100 Mbit/s /接口带宽。其中100 Mbit/s为OSPF指定的缺省参考值，该值是可配置的
• 一条OSPF路由的Cost值可以理解为是从目的网段到本路由器沿途所有入接口的Cost值累加

OSPF协议报文类型

报文名称	报文功能
Hello	周期性发送，用来发现和维护OSPF邻居关系
Database Description	描述本地LSDB的摘要信息，用于两台设备进行数据库同步
Link State Request	用于向对方请求所需要的LSA
Link State Update	用于向对方发送其所需要的LSA
Link State ACK	用来对收到的LSA进行确认

OSPF三大表项

OSPF的邻居表

• OSPF在传递链路状态信息之前，需先建立OSPF邻居关系
• OSPF的邻居关系通过交互Hello报文建立
• OSPF邻居表显示了OSPF路由器之间的邻居状态

<R1> display ospf [ process-id ] peer [ [ interface-type interface-number ] [ neighbor-id ] | brief | last-nbr-down ]	#用来显示OSPF中各区域邻居的信息

参数	参数说明
process-id	OSPF进程号
interface-type interface-number	指定接口类型和接口号
neighbor-id	邻居的Router ID
brief	显示OSPF各区域中邻居的概要信息
last-nbr-down	显示OSPF区域中最后Down掉的邻居的概要信息

OSPF的LSDB表

• LSDB会保存自己产生的及从邻居收到的LSA信息
• Type标识LSA的类型，AdvRouter标识发送LSA的路由器

<R1> display ospf lsdb

OSPF的路由表

• OSPF路由表和路由器路由表是两张不同的表项
• OSPF路由表包含Destination、Cost和NextHop等指导转发的信息。

display ospf [ process-id ] routing router-id [ router-id ]
display ospf [ process-id ] routing [ ip-address [ mask | mask-length ] ] [ interface interface-type interface-number ] [ nexthop nexthop-address ] [ verbose ]  

参数	参数说明
process-id	OSPF进程号
router-id router-id	目的设备的Router ID
ip-address	目的IP地址
mask	指定子网掩码
mask-length	指定掩码长度
interface interface-type interface-number	接口类型及接口号
nexthop nexthop-address	显示下一跳IP地址为此指定值的路由信息
verbose	查看详细信息

OSPF 协议报文格式与类型

OSPF一共定义了5种类型的报文，不同类型的OSPF报文有相同的头部格式，OSPF报文直接采用IP封装，在报文的IP头部中，协议号为89

报文名称	报文功能
Hello	周期性发送，用来发现和维护OSPF邻居关系
Database Description	描述本地LSDB的摘要信息，用于两台设备进行数据库同步
Link State Request	用于向对方请求所需要的LSA。设备只有在OSPF邻居双方成功交换DD报文后才会向对方发出LSR报文
Link State Update	用于向对方发送其所需要的LSA
Link State ACK	用来对收到的LSA进行确认

重要字段解释：

• Version ：对于当前所使用的OSPFv2，该字段的值为2
• Router ID：表示生成此报文的路由器的Router ID
• Area ID：表示此报文需要被通告到的区域
• Type：类型字段
• Packet length：表示整个OSPF报文的长度，单位是字节
• Checksum：校验字段，其校验的范围是整个OSPF报文，包括OSPF报文头部
• Auth Type：为0时表示不认证；为1时表示简单的明文密码认证；为2时表示加密认证
• Authentication：认证所需的信息。该字段的内容随Au Type的值不同而不同

OSPF协议工作原理

OSPF邻接关系建立过程

OSPF完成邻接关系的建立有四个步骤，建立邻居关系、协商主/从、交互LSDB信息，同步LSDB

建立邻居关系：

OSPF使用Hello报文发现和建立邻居关系

• 在以太网链路上，缺省时OSPF采用组播的形式发送Hello报文 [目的地址224.0.0.5]
• OSPF Hello报文中包含了路由器的Router ID、邻居列表等信息

1. 当一台OSPF路由器收到其他路由器发来的首个Hello报文时会从初始Down状态切换为Init状态
2. 当OSPF路由器收到的Hello报文中的邻居字段包含自己的Router ID时，从Init切换2-way状态

Hello报文

Hello报文的主要作用：

• 邻居发现：自动发现邻居路由器
• 邻居建立：完成Hello报文中的参数协商，建立邻居关系
• 邻居保持：通过周期性发送和接收，检测邻居运行状态

重要字段解释：

• Network Mask：发送Hello报文的接口的网络掩码
• HelloInterval：发送Hello报文的时间间隔。通常为10s
• RouterDeadInterval：失效时间。如果在此时间内未收到邻居发来的Hello报文，则认为邻居失效
• Neighbor：邻居，以Router ID标识

其它字段解释：

• Options：
  • E：是否支持外部路由
  • MC：是否支持转发组播数据包
  • N/P：是否为NSSA区域
• Router Priority ：DR优先级。默认为1。如果设置为0，则路由器不能参与DR或BDR的选举。
• Designated Router ：DR的接口地址
• Backup Designated Router ：BDR的接口地址

建立邻接关系：

• 邻居状态机从2-way转为Exstart状态后开始主从关系选举：
  • R1向R2发送的第一个DD报文内容为空，其Seq序列号假设为X
  • R2也向R1发出第一个DD报文，其Seq序列号假设为Y
  • 选举主从关系的规则是比较Router ID，越大越优。R2的Router ID比R1大，因此R2成为真正的主设备主从关系比较结束后，R1的状态从Exstart转变为Exchange
• R1邻居状态变为Exchange后，R1发送一个新的DD报文，包含自己LSDB的描述信息，其序列号采用主设备R2的序列号。R2收到后邻居状态从Exstart转变为Exchange
• R2向R1发送一个新的DD报文，包含自己LSDB的描述信息，序列号为Y+1
• R1作为从路由器需要对主路由R2发送的每个DD报文进行确认，回复报文的序列号与主路由R2一致
• 发送完最后一个DD报文后，R1将邻居状态切换为Loading

• 邻居状态转变为Loading后，R1向R2发送LSR报文，请求那些在Exchange状态下通过DD报文发现的，但是在本地LSDB中没有的LSA
• R2收到后向R1回复LSU。在LSU报文中包含被请求的LSA的详细信息
• R1收到LSU报文后，向R2回复LS ACK报文，确认已接收到，确保信息传输的可靠性
• 此过程中R2也会向R1发送LSA请求。当两端LSDB完全一致时，邻居状态变为Full，表示成功建立邻接关系

DD报文

DD报文包含LSA头部信息，包括LS Type、LS ID、Advertising Router、LS Sequence Number、LS Checksum

DD报文部分字段解释

• Interface MTU：

  • 指示在不分片的情况下，此接口最大可发出的IP报文长度。在两个邻居发送DD报文中包含MTU参数，如果收到的DD报文中MTU和本端的MTU不相等，则丢弃该DD报文
  • 缺省情况下，华为设备未开启MTU检查

• Optinons：字段同Hello报文

• 标准位：

  • I：当发送连续多个DD报文时，如果这是第一个DD报文，则置为1，否则置为0。
  • M [More]：当发送连续多个DD报文时，如果这是最后一个DD报文，则置为0。否则置为1，表示后面还有其他的DD报文。
  • MS [Master/Slave]：当两台OSPF路由器交换DD报文时，首先需要确定双方的主从关系，Router ID大的一方会成为Master。当值为1时表示发送方为Master

• DD sequence number ：DD报文序列号。主从双方利用序列号来保证DD报文传输的可靠性和完整性

邻居状态及含义说明：

邻居状态	含义
Down	初始状态，表示没有从邻居收到任何信息
Init	路由器已经从邻居收到了Hello报文，但自己的Router ID不在所收到的Hello报文的邻居列表中
2-way	路由器发现自己的Router ID存在于收到的Hello报文的邻居列表中
ExStart	路由器开始向邻居发送DD报文，在此状态下发送的DD报文不包含链路状态描述
Exchange	路由器与邻居之间相互发送包含链路状态信息摘要的DD报文
Loading	路由器与邻居之间相互发送LSR报文、LSU报文、LSAck报文
Full	路由器已完成了与邻居的LSDB同步

OSPF网络类型

OSPF网络类型是一个非常重要的接口变量，会影响OSPF在接口上的操作。接口默认的OSPF网络类型取决于接口所使用的数据链路层封装

• OSPF的有四种网络类型，Broadcast、NBMA、P2MP和P2P
• 链路两端的OSPF接口网络类型必须一致，否则双方无法建立邻居关系

DR [指定路由器] 与BDR [备份指定路由器]

背景引入：

• MA[ Multi-Access] 多路访问网络有两种类型：广播型多路访问网络 [BMA] 及非广播型多路访问网络[NBMA]
• 以太网 [Ethernet] 是一种典型的广播型多路访问网络
• 在MA网络中，如果每台OSPF路由器都与其他的所有路由器建立OSPF邻接关系，便会导致网络中存在过多的OSPF邻接关系，增加设备负担，也增加了网络中泛洪的OSPF报文数量
• 当拓扑出现变更，网络中的LSA泛洪可能会造成带宽的浪费和设备资源的损耗

引入DR与BDR：

• 为优化MA网络中OSPF邻接关系，OSPF指定了三种OSPF路由器身份，DR [Designated Router，指定路由器]、BDR [Backup Designated Router，备用指定路由器 ]和 [DRother] 路由器
• 只允许DR、BDR与其他OSPF路由器建立邻接关系。DRother之间不会建立全毗邻的OSPF邻接关系，双方停滞在2-way状态
• BDR会监控DR的状态，并在当前DR发生故障时接替其角色

选举规则：

• DR/BDR的选举是基于接口的

  • 优先级更高的接口成为该MA的DR，如果优先级相等 [默认值都是1]，则具有更高的OSPF Router-ID的路由器 [的接口] 被选举成DR

• DR/BDR的选举是非抢占式的

广播链路或者NBMA链路上DR和BDR的选举过程

1. 接口UP后，发送Hello报文，同时进入到Waiting状态。在Waiting状态下会有一个WaitingTimer，该计时器的长度与DeadTimer是一样的。默认值为40秒，用户不可自行调整。
2. 在WaitingTimer触发前，发送的Hello报文是没有DR和BDR字段的。在Waiting阶段，如果收到Hello报文中有DR和BDR，那么直接承认网络中的DR和BDR，而不会触发选举。直接离开Waiting状态，开始邻居同步
3. 假设网络中已经存在一个DR和一个BDR，这时新加入网络中的路由器，不论它的Router ID或者DR优先级有多大，都会承认现网中已有的DR和BDR
4. 当DR因为故障Down掉之后，BDR会继承DR的位置，剩下的优先级大于0的路由器会竞争成为新的BDR
5. 只有当不同Router ID，或者配置不同DR优先级的路由器同时起来，在同一时刻进行DR选举才会应用DR选举规则产生DR

OSPF网络类型	常见链路层协议	是否选举DR	是否和邻居建立邻接关系
Point-to-point	PPP链路；HDLC链路	否	是
Broadcast	以太网链路	是	DR和BDR与其他设备建立邻接关系、DRother之间只建立邻居关系
NBMA	帧中继链路
P2MP	需手工指定	否	是

OSPF域

OSPF域 [Domain]：一系列使用相同策略的连续OSPF网络设备所构成的网络
OSPF路由器在同一个区域 [Area ]内网络中泛洪LSA。为了确保每台路由器都拥有对网络拓扑的一致认知，LSDB需要在区域内进行同步

OSPF单区域与其产生的问题：

• 如果OSPF域仅有一个区域，随着网络规模越来越大，OSPF路由器的数量越来越多，这将导致诸多问题：
  • LSDB越来越庞大，同时导致OSPF路由表规模增加。路由器资源消耗多，设备性能下降，影响数据转发
  • 基于庞大的LSDB进行路由计算变得困难
  • 当网络拓扑变更时，LSA全域泛洪和全网SPF重计算带来巨大负担

OSPF多区域：

• OSPF引入区域 [Area] 的概念，将一个OSPF域划分成多个区域，可以使OSPF支撑更大规模组网
• OSPF多区域的设计减小了LSA泛洪的范围，有效的把拓扑变化的影响控制在区域内，达到网络优化的目的
• 在区域边界可以做路由汇总，减小了路由表规模
• 多区域提高了网络扩展性，有利于组建大规模的网络

区域的分类：区域可以分为骨干区域与非骨干区域。骨干区域即Area0，其他区域都称为非骨干区域

多区域互联原则：基于防止区域间环路的考虑，非骨干区域与非骨干区域不能直接相连，所有非骨干区域必须与骨干区域相连

OSPF路由器类型

OSPF路由器根据其位置或功能不同，有这样几种类型：

• 区域内路由器 IR [Internal Router]：该类路由器的所有接口都属于同一个OSPF区域
• 区域边界路由器 ABR [Area Border Router]：该类路由器的接口同时属于两个以上的区域，但至少有一个接口属于骨干区域
• 骨干路由器 BR [Backbone Router]：该类路由器至少有一个接口属于骨干区域
• 自治系统边界路由器 ASBR [AS Boundary Router]：该类路由器与其他AS交换路由信息。只要一台OSPF路由器引入了外部路由的信息，它就成为ASBR

OSPF协议配置命令

1. 创建并运行OSPF进程

[Huawei] ospf [ process-id | router-id router-id ]
#porcess-id用于标识OSPF进程，默认进程号为1
#OSPF支持多进程，在同一台设备上可以运行多个不同的OSPF进程，它们之间互不影响，彼此独立
#router-id用于手工指定设备的ID号。如果没有通过命令指定ID号，系统会从当前接口的IP地址中自动选取一个作为设备的ID号

2. 创建并进入OSPF区域

[Huawei-ospf-1] area area-id 
# area命令用来创建OSPF区域，并进入OSPF区域视图
# area-id可以是十进制整数或点分十进制格式。采取整数形式时，取值范围是0～4294967295

参数	参数说明
area-id	指定区域的标识，其中区域号area-id是0的称为骨干区域

3. [OSPF区域视图] 在OSPF区域中使能OSPF

[Huawei-ospf-1-area-0.0.0.0] network network-address wildcard-mask 

参数	参数说明
network-address	接口所在的网段地址
wildcard-mask	IP地址的反码，将IP地址的掩码反转 [0变1，1变0]
description text	OSPF指定网段的描述信息

4. 接口视图下使能OSPF：

[Huawei-GigabitEthernet1/0/0] ospf enable process-id  area area-id
#	ospf enable命令用来在接口上使能OSPF，优先级高于network命令

5. [接口视图] 配置OSPF接口开销

[Huawei-GE1/0/1] ospf cost cost	# ospf cost命令用来配置接口上运行OSPF协议所需的开销
#	缺省情况下，OSPF会根据该接口的带宽自动计算其开销值cost取值范围是1～65535

6. [OSPF视图] 设置OSPF带宽参考值

[Huawei-ospf-1] bandwidth-reference value
#	bandwidth-reference命令用来设置通过公式计算接口开销所依据的带宽参考值
#	value取值范围是1～2147483648，单位是Mbit/s，缺省值是100Mbit/s

7. [接口视图] 设置接口在选举DR时的优先级

[Huawei-GigabitEthernet0/0/0] ospf dr-priority priority
#	缺省情况下，优先级为1

参数	参数说明
priority	接口在选举DR或BDR时的优先级，其值越大，优先级越高

8. [接口视图] 设置Hello报文发送的时间间隔：

[Huawei-GigabitEthernet1/0/0] ospf timer Hello interval
#缺省情况下，P2P、Broadcast类型接口发送Hello报文的时间间隔的值为10秒，且同一接口上邻居失效时间是Hello间隔时间的4倍

9. [接口视图] 设置网络类型：

[Huawei-GigabitEthernet1/0/0] ospf network-type { broadcast | nbma | p2mp | p2p }
#	缺省情况下，接口的网络类型根据物理接口而定。以太网接口的网络类型为广播，串口和POS口（封装PPP协议或HDLC协议时）网络类型为P2P