3. 架构
在本节中，我们描述了一种将商用交换机互连成胖树拓扑的架构。我们首先说明需要对路由表结构进行轻微修改的原因。然后我们描述如何为集群中的主机分配 IP 地址。接下来，我们引入两级路由查找的概念，以协助完成跨胖树多路径路由。然后介绍在每个交换机中填充转发表的算法。我们还描述了流分类和流调度技术作为多路径路由的替代方法。最后，我们介绍了一个简单的容错方案，并描述了该方案的热量和功耗特征。
3.1 动机
为了实现最大化网络的双工带宽，需要将任何给定 pod 的输出流量尽可能均匀地分布在核心交换机之间。路由协议如 OSPF2 通常以跳数作为“最短路径”的度量标准，在 k 元胖树拓扑结构（参见 2.2 节）中，不同 pod 的任意两台主机之间有 （k/2)2 条这样的最短路径，但只能选择了一条。因此，交换机将发送到给定子网的流量集中到单个端口，即使存在其他具有相同成本的选择。此外，由于 OSPF 消息到达时间交错，可能只选择少数核心交换机，甚至只选择一个作为 pod 之间的中间链路。这将导致这些点严重拥塞，并且无法利用胖树中的路径冗余
OSPF-ECMP 等扩展，除了不可用在候选的交换机类别之外，还会导致所需前缀数量爆炸性增长。一个较低层的 pod 交换机中需要为其他每个子网存储 （k/2) 个前缀；总计 k∗（k/2)2 个前缀。
因此，我们需要一种简单、细粒度的方法，利用拓扑结构在 pod 之间进行流量扩散。交换机必须能够识别需要均匀分布的流量类别，并给予特殊处理。为此，我们提出使用两级路由表，根据目标 IP 地址的低位字节来传播输出流量（参见第 3.3 节）。
3.2 编址
我们分配私有的 10.0.0.0/8 段内所有网络 IP 地址。我们遵循熟悉的四点形式，满足以下条件：pod 交换机的地址形式为 10.pod.switch.1，其中 pod 表示 pod 编号（ [0,k-1] ），switch 表示该交换机在 pod 中的位置（[0,k−1]，从左到右，从下到上）。我们给出核心交换机的地址形式为 10.k.j.i，其中 j 和 i 表示交换机在 （k/2)2 核心交换机网格中的坐标（每个都包含在 [1，（k/2)] 内，从左上角开始)。
主机的地址位于所连接的 pod 交换机之后；主机的地址格式为：10.pod.switch.ID，其中ID 是主机在该子网中的位置（[2,k/2+1]，从左到右）。因此，每个下层交换机负责 k/2 台主机的 /24 子网（k < 256）。图 3 显示了这种寻址方案的示例，对应于 k = 4 的胖树。尽管这种使用方式相对浪费可用地址空间，但它简化了路由表的构建，如下所示。而且，这种方案可以伸缩到 420 万台主机。
3.3 两级路由表
为了提供第 3.1 节提出的均匀分布机制，我们修改路由表以允许两级前缀查找。主路由表中的每个条目都可能有一个额外的指针，指向一个由（后缀，端口)条目组成的小型二级表。如果一级前缀不包含任何二级后缀，则终止，并且二级表可以被多个一级前缀指向。主表中的项是左旋的（即，/m 前缀掩码为 1m032−m)，而二级表中的项是右旋的（即， /m 后缀掩码为 032−m1m)。如果最长匹配前缀搜索得到非终止前缀，则在二级表中找到最长匹配后缀并使用。
两级结构会稍微增加路由表查找延迟，但硬件中前缀搜索的并行性应该只会带来很小的损耗（见下文）。因为这些表都非常小。如下图所示，任何 pod 交换机的路由表都不会超过 k/2 个前缀和 k/2 个后缀。
3.4 两级查找实现
我们现在描述如何使用内容可寻址存储器(Content-Addressable Memory, CAM) 在硬件中实现两级查找。CAM 用于搜索密集型应用，在查找位模式的匹配时，比算法实现更快。CAM 可以在单个时钟周期内并行搜索所有条目。查找引擎使用一种特殊的 CAM，称为三元 CAM (Ternary CAM, TCAM)。除了匹配 0 和 1 之外，TCAM 还可以在特定位置存储 —don’t care 位，使得它适合存储变长前缀，例如路由表中的前缀。缺点是，CAM 的存储密度很低，非常耗电，而且每比特的成本很高。然而，在我们的架构中，路由表可以实现在一个相对较小的 TCAM 中(k 个条目，每个 32 位宽)。
图 5 显示了我们提出的两级查找引擎的实现。TCAM 存储地址前缀和后缀，又索引一个 RAM，该 RAM 存储下一跳 IP 地址和输出端口。我们在数值较小的地址中存储左旋(前缀)条目，在较大的地址中存储右旋(后缀)条目。我们对 CAM 的输出进行编码，以便输出具有数值最小匹配地址的条目。这满足了特定的二级查找应用的语义：当数据包的目标 IP 地址同时匹配一个左旋项和一个右旋项时，则选择左旋项。例如，使用图 5 中的路由表，一个目标 IP 地址为 10.2.0.3 的数据包与左旋条目 10.2.0.X 和右旋条目 X.X.X.3 匹配。数据包正确地转发到端口 0。而目标地址为 10.3.1.2 的数据包只匹配右旋 X.X.X.2，并在端口 2 上转发。
3.5 路由算法
胖树的前两层交换机充当过滤流量扩散器；任何给定 pod 中的下层和上层交换机都具有该pod 中子网的终止前缀。因此，如果一个主机将一个数据包发送到另一个同一 pod 但不同子网的主机，那么该 pod 中的所有上层交换机都具有一个指向目标子网交换机的终止前缀。
对于所有其他输出的 pod 间流量，pod 交换机有一个默认 /0 前缀，带有一个与主机 ID(目标 IP 地址的最低有效字节)匹配的二级表。我们利用主机 ID 作为确定性熵的来源；它们将使流量均匀地上行分布到核心交换机的出口链路。这也将导致到同一主机的后续数据包遵循相同的路径，从而避免数据包重排。
在核心交换机中，我们为所有网络 ID 分配终止第一级前缀，每个前缀指向包含该网络的适当 pod。一旦数据包到达核心交换机，就只有一条链路到它的目标 pod，并且该交换机将包含该数据包的 pod 的终止 /16 前缀(10.pod.0.0/16, port)。一旦一个数据包到达它的目标 pod，接收的上层 pod 交换机也将包括一个(10.pod.switch.0/24,port)前缀，以将该数据包定向到其目标子网交换机，在那里它最终被交换到其目标主机。因此，流量扩散只发生在数据包传输的前半段。
设计分布式协议可以在每个交换机中增量地建立所需的转发状态。然而，为简单起见，假设一个完全了解集群互连拓扑的中央实体。这个中央路由控制负责静态地生成所有路由表，并在网络设置阶段将这些表加载到交换机中。动态路由协议还负责检测单个交换机的故障并执行路径故障转移(见第 3.8 节)。下面，我们总结了在 pod 和核心交换机上生成转发表的步骤。
Pod 交换机
在每个 pod 交换机中，我们为包含同一 pod 中的子网分配终止前缀。对于 pod 间流量，添加一个 /0 前缀和一个与主机 ID 匹配的二级表。算法 1 展示了为上层 pod 交换机生成路由表的伪代码。输出端口模数移位的原因是避免来自同一个主机、不同底层交换机的流量流向同一个上层交换机。
对于下层 pod 交换机，我们简单地省略了 /24 子网前缀步骤（第 3 行），因为该子网自己的流量被交换，并且pod 间和 pod 内流量应该在上层交换机之间均匀分割。
核心交换机
由于每个核心交换机连接到每个 pod(端口 i 连接到 pod i)，因此核心交换机只包含指向其目标 pod 的终止 /16 前缀，如算法 2 所示。该算法生成的表大小与 k 成线性关系。网络中没有交换机包含超过 k 个一级前缀或 k/2 个二级后缀的表。
路由示例
为了说明使用两级表的网络操作，我们给出一个数据包从源 10.0.1.2 到目标 10.2.0.3 的路由决策示例，如图 3 所示。首先，源主机的网关交换机（10.0.1.1）只有 /0 的第一级前缀匹配该数据包，因此会根据该前缀的二级表中的主机 ID 字节转发该数据包。在该表中，在该表中，数据包与 0.0.0.3/8 后缀匹配，该后缀指向端口 2 和交换机 10.0.2.1。交换机 10.0.2.1 也遵循相同的步骤，并转发到端口 3，连接到核心交换机 10.4.1.1。核心交换机将数据包与终止 10.2.0.0/16 前缀匹配，该前缀指向目标 pod 2 的端口 2 和交换机 10.2.2.1。这个交换机与目标子网属于同一个 pod，因此有一个终止前缀 10.2.0.0/24，该前缀指向负责该子网的交换机 10.2.0.1 的端口 0。从那里，标准切换技术将数据包传递到目标主机 10.2.0.3。
请注意，对于从 10.0.1.3 到另一个主机 10.2.0.2 的同时通信，传统的单路径 IP 路由将遵循与上述流程相同的路径，因为两个目标地都属于同一个子网。不幸的是，这将消除胖树拓扑的所有扇出优势。相反，我们的两级表查找允许交换机 10.0.1.1 基于两级表中的右旋匹配将第二条流转发到 10.0.3.1。
3.6 流分类
除了上述两级路由技术，我们还考虑了两种可选的动态路由技术，因为它们目前在一些商用路由器中可用[10,3]。我们的目标是量化这些技术的潜在好处，但承认它们会产生每个数据包的额外开销。重要的是，这些方案中维护的任何状态都是软性的，如果状态丢失，单个交换机可以回退到两级路由。
作为流量扩散到核心交换机的另一种方法，我们在 pod 交换机中执行流分类，并使用动态端口重分配，以克服可避免的局部拥塞情况(例如，当两条流竞争同一个输出端口时，即使另一个到目标具有相同成本的端口未使用)。我们将 流 定义为一系列的数据包，这些数据包具有相同头部字段子集(通常是源 IP 地址和目标 IP 地址、目标传输端口)。特别是 pod 交换机:
- 识别同一条流的后续数据包，并将它们转发到相同的输出端口。
- 周期性地重新分配一个最小数量的流输出端口，以最小化不同端口聚合流容量的差异。
第 1 步是针对数据包重排序的措施，第 2 步是在流大小动态变化的情况下，保证上行端口的流公平分布。第 4.2 节更详细地描述了流分类器的实现和流分布启发式方法。
3.7 流调度
已有研究表明，网络流量的传输时间和突发长度分布呈长尾分布，其特征是很少长生命周期的大数据流(占大部分带宽)，而有许多短生命周期的小数据流。本文认为路由大型流在确定网络可实现的双工带宽方面，起着至关重要的作用，因此需要进行特殊处理。在这种流管理的替代方法中，我们调度大数据流以尽量减少彼此的重叠。中央调度器根据网络中所有活动的大数据流的全局信息做出此选择。在这个初始设计中，我们仅考虑每台主机一次只有一条大数据流的情况。
3.7.1 边缘交换机
与之前一样，边缘交换机最初会在本地将新流分配给负载最少的端口。然而，边缘交换机还会检测任何规模增长超过预定义阈值的输出流，并定期向指定所有活动大数据流的源和目标的中央调度器发送通知。这表示边缘交换机将该流放置非竞争路径的请求。
请注意，与第 3.6 节不同的是，该方案不允许边缘交换机独立地重新分配流的端口，无论其大小。中央调度器是唯一有权下令重新分配的实体。
3.7.2 中央调度器
中央调度器(可能是复制的)跟踪所有活动的大数据流，并试图为它们分配不冲突的路径。调度器维护网络中所有链路的布尔状态，表示它们是否可用来承载大数据流。
对于 pod 间流量，回想一下，网络中任意一对主机之间都有 (k/2)2 条可能的路径，每条路径对应一台核心交换机。当调度器收到新流的通知时，它线性搜索核心交换机，以找到对应路径组件不包含预留链路的交换机。一旦找到这样的路径，调度器将这些连接标记为保留，并通知源 pod 相关的下层和上层交换机及流选择的路径相对应的正确输出端口。对pod 间的大数据流执行类似的搜索；这次是通过上层 pod 交换机找到一条无竞争路径。调度器垃圾收集最后更新时间超过给定时间的流，清除它们的预留标记。请注意，边缘交换机不会阻塞并等待调度器执行该计算，但一开始会像处理其他流一样处理大数据流。
3.8 容错
任意一对主机之间可用路径的冗余使得胖树拓扑具有容错能力。我们提出了一种简单的故障广播协议，该协议允许交换机在下游一两跳处绕过链路或交换机故障。
在该方案中，网络中的每台交换机都与其每个邻居维护一个双向转发检测会话(BFD)，以确定链路或邻居交换机何时发生故障。从容错的角度来看，可以承受两类故障：(a) 在 pod 间的下层交换机和上层交换机之间，(b) 在核心交换机和上层交换机之间。显然，较低层的交换机故障将导致直接连接的主机断开连接；叶子上的冗余交换机元件是容忍这种故障的唯一方法。我们在这里描述链路故障，因为交换机故障会触发相同的 BFD 警报，并引发相同的响应。
3.8.1 下层到上层交换机
当下层和上层交换机之间发生链路故障时，会影响三类流量：
- 从下层交换机发出的 pod 间和内的输出流量。在这种情况下，本地流分类器将该连接的“成本”设置为无穷大，并且不为其分配任何新流，并选择另一个可用的上层交换机。
- 使用上层交换机作为中介的 pod 内流量。作为响应，该交换机广播一个标签，通知同一 pod 中的所有其他底层交换机链路故障。在分配新流时，这些交换机将检查预期的输出端口是否属于这些标记，并尽可能规避。
- 进入上层交换机的 pod 间流量。连接到上层交换机的核心交换机将其作为访问该 pod的唯一入口，因此上层交换机向其所有核心交换机广播此标记，表明其无法将流量传送到下层交换机的子网。这些核心交换机依次将此标签镜像到它们连接到其他 pod 的所有上层交换机。最后，上层交换机在将新数据流分配给该子网时，规避单个受影响的核心交换机。
3.8.2 上层到核心交换机
当上层交换机与核心交换机之间发生链路故障时，会影响两类流量：
- pod 间的输出流量，本地路由表将受影响的链路标记为不可用，并在本地选择另一台核心交换机。
- pod 间的输入流量。在这种情况下，核心交换机向它直接连接的所有上层交换机广播一个标记，表示它无法将流量传送到整个 pod。和之前一样，上层交换机在分配流向pod 的数据流时，会避免使用核心交换机。
自然地，当故障链路和交换机恢复并重新建立 BFD 会话时，上述步骤将被反转以抵消其效果。此外，调整第 3.7 节的方案适应链路和交换机故障相对简单。调度器将任何被报告为 down 的链路标记为繁忙或不可用，从而取消任何包含它的路径的候选资格，最终大型流绕过故障路由。
