使用TCP/IP进行网际互连---第十三章（路由信息传播算法）

使用TCP/IP进行网际互连---第十三章（路由信息传播算法）

1. 路由的建立包括路由的初始化和更新。
每个路由器在启动时都必须建立一个初始的路由集合，还要随着路由的改变而更新该表（如某个特定网络中的硬件出故障时）。
初始化过程与操作系统有关：
1）在某些系统中，路由器启动时从辅存中（如硬盘）读取初始路由表，然后将其驻留在高速内存中。
2）在另一些系统中，路由器刚开始只有一张空表，然后必须使用显式命令（例如，启动命令脚本中包含的
   命令）填入表项值。
3）最后，还有一些系统在启动时，先从本机直接相连的网络所含有的地址集合推导出一个初始的路由集合，
   然后和相邻的机器联络，请求得到其他路由。

2. 最初的Internet体系结构
最初的路由器体系结构由少量中心路由器和大量外围路由器组成， 中心路由器保存了所有可能目的站的全部信息，而大量外围路由器仅保存部分信息。保存全部信息的中心路由器集合称为因特网的核心（core）。最初的因特网核心系统避免了使用默认路由，因为它把所有可能目的站的全部信息传播到了每个核心路由器。（因为使用默认路由，一个数据包可能经过所有的路由器，形成一个大环，导致了低效。）

3. 从核心结构到对等主干网结构
在因特网（实际为ARPANET）中引入 NSFNET 主干网之后，因特网从一个中心的主干网发展成一组对等主干网络（peer backbone networks） ，或简称为对等方（peers）。

4. 路由选择协议有两个重要功能：
1）首先，负责计算一组最短的路径；
2）其次，通过持续地更新路由信息，响应网络故障或拓扑的改变。

5. 路由传播算法1——距离向量（distance-vector）路由选择
距离向量算法的思想很简单：每个路由器在路由表中列出所有已知路由。路由器启动时对路由表进行初始化，为自己直接相连的每个网络生成一个表项。表中的每个表项指出了一个目的网络，并给出到那个网络的距离，通常用跳数（hop）来度量距离值。每个路由器定期把自己的路由表副本发送给与其直接相连的其他路由器。当来自路由器 J 的报告到达路由器 K 之后，K 检查这个报告中列出的目的站以及到各个目的站的距离。
1）如果 J 知道有一条更短的路由去某个目的站；
2）或者 J 列出 K 的表中不曾有的目的站；
3）或者 K 目前到某个目的站的路由经过 J，而 J 到该目的站的距离有所改变；
K 就会替换自己的路由表中的相应表项。

距离向量这个术语来源于定期发送报文中的信息。一个报文包含成对的（D，V）列表，其中 V 表示目的站，称为向量（vector） ，而 D 是到该目的站的距离。

距离向量算法的缺点:
1）当路由迅速发生变化时， 对变化反应太慢，算法可能无法稳定下来。
2）最主要的缺点是其无法适应网络规模变大的情况。该算法要进行大量的报文交换，由于每次路由更新
   都包含每个可能的网络对应的表项，报文的长度与互联网中的网络总数成正比。
3）此外，由于距离向量协议要求每个路由器都参与进来，所以交换的信息量可能会十分庞大。

6. 路由传播算法2——链路状态 / 最短路径优先（SPF）路由选择
链路状态（link state/link status）算法，或称最短路径优先（shortest Path First，简称SPF）算法。SPF 算法要求每个参与的路由器都被给予或计算出拓扑结构的信息。我们可以想象每个路由器都有一张映射图，图中标出了其他所有路由器以及与路由器连接的网络，这种方法最易于我们思考拓扑结构。用抽象的术语表示，路由器对应于图中的结点，而连接路由器的网络对应于图中的边。当且仅当两个结点对应的路由器之间能直接通信时，这两个结点之间才有一条边。

参与 SPF 算法的路由器并不发送包含目的站列表的报文，而是要完成两项任务：
1）首先，它要积极地检测所有相邻路由器的状态。用图论的术语来讲，如果两个路由器共享一条链接，
   则称它们是相邻的路由器；用网络的术语来讲，两个相邻的路由器连接到同一个网络中。
2）其次，路由器要向所有其他路由器定期传播链路状态信息。
（两个相邻的路由器之间是通过物理链路相连的，这条物理链路在SPF算法中表示为一条边，检测链路状态，即检测两个路由器之间的物理链路的相连性，即检测连接是否正常。所以该算法称为“链路状态算法”。同时，在路由器选择路由时，使用的是最短路径优先算法，所以又称为“最短路径优先算法”）

为了检测直接连接的相邻路由器的状态，两个相邻路由器交换短报文，确认对方是否可达且处于活跃状态。如果相邻的路由器回答了，则称这两者之间的链路是正常工作的（up），否则就称链路是有故障而不能工作的（down）。实际上，为了避免在正常状态和故障状态之间来回变化，许多协议使用n中取k的规则（k-out-of-n rule）来检测活跃状态，即在大多数请求得不到回答的情况下，链路状态才由正常转为故障，而在大多数请求都得到回答的情况下，链路状态由故障转为正常。

为了通知其他所有路由器，每个路由器定期广播一个报文，报文中列出该路由器的各个链路状态。这个状态报文并不指明路由，而是报告成对的路由器之间是否能够通信。路由器中的协议软件设法把各个链路状态的报文副本交付给所有相关的路由器。

SPF算法的主要优点之一就是每个路由器使用相同的原始状态数据，独立地计算路由，而不需要依靠中间路由器的计算。由于链路状态报文仅携带与单个路由器直接相连的链路信息，报文的长短与下层互联网中的网络数目无关。因此，SPF算法比距离向量算法更适用于大规模的互联网。

7. 小结
为了确保所有网络保持高可靠性的可达状态，互联网必须提供全局一致的转发。主机和大多数路由器仅含有部分路由信息，依靠默认路由把数据报发送给远方的目的站。

全球因特网最初使用核心路由器结构来解决路由选择问题，在这种结构中，一组核心路由器各自包含所有网络有关的全部信息。

当额外有一些主干网加入到因特网后，出现了一种新的路由选择结构来适应这种扩展的拓扑结构。目前仍存在一组独立管理的对等主干网，这些主干网通过多个地方的路由器互连起来。当路由器交换路由信息时，通常会使用两种基本算法，即距离向量算法或 SPF 算法。距离向量算法的主要缺点是进行分布式的最短路径计算，当网络连接的状态频繁变化时，计算可能不收敛。因此，SPF算法更适用于大型互联网或下层拓扑结构变化快的互联网。