开放式最短路径优先

網際網絡協定
(重定向自开放最短路径优先

开放式最短路径优先(英語:Open Shortest Path First,缩写为 OSPF)是广泛使用的一种路由协议,它属于链路状态路由协议,具有路由变化收敛速度快、无路由环路、支持变长子网掩码(VLSM)和汇总、层次区域划分等优点。

OSPF是一种基于IP协议路由协议。它是大中型网络上使用较为广泛的IGP协议。OSPF是对链路状态路由协议英语Link-state routing protocol的一种实现,运作于自治系统内部。OSPF分为OSPFv2和OSPFv3两个版本:OSPFv2定义于RFC 2328(1998),支持IPv4网络;而OSPFv3定义于RFC 5340(2008),支持IPv6网络。

它采用戴克斯特拉算法来计算最短路径树。它使用“开销(Cost)”作为路由度量。链路状态数据库(LSDB)用来保存当前网络拓扑结构,路由器上属于同一区域的链路状态数据库是相同的(属于多个区域的路由器会为每个区域维护一份链路状态数据库)。

OSPF提出了“区域(Area)”的概念,一个网络可以由单一区域或者多个区域组成。其中,一个特别的区域被称为骨干区域(Backbone Area),该区域是整个OSPF网络的核心区域,并且所有其他的区域都与之直接连接。所有的内部路由都通过骨干区域传递到其他非骨干区域。所有的区域都必须直接连接到骨干区域,如果不能建立直接连接,那么可以通过虚链路(virtual link)和骨干区域建立虚拟连接

同一个广播域(Broadcast Domain)的路由器或者一个点对点(Point To Point)连接的两端的路由器,在发现彼此的时候,建立邻接(Adjacencies)[註 1]。多路访问网络以及非广播多路访问网络的路由器会选举指定路由器(Designated Router, DR)和备份指定路由器(Backup Designated Router, BDR),DR和BDR作为网络的中心负责路由器之间的信息交换从而降低了网络中的信息流量。OSPF协议同时使用单播(Unicast)和群播(Multicast)来发送Hello包和链路状态更新(Link State Updates),使用的群播地址为224.0.0.5和224.0.0.6。与RIPBGP不同的是,OSPF协议不使用TCP或者UDP协议而是直接承载在IP协议之上,IP协议号为89。

区域

 
一个多区域OSPF网络,注意所有的非骨干区域都和骨干区域直接相连,并且R2和R3属于多个区域。

一个OSPF网络分为多个区域。区域将网络中的路由器在逻辑上分组并以区域为单位向网络的其余部分发送汇总路由信息。区域编号由一个长度为32位的字段所定义,区域编号有两种表示方法,一种为点分十进制(如Area 1.1.1.1,写法规则同IPv4地址);另外一种为十进制数字格式(如Area 1,注意Area 1不等于Area 1.1.1.1,而是0.0.0.1)。根據 RFC2328 描述,區域編號通常使用 32 bits的點分十進位表示。区域编号不是IP地址,用于IPv6网络的OSPFv3也使用同样的(形似IPv4地址的)区域编号格式。

区域是以接口(Interface)为单位来划分的,所以一台多接口路由器可能属于多个区域。相同区域内的所有路由器都维护一份相同的链路状态数据库(LSDB),如果一台路由器属于多个区域,那么它将为每一个区域维护一份LSDB。 将一个网络划分为多个区域有以下优点:[來源請求]

  • 某一区域内的路由器只需要维护该区域的链路状态数据库,而不用维护整个OSPF网络的链路状态数据库。
  • 将某一区域网络拓扑变化的影响限制在该区域内,不会影响到整个OSPF网络,从而减小OSPF计算的频率。
  • 将链路状态通告(LSA)的洪泛限制在本区域内,从而降低OSPF协议产生的数据量。
  • 划分区域可以对网络进行层次化结构设计。
  • 划分区域有利于资源合理调配,核心区域部署性能较好的设备资源,边缘区域部署性能较差的设备资源即可。

OSPF有多种区域类型,其中定义了几种特殊的区域:

骨干区域

骨干区域(Backbone Area),Area 0(点分十进制表示为0.0.0.0),是整个OSPF域的核心区域。所有其他非骨干区域必须和骨干区域直接或间接相连。骨干区域的功能是在不同的非骨干区域之间分发路由信息。

骨干区域必须是唯一而且连续的,但不需要在物理上连续:它可以使用虚拟连接。

传送区域

传送区域连接至少2个其他区域,它将通告从一个区域传送到另一个区域。

末梢区域

末梢区域(Stub Area)是一个不允许AS外部路由通告(AS External LSA,即类型5 LSA)在其内部进行洪泛扩散的区域。末梢区域的ABR会通告一条默认路由(default route)到该区域内所有路由器,任何发往AS外部网络的数据流都将依据默认路由来转发。

不完全末梢区域

非纯末梢区域(Not-So-Stubby Area,NSSA)允许引入AS外部路由并且扩散到其他区域,但是NSSA仍旧不允许其他区域通告的AS外部路由进入该区域。为了使NSSA能够引入AS外部路由,OSPF定义了新的LSA类型,即NSSA External LSA(类型7 LSA)。NSSA ASBR将产生类型7 LSA,并在NSSA区域内洪泛。NSSA ABR将会把类型7 LSA转换成5类LSA,并洪泛到其他区域。

完全末梢区域

完全末梢区域(Totally Stubby Areas)是 Cisco 特有的区域类型。完全末梢区域不仅不允许AS外部路由通告在其内部洪泛,还不允许区域间汇总路由(Network Summary LSA ,即类3 LSA)在其内部洪泛。同末梢区域一样,完全末梢区域ABR也会向该区域内所有路由器通告一条默认路由,任何发往其他区域以及AS外部网络的数据流都将依据默认路由来转发。将区域设置为完全末梢区域可以显著的降低路由表条目的数量。

完全非纯末梢区域

完全非纯末梢区域(Totally NSSA)也是 Cisco 特有的区域类型,该种区域除了拥有和NSSA相同的特性外,还不允许类型3 LSA在该区域内部洪泛。完全非纯末梢区域ABR也会向该区域内所有路由器通告一条默认路由。将区域设置为完全非纯末梢区域也会显著的降低路由表条目的数量。

OSPF路由器类型

 
R2既是骨干路由器,也同时是ABR和ASBR(R2和R5之间运行了BGP,并且R2将BGP路由重分发进OSPF)。R3是一台ABR,R1和R4是内部路由器。

OSPF定义了以下4种路由器类型:

  • 内部路由器(Internal Router)
  • 骨干路由器(Backbone Router)
  • 区域边界路由器(Area Border Router,ABR)
  • 自治系统边界路由器(Autonomous System Boundary Router,ASBR)

一台路由器可以同时属于多种类型,如右图所示,R2同时属于多种类型路由器。

每一台OSPF路由器都有一个路由器标识符(Identifier),一般写作路由器ID。路由器ID由一个长度为32 bits的字段所定义,通常用IPv4地址格式来表示(如1.2.2.2)。如果没有显式的设置路由器ID,则该路由器上最大的活跃逻辑接口IP地址将成为路由器ID;如果路由器不存在逻辑接口,则最大的活跃物理接口IP地址将成为路由器ID。注意,不要将路由器类型和指定路由器(Designated Router,DR)、备份指定路由器(Backup Designated Router,BDR)混淆,DR和BDR是路由器接口属性,而不是整个路由器的属性。

内部路由器

如果一台路由器上所有启用了OSPF的接口都在同一区域,那么这台路由器就是内部路由器。

骨干路由器

骨干路由器是指至少有一个启用了OSPF的接口是和骨干区域(Area 0)相连的路由器。一台骨干路由器也可以同时是ABR或ASBR,如上图中的R2和R3。

区域边界路由器

区域边界路由器是指连接一个或者多个区域的路由器。区域边界路由器为每一个与之相连的区域维护一份链路状态数据库,因此区域边界路由器需要比内部路由器更多的内存资源和更高性能的处理器

自治系统边界路由器

自治系统边界路由器(ASBR)用来把从其他路由协议(如BGPEIGRP其他进程号的OSPF等)学习到的路由以路由重分发的方式注入到OSPF进程中,从而使得整个OSPF域内的路由器都可以学习到这些路由(除了末梢区域内的路由器)。一台ASBR可以是OSPF域内非末梢区域的任何路由器,它可以是内部路由器、区域边界路由器、骨干路由器。

OSPF网络类型

OSPF定义了以下4种网络类型:[1]

  • 点到点网络(point-to-point)
  • 广播网络(broadcast)
  • 非广播多路访问网络(non-broadcast multi-access,NBMA)
  • 点到多点网络(Point-to-MultiPoint)

点到点网络

点到点网络,例如E1、SONET,是单独连接一对路由器的网络。点到点网络上的一对OSPF路由器形成完全邻接关系(Full Adjacency),并且不进行DR和BDR的选举。点到点网络上的路由器使用群播地址224.0.0.5发送OSPF协议数据包。

广播网络

广播网络即可以同时连接多于两台设备的网络,如以太网令牌环网FDDI。广播网络上的路由器发送的群播/广播数据包会被其他与之相连的路由器收到。在广播网络上的OSPF路由器会选举一台指定路由器(DR)和一台备份指定路由器(BDR)。所有始发于DR和BDR的OSPF数据包使用目的地址224.0.0.5,以群播方式发送到所有其他OSPF路由器,所有其他的路由器都将使用目的地址224.0.0.6,以群播方式发送OSPF数据包到DR和BDR。所有其他的路由器只与DR和BDR建立完全邻接关系。

非广播多路访问网络

NBMA网络,诸如X.25帧中继ATM等,可以同时连接两台以上的路由器,但是这种网络没有广播数据包的能力。一台处于NBMA网络上的路由器发送的群播/广播数据包将不能被其他与之相连的路由器收到。在NBMA网络上需要选举DR和BDR,并且所有的OSPF数据包都是单播发送的。

点到多点网络

点到多点网络是NBMA网络的一个特殊设置,可以看作是一群点到点链路的集合,因此在该种网络上不必选举DR和BDR。点到多点网络上OSPF的行为和点到点网络OSPF的行为一样,也使用群播地址224.0.0.5发送OSPF协议数据包。

虚链路

虚链路被路由器认为是没有编号的点到点网络的一种特殊设置,在虚链路上OSPF数据包是以单播方式发送的。不能人工设置一个接口的网络类型为虚链路。

此外还有一种特殊的网络类型,称之Loopback类型。OSPF路由器上的环回接口在默认状态下均为此类型。不能人工设置一个接口的网络类型为Loopback。

指定路由器和备份指定路由器

 
多路访问网络上OSPF邻接关系示意图

在广播多路访问网络和NBMA网络上会选举DR和BDR。所有其他路由器只与DR和BDR建立完全邻居关系,其他路由器之间的邻居状态停留在2-Way状态。所有其他路由器使用群播目的地址224.0.0.6向DR和BDR发送链路状态更新。

如果在多路访问网络中不选举DR,所有路由器之间都建立完全邻接关系,会产生很多不必要的LSA。假设一个多路访问网络上有n台路由器,那么就会建立n(n-1)/2个邻接关系。每台路由器都会产生n-1条LSA到与之建立邻接关系的路由器,再加上1条网络LSA,最终这个网络上会产生n²条LSA,并且其中很多都是重复的LSA副本。

DR完成以下工作:

  • 描述该多路访问网络和与其相连的路由器。
  • 管理该多路访问网络上的LSA洪泛扩散过程。

DR本后的概念是将多路访问网络看作一个“伪节点(Pseudo Node)”。当SPF进行计算的时候,把链路看作一个节点,与该链路相连的路由器也是连接到这个节点上的。从与伪节点相连的路由器到这个伪节点的代价是该路由器与这个多路访问网络相连的接口的出站代价,从伪节点到任何与之相连的路由器的代价都为0。一台路由器可能连接到多个多路访问网络,该路由器可能是它所连接的其中一个多路访问网络的DR,也可能不是它所连接的另一个多路访问网络的DR,也就是说,DR是路由器接口的属性,而不是整个路由器的属性。

为了避免因DR失效导致的单点故障,多路访问网络上还将选举BDR。DR失效时,BDR将成为DR,由于网络上其他路由器已经和BDR形成了完全邻接关系,因此可以将DR失效对网络的影响降至最低。

DR和BDR的相关选举规则如下:

  • 如果一台OSPF路由器的接口优先级(Priority)为0,那么这台路由器永远不能成为DR或BDR。
  • 具有最高优先级的路由器将会选举为DR,具有次高优先级的路由器将会选举为BDR。
  • 如果同时有多台路由器具有相同的优先级,那么具有最高路由器ID的路由器将会选举为DR。
  • 当DR失效时,BDR将成为DR,并将重新选举一个BDR。
  • 优先级的取值范围为0-255,更高的优先级意味着路由器有更大的机会成为DR。
  • 如果一台具有更高优先级的路由器在选举完DR和BDR之后接入网络,该路由器将不会成为DR或BDR,直到DR和BDR失效,当DR失效,具有更高优先级的路由器也只会成为BDR。即DR和BDR的选举不是抢占式的。

OSPF邻接关系

在OSPF路由器之间互相交换信息之前,必须先建立邻接关系。

两台OSPF路由器要建立完全邻接关系,以下参数必须相同:

  1. Hello时间间隔
  2. Dead时间间隔
  3. 区域编号
  4. 认证(如果启用了认证)
  5. 链路MTU大小
  6. 子网掩码
  7. 子网号
  8. 末梢区域设置

一般来说,建立OSPF完全邻接时会经过以下状态:

  1. 失效状态(Down):这是邻居会话的初始状态,表示最近没有从邻居收到信息。在NBMA网络上,可能仍然会以较低频率向处于Down状态的邻居发送Hello数据包。
  2. 尝试状态(Attempt):该状态仅仅适用于连接在NBMA网络上的邻居。该状态表示最近没有从邻居收到信息,但仍需要作进一步的尝试,来联系邻居。这时按某一特定间隔向邻居发送Hello数据包。
  3. 初始状态(Init):在此状态下,表示最近收到了从邻居发来的Hello数据包。但是,仍然没有和邻居建立双向通信(Bidirectional Communication),例如,路由器自身并没有出现在邻居发送的Hello数据包中。
  4. 双向通信状态(2-Way):此状态意味着两台路由器之间建立了双向通信。在此状态下还将进行DR和BDR的选举(只有处于2-Way状态的路由器才有资格参选DR和BDR)
  5. 信息交换初始状态(ExStart):这个状态是建立邻接关系的第一步。该状态的目标是决定信息交换时路由器的主从关系,并确定初始数据库描述(DD)数据包的序列号。具有最高路由器ID的路由器将成为主路由器。
  6. 信息交换状态(ExChange):在此状态的路由器通过向邻居发送DD数据包来描述其完整的链路状态数据库。每一个DD数据包都有一个序列号,并且需要被显式的确认。在任何时候,每次只能发送一个DD数据包。在此状态下,路由器也可以发送链路状态请求数据包,用来向邻居请求最新的LSA。实际上,这些状态的邻接关系完全有能力发送和接收所有类型的OSPF协议数据包。
  7. 信息加载状态(Loading):在此状态下,路由器将会向邻居路由器发送链路状态请求数据包,用来请求信息交换状态发现的最新的LSA。
  8. 完全邻接状态(Full):在此状态下,邻居路由器形成完全邻接关系。这些邻接关系将会在路由器LSA和网络LSA中被描述。

OSPFv2数据包类型和格式

OSPFv2定义了以下5种协议数据包类型:

  1. Hello包 HELLO
  2. 数据库描述包 DBD
  3. 链路状态请求包 LSR
  4. 链路状态更新包 LSU
  5. 链路状态确认包 LSAck

OSPF包头

5种OSPF消息有共通的24字节的头部结构。其结构如下:

第1字节 第2字节 第3字节 第4字节
0~31 Version # type Packet length
32~63 Router ID
64~95 Area ID
96~127 Checksum AuthType
128~159 Authentication
160~191 Authentication

Hello包

Hello包的OSPF包类型为1。这些包被周期性的从各个接口(包括虚链路)发出,用来建立和维护邻居关系。另外,在支持群播或广播的物理网络上,Hello包使用群播地址(通常为224.0.0.5)发送。 Hello包的发送间隔由HelloInterval指定(通常为10s),路由器将会先发出不包含邻居字段的空Hello包,当收到邻接路由器的Hello包之后,将对方的路由器标识放入本机的Hello包中进行群播,这种包含邻居字段的包,也被称为HelloSeen包。假如在间隔达到RouterDeadInterval所规定的时长(通常为40s)内仍未收到一个已建立连接的路由器的Hello包,路由器将会终止这一连接。将对方的状态转为Down。 Hello包的格式如下:

第1字节 第2字节 第3字节 第4字节
0~191 OSPF包头
192~223 Network Mask
224~255 HelloInterval Options Rtr Pri
256~287 RouterDeadInterval
288~319 Designated Router
320~351 Backup Designated Router
352~383 Neighbor
……

数据库描述包

数据库描述包(Database Description)的OSPF包类型为2。当邻接关系初始化后,便开始交换这些数据包。它们描述了链路状态数据库的摘要信息(只包含LSA的头部信息)。

数据库描述包包含两种,即空数据库描述包和包含LSA头部信息的数据库描述包。

当两个路由器互相收到HelloSeen包之后,他们将会开始互相发送空数据库描述包,空数据库描述包被用来进行主从关系的确定。 通常以路由标识较大的为Master,当主从关系确立之后,从机将会使用主机的序号向主机发送第一个包含LSA头部信息的数据库描述包。主机将会在收到从机的数据库描述包之后发送自己的序号加一的数据库描述包,作为对于从机的收到确认。在这样的交互过程中,只有主机可以更改序号(DD sequence number),从机使用主机序号。数据库描述包的格式如下:

0~7 8~15 16~23 24 25 26 17 28 29 30 31
第1字节 第2字节 第3字节 第4字节
0~191 OSPF包头
192~223 Interface MTU Options 0 0 0 0 0 I M MS
224~255 DD sequence number
256~287 An LSA Header
288~319
320~351
352~383
384~415
……

链路状态请求包

链路状态请求包(Link State Request)的OSPF包类型为3。在交换数据库描述包之后,路由器便知道其自身链路状态数据库缺少哪些LSA,以及哪些LSA是过期的。这时就可以发送链路状态请求包来请求对方发送缺少的LSA和最新的LSA。链路状态请求包格式如下:

第1字节 第2字节 第3字节 第4字节
0~191 OSPF包头
192~223 LS type
224~255 Link State ID
256~287 Advertising Router
……

链路状态更新包

链路状态更新包(Link State Update)的OSPF包类型为4。LSA的洪泛就是由此类型的包实现的。每一个链路状态更新包可能包含多条LSA信息。这里的LSA信息是完整的,而不像数据库描述包只包含LSA的头部信息。

链路状态更新包的格式如下:

第1字节 第2字节 第3字节 第4字节
0~191 OSPF包头
192~223 # LSAs
224~255 LSAs
256~287
288~319
……

链路状态确认包

链路状态确认包(Link State Acknowledgement)的OSPF包类型为5。为了确保LSA的洪泛是可靠的,LSA信息必须被显式的确认。链路状态确认包的格式如下:

第1字节 第2字节 第3字节 第4字节
0~191 OSPF包头
192~223 An LSA Header
224~255
256~287
288~319
320~351
……

LSA类型

OSPF定义了11种LSA,所有类型的LSA都以一个20字节的通用LSA头部开始。这些不同类型的LSA共同描述了OSPF域内的网络拓扑结构。所有的LSA都保存在LSDB中。SPF算法根据LSDB中的信息计算出最佳路径。

  1. 路由器LSA(Router-LSA):路由器LSA的类型为1。每一台OSPF路由器生成一条路由器LSA。该LSA描述了路由器的接口状态,以及每一个接口的出站代价。路由器LSA只能在始发他们的OSPF区域内进行洪泛,不能洪泛到其他区域。
  2. 网络LSA(Network-LSA):网络LSA的类型为2。网络LSA是DR为了描述连接到多路访问网络并且和DR建立了完全邻接关系的路由器而生成的,包括DR本身。和路由器LSA一样,网络LSA也只能在始发这条LSA的区域内进行洪泛。
  3. 汇总LSA(Summary-LSA):汇总LSA的类型为3。此类LSA描述了区域间的网络,由ABR生成。对于末梢区域,汇总LSA同样被用于描述默认路由。
  4. ASBR汇总LSA(ASBR Summary-LSA):ASBR汇总LSA的类型为4,也是由ABR生成。ASBR汇总LSA通告的是一台区域外部的ASBR路由器,而不像汇总LSA通告的是区域外的网络。
  5. 自治系统外部LSA(AS-External-LSA):自治系统外部LSA的类型为5,由ASBR生成。此类LSA描述AS外部的网络,并可以洪泛到所有非末梢区域中去。
  6. 组成员LSA(Group-Membership-LSA ):组成员LSA类型为6。组成员LSA是对标准OSPF的一个扩展,使其支持群播路由功能,扩展后的OSPF称之Multicast Open Shortest Path First(MOSPF)。
  7. NSSA外部LSA(NSSA-External-LSA):NSSA外部LSA类型为7。此类LSA由NSSA区域内的ASBR生成,也用来描述AS外部的网络。NSSA外部LSA仅仅在始发他们的NSSA区域内进行洪泛,而不像自治系统外部LSA可以洪泛到所有非末梢区域。
  8. 链路本地LSA(Link-Local LSA):链路本地LSA类型为8。该LSA专门用于OSPFv3(用于IPv6网络的OSPF)。链路本地LSA包含了每一个接口的链路本地地址和一个IPv6地址列表。

RFC2370定义了3种新的LSA,称作不透明LSA(Opaque LSA)。这3种新的LSA为OSPF的扩展性提供了通用的机制。它们可以携带用于OSPF的信息,也可以直接携带应用的信息。 目前有以下3种不透明LSA,它们的区别主要是洪泛范围不同:

  • 类型9不透明LSA:洪泛范围仅仅是本地链路。
  • 类型10不透明LSA:洪泛范围是始发该LSA的区域。
  • 类型11不透明LSA:洪泛范围是整个OSPF域。

OSPF路径选择

OSPF使用“开销(Cost)”作为路由的度量值(Metric),路径的度量值越低,说明该路径越好,具有最低度量值的路径将装入路由表。开销是根据接口所配置的带宽来计算的,带宽越高,开销越低。在Cisco路由器上,默认情况下使用公式10^8/带宽(10^8是基准值,可以调整;带宽的单位是bit/s)来计算代价。例如,接口带宽为100Mbit/s,则开销为1;接口带宽为1000Mbit/s,计算所得的开销还是1(如果计算所得的开销小于1,则按1计算)。 OSPF有以下4种路由类型,优先级由高到低排序如下:

  1. 内部路由:去往区域内部网络的路由。
  2. 区域间路由:去往不同区域网络的路由。
  3. 类型1的外部路由:去往OSPF域外的路由,类型1的外部路由的度量值包括了外部路由的度量值和到ASBR的度量值。
  4. 类型2的外部路由:去往OSPF域外的路由,类型2的外部路由的度量值只包括了外部路由的度量值。

因此如果有多条去往相同目的地的路由具有相同的度量值,那么将比较它们的路由类型。假设有两条去往相同目的地的路由A和路由B的度量值都是30,A是内部路由,B区域间路由,则A将会被装入路由表。如果有多条去往相同目的地的路由具有相同的类型,相同的度量值,则它们都将被装入路由表,并在不同路由之间进行负载均衡。

OSPF的反击机制

大多数运行OSPF的路由器具有一种被称为(fight back)的安全机制。即当一个路由器收到关于自己的虚假或者不正确的LSA信息时,它将立刻发出一个包含自己正确的LSA的LSU报文,这一机制被称为反击或者自反击。 不过需要注意的是,反击机制并不是OSPF协议官方规定的安全机制。在RFC2328中,没有对此机制的任何描述。

注释

  1. ^ 实际上,广播网路中的路由器彼此之间并不一定建立邻接,这取决于网络中指定路由器的选举结果,所有的路由器都与同一个广播网络中的指定路由器以及备份指定路由器建立邻接,而非指定路由器之间彼此仅仅纪录对方为双工通信可能而不建立邻接。

参考文献

引用

  1. ^ RFC 2328 - OSPF Version 2. RFC. [2017-07-20]. (原始内容存档于2021-04-27). The neighborhood of each network node in the graph depends on the network's type (point-to-point, broadcast, NBMA or Point-to-MultiPoint) and the number of routers having an interface to the network. 

来源

  • Jeff Doyle; Jennifer Carroll. Routing TCP/IP. Volume I Second Edition. America: Cisco Press. 2005-10-19 (英语). 

相關條目

外部連結