计算机网络协议系列 - 网络层路由协议篇：动态路由协议相关算法
- 1 min计算机网络协议系列（十四）
上一篇给大家介绍了静态路由和动态路由，现实网络中，基本使用的都是动态路由，使用动态路由路由器，可以根据动态路由协议算法生成动态路由表，并且路由表随网络运行状况的变化而变化，这就极大降低了 IT 运维人员的管理和维护成本。
动态路由离不开相关的动态路由协议，而这些路由协议算法又可以转化为从图中找到最短路径的问题（计算机网络拓扑可以看作是图结构），我们在数据结构与算法中介绍最短路径的时候，提到了两种算法：弗洛伊德（Floyd）算法和迪杰斯特拉（Dijkstra）算法。
动态路由协议中两个典型的算法 —— 距离向量算法和链路状态算法，正是基于以上最短路径算法实现。下面我们来详细介绍这两种算法的实现思路。
距离向量算法
基于弗洛伊德算法，是一种根据距离和方向（向量）决定目标网络或目标主机位置的算法。这种算法的基本思路是，每个路由器都保存一个路由表，包含多行，每行对应网络中的一个路由器，每一行包含两部分信息，一个是要到目标路由器，从那条线出去，另一个是到目标路由器的距离。
由此可以看出，每个路由器都是知道全局信息的。那这个信息如何更新呢？路由器之间可以互换目标网络的方向及其距离的相关信息，并以这些信息为基础制作路由控制表，每个路由器都知道自己和邻居之间的距离，每过几秒，每个路由器都将自己所知的到达所有的路由器的距离告知邻居，每个路由器也能从邻居那里得到相似的信息。每个路由器根据新收集的信息，计算和其他路由器的距离，比如自己的一个邻居距离目标路由器的距离是 M，而自己距离邻居是 x，则自己距离目标路由器是 x+M。
这种方法在处理上比较简单，不过由于只有距离和方向信息，所以当网络构造变得异常复杂时，在获得稳定的路由信息之前需要消耗一定时间，也极易发生路由循环问题。
链路状态算法
基于迪杰斯特拉算法，是一种路由器在了解网络整体连接状态的基础上生成路由控制表的算法。这种算法的基本思路是：当一个路由器启动的时候，首先是发现邻居，向邻居发送消息，邻居都回复。然后计算和邻居的距离，发送一个 echo，要求马上返回，除以二就是距离。然后将自己和邻居之间的链路状态包广播出去，发送到整个网络的每个路由器。这样每个路由器都能够收到它和邻居之间的关系的信息。因而，每个路由器都能在自己本地构建一个完整的图，然后针对这个图使用迪杰斯特拉算法，找到两点之间的最短路径。
不像距离向量路由协议那样，更新时发送整个路由表，链路状态路由协议只广播更新的或改变的网络拓扑，这使得更新信息更小，节省了带宽和 CPU 利用率。而且一旦一个路由器挂了，它的邻居都会广播这个消息，可以使得坏消息迅速收敛。
了解了动态路由协议算法，下一篇我们就来介绍基于这些算法实现的路由协议，常见的路由协议如下：
目前互联网中广泛应用的是 OSPF 和 BGP 这两个路由协议，具体细节将在下一篇与大家分享。