路由器硬件
路由器的作用是什么？
路由器运行某种路由协议来填充转发表。
当数据包进入时，路由器会查看其目的 IP，并使用转发表选择一条链路来转发数据包。请记住，转发表中可能包含地址范围。
到目前为止，我们在图表中把路由器画成盒子的样子。实际上，路由器是一种专门优化用于执行路由和转发任务的专用计算机。在本节中，我们将探讨路由器内部的硬件。
路由器在哪里？
在现实生活中，家庭和办公室都有小型路由器，用于将主机连接到互联网。那么所有这些路由器是如何相互连接的呢？
托管机房或电信酒店是多个互联网服务提供商（ISP）安装路由器以相互连接的建筑物。这些建筑物专门设计有电力和冷却基础设施，ISP 可以租用空间安装路由器，并将其与同一建筑物内的其他路由器连接。
在电信酒店内部，路由器被堆叠在机架中（高 6-7 英尺，宽 19 英寸）。
路由器的尺寸和容量
路由器有各种尺寸，具体取决于用户需求。家用路由器只为少数用户转发流量，转发表只有一个默认条目。工业级路由器可能需要为数千名客户转发流量，因此具有庞大的转发表。
我们可以通过多种方式衡量路由器的大小。我们可以考虑它的物理尺寸、物理端口数量以及带宽。
我们可以通过物理端口数量乘以每个物理端口的带宽来衡量路由器的容量。物理端口的速度或带宽通常称为其线速。
并非所有物理端口都需要具有相同的线速。例如，现代家用路由器可能有 4 个物理端口，每个端口的发送速度为 100 Mbps，还有 1 个物理端口的发送速度为 1 Gbps。该路由器的总容量为 1.4 Gbps。
ISP 使用的现代最先进的路由器可能每个物理端口的线速高达 400 Gbps。
这种路由器包含多个可更换的线卡，每个线卡包含一组物理端口。一台现代路由器可能有 8 个线卡，每个线卡有 36 个物理端口，总共 288 个物理端口。
288 个物理端口，每个端口的带宽为 400 Gbps，这使得我们的路由器总容量达到 115.2 Tbps。
这种路由器的成本可能高达 100 万美元。将路由器拆分为线卡，使我们能够在需要更多容量时安装更多线卡。
未来，下一代路由器将拥有 800 Gbps 的物理端口。路由器的物理空间有限，因此现代改进的重点是提高每个端口的速度，而不是增加端口数量（在相同空间内塞入更多端口也很困难，因为受到电力和冷却的限制）。
随着用户需求的增长（例如，视频质量从 720p 提升到 8K = 8000p），路由器容量多年来一直在增加。2010 年，最先进的路由器容量为 1.7 Tbps，在过去十年中增长了 100 倍。这种改进在很大程度上来自链路速度的提升，从 2010 年的 10 Gbps 到 2016 年左右的 100 Gbps，再到如今的 400 Gbps。由于摩尔定律放缓以及高速传输信号面临的物理挑战等限制，这些改进开始放缓。下一次向 800 Gbps 的改进仅为 2 倍增长（相比之下，早期有 10 倍和 4 倍的增长）。
数据平面、控制平面、管理平面
路由器的硬件和软件组件在概念上可以分为三个平面。数据平面主要负责转发数据包。每次有数据包到达并需要转发时，都会使用数据平面。数据平面在本地运行，无需与其他路由器协调。
控制平面主要负责与其他路由器通信并运行路由协议。这些路由协议的结果（例如转发表）可被数据平面使用。每次网络拓扑发生变化（例如添加或删除链路时），都会使用控制平面。
由于数据平面和控制平面在不同的时间尺度上运行，并且运行不同的协议，因此路由器的硬件和软件针对不同的任务进行了优化。实际上，数据包到达的频率远高于网络拓扑变化的频率。因此，数据平面经过优化，可非常快速地执行非常简单的任务（表查找和转发）。相比之下，控制平面经过优化，可执行更复杂的任务（重新计算网络中的路径）。
管理平面用于告知路由器要做什么，并查看它们在做什么。系统和人员通过管理平面与路由器交互，以配置和监控路由器。这是操作员可以配置设备功能的地方。应为每个链路分配什么成本？应运行什么路由协议？这些都需要操作员手动决定。
除了配置之外，管理平面还提供监控工具。每条链路上承载多少流量？路由器的任何物理组件是否出现故障？这些信息可以反馈给操作员。
管理平面是操作员从设备外部访问和与路由器交互的主要地方。如果操作员使用某些代码与路由器交互，我们通常也将其视为管理平面的一部分。
数据平面和控制平面实时运行，处理数据包的时间尺度分别为纳秒级（数据平面）和秒级（控制平面）。相比之下，管理平面的工作时间尺度为几十到几百秒。如果操作员更改配置，路由器可能需要花费时间执行验证检查和处理配置，然后才能完全应用更新。
网络管理系统（NMS） 是操作员运行的用于与路由器交互的某种软件。该软件计算网络配置（可能需要操作员手动输入），然后将该配置应用于路由器。路由器会发布系统可用于与路由器通信的 API。
网络管理系统还允许从路由器读取遥测数据（统计信息和运行状态）。
网络管理系统的复杂性取决于操作员想要实现的目标。
运行路由器需要这三个平面。如果我们只有数据平面而没有控制平面，我们可以转发数据包，但不知道要将它们转发到哪里。
路由器内部有什么？
我们将路由器定义为执行路由任务的计算机，但实际上，在路由器内部，有许多更小的计算机（例如 CPU、专用芯片）协同工作来执行路由任务。
构成工业级路由器的物理架子称为机箱。在机箱内部，我们安装了许多线卡，每个线卡上有多个物理端口。每个物理端口可用于输入或输出。
路由器中的每个物理端口都必须连接到其他每个物理端口（包括同一线卡和其他线卡上的端口）。你可能通过一个端口接收数据包，然后需要从另一个线卡上的端口转发出去。
将每个端口与其他每个端口进行物理布线效率非常低。相反，我们有一个线路结构（fabric）来连接线卡。每个线卡也有芯片，以促进与线路结构的连接。
与所有线卡分开的是一个带有自己 CPU 的控制器卡，它与其他路由器通信以执行路由协议。在运行某种算法计算路径后，控制器会用正确的转发表条目对转发芯片进行编程。
每个线卡都有自己的本地 CPU 来控制线卡功能（例如填充转发表）。线卡还具有用于数据包基本处理的硬件（例如在发送出去之前更新其 TTL）。线卡包含一个或多个专门为转发优化的芯片。
我们也可以按不同的平面对路由器组件进行分类。数据平面由线卡上的转发芯片、连接线卡的线路结构以及将线卡连接到线路结构的结构芯片支持。控制平面和管理平面由控制器卡支持。
这是一张工业级路由器的图片。该路由器有 6 个插槽，其中 4 个装有线卡，另外 2 个装有控制器卡。还有一个用于冷却的风扇托盘。连接线卡的线路结构在背面（未显示）。
数据包类型
最常见的数据包是用户数据包，包含来自终端主机的数据。当路由器收到此数据包时，转发芯片首先读取头部中的目的字段，并查找相应的端口。如果该端口在另一个线卡上，数据包会通过线路结构发送到相应的线卡。一旦数据包到达正确的线卡，就会通过相应的端口发送出去。
有些数据包是控制平面流量，其目的地是路由器本身。特别是，当我们运行路由协议时，通告会发送到路由器本身。当路由器收到此数据包时，转发芯片会将数据包发送到控制器卡。控制器卡上的 CPU 会对数据包进行相应处理。
最后一种流量是 ** punt 流量 **。这些是用户数据包，但需要一些额外的特殊处理。例如，如果我们收到一个 TTL 为 1 的数据包，该数据包已过期，我们不应转发它。我们可能还需要向发送方发送错误消息。当路由器收到 punt 数据包时，转发芯片会将数据包 “punt” 到控制器卡进行特殊处理。
路由器的扩展
为什么我们的路由器要分解为这种特定的架构，带有转发芯片和控制器卡？难道不能在通用 CPU 上运行所有功能吗？
问题在于，最先进的路由器需要在极大的规模下运行。以现代 400 Gbps 的速度计算，假设是 64 字节的数据包，我们每个端口每秒必须处理 7.81 亿个数据包。对于 36 个端口，整个路由器必须每秒处理 560 亿个数据包（实际上，如果某些数据包更大，这个数字可能会略低）。
这种规模在通用 CPU 上的软件中是无法实现的。为了理解这个规模，假设我们尝试编写一个转发数据包的程序，并在 CPU 上运行该程序，那么每秒能转发 10 万个数据包（每个数据包 10 微秒）就已经很令人印象深刻了。而最先进的路由器大约需要每 10 纳秒处理一个数据包。即使是最优化的软件也无法以这种规模处理数据包。相反，我们需要直接在硬件中实现路由器功能。
通过将路由器分为专门的数据平面线卡和控制平面控制器卡，我们创建了快速路径和慢速路径。快速路径仅涉及转发硬件，并针对以极高速率转发数据包进行了优化。带有控制 CPU 的慢速路径仅在必要时使用，大多数数据包通过快速路径发送。这些专用组件使路由器效率更高（使用更少的电力、成本更低、占用更少的物理空间）。
线卡功能
线卡收到数据包时需要执行哪些具体任务？
首先，线卡需要接收信号（例如光信号、电信号）并将其解码为组成数据包的 0 和 1。这是线卡的PHY部分，负责物理层（第 1 层）功能。
一旦我们有了一系列 0 和 1，就必须读取这些位并对其进行解析（例如，找出哪些位对应于 IP 头部）。我们可能还需要执行其他链路层操作（例如，如果一条链路连接到两台以上的机器）。线卡的MAC部分负责链路层功能（第 2 层）。
现在我们有了一个 IP 数据包，就必须对其进行解析。例如，我们需要检查数据包是 IPv4 还是 IPv6。然后，我们必须读取目的地址并执行转发查找（或者发现需要将数据包 punt）。
我们可能还需要更新各种 IP 头部字段。我们必须减少 TTL。由于我们更新了头部，我们还需要更新头部中的校验和。我们可能还需要更新其他字段，如选项和分片（在 IP 头部部分将详细讨论）。
所有这些功能都必须在几纳秒内完成。即使我们以某种方式在一个时钟周期内完成所有处理，线卡仍必须以 0.2 GHz 运行。实际上，所有这些操作都需要不止一个时钟周期。此外，我们必须对於线卡上的每个端口执行所有这些处理（一个转发芯片支持所有端口）。
为了使这些操作快速进行，转发芯片针对它们执行的有限任务（例如读取数据包头、表查找）进行了极其专门的优化。你不能编写通用程序并在转发芯片上运行。如果数据包需要转发芯片不支持的功能，我们总是可以将数据包 punt 到控制器卡上的通用 CPU。
简单的操作，如递减 TTL，很容易在硬件中实现。更复杂的操作，如特殊选项，通常需要 punt 到控制器卡。在现代互联网中，我们尽可能避免使用特殊选项，以最大限度地利用快速路径并避免 punt（如果所有内容都 punt，控制器卡将不堪重负）。
结构互连芯片也有类似的专门设计。这些芯片帮助通过线路结构将数据包发送到其他线卡。这些芯片往往是整个路由器中最专门化和性能最高的芯片。
数据包排队
TODO
高效的转发表查找
我们现在知道，路由器需要以极高的速率在转发表中执行查找。一个主要挑战是，我们的表条目除了单个 IP 地址外，还可以包含 IP 地址范围（192.0.1.0/24）。此外，这些范围可能重叠（一个目的地可能匹配多个范围）。我们如何使查找速度极快？
理想情况下，为了获得最大速度，转发表可以包含每个目的地的一个条目，没有范围。然后，我们只需要获取数据包中的目的地，并查找精确匹配以了解下一跳。
为了实现这种理想方法，我们可以将每个范围扩展为其各个 IP 地址。例如，24 位前缀 192.0.1.0/24 的条目将扩展为 256 个条目。
这在空间上是低效的（请记住，这是在硬件中实现的）。此外，如果路由发生变化，我们将不得不更新表中的大量条目。扩展路由是行不通的，因此我们必须处理范围。
回想一下，转发表查找是使用最长前缀匹配来完成的。如果多个范围与目的地匹配，我们选择最具体的范围（固定前缀位最多的）。如果没有范围匹配，我们选择默认路由（.，0.0.0.0/32，匹配所有目的地）。如果没有默认路由，我们丢弃数据包。
我们如何在硬件中高效地实现最长前缀匹配？
TODO 重写以匹配图表
首先，为了可读性，我们将所有范围和目的地都改写为二进制。然后，我们逐位扫描目的地位。对于前 21 位，所有四个范围都匹配，因此所有四个范围仍然有效。然后，第 22 位是 1。第一行在第 22 位是 0，因此我们可以排除这一行（不匹配）。其他三行在前 22 位仍然匹配，因此它们仍然有效。
接下来，我们检查第 23 位，也是 1。第二行和第三行在第 23 位是 0，因此我们排除它们（不匹配）。第四行仍然匹配。
此时，我们可以确认第四行是完全匹配的，因为它是 23 位前缀，且所有 23 位都匹配。不需要进一步检查这一行。
我们继续逐位检查，排除不匹配的行，并确认完全匹配的行。最终，我们有一个或多个匹配的行，我们选择前缀最长的匹配。
如果我们天真地实现这一点，那么对于每一位，我们都必须将该位与转发表中的每个条目进行匹配。渐近运行时间将随转发表中的条目数量而扩展。我们能做得更好吗？
使用字典树（Tries）进行高效查找
回想一下数据结构课程（如加州大学伯克利分校的 CS 61B），你可能记得字典树是一种高效存储键为字符串（在本例中为位串）的映射的数据结构。字典树通过一次写出键的一个字符（位）来存储键值对，这实现了高效的最长前缀匹配。
例如，这个字典树存储了一个从单词到数字的映射。如果你不记得字典树，也没关系。
如果我们想找到最长前缀，就像之前一样，我们一次读取单词的一个字母。这使我们能够沿着树从根到叶追踪一条路径。沿着这条路径，我们查找表中的所有前缀（有颜色的节点），并选择最长的前缀。
我们可以对转发表使用类似的方法。字典树的每一层代表 IP 地址中的一位。第 0 层是根（空字符串），第 1 层代表第一位，第 2 层代表第二位，依此类推。
字典树中的每个节点代表一个前缀。例如，2 位前缀 11 * 在树的第二层，3 位前缀 100 在树的第三层。该字典树包含所有可能的 3 位前缀。如果某个前缀在转发表中，我们在相应的节点中写入下一跳。如果该前缀不在转发表中，我们不在节点中写入任何内容（在图片中为白色）。
沿着树追踪路径可以在恒定时间内完成。我们每个目的地址的位访问一个节点，而目的地址总是 32 位（恒定的）。即使转发表有数百万个条目，我们也只会访问 32 个节点。
如果没有重叠范围，每个有效前缀对应一个叶节点。如果范围重叠，非叶节点也可能是有效前缀。
和以前一样，我们使用目的地址沿着树追踪路径。如果我们走出了树，我们提前停止，并从我们访问过的节点中选择最长的前缀。
作为一个小优化，当我们沿着树向下走时，我们可以跟踪到目前为止看到的最长前缀匹配。这将始终是最近的匹配，因为随着我们向下移动树，前缀会变长。如果我们走出了树，我们使用最长前缀匹配（我们找到的最近的匹配）。
请注意，默认路由将存储在根节点（0 长度前缀）。我们沿着树向下走的算法确保只有在没有其他前缀匹配时，我们才使用默认路由。
所有路由器都有某种形式的最长前缀匹配功能，但有些使用比其他更先进的解决方案。例如，我们可以基于现实世界的互联网假设添加启发式和优化。有些目的地可能更受欢迎，因此我们可能希望更高效地查找它们。有些端口可能用于更多范围。现代互联网对于前缀大小有一些约定（例如，到其他网络的路由的最长 IPv4 前缀是 24 位）。我们也可以为更新转发表进行优化。
（注：文档部分内容可能由 AI 生成）