【计算机网络】十九. 网络层--内部网关路由协议之OSPF协议
内部网关路由协议之OSPF协议
目录
注：转载请标明原文出处链接：https://lvxiaowen.blog.csdn.net/article/details/103926963
一、Dijkstra（迪杰斯特拉）算法
Dijkstra算法是著名的图算法Dijkstra（迪杰斯特拉）算法，解决有权图从一个节点到其他节点的最短路径问题， “以起始点为中心，向外层层扩展”。
1. 初始化两个集合(S, U)（S为只有初始顶点点A的集合，U为其他顶点集合）
2. 如果U不为空， 对U集合顶点进行距离的排序，并取出距离A最近的一个顶点D i. 将顶点D的纳入S集合
ii.更新通过顶点D到达U集合所有点的距离（如果距离更小则更新，否则不更新）
iii. 重复2步骤
3. 直到U集合为空，算法完成
二、OSPF协议
(1) 链路状态（LS）协议
LS协议向所有的路由器发送消息：一传十、十传百。
RIP协议只和相邻的路由器交换信息。
LS协议发送的消息描述该路由器与相邻路由器的链路状态。
LS协议只有链路状态发生变化时，才发送更新信息。
RIP协议每隔30s交换路由信息 。
(2) 五种消息类型
问候消息（Hello）；
链路状态数据库描述信息；
链路状态请求信息；
链路状态更新信息；
链路状态确认信息。
(3) OSPF协议的过程
OSPF协议(Open Shortest Path First：开放最短路径优先)，核心是Dijkstra算法。
三、RIP协议与OSPF协议对比
最短路径优先协议主要特点包括：
①OSPF 最主要的特征是使用分布式链路状态协议( Link StateProtocol)，而RIP 使用的是距离向量协议。
②OSPF协议要求路由器发送的信息是本路由器与哪些路由器相邻，以及链路状态的度量(metric)。
③OSPF协议要求当链路状态发生变化时用洪泛法（flooding）向所有路由器发送此信息，而RIP仅向自己相邻的几个路由器交换路由信息。
④由于执行OSPF 协议的路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库(Link State Database)，这个数据库实际上就是全网的拓扑结构图，并且在全网范围内是保持一致的。
⑤为了适应规模很大的网络，并使更新过程收敛得很快，OSPF协议将一个自治系统再划分为若干个更小的范围，叫做区域。
参考资料：
[1] https://coding.imooc.com/class/355.html
[2] https://www.shangxueba.cn/60943.html