OSPF动态路由协议笔记之(四) : 域内路由和计算最短路径

OSPF动态路由协议笔记之(四) : 域内路由和计算最短路径

　　本节笔记，主要介绍OSPF域内路由的基本知识，内容涵盖如何使用一类LSA（Router-LSA）和二类LSA（Network-LSA）描述拓扑信息和路由信息，以及如何使用这两类LSA通过SPF算法计算域内路由，构建最短路径树。

　　第一类LSA：Router-LSA

　　每台OSPF路由器使用一条Router-LSA描述本区域内的链路状态信息。

　　LSA头部的三个字段含义如下：

　　① Type ：LSA类型，Router-LSA是一类LSA。

　　② LS id ：链路状态ID。

　　③ Adv rtr ：产生此Router-LSA的路由器Router ID。

　　（1）Router-LSA描述P2P网络

　　一条Router-LSA可以描述多条链接，每条链接描述信息由Link ID，Data，Link Type和Metric组成。

　　命令： display ospf lsdb router self-originate 

 　　

　　其关键字含义如下：

　　① Type ：链接类型（并非OSPF定义的四种网络类型），Router LSA描述的链接类型主要有：

　　l Point-to-Point（P2P）：描述一个从本路由器到邻居路由器之间的点到点链接，属于拓扑信息。

　　l TransNet：描述一个从本路由器到一个Transit网段（例如MA网段或者NBMA网段）的链接，属于拓扑信息。

　　l StubNet：描述一个从本路由器到一个Stub网段（例如Loopback接口）的链接，属于路由信息。

　　② Link ID ：此链接的对端标识，不同链接类型的Link ID表示的意义也不同。

　　③ Data ：用于描述此链接的附加信息，不同的链接类型所描述的信息也不同。

　　④ Metric ：描述此链接的开销。

　　（2）Router-LSA描述MA网络或NBMA网络

　　如下图所示，RTB、RTC、RTE之间通过以太链路互连，链接类型（Link Type）为TransNet。以RTC产生的LSA为例，Link ID为DR的接口IP地址（10.1.235.2），Data为本地路由器连接此MA网络的接口IP地址（10.1.235.3），Link Type为TransNet，Metric表示到达DR的开销值。

 　　

　　TransNet描述的链接中仅包括与DR的连接关系及开销，没有网络号/掩码及共享链路上其他路由器的任何信息。

 　　

　　Tips：总结。当链接类型Link Type有所不同时，其Link ID和Data分别代表什么：

Link Type	场景	Link ID含义	Data含义
P-2-P	点对点链接	邻居路由器Router ID	宣告该Router LSA的路由器接口的IP地址
TransNet	MA或NBMA网段	DR的接口IP地址	宣告该Router LSA的路由器接口的IP地址
StubNet	Loopback接口	该Stub网络的IP地址	该Stub网络的网络掩码

 

 

　　第二类LSA：Network-LSA

　　MA共享网段或NBMA共享网段中的网络号/掩码及路由器间的链接关系，通过Network-LSA来呈现。

　　命令： display ospf lsdb network self-originate 

　　

 

　　在Network-LSA中关键字含义如下：

　　l Type：LSA类型，Network-LSA是二类LSA。

　　l LS id：DR的接口IP地址。

　　l Adv rtr：产生此Network-LSA的路由器Router ID，在该例子中就是DR的Router ID。

　　l Net mask：该网段的网络掩码。

　　l Attached Router：连接到该网段的路由器列表，呈现了此网段的拓扑信息。

　　基于上述字段表达的信息，Ls id和Net mask做与运算，即可得出该网段的IP网络号，另外，从DR路由器到其所连接的路由器的开销为0。

　　从Attached Router部分可以看出，2.2.2.2、3.3.3.3、5.5.5.5共同连接到该共享MA网段中，DR路由器为2.2.2.2，网络号10.1.235.0，掩码255.255.255.0。

　　OSPF区域LSDB

　　如下图所示，五台路由器互连并运行OSPF协议。以RTA的LSDB为例，其中包括了五个路由器产生的Router-LSA，以及两个广播型网络中产生的Network-LSA。

　　命令： display ospf lsdb 

 　　

　　SPF算法

　　在一类LSA和二类LSA中，包括了拓扑信息和路由信息。OSPF路由协议通过使用SPF（最短路径优先）算法，计算到达每个路由器的最短路径。

　　SPF算法分为两个阶段：构建SPF树和计算最优路由。OSPF将依据SPF算法和各类LSA进行最短路径树的计算。

　　阶段 1：构建SPF树。

　　根据Router-LSA中的Point to Point，TransNet（拓扑信息）和Network-LSA中的拓扑信息，构建SPF树干。

　　阶段 2：计算最优路由

　　基于SPF树干和Router-LSA中的Stub（路由信息）、Network- LSA中的路由信息，计算最优路由。

 

　　阶段一：构建SPF树

　　接下来将会分步骤介绍SPF算法计算最短路径：

　　Step 1：OSPF路由器将分别以自身为根节点计算最短路径树。

　　以RTA为例，计算过程如下：

　　RTA将自己添加到最短路径树的树根位置，然后检查自己生成的Router-LSA，对于该LSA中所描述的每一个连接，如果不是一个Stub连接，就把该连接添加到候选列表中，分节点的候选列表为Link ID，对应的候选总开销为本LSA中描述的Metric值和父节点到达根节点开销之和。

 　　

　　根节点RTA的Router-LSA中存在TransNet中Link ID为10.1.12.2 Metric=1和P-2-P中Link ID为3.3.3.3 Metric=48的两个连接，被添加进候选列表中。

　　RTA将候选列表中候选总开销最小的节点10.1.12.2移到最短路径树上，并从候选列表中删除。

 

　　Step 2：DR被加入到SPF中，接下来检查Ls id为10.1.12.2的Network-LSA。如果LSA中所描述的分节点在最短路径树上已经存在，则忽略该分节点。

 　　

　　如上图所示，在Attached Router部分：

　　节点1.1.1.1被忽略，因为1.1.1.1已经在最短路径树上。

　　将节点2.2.2.2，Metric=0，父节点到根节点的开销为1，所以候选总开销为1，加入候选列表。

　　候选节点列表中有两个候选节点，选择候选总开销最小的节点2.2.2.2加入最短路径树并从候选列表中删除。

 

　　Step 3：节点2.2.2.2新添加进最短路径树上，此时继续检查Ls id为2.2.2.2的Router-LSA：

 　　

　　第一个TransNet连接中，Link ID为10.1.12.2，此节点已经在最短路径树上，忽略。

　　第二个TransNet连接中，Link ID为10.1.235.2，Metric=1，父节点到根节点的开销为1，候选总开销为2，加入候选列表。

　　第三个P-2-P连接中，Link ID为4.4.4.4，Metric=48，父节点到根节点的开销为1，候选总开销为49，加入候选列表。

　　候选节点列表中有三个候选节点，选择候选总开销最小的节点10.1.235.2加入最短路径树并从候选列表中删除。

 

　　Step 4：DR被加入到SPF中，接下来检查Ls id为10.1.235.2的Network-LSA。

 　　

　　如上图所示，在Attached Router部分：

　　节点2.2.2.2被忽略，因为2.2.2.2已经在最短路径树上。

　　将节点3.3.3.3，Metric=0，父节点到根节点的开销为2，候选总开销为2，加入候选列表。（如果在候选列表中出现两个节点ID一样但是到根节点的开销不一样的节点，则删除到根节点的开销大的节点。所以删除节点3.3.3.3 累计开销为48的候选项)。

　　将节点5.5.5.5，Metric=0，父节点到根节点的开销为2，候选总开销为2，加入候选列表。

　　候选节点列表中有三个候选节点，选择候选总开销最小的节点3.3.3.3和5.5.5.5加入最短路径树并从候选列表中删除。

 

　　Step 5：节点3.3.3.3和5.5.5.5新添加进最短路径树上，此时继续检查Ls id分别为3.3.3.3和5.5.5.5的Router-LSA。

 　　

　　① Ls id为3.3.3.3的LSA：

　　Link ID为10.1.235.2的节点已经在最短路径树上，忽略。

　　Link ID为1.1.1.1的节点已经在最短路径树上，忽略。

 　　

　　② Ls id为5.5.5.5的LSA：

　　Link ID为10.1.235.2的节点已经在最短路径树上，忽略。

　　Link ID为4.4.4.4的P-2-P连接，Metric=48，父节点到根节点的开销为2，候选总开销为50。因为节点4.4.4.4已经在候选列表中出现，且候选总开销为49。49<50，所以子节点4.4.4.4的父节点选择2.2.2.2。

 　　

　　至此，再通过命令display ospf lsdb router 4.4.4.4发现，LSA中的连接所描述的相邻节点都已经添加到了SPF树中。

　　此时候选列表为空，完成SPF计算，其中10.1.12.2和10.1.235.2是虚节点（DR）。

 

 

　　阶段二：计算最优路由

　　从根节点开始依次添加各节点LSA中的路由信息，添加顺序为各节点加入SPF树的顺序。

 　　

　　第二阶段根据Router LSA中的Stub、Network LSA中的路由信息，完成最优路由的计算。

　　从根节点开始，依次添加LSA中的路由信息（添加顺序按照每个节点加入SPF树的顺序）：

　　① 1.1.1.1（RTA）的Router LSA中，共1个Stub连接，网络号/掩码10.1.13.0/24，Metric=48；

　　② 10.1.12.2（DR）的Network LSA中，网络号/掩码10.1.12.0/24，Metric=1+0=1；

　　③ 2.2.2.2（RTB）的Router LSA中，共1个Stub连接，网络号/掩码10.1.24.0/24，Metric=1+0+48=49；

　　④ 10.1.235.2（DR）的Network LSA中，网络号/掩码10.1.235.0/24，Metric=1+0+1=2；

　　⑤ 3.3.3.3（RTC）的Router LSA中，共1个Stub连接，网络号/掩码10.1.13.0/24，已在RTA上，忽略；

　　⑥ 5.5.5.5（RTE）的Router LSA中，共1个Stub连接，网络号/掩码10.1.45.0/24，Metric=1+0+0+1+48=50；

　　⑦ 4.4.4.4（RTD）的Router LSA中，共2个Stub连接，网络号/掩码10.1.24.0/24，已在RTB上，忽略；网络号/掩码10.1.45.0/24，已在RTE上，忽略。

　　查看OSPF路由表

　　经历上述两个阶段的计算，RTA生成的OSPF路由如下图所示。

　　

　　经过OSPF优选后的路由并不一定会安装进系统路由表，因为路由器还可以通过其他协议获得路由，通过不同方式获得的路由需要进行优先级比较。

　　Q：Router-LSA中主要包含哪几种链路类型？

　　A：P2P、TransNet、StubNet、vlink。

 

　　Q：经过SPF算法计算后，被认为是最优的OSPF路由是否一定会被放入路由器的路由表中？

　　A：不一定，路由器可能通过多种路由协议获得同一路由前缀的路由信息，还需要通过路由优先级比较确定通过哪个路由协议获得的路由会放入路由表。

 

　　下一节笔记，将会介绍OSPF路由区域间传递过程，理解区域间防环机制，以及掌握虚连接的配置过程。