路由选择算法

路由选择算法是为了选出从一个点发出的数据报，该如何经过各个路由器，以最小的成本或最快的速度到达目的ip的一种算法，可以理解为图中的最短路径问题。

一般而言，路由选择算法的一种分类方式是根据该算法是集中式还是分散式来划分。

集中式还是分散式

集中式路由选择算法

该算法以所有节点的连通性以及所有链路的开销为输入，这就要求算法在开始之前获得这些信息。该算法可以在一个集中的控制器或者在每台路由器的路由选择组件中重复进行。

集中式算法具有关于连通性和链路开销方面的完整信息。具有全局状态信息的算法常被称作链路状态（Link State, LS）算法, 因为该算法必须知道网络中每条链路的开销。

分散式路由选择算法

该算法中，路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。 相反，每个节点仅有与其直接相连链路的开销知识即可开始工作。

然后，通过迭代计算过程以及与相邻节点的信息交换，一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径。

静态的还是动态

路由选择算法的第二种分类是基于算法是静态的还是动态的进行分类。

在静态路由选择算法（static routing algorithm）中，路由随时间的变化非常缓慢，通常是人工进行调整。

动态路由选择算法（dynamic routing algorithm） 随着网络流量负载或拓扑发生变化而改变路由选择路径。一个动态算法可周期性地运行或 直接响应拓扑或链路开销的变化而运行。虽然动态算法易于对网络的变化做岀反应，但也 更容易受诸如路由选择循环、路由振荡之类问题的影响。

负载敏感的还是负载迟钝

负载敏感算法（load-sensitive algorithm）中，链路开销会动态地变化以反映出底层链路的当前拥塞水平。如果当前拥塞的一条链路与高开销相联系，则路由选择算法趋向于绕开该 拥塞链路来选择路由。

负载迟钝的并不会选择性的避开。

参考

《计算机网络自顶向下》