OSPF的灵魂—SPF算法

闫辉

SPF算法（最短路径优先算法）也叫Dijksrta算法，是荷兰计算机科学家迪杰斯特拉1956年发现的算法，并于三年后在期刊上发表。使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

                               
登录/注册后可看大图

戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。

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

OSPF正是使用SPF算法来计算最短路径树。它使用“Cost”作为路由度量。使用链路状态数据库（LSDB）用来保存当前网络拓扑结构，路由器上属于同一区域的链路状态数据库是相同的（属于多个区域的路由器会为每个区域维护一份链路状态数据库）。

                               
登录/注册后可看大图

OSPF根据区域概念，每台路由器都会分不同区域计算属于自己的SPF树形结构，需要分别计算树干、树枝和树叶部分。

1、树干：互联路由器骨干链路，其网络类型分为Transnet、P2P和Virtual。

2、树枝：非路由器所在网络，可以理解为终端设备所在的网络或环回口。

3、树叶：不靠拓扑计算的路由，用3类LSA或5类LSA传递的区域间和外部路由。

首先，路由器以自身为树根出发，先进行树干部分的计算。只计算出向路径，并同时计算度量值。如果有多条树干可以计算，则先计算度量值最小的，直到所有链路计算完毕。要注意如果网络为Transnet网络，则计算为Dother连接DR的网段，记作伪节点。如果网络为P2P网络，则分别计算路由器和网络部分。

                               
登录/注册后可看大图

然后进行树枝部分的计算，将Stub连接挂在节点上，只计算出向度量值。P2P需要在骨干链路基础上添加单独的Stub连接。

                               
登录/注册后可看大图

最后计算树叶部分，3类5类（加4类）LSA挂在ABR和ASBR（先确定关联5类LSA的ABR）之上即可。

最后

太阁老师的个人微信

添加太阁老师个人微信领取：太阁免费视频资料、NA综合实验配置文件拓扑图及模拟器、太阁独家实验手册、网工必读书籍等   

                               
登录/注册后可看大图