B4及之后：为谷歌软件定义WAN的可用性和扩展管理层次化、划分和不对称

本文为SIGCOMM 2018会议论文，由谷歌提供。
笔者翻译了该论文。由于时间仓促，且笔者英文能力有限，错误之处在所难免；欢迎读者批评指正。
本文及翻译版本仅用于学习使用。如果有任何不当，请联系笔者删除。
如需转载，请联系笔者。

摘要

私有广域网对企业、电信和云提供商的运维来说正变得越来越重要。例如，谷歌的私有软件定义广域网B4的连接规模和增长速度超过其到公共因特网的连接。本文中，我们介绍了B4系统的5年演进过程。我们描述了提供由尽力而为的内容拷贝服务到电信级可用性逐渐转变的技术，同时B4系统扩展到适应100倍以上的通信量。我们的关键挑战是均衡以下因素导致的矛盾：可扩展性要求的层次化、可用性要求的网络划分以及任何大规模网络构建和运维所固有的容量不对称。我们讨论了解决这一矛盾的方法：1）我们为水平和垂直软件扩展设计了一种定制的层次化网络拓扑，2）我们在层次化拓扑中使用一种创新的无需数据包封装的流量工程算法来解决固有的容量不对称，和3）我们通过两阶段匹配/哈希重构了交换机转发规则，以解决一定规模下的不对称网络故障问题。

1 引言

图1： B4全球拓扑。每个标记点表明单个站点或多个地理位置接近的站点。截止到2018年1月，B4包含33个站点。

B4[18]是谷歌用来连接其全球数据中心的私有骨干网络（见图1）。它所采用的软件定义网络控制栈具有灵活的和集中的网络管理能力，带来极大的成本和革新效益。具体地讲，使用集中式流量工程（TE）基于利用率和故障动态优化站间选路，B4支持更高级别的利用率，提供更具预测性地行为。

表1：服务等级及他们对应的应用示例，以及为他们分配的可用性SLO。

B4的初始范围只限于容丢失的低可用性应用，这些应用不需要高于99%的可用性（如跨数据中心索引复制）。然而，随着时间的迁移，我们的需求变得更为严格，以服务水平目标（SLOs）为99.99%可用性的应用为目标。具体地，SLO为X%可用性指的是任意一对数据中心站点间的网络连通性（即，数据丢包低于某一阈值）和许诺带宽[25]在30天的时间窗口内的可用分钟数达到X%[笔者注：30天包含43200分钟，则10%的可用性要求可用分钟数达到4320分钟]。表1给出应用到服务等级的分类，这些服务等级具有指定的可用性SLO。

初看起来，匹配电信级网络的可用性是令人畏惧的。考虑长距离传输链路的固有不可靠性[17]和不可避免的与必要的管理操作相关的宕机[13]，传统的知识认为达到这一等级的可用性（电信级可用性）需要大量的超额配置和快速本地故障恢复（如50毫秒内[7]）。

广域网流量的指数增长使我们对更高可用性的努力复杂化；我们的带宽需求在5年期间增长了100倍。事实上，带宽需求每九个月翻一番的速度比其它基础设施组件更快，表明应用可以从大量的集群到集群带宽中显著受益。可扩展性需求包含多个维度，包括聚合网络容量、数据中心站点数目、TE路径数量和网络聚合前缀。此外，我们必须在不导致现有数据流中断的情形下获得扩展性和可用性。因此，我们需要激进地革新并研发解决多个问题的创新点方案。

本文中，我们介绍了过去5年在解决网络演进导致的矛盾方面的经验教训；网络演进是取得我们可用性和流量需求所必须的（第二部分）。我们将B4逐渐演化为一种层次化拓扑（第三部分），同时研发了一种去中心化的TE架构和可扩展交换机规则管理方法（第四部分）。总体来看，实验结果表明我们的设计改变将可用性提升了两个量级（由99%提高到99.99%），同时在过去5年支持了100倍的流量增长（第6部分）。

2 背景和动机

本节，我们给出B4演进过程中运维方面的经验教训，展示其它设计选择问题的动机性实例，以及我们设计方案的概要。

2.1 扁平拓扑扩展性差且损害可用性

现有的B4站点硬件拓扑使用刚性结构，导致网络难于扩展。其结果是，我们传统的扩展方法是通过增加B4站点的方式增加容量；增加的B4站点与现有站点在地理位置邻近。然而，这种方法导致三个问题，这些问题只在一定规模后才会呈现。首先，站点数量的增加导致集中TE优化算法（在站点级拓扑下运行）显著变慢。随着站点数量的增加，算法的运行时间超线性增长；运行时间的增长导致数据平面故障期间数据流黑洞的时间延长，最终违反我们的可用性目标。其次，站点数量的增加导致有限交换机转发表空间方面的扩展压力。最后，最重要的是，这种方法使容量规划复杂化并混淆应用开发者。当计算和存储容量在邻近点（一个不同的站点之后）可用时，容量规划必须考虑站点间的WAN带宽约束。开发者由考虑跨集群的区域复制转变到必须理解集群到多个B4站点中一个站点的映射。

为了解决带宽需求指数增长引入的矛盾，我们重新设计了硬件拓扑为层次化拓扑抽象（细节见图4和第三部分）。具体地讲，每个站点构建为2层拓扑抽象：在底层，我们引入"超级节点”结构（由商用硅交换芯片构建的标准两层Clos网络）；在上层，我们松散的链接多个超级节点构成一个全mesh拓扑，以解决增量扩展和网络维护、升级及软硬件故障导致的固有不对称。基于我们的运维经验，这种两层拓扑提供了可扩展性（按需向上层水平增加更多的超级节点，而不需要增加站点数量）和可用性（垂直就地升级超级节点为新一代设备，而无需打断现有流量）。

2.2 解决层次化拓扑中的容量不对称

图2: 2017年10月到2018年1月，B4中具有不同量级容量不对称的站点级链路的比例。

然而，2层层次化拓扑给TE带来挑战。我们发现，由于固有的网络维护、运维和数据平面设备的不稳定，在一定规模下容量不对称问题是不可避免的。我们设计的拓扑在超级节点级具有对称的WAN容量，即所有的超级节点具有相同的向其它站点的出口容量。然而，图2表明B4中6-20%的站点级链路仍然具有大于5%的容量不对称。我们定义站点级链路的容量不对称为(avg_∀i(C_i) - min_∀i(C_i))/avg_∀i(C_i)，这里C_i表示超级节点i向其它相邻站点的总活跃流量。

图3： 包含2个站点且每个站点包含2个超级节点的站点级拓扑示例。每条链路上的标注表示该链路的有效容量，入口流量在A₁和A₂之间平均分配。子图给出受限于链路容量，站点级链路（A，B）的最大准入流量。（a）没有旁路；（b）包含旁路。

此外，我们发现容量不对称显著抑制了层次化拓扑的效率—在约17%的不对称站点级链路中，具有100%的站点级抽象容量损失，这是因为至少一个超级节点完全失去到另一个站点的链接。为了理解层次化次拓扑中容量不对称管理的重要性，我们首先给出一个动机性实例。图3a中超级节点A₁和A₂到站点B分别有10和2个单位的有效容量，这是由网络运维或物理链路故障导致的。由于瓶颈超级节点A₂具有更低的出口容量，为了避免网络拥塞，此站点级链路仅允许4个单位的流量。这表明有8个单位的超级节点级容量是浪费的，因为容量不对称导致他们无法在站点级拓扑中使用。

为了减少容量不对称导致的低效问题，我们引入了旁路(sidelink)的概念；旁路互连同一站点中的超级节点构成全mesh拓扑。图3b展示了如何通过使用旁路将本例中的准入流量增加3倍。集中控制器利用旁路动态重均衡站点内的数据流以适应不对称WAN链路故障。由于B4站点内的超级节点的位置是邻近的，与其他数据中心网络链路类似，旁路的价格更为低廉且比长传输距离的WAN链路更为可靠。这种异构链路的成本/可靠性是驱动我们设计的独特WAN特征。旁路的灵活使用配合超级节点级TE不仅提高了WAN链路的利用率，并且使得增量式就地网络升级成为可能，极大地降低了网络部署的预付成本。具体地，使用旁路的非最短路径TE，因升级/维护而断掉超级节点级链路不会导致任何现有流量的中断。即，仅导致站点级容量的轻微退化。

将现有的站点级TE演化为层次化TE（站点级，其后是超级节点级）证明是具有挑战性的。TE通常需要隧道封装（如，MPLS标签[34]，IP-in-IP封装[30]或VLAN标签[3]），然而商用交换机芯片只能依据数据包内部或者外部报头进行哈希计算。使用两层隧道封装，内部和外部数据报头均只有非常低的熵值，导致无法实施流量切分。另一种可选方案是重写每个数据包的MAC地址作为超级节点级TE的标签。然而，我们已经保留MAC地址以实行更有效的哈希计算（第五部分）。为了解决这个问题，我们设计和实现了新型站点内TE算法（第四部分），该算法不需要数据包打标/封装。此外，该算法是可扩展的，在目标规模下运行时间为200-700毫秒；该算法是高效的，在典型站点级链路上，即使在容量不对称问题存在时也可减少拓扑抽象导致的容量损失到0.6%。

另一个挑战是TE升级可能会引入路由黑洞和环路。使用预设隧道，由于只有入口源节点需要更新从而将流量封装到一个不同的隧道，将流量由一个隧道导向另一个隧道是的过程是原子操作。然而，移除隧道封装使网络更新复杂化。我们发现，以任意顺序应用TE更新导致2%的网络更新的前向环路中有多达38%的数据包黑洞（见6.3节）。为了解决这个问题，前期工作采用两阶段提交[31]和基于依赖树/森林的方法[28]实现无环更新。最近，Dionysus[21]将网络更新建模为资源调度问题，并使用关键路径调度来动态搜索可行的更新调度方法。然而，这些工作假设隧道/版本打标，对我们的层次化TE来说，导致前文所描述的哈希问题。我们开发了一种简单的基于依赖图的方法，排定超级节点级TE更新操作的顺序，其是可证明无黑洞/环路的，而且不需要任何隧道/标签（见4.4节）。

2.3 高效交换机规则管理

商用硅交换机支持有限数量的匹配和哈希规则。使用我们现有的包转发流水线，在32个站点时，我们将达到交换机匹配规则的数量限制。另一方面，层次化TE需要更多的交换机哈希项来执行两层的细粒度流量划分。SWAN[16]研究了吞吐量和交换机哈希规则限制之间的权衡，发现动态隧道化比静态隧道集合需要更少的哈希规则。然而，我们发现在层次下TE下采用动态隧道化仍然需要比达到目标规模下的最大吞吐量所需要的交换机哈希规则多8倍以上。

我们使用两种机制优化交换机转发行为(第五部分）。首先，我们将流匹配规则分解到两个交换机流水表。我们发现这种层次化的两阶段匹配机制将支持的站点数目增加了接近60倍。其次，我们将路径分割规则去中心化为跨Clos设施边缘和后端阶段的2阶段哈希。我们发现这种优化方法是层次化TE的关键，将吞吐量提升6%（在我们的规模下，就绝对值来说是非常大的），这是因为不采用这种优化方法导致流量划分粒度不足。

3 站点拓扑演化

表2：B4设施代次。所有的设施均有常用硅交换芯片构建。

表2总结了B4硬件和站点设施拓扑如何由扁平拓扑逐年演化为可扩展的两阶段层次化拓扑。我们接下来讨论我们第一代网络设施Saturn（见3.1节），接着讨论新一代站点网络设施Jumpgate（见3.2节）；jumpgate提升了硬件和拓扑结构。

3.1 Saturn

图4：B4设施由扁平Saturn拓扑到层次化Jumpgate拓扑的演化；Jumpgate包含一个称为超级节点的抽象层。

Saturn是B4的第一代网络设施，2010年在全球部署。如图4所示，部署包括两个步骤：4个Saturn底架构成的底层，提供5.12Tbps的面向集群的容量；由2个或4个底架构成的上层，向B4的其他部分分别提供3.2 Tbps和6.4 Tbps的容量。面向集群和WAN的容量的差异使得设施可以提供额外的中转流量。针对可用性，我们将单一Saturn的站点从物理上划分到数据中心的两个建筑。这使得Saturn站点可以在容量降低的情形下仍然工作（单一建筑中的某些或者所有设备不可达）。每个物理机架包含2个Saturn底架，我们设计交换机到机架映射使得任意单机架故障情形下容量损失最小化。

3.2 Jumpgate

Jumpgate是覆盖两种B4设施特点的涵盖性术语。与其继承Saturn的拓扑结构，我们意识到扁平拓扑会限制扩展性，因此我们在Jumpgate中设计了一种新的定制的层次化网络拓扑；Jumpgate为站点级容量提供水平和垂直扩展，而不影响控制软件的扩展需求。如图4所示，我们引入超级节点作为中间拓扑抽象层。每个超级节点是一个2阶段folded-Clos网络。底层的一半端口是面向外部的，可以灵活地分配给对等B4站点、集群设施或者同一站点内其它的超级节点。接着，我们使用互连超级节点的全mesh拓扑构建Jumpgate站点。这些互连链路称为旁路。此外，由于每个站点只有一个控制域，Saturn中B4的可用性显著降低。我们观察到大量的由域控制器故障导致的中断，这会广泛损害所有途径受影响站点的数据流。因此，Jumpgate中将站点划分为多个控制域，每个超级节点一个控制域。采用这种方式，通过减少任意域控制器故障的爆炸半径到途径单一超级节点的数据流，提升了B4的可用性。

我们展示了两代Jumpgate，不同代次间站点划分为更多的超级节点和控制域，从而提升了可用性，如图4所示。这种新型架构解决了先前提到的网络扩展问题；解决方案是使用灵活的旁路重配和增量增加站点内的超级节点数量。此外，这种架构通过依次升级每个超级节点（由某一代到下一代）为无缝设施演进提供了便利，并且无需干扰其他超级节点的流量。

JPOP:通过减少数据中心间网络线缆的跨度，战略性部署中转站点提升了B4的总可用性。中转站点同时提高了站点级拓扑的“meshiness”，进而提升了集中TE绕过故障的能力。因此，我们开发了JPOP，一种用于只支持中转流量的中转POP站点轻量级部署的低成本配置方案。由于POP站点通常受到电源和物理空间的限制，我们使用高带宽密度16x40G商用硅（图4）构建JPOP，因此每个站点只需要少量的交换机机架。

图5：Stargate纳入园区汇聚网络。

Stargate: 我们在全球范围内使用Stargate替代Saturn。Stargate是一种支持数据中心WAN流量需求增长的大型网络设施。Stargate站点由多达4个超级节点构成，每个超级节点由32x40G商用硅（图4）构建成2阶段folded-Clos网络。Stargate部署于数据中心，可以提供高达81.92 Tbps的站点到外部容量，这些容量可以在WAN、集群和旁路间划分。与Saturn相比，Stargate将站点容量提升了8倍以上，从而满足增长的流量需求；这种增长的关键是商用硅交换芯片中转发容量密度的增长，使得我们可以维护相对简单的拓扑。容量的提升使得Stargate可以纳入园区汇聚网络。其结果是，我们可以直接将Stargate链接到Jupiter集群设施[32]，如图5所示。架构改变简化了网络建模、容量规划和管理。

4 层次化流量工程TE

本节，我们以两个解决容量不对称问题的稻草人方案为起始（见4.1节）:我们通过扁平化TE演化为层次化TE架构解决这个问题（见4.2节），开发了一种可扩展的站内TE算法，最大化站点间链路容量（见4.3节）。最后，我们给出了基于依赖图的超级节点级规则升级序列算法（见4.4节）。这些算法均是可扩展，无黑洞和环路的，并且不需要数据包封装/打标。

4.1 驱动性示例

在层次化拓扑中管理容量不对称需要一种超级节点级负载均衡机制，以最大化站点级拓扑容量。此外，我们需要解决方案快速（通过减少数据平面故障后黑洞窗口时间提高可用性）和高效（在硬件交换机表约束下取得高吞吐量）。最后，该解决方案不能使用多于一层的数据包封装。我们讨论两种稻草人方案：

超级节点上的扁平化TE无法扩展。使用层次化拓扑，可以直接将TE应用于全部超级节点拓扑。这种模型中，集中控制器使用IP-in-IP封装在超级节点隧道间均衡负载。我们的评估表明采用这种方法来支持高吞吐量会导致过高的运行时间（比层次化TE高188倍），并且需要更多的交换机表空间（详见第6部分）。由于TE问题的复杂度随着拓扑大小超线性增长，这种方法是不可行的。例如，假设每个站点包含4个超级节点，那么单条三跳的站点-站点路径可以由4^3=64条超级节点级路径表示。

超级节点级最短路径路由因容量不对称问题而不高效。一种可选择的方案是结合站点级TE和超级节点级最短路径路由。这种两阶段的层次化路由是可扩展的，并且只需要一层封装。此外，最短路径路由可以通过旁路完全绕开WAN故障。然而，这种方法无法有效的应对容量不对称。例如，图3b中，最短路径路由无法利用通过旁路的长路径，导致站点级容量不理想。可以微调旁路的代价度量提升站点A和站点B之间的容量。然而，由于旁路的代价由所有到下一跳站点的隧道共享，改变度量值同样会影响其他站点级链路的路由。

4.2 层次化TE架构

图6给出层次化TE的架构。具体地，我们采用下述选路层次：

流分组（FG）将流聚合作为元组（源站点、目标站点、服务等级），当前，我们将服务等级映射为数据包头中的DSCP标记。为了扩展性，集中控制器为每个FG分配路径。

隧道分组（TG）通过IP-in-IP封装将FG映射到隧道集合（即，站点级路径）。我们使用一种近似的最大-最小公平优化算法为每个隧道的流量划分设置权重值（[18]的4.3节）。

隧道划分组（TSG），一种新的选路抽象，指明某一隧道中的流量分布。具体地，TSG是一种超级节点级规则，用于控制如何在自站点（当前站点中的其他超级节点）和下一站点（隧道另一站点的超级节点）间划分流量。

交换机划（SSG）分组：指明在交换机上跨物理链路的流量划分。域控制器计算SSG。

为了可扩展性，我们解耦TG和TSG计算。具体地，TG算法运行于站点级拓扑之上，且基于TSG的计算结果。TSG的计算只使用拓扑数据，并且不受TG运算结果的影响。我们以如下步骤简述层次化TE算法。首先，域控制器通过聚合有效物理链路的容量计算超级干线（超级节点级链路）的容量，然后基于设施损害调整容量。例如，由于故障或者维护，超级节点Clos设施可能没有全折半带宽。其次，使用超级干线容量，中央控制器计算每个出口站点级链路的TSG。当入口站点级链路的容量在超级节点间是对称的，旁路不被使用。否则，集中控制器生成TSG通过旁路重新均衡到达每个站点超级节点的流量，以匹配出口超级干线容量；这是通过超级节点级拓扑（只包含站点的旁路和站点级链路的超级干线）上的公平共享算法实现的。第三，我们使用TSG计算站点级拓扑中每条链路的有效容量，结果接着由TG生成所消耗（见[18]中4.3节）。第四，我们生成依赖图以序列化TE操作，使得其是无黑洞和环路的（见4.4节）。最后，我们通过域控制器编排FG，TG和TSG；根据域内拓扑计算SSG，跨Clos设施的两层实现层次化划分规则以达到可扩展性（第5部分）。

图6: 层次化TE示例；超级节点级TE为新开发的组件以通过旁路应对容量不对称。

4.3 TSG生成

问题声明：假设某隧道的输入流量在源站点的所有超级节点间均匀划分，在该隧道途径的每个站点内计算每个超级节点的TSG使得该隧道的准入流量总量最大（受限于超级干线约束）。此外，以整数表示该TSG划分中每个出口超级干线的相对权重。每个TSG中的权重总和不能超过阈值T，这是因为交换机哈希表项的限制。

图7：不同故障场景下TSG功能示例。此处展示的流量封装为A->B->C的隧道，TSG控制流量如何在超级节点级划分（Ai，Bi和Ci）。每个超级干线的容量为C，标记TC表明给定TSG配置下的最大隧道容量。

示例：我们首先使用TSG计算的例子，用于计算某一隧道内细粒度流量工程。图7a中，到超级节点B_i的流量在两个到下一隧道站点的超级站点间均匀划分（C₁和C₂）。由于拓扑设计为对称超级节点级容量，图7a展示了常见场景。然而，由于数据平面故障和网络操作，容量不对称仍有可能发生。图7b展示了一种故障场景，其中B₁完全失去与C₁和C₂的链接。为了绕过故障，B₁上的TSG编排为仅转发到B₂。图7c展示了B₂相对于B₁有两倍到C的容量的场景。其结果是，计算出的B₁的TSG在下一站点（C₂）和自站点（B₂）间划分的比例为2:1。简化起见，下一站点C的TSG不需要重新均衡入口流量。

我们单独为站点级链路计算TSG。对于我们的部署来说，我们假设超级节点间的入口流量是均衡的；实践中，我们发现很少出现违反这一假设的情形。这一假设允许TSG在途径站点级链路的所有隧道间被重用，使得并行TSG计算成为可能，并且允许我们实现一种简单的方案满足硬件限制。我们讨论两种很少出现的场景，这些场景中我们的解决方案可能导致TSG划分不理想。首先，图7d展示了一种场景，其中B₁失去子站点和下一站点的链接。这种场景并不常见，且只发生了一次，这是因为旁路在同一数据中心中，因此比WAN链路更为可靠。这种情形下，站点级链路(B,C)不可用。可以通过使B₁失效（所有进入B₁的链路无效）恢复站点级链路的容量，但这种方法的代价是B₁到其他地方的容量不可用。第二，图7e显示了并发故障导致的两个连续不对称站点级链路的情景。由于站点B处入口流量均衡对TSG计算是不可知的，隧道容量降低到9c/4，比理想划分降低了25%（B₁转发其一半的流量到自站点B₂以适应B₁和B₂间入口流量的不均衡，如图7f所示）。我们的测试表明这种故障模式极少发生：平均只有0.47%的链接站点级链路对。我们将更精致的每隧道TSG生成留作未来工作。

TSG生成算法：我们将TSG计算建模为每条直连站点级链路的网络流问题。首先，生成图G_TSG，图中顶点包含站点级链路的源站点的超级节点（Si，1<=i<=N）和站点级链路的目的站点（D）。我们增加两种类型的链路到图中。首先，我们将源站点中所有超级节点构成全mesh（∀i, j 不等于 i : Si ↔ Sj)。第二，增加每个源站点的超级节点和目的站点的链接：(∀i : Si ↔ D)。我们将相应超级干线容量关联到每条链路。随后，我们生成由每个超级节点i到目的站点D的具有无限需求的数据流，并尝试使用两种选路组（PG）满足这一需求。两种选路组分别为单跳路径和2跳路径。我们使用贪心的穷举瀑布算法以最大-最小公平方式迭代的分配瓶颈容量。TSG生成算法的伪代码如算法1所示。

定理4.1：生成的TSG不会形成环路。

证明. 假设生成图中有K+1个顶点：Si（0 ≤ i ≤ K - 1）表示源站点中的超级节点，和表示目的站点的D。给定步骤（1）中施加的选路限制，每条流智能使用单跳直连链路 (Si→D) 或两跳路径 (Si→Sj不等于i→D)，且单跳路径严格优先于两跳路径。假设ℓ > 1跳的环路在转发序列中形成，不失一般性，假设环路为<S0, S1, ..., Sℓ-1, S0>。注意到环路中不能包含目的顶点D。考虑到选路优先和环路序列，链路 (Si , D) 在 (Si+1, D)前成为瓶颈，且(Sℓ-1, D)在(S0, D)前成为瓶颈。我们发现这种瓶颈序列形成环路，考虑到算法中每条链路只成为瓶颈一次，上述序列是不可能的。

算法1： TSG生成

4.4 编排TSG更新顺序

我们发现以任意顺序进行TSG更新会导致瞬时但严重的流量环路/黑洞（6.3节），降低可用性。为此，我们开发了编排TSG更新顺序的可扩展算法，使得更新是无黑洞/环路的，描述如下。

TSG序列化算法：给定图G_TSG和4.3节描述的TSG结果，我们按如下方式构造依赖图。首先，依赖图中的顶点和图G_TSG中一样。如果S_j出现在目标TSG配置中S_i的下一跳集合中，增加直连链路S_i->S_j。如果S_i直接转发任意流量到目标TSG配置中的下一跳，则增加S_i到D的直连链路。根据定理4.1，依赖图中不包含环路，因此是具有当前拓扑序的有向无环图(DAG)。我们以逆拓扑序应用每个超级节点的TSG更新；在如下转变期间，该算法不会导致瞬时环路或黑洞。注意，基于依赖的TSG序列和内部网关协议中（IGP）特定时间如何处理类似，如链路断掉、度量值改变[11]和迁移[33]。

定理4.2. 假设原始或目标TSG配置中均不含环路，那么中间TSG配置也不会包含环路。

证明：在任意中间步骤，每个顶点可以认为是已决断的（超级节点使用目标TSG转发流）或者未决断的（超级解决使用原始TSG转发流）。顶点D总是已决断的。我们发现环路不会在已决断顶点间形成，这是因为目标TSG配置不包含环路。类似地，环路也不能在未决断顶点间形成，因为原始的TSG配置是无环的。因此，环路必须要包含至少一个已决断顶点和至少一个未决断顶点。然而，由于顶点以依赖图的逆拓扑序更新，已决断顶点不可能转发流到未决断顶点，因此无法形成环路。

定理4.3. 给定TSG配置，如果某流途径失效链路那么该留认为具有黑洞。假设原始TSG配置可能包含黑洞流，目标TSG配置没有黑洞，并且是失效链路未发生变化，那么如果流在原始TSG配置中没有黑洞，那么在任何中间TSG配置中也不会具有黑洞。

证明：参见定理4.2证明中已决断和未决断顶点的定义。假设流Si->D在由原始TSG到目标TSG转变的中间步骤中具有黑洞。假设该流在原始TSG中不具有黑洞。那么，该留的至少一个中转顶点是已决断的，且黑洞发生在第一个已决断顶点或其后。然而，由于已决断顶点不会转发流回到未决断顶点，黑洞只能出现在已决断顶点，与我们的假设相悖。

5 高效交换机规则管理

商用交换芯片具有严格的表大小限制。本节，我们指出FG匹配和流哈希是推动我们打破交换机转发规则限制以满足可用性和可扩展性目标的关键驱动力。为了解决这些限制，我们将FG匹配规则划分到两个交换机流水表以支持60倍数量的站点（5.1节）。我们进一步解耦层次化TE划分到跨2阶段Clos超级节点交换机的2阶段哈希计算（5.2节）。没有上述优化方案的情形下，我们发现层次化TE将损失6%的吞吐量，因为粗粒度流划分。

5.1 层次化FG匹配

最初，我们采用访问控制列表（ACL）表实现FG匹配，以利用他们的通配能力。FG匹配项的数量受限于ACL表大小：

size_ACL ≥ num_Sites × num_{Prefixes/Site} × num_{ServiceClasses}

给定ACL表大小限制(size_ACL = 3K)，支持的服务等级数量（参见表1，num_{ServiceClasses} = 6）和每站点平均聚合IPv4和IPv6集群前缀（num_{Prefixes/Site} ≥ 16），在有约32个站点时，达到ACL表限制。

图8：解耦FG匹配为两个阶段。

因此，我们将FG匹配划分为两个层次化阶段，如图8b所示。我们首先将集群前缀匹配移动到最长前缀匹配（LPM）表，该表比ACL表大得多，可以存储多达几十万表项。尽管LPM表项无法直接匹配DSCP比特以支持服务等级，LPM表项可以匹配虚拟路由转发（VRF）标签。因此，我们通过虚拟转发平面（VFP）表匹配DSCP标记，使得匹配的数据包在进入交换机流水线的LPM表之前可以关联一个VRF标签标示其相应的服务等级。我们发现这种2阶段可扩展的方法可以支持多达1920个站点。

这种优化还可以使能其他有用的特征。我们以TE作为主要的路由栈，BGP/ISIS路由作为备份。面对关键TE问题时，我们可以在源站点断掉TE临时回滚到BGP/ISIS路由。这表明在入口站点我们删除交换机中TE转发规则，这样数据包可以回滚回匹配低优先级BGP/ISIS转发规则的方式，而不需要封装。然而，仅使单一源-目的对（端到端）之间的流的TE失效是具有挑战的，因为我们必须匹配面向集群的入口端口。否则，即使源站点不封装数据包，为封装的数据包可以随着BGP/ISIS路由，随后在中转站点（到给定目标的TE仍然有效）被不正确的封装。增加入口端口匹配只有在使用可扩展的两阶段FG匹配时才可行。

5.2 使用划分的高效流哈希

使用层次化TE，源站点负责实现TG、TSG和SSG划分。原始设计中，我们折叠层次划分，并仅在入口边交换机实现。然而，我们预计这会接近交换机ECMP表大小的硬限制：

size_ECMP ≥ num_Sites × num_{PathingClasses} × num_TGs × num_TSGs × num_SSGs

这里，num_{PathingClasses} = 3表示聚合服务等级的数量（共享相同的选路限制），num_TGs = 4表示隧道划分粒度，num_TSGs = 32表示每超级节点划分粒度，and num_SSGs = 16在Stargate后端阶段跨交换机划分。为了支持33个站点，需要198K ECMP表项，然而在排除2K BGP/ISIS表项后我们的交换机只支持 size_ECMP = 14K表项，我们下量化流划分以避免达到表限制。然而，我们发现TE的优势将急剧下降，因为较差的流划分粒度。

我们通过接口流划分规则到跨两级Clos设施克服每交换机限制（如表3所示）。首先，边缘交换机决定使用哪个隧道（TG划分）以及入口流应该转发到哪个站点（TSG划分第一部分）。为了把决定传播到后端交换机，我们将数据封装到用于指定选定隧道的IP地址（TG划分）并且使用特定的MAC地址用来表示自站点/下一站点目标（TSG划分部分1）。基于隧道IP和源MAC地址，后端交换机决定数据包应该转发到的对等超级节点（TSG划分部分2）以及与目标超级节点具有连接的出口边缘交换机（SSG划分）。为了进一步降低入口交换机上的划分规则，我们为每个边缘交换机到可见后端交换机配置了链路聚合组（LAG）。为了简化起见，我们认为后端交换机是可见的，如果该交换机自身是有效的并且到超级节点中的每个边缘交换机具有有效连接。

6 评估

本节，我们评估演进的B4网络。我们发现，在过去5年，我们的方法使得B4成功的扩展到应用100倍流量（6.1节），同时满足严格的每个服务等级的可用性目标（6.2节）。我们评估了设计选择，包括层次化拓扑中旁路的应用，层次化TE架构和两阶段哈希机制（6.3节），用于理解取得我们要求的权衡。

6.1 扩展性

图9：B4在5年内的规模扩展度量。(a)总流量；B4面向集群的端口的字节计数总量。(b)B4域和站点的数量。（c）每站点FG数量。（d）每站点TG数量。（e）每站点中转隧道数量。

图9表明B4在多个维度取得长足的发展。具体地，B4聚合流量在过去的5年增长了2个量级，如图9a所示。平均来讲，B4流量每9个月翻一番。B4正在传输比面向因特网的WAN更多的流量且增长速度更快。关键的增长驱动是Stargate纳入了园区聚合网络（3.2节），并且自2015年开始提供大量的园区带宽。

图9b给出B4拓扑大小的增长，以站点数量和控制域数量计。在基于Saturn的B4中（每站点一个控制域），这两个数字相同，并在2013年开始分离，这是因为JPOP开始部署。为了解决扩展性挑战，自2015年通过使用Stargate替代Saturn，我们极大的降低了站点数量。讽刺的是，这里给出迁移期间扩展性挑战，这一期间Saturn和Stargate在同一站点共存

图9c给出每个源站点的FG数量在过去5年增长了6倍。2015年，我们停止为交换机和超级干线端口分发管理IP地址。这些IP地址无法聚合为集群前缀，移除这些地址帮助将每个站点的FG数量减少约30%。

B4支持每服务等级隧道。2013开始，最初是使用两个服务等级，结果是导致每站点TG数量翻番，如图9d所示。随后，TG数量技术随着新部署站点和更多服务等级增长。

每站点最大中转隧道数量由集中控制器配置控制。这一约束帮助我们避免安装比可用规则更多的交换机规则，也限制了备份隧道的数量（对于数据平面故障的快速黑洞恢复是必须的）。2016年，交换机规则管理的提升使我们能够安装更多的备份隧道，并提升非计划节点/链路故障时的可用性。

6.2 可用性

我们以FG的粒度度量B4的可用性，这一度量通过结合两个方法：

基于带宽的可用性：定义为谷歌带宽实施者[25]给定的带宽满足率：

这里，需求基于短期历史使用量度量，批准指每SLO合约许可的最小带宽，分配是当前准入带宽（受限于网络容量和公平性约束）。该度量是不充分的，因为带宽实施响应延迟和带宽评估的不准去性（如，由于拥塞期间的TCP回退）。

基于链接的可用性作为带宽满足限制的互补。网络度量系统用于主动在所有集群对间的每个服务等级发送探测。探测结果按B4站点对分组，并使用1-分钟桶，每个桶的可用性按如下计算：

公式

这里α = 5%为敏感阈值，滤除大部分瞬时丢失，并捕获影响可用性的大的丢失事件。阈值之上，可用性随着流量丢失率的增加以衰减因子β = 2%指数级减少。合理性解释是大部分数据中心间服务运行于并行工作者模式，任何工作者的黑洞传输可以不成比例的影响服务完成时间。

图10：网络不可达性。y轴给出测量的和目标不可用性（使用演化前后每月数据），这里粗条表示95th百分比（站点对间），误差条表示90th和99th百分比。x轴给出按目标不可用性排序的服务等级。

可用性通过这两个度量值的较小者计算。图10比较了每个服务等级的测量的可用性和目标可用性。我们发现B4最开始在多个服务等级的90th百分比的流取得低于三个九的可用性。那时，B4不适用于传输SC3/SC4流量（除了用于可用性测量的探测包）。然而，我们见证了清晰的提升趋势：SC1/SC2的4-7倍提升和SC3/SC4的10-19倍提升。其结果是，B4的每个服务等级都可以取得我们的可用性目标。

6.3 设计权衡

图11：层次化拓扑中容量不对称导致的容量损失。

拓扑：图11展示层次化拓扑中旁路的重要性。没有旁路时，集中控制器依赖于ECMP以在多个通向隧道中下一站点的超级节点间均匀划分流量。使用旁路，集中控制器使用TSG最小化容量损失（由于层次化拓扑）的影响（通过重新均衡流量以匹配超级节点间的不对称连通）。平均情形下，抽象容量损失由3.2%（没有旁路）减少到0.6%（使用旁路和TSG）。此外，我们发现不使用旁路在83rd百分比时容量损失达100%,这是因为至少一个超级节点失去到下一站点的连通。在这种故障情景，使用旁路可以有效避免大部分容量损失。

图12：使用两阶段哈希的层次化TE运行时间为2-4秒，取得较高的吞吐量且满足交换机哈希限制。

2阶段哈希的层次化TE：图12量化吞吐量和运行时间的权衡（作为TE算法和流量划分粒度的函数）。我们比较了新的层次化TE方法和扁平TE（直接在超级节点级拓扑上运行TE优化算法，参见[18]中4.3节）。为了评估受限于划分粒度限制的TE容量，我们线性扩展每个FG流量使用量（2018年1月测量），将调整后的流量使用量作为需求灌输到扁平和层次化TE，接着将需求、拓扑和TE选路灌输到带宽分配算法（[25]中第5部分）以获得基于最大-最小公平需求分配的最大可得吞吐量。

我们由上述结果中得出如下结论。首先，我们发现层次化TE的运行时间为2-3秒，比扁平化TE快188倍。TSG生成运行时间是总运行时间的一小部分，从200到700毫秒。第二，当最大流划分粒度设置为1时，层次化和扁平TE性能较差，取得少于91%和46%的最大吞吐量。原因很简单：每个FG只能使用最短可用路径，且充分路径多样性的缺失导致很多链路无法充分使用，特别是对扁平拓扑（因为在超级节点级图中有指数级数量更多的链路）。第三，我们发现使用原始的8-路流划分，层次化TE取得94%的最大吞吐量。通过采用两阶段哈希，我们使用128-路TG和TSG划分粒度达到接近最大化吞吐量，并且满足交换机哈希限制。

TSG顺序：我们使用一个月的trace评估使用和不使用TSG序列的权衡。实验中，我们排除17%的只更新一个超级节点的TSG操作。图13a显示只采用1步或2步的TSG序列多达TSG操作的99.7%。每个步骤只有一个或多个TSG更新（其相对顺序没有规定）。图13b比较使用和不使用序列化时TSG操作的端到端延迟。我们发现99.7th百分比时2倍的延迟增长，最坏情形下有2.63倍的延迟增长。此外，我们发现TSG序列算法的运行时间与程序延迟负相关。图13c给出TSG操作期间每个中间状态的可用容量。不使用TSG序列化，由于3%情形下的黑洞/环路，可用容量降至0，使用序列化时该数字提升了一个数量级。图13d表明不使用序列化，多达38%的入口流量因大于2%的中间状态形成环路而丢失。

7 运维经验和开放问题

本节，我们总结生产环境中B4网络的经验教训和一些仍然活跃的开放问题。

管理工作流简化：演化前，我们依赖ECMP在Saturn底板的每个阶段均衡数据流（节3.1），因此，数据流受限于具有最小出口容量的瓶颈底板。设计中，当故障或网络操作导致的容量不对称存在时，Saturn的准入流量显著降低。因此，我们需要人为考虑容量不对称导致的容量损失以保证降低的站点容量仍然满足流量需求。Jumpgate采用旁路和TSG提高不对称处理，减少了人工干预需求，这是因为TE系统可以自动高效使用不对称容量。

凭借Jumpgate每站点多个独立控制域（节3.2），我们限制操作只能每次修改一个域以限制可能的影响。为了评估改变对网络可用性的影响，我们以预测的容量改变、可能的网络故障和其他网络操作窗口内的维护来执行影响分析。我们将软件控制器和影响分析工具紧耦合以精确核算可能的容量损失（打断性网络操作导致）。基于这些结果，网络操作可能被许可或拒绝。

为了最小化可用性影响，我们开发了称为“drain”的机制在中断性改变发生前安全地将流量转移出特定的网络实体，以防止流丢失。在B4的规模下，网络操作者和站点可靠性工程师不太可能使用命令行接口（CLI）管理每个域控制器。因此，drain操作由管理工具调用；管理工具通过控制器暴露的管理RPC编排网络操作。

旁路容量规划：旁路在超级节点间形成mesh拓扑，应对物理故障、网络操作和划分不充分导致的WAN容量不对称。多达16%的B4站点容量指定给旁路，保证TSG算法可以充分利用WAN容量。然而，确定最优的旁路容量（满足带宽保证）是困难的供应问题，依赖于长期需求预测、成本评估和商业案例分析[5]。我们正在积极开发日志驱动的统计分析框架使得我们可以规划旁路的容量，同时最小化成本以满足网络可用性需求。

不均衡入口流哈希：TSG算法假设站点内超级节点间的输入流量是均衡的（4.3节）。这一假设简化了我们的设计，更重要的是，这允许我们满足一定规模下的交换机硬件需求（共享相同站点链路的隧道使用相同的TSG规则集合，这些集合编程到交换机转发表）。与每隧道TSG分配相比（要求>1K TSG规则，超过硬件规则限制），TSG算法需要多大N TSG规则，这里N ≈ 6指对等站点的数量。然而，它并不处理入口流的不均衡。我们计划研究可选设计，例如为每对相邻站点级链路计算TSG。这一设计将处理基于容量不对称的入口流量不对称（上游站点级链路中观察到），同时交换机硬件中需要稍多数量的TSG规则(N(N - 1) = 30) 。