到底什么是路由？

路由是指路由器从一个接口上收到数据包，根据数据包的目的地址进行定向并转发到另一个接口的过程。

从下面的动图可以明显看出，进行从源到目标的数据管理不是一件容易的事情。

让我们试着通过一个类比来理解路由。想象一个场景，你下班后正准备从公司开车回家，此时路上塞满了车辆，你将在手机地图上查找道路和交通状况。根据路况，你将选择最通畅的那条路回家。

类似地，在路由中，有关数据包移动的决策是根据网络的状态做出的，路由器负责做出这些逻辑数据决策。

设置路由器的主要目的是找到数据包从源到目的地的最有效路径。使用非常复杂的算法，路由器决定当前数据包必须通过哪个路由器或设备发送。重复此过程，直到数据包最终到达目的地。

路由可以分为两类：静态路由和动态路由。在静态路由中，所有路由都是在一个路由器中手动设置的。因此，如果网络有任何变化，路由也不会有任何变化，除非有人手动更正它。

在动态路由中，路由是由软件根据网络的当前状态来设置的。

网络变化，如链路故障、流量变化等，将在每一个离散时间步更新。根据这些信息，将在每个时间步长确定新路线。动态路由优于静态路由，因为路由器会根据网络中的变化进行实时更新。

下面介绍一下最流行的动态路由算法之一，链接状态算法。

链路状态算法分为 Reliable Flooding和Dijkstra最短路径算法。

这个算法是由著名的荷兰计算机科学家Edsger Wybe Dijkstra（1930-2002）在1956年开发的。下面的网络中标记出了每个节点之间的成本，挑战在于找出从一个节点到另一个节点的最短路径。Dijkstra算法生成一个表作为它的输出，利用这个表我们可以确定网络中的最短路径。

这个表是为顶点A生成的。使用这个表，你可以预测到任何其他点的最短路径。如果你想要到点I的最短路径，只要检查之前的顶点即可。从这个顶点开始，检查它之前的顶点，以此类推，直到到达点A。这个表是使用迭代方法生成的，其中最短距离的初始值为无穷大。

下面的动图简单演示了这个过程。

现在我们再来看链路状态算法的第一部分，Reliable Flooding。

您可能已经注意到，为了完美地执行Dijkstra算法，每个路由器应该具有整个拓扑的信息。这是链路状态路由的第一步。路由器的邻域信息称为它的链路状态。这些信息可以是相邻路由器的IP地址、相邻链路的成本等。包含此邻域信息的小数据包称为链路状态数据包。我们应该准确地用拓扑中所有其他路由器的链接状态填充每个路由器。

在网络中，最初每个路由器都知道自己的链路状态。对于下面的小网络，A将它的链路状态包传递给它的邻居，B将这个包传递给它的邻居，以此类推。这样，所有节点都将拥有拓扑的完整链接状态信息。利用这个数据包信息，所有节点都创建或更新一个路由表，并应用Dijkstra的最短路径算法来发送信息包。然而，Flooding并不是那么简单。

考虑一个场景，其中三个节点A、B和C相互连接。节点A向B和C发送链路状态信息。类似地，C将信息发送给B，B再次将信息发送给C，这个过程在一个循环中继续。这个问题称为循环。

因此，在理想的情况下，你希望节点只接收此信息一次。

那么如何克服循环问题呢?

每个包被分配一个唯一的ID。当B从A和C收到这个唯一ID的数据包时，它不发送给C。

Flooding操作后，每个节点独立运行Dijkstra最短路径算法，以确定从自身到网络中其他节点的最短路径。我们所看到的算法是在网络协议的帮助下实现的。

将Flooding操作应用到整个全球网络几乎是不可能完成的任务。

链路状态路由算法的协议称为OSPF。

在OSPF中，整个网络被分成几个局部区域。还创建了一个主干区域，它共享来自本地区域的至少一个路由器。这样就创建了一些边界路由器。你可以看到所有的本地区域都通过这些边界路由器连接到主干区域。在OSPF中，Flooding操作发生在局部区域，而不是全局。

如果一个局部区域的数据包需要传送到另一个局部区域，它们必须经过主干区域。比如数据包从区域二流向区域三，它们必须通过主干区域，而不是直接通过。这种类型的结构通过减少路由表的大小来降低操作的复杂性，还有助于提高网络的可伸缩性。

希望这篇文章能帮助你对路由操作有一个更好的认识！

——END——