通信网络/路由

路由

路由是将信息数据包传送到目的地所需经过的过程。路由是一个出乎意料的复杂任务，有多种不同的算法被用来找到两个点之间的最短路径。

介绍

IP 地址基于主机和网络的概念。主机本质上是网络上任何能够接收和传输 IP 数据包的设备，例如工作站或路由器。路由是将数据从一台主机计算机移动到另一台主机计算机的过程。路由和桥接之间的区别在于，桥接发生在 OSI 参考模型的第 2 层（链路层），而路由发生在第 3 层（网络层）。路由确定通过网络的最佳路由路径。

路由算法

路由算法存储在路由器的内存中。路由算法是路由环境性能的主要因素之一。路由算法的目的是为路由器做出有关数据最佳路径的决策。路由器使用路由算法来计算最适合将数据从源传输到目的地的路径。请注意，您无法直接选择路由器使用的算法。相反，您为网络选择的路由协议决定了将使用哪种算法。例如，虽然路由信息协议 (RIP) 路由协议可能使用一种类型的路由算法来帮助路由器移动数据，但开放最短路径优先 (OSPF) 路由协议使用另一种算法。路由算法不可更改。更改它的唯一方法是更改路由协议。您网络的整体性能主要取决于路由算法，因此您应该在决定在网络上实施哪个协议之前，研究每个协议使用的算法。路由算法主要分为两大类：距离向量或链路状态。每个名为“距离向量”的路由协议都使用距离向量算法，而每个链路状态协议都使用链路状态算法。

路由协议中的路由算法

路由协议的工作之一是提供路由算法计算其决策所需的信息。这是许多协议有所不同的点。提供给算法的信息在不同的协议中可能不同。

路由协议从周围环境收集有关网络和路由器的信息，并将信息存储在路由器内存中的路由表中。路由算法使用该表中的信息来计算从一个网络到另一个网络的最佳路径。计算公式中的新值，然后生成一个总和。该计算结果随后用于确定将信息发送到哪里。例如，下表说明了虚构路由环境的示例路由表。路由表中传递给路由算法的信息是通过称为路由更新的过程由路由协议收集的。通过一系列更新，每台路由器都会告诉其他路由器它拥有哪些信息。最终，将建立完整的路由表。

路由器链路	度量
路由器 A 到路由器 B	2
路由器 B 到路由器 C	3
路由器 A 到路由器 C	6
路由器 C 到路由器 D	5

示例路由算法指出，到达任何目的地的最佳路径是度量值最低的路径。度量是一个数字，用作衡量网络链路的标准。每个链路都被分配一个度量，以代表从使用线路的货币成本到可用带宽的数量的任何内容。当路由器 A 接收一个从路由器 C 发送的数据包时，路由表显示了两种可能的路径供选择。第一个选择是将数据包从路由器 A 直接通过链路发送到路由器 C。第二个选择是将数据包从路由器 A 发送到路由器 B，然后继续发送到路由器 C。路由算法用于确定哪个选项最佳。

一些路由协议可能只向路由算法提供一个度量，而另一些协议可能提供多达十个度量。另一方面，虽然两个协议都可能只向算法发送一个度量，但该度量的来源可能在不同的协议中有所不同。一种路由协议可能会给算法提供成本的单个度量，但该成本可能代表与使用相同度量的另一种协议不同的东西。

我们示例中的算法指出，最佳路径是度量值最低的路径。因此，通过添加与每条可选链路相关的度量数字，我们看到，从路由器 A 到路由器 B 再到路由器 C 的路由的度量值为 5，而到路由器 C 的直接链路的度量值为 6。算法选择 A-B-C 路径并将信息发送过去。

距离向量算法

距离向量算法使用称为成本的度量来帮助确定到达目的地的最佳路径。总成本最低的路径被选为最佳路径。

当路由器使用距离向量算法时，每个路由器都会收集不同的成本。这些成本可以是完全任意的数字。成本也可以是动态收集的值，例如路由器在通过一条链路而不是另一条链路发送数据包时所经历的延迟量。所有成本都被编译并放置在路由器的路由表中，然后由算法用于计算任何给定网络场景的最佳路径。

尽管有很多资源会提供关于距离向量算法是什么以及它们如何计算其决策的复杂数学表示，但核心概念仍然相同——通过添加网络上每条可选路径的度量，您将得到至少一条最佳路径。该公式如下所示

M(i,k) = min [M(i,t) + M(t,k)]

该公式指出，两个网络之间的最佳路径 (M(i,k)) 可以通过找到所有网络点之间路径的最低 (min) 值来找到。让我们再次看一下上面表格中的路由信息。将此信息代入公式，我们看到，从 A 到 B 再到 C 的路由仍然是最佳路径

5(A,C) = min[2(A,B) + 3(B,C)]

而从 A 到 C 的直接路由公式如下所示

6(A,C) = min[6(A,C)]

此示例显示了距离向量算法如何使用传递给它们的信息来做出明智的路由决策。路由器和路由协议使用的算法不可配置，也不能修改。

距离向量算法和链路状态协议之间另一个主要区别在于，当距离向量路由协议相互更新时，整个或部分路由表（取决于更新类型）将从一台路由器发送到另一台路由器。通过此过程，每台路由器都会接触到其他路由器表中包含的信息，从而使每台路由器对网络环境有更完整的了解，并能够做出更好的路由决策。距离向量算法的示例包括 RIP 和 BGP，它们是当今使用最广泛的两种协议。其他流行的协议，如 OSPF，是使用链路状态路由算法的协议的示例。

距离向量算法也称为贝尔曼-福特路由算法和福特-福克森路由算法。在这些算法中，每台路由器都有一个路由表，显示了到任何目的地的最佳路由。下面显示了路由器 J 的典型图和路由表。

目的地	权重	线路
A	8	A
B	20	A
C	20	I
D	20	H
E	17	I
F	30	I
G	18	H
H	12	H
I	10	I
J	0	N/A
K	6	K
L	15	K

该表显示，如果路由器 J 想要将数据包发送到路由器 D，它应该首先将数据包发送到路由器 H。当数据包到达路由器 H 时，当前路由器会检查自己的表并决定如何将数据包发送到 D。在距离向量算法中，每台路由器都必须遵循以下步骤

1. 它计算直接与其连接的链路的权重并将信息保存到其表中。

2. 在特定的时间段内，路由器将其表发送到其邻居路由器（而不是所有路由器）并接收其每个邻居的路由表。

3. 基于路由器从其邻居路由表中接收的信息，它更新自己的路由表。

让我们再看一个例子（下面显示的图形）。

每条链路的成本都设置为 1。因此，最低成本路径只是跳数最少的路径。下表表示每个节点关于到所有其他节点距离的知识

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F	G
A	0	1	1	$\infty$	1	1	$\infty$
B	1	0	1	$\infty$	$\infty$	$\infty$	$\infty$
C	1	1	0	1	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	1	0	$\infty$	$\infty$	1
E	1	$\infty$	$\infty$	$\infty$	0	$\infty$	$\infty$
F	1	$\infty$	$\infty$	$\infty$	$\infty$	0	1
G	$\infty$	$\infty$	$\infty$	1	$\infty$	1	0

最初，每个节点将其直接连接的邻居的成本设置为 1，将其余所有节点的成本设置为无穷大。以下是节点 A 的初始路由表

目的地	成本	下一跳
B	1	B
C	1	C
D	$\infty$	-
E	1	E
F	1	F
G	$\infty$	-

在下一步中，每个节点都向其直接连接的邻居发送一条消息。该消息包含该节点的个人距离列表。例如，节点 F 告诉节点 A 它可以以 1 的成本到达节点 G；节点 A 也知道它可以以 1 的成本到达 F，因此它将这些成本加起来以获得通过 F 到达 G 的成本。由于 2 小于当前的无穷大成本，因此节点 A 记录它可以以 2 的成本通过 F 到达 G。节点 A 从 C 处得知节点 B 可以从 C 处以 1 的成本到达，因此它得出结论，通过 C 到达 B 的成本为 2。由于这比当前到达 B 的成本（1）更差，因此忽略了新信息。节点 A 的最终路由表如下所示

目的地	成本	下一跳
B	1	B
C	1	C
D	2	C
E	1	E
F	1	F
G	2	F

将一致的路由信息传播到所有节点的过程称为收敛。下表显示了从每个节点到所有其他节点的最终成本集

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F	G
A	0	1	1	2	1	1	2
B	1	0	1	2	2	2	3
C	1	1	0	1	2	2	2
D	2	2	1	0	3	2	1
E	1	2	2	3	0	2	3
F	1	2	2	2	2	0	1
G	2	3	2	1	3	1	0

每条链路的成本都设置为 1。因此，最低成本路径只是跳数最少的路径。

距离向量算法的一个问题称为“无限计数”。让我们通过一个例子来检查以下问题

考虑一个网络，其图形如下所示。D 和网络其他部分之间只有一条链路。

带有向量

d [A][A] = 0 d [A][B] = 1 d [A][C] = 2 d [A][D] = 3

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	1
D	3	2	1	0

现在 C 到 D 的链路崩溃了，所以 cost [C][D] = ∞ C 以前将任何地址为 D 的数据包直接转发到 CD 链路，但现在链路已断开，因此 C 必须重新计算其距离向量（并做出新的选择以转发到 D 的数据包）- 同样，D 也必须更新其向量。在更新 C 和 D 处的向量后，我们有

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

C 将 B 视为到达 D 的最佳路由，成本为 1 + 2，因此 C 将新向量发送到 B。B 了解到它以前通过 C 发送到 D 的选择现在成本更高，因此 B 应该重新计算其向量。

	A	B	C	D
A	0	1	2	3
B	1	0	1	4
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

B 的观点是路由到 D 可以通过 A 或 C 进行，成本相同 - B 发送更新的向量。A 和 C 都从 B 处获得更新的向量，并了解到它们到 D 的首选路由现在成本更高，因此它们重新计算自己的向量。

	A	B	C	D
A	0	1	2	5
B	1	0	1	4
C	2	1	0	5
D	$\infty$	$\infty$	$\infty$	0

然后 A 和 C 发送它们的向量，B 必须再次更新其向量，向 A 和 C 发送另一轮，得到。

	A	B	C	D
A	0	1	2	7
B	1	0	1	6
C	2	1	0	7
D	$\infty$	$\infty$	$\infty$	0

请注意，路由表非常缓慢地收敛到以下事实

d [x][D] = ∞ for x = A 或 x = B 或 x = C

这个过程会循环，直到所有节点都发现到 D 的链路的权重为无穷大。这样，专家们说距离向量算法的收敛速度很慢。总之，距离向量算法不是健壮的。解决此问题的一种方法是让路由器只向非目的地独占链路的邻居发送信息。例如，在本例中，B 不应向 C 发送有关 D 的任何信息，因为 C 是到达 D 的唯一途径。

链路状态算法

距离向量算法和链路状态算法都偏爱成本最低的路径。但是，链路状态协议以更本地化的方式工作。虽然运行距离向量算法的路由器将计算任何给定数据包的端到端路径，但链路状态协议将计算与最直接链路相关的路径。也就是说，距离向量算法将计算网络 A 和网络 C 之间的最低度量，而链路状态协议将将其计算为两个不同的路径，即 A 到 B 和 B 到 C。对于更大的环境，此过程非常高效。链路状态算法使路由器能够专注于自己的链路和接口。网络上的任何一台路由器都只知道直接与其连接的路由器和网络（或其自身链路的状态）。在更大的环境中，这意味着路由器将使用更少的处理能力来计算复杂的路径。路由器只需要知道它的哪个直接接口可以最快地将信息传送到需要去的地方。下一台路由器将重复此过程，直到信息到达其目的地。这种本地化路由过程的另一个优势是协议可以维护更小的路由表。由于链路状态协议只维护其直接接口的路由信息，因此路由表包含的信息比可能包含多个路由器信息的距离向量协议少得多。与距离向量协议类似，链路状态协议需要更新来彼此共享信息。这些路由更新称为链路状态通告 (LSA)，它们在路由器链路状态发生变化时发生。当某个特定链路不可用（状态发生变化）时，路由器会通过环境发送更新，提醒与其直接连接的所有路由器。

在链路状态算法中，每台路由器都必须遵循以下步骤

1. 识别与之物理连接的路由器并获取它们的 IP 地址 当路由器开始工作时，它首先通过网络发送一个“HELLO”数据包。接收此数据包的每台路由器都会回复一条包含其 IP 地址的消息。

2. 路由器测量邻居路由器的延迟时间（或网络的其他任何重要参数，例如平均流量）。为了做到这一点，路由器通过网络发送回声数据包。接收这些数据包的每台路由器都会回复一个回声回复数据包。通过将往返时间除以 2，路由器可以计算延迟时间。延迟时间包括传输时间和处理时间 - 数据包到达目的地所需的时间以及接收器处理它并回复所需的时间。

3. 将其信息广播到网络中供其他路由器使用，并接收其他路由器的信息。在此步骤中，所有路由器都共享其知识并将信息广播给彼此。这样，每台路由器都可以了解网络的结构和状态。

4. 路由器使用适当的算法来识别网络中两个节点之间的最佳路由。在此步骤中，路由器选择到每个节点的最佳路由。它们使用一个算法（例如 Dijkstra 最短路径算法）来做到这一点。在该算法中，路由器根据从其他路由器收集的信息，构建一个网络图。该图显示了网络中路由器的位置以及它们彼此之间的链路。每个链路都标有一个称为权重或成本的数字。此数字是延迟时间、平均流量以及有时只是节点之间跳数的函数。例如，如果节点和目的地之间有两条链路，路由器将选择权重最低的链路。

Dijkstra 算法

Dijkstra 算法通过以下步骤进行

1. 路由器构建网络图。然后它识别源节点和目标节点，例如 R1 和 R2。路由器然后构建一个矩阵，称为“邻接矩阵”。在邻接矩阵中，坐标表示权重。例如，[i, j] 是节点 Ri 和 Rj 之间链路的权重。如果 Ri 和 Rj 之间没有直接链路，则该权重被识别为“无穷大”。
2. 路由器然后为网络上的每个节点构建一个状态记录。该记录包含以下字段
   • 前驱字段 - 显示前一个节点。
   • 长度字段 - 显示从源节点到该节点的权重总和。
   • 标签字段 - 显示节点的状态；每个节点都有一种状态模式："永久"或"暂定"。
3. 在下一步中，路由器初始化状态记录的参数（对于所有节点）并将它们的标签设置为“暂定”，并将它们的长度设置为“无穷大”。
4. 在此步骤中，路由器设置一个 T-节点。例如，如果 R1 是要作为源 T-节点，则路由器将 R1 的标签更改为“永久”。一旦标签更改为“永久”，它将永远不会再更改。
5. 路由器更新所有直接链接到源 T-节点的暂定节点的状态记录。
6. 路由器遍历所有暂定节点，并选择权重到 R1 最小的那个节点。然后，该节点就是目标 T-节点。
7. 如果新的 T-节点不是 R2（预期目标），则路由器返回步骤 5。
8. 如果该节点是 R2，则路由器从状态记录中提取其上一个节点，并一直这样做，直到它到达 R1。此节点列表显示了从 R1 到 R2 的最佳路线。

Dijkstra 算法示例

让我们找到路由器 A 和 E 之间的最佳路线。它们之间有六条可能的路线（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），并且很明显 ABDE 是最佳路线，因为它的权重最低。但生活并不总是那么容易，我们有一些复杂的情况，我们必须使用算法来找到最佳路线。

1. 源节点 (A) 已被选为 T-节点，因此它的标签是永久的（永久节点用实心圆表示，T-节点用 -> 符号表示）。

2. 在此步骤中，已更改直接链接到 T-节点 (B、C) 的暂定节点的状态记录。此外，由于 B 的权重较小，因此它已被选为 T-节点，并且它的标签已更改为永久。

3. 与步骤 2 相似，已更改与 T-节点 (D、E) 有直接链接的暂定节点的状态记录。由于路由器 D 的权重较小，因此它已被选为 T-节点，并且它的标签已更改为永久。

4. 由于我们没有任何暂定节点，因此我们只需识别下一个 T-节点。由于节点 E 的权重最小，因此它已被选为 T-节点。

现在我们必须识别路线。E 的上一个节点是节点 D，D 的上一个节点是节点 B，B 的上一个节点是节点 A。因此，我们确定最佳路线是 ABDE。在这种情况下，总权重为 4 (1+2+1)。该算法运行良好，但它非常复杂，路由器可能需要很长时间才能处理它。这会导致网络效率下降。我们应该在这里注意的另一点是，如果路由器向其他路由器提供错误信息，则所有路由决策将无效。

下一个示例显示了如何在网络中的所有节点之间找到最佳路线。该示例使用 **最短路径 Dijkstra 算法**。请考虑以下显示的网络

让我们使用 Dijkstra 算法查找 A 将用于向网络上的任何节点传输数据的路线。Dijkstra 路由算法在下表中表示

		B	C	D	E	F	G	H	I
步骤 1	A	2-A	3-A	5-A	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
步骤 2	AB		3-A	5-A	7-B	9-B	$\infty$	$\infty$	$\infty$
步骤 3	ABC			4-C	4-C	9-B	$\infty$	$\infty$	$\infty$
步骤 4	ABCD				4-C	9-B	$\infty$	11-D	$\infty$
步骤 5	ABCDE					8-E	12-E	7-E	$\infty$
步骤 6	ABCDEH					8-E	12-E		11-H
步骤 7	ABCDEHF						10-F		11-H
步骤 8	ABCDEHFG								11-H
步骤 9	ABCDEHFGI

这是网络在所有更新后看起来的样子，显示了节点之间的最短路线

内部路由

互联网中的数据包路由分为两大类：内部路由和外部路由。内部路由发生在独立网络系统内部或内部。在 TCP/IP 术语中，这些独立的网络系统称为自治系统。在自治系统 (AS) 内，使用自治系统管理选择的内部路由协议交换路由信息。另一方面，外部路由协议用于自治系统之间。内部路由协议确定到每个目的地的“最佳”路线，并在网络上的系统之间分发路由信息。有几种内部协议

- 路由信息协议 (RIP) 是 UNIX 系统上最常用的内部协议。RIP 使用距离向量算法，该算法选择具有最低“跳数”(度量) 的路线作为最佳路线。RIP 跳数表示数据必须通过多少网关才能到达其目的地。RIP 假设最佳路线是使用最少网关的路线。

- Hello 是一种协议，它使用延迟作为选择最佳路线的决定因素。延迟是数据报从源到目的地往返所需的时间。

- 中间系统到中间系统 (IS-IS) 是来自 OSI 协议套件的内部路由协议。它是一种链路状态协议。它是在 T1 NSFNET 骨干网上使用的内部路由协议。

- 开放最短路径优先 (OSPF) 是为 TCP/IP 开发的另一种链路状态协议。它适用于非常大的网络，并提供比 RIP 更好的几个优势。

路由信息协议 (RIP)

RIP（路由信息协议）是网关和主机之间交换路由信息的标准。它是一种距离向量协议。RIP 作为“内部网关协议”最为有用。网络被组织为“自治系统”的集合。每个自治系统都有自己的路由技术，对于不同的自治系统，这种技术可能完全不同。在自治系统内使用的路由协议被称为内部网关协议或“IGP”。路由信息协议 (RIP) 旨在与使用相当同质技术的中等规模网络一起使用。因此，它适合作为许多校园和使用串行线路（速度变化不大）的区域网络的内部网关协议 (IGP)。它不适合在更复杂的环境中使用。RIP2 源自 RIP，是路由信息协议 (RIP) 的扩展，旨在扩展 RIP 消息中承载的有用信息量并增加一定程度的安全性。RIP2 是一种基于 UDP 的协议。

使 RIP 正常工作的是一个路由数据库，它存储有关计算机之间最快速路线的信息，一个更新过程，使每个路由器能够告诉其他路由器从其角度来看哪条路线最快，以及一个更新算法，使每个路由器能够使用从相邻路由器传达的最快速路线来更新其数据库

**数据库** - 给定网络上的每个 RIP 路由器都保存一个数据库，该数据库为该网络中的每台计算机存储以下信息

IP 地址 - 计算机的互联网协议地址。

网关 - 发送到该 IP 地址的消息的最佳网关。

距离 - 此路由器与能够直接发送消息到该 IP 地址的路由器之间的路由器数量。

路线更改标志 - 表示此信息已更改的标志，其他路由器使用它来更新自己的数据库。

计时器 - 各种计时器。

**算法** - RIP 算法的工作原理如下

更新 - 每隔一段时间，每个路由器都会向其直接连接到的所有其他路由器发送一条更新消息，描述其路由数据库。有些路由器会每隔 30 秒发送一次此消息，以便网络始终拥有最新信息，以便在计算机和路由器启动和关闭网络时快速适应变化。RIP 和 RIP2 的协议结构如下所示

RIP 和 RIP2 的协议结构如下所示

8 位	16 位	32 位
命令	版本	未使用
地址族标识符		路由标签（仅适用于 RIP2；RIP 为 0）
IP 地址
子网掩码（仅适用于 RIP2；RIP 为 0）
下一跳（仅适用于 RIP2；RIP 为 0）
度量

**命令** - 命令字段用于指定数据报的目的。有五个命令：请求、响应、Traceon（已过时）、Traceoff（已过时）和保留。

**版本** - RIP 版本号。当前版本为 2。

**地址族标识符** - 指示在此特定条目中指定了哪种类型的地址。这是因为 RIP2 可能会承载几种不同协议的路由信息。IP 的地址族标识符为 2。

**路由标签** - 分配给路由的属性，必须保留并使用路由重新通告。路由标签提供了一种方法来区分内部 RIP 路由（RIP 路由域内网络的路由）和外部 RIP 路由，这些路由可能是从 EGP 或其他 IGP 导入的。

**IP 地址** - 目的地 IP 地址。

子网掩码 - 应用于 IP 地址的值，以产生地址的非主机部分。如果为零，则没有为此条目包含子网掩码。

**下一跳** - 应将发送到此路由条目指定的目的地的数据包转发到的直接下一跳 IP 地址。

**度量** - 表示从主机到该目的地的数据报的总成本。此度量是与要遍历以到达目的地的网络相关的成本的总和。

开放最短路径优先协议 (OSPF)

OSPF 是一种内部网关协议，用于连接属于单个自治系统的路由器。OSPF 使用链路状态技术，其中路由器彼此发送有关它们与其他路由器之间的直接连接和链路的信息。每个 OSPF 路由器都维护一个描述自治系统拓扑的相同数据库。从该数据库中，通过构建最短路径树来计算路由表。OSPF 在拓扑发生变化时会快速重新计算路由，并使用最少的路由协议流量。提供了区域路由功能，从而可以提供额外的路由保护级别并减少路由协议流量。此外，所有 OSPF 路由协议交换都经过身份验证。OSPF 根据 IP 数据包报头中找到的目标 IP 地址来路由 IP 数据包。IP 数据包按原样路由 - 它们在穿过自治系统时不会封装在任何其他协议报头中。OSPF 允许将网络集分组在一起。这种分组称为区域。区域的拓扑对自治系统的其余部分隐藏。这种信息隐藏可以显着减少路由流量。此外，区域内的路由仅由区域自身的拓扑决定，从而使区域免受错误路由数据的侵害。

OSPF 算法的工作原理如下

启动 - 当路由器打开时，它会向所有邻居发送 Hello 数据包，接收它们的 Hello 数据包，并通过与同意同步的相邻路由器同步数据库来建立路由连接。

更新 - 每隔一定时间，每个路由器都会向所有其他路由器发送一条名为“链路状态”的更新消息，其中描述了其路由数据库，以便所有路由器都具有对本地网络拓扑的相同描述。

最短路径树 - 然后每个路由器计算一个称为“最短路径树”的数学数据结构，该结构描述了到每个目标地址的最短路径，因此指示了发送到每个通信的最接近路由器；换句话说 - “开放最短路径优先”。

OSPF（开放最短路径优先版本 2）的协议结构如下所示

8 位	16 位	24 位
版本号	数据包类型	数据包长度
路由器 ID
区域 ID
校验和		AuType
身份验证

版本号 - 协议版本号（当前为 2）。

数据包类型 - 有效类型如下：1 Hello 2 数据库描述 3 链路状态请求 4 链路状态更新 5 链路状态确认。

数据包长度 - 协议数据包的长度（以字节为单位）。此长度包括标准 OSPF 标头。

路由器 ID - 数据包源的路由器 ID。在 OSPF 中，路由协议数据包的源和目标是（潜在）相邻关系的两端。

区域 ID - 标识此数据包所属的区域。所有 OSPF 数据包都与单个区域相关联。大多数只传播单跳。

校验和 - 数据包整个内容的标准 IP 校验和，从 OSPF 数据包标头开始，但不包括 64 位身份验证字段。

AuType - 标识要用于数据包的身份验证方案。

身份验证 - 用于身份验证方案的 64 位字段。

中间系统到中间系统路由协议（IS-IS）

中间系统到中间系统 (IS-IS) 是一种链路状态协议，其中 IS（路由器）基于单个度量交换路由信息以确定网络拓扑。它在 TCP/IP 网络中的行为类似于开放最短路径优先 (OSPF)。在 IS-IS 网络中，有终端系统、中间系统、区域和域。终端系统是用户设备。中间系统是路由器。路由器被组织成称为“区域”的本地组，多个区域被分组到一个“域”中。IS-IS 主要用于提供域内路由或区域内的路由。IS-IS 与 CLNP、ES-IS 和 IDRP 协同工作，提供整个网络的完整路由。IS-IS 路由利用两级层次路由。级别 1 - 路由器了解其区域内的拓扑结构，包括所有路由器和主机，但它们不知道其区域之外的路由器或目标的身份。级别 1 路由器将所有指向其区域之外的目标的流量转发到其区域内的级别 2 路由器，该路由器了解级别 2 拓扑。级别 2 路由器不需要了解任何级别 1 区域内的拓扑，除非级别 2 路由器也可能是一个区域内的级别 1 路由器。IS-IS 已被改编为承载 IP 网络信息，称为集成 IS-IS。集成 IS-IS 具有现代路由协议中最重要的特征：它支持 VLSM 并快速收敛。它还可以扩展以支持非常大的网络。IS-IS 地址有两种类型：网络服务访问点 (NSAP) - NSAP 地址标识网络层服务，每个运行的服务一个。网络实体标题 (NET) - NET 地址标识网络层实体或进程，而不是服务。设备可能拥有两种类型地址中的多个地址。但是 NET 应该是唯一的，并且 NSAP 的系统 ID 部分必须对每个系统都唯一。IS-IS（中间系统到中间系统路由协议）的协议结构如下所示

8 位				16 位
域内路由协议鉴别符				长度指示器
版本/协议 ID 扩展				ID 长度
R	R	R	PDU 类型	版本
保留				最大区域地址

域内路由协议鉴别符 - 分配给此协议的网络层协议标识符

长度指示器 - 固定报头的长度（以八位字节为单位）。

版本/协议 ID 扩展 - 等于 1。

ID 长度 - 此路由域中使用的 NSAP 地址和 NET 的 ID 字段长度。

R - 保留位。

PDU 类型 - PDU 的类型。位 6、7 和 8 保留。

版本 - 等于 1。

最大区域地址 - 此中间系统区域允许的区域地址数量。

IS-IS 的 NSAP 格式如下所示

<-IDP->		<-DSP->
		<-HO-DSP->
AFI	IDI	由 IDI 字段中标识的授权机构分配的内容
<-区域地址->			<-ID->	<-SEL->

IDP - 初始域部分

AFI - 授权和格式标识符（1 字节）；提供有关 IDI 和 DSP 字段的结构和内容的信息。

IDI - 初始域标识符（可变长度）

DSP - 域特定部分

HO-DSP - 高阶域特定部分

区域地址（可变）

ID - 系统 ID 1-8 字节

SEL - n 选择器（1 字节值，其功能类似于 Internet 协议中的端口号）。

外部路由

外部路由发生在自治系统之间，是服务提供商和其他大型或复杂网络关心的问题。基本可路由元素是自治系统。虽然可能存在许多不同的内部路由方案，但单个外部路由系统管理着全球互联网，主要基于 BGP-4 外部路由协议。

边界网关协议 (BGP)

边界网关协议 (BGP) 确保数据包无论当前网络状况如何都能到达其目标网络。BGP 本质上是一种距离矢量算法，但有一些额外的变化。首先，BGP 路由器与它直接通信的其他 BGP 路由器建立连接。它所做的第一件事是下载每个相邻路由器的整个路由表。之后，它只与其他路由器交换短得多的更新消息。BGP 路由器发送和接收更新消息以指示到达具有给定 IP 地址的计算机的首选路径的更改。如果路由器决定更新自己的路由表，因为此新路径更好，那么它将随后将此信息传播到它连接的所有其他相邻 BGP 路由器，而它们反过来将决定是否更新自己的表并将信息进一步传播出去。

BGP 在端口 179 上使用 TCP/IP 协议建立连接。它具有强大的安全功能，包括在 BGP 路由器之间所有通信中包含数字签名。每个 BGP 路由器都包含一个路由信息库 (RIB)，其中包含该路由器维护的路由信息。RIB 包含三种类型的信息

• Adj-RIBs-In - 相邻路由器发送的未经编辑的路由信息。
• Loc-RIB - 路由器实际使用的路由信息，从 Adj-RIBs-In 开发而来。
• Adj-RIBs-Out - 路由器选择发送给相邻路由器的信息。

BGP 路由器使用四种类型的消息交换信息

• 打开 - 用于与相邻路由器打开初始连接。
• 更新 - 这些消息完成了大部分工作，在相邻路由器之间交换路由信息，并包含以下信息之一
  • 撤回的路由 - 路由器不再可以路由消息到的计算机的 IP 地址。
  • 路径 - IP 地址的新首选路由。此路径包含两部分信息 - IP 地址和用于路由到该地址的目标消息的路径中下一个路由器的地址。
• 通知 - 用于指示错误，例如接收到的错误或不可读的消息，并且之后立即关闭与相邻路由器的连接。
• 保持活动 - 每个 BGP 路由器大约每 30 秒向每个相邻路由器发送一个 19 字节的 Keepalive 消息，以告知它们它仍然可以运行，并且每三秒不超过一次。如果任何路由器在设定的时间内没有从相邻路由器收到 Keepalive 消息，它将关闭与该路由器的连接，并将其从路由信息库中删除，修复它认为对网络造成的损害。

路由消息是互联网上优先级最高的流量，每个 BGP 路由器都优先考虑它们，优先于所有其他流量。这是有道理的 - 如果路由信息无法通过，那么其他任何信息也无法通过。

BGP 算法在 BGP 路由器从相邻路由器收到更新消息后运行，并包含以下三个步骤，这些步骤针对相邻路由器发送的每个 IP 地址执行

• 更新 - 如果更新消息中 IP 地址的路径信息与之前从该路由器接收的信息不同，那么 Adj-RIBs-In 数据库将使用最新信息更新。
• 决策 - 如果是新信息，则会运行一个决策过程，以确定在所有当前记录在 Adj-RIBs-In 数据库中的 BGP 路由器中，哪个路由器对更新消息中的 IP 地址具有最佳路由路径。该算法没有强制要求，BGP 管理员可以为决策过程设置本地策略标准，例如与每个相邻路由器通信需要多长时间，以及每个相邻路由器与路径中的下一个路由器通信需要多长时间。如果此决策过程所选择的最佳路径与当前记录在 Loc-RIB 数据库中的路径不同，则更新数据库。
• 传播 - 如果决策过程发现了一条更好的路径，则 Adj-RIBs-Out 数据库也会更新，路由器会向所有相邻的 BGP 路由器发送更新消息，告诉它们关于更好的路径。然后，每个相邻路由器依次运行自己的 BGP 算法，决定是否更新其路由数据库，然后依次将所有新的和改进的路径传播到相邻路由器。

BGP 算法执行的另一个重要功能是消除路由信息中的循环。例如，当路由器 A 认为路由器 B 是发送某些计算机消息的最佳路径，而 B 认为最佳路径是通过 C，但 C 认为最佳路径是返回 A 时，就会发生路由循环。如果允许这种类型的路由循环发生，那么任何通过路由器 A、B 或 C 传递到该计算机的消息将永远在它们之间循环，无法传递消息，并且会消耗越来越多的网络资源。BGP 算法会捕获并停止任何此类循环。

分层路由

在链路状态和距离向量算法中，每个路由器都必须保存一些关于其他路由器的信息。当网络规模扩大时，网络中路由器的数量会增加。因此，路由表的规模也会增加，路由器无法像以前那样高效地处理网络流量。分层路由用于克服这个问题。让我们来考察一个例子。

距离向量算法用于找到节点之间的最佳路径。在下面的情况下，网络中的每个节点都必须保存一个包含 17 条记录的路由表。

以下是 A 的典型图和路由表

目的地	线路	权重
A	N/A	N/A
B	B	1
C	C	1
D	B	2
E	B	3
F	B	3
G	B	4
H	B	5
I	C	5
J	C	6
K	C	5
L	C	4
M	C	4
N	C	3
O	C	4
P	C	2
Q	C	3

在分层路由中，路由器被分类为称为区域的组。每个路由器只拥有其自身区域中路由器的信息，而没有其他区域中路由器的信息。这样，路由器在表中只需为每个区域保存一条记录。在这个例子中，我们将我们的网络分为五个区域（见下图）。

目的地	线路	权重
A	N/A	N/A
B	B	1
C	C	1
区域 2	B	2
区域 3	C	4
区域 4	C	3
区域 5	C	2

如果 A 要向区域 2（D、E、F 或 G）中的任何路由器发送数据包，则将数据包发送到 B，依此类推。如您所见，在这种类型的路由中，表可以被概括，从而提高了网络效率。上面的例子展示了双层分层路由。我们也可以使用三层或四层分层路由。在三层分层路由中，网络被分为若干个集群。每个集群由若干个区域组成，每个区域包含若干个路由器。分层路由被广泛用于互联网路由，并利用了多种路由协议。

总结

在距离向量算法中，将你所知道的全部信息发送给你的邻居，而链路状态算法则将你邻居的信息发送给所有人。

链路状态算法的消息大小很小，而距离向量算法的消息大小可能很大。

链路状态算法的消息交换量很大，而距离向量算法的消息交换量只限于邻居。

收敛速度

– 链路状态算法：很快

– 距离向量算法：使用触发更新时很快

空间需求

– 链路状态算法维护整个拓扑

– 距离向量算法只维护邻居状态

鲁棒性

• 链路状态算法可以广播不正确/损坏的 LSP - 局部问题

• 距离向量算法可以向所有目的地发布不正确的路径 - 不正确的计算会蔓延到整个网络

练习

1. 对于下面给定的网络，给出全局距离向量表，当

a) 每个节点只知道到其直接邻居的距离

b) 每个节点已将其在先前步骤中所拥有的信息报告给其直接邻居

c) 步骤 b) 再次发生

2. 对于练习 1 中的网络，展示链路状态算法如何为节点 D 构建路由向量表。

3. 对于下图给定的网络，给出全局距离向量表，当

a) 每个节点只知道到其直接邻居的距离

b) 每个节点已将其在先前步骤中所拥有的信息报告给其直接邻居

c) 步骤 b) 再次发生

4. 假设我们在一个所有链路成本都为 1 的网络中，有如下所示的节点 A 和 F 的转发表。给出与这些表一致的最小网络图。

对于节点 A，我们有

节点	成本	下一跳
B	1	B
C	1	C
D	2	B
E	3	C
F	2	C

对于节点 F，我们有

节点	成本	下一跳
A	2	C
B	3	C
C	1	C
D	2	C
E	1	E

5. 对于下面的网络，使用最短路径 Dijkstra 算法找到从节点 A 作为源头的最小成本路由。

答案

1.

a)

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F
A	0	$\infty$	3	8	$\infty$	$\infty$
B	$\infty$	0	$\infty$	$\infty$	2	$\infty$
C	3	$\infty$	0	$\infty$	1	6
D	8	$\infty$	$\infty$	0	2	$\infty$
E	$\infty$	2	1	2	0	$\infty$
F	$\infty$	$\infty$	6	$\infty$	$\infty$	0

b)

c)

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F
A	0	6	3	6	4	9
B	6	0	3	4	2	9
C	3	3	0	3	1	6
D	6	4	3	0	2	9
E	4	2	1	2	0	7
F	9	9	6	9	7	0

2.

D	已确认	暂定
1.	(D,0,-)
2.	(D,0,-)	(A,8,A) (E,2,E)
3.	(D,0,-) (E,2,E) (C,3,E)	(A,8,A) (B,4,E)
4.	(D,0,-) (E,2,E) (C,3,E)	(A,6,E) (B,4,E) (F,9,E)
5.	(D,0,-) (E,2,E) (C,3,E) (B,4,E)	(A,6,E) (F,9,E)
6.	previous + (A,6,E)
7.	previous + (F,9,E)

3.

a)

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F
A	0	2	$\infty$	5	$\infty$	$\infty$
B	2	0	2	$\infty$	1	$\infty$
C	$\infty$	2	0	2	$\infty$	3
D	5	$\infty$	2	0	$\infty$	$\infty$
E	$\infty$	1	$\infty$	$\infty$	0	3
F	$\infty$	$\infty$	3	$\infty$	3	0

b)

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F
A	0	2	4	5	3	$\infty$
B	2	0	2	4	1	4
C	4	2	0	2	3	3
D	5	4	2	0	$\infty$	5
E	3	1	3	$\infty$	0	3
F	$\infty$	4	3	5	3	0

c)

信息 存储在节点	到达节点的距离
	A	B	C	D	E	F
A	0	2	4	5	3	6
B	2	0	2	4	1	4
C	4	2	0	2	3	3
D	5	4	2	0	5	5
E	3	1	3	5	0	3
F	6	4	3	5	3	0

4.

5.

步骤 1

步骤 2

步骤 3

步骤 4

步骤 5

参考文献

• http://e-books.amagrammer.net/
• 计算机网络，第 3 版，2003 年，Peterson 和 Davie
• http://www.eng.ucy.ac.cy/christos/Courses/ECE360/Lectures.htm