网络中的「动态路由算法」，你了解吗？

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

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

本文主要聊的就是「动态路由算法」，你知道动态路由算法有哪些吗？

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

• 距离矢量路由算法
• 链路状态路由算法

下面我们来看一下这两类算法的特点：

一、距离矢量路由算法

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

如图，

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

每隔一段时间当前路由器会向所有的邻居节点发送自己的这个表，同时它也会接收每个邻居发来的它们的表。并会将邻居的表和自己的表做一个对比更新。
比如当前 路由器X 离 邻居Y路由器 的距离是m，此时收到 邻居Y 发来的表中写到了“ 邻居Y离路由器Z的距离是n ”，那 当前路由器X 就知道它离 路由器Z 的距离可能就是 m+n 了，如图：

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

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

好了，讲到这里，基本上对「距离矢量路由算法」大概原理有个认识了，现在我们再来仔细分析分析这个算法的名字，可以发现，它的名字取的还是蛮有意思的，非常贴切。“距离”这个词就基本表明了这个算法是通过 距离（跳数/时间）来度量2个路由网络之间的线路的，而“矢量”这个词，可以看出线路是有方向性的，且路由表中只记录了数据包去往目的地应该走哪个出口方向，并不会记录到达目的地的整条路径。

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

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

二、链路状态路由算法

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

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

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

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

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

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

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

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

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

图片来源网络，经供参考。

以上，就是对计算机网络中的动态路由算法的基本讲解了，欢迎大家一起交流。

本文原创发布于微信公众号「 不止思考 」，欢迎关注，交流Java、Web、架构、大数据、职业发展、技术管理。