OSPF协议的LSDB分析和路由计算

本文格式为Word版，下载可任意编辑——OSPF协议的LSDB分析和路由计算

北京金桥世纪

OSPF协议的LSDB分析和路由计算

北京金桥世纪

目录

1OSPF协议的LSDB分析和路由计算61.1OSPF的路由形成概述61.2组网图61.3OSPF的启动7

1.3.1启动OSPF71.3.2接口使能OSPF81.4LSDB详解91.5RouterLSA101.6NetworkLSA121.7由一、二类LSA计算域内路由13

1.7.1域内路由计算1：计算最短路径树131.7.2域内路由计算2：把存根网络作为叶子参与最短路径树231.8SummaryLSA24

1.8.1SummaryNetworkLSA241.8.2SummaryASBRLSA261.9AS-external-LSA261.10计算区域外部路由27

1.10.1根据SummaryLSA计算区域外部路由271.10.2根据AS-external-LSA计算区域外部路由28

2FAQ302.1初学OSPF，看哪些文章好？302.2什么是接口状态，什么是邻居状态，它们之间有什么关系？302.3建立邻居关系需要多少时间？332.4当存在连续的两个非骨干区域时，最边缘的区域怎样建立虚连接？332.5在NSSA区域中的ABR，没有引入路由的状况下，为什么其声称自己是ASBR？...332.6当NSSA区域有多个ABR时，谁进行type7类LSA到type5类LSA的转换？332.7LSA和报文的关系332.8报文的作用342.9DD报文中的I/M/MS位解释342.10有关路由COST的问题34

北京金桥世纪

图目录

图1OSPF组网图7图2的area0上的最短路径树114图3的area0上的最短路径树216图4的area0上的最短路径树317图5的area0上的最短路径树419图6的area0上的最短路径树520图7的area0上的最短路径树622图8的area0上的最短路径树723图9邻居状态机转换图30图10OSPF的邻居状态截图31图11接口状态机转换图32图12OSPF的接口状态截图32

北京金桥世纪

图目录

表1五种LSA类型9表2交换机接口的四种连接类型11表3最短路径树计算所需的节点数据结构14

北京金桥世纪

OSPF协议的LSDB分析和路由计算

北京金桥世纪

ID、Date、Type和Metric等四项。

这里的Type指的是交换机接口的连接类型，见表2：

表2交换机接口的四种连接类型

1234连接类型P2PTransNetStubNetVirtual?说明：

描述点对点连接连接到传输网络连接到存根网络虚拟通道

连接标识邻居路由器标识DR的接口地址网络IP地址邻居路由器标识连接数据自身的IP接口地址自身的IP接口地址网络掩码自身的IP接口地址传输网络是指接入了两台或更多路由器的网络。假使路由器与DR完全邻接，或路由器自身为DR且与至少一台其他路由器邻接，则所接入的网络的网络类型就是传输网络类型。

存根网络就是接入了一台路由器的网络，即该网络只通过一个路由器和外界联系。假使某网络只接入了当前路由器，则该接口的连接类型就是存根网络类型。

另外，最开始显示的area0的LSDB中有这么一条LSA：

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhereStub1124240x00SpfTree

这个Stub类型的LSA似乎很熟悉，可它又不是五类LSA中的一种，那么它是哪来的？比较这个LSA和生成RouterLSA，发现该LSA的LinkStateID和发布的RouterLSA中的一个StubNet连接一致。

咨询过开发的同事，了解到原来V3实现OSPF时，为便利计算路由，把RouterLSA中的StubNet连接单独拿出来列为一个LSA。

注意，这类“LSA〞虽然有老化时间，但是它的序列号是永远为0，也就是说它的内容是不会改变的。再细心想想，其实StubNet路由的处理方法和AS外的路由（作为第五类LSA）很类似，都是单独对待的。

就拿方才的LSA举例：

LinkID:表示发布路由器接入的网络IP地址是Data:表示发布路由器接入的网络IP地址的掩码是8位的。Type:StubNet表示/8只接入了一个路由器Metric:1表示从发布路由器传送数据包到该网段所需花费为1下面是连接为传输网络的例子：

LinkID:表示发布路由器接口所在网段的DR的接口地址Data:表示发布路由器接口自身在地址Type:TransNet表示该网络接入了多台路由器

Metric:5表示从发布路由器传送数据包到该网段所需花费为5

再来看一下发布的RouterLSA：

Type:RouterLsid:Advrtr:

北京金桥世纪

Lsage:190Len:60Seq#:0x800003d6Chksum:0x2f57Options:(DC)ABRLinkcount:3LinkID:Data:Type:TransNetMetric:9LinkID:Data:Type:TransNetMetric:8LinkID:Data:Type:VirtualMetric:11这里出现了第四类连接类型：虚拟通道：

LinkID:表示的虚拟邻居是Data:表示在与该IP地址关联的接口建立虚连接Type:Virtual

Metric:11表示到邻居的距离为11

1.6NetworkLSA

其次类LSA：NetworkLSA。

例子：由网段/24的DR（IP为）生成的NetworkLSA：TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhereNet1752320x8000000d0SpfTree

生成时间：当网络类型为广播或NBMA时，会选举产生DR。仅当DR与网络上至少一台路由器完全邻接后，才生成NetworkLSA。

用displayOSPF100lsdbnetworkverbose命令可以查看该LSA的详细内容：Type:Net

Lsid:Advrtr:Lsage:1294Len:32

Seq#:0x80000003Chksum:0xd684Options:(DC)

Netmask:

AttachedRouter

北京金桥世纪

AttachedRouter

Netmask指明白网段的掩码，Lsid字段是DR的接口IP地址，Netmask结合Lsid字段就可以计算出网络地址，这个LSA描述的网络是/24。

AttachedRouter：与DR完全邻接的邻居列表，由其OSPF进程的routerid来识别，DR自己也包含在这个列表中。

1.7由一、二类LSA计算域内路由

此时，上area0内的LSA如下：Area:

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhere1Rtr1764600x800000630SpfTree2Rtr515360x800000090SpfTree3Rtr345480x800001590SpfTree4Rtr201600x800001560SpfTree5Net345320x800000030SpfTree6Net201320x800000030SpfTree7Net345320x800000560SpfTree

有了第一、二类LSA就可以来计算area0的域内路由了。每个路由器上area0内的LSDB是一致的，不同的是：它们各自为政、以自己为根计算SPF。这里以为例计算SPF。

1.7.1域内路由计算1：计算最短路径树

为便利最短路径树计算，rfc2328使用了称为节点的数据结构来包装LSA、LSA的发布者以及其它信息。节点中包含四个子项：标识、与节点关联的LSA、下一跳列表、从树根到到本节点的距离。

?节点标识/Vertex(node)ID：

32位数，用于唯一标识节点。有两种节点类型：路由器和网络。对于路由器节点，节点标识就是OSPF路由器标识；对于网络节点，就是网络上DR的IP地址。?一个LSA/AnLSA：

每一个传输节点都有相关联的LSA。对于路由器节点就是RouterLSA；对于传输网络，就是NetworkLSA。即节点标识和对应LSA的LS标识保持一致。?下一跳列表/Listofnexthops：

从树根到该节点最短路径的下一跳列表。由于存在等值多路径，可能会有多条最短路径。每个下一跳都标记有输出接口。

?从树根的距离/Distancefromroot：

从树根到节点最短路径的距离，是最短路径中各组成部分距离值之和（在Router-LSA和Network-LSA中宣告）。

算法中使用到的另外一个重要的数据结构是候选节点列表，该列表存放了当前从树根可达的而又不在最短路径树上的节点。

最短路径树的计算过程大致如下：

北京金桥世纪

计算从树根到候选节点列表中各节点的路径距离；选取路径最短的节点参与最短路径树，并从候选节点列表中删除。再检查新节点的邻接节点，并增加/修改候选列表。如此递归，直至候选列表为空。

首先由一、二类LSA生成节点数据结构，见下表。

表3最短路径树计算所需的节点数据结构

序号标识1234567节点标识类型routerrouterrouterrouter01020304-LSA下一跳列表从树根的距离netowrk05netowrk06netowrk07此时候选节点列表为空：候选列表：空

开始计算最短路径树：

1、以自己为根计算最短路径树，则最先把节点参与树，称其为节点V。

2图2的area0上的最短路径树1

1.1、查看与节点V关联的LSA，遍历LSA中描述的每个连接（这里有三个连接，每一

个连接也是一个节点，这里称其为W节点）：

Type:RouterLsid:Advrtr:Lsage:55Len:60

Seq#:0x8000007aChksum:0x6801

Options:(DC)ASBRLinkcount:3

LinkID:-\\Data:|

－连接1

Type:StubNet|Metric:1-/LinkID:-\\Data:|

－连接2

北京金桥世纪

Type:TransNet|Metric:10-/LinkID:-\\Data:|

－连接3

Type:TransNet|Metric:5-/1.1.1、遍历第一个连接。LinkID:Data:Type:StubNetMetric:1

该连接为存根网络，到存根网络的连接在最短路径计算的其次步中考虑，故再检查下一个连接。

1.1.2、遍历其次个连接。LinkID:Data:Type:TransNetMetric:10

这个连接是传输网络类型的。

?首先计算从树根到这个传输网络（即节点W）的距离D。D是树根到节点V的最短路

径的距离（此时是VV=0），加上节点V、W之间的连接所宣告距离值VW＝10。即：D=VV+VW=0+10=10

?由于W不在候选列表中，将W参与候选列表。

?填写到节点W的下一跳是节点W的Data域：。序号节点标识标识1234567类型routerrouterrouterrouter01020304050607-LSA下一跳列表从树根的距离0netowrknetowrknetowrk10此刻候选列表为：候选列表：

1.1.3、遍历第三个连接。LinkID:Data:Type:TransNetMetric:5

这个节点也是网络节点，计算过程同上。D=VV+VW=0+5=5；W不在候选列表中，则

北京金桥世纪

LSA类型routerrouterrouterrouter01020304050607下一跳列表

将W参与候选列表。设定到W的下一跳值为。序号节点标识标识1234567从树根的距离netowrknetowrknetowrk510此刻候选列表为：候选列表：

1.2、连接遍历完毕后，在候选列表中选择最靠近树根的节点，将其参与最短路径树（同

时在候选列表中删除该节点），5

北京金桥世纪

Data:Type:TransNetMetric:9

LinkID:Data:Type:TransNetMetric:8

LinkID:

Data:Type:VirtualMetric:11

5.1.1、遍历第一个连接。LinkID:Data:Type:TransNetMetric:9

节点已经在最短路径树上，检查LSA中下一个连接。5.1.2、遍历其次个连接。LinkID:Data:Type:TransNetMetric:8

计算从树根到节点W路径的连接状态距离值D=10+VW=10+8=18；大于候选列表中节点W已经有的值，检查下一个连接。5.1.3、遍历第三个连接。LinkID:

Data:Type:VirtualMetric:11

计算从树根到节点W路径的连接状态距离值D=10+VW=10+11=21；W不在候选列表中，将W参与候选列表，并说明到达树根的距离为D。序号节点标识标识1234567类型routerrouterrouterrouter01020304050607-LSA下一跳列表从树根的距离02151051012netowrknetowrknetowrk候选列表：

北京金桥世纪

5.2.在候选列表中选择最靠近树根的节点，将其参与最短路径树（同时在候选列表中删

除该节点）为：7

2/24/24netowrk07200812/24图7的area0上的最短路径树6

候选列表：5.3.计算路由表

DestinationCostTypeNextHopAdvRouterArea/2412Net6.将新参与树的节点/24称为节点V。6.1.查看与节点V关联的LSA：Type:Net

Lsid:Advrtr:Lsage:787Len:32

Seq#:0x80000006Chksum:0x42fbOptions:(DC)

Netmask:AttachedRouterAttachedRouter6.1.1、遍历第一个连接。AttachedRouter

北京金桥世纪

节点已经在最短路径树上，检查LSA中下一个连接。6.1.2、遍历其次个连接。AttachedRouter

节点已经在最短路径树上，检查LSA中下一个连接。

6.2.在候选列表中选择最靠近树根的节点，将其参与最短路径树（同时在候选列表中删

除该节点）为：22/24/24router02210812/243图8的area0上的最短路径树7

候选列表：空6.3.计算路由表

DestinationCostTypeNextHopAdvRouterAreaOptions21Rtr.2(DC)7.候选列表为空，最短路径树（只包含了传输节点）就被构建完成，最短路径树的第

一部分计算完毕。1.7.2域内路由计算2：把存根网络作为叶子参与最短路径树

其次步，把存根网络连接作为叶子参与树。计算过程是：对于每一个可达的路由器节点（称其为V），找到其在LSDB中所关联的Router-LSA。检查其中出现的每个存根网络，作为叶子参与最短路径树。

例如：的Router-LSA中包含由存根网络（称为W节点），计算从存根网络到树根的距离D=VV+VW=0+1=1。D等于从树根到路由器节点的距离（在第一步中计算），加上存根网络的宣告距离。最终把这条路由参与到路由表中。

DestinationCostTypeNextHopAdvRouterArea/81Stub

北京金桥世纪

同理，其它路由器各自计算自己所在区域的域内路由。

1.8SummaryLSA

有了路由表，可以计算第三类和第四类LSA：SummaryLSA。SummaryLSA描述一个IP网络（SummaryNetworkLSA）或者一台ASBR（SummaryASBRLSA）。SummaryLSA所描述的目标是在区域之外，但仍属于这个AS。SummaryLSA是由ABR生成的，依照ABR所在区域，逐个区域计算各区域的SummaryLSA。

设要计算的区域为A，计算过程是：

依照本OSPF进程的当前路由表（包括：①由每个域内的第一、二类LSA计算生成的本域内路由；②由上次计算SummaryLSA时得到的域间路由，若是第一次计算SummaryLSA，则不存在域间路由为）依照一定算法（即：①只有目标类型为网络或ASBR时，才在SummaryLSA中被宣告；②凡是路径本身或者路径的下一跳与areaA有关联的，均不再次发布给areaA）选择向areaA发布的路由。

另外，1、“向骨干区域只宣告区域内路径〞，即计算骨干区域的SummaryLSA时，只计算其余非骨干区域的域内路由，非骨干区域的域间路由不计算

2、“向其他区域要宣告区域内和区域间路径〞，即计算非骨干区域的SummaryLSA时，骨干区域的域内、域间路由都算入内。1.8.1SummaryNetworkLSA

以下是AS的area0内的各ABR上的路由信息：上的路由表：RoutingforNetwork

DestinationCostTypeNextHopAdvRouterArea/810Stub/822SNet/812SNet/2414Net

/249Net/248Net/2421SNet/2411Net

上的路由表：RoutingforNetwork

DestinationCostTypeNextHopAdvRouterArea/87Stub/814Stub

北京金桥世纪

/819SNet/246Net/2416Net

/247Net/2413Net/2418SNet

上的路由表：RoutingforNetwork

DestinationCostTypeNextHopAdvRouterArea/822Stub/834SNet/81Stub/2426Net/2421Net/2420Net/2433SNet/2412Net

依照算法依次遍历各个路由表项（即去掉路径本身或者路径的下一跳与area0有关联的路由表项），可以得到以下SummaryNetworkLSA：

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhere

SNet133280x8000039213UninitializedSNet137280x8000026312UninitializedSNet33280x800003a511UninitializedSNet133280x8000005414UninitializedSNet137280x800000311Uninitialized

使用displayospf100lsdbsummaryverbose命令可查看SummaryLSA的详细信息。例如：

Type:SumNetLsid:Advrtr:Lsage:16Len:28

Seq#:0x8000000aChksum:0x91c3

Options:(DC)(NonDN)Netmask:Tos0metric:14

北京金桥世纪

1.8.2SummaryASBRLSA

AS中各路由器发布的RouterLSA形成的路由表项如下：DestinationTypeAdvRouterAreaOptionsRtr（DC）ASBRRtr(DC)ABRASBRRtr(DC)ABRRtr(DC)ABR

Rtr(DC)ABRVirtualRtr(DC)ABRVirtualRtr(DC)ASBRRtr(DC)ABRASBR

依照算法依次遍历各个路由表项（即选取目标类型为ASBR的路由表项），可以得到以下SummaryNetworkLSA：

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhere

ASB676280x8000000f21UninitializedASB674280x800000139SumAsbListASB676280x8000000c20UninitializedASB674280x800000028SumAsbList

使用displayospf100lsdbasb命令可查看SummaryLSA的详细信息的。例如：

Type:SumASBLsid:Advrtr:Lsage:682Len:28

Seq#:0x8000000fChksum:0xc543Options:(DC)Tos0metric:21

1.9AS-external-LSA

AS-external-LSA描述了到达AS外部目标的路径，LS标识被设为目标网络的IP地址。AS-external-LSA是由ASBR所生成。不管是从其他路由协议（如BGP），或通过配置信息得到，ASBR为每条外部路径生成单独的一个AS-external-LSA。AS-external-LSA是唯一在整个AS中洪泛的LSA，因此AS-external-LSA在LSDB中不属于任何区域。

北京金桥世纪

ASExternalDatabase:

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhereASE65360x800000021UninitializedASE1465360x800000a11AseList

使用displayospf100lsdbaseverbose命令可查看AS-external-LSA的详细信息的：Type:ASELsid:Advrtr:Lsage:81Len:36

Seq#:0x80000002Chksum:0x7460Options:(DC)

Netmask:Tos0metric:1Etype:2

ForwardingAddress:Tag:1

1.10计算区域外部路由

1.10.1根据SummaryLSA计算区域外部路由

遍历SummaryLSA可以计算区域间路径。假使路由器接入了多个区域，则仅检查骨干区域的SummaryLSA。

例如：此时area0内的SummaryLSA如下：

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhere

SNet306280x8000001314UninitializedSNet306280x800000fa13UninitializedSNet611280x800000ab12UninitializedSNet426280x800000bd11UninitializedSNet611280x800000a61Uninitialized

依次遍历以上所列的SummaryLSA：Type:SumNetLsid:Advrtr:Lsage:687Len:28

Seq#:0x80000013Chksum:0x7fcc

Options:(DC)(NonDN)

北京金桥世纪

Netmask:Tos0metric:14

在area0内找到从Summary-LSA到该LSA的发布者的cost=5，再加上LSA中的metrix=14，就是区域间的metrix=5+14=19。参与路由表：

DestinationCostTypeNextHopAdvRouterArea/819SNet

同理将/8参与路由表：

DestinationCostTypeNextHopAdvRouterArea/822SNet

再考虑其余三条LSA的目的路由在路由表中已存在，终止遍历。1.10.2根据AS-external-LSA计算AS外部路由

通过检查AS-external-LSA可以计算AS外部路径。此时的LSDB内的AS-external-LSA如下：

TypeLinkStateIDAdvRouterAgeLenSequenceMetricWhereASE1678360x800000051UninitializedASE542360x800000051AseList遍历这些LSA：1、

Type:ASELsid:Advrtr:Lsage:61Len:36

Seq#:0x80000006Chksum:0x6c64Options:(DC)

Netmask:Tos0metric:1Etype:2

ForwardingAddress:Tag:1

?在路由表中查找生成该LSA的ASBR：，找到说明可达；

?再在路由表中查找转发地址，找到，则把参与路由表中，设定下一

跳为转发地址的下一跳列表，宣告路由器为ASBR。因外部路径的类型为2，则路径类型为类型2外部路径，即：

DestinationCostTypeTagNextHopAdvRouter/81212、对于

北京金桥世纪

Type:ASE

Lsid:Advrtr:Lsage:675Len:36

Seq#:0x80000005Chksum:0x2672Options:(DC)

Netmask:Tos0metric:1Etype:2

ForwardingAddress:Tag:1

此LSA是由计算路由器自己生成的，不考虑。遍历终止。

至此，area0的路由全部计算完毕，其路由表如下：OSPFProcess100withRouterIDRoutingTables

RoutingforRouter

DestinationCostTypeNextHopAdvRouterAreaOptions

5Rtr(DC)ABRASBR5Rtr(DC)ABR21Rtr(DC)ABR

DestinationCostTypeNextHopAdvRouterArea/245Net/2410Net/2412Net/2418SNet/2421SNet/81Stub/822SNet/819SNet

RoutingforASEs

DestinationCostTypeTagNextHopAdvRouter/8121

注意：实际的路由计算过程还包括对LSA的有效性检查；存在虚连接时，还有对路由的优化等等。

北京金桥世纪

2FAQ

2.1初学OSPF，看哪些文章好？

从我学习OSPF的过程来看，对OSPF不熟悉的同学首先推荐：

1.HCNP培训教材（OSPF部分），比较详细的介绍了OSPF协议，是初学者不错的

选择。

2.经典多媒体课件OSPF协议，李大师经典课程，不容错过！！有了一定的基础后，可以看我司的集ospf高手之大成的名篇：3.网络之路-001(2023-07-08).pdf

要是觉得在公司还没看够的话，还可以拿到家里去看！等等，有人马上指出：“这是严重违反信息安全！〞，别急，其实我司对外网站上也有这篇文章的，地址是：

.->服务支持->技术专题->路由器->网络之路001期-OSPF专题探讨

4.rfc2328

以上文章都可以在tech网站上找到。

2.2什么是接口状态，什么是邻居状态，它们之间有什么关系？

图9是邻居状态机转换图，邻居状态有七种，分别是：Down、Init、2Way、ExStart、ExChange、Loading、Full、Attempt。

++|Down|++|\\|\\Start|\\++Hello|+>|Attempt|Received|++||

++|2-Way|++++

图9邻居状态机转换图

状态Down说明a.在DeadInterval时间内未接收到hello报文,相应邻居状态变为down

北京金桥世纪

b.对于非NBMA网络,不向处于down状态的邻居发送hello报文;对于NBMA网络,以PollInterval为时间间隔(4倍DeadInterval)向处于down状态的邻居发送hello报文c.邻居状态迁Inita.在DeadInterval时间内收到邻居的hello报文,但自己尚未出现在对端hello报文的neighbor字段中b.达到或超过init状态的路由器必需在hello报文的相应字段包含自己所见所有邻居的routerid.2Waya.在收到的邻居的hello报文的neighbor字段中发现自己的routerid，则邻居状态达到2-wayb.在处于init状态时收到邻居发送的DD报文,则相应邻居也达到2-way状态（备注：广播网络和NBMA网络的DRother之间相应邻居为稳定在2-way状态。）Full广播网络和NBMA网络的DR/BDR和其他路由器之间建立邻接关系，相应邻居为full状态。点到点、点到多点网络的邻居之间应达到full状态（备注：完成数据库同步后达到的邻居状态，检查相邻邻居在相应区域中的LSA的校验和之和是否相等。相等表示完成数据库同步）Attempta.当去往NBMA邻居的接口被激活,并且邻居有资格参与DR选举或者路由器成为DR/BDR,而邻居没有资格参与DR选举时邻居状态为attemptb.处于attempt状态的路由器hello报文的发送间隔为helloInterval

displayospf100peer命令显示的就是当前OSPF进程100的邻居状态，其中的State：

Exstart字段指示其邻居当前的状态为：Exstart。

图10OSPF的邻居状态截图

注意：只有在全部满足以下条件时路由器才会形成邻居关系：?网络类型为Brodcast、nbma、虚连接?路由器为DR/BDR?对端为DR/BDR

否则两个路由器只是停留在2Way的关系。

OSPF大致分网络为两种：广播和非广播。广播有广播、nbma，非广播即p2p、p2mp

图11是rfc2328中的OSPF接口状态机转换图。接口状态有五种，即：downLoopbackwaitingDRBDRDROther。

++UnloopInd++|Down|++|LoopInd||InterfaceUp

++|++|Waiting||Point-to-point|++++|

WaitTimer|BackupSeen

||

|NeighborChange

+++-+|DROther|++>+-+|DR|+--+

图11接口状态机转换图

注意：并不是所有的状况下都会出现DR、BDR、DROther这三种状态的。当网络类型为Broadcast、NBMA时，才会选举；当网络类型为P2P、P2MP时，不选举DR、BDR，自然不会出现这些状态。

displayospf100brief命令显示的就是当前ospf进程的概要信息，其中某区域下的某接口中的State：DROther字段指示的是该接口当前的状态为DROther。

图12OSPF的接口状态截图

接口和邻居的关系如何？其实这个关系很简单：关系：邻居建立在接口之上：

北京金桥世纪

1、Init:路由器收到了hello，但自身没有出现的hello包中(非双向通讯)2、