网络：简述路由算法之动态路由算法

---

在计算机网络中，路由器的一个很重要责任就是要在端对端的节点中找出一条最佳路径出来，通过自己与相邻节点之间的信息，来计算出从自己位置到目的节点之间的最佳线路，这种算法我们可以理解为路由算法。

路由的模式又主要分为「静态路由」和「动态路由」。静态路由协议是由网络管理员手动输入配置的，适用于小型的不太复杂的网络环境中，或者有特定需求的网络场景中。而动态路由协议是现代计算机网络中最为常用的一种方式。动态路由算法能够根据网络拓扑结构去适应流量的变化。

动态路由算法大致可以分为两类：

1. 距离矢量路由算法
2. 链路状态路由算法

一、距离矢量路由算法

距离矢量路由算法（Distance Vector Routing），它是网络上最早使用的动态路由算法，也称为Bellman-Ford或者Ford-Fulkerson算法。基于这类算法实现的协议有：RIP、BGP等。

如图，这类算法的基本思路是：网络中每一个路由器都要维护一张 矢量表 ，这个矢量表 中的每一行都记录了从当前位置能到达的目标路由器的最佳出口（接口）和距离（跳数）。

每隔一段时间当前路由器会向所有的邻居节点发送自己的这个表，同时它也会接收每个邻居发来的它们的表。并会将邻居的表和自己的表做一个对比更新。

比如当前 路由器X 离 邻居Y路由器 的距离是m，此时收到 邻居Y 发来的表中写到了“ 邻居Y离路由器Z的距离是n ”，那 当前路由器X 就知道它离 路由器Z 的距离可能就是 m+n 了，如图：

就这样继续类推，要不了多久，每个路由器就可以将网络中所有路由节点和子网线路都汇聚起来了。这样的话，每个路由器只需要查找自己的表就可以很容易的知道到达目的地的最佳出口（接口）是哪个了。

当然，当网络结构发生变化的时候，各个路由器中的矢量表也会随之动态更新。

「距离矢量路由算法」，“距离”这个词就基本表明了这个算法是通过 距离（跳数/时间）来度量2个路由网络之间的线路的，而“矢量”这个词，可以看出线路是有方向性的，且路由表中只记录了数据包去往目的地应该走哪个出口方向，并不会记录到达目的地的整条路径。

「距离矢量路由算法」的优点很明显：非常简单清晰，且任何加入到网络中的新节点都能很快的与其它节点建立起联系获得补充信息。

「距离矢量路由算法」的缺点如下：

1. 每次发送信息的时候，要发送整个全局路由表，太大了，因为每个路由器需要在矢量表中记录下整个网络的信息，导致需要较大存储、CPU、网络开销，对资源的要求越来越高。
2. 收敛时间太慢，也就是路由器共享路由信息并使各台路由器掌握的网络情况达到一致所需的时间比较久，收敛速度慢会导致有些路由器的表更新慢，从而造成路由环路的问题。

二、链路状态路由算法

链路状态路由算法（Link State Routing ），基于Dijkstra算法，它是以图论作为理论基础，用图来表示网络拓扑结构，用图论中的最短路径算法来计算网络间的最佳路由。基于这类算法实现的协议有：OSPF 等。

如图，这类算法的基本思路是：采用的是不停的拼接地图的方式。每一个路由器首先都会发现自己身边的邻居节点，然后将自己与邻居节点之间的链路状态包广播出去，发送到整个网络。这样，当某个路由器收到从网络中其它路由器广播来的路由信息包（链路状态包）之后，会将这个包中的信息与自己路由器上的信息进行拼装，最终形成一个全网的拓扑视图。

当路由器中形成了全网的拓扑视图后，它就可以通过最短路径算法来计算当前节点到其它路由器之间的最短路径了。当某台路由器的链路状态发生变化时，路由器采用洪泛法向所有路由器发送此信息，其它路由器使用收到的信息重新计算最佳路径，重新生成路由表（拓扑图）。

这里可以做一个类比，有一个路人去问路，然后本地人A只知道A自己生活方圆5公里的地图，本地人B只知道B自己生活的方圆5公里的地图，但是路人要去的地方需要穿过A和B所在区域，那么就把A和B的2份地图拿来拼装在一起，然后去往目的地的完整路线就可以查出来了。

链路状态路由算法简单而言就是五个步骤：

1. 发现邻居节点，并了解邻居网络地址
2. 测量到邻居节点的距离或成本度量值
3. 构建一个包含自己所拥有信息的链路状态包
4. 将这个包广播到网络中，并接收其它路由器的链路状态包
5. 计算出当前节点到其它节点之间的最短路径（基于Dijkstra算法）

链路状态路由算法 不会像 距离矢量路由算法 那样发送整个路由表，链路状态路由协议只会广播更新的或者改变了的网络拓扑，这样传播的信息量会少很多，同时对带宽和CPU资源也是一种节省。

「链路状态路由算法」具有很好的扩展能力，也具有更快的收敛速度，能够快速的适应网络变化，且由于一个路由器的链路状态只涉及与其相邻的路由器的联通状态，因而与整个互联网的规模并无直接关系，因此链路状态路由算法可以用于大型的或者路由信息变化剧烈的互联网环境。

将上述两种算法做一个简单的对比：

参考：

1. https://mp.weixin.qq.com/s/7TTrDuykPWcYWeK5JnBT2A