交换机、路由器、网桥和局域网/路由器/路由基础

什么是路由？

路由是在互联网中将信息从源头移动到目的地的过程。在此过程中必须遇到至少一个中间节点。路由和桥接看起来很相似，但两者之间的主要区别在于桥接发生在 OSI 参考模型的第 2 层（链路层），而路由发生在第 3 层（网络层）。路由和桥接之间的重要区别之一是，第 3 层地址是按层次结构分配的，因此路由器可以有一个规则来允许它路由到数千或数百万个地址的整个地址范围。这在处理互联网规模时是一个重要的优势，因为互联网上的主机数量太多（并且添加和删除速度太快），以至于任何路由器都无法知道互联网上所有主机的地址。

路由器在网络层中承担着信息路由的角色。路由器是网络层的核心。首先我们来看看路由器的体系结构、数据报在路由器中的处理，然后我们将学习路由算法。

路由器的体系结构

路由器将包含以下组件

输入端口

输入端口执行多个功能。物理层功能由线路终结单元执行。协议解封装由数据链路处理执行。输入端口还执行查找和转发功能，以便从路由器交换结构的适当输出端口出来的数据包被转发出去。控制数据包（如携带 RIP、OSPF 等路由协议信息的）被转发到路由处理器。输入端口在输出线路繁忙时还会执行输入排队。

输出端口

输出端口将来自交换结构的数据包转发到相应的输出线路。它执行与输入端口完全相反的物理和数据链路功能。输出端口还执行来自交换结构的数据包排队。

路由处理器

路由处理器执行路由协议。它维护路由信息和转发表。它还在路由器内部执行网络管理功能。

交换结构

交换结构的工作是将数据包移动到特定的端口。交换可以通过多种方式完成

• 通过内存交换：最简单、最容易的路由器，输出端口和输入端口之间的交换在 CPU（路由器处理器）的直接控制下完成。每当数据包到达输入端口时，路由处理器就会通过中断得知。然后它将传入数据包从输入缓冲区复制到处理器内存。处理器然后提取目标地址，从相应的转发表中查找，并将数据包复制到输出端口的缓冲区。在现代路由器中，目标地址的查找和数据包存储（交换）到相应内存位置的操作由处理器的输入线路卡完成。
• 通过总线交换：输入端口直接将数据包通过共享总线传输到输出端口，无需路由处理器的干预。由于总线是共享的，因此一次只能传输一个数据包。如果总线繁忙，则传入数据包必须在队列中等待。路由器的带宽受共享总线的限制，因为每个数据包都必须穿过单个总线。示例：总线交换 CISCO-1900、3-COM’s care builder5。
• 通过互连网络交换：为了克服共享总线的带宽问题，使用了交叉连接交换网络。在交叉连接交换网络中，输入端口和输出端口通过水平和垂直总线连接。如果我们有 N 个输入端口和 N 个输出端口，则需要 2N 根总线来连接它们。要将数据包从输入端口传输到相应的输出端口，数据包沿着水平总线移动，直到它与通向目标端口的垂直总线交叉。如果垂直总线空闲，则传输数据包。但如果垂直总线繁忙，因为其他一些输入线路正在传输数据包到同一个目标端口，则数据包将被阻塞并排队在相同的输入端口。

处理 IP 数据报

传入输入端口的数据包被存储在队列中，等待处理。当处理开始时，首先处理 IP 头。执行错误校验和以识别传输中的错误。如果没有错误，则检查目标 IP 地址字段。如果目标地址是本地主机，则考虑协议 UDP、TCP 或 ICMP 等，数据字段将传递给相应的模块。

如果目标 IP 地址不是本地主机，则它将在其路由表中检查目标 IP 地址。路由表包含应将数据包转发到的下一个路由器的地址。然后，对传出的数据包执行输出操作，例如其 TTL 字段必须减少 1，并且重新计算校验和位，并将数据包转发到通向相应目的地的输出端口。如果输出端口繁忙，则数据包必须在输出队列中等待。

输出端口的数据包调度程序必须从队列中选择数据包进行传输。数据包的选择可以基于先到先服务（FCFS）或优先级或等待公平排队 (WFQ)，它在为传输排队的数据包的不同端到端连接之间“公平地”共享出站链路。对于服务质量，数据包调度起着至关重要的作用。如果传入数据报包含路由信息，则将数据包发送到路由协议，该协议将相应地修改路由表条目。

路由算法

现在我们将考虑不同的路由算法。有两种类型的协议用于将信息从源头传输到目的地。

路由协议与被路由协议

路由协议用于在路由器之间传递用户流量，例如 IP 或 IPX。路由数据包包含足够的信息，使路由器能够传递流量。路由协议定义字段以及如何使用这些字段。

路由协议包括

• 互联网协议
  • Telnet
  • 远程过程调用 (RPC)
  • SNMP
  • SMTP
• Novell IPX
• 开放式系统互连网络协议
• DECnet
• Appletalk
• Banyan Vines
• 施乐网络系统 (XNS)

路由协议允许路由器收集和共享路由信息以维护和更新路由表，而路由表反过来用于查找到达目的地的最有效路线。

路由协议包括

• 路由信息协议 (RIP 和 RIP II)
• 开放式最短路径优先 (OSPF)
• 中间系统到中间系统 (IS-IS)
• 内部网关路由协议 (IGRP)
• 思科的增强型内部网关路由协议 (EIGRP)
• 边界网关协议 (BGP)

路由算法的设计目标

路由算法具有以下一个或多个设计目标

• 最优性: 这是路由协议搜索并获取最佳路线的能力。路由度量用于查找最佳路由器。跳数或延迟可用于查找最佳路径。应优先选择跳数更少或延迟最小的路径作为最佳路线。
• 简单性和低开销: 路由算法的设计也尽可能简单。路由算法必须高效地提供其功能，并将软件开销降至最低。效率在软件实现路由算法必须在物理资源有限的计算机上运行或处理大量路由时尤为重要。
• 健壮性和稳定性: 路由协议应该在异常或不可预见的情况下正确运行，例如硬件故障、高负载条件和错误实现。路由协议的这一特性称为健壮性。最好的路由算法通常是那些经受住了时间考验并在各种网络条件下证明稳定的算法。
• 快速收敛: 路由算法必须快速收敛。收敛是所有路由器就最佳路线达成一致的过程。在网络中，当网络事件导致路由中断或变得可用，或者链路成本发生变化时，路由器会分发路由更新消息，这会导致网络中的其他路由器重新计算最佳路线，并最终导致网络中的其他路由器就这些路线达成一致。
• 灵活性: 路由算法也应该具有灵活性。它们应该快速准确地适应各种网络环境。

路由算法的分类

路由算法主要分为两种类型

• 静态路由: 在静态路由算法中，数据包遵循的路线始终保持不变。当路线变化非常缓慢时，使用静态路由算法。在这种网络中，网络管理员预先计算路由表，数据包在两个目的地之间采取的路径始终是已知的，并且可以精确地控制。
  • 优点
    • 可预测性: 由于网络管理员预先计算路由表，因此数据包在两个目的地之间采取的路径始终是已知的，并且可以精确地控制。
    • 路由器或网络链路无开销: 在静态路由中，不需要所有路由器都定期发送包含可达性信息的更新，因此路由器或网络链路的开销很低。
    • 简单性: 小型网络的配置很容易。
  • 缺点
    • 缺乏可扩展性: 计算少量主机和路由器的静态路由很容易。但对于较大的网络，查找静态路由变得很麻烦，并可能导致错误。
    • 如果网络段移动或添加: 要实施更改，您需要更新网络上每个路由器的配置。如果您错过了一个，在最好的情况下，连接到该路由器的段将无法到达已移动或添加的段。在最坏的情况下，您将创建一个影响许多路由器的路由循环。
    • 它无法适应网络中的故障: 如果使用静态路由的网络中的链路出现故障，那么即使有可用的备用链路，路由器也不会知道要使用它。
• 动态路由: 机器可以通过路由协议相互通信并构建路由表。然后路由器将数据包转发到下一个跳跃点，该跳跃点更靠近目的地。使用动态路由，路线变化更快。定期发送网络更新，以便如果链路成本发生变化，网络上的所有路由器都会知道，并将相应地更改其路由表。
  • 优点
    • 可扩展性和适应性: 动态路由网络可以更快地增长，并且在规模更大时不会变得难以管理。它能够适应这种增长带来的网络拓扑变化。
    • 适应网络中的故障: 在动态路由中，路由器通过与其他路由器通信来了解网络拓扑。每个路由器都会宣布其存在。它还会向网络上的其他路由器宣布其可用的路线。因此，如果您添加了新的路由器，或者向现有路由器添加了其他段，其他路由器将听到添加的内容，并相应地调整其路由表。
  • 缺点
    • 复杂性增加: 在动态路由中，它必须定期发送关于拓扑的通信信息的更新。路由器必须准确地确定它必须发送什么信息。当路由器从其他路由器了解网络信息时，正确适应网络变化非常困难，它必须准备删除旧的或不可用的路由，这会增加更多复杂性。
    • 线路和路由器的开销: 路由器定期向其他路由器发送关于网络拓扑的通信信息包。这些数据包不包含用户信息，只包含路由器所需的信息，因此这仅仅是线路和路由器的额外开销。

动态路由协议的分类

第一种分类基于协议的预期使用位置: 在您的网络和另一个网络之间，或在您的网络内: 这就是内部和外部之间的区别。第二种分类与协议承载的信息类型以及每个路由器如何做出关于如何填写其路由表的决定有关，即链路状态与距离矢量。

链路状态路由

在链路状态协议中，路由器提供有关其附近网络拓扑的信息，而不提供有关它知道如何到达的目的地信息。此信息包括它所连接的网络段或链路的列表，以及这些链路的状态（正常运行或未正常运行）。然后将此信息广播到整个网络。由于在整个网络中广播的信息，每个路由器都可以构建自己对网络当前状态的图像。由于每个路由器都看到相同的信息，因此所有这些图像都应该相同。从这个图像中，每个路由器计算其到所有目的地的最佳路径，并使用此信息填充其路由表。现在我们将看到称为迪杰斯特拉算法的链路状态算法。

符号及其含义如下

• $N$ 表示图中所有节点的集合。
• $l(i,j)$ 表示从节点 $i$ 到节点 $j$ 的链路成本，它们都在 $N$ 中。如果两个节点没有直接连接，则 $l(i,j)=\infty$。该算法最通用的形式不需要 $l(i,j)\neq l(j,i)$，但为了简化起见，我们假设它们相等。
• $s$ 是执行算法以找到到所有其他节点的最短路径的节点。
• $M$ 表示到目前为止，该算法已将节点合并到 $N$ 中，以找到到所有其他节点的最短路径。
• $C(n)$ 是从源节点 $s$ 到目标节点 $n$ 的路径成本。

算法定义

在实际中，每个路由器维护两个列表，称为 Tentative 和 Confirmed。这两个列表都包含一组 (Destination, Cost, Nexthop) 格式的条目。

该算法的工作原理如下

1. 将 Confirmed 列表初始化为一个关于我自己的条目；该条目成本为 0。
2. 对于之前步骤中刚刚添加到 Confirmed 列表中的节点，称其为节点 Next，选择其 LSP。
3. 对于 Next 的每个邻居 (Neighbor)，计算到达此邻居的成本 (Cost)，作为从我到 Next 的成本和从 Next 到邻居的成本之和。
   1. 如果邻居当前既不在 Confirmed 列表上也不在 Tentative 列表上，则将 (Neighbor, Cost, NextHop) 添加到 Tentative 列表，其中 NextHop 是我到达 Next 所要走的路线。
   2. 如果邻居当前在 Tentative 列表上，并且 Cost 小于邻居当前列出的成本，则用 (Neighbor, Cost, NextHop) 替换当前条目，其中 NextHop 是我到达 Next 所要走的路线。
4. 如果 Tentative 列表为空，则停止。否则，从 Tentative 列表中选择成本最低的条目，将其移动到 Confirmed 列表，并返回步骤 2。

列表中成本最低的条目，将其移动到 Confirmed 列表，并返回步骤 2。

[算法来自 Computer Networks a system approach – Peterson 和 Davie。]

现在让我们看一个例子：考虑下面描绘的网络。

为 A 生成路由表的步骤如下

步骤	Confirmed	Tentative	注释
1	( A,0,-)		由于 A 是 Confirmed 列表中唯一的新的成员，所以查看它的 LSP。
2	(A,0,-)	(B,9,B) (C,3,C) (D,8,D)	A 的 LSP 表示我们可以通过 B 访问 B，成本为 9，这比任何其他列表中的成本都低，C 和 D 也是如此。
3	(A,0,-) (C,3,C)	(B,9,B) (D,8,D)	将 Tentative 中成本最低的成员 (C) 放入 Confirmed 列表。接下来，检查新确认的成员 (C) 的 LSP
4	(A,0,-) (C,3,C)	(D,4,C)	通过 C 访问 E 的成本为 4，因此替换 (B, infinity,-)。
5	(A,0,-) (C,3,C) (D,4,C)	(B,6,E) (D,6,E)	通过 E 访问 B 的成本为 6，因此替换 (B, 9, B)。
6	(A,0,-) (C,3,C) (D,4,C) (B,6,E)		唯一剩下的节点是 D，再次执行步骤 2 到 6，我们将通过 E 从 A 到 D 的距离设置为 6，按照算法操作。因此，在下一次迭代中，添加 (D,6,E)
7	(A,0,-) (C,3,C) (D,4,C) (B,6,E) (D,6,E)		我们完成了。现在已经知道了到所有目的地的最短路径。

距离向量路由

距离向量算法是迭代的、异步的、分布式的。在距离向量中，每个节点都会从一个或多个直接连接的邻居收到一些信息。然后执行一些计算，并可能将计算结果分发给它的邻居。因此它是分布式的。它是交互式的，因为这种交换信息的过程会持续下去，直到邻居之间不再交换信息为止。

令 $dx(y)$ 是从节点 $x$ 到节点 y 的最小成本路径的成本。最小成本由 Bellman-Ford 方程描述

$Dx(y)=\min v\left\{C(x,V)+dv(y)\right\}$

其中公式中的 min v 是对 x 的所有邻居取最小值。从 x 到 v 行进后，再从 v 到 y 选择最短路径，从 x 到 y 的最短路径将是 C(x, V) + dv(y)。当我们开始前往某个邻居 v 时，从 x 到 y 的最小成本是在所有邻居 v 上取 C(x, V) + dv(y) 的最小值。

在距离向量算法中，每个节点 x 都维护路由数据。它应该维护

1. 连接到邻居的每条链路的成本，即对于连接节点 v，它应该知道 C(x,v)。
2. 它还维护其路由表，这实际上是 x 对其到 N 中所有目的地 y 的成本的估计。
3. 它还维护其每个邻居的距离向量。即 Dv = [Dv(y): y in N]

在分布式异步算法中，每个节点都会定期向其每个邻居发送距离向量的副本。当节点 x 收到其邻居的距离向量时，它会保存该向量并更新其距离向量，如下所示：

$Dx(y)=\min v\left\{C(x,v)+Dv(y)\right\}{\text{for each node }}y{\text{ in }}N$

当节点更新其距离向量时，它会将其发送到其邻居。邻居会执行相同的操作，此过程会持续进行，直到每个节点都没有信息要发送。

距离向量算法 [来自 kurose] 如下所示

在每个节点 x 上

让我们考虑以下示例：网络拓扑结构如下所示

现在我们将看看在步骤 1 后构建 R8 的路由表的步骤：在步骤 2 后：在步骤 3 后：这就是解决方案。对于节点 R8，现在路由表包含以下内容。

目标	下一跳	到目标的成本
R1	R5	5
R2	R5	4
R3	R3	4
R4	R5	5
R5	R5	2
R6	R6	2
R7	R7	3

无穷大计数问题

“网络中坏消息传播很慢”。假设 R1、R2、R3 和 R4 是以以下方式连接的四个路由器。

这些路由器要从它们自己到路由器 R4 的路由信息是 R1 R2 R3 3、R2 2、R3 1、R4。假设 R4 失败。那么由于 R3 和 R4 之间没有直接路径，因此 R3 到 R4 的距离变为无穷大。但是在下一次数据交换中，R3 会发现 R2 有一条到 R4 的路径，跳数为 2，因此它会将自己的条目从无穷大更新为 2 + 1 = 3，即 (3,R3)。在第二次数据交换中，R2 会发现 R1 和 R2 都到 R4 的距离为 3，因此它会将自己对 R4 的条目更新为 3 + 1 = 4，即 (4, R3)。在第三次数据交换中，路由器 R1 会将自己的条目更改为 4 + 1 = 5，即 ( 5, R2)。此过程将继续增加距离。以下是对此的总结表格。

交换	R1	R2	R3
0	3, R2	2, R3	1, R4
1	3, R2	2, R3	3, R3
2	3, R2	4, R3	3, R3
3	5, R2	4, R3	5, R3
… 无限计数 …

无穷大计数问题的解决方案

定义最大计数

例如，在 RFC 1058 [2] 中，将最大计数定义为 16。这意味着如果一切其他方法都失败，则无限计数将在第 16 次迭代时停止。

分隔范围

使用分隔范围。分隔范围意味着如果节点 A 通过节点 B 了解了到节点 C 的路由，则节点 A 不会在路由更新期间将 C 的距离向量发送到节点 B。

中毒反向

中毒反向是与分隔范围一起使用的附加技术。分隔范围经过修改，以便节点不会不发送路由数据，而是发送数据，但将链路成本设置为无穷大。带有中毒反向的分隔范围可防止仅涉及两个路由器的路由循环。对于涉及同一链路上更多路由器的循环，带有中毒反向的分隔范围将不足。