3.3.5 路由
路由是除了局域网以外，例如以太网（局域网在所有相连的主机间两两都有直接连接），其他网络都需要的功能。在大型网络中，采用的是自适应路由，即网络两点间通信的最佳路由会周期性地重新评估， 图3-7 广域网中的路由评估时会考虑到当时的网络流量以及故障情况（如路由器故障或网络断链）。
如图3-7所示，在网络中将数据包传递到目的地址是处于连接点的路由器的共同责任。除非源主机和目的主机都在同一个局域网中，否则数据包都必须经过一个或多个路由结点，辗转多次才能到达。而决定数据包传输到目的地址的路由是由路由算法负责的——它由每个结点的一个网络层程序实现。
路由算法包括两个部分：
1）它必须决定每个数据包穿梭于网络时所应经过的路径。在电路交换网络层（如X.25）和帧中继网络（如ATM）中，一旦建立虚电路或连接，路由也就确定了。98在包交换网络层（如IP）中，数据包的路由是单独决定的。如果希望不降低网络性能，算法必须特别简单有效。
2）它必须通过监控流量和检测配置变化或故障来动态地更新网络的知识。在这种活动中，时间并不是至关重要的，可以使用速度较慢但计算量较大的技术。
这两个活动分布在整个网络中。路由是一段一段决定的，它用本地拥有的信息决定每个进入的数据包下一步的方向。本地拥有的路由信息依靠一个分发链路状态信息（它们的负载和故障状态）的算法定期更新。
一个简单的路由算法 我们在这里描述的是“距离向量”算法。这将为3.4.3节中讨论链路-状态算法提供基础，而链路-状态算法从1979以来就成为互联网上主要的路由算法。网络中的路由是在图中寻找路径问题的一个实例。Bellman的最短路径算法［Bellman 1957］早在计算机网络出现之前就发表了，它为距离向量法提供了基础。Bellman的方法已被Ford和Fulkerson［1962］改写成一个适合大型网络实现的分布式算法，而基于他们的工作成果的协议常常被称为“Bellman-Ford”协议。
图3-8给出了图3-7的网络中每个路由器中保存的路由表，其中假设网络中没有出故障的链路和路由器。路由表的每行为发送给定目的地址的数据包提供了路由信息。链路域为发送到指定目的地的数据包指明了下一段链路。开销域计算向量距离，99或到达目的地的跳数。对于具有相似带宽的链路的存储转发网络，这张表对一个数据包传输到目的地所需的时间给出了合理估计。存储在路由表中的开销信息并不是路由算法的第1部分所采取的包路由动作中使用的，而是在算法的第2部分建立和维护路由表时使用。
路由表中为每个可能的目的地单独设置一项，给出了数据包到达目的地而要采取的下一跳（hop）。当数据包到达一个路由器时，就会抽取目的地址并在本地路由表中查找该地址。路由表中的表项给出了指引数据包发送到目的要经过的下一个链路。
例如，一个目的地为C的数据包从路由器A开始发送，路由器在路由表中检查有关C的项。路由表表明数据包应该从A沿标号为1的链路路由。数据包到达B后，按照前述的过程，在B的路由表中查询，发现需要经过标号为2的链路路由到C。当数据包到达C时，路由表中的相关项显示“本地”，而不是一个链路号。这表明应该将数据包发送到本地主机上去。
现在让我们来考虑一下怎样建立路由表，以及在网络发生故障时怎样维护路由表，即上面所说的路由算法的第2部分是怎样完成的。因为每个路由表只为每个路由指定一跳，所以路由信息的构建或修正就可以按分布的方式进行。每个路由器使用路由器信息协议（Router Information Protocol,RIP）通过发送自己路由表信息的概要和邻接结点相互交换网络信息。下面简要描述一下路由器所完成的RIP动作：
1）周期性地并且只要本地路由表发生改变，就将自己的路由表（以概要的方式）发给邻接的所有可访问的路由器。也就是说，在每个没有故障的链路上发出一个包含路由表副本的RIP数据包。
2）当从邻接路由器收到这样的表时，如果接收到的表中给出了到达一个新目的地的路由，或对于已有的一个目的地更好（开销更低）的路由，则用新的路由更新本地的路由表。如果路由表是从链路n接收到的，并且表中给出的从链路n开始到达某地的开销和本地路由表中的不相同，则用新的开销替换本地表中已有的开销。这样做的原因是，新表是从和相关的目的地更近的路由器传来的，因此对经过该路由器的路由而言更加有权威性。
图3-9给出的伪代码程序将更准确地描述这个算法，其中Tr是从另一个路由器接收到的表，Tl是本地路由表。Ford和Fulkerson［1962］已经证明，无论何时网络发生变化，上面描述的步骤都能充分确保路由表收敛到到达每个目的地的最佳路由。即使网络没有发生变化，也会以频率t来传播路由表，以确保其稳定性，例如，要在丢失RIP数据包的情况下保证稳定性。互联网采用的t值是30s。
为了处理故障，每个路由器都监控着自己的链路并做以下的工作：
当检测到一条有故障的链路n时，将本地表中指向故障链路的所有项的开销都设为无穷大（∝），并执行Send动作。
这样，一个断开的链路信息被表示成通往相关目的地的开销值是无穷大。当这一信息传播到邻接路由器时，它们的路由表也将根据Receive动作进行更新（注意：∝+1=∝），然后继续传播直到有路由到相关目的地的结点。最终，具有可用路由的结点将会传播其路由表，它的可用路由也将替代所有结点上的故障路由。
向量-距离算法可以用多种方法进行改进。开销，也被称为度量，可以根据链路的实际带宽来计算；可以修改算法，以增加信息收敛的速度，并避免那些在达到收敛前可能出现的不希望出现的中间状态，例如循环。具有这些改进的路由信息协议是第一个在互联网中使用的路由协议，也就是众所周知的RIP-1，其具体描述见RFC 1058［Hedrick 1988］。但收敛速度过慢所带来的问题并没有得到很好的解决，当网络处于中间状态时就会出现路由低效和数据包丢失的问题。
后来，路由算法的发展趋于在每个网络结点中增加对于网络的信息容量。这一类算法中最重要的一族是链路-状态算法。它们的基本思想是分布并更新在每个结点中一个表示网络所有部分或重要部分的数据库。每个结点负责计算在自己的数据库中所显示的到达目的地的最佳路由。这种计算可利用多种算法完成，有些算法避免了Bellman-Ford算法中存在的问题，如收敛的时间慢和出现的不希望中间状态。101路由算法的设计是一个相当重要的主题，我们这里的讨论是非常有限的。我们将在3.4.3节重新讨论这个主题，在那里将描述RIP-1算法的操作，RIP-1算法是最早用于IP路由的算法之一，目前在互联网的许多地方还在使用它。对于互联网中更深入的路由问题，请参阅Huitema［2000］，如想全面地了解路由算法，请参阅Tanenbaum［2003］。
