OSPF 算法

OSPF在区域内会产生俩类LSA：

路由器以自己为树根构建最短路径树 ，
这里的最短路径树按两步形成：

区域内部OSPF对网络是通过Router LSA ，Network LSA来描述网络的，最终路由器收到LSA
构建出LSDB。

LSDB通过描述一个有向线段图来描述网络拓扑结构，该有向图的端点有三种类型：路由器节
点，Stub网段和Transit网段。

Router LSA使用Link ID，Data，Type和Metric描述一条链路

类型有四种

Stub网段表示该网段只有数据入口，例如一个Loopback接口就是一个Stub网段。
此胶片描述了路由器节点和Stub网段的表示方式。
Cost表示从一个端点到另一个端点的开销，该参数可以在OSPF接口上配置，表示数据离开该
接口（出接口）的开销。

Transit网段有能力转发既不是本网段产生的，也不以本网段做为目的地的数据。
有至少两台路由器的广播型网段或NBMA网段就是一种Transit网段。
从路由器到所连Transit网段的开销值就是连接到这个网段的接口所配置的开销值。
从一个Transit网段到连接到这个网段的路由器的开销为0。（称为伪节点）

在描述点到点接口的Router-LSA中：

1. 通告一个到邻居路由器的点到点链接，Link ID设置为对端的Router ID，Data设置为本地
   接口的IP地址；
2. 通告一个到该点到点网段的Stub连接，Link ID设置为该点到点网段的网络号，Data设置
   为该点到点网段的网络掩码；
3. 上述两个连接的Cost值均为该点到点接口上的Cost值。
   
   LSDB描述两接口处于不同网段的点到点网段的规则如下：
   两台路由器经由两条有向线段直接相连，每个方向一条。
   两个接口的网段被表示成Stub网段。
   每个路由器通告一个Stub连接到该路由器所连的网段。
   

LSDB描述两接口处于同一网段的点到点网段的规则如下：
两台路由器经由两条有向线段直接相连，每个方向一条。
连接两个接口的网段被表示成Stub网段。
两个路由器同时通告Stub连接到该PPP网段。

在描述广播型或NBMA型接口的Router-LSA中：

1. 如果接口状态是Waiting，或者该网段上只有一个运行OSPF的路由器，或者该网段上没有
   DR，则通告一个通往该网段的Stub链接，Link ID设置为该网段的IP网络号，Link Data设置
   为该网段的网络掩码；
   其他情况下，通告一个通往该网段的Transit连接，Link ID设置为DR的接口IP地址，Link
   Data设置为本地接口的IP地址。
2. 连接的开销值为接口的开销。
   
   

在描述广播型网段或者NBMA网段的Network-LSA中：
Link State ID设置为DR的接口IP地址。
Net mask设置为该网段的网络掩码。
Link State ID和Net mask做与运算，即可得出该网段的IP网络号。
在该LSA中，还包含一个连接到该网段的路由器列表。
从一个Transit网段到所连接的路由器的连接没有开销。

计算过程

根据上文描述上图拓扑在LSA传递完毕后生成有向图

接下来计算分为俩个阶段
第一阶段 计算Transit节点，忽略Stub节点，生成一个最短路径树
第二阶段 只计算Stub节点，将Stub网段挂到最短路径树上去

计算过程中首先初始化最短路径树，RTA将自己做为根节点添加到最短路径树上

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

将候选列表中到根端点开销最小的端点移到最短路径树上

当有新节点添加到最短路径树上的时候，则检查LS ID为新节点的link-idID的LSA，本例中检查
LS ID为2.2.2.2的LSA。
如果LSA中所描述的连接的Link ID在最短路径树上已经存在，则忽略该连接。本例中，Link
ID为1.1.1.1的连接被忽略，只有10.3.1.1的连接被添加到候选列表中。到根端点的开销设置
分区 HCIP 的第 43 页
ID为1.1.1.1的连接被忽略，只有10.3.1.1的连接被添加到候选列表中。到根端点的开销设置
为此连接的Metric值（本例中此连接的Metric值为1）与父端点（本例中此连接的父端点为
2.2.2.2）到根端点的开销（本例中此开销值为48）之和。

将候选列表中到根端点的开销最小的端点移动到最短路径树上，本例中，将10.3.1.1移到最
短路径树上。

检查LS ID为最新添加节点的端点ID的LSA，本例中检查LS ID为10.3.1.1的LSA。
在所描述的连接中，忽略2.2.2.2，将3.3.3.3和4.4.4.4添加到候选列表中。从Transit网段
到所连路由器的开销为0。
如果在候选列表中出现两个端点ID一样但是到根端点的开销不一样的端点，则删除到根端点
的开销大的端点。

将候选列表中到根端点的开销最小的端点移动到最短路径树上，本例中，将3.3.3.3移到最短
路径树上。

检查LS ID为最新添加节点的端点ID的LSA，本例中检查LS ID为3.3.3.3的LSA。
本例中，没有新端点被添加到候选列表中。
在这里插入图片描述

将候选列表中到根端点的开销最小的端点移动到最短路径树上，本例中，将4.4.4.4移到最短
路径树上。

检查LS ID为最新添加节点的端点ID的LSA，本例中检查LS ID为4.4.4.4的LSA。
本例中，没有新端点被添加到候选列表中。
如果在此时候选列表为空，则计算最短路径树的第一阶段结束。

检查每个路由器端点的Router-LSA，计算Stub网段。
本例中，首先检查RTA的Router-LSA，共有三个Stub网段。

本文由 在线网速测试 整理编辑，转载请注明出处，原文链接：https://www.wangsu123.cn/news/18906.html。