路由算法

网络层的主要功能是将数据包从源机器路由到目标机器。在大多数网络中，数据包需要经过多跳才能到达目的地。路由算法和这些算法所用的数据结构是网络层设计的最主要内容。

可以这样想，路由器内部有两个进程。其中一个进程在每个数据包到达的时候，对它进行处理，它在路由表中查找该数据包所对应的出境路线，这个进程即为转发进程；另一个进程负责生成和更新路由表，这正是路由算法发挥作用的地方

路由算法可以分为两大类：
非自适应算法不会根据当前测量或者估计的流量和拓扑结构，来调整他们的路由决策。相反，从I到J的所使用的了路由选择是预先下载到路由器中的，也称为静态路由。因为它无法响应故障，所以对与路由选择已经很清楚的场合非常有用。
自适应算法会改变它们的路由决策以便反映出拓扑结构的变化，通常也会反映出流量的变化情况。这些动态路由算法在多方面有些差别：获取信息的来源不同（本地、邻居路由器、所有路由器）、改变路径的时间不同（每当拓扑发生变化时、每隔T秒随负载变化）、路由优化的度量不同（距离、跳数、估计的传输时间）

从Dijkstra最短路径算法开始

给定一个完整的网络视图，dijkstra最短路径算法可以计算出单点到其他所有点的最优路径。这些路径是我们希望分布式路由算法发现的，即使不是全部路由器都知道网络的所有细节。

可以参看博客 Dijkstra最短路径算法的描述

泛洪算法

在实现路由算法时，每个路由器必须根据本地只是而不是网络的全貌做决策，一个简单的本地技术是泛洪（flooding）。这种技术将每一个入境数据包发送到除了该数据包到大的那条线路以外的每条出境路线。
很明显，泛洪法会产生大量的重复的数据包，这就需要采取一些措施：

在每个数据包的头中设置一个跳计数器，每经过一跳该计数器减一，当计数器到达0时就丢弃该数据包
跟踪已经泛洪过的数据包，从而避免第二次发送它们。一种方式是，让每个源路由器在接收来自主机的数据包时填上一个序号，然后每个路由器为每个源路由器准备一张表，记录已经观察到的来自源路由器的序号，如果入境包在这张表中，就不再泛洪该数据包。
为了防止该表膨胀，每个表应该使用一个计数器K作为参数，表示直到K的所有序号都已经观察到了，不需要记录K以下的整个列表。

对于发送大多数数据包来说，泛洪算法是不切实际的，但它确实有一些重要的用途。首先，它确保数据包能被送到网络中的每个节点。对于广播信息来说，这是一种有效的广播手段。其次，泛洪算法的鲁棒性非常好，即使大量的路由器被炸碎，它依然可以找到一条路径（如果存在），把数据包送到目的地。泛洪需要的安装很少，路由器仅仅需要知道自己的邻居即可。
这意味着，泛洪可以作为其他路由算法的基本构件，那些算法更有效但需要更多的处理。泛洪算法总能选出最短的路径，没有其他的算法能够产生一个更短的延迟（当然，这要忽略泛洪过程本身产生的开销）

距离矢量算法(distance vector routing)

每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所用的链路。这些表通过邻居之间交换信息而不断被更新，最终每个路由器都了解到达每个目的地的最佳链路。也叫分布式Bellman-Ford路由算法

可以参考：距离矢量算法简介和距离矢量算法示例

这个算法存在一个严重的缺陷：虽然它总是能够收敛到正确的答案，但速度可能非常慢。尤其是，它对于好消息的反应非常迅速，而对于坏消息的反应异常迟钝。这个算法存在无穷计数的问题。可扩展性很差，越大的网络收敛的越慢。而且，会占用比较大的网络带宽。

链路状态路由（link state routing）

导致距离矢量算法退位的主要原因在于，当网络拓扑结构发生变化后距离矢量路由算法需要太长的时间才能收敛到稳定的状态（由于无穷计数的问题）。因此，出现了一个全新的算法，链路状态路由算法。今天，链路状态路由算法的变种算法——IS-IS或者OSPF已经称为大型网络或Internet应用最为广泛的路由算法。

该算法的设计思路非常简单，对于每个路由器来说，需要完成以下步骤：

发现它的邻居节点，并了解其网络地址
设置到每个邻居节点的距离或者成本度量值
构造一个包含所有刚刚获知的链路信息包
将这个包发送给所有其他的路由器，并接收来自所有其他路由器的信息包
计算出到每个其他路由器的最短路径

实际上，该算法将完整的拓扑结构分发给了每一个路由器。然后每个路由器运行Dijkstra算法就可以找到从本地到每一个其他路由器的最短路径。

发现邻居

当一个路由器启动时，它的第一个任务就是找出哪些路由器是它的邻居。为了实现这个目标，它只需要在每一条点到点线路上发送一个特殊的 HELLO数据包。线路另一端的路由器应该返回一个应答说明自己是谁。

设置链路成本

为了寻求最短路径，链路状态路由算法需要每条链路以距离或成本度量。到邻居节点的成本可自动设置或由网络运营商配置的度量。一种常见的选择是使成本和带宽成反比。如果网络地理上分散，链路的延迟可以作为成本的组成部分。确定这种延迟的最直接的方法是通过线路给另一边发送一个特殊的 ECHO数据包，要求对方立即返回，通过测量往返时间再除以2，发送路由器可以得到一个合理的延迟估计值。

构造链路状态包

该数据包的内容首先是发送方的标识符，接着是一个 序号（seq） 和 年龄（age），以及一个 邻居列表，对于每个邻居同时要给出 到这个邻居的成本。
构造链路状态包很容易。难得是确定什么时候构造数据包，一种做法是周期性的构造数据包。另一种做法是每当发生某些重要的事情时才创建数据包，比如当一条线路断掉或者一个邻居节点停机时，或者当它们重新恢复运行时，或当它们得特性发生了一定变化时。

分发链路状态包

链路状态路由算法最技巧的部分在于分发路由状态数据包。首先，基本的思路是使用泛洪法将链路状态包分发给所有的路由器。

为了控制泛洪规模，每个数据包都包含一个 序号（seq），序号随着每一个新数据包发出而注意递增。路由器记录下它所看到的所有（源路由器、序号）对。当一个新的链路状态数据包到达时，路由器检查这个新来的数据包是否已经出现在上述观察到的列表中。如果是一个新的数据包，则把它转发到除了入境路线之外的所有其他线路上。如果这是一个重复的数据包，则将它丢弃。如果数据包得序号小于当前所看到过得来自该源路由器得最大序列号，则将它作为过时数据包而拒绝接收，因为路由器已经有了更新得数据。
问题一：序号绕回，可能会产生混淆。解决方案是使用一个32位得序列号，即使1S一个链路状态数据包，也要137年才能绕回，所以这种可能性可以忽略！
问题二：序号被破坏了。比如发送方发送得序号是4，由于产生1bit错误，所以接收方接受的65540，那么，序号5-65540得数据包都将被作为过时数据包而拒绝接受。

所有这些问题的解决方案都一样：在每个数据包得序号后面包含一个 年龄（age） 字段，并且每秒钟将年龄减1，当年龄字段的值被减到0时，来自路由器的该信息将被丢弃。通常情况下，每隔一段时间，比如10s，一个新的数据包就会到来；所以只有当一个路由器停机时（或者6个连续的数据包被丢失，这种情况发生的可能性不大），路由器信息才会超时。在初始泛洪过程中，每个路由器也要递减age字段，这样可以确保没有数据包丢失，也不会无限制生存下去。

为了使得算法更为健壮。当一个链路状态数据包被泛洪到一个路由器时，它并没有立即被排入队列等待传输。相反，它首先被放到一个 保留区 中等待一段时间。如果在这个数据包被发出去之前，另一个来自同一个源路由器的链路状态数据包也到来了，那么就比较它们得序号，保留最新的包。为了防止线路产生错误导致丢包和错包，所有的链路状态数据包都要被确认。
在这里插入图片描述
在图中，来自A得链路状态数据包可以直接到达，所以B必须将它发送给C和F，并按照标志位得指示向A发送确认。
然而，第三个数据包，即来自E得数据包有所不同。它到达两次，依次经过EAB，另一次经过EFB。因此它只需要被发送给C，但仍然需要向A和F确认。

计算新路由

一旦路由器积累了全部的链路状态数据包之后，它就可以构造出完整的网络图，然后就可以在路由器本地运行Dijkstra算法，从而构造出从本地出发到所有可能目标的最短路径。这个算法的运行结果告诉路由器到达每个目的地能够走那条路径。这个信息被安装在路由表中。

实际应用

相比于距离矢量算法，链路状态路由算法需要更多的内存和计算，在大型网络中运行这个算法依然是个问题。不过，在许多现实场合，链路状态路由算法工作得非常好，因为它没有慢收敛得问题。

链路状态路由算法被广泛应用于实际网络中。IS-IS，Intermediate System-Intermediate System，被很多的ISP使用。后来它被ISO采纳用于OSI协议；然后它被修改多次以便能够处理多种协议，比如IP协议。OSPF，Open Shortest Path First，是另一个主流的链路状态协议。