我们都知道，计算机网络的通用分层模型是五层分级模型（物理层、链路层、网络层、运输层、应用层）。每一层都承担着不同任务，你能顺利地和小姐姐在网上聊天，这五层缺一不可?。今天，我们要讲的便是网络层的重要内容。 “咳咳，现在开始上课！”

网络层的核心功能

泛泛来讲，网络层在计算机网络中承担的主要功能是：将数据从一台主机移动到另外一台主机。详细一点说，网络层的主要功能是：路由和转发。

不用说你也知道，承担路由和转发功能的部件是路由器。

那么问题来了，路由器究竟是如何将聊天信息数据从你的主机转移到小姐姐的主机呢？

简单的说，当你在聊天窗口按下“发送”按钮后，你的聊天数据被应用层打包成数据包，经过运输层向路由器运送，而路由器会将数据包中包含地址信息解析出来，交给路由转发表处理，路由转发表就能够确定数据包在本路由器如何转发分组。

问题又来了，路由转发表到底是啥？他怎么能够知道我的信息要转发到小姐姐那里呢？

这就涉及到我们今天的主角：路由算法。路由算法能够确定去往目的网络的最佳路径，而转发表则能够确定数据包在本路由器如何转发分组。

为了方便处理，我们一般将网络抽象为图。其中，路由器为图中的结点，网络链路抽象为图中的边，链路长度则为图中的权值。

路由算法的分类

路由算法从配置方式划分，分为静态路由和动态路由；而动态路由的路由算法，从掌握网络拓扑信息的规模来说，又可以分为全局路由选择算法和分散路由选择算法。

静态路由和动态路由

所谓静态路由，是基于手工配置的路由方式。我们可以类比获取IP的方式，ip获取方式也有两种，一种是静态，一种是动态。静态就是由网络管理员来配置网络ip，而动态则是由网络运营商直接分配。如果你还是不太明白，你可以设想下民国时期打电话的方式：你拨通电话，并非直接打到目的地，而是达到了电话局，由电话局接线，才能拨通。所以说，静态路由的网络管理员，扮演的就是接线员的角色。

静态路由有如下特点：

• 路由信息更新慢
• 优先级高

同样的，动态路由是基于算法的方式是基于某种路由算法实现的，这种方案自动化程度高，是非常明智的选择。

动态路由有如下特点：

• 路由更新快
• 定期更新（周期性）

全局信息和分散信息

全局信息方案的代表是链路状态路由算法，分散信息的代表方案是距离向量路由算法。

链路状态路由算法

在链路状态路由算法中，网络拓扑和所有的链路费用都是已知的。所有的结点或者说路由器都掌握着完整的网络拓扑和链路费用。

到这里，你是否能猜到链路状态路由算法是谁了吧？

没错，他就是我们的老朋友——迪杰斯特拉算法。

从前面介绍中我们也能知道，不论是链路状态路由算法还是距离向量选择算法，核心要义都是四个字：”最短路径“。

所以，知道了整张网络拓扑，最佳的方案就是迪杰斯特拉算法。当然，另外一个最短路径算法”Prim“也是一个选择，这里不做展开。

我们还是先从一个例子开始。

在上图中，我们以u为起点，计算u到z的最短路径。可见，若要计算u到z的路径，那么必须考虑全局信息。

实际上，迪杰斯特拉算法的核心内容是：找最小，然后找最小的邻居。

具体过程参考下图。

1. 初始化 与u相邻的置为权值，不与u相邻的置为无穷。
2. 找到最小 在上图中，与u相邻的权值最小的是（w，3），所以将w加入集合中。
3. 在其余中找最小 5为最小，则将x加入集合。经过x，可以到达z，这样最短，将z更新为14。
4. 接着找最小 6为最小，将v加入集合。经过uwv，可以到达y，最小值为10，则更新。
5. 依次类推，得到最终结果

所以，我们能够得到最终的转发表。

距离向量路由算法

距离向量路由算法，是基于Bellman-Ford方程，也就是动态规划算法实现的。

在距离向量路由算法中，同样是计算由u到其他任意一点。但在这种算法中，u无需知道整个网络的拓扑结构。对u来说，最重要的事情是知道，如果需要把数据运往z，最合适的邻居节点究竟是哪一个。

即节点只需获取最短路径的下一跳，无需知道整个网络拓扑的情况，并且该信息用于转发表中。

所以，距离向量路由算法是一种迭代的、异步的、分布式的算法。

迭代很好理解，在每个节点只需要知道他的下一跳的目的地的情况下，想要求得最小路径，那么必然需要使用迭代，使得最短路径不断趋近于真实值。

为什么说是不断趋近于真实值呢？一开始，也就是初始化时，结点只知道他到其邻居结点的距离，而不知道到其他结点的距离。

这就必然造成此结点到其直接邻居结点的距离并非是最优的，可能是绕过一个或两个结点再到此结点的情况，才是最短的路径。

所谓异步的，是因为我们不要求结点的步调整齐一致，也就是计算最短路径的时间可以是不同的。实际上，时间基本上就是不同。

所谓分布式的，是说每个节点都能接收到来自其邻居的信息，并执行计算，然后再将计算结果分发给邻居，邻居再将收到的数据进行计算，如果发现了其他最短路径，那么就会更新自身的信息，又进入了一个迭代的过程。

整个算法中最重要的是这样一个方程：

先来解释一下这个方程。

我们要找到从x到y找到最短路径，就需要知道x到底是经过哪个结点到达y的总长度最短（也可以不经过邻居结点，此时y就是x的邻居）。

即我们需要知道，x到底是经过了哪一个邻居，才使得x到邻居到y的距离最短。

所以，我们来总结一下。

距离向量路由算法的核心思想是：

• 每个结点都不定时地将其自身的距离向量（到达其邻居）的估计（非精确，后期迭代可能会调整）发送给其邻居
• 当x接收到邻居新的距离向量时，根据动态规划方程更新距离向量估计。若数据不发生变化，则无需更新和发送。

具体描述如下（DV即为距离向量）

写在最后

所谓“金无足赤人无完人”。以上算法同样如此，不论是链路状态路由算法还是距离向量路由算法，都有其自身的问题。他们在实际应用中都有着非常明显的问题，从而又有解决这些问题的方法出现。

计算机科学乃至是任意一门科学，都是在不断地发现问题、解决问题的迭代过程中渐渐趋于真相。

我们要相信，尽管眼前可能看起来麻烦很多，但是我们找到了解决麻烦的方法时，就会惊喜的发现：“Trouble is a friend”。

好了，今天文章就到这里，感谢您的阅读，如果你喜欢我的文章，请点个赞吧！

引用： 《计算机网络：自顶向下》 中国大学MOOC，哈尔滨工业大学计算机网络，李金龙等