计算机网络原理（15）—— 路由算法层级、RIP协议、OSPF和BGP协议

一、路由算法分类

路由算法

• 路由协议用于识别到达目标网络的最优传输路径。
  • 转发表则规定了当前路由器对数据包的具体处理方式。
  • 网络模型的构建涉及图结构、成本参数以及最低成本路径的计算。

1. 静态路由 vs 动态路由

静态路由:

人工设定

路由信息更新速度较缓

具有较高的优先级

动态路由:

• 路由信息更新迅速
  • 实施周期性更新
  • 能够对链路成本或网络结构的变动作出即时反应

2. 全局信息vs分散信息

全局信息

所有路由器均具备完整的网络拓扑结构及链路费用数据

例如，链路状态（LS）路由算法即属于此类

分散式信息：

路由器仅了解与其直接相连的相邻节点及对应的链路费用

通过相邻节点间的信息交互与计算迭代实现信息传递与处理

例如，距离向量（DV）路由算法即为典型代表

二、常用的路由算法

1. 链路状态(LS)路由算法——Dijkstra算法（全局信息）

所有网络节点（路由器）均具备完整的网络拓扑结构及链路费用信息

* 依靠“链路状态广播”机制实现信息同步  
* 每个节点所存储的数据内容保持一致  

确定从某一特定节点（即“源”节点）至其余所有节点的最短路径

* 由此生成该节点对应的路由转发表