摘要
当今的数据中心可能包含数万台计算机，具有巨大的总带宽需求。网络架构通常是由路由器和交换机等元件构成的一棵树，网络层次结构越靠上，设备越专业化、越昂贵。不幸的是，即使部署最高端的 IP 交换机/路由器，所得拓扑也只能支持网络边缘可用总带宽的 50%，同时仍然产生巨大的成本。数据中心节点之间的非均匀带宽，使应用程序设计复杂化，并限制了整个系统性能。
在本文中，我们展示了如何利用大量商用以太网交换机来支持由数万个元件组成的集群的全部总带宽。与商用计算机集群在很大程度上取代了更专业化的 SMP 和 MPP 类似，我们认为适当架构和互连的商用交换机，能以更低的成本提供比现有高端解决方案更高的性能。我们的方法不需要对终端主机网络接口、操作系统或应用程序进行任何修改；关键是，它完全后向兼容以太网、IP和TCP。
1. 介绍
越来越多的专业知识使许多机构能够以经济高效的方式运用兆亿次浮点运算能力和兆字节存储能力。数万台 PC 组成的集群在最大机构中并不少见，在大学、研究实验室和公司中千节点集群日益普遍。重要应用类别包括科学计算、金融分析、数据分析和仓储以及大规模网络服务。
如今，大型集群中主要瓶颈通常是节点间通信带宽。许多应用程序必须与远程节点交换信息才能继续进行本地计算。例如，MapReduce 必须执行大量数据洗牌（shuffling），以传输 map 阶段输出，然后才能继续进行 reduce 阶段。在基于集群的文件系统上运行的应用程序通常需要远程节点访问才能继续执行其 I/O 操作。搜索引擎查询通常需要与集群中存储倒排索引的每个节点进行并行通信，以返回最相关的结果。甚至逻辑上不同的集群之间，通常也存在重要的通信需求，例如，从负责构建索引的站点更新各个执行搜索的集群的倒排索引时。互联网服务越来越多地采用面向服务的架构，检索单个网页可能需要与远程节点上运行的数百个单独子服务进行协调和通信。最后，并行科学应用程序的重大通信需求众所周知。
大型集群的通信矩阵有两种高层选择。一种选择是利用专用硬件和通信协议，如 InfiniBand 或 Myrinet。虽然这些解决方案可以伸缩到具有高带宽的数千个节点的集群，但它们不利用商用零件（因此更昂贵），并且与 TCP/IP 应用程序不兼容。第二种选择是利用商用以太网交换机和路由器来互连集群机器。这种方法支持熟悉的管理基础设施以及未修改的应用程序、操作系统和硬件。不幸的是，集群带宽不能很好的随着集群规模伸缩，并且实现最高水平带宽会随着集群规模呈非线性增长。
由于兼容性和成本原因，大多数集群通信系统遵循第二种方法。然而，在大型集群中，由于通信模式的不同，通信带宽可能会被超分使用。也就是说，连接到同一物理交换机的两个节点可能能够以全带宽（例如 1Gbps）进行通信，但在交换机之间移动，可能跨越多个层次结构层次，可用带宽可能会严重受限。解决这些瓶颈需要非商用解决方案，例如大型 10Gbps 交换机和路由器。此外，典型的沿着相互连接的交换机树的单路径路由，意味着整个集群的带宽受到通信层次结构根部可用带宽的限制。即使我们处于一个转折点，10Gbps 技术正在变得具有成本竞争力，最大的 10Gbps 交换机仍然产生巨大的成本，并且仍然限制了最大集群的整体可用带宽。
在这种情况下，本文的目标是设计一种数据中心通信架构，满足以下目标：
- 可伸缩的互连带宽：数据中心中的任意主机应该能够以其本地网络接口的全带宽与网络中的任何其他主机通信
- 规模经济：正如商用个人电脑成为大型计算环境的基础一样，我们希望利用同样的规模经济，使廉价的现成以太网交换机成为大型数据中心网络的基础。
- 向后兼容性：整个系统应该后向兼容运行以太网和 IP 的主机。也就是说，现有的数据中心几乎都是利用普通以太网和运行IP，应该能够在不作任何修改的情况下利用新的互联架构。
通过在胖树（fat-tree）结构中互连商用交换机，可以实现由数万个节点组成的集群的双工带宽。具体来说，我们的架构实例使用 48 端口以太网交换机，能够为多达 27,648 个主机提供全带宽。通过完全使用商用交换机，我们实现了比现有解决方案更低的成本，同时提供了更多的带宽。我们的解决方案不需要对终端主机进行任何更改，完全兼容 TCP/IP，只对交换机本身的转发功能进行适度修改。我们还预计，一旦 10 GigE 交换机在集群边缘商用，我们的方法将是唯一一种能够为大型集群提供全带宽的方法，因为目前没有任何更高速度以太网替代方案（无论成本多少）。即使更高速度以太网解决方案可用，它们最初也会以巨大的成本得到小的端口密度。
2. 背景
2.1 当前数据中心网络拓扑
我们进行了一项研究，以确定当前数据中心通信网络的最佳实践。我们在这里关注利用以太网和 IP 的商用设计；我们在第 7 节讨论我们的工作与替代技术的关系。
2.1.1 拓扑
当前典型的架构由两层或三层树形交换机或路由器组成。三层设计（见图 1）树的根部是核心层，中间是聚合层，树的叶子处是边缘层。两层设计只有核心和边缘层。通常，两层设计可以支持 5K 到 8K 台主机。由于我们的目标大约是 25,000 台主机，因此我们将注意力聚焦在三层设计上。树叶处的交换机具有一些 GigE 端口（48-288）以及一些 10 GigE 上行链路到一个或多个网络元件层，这些元件聚合和传输叶子交换机之间的数据包。在层次结构的更高层，有具有 10 GigE 端口（通常为 32-128）和显著交换能力的交换机来聚合边缘之间的流量。
术语“：交换机” 指代执行二层交换和三层路由的设备。
假设使用两种类型的交换机，它们分别代表端口密度和带宽方面的高端型。前者，用于树的边缘，是一个带有四个 10 GigE 上行链路的 48 端口 GigE 交换机。对于通信层次结构的更高层，我们考虑 128 端口 10 GigE 交换机。两种类型的交换机都允许所有直连的主机彼此相互通信。
2.1.2 超分
许多数据中心设计引入超分作为降低设计总成本的手段。我们定义超分这个术语为终端主机之间最坏情况下可实现的总带宽与特定通信拓扑双工带宽之比。超分比为 1:1 表示所有主机可与任意其他主机以其网络接口的全带宽（例如，商用以太网设计中的 1 Gb/s）进行通信。超分值为 5:1 意味着只有 20% 的可用主机带宽可用于某些通信模式。典型设计超分比为 2.5:1 （400 Mbps) 至 8:1 （125 Mbps)。尽管对于 1 Gb/s 的以太网，可以实现超分比为 1:1 的数据中心，但正如我们在第 2.1.4 节中所述，这种设计的成本通常是令人望而却步的，即使对于中等规模的数据中心也是如此。当超越单台交换机时，为 10 Gb/s 的以太网实现双工带宽目前是不可能的。
2.1.3 多路径路由
在大型集群中，实现任意主机之间的全带宽需要一个具有多个核心交换机的“多根”树（见图 1）。这反过来需要多路径路由技术，例如 ECMP。目前，大多数企业核心交换机都支持 ECMP。如果不使用 ECMP，则仅使用单根核心的 1:1 超分的集群最大大小将受到限制，最多为 1,280 个节点（对应于单个 128 端口 10 GigE 交换机的带宽）。
为了利用多条路径，ECMP 对流进行静态 负载分割 。在进行分配决策时，并未考虑流带宽，即使是简单的通信模式也可能导致超分。此外，当前的 ECMP 实现将路径的多样性限制在 8-16 之间，通常比大型数据中心所需的高双工带宽多样性更少。此外，路由表条目标数量随着考虑的路径数量成倍增长，这增加了开销与查找延迟。
2.1.4 成本
为大型集群构建网络互连的成本极大地影响了设计决策。正如我们上面所讨论的，超分通常是为了降低总成本。在这里，使用当前最佳实践，我们给出了不同数量主机和超分配置的粗略成本。假设每个边缘的 48 端口 GigE 交换机的成本为 $7,000，聚合和核心层中的 128 端口 10 GigE 交换机的成本为 $700,000。在这些计算中，不考虑布线成本。
图 2 绘制了以百万美元为单位的成本与 x 轴上终端主机总数之间的关系。每条曲线代表目标超分比。例如，连接 20,000 台主机，并在所有主机之间提供全带宽的交换硬件约为 $37M。3∶1 超分比的曲线绘制了连接终端主机的成本，任意终端主机之间通信可用的最大带宽将限制在约 330 Mbps。图中还包括，胖树架构超分比为 1:1 的交付成本，以进行比较。
总的来说，我们发现使用现有技术为大型集群提供高水平带宽会产生巨大成本，而且基于胖树的集群互连在以适中的成本提供可伸缩带宽方面潜力巨大。然而，在某种意义上，图 2 低估了在构建数据中心架构中使用最高端的组件的难度和成本。2008 年，10 GigE 交换机即将成为商用零件；GigE 与 10 GigE 交换机相比，每端口每比特/秒价格差约为 5 倍，并且这种差值还在继续缩小。为了探究历史趋势，在表 1 中展示了特定年份中使用可用的最高端的交换机所支持的最大集群配置的成本。历史研究数据来自于各高端 10 GigE 交换机供应商 2002 年、2004 年、2006 年和 2008 年的产品公告。
使用我们的发现构建当年技术能够支持的、超分比为 1:1 的、最大集群配置。表 1 显示了特定年份可用的最大 10 GigE 交换机；在核心和聚合层中使用这些交换机进行分层设计。表格还显示了该年份可用的最大商用 GigE 交换机；在胖树的所有层和分层设计的边缘层中使用这些交换机。
传统技术采用高端交换机支持的最大集群大小一直受到可用端口密度的限制，直到最近。此外，当 10 GigE 交换机最初可用时，高端交换机成本让人望而却步。请注意，我们对传统层次结构的计算比较慷慨，因为聚合层的商用 GigE 交换机直到最近才有必要的 10 GigE 上行链路。相比之下，基于胖树拓扑的集群具有很好的可伸缩性，总成本下降的更早且更快（因为它更早地遵循商用定价趋势）。此外，在胖树拓扑中也不需要高速上行链路。
最后，值得注意的是，今天，技术上不可能构建一个具有 27,648 个节点，节点之间仅有 10 Gbps 带宽的集群。另一方面，胖树交换架构采用近乎商用的 48 端口 10 GigE 交换机，产生超过 6.9 亿美元的成本。虽然在大多数情况下可能成本过高，但最重要的事实是，甚至不可能使用传统聚合与高端交换机构建这样一个配置，因为今天没有产品，甚至没有以太网标准用于速度超过10 GigE 的交换机。
2.2 Clos 网络/胖树
今天，商用和非商用交换机之间的价格差提供了强大的动力，用许多小型商用交换机取代少量大型、昂贵的交换机构建大规模通信网络。五十年多前，电话交换机类似的趋势促使 Charles Clos 设计了一种网络拓扑，通过适当地互连较小的商用交换机为许多终端设备提供高水平带宽。
本文采用一种特殊的 Clos 拓扑称为胖树（fat-tree）来互连商用以太网交换机。我们将 k 元胖树组织如图 3 所示。有 k 个 pod ，每个 pod 包含两层 k/2 台交换机。下层的 k 端口交换机直接连接到 k/2 台主机。剩余的 k/2 个端口连接到层次结构中聚合层的 k 个端口中的 k/2 个。
有 （k/2)2 台 k 端口核心交换机。每个核心交换机都有一个端口连接到 k 个 pod 。任何核心交换机的第 i 个端口连接到 pod i，使得每个 pod 交换机中以 （k/2) 步幅的连续端口连接到核心交换机。一般来说，k 端口交换机构建的胖树支持 k3/4 个主机。在本文中，我们专注于 k = 48 及以下的设计。我们的方法可以推广到任意 k 值。
胖树拓扑的一个优点是，所有交换元件都是相同的，使我们能够利用廉价的商用部件来实现通信架构中的所有交换器。此外，胖树是 _可重排非阻塞的_，这意味着对于任意通信模式，都有一组路径饱和拓扑中终端主机的所有可用带宽。由于需要防止 TCP 流的数据包重排，在实践中实现 1:1 的超分配置比较困难
图 3 显示了 k = 4 的简单胖树拓扑。连接到同一台边缘交换机的所有主机形成自己的子网。因此，所有流向同一子网的流量都被交换，而所有其他流量都被路由。
例如，由 48 端口千兆交换机构建的胖树包括 48 个 pod，每个 pod 包含一个边缘层和一个汇聚层，每个汇聚层有 24 台交换机。每个 pod 中的边缘交换机分配 24 台主机。网络支持 27,648 台主机，由 1,152 个子网组成，每个子网 24 台主机。不同 pod 中的任意两个主机之间有 576 条等价路径。部署这种网络架构的成本为 $8.64M，而前面描述的传统技术为 $37M。
2.3 总结
鉴于我们的目标网络架构，在本文的其余部分，我们解决在以太网部署中采用这种拓扑的两个主要问题。首先，IP/以太网通常在每个源和目标之间建立单一路由路径。即使是简单的通信模式，单一路径路由也会迅速导致胖树上行下行的瓶颈，严重限制整体性能。我们描述了简单的 IP 转发扩展，以有效利用胖树的高扇出可用性。其次，在大型网络中，胖树拓扑会增加布线的复杂性。在某种程度上，这种开销是胖树拓扑固有的，但在第6节中，我们将介绍减轻这种开销的封装和放置技术。最后，我们在 Click 中构建了第 3 节所述架构的原型。第 5 节中给出的初步性能评估证实了我们的方法在小规模部署中潜在的性能优势。
