[网络协议]路由选择算法学习笔记

1.路由选择算法的分类：

1）静态路由算法（又称非自适应路由算法）

2）动态路由算法（又称自适应路由算法）：常用的动态路由算法可分为两类——距离-向量路由算法和链路状态路由算法。

2.静态路由算法：由网络管理员手工配置路由信息。当网络的拓扑结构h或链路的状态发生变化时，网络管理员需要手工去修改路由表中的静态路由信息。大型和复杂的网络环境通常不宜采用静态路由。一方面，网络管理员难以全面了解整个网络的拓扑结构；另一方面，当网络的拓扑结构和链路状态发生变化时，路由器中的静态路由信息需要大范围调整，这一工作的难度和复杂程度非常高。

静态路由算法的优点是简便、可靠，在负荷稳定、拓扑变化不大的网络中运行效果好，因此仍广泛用于高度安全的军事系统和较小的商业网络。

动态路由算法能改善网络的性能并有助于流量控制；但算法复杂，会增加网络的负担，有时因对动态变化的反应太快而引起振荡，或反应太慢而影响网络路由的一致性。

3.距离-向量路由算法（RIP）

在距离-向量路由算法中，所有结点都定期地将它们的整个路由选择b表传送给与之直接相邻的结点。这种路由选择表包含：1.每条路径的目的地（另一结点）；2.路径的代价（也称距离）。

在这种算法中，所有结点都必须参与距离向量交换，以保证路由的有效性和一致性，也就是说，所有的结点都监听从其他结点传来的路由选择更新信息，并在下列情况下更新它们的路由选择表。

1.被通告一条新的路由，该路由在本结点的路由表中不存在，此时本地系统加入这条新的路由；

2.发来的路由信息中有一条到达某个目的地的路由，该路由与当前使用的路由相比，有较短的距离。此种情况下，就用经过发送路由信息的结点的新路由替换路由表中到达那个目的地的现有路由。

4.链路状态路由算法（OSPF）

链路状态路由算法要求每个参与该算法的结点都具有完全的网络拓扑信息，它们执行下述两项任务：

1.主动测试所有邻接结点的状态。两个共享一条链接的结点是相邻结点，它们连接到同一条链路，或者连接到t同一广播型物理网络；

2.定期地将链路状态传播给所有其他结点。

每当链路状态报文到达时，路由结点便使用这些状态信息去更新自己的网络拓扑和状态“视野图”，一旦链路状态发生变化，结点就对更新的网络图利用Dijsktra最短路径算法重新计算路由，从单一的源出发计算到达所有目的结点的最短路径。