编者按

Nick McKeown 在 ONF Connect 2019演讲中定义了SDN发展的三个阶段：

l第一阶段（2010–2020年）：通过Openflow将控制面和数据面分离，用户可以通过集中的控制端去控制每个交换机的行为；

l第二阶段（2015–2025年）：通过P4编程语言以及可编程FPGA或ASIC实现数据面可编程，这样，在包处理流水线加入一个新协议的支持，开发周期从数年降低到数周；

l第三阶段（2020–2030年）：展望未来，网卡、交换机以及协议栈均可编程，整个网络成为一个可编程平台。

（备注：引用部分为《软硬件融合——超大规模云计算架构创新之路》图书内容的节选。）

Nick为我们描绘了SDN网络发展的一个非常美好的未来，而这美好未来的核心是可编程网络DSA。Barefoot公司（Nick是Barefoot创始人之一，Intel于2019年收购了Barefoot）的核心竞争力在于围绕着P4网络编程语言构建的一整套芯片及软件生态，其构建的全球唯一商用的可编程交换芯片的核心架构是PISA（Protocol Independent Switch Architecture，协议无关的交换架构），而PISA的原型来自于RMT（可重构匹配表）。

本文是RMT的经典论文，希望通过此篇论文，管中窥豹，能够学习到PISA架构的核心精髓。

参考文献

Forwarding Metamorphosis: Fast Programmable Match-Action Processing in Hardware for SDN, Pat Bosshart, Glen Gibb, Hun-Seok Kim, etc., SIGCOMM’13

（原标题）转发变形：硬件实现的快速可编程SDN数据面匹配-动作处理

摘要

在SDN (Software Defined Networking)中，控制平面和转发平面在物理上是分离的。控制软件使用开放接口(如OpenFlow)对转发平面(如交换机和路由器)进行编程。本文旨在克服当前交换芯片和OpenFlow协议的两个限制：

1. 当前硬件交换机非常严格，只允许在一组固定的字段上进行“匹配-动作”处理，

2. OpenFlow规范仅定义了有限的包处理动作集。

我们提出了RMT(可重构匹配表)模型，这是一种新的基于RISC的交换芯片流水线结构，我们确定了基本的最小动作原语集，以指定在硬件中如何处理报头。RMT允许在不修改硬件的情况下在字段中更改转发平面。与在OpenFlow中一样，程序员可以指定多个任意宽度和深度的匹配表，只受总体资源限制，每个表可配置为在任意字段上进行匹配。然而，RMT允许程序员比OpenFlow更全面地修改所有报头字段。本文描述了一个实现RMT模型的64端口10Gb /s开关芯片的设计。我们的具体设计表明，与社区内部的担忧相反，灵活的OpenFlow硬件交换机实现几乎不需要额外的成本或电力。

1 介绍

改进就是改变;要做到完美就要经常改变。——丘吉尔

好的抽象——比如虚拟内存和分时——在计算机系统中是至关重要的，因为它们允许系统处理变化，并允许在更高的层次上简化编程。网络的发展得益于关键的抽象：TCP提供端点之间连接队列的抽象，IP提供从端点到网络边缘的简单数据报抽象。然而，网络中的路由和转发仍然是一个令人困惑的集合，路由协议(如BGP、ICMP、MPLS)和转发行为(如路由器、网桥、防火墙)，控制和转发平面仍然交织在封闭的、垂直集成的盒子中。

软件定义网络(SDN)在抽象网络功能方面迈出了关键一步，它通过一个开放的接口(如OpenFlow[27])将控制平面和转发平面的角色分离开来。控制平面被抬起并离开交换机，将其置于外部软件中。这种对转发平面的编程控制允许网络所有者向其网络添加新功能，同时复制现有协议的行为。OpenFlow作为一种基于“Match-Action”方法的控制平面和转发平面之间的接口，已经非常出名了。粗略地说，数据包字节的子集与表相匹配；匹配的表项指定了对报文应用的相应动作。

我们可以想象在通用CPU上的软件中执行Match-Action。但是对于我们感兴趣的速度——今天大约1Tb/s——我们需要专用硬件的并行性。10年来，交换芯片的交换速度一直比CPU快两个数量级，比网络处理器快一个数量级，而且这种趋势不太可能改变。因此，我们需要考虑如何在硬件中实现Match-Action来利用流水线和并行性，同时又受到片上表内存的限制。

在可编程性和速度之间有一个自然的权衡。如今，要支持新特性，经常需要更换硬件。如果Match-Action硬件允许在现场进行足够的重新配置，以便在运行时支持新类型的包处理，那么它将改变我们对网络编程的看法。这里真正的问题是，能否在不牺牲速度的情况下，以合理的成本完成这项工作。

单匹配表：最简单的方法是在我们称为SMT(单匹配表)模型中抽象匹配语义。在SMT中，控制器告诉交换机将任何一组报头字段与单个匹配表中的条目进行匹配。SMT假设解析器定位并提取正确的报头字段以与表匹配。例如，一个以太网包可能有一个可选的MPLS标记，这意味着IP报头可以位于两个不同的位置。当所有字段都完全指定时，匹配是二进制精确匹配，当某些位被关闭时，匹配是三元匹配(通配符项)。表面上，SMT抽象对程序员(还有什么比单一匹配更简单的呢?)和实现者(SMT可以使用宽的三元内容可寻址内存(TCAM)来实现)都有好处。请注意，转发数据平面抽象具有最严格的硬件实现约束，因为转发通常需要以大约1Tb/s的速度运行。

然而，进一步观察会发现，由于一个经典问题，SMT模型的使用成本很高。表需要存储每个头文件的组合；如果报头行为是正交的(条目将有许多通配符位)，那么这是浪费。如果一个报头匹配影响到另一个报头，则会更加浪费，例如，如果第一个报头的匹配决定了第二个报头匹配一组不相连的值(例如，在虚拟路由器[11]中)，则需要表保存两者的笛卡尔积。

多匹配表：MMT(多匹配表)是SMT模型的自然细化。MMT在一个重要方面超越了SMT：它允许多个较小的匹配表通过包字段的子集进行匹配。所述匹配表被布置成一系列的阶段；阶段j的处理可以依赖于阶段i (i < j) 的处理，i阶段修改报头或其他信息然后传递给j阶段；MMT很容易实现，在每个阶段使用一组更窄的表；事实上，它与现有的交换芯片的实现方式非常接近，可以很容易地映射到现有的流水线上[3,14,23,28]。谷歌报告使用商业交换机芯片[13]将他们的整个私有广域网转换为这种方法。

OpenFlow规范转变为MMT模型[31]，但没有规定表的宽度、深度，甚至表的数量，让实现者可以自由选择他们希望的多个表。虽然许多字段已经标准化(如IP和以太网字段)，但OpenFlow允许通过用户定义的字段设施引入新的匹配字段。

现有的交换芯片实现了少量(4-8)的表，其宽度、深度和执行顺序在芯片制造时设置。但这严重限制了灵活性。用于核心路由器的芯片可能需要一个非常大的32位IP最长匹配表和一个小的128位ACL匹配表；用于L2桥的芯片可能希望有一个48位目的MAC地址匹配表和第二个48位源MAC地址学习表；企业路由器可能希望有一个较小的32位IP前缀表和一个更大的ACL表以及一些MAC地址匹配表。为每个用例制造单独的芯片是低效的，因此商业交换机芯片往往被设计为支持所有通用配置的超集，并以预先确定的流水线顺序安排一组固定大小的表。这给网络所有者带来了一个问题，他们希望调整表大小以优化他们的网络，或者实现超出现有标准定义的新转发行为。在实践中，MMT通常转换为固定的多个匹配表。

第二个更微妙的问题是，交换芯片只提供了与常见处理行为相对应的有限的操作集，例如转发、删除、减少TTL、推送VLAN或MPLS报头以及GRE封装。到目前为止，OpenFlow只指定了其中的一个子集。这个操作集不容易扩展，也不是很抽象。更抽象的操作集将允许修改任何字段，更新与包关联的任何状态机，并将包转发到任意一组输出端口。

可重构匹配表：因此，在本文中，我们探索了MMT模型的一个改进，我们称之为RMT(可重构匹配表)。与MMT一样，理想的RMT将允许一组流水线阶段，每个阶段都具有任意深度和宽度的匹配表。RMT超越了MMT，它允许以以下四种方式重新配置数据平面。

• 首先，可以修改字段定义并添加新字段；

• 其次，可以指定匹配表的数量、拓扑结构、宽度和深度，只受匹配位数的总体资源限制；

• 第三，可以定义新的操作，比如写入新的拥塞字段；

• 第四，可以将任意修改的数据包放置在指定的队列中，以便在端口的任意子集输出，并为每个队列指定排队规则。

这种配置应该由一个SDN控制器来管理，但在本文中我们没有定义控制协议。

考虑到最近几年提出的新协议，如PBB[16]、VxLAN[22]、NVGRE[19]、STT[21]和OTV[20]，可以看出RMT的好处。每个协议都定义了新的报头字段。如果没有像RMT这样的体系结构，就需要新的硬件来匹配和处理这些协议。

注意，RMT与当前的OpenFlow规范完全兼容(甚至部分实现)。单个芯片显然可以允许接口重新配置数据平面。事实上，一些现有的芯片，至少在一定程度上是受多个细分市场需求的驱动，已经有了一些可重构性，可以通过芯片的特别接口来表达。

许多研究人员已经认识到需要类似于RMT的东西，并提倡它。例如，IETF ForCES工作组开发了一个灵活的数据平面[17]；类似地，ONF中的转发抽象工作组也致力于可重构性[30]。然而，人们对RMT模型能否以非常高的速度实现持怀疑态度，这是可以理解的。如果没有芯片提供RMT的存在证明，将控制器和数据平面之间的重构接口标准化似乎是徒劳的。

从直觉上看，以太比特速度任意重构似乎是一项不可能完成的任务。但在这些速度下，什么样的受限形式的可重构性是可行的？受限制的可重构性是否涵盖了我们前面提到的需求的足够大的一部分？人们能否通过使用包含这些想法的硅来证明其可行性？与固定桌面的MMT芯片相比，这种RMT芯片有多贵？这些是我们在本文中要解决的问题。

通用Payload处理不是我们的目标。SDN/OpenFlow(以及我们的设计)的目标是确定在硬件中处理报头的最小原语集。可以把它看作是像RISC那样的最小指令集，它被设计成在大量流水线操作的硬件中运行得非常快。我们非常灵活的设计是在成本上具有竞争力的固定设计。在美国，灵活性几乎不需要任何成本。

论文贡献：我们的论文对以下争论做出了具体贡献：哪些转发抽象在高速下是实用的，以及转发平面在多大程度上可以由控制平面重新配置。具体来说，我们对上述问题的处理如下：

• 1)一个RMT的体系结构(第2章)：我们描述了一个RMT交换体系结构，它允许定义任意的报头和报头序列，通过任意数量的表任意匹配字段，任意写入包报头字段(但不包括包体)，以及每个包的状态更新。为了实现该体系结构，引入了一些限制条件。我们概述了如何通过解析图来表示所需的配置，以定义标题，以及表流图来表示匹配表拓扑。

• 2)用例(第3章):我们提供的用例显示了如何配置RMT模型来使用以太网和IP头实现转发，并支持RCP[8]。

• 3)芯片设计和成本(第4-5章)：我们展示了我们所提倡的可重构性的具体形式是切实可行的，并描述了一个640Gb/s (64 x 10Gb/s)交换芯片的实现。我们的架构和实施研究包括逻辑和电路设计的重要细节，布图规划和布局，使用的技术经过设计团队开发复杂数字集成电路的长期历史证明。采用了工业标准的28nm工艺。这项工作是必要的，以证明可行性的目标，如时间和芯片面积(成本)。我们还没有生产出一个完整的设计或实际的硅。根据我们的调查，我们表明重配置的成本预计是适中的：比固定(不可重配置)版本的成本高出不到20%。

我们并不声称我们是第一个提倡可重新配置匹配的人，或者我们所提议的重新配置功能是“正确的”。我们确实认为，重要的是通过对RMT模型进行具体定义，并通过展示芯片来证明它是可行的，就像我们在本文中试图做的那样。虽然芯片设计通常不是SIGCOMM的领域，但我们的芯片设计表明，RMT模型的一种相当普遍的形式是可行的，而且价格低廉。我们展示了RMT模型不仅是一种考虑网络编程的好方法，而且还可以使用匹配表和动作处理器的可配置流水线在硬件中直接表达。

2 RMT架构

我们说RMT是“允许一组流水线阶段……每个字段都有一个任意深度和宽度的匹配表”。一个逻辑推论是，RMT交换机由一个解析器组成，用于在字段上进行匹配，然后是任意数量的匹配阶段。审慎性建议我们在输出中加入某种排队来处理拥塞。

让我们再深入一点。解析器必须允许修改或添加字段定义，这意味着解析器是可重构的。解析器输出是一个包报头向量，它是一组报头字段，如IP dest、Ethernet dest等。此外，包报头向量包括“元数据”字段，如包到达的输入端口和其他路由器状态变量(例如，路由器队列的当前大小)。向量流过一系列的逻辑匹配阶段，每个阶段抽象出图1a中包处理(如以太网或IP处理)的逻辑单元。

每个逻辑匹配阶段都允许配置匹配表的大小：例如，对于IP转发，可能需要一个包含256K 32位前缀的匹配表，对于以太网，可能需要一个包含64K 48位地址的匹配表。输入选择器选择要匹配的字段。包修改使用宽指令（图1c中的VLIW-超长指令字）来完成，该指令可以同时对包报头向量中的所有字段进行操作。

(a) RMT模型作为逻辑匹配动作阶段的序列

(b) 灵活的匹配表配置 (c) VLIW动作架构

图1：RMT模型架构

更准确地说，包报头向量中的每个字段F都有一个操作单元(图1c)，它最多可以接受三个输入参数，包括头向量中的字段和匹配的操作数据结果，并重写F。允许每个逻辑阶段重写每个字段似乎有点过分，但它在移动头文件时很有用；我们稍后将说明，与匹配表相比，动作单位成本较小。一个逻辑的MPLS阶段可能弹出一个MPLS报头，将后续的MPLS报头向前移动，而一个逻辑的IP阶段可能只是减少TTL。指令还允许修改有限状态(例如计数器)，这可能会影响后续包的处理。

控制流是通过提供下一个要执行的表的索引的每个表匹配的附加输出来实现的。例如，阶段1中特定以太类型上的匹配可以指导后面的处理阶段在IP(路由)上进行前缀匹配，而不同的以太类型可以在以太网DA(桥接)上指定精确匹配。数据包的命运是通过更新一组目标端口和队列来控制的；它可以用来丢弃数据包、实现多播或应用指定的QoS(如令牌桶)。

在流水线的末端需要一个重组块来将包报头向量修改推回数据包(图1a)。最后，包被放置在指定输出端口的指定队列中，并应用一个可配置的队列规则。

总之，图1a的理想RMT允许通过修改解析器来添加新字段，通过修改匹配内存来匹配新字段，通过修改阶段指令来执行新动作，通过修改每个队列的队列规则来创建新的队列。理想的RMT可以模拟现有的设备，如网桥、路由器或防火墙；可以实现现有的协议，如MPLS、ECN，以及文献中提出的协议，如使用非标准拥塞字段的RCP[8]。最重要的是，它允许将来在不修改硬件的情况下修改数据平面。

2.1 在640Gbps下的实现架构

我们提倡如图1b所示的实现体系结构，它由大量的物理流水线阶段组成，根据每个逻辑阶段的资源需求，可以将少量的逻辑RMT阶段映射到这些物理流水线阶段。这个实现架构的动机是：

1. 分解状态：路由器转发通常有几个阶段(如转发、ACL)，每个阶段使用一个单独的表；将这些组合到一个表中会产生状态的叉积。阶段是通过依赖顺序处理的，因此物理流水线是自然的。

2. 灵活的资源分配最小化资源浪费：物理流水线阶段有一些资源(如CPU、内存)。逻辑阶段所需的资源可能有很大差异。例如，防火墙可能需要所有ACL，核心路由器可能只需要前缀匹配，边缘路由器可能各种资源都需要一些。通过灵活地将物理阶段分配到逻辑阶段，可以重新配置流水线，将其从防火墙转变为现场的核心路由器。物理阶段N的数量应该足够大，以便使用很少资源的逻辑阶段最多浪费1/N的资源。当然，增加N将增加开销(布线、功率):在我们的芯片设计中，我们选择N = 32作为减少资源浪费和硬件开销之间的折衷。

3. 布局优化：如图1b所示，通过将逻辑阶段分配给多个连续的物理阶段，可以为逻辑阶段分配更多内存。另一种设计是通过交叉开关[4]将每个逻辑阶段分配给一组解耦的存储器。虽然这种设计更加灵活(任何内存组都可以分配到任何阶段)，但在最坏的情况下，处理阶段和内存之间的线延迟至少会以sqrt(M)的速度增长，而在需要大量内存的路由器芯片中，M可以很大。虽然这些延迟可以通过流水线来改善，但这种设计的终极挑战是布线:除非减少当前的匹配和动作宽度(1280位)，否则在每个阶段和每个内存之间运行如此多的布线可能是不可能的。

总而言之，图1b的优势在于它使用了带有短线的平铺架构，其资源可以以最小的浪费重新配置。我们承认有两个缺点。首先，物理阶段的数量越多，对能量的需求就越高。第二，这个实现体系结构合并了处理和内存分配。需要更多处理的逻辑阶段必须分配给两个物理阶段，但是即使它可能不需要内存，它也会得到两倍的内存。实际上，这两个问题都不重要。我们的芯片设计显示，阶段处理器的功耗最多是总功耗的10%。其次，在网络中，大多数用例是由内存使用而不是处理决定的。

2.2 可实现性限制

物理流水线阶段架构需要限制以允许tb级速度实现：

1、匹配限制：设计必须包含固定数量的物理匹配阶段和固定的资源集。我们的芯片设计在入口和出口提供了32个物理匹配阶段。在出口的匹配动作处理允许更有效地处理组播数据包，通过延迟每个端口的修改，直到缓冲之后。

2、包报头限制：包含用于匹配和操作的字段的包报头向量必须受到限制。我们的芯片设计限制是4Kb (512B)，这允许处理相当复杂的头。

3、内存限制：每个物理匹配阶段都包含相同大小的表内存。通过将每个逻辑匹配阶段映射到多个物理匹配阶段或其分数，可以近似得到任意宽度和深度的匹配表(见图1b)。例如，如果每个物理匹配阶段只允许1000个前缀条目，那么2000个IP逻辑匹配表将分两个阶段实现(图1b左上角的矩形)。同样，一个小型Ethertype匹配表可能会占用匹配阶段内存的一小部分。

SRAM中基于哈希的二进制匹配比TCAM的三元匹配便宜6倍。两者都是有用的，因此我们在每个阶段提供固定数量的SRAM和TCAM。每个物理阶段包含106个1K 112b SRAM块，用于80b宽哈希表(开销位稍后解释)和存储操作和统计数据，以及16个2K 40b TCAM块。块可以并行地用于更宽的匹配，例如，使用四个块的160b ACL查找。32级的总内存为370 Mb SRAM和40 Mb TCAM。

4、动作限制：为了可实现，每个阶段的指令数量和复杂性必须受到限制。在我们的设计中，每个阶段可以在每个字段执行一条指令。指令仅限于简单的算术、逻辑和位操作(见4.3)。这些操作允许实现RCP[8]这样的协议，但不允许在包体上进行包加密或正则表达式处理。

指令不能实现状态机的功能；它们只能修改包报头向量中的字段、更新有状态表中的计数器或将包直接发送到端口/队列。队列系统提供了四个层次和每个端口2K队列，允许赤字轮循、分层公平队列、令牌桶和优先级的各种组合。但是，它不能模拟WFQ所需的排序。

在我们的芯片中，每个阶段包含超过200个动作单元：一个用于包报头向量中的每个字段。芯片中包含超过7000个动作单元，但与内存相比，这些单元占用的面积很小(<< span="">10%)。动作单元处理器是简单的，特别的架构，以避免昂贵的执行指令，并需要少于100门每位。

这样的RMT体系结构应该如何配置？需要两段信息：表示允许的报头序列的解析图，以及表示匹配表集和它们之间的控制流的表流图(参见图2和4.4)。理想情况下，编译器执行从这些图到适当的交换配置的映射。我们还没有设计出这样的编译器。

3 示例用例

(a) L2/L3交换

(b) RCP和ACL支持

图2 交换配置示例

为了对如何使用RMT芯片有更深层次的理解，我们将看两个用例。

例1：L2/L3开关。

首先，我们需要配置解析器、匹配表和操作表。对于我们的第一个示例，图2a显示了L2/L3交换机的解析图、表流图和内存分配。解析图和表流图告诉解析器在宽报头总线上提取和放置四个字段(Ethertype、IP DA、L2 SA、L2 DA)。表流图告诉我们应该从宽头总线读取哪些字段并在表中匹配。内存分配告诉我们如何将这四个逻辑表映射到物理内存阶段。在我们的示例中，Ethertype表自然属于阶段1，其余三个表分布在所有物理阶段，以最大限度地扩大它们的大小。大多数哈希表RAM是在L2 SA和DA之间分割的，每个有120万个条目。我们致力于32个阶段的TCAM条目，以容纳100万个IP DA前缀。最后，我们需要存储VLIW动作原语，以便在匹配后执行(例如，出口端口，减少TTL，重写L2 SA/DA)。这需要30%的阶段RAM内存，剩下的留给L2 SA/DA。如果启用，包和字节计数器也将消耗RAM, L2表大小减半。

一旦配置完成，控制平面就可以开始填充每个表，例如通过添加IP DA转发表项。

例2：支持RCP和ACL。

我们的第二个用例为简单的防火墙添加了速率控制协议(RCP)支持[8]和ACL。RCP通过交换显式地指示流量的公平共享率，从而减少了流量完成时间，从而避免了使用TCP慢启动的需求。公平共享速率被每个开关标记到RCP报头中。图2b显示了新的解析图、表流图和内存分配。

为了支持RCP，数据包的当前速率和估计的RTT字段被解析器提取并放置在头部向量中。第32阶段的出口RCP表更新出包的RCP速率——小的动作选择包当前速率和链路公平共享速率中较小的那个。(公平份额比率由控制平面定期计算。)

有状态表(第4.4节)积累计算公平份额率所需的数据。状态表在第32阶段实例化，并为每个目标端口累积字节和RTT和。

我们还从TCAM的最后两个阶段创建了20K ACL条目(120b宽)，将L3表的前缀减少到960K，以及保存相关操作(例如，drop、log)的RAM条目。

在实践中，用户不应该关注底层配置细节，而应该依赖编译器从解析图和表流图生成开关配置。

4 芯片设计

图3 交换芯片架构

到目前为止，我们使用了方便网络用户的RMT转发平面的逻辑抽象和实现RMT的物理体系结构。

现在我们描述实现设计细节。我们选择1 GHz交换芯片工作频率，因为在64个10 Gb/s端口的总吞吐量960MPPS，一个流水线可以处理所有输入端口数据，服务所有端口，而在较低的频率，我们需要使用多个这样的流水线，需要附加一些区域开销。交换IC的框图如图3所示。注意，这与图1a的RMT体系结构图非常相似。

输入信号由64个10Gb SerDes IO模块接收。40G通道由4个10G端口组在一起组成。经过执行低级信令和CRC生成/检查等MAC功能的模块后，输入数据由解析器处理。我们使用16个入口解析器块，而不是图1a中所示的单个逻辑解析器，因为我们的可编程解析器设计可以处理40Gb的带宽，四个10G通道或一个40G通道。

解析器接受单个字段位于可变位置的包，并输出一个固定的4kb包报头向量，其中每个解析字段被分配一个固定的位置。位置是静态的，但可以配置。字段的多个副本(例如，多个MPLS标签或内部和外部IP字段)被分配到包报头向量中唯一的位置。

输入解析器的结果被多路复用到单个流中，以提供由32个顺序匹配阶段组成的匹配流水线。一个大的共享缓冲区提供存储来容纳由于输出端口过度订阅而导致的排队延迟；根据需要将存储分配给通道。分离者将数据包报头向量中的数据重新组合到每个数据包中，然后存储在公共数据缓冲区中。

队列系统与公共数据缓冲区相关联。数据缓冲区存储数据包数据，而指向该数据的指针保存在每个端口的2K队列中。每个通道依次使用可配置的队列策略从公共数据缓冲区请求数据。接下来是出口解析器、出口匹配流水线(由32个匹配阶段组成)和分离器，在分离器之后，包数据被定向到适当的输出端口并由64个SerDes输出通道驱动出芯片。

虽然单独的32步出口处理流水线似乎有点小题大做，但我们表明出口和进口流水线共享相同的匹配表，因此成本最低。此外，出口处理允许组播数据包通过端口被定制(比如它的拥塞位或MAC目的地)，而无需在缓冲区中存储几个不同的数据包副本。现在我们描述设计中的每个主要组件。

4.1 可配置的Parser

图4 可配置的Parser模型

解析器接受输入的包数据并生成4K位包报头向量作为输出。解析由用户提供的解析图(如图2)指导，通过脱机算法转换为256条目40b TCAM中的条目，该条目匹配入包数据的32b和解析器状态的8b。注意，这个解析器TCAM与每个阶段中使用的匹配TCAM是完全分离的。例如，当以太类型的16位到达时，CAM匹配32位中的16位(通配符匹配其余部分)，更新指示下一个报头类型(例如VLAN或IP)的状态，以指导进一步解析。

更一般地说，TCAM匹配的结果会触发一个操作，该操作更新解析器状态，将传入数据移动指定字节数，并将一个或多个字段的输出从输入包中的位置定向到包报头向量中的固定位置。重复这个循环来解析每个包，如图4所示。通过将关键更新数据(如输入移位计数和下一个解析器状态)从RAM中提取到TCAM输出优先级逻辑中，循环得到了优化。解析器的单循环循环以32Gb/s的速度匹配字段，这意味着更高的吞吐量，因为不是所有字段都需要解析器匹配。一个单独的解析器实例很容易支持一个40Gb/s的包流。

4.2 可配置的Match内存

每个匹配阶段包含两个640b宽匹配单元，一个TCAM用于三元匹配，一个基于SRAM的哈希表用于精确匹配。SRAM哈希单元的位宽由8个80b子单元聚合而成，而三元表则由16个40b TCAM子单元组成。这些子单元可以单独运行，也可以分组以获得更宽的宽度，或者组合在一起以形成更深的表。输入交叉开关为每个子单元提供匹配数据，子单元从4Kb包报头向量中选择字段。如前所述(图1b)，相邻匹配阶段的表格可以组合成更大的表格。在限制下，所有32个阶段都可以创建一个表。

此外，图3中的入口和出口匹配流水线实际上是同一个物理块，在入口和出口线程之间以细粒度共享，如图1b所示。为此，首先在输入和输出向量之间共享包报头向量；向量中的每个字段都被配置为由入口线程或出口线程拥有。其次，每个字段对应的功能单元以相同的方式分配入或出。最后，每个内存块分配给入口或出口。不会出现争用问题，因为每个字段和内存块都是由出口或入口独占的。

每个匹配阶段有106个包含1K项x 112b的RAM块。分配给匹配、操作和统计内存的RAM块的分片是可配置的。精确匹配表被实现为布谷鸟哈希表[10,26,32]，(至少)有四种1K条目的方式，每一种方式都需要一个RAM块。读取是确定地在一个周期内执行的，所有的方式都是并行访问的。每个比赛阶段也有16个TCAM块，每块为2K项x 40b，可以组合成更宽或更深的表。

与每个匹配表RAM条目相关联的是一个指向动作内存和动作大小的指针，一个指向指令内存的指针，以及下一个表地址。动作内存包含参数(例如，在输出封装中使用的下一跳信息)，指令指定要执行的函数(例如，添加头)。动作内存和匹配内存一样，由8个更窄的单元组成，每个单元包含1K个112位字，每个单元产生96b数据(以及字段有效位和内存ECC位-错误纠正码)。操作内存从106个RAM块中分配，而操作指令保存在一个单独的专用内存中。

与OpenFlow一样，我们的芯片为每个流表条目存储包和字节统计计数器。这些计数器的完整64b版本包含在片外DRAM中，芯片上使用1K RAM块并应用LR(T)算法[33]提供可接受的DRAM更新速率的有限分辨率的计数器。一个字的统计内存可配置地容纳两个或三个流条目的计数器，允许在统计内存成本和DRAM更新速率之间进行权衡。每个计数器增量都需要一个读写内存操作，但在1GHz的流水线中，每个包只有一个操作可用，因此通过增加一个内存块，就合成了第二个内存端口。

4.3 可配置的动作引擎

为每个包报头字段提供一个单独的处理单元(参见图1c)，以便所有字段都可以被同时修改。包报头向量中分别有64、96和64个字(8、16和32b)，每个单词对应一个有效位。较小的字的单位可以组合起来执行一个较大的字段指令，例如，两个8b的单位可以合并成一个单独的16b字段来操作它们的数据。每个VLIW包含每个字段字的单个指令字段。

OpenFlow指定了简单的操作，如将字段设置为值，以及复杂的操作，如PBB封装和从内到外或从外到内的TTL副本，其中外部和内部字段可能是众多选择之一。复杂的修改可以是低速的子例程，但必须在我们的1GHz时钟速率下使用精心选择的指令集将其简化为单周期操作。

表1：部分动作指令集

表1是我们的操作指令的子集。

• Deposit-bype允许从源字的任意位置存储任意字段到背景字的任意位置。

• Rot-mask-merge独立地旋转两个源，然后根据一个字节掩码合并它们，这在执行Pv6到IPv4地址转换[18]时很有用。

• bitmask-set用于选择性的元数据更新；它需要三个源：两个源要合并和一个位掩码。

• Move，和其他操作符一样，只会在源有效的情况下将源移动到目的地，也就是说，如果该字段存在于包中。

• 另一个通用的可选条件化是目标有效。cond-move和cond-mux指令对于从内到外和从外到内的字段拷贝是有用的，其中内部和外部字段是依赖于包的。例如，一个到MPLS标签的从内到外的TTL拷贝可以从内部MPLS标签获取TTL(如果它存在的话)，或者从IP头获取TTL。移位、旋转和字段长度值通常来自指令。一个源操作数从包报头向量中选择字段，而第二个源操作数从包报头向量或动作字中选择字段。

一个复杂的操作，如PBB、GRE或VXLAN封装，可以被编译成一个单独的VLIW指令，然后被认为是一个原语。灵活的数据平面处理也可以用网络处理器、FPGA或软件实现操作，但是需要更高的成本功能才能达到640Gb/s。

4.4 其他特性

通过依赖分析减少延迟：通过要求物理匹配阶段I只在阶段I-1完全完成处理P后才处理包头向量P，可以很容易地确保正确性。但在许多情况下，这是过度杀伤，并可能严重增加延迟。减少延迟的关键是在连续的阶段确定匹配表之间的三种依赖关系：匹配依赖关系、动作依赖关系和继承依赖关系[2]，每一种都在下面描述。

图5 匹配阶段依赖

当一个匹配阶段修改数据包报头字段，并且随后的阶段对该字段进行匹配时，就会产生匹配依赖。在这种情况下不可能有执行重叠(图5a)。当匹配阶段修改数据包报头字段，而后续阶段使用该字段作为动作的输入时，动作依赖就会发生，例如，如果一个阶段设置了一个TTL字段，而下一个阶段减少了TTL。部分执行重叠是可能的(图5b)。当匹配阶段的执行是基于前一阶段的执行结果时，就会产生后续依赖关系；前一阶段的执行可能会导致后续阶段被跳过。如果后续阶段是推测运行的，并且在后续结果提交之前解决了预测，则后续阶段可以与其前身阶段并发运行(图5c)。没有依赖关系的表也可以同时运行。连续阶段之间的流水线延迟是在图5的三个选项之间静态配置的，分别针对入口和出口线程。

组播和ECMP：组播处理在入口和出口之间进行分割。输入处理写入输出端口位向量字段，以指定输出，并可选地写入用于以后匹配的标记和路由到每个端口的副本数量。每个多播包的一个副本存储在数据缓冲区中，多个指针放置在队列中。当数据包被注入出口流水线时，就会创建副本，在出口流水线中，表可以匹配标签、输出端口和数据包拷贝计数，以允许每个端口的修改。ECMP和uECMP处理类似。

计量器和状态表：计量器对匹配表项的流量速率进行测量和分类，可用于修改或丢弃报文。计量只是有状态表的一个例子，其中一个操作修改了后续包可见的状态，并可用于修改它们。可以任意增加和重置的有状态计数器。例如，它们可以用来实现GRE序列号(在每个封装包中递增)和OAM[15,25]。

一致性和原子更新：为了允许一致性更新[34]，版本信息包含在表项中，版本ID通过流水线与每个包一起流动，根据版本兼容性对表进行匹配。

5 评估

相对于传统的可编程开关芯片，我们通过增加设计面积和功耗来描述可配置性的成本。我们的比较在第5.5节中对总芯片面积和功耗进行了比较。为了达到这个目的，我们依次考虑解析器、匹配阶段和动作处理，从而考虑成本的组成。

5.1 可编程解析器成本

可编程性是有代价的。传统解析器针对一个解析图进行优化，而可编程解析器必须处理任何受支持的解析图。通过比较常规设计和可编程设计的综合结果来评估成本。图6显示了实现几个解析图和一个可编程解析器的传统解析器的总门数。我们假设通过组合运行在1GHz的40 Gb/s解析器的16个实例，解析器的总吞吐量为640 Gb/s。所有设计的结果模块在解析时都包含4Kb的包报头向量。该可编程解析器使用256 x 40位TCAM和256 x 128位动作RAM。

图6 提供640Gb/s聚合吞吐量的Parser总门数

解析器门计数由填充解析器报头向量的逻辑决定。传统设计需要290 - 300万个门，这取决于解析图，而可编程设计需要560万个门，其中160万个由增加的TCAM和动作RAM模块贡献。从这些结果来看，解析器可编程性的成本约为2(5.6/3.0 = 1.87 ≈ 2)。

尽管将解析器门数增加了一倍，但解析器只占芯片总体面积不到1%，因此使解析器可编程的成本不是问题。

5.2 内存成本

读者可能会担心内存的成本。

• 首先，内存技术本身(哈希表，TCAM)相对于标准SRAM内存的成本，以及将内存分割成可以重新配置的更小块的成本；

• 其次，每个匹配表条目需要额外的数据来指定操作和保持统计数据；

• 第三，当一个48位的以太网目的地址被放置在112位宽的内存中时，有内部碎片的成本。

我们轮流处理每个开销，并特别指出可编程性的(小的)额外成本。在接下来的内容中，我们将匹配表(例如48位以太网DA)中的条目称为流条目。

5.2.1 内存技术成本

精确匹配：我们使用布谷鸟哈希进行精确匹配，因为它的填充算法占用率很高，对于4路哈希表，通常超过95%。布谷鸟哈希表通过递归地将冲突项逐出到其他位置来解决填充冲突。此外，虽然我们的内存系统是由1K × 112位RAM块构成的，但与使用更大、更高效的内存单元相比，可能会有一个面积代价。然而，使用1K RAM块只会带来大约14%的面积损失，可以说是该技术实现的最密集的SRAM模块。

通配符匹配：我们在芯片上使用了大量的TCAM，直接支持前缀匹配、ACL等通配符匹配。TCAM传统上被认为是不可行的，因为电力和地区的考虑。然而，TCAM的工作功率已经被新的TCAM电路设计技术[1]减少了大约4/5。因此，在最坏的情况下，在所有通道上的最小包大小的最大包速率下，TCAM功率是对总芯片功率的少数几个主要贡献者之一；在更典型的长包和短包混合物中，TCAM功率降低到总功率的一个非常小的比例。

其次，相当于一个等效的比特数SRAM，TCAM通常需要6-7倍的面积，三元和二元流项都有与它们相关的其他位，包括动作内存、统计计数器、指令、动作数据和下一个表指针。例如，使用32位IP前缀、48位统计计数器和16位动作内存(假设用于指定下一跳)，TCAM部分仅为内存比特数的1/3，因此TCAM的面积代价降至3左右。

虽然3倍是重要的，考虑到32b (IPv4)或128b (IPv6)最长前缀匹配和ACL是所有现有路由器的主要使用案例，为TCAM投入大量资源以允许1M IPv4前缀或300K ACL似乎是有用的。虽然我们可以使用具有特殊用途的LPM算法的SRAM，而不是像[6]那样，实现32位或128位LPM的TCAM的单周期延迟是非常困难甚至不可能的。然而，决定三元表和二进制表容量的比率(我们的芯片提出1:2的比率)是一个重要的实现决策，具有重大的成本影响，目前还没有什么现实世界的反馈。

5.2.2 动作规格的代价

除了流条目外，每个匹配表RAM条目还有一个指向动作内存(13b)的指针，一个动作大小(5b)的指针，一个指向指令内存(32条指令的5b)的指针，以及一个下一个表地址(9b)。对于最窄的流入口来说，这些额外的位大约占35%的开销。也有版本和错误校正位，但这些是常见的任何匹配表设计，所以我们忽略他们。

除了流条目中的开销位外，还需要其他内存来存储操作和统计信息。这些增加了总开销(匹配字段所需的总位数与匹配字段位的比率)，但有时这两种额外成本都可以降低。我们将展示如何在某些情况下减少流入口开销位。此外，应用程序需要不同数量的操作内存，有时不需要统计数据，因此可以减少或消除这些内存成本。

给定匹配、操作和统计数据之间的内存块的可变配置，我们使用一些配置示例来了解与不可配置的固定分配相比，记帐开销是如何变化的。

图7 匹配阶段单元内存映射示例

表2 内存单元分配和相对精确匹配容量

在第一个配置中，如图7a和表2所示，在一个阶段中使用32个内存块来匹配内存，实现32K 80b宽的精确匹配流条目。另一个16K 80b三元项在TCAM模块中。所有流条目都具有相同大小的操作条目，操作需要48个内存。统计信息消耗24个内存块组，以及用于多移植统计信息内存的备用存储块组。为每个匹配内存分配大约相等的操作内存份额，可以将其视为具有最小流表容量的基本情况。

除去用例a中用于三元操作和统计的24个块组，用于二元操作的银行中有40%是匹配表，这表明开销为2.5倍。再加上匹配表中35%的位开销，总的二进制开销是3.375，即总比特数与匹配数据比特数的比率。换句话说，只有三分之一的RAM位可以用于流入口。

表2中的用例a2和a3将匹配宽度分别更改为160和320位，减少了动作和统计需求，增加了匹配容量。

配置表2的b进一步增加二元和三元流表匹配宽度640位,如图7所示(水平的内存宽度显示)，比基本情况，减少8倍流条目的数量，以及所需的动作和统计能力。虽然这种广泛的匹配可能很少见(比如整个标题匹配)，但我们看到，与上面的基本情况相比，有8个更宽的流条目，80个块组可以用于精确匹配，内存容量的75%，比基本情况高2.5个表容量。

表2的c1配置，如图7c所示，利用了单个操作数量有限的用例。例如，一个数据中心地址虚拟化应用程序需要大量的流条目，但是匹配条目可能指向TOR交换机的1000个可能的目的地中的一个。因此4K的动作内存就足够了。这将允许62个内存块用于匹配，40个内存块用于统计，几乎是基本情况下精确匹配条目数量的两倍。如果不需要统计信息，则可以使用102个内存块进行匹配，如表项c2所示，占总内存容量的96%。

简而言之，如果动作或统计数据减少或消除，流入密度将大大增加。如果芯片的用户认为这些复杂的操作和统计数据是必要的，那么将这种开销归咎于芯片可配置选项是不公平的。唯一可以直接归因于可编程性的基本记事簿成本是指令指针(5b)和下一个表地址(9b)，大约占15%。

在固定行为的表格中，成本可以进一步降低。一个固定函数表使用相同的指令和下一个表指针为所有的条目，例如，L2 dest MAC表；可以为这些属性配置静态值，允许14位指令和下一表指针被回收以匹配。更一般地，流条目中的可配置宽度字段可以选择性地为操作、指令或下一表地址提供LSB，从而允许减少不同指令或操作的数量，或为下一表寻址一个小数组，同时回收尽可能多的指令、下一个表、和动作地址位尽可能考虑到功能的复杂性。

接下来，表可以提供一个动作值作为一个直接常量，而不是小常量的动作内存指针，从而保存指针和动作内存位。

一个简单的机制可以实现这些优化：匹配表字段边界可以灵活配置，允许每个字段具有任意大小的表配置范围，受总位宽限制。带有固定或几乎固定函数的表可以有效地实现，与固定的表相比几乎没有任何损失。

5.2.3 交叉开关成本

每个阶段中的交叉开关从报头向量中选择匹配表输入。从4Kb输入向量中选择1280个输出位(TCAM和哈希表各为640b)。每个输出位由一个224输入多路复用器驱动，该多路复用器由与-或-反 AOI22门 的二叉树组成，每多路复用器输入成本为0.65µm2。总横木面积为1280 x 224 x 0.65µm2 x 32阶段 ≈ 6 mm2。动作单元数据输入多路复用开关的面积计算也是类似的。

5.3 碎片的成本

最后一个开销是内部分裂或打包的成本。显然，放置在112b宽内存中的48位以太网目的地址浪费了超过一半的内存。相比之下，固定功能的以太网桥包含定制的48位宽RAM。因此，这一成本完全归因于可编程性和我们选择的112b宽RAM。人们可以通过选择48b作为基本RAM宽度来减少以太网的这种开销，但是为通用用途(和未来协议)设计的芯片如何预测未来的匹配标识符宽度呢？

幸运的是，通过另一种架构技巧，甚至可以减少这种开销，这种技巧允许将流条目集打包在一起，而不损害匹配功能。例如，标准的TCP 五元组是104位宽。其中三个条目可以被打包到四个宽度为448b的内存单元中，而不是分别要求每个条目消耗两个内存单元。或者，使用相当于简单成功/失败的低输入开销，由于ECC比特在更宽的数据上的摊销，其中4个可以被打包成4个字。从根本上说，这是可行的，因为本质上，较长的匹配是由较小的8位匹配树构建的；灵活性只是稍微使这个逻辑复杂化了一些。

这两种技术的结合，将可变数据打包到一个数据字(以降低操作规范成本)，和将可变流输入打包到多个数据字(以降低碎片成本)确保了在广泛配置下的高效内存利用。总而言之，虽然传统的交换机对特定的表配置有高效的实现，但这种架构可以达到这种效率，不仅对那些特定的表配置，而且对许多其他配置也是如此。

5.4 动作可编程性的成本

除了指令RAM和动作存储器的成本，大约有7000个处理器数据路径，宽度从8位到32位不等。幸运的是，因为它们使用简单的RISC指令集，它们的总面积只占用芯片的7%。

5.5 面积及功耗成本

这个交换机设计有很大的匹配表容量，所以匹配和动作存储器很大程度上贡献了芯片面积估计，如表3所示。第一项包括IO、数据缓冲区、CPU等，在传统交换机中占据了类似的区域。可以看出，VLIW动作引擎和解析器/分离器对区域的贡献相对较小。

表3 评估芯片面积

表4 评估芯片功耗

我们之前提出过，与最优的RAM设计相比，匹配阶段单元RAM遭受了14%的面积惩罚。考虑到对匹配阶段SRAM(不是TCAM)面积的惩罚，以及与传统交换机(15%)相比额外比特数的一些许可，剩余内存区域约为芯片总数的8%。如果解析器和动作引擎中的多余逻辑又增加了6.2%，那么就会产生14.2%的区域成本，这证明了之前宣称的低于15%的成本差异是正确的。

评估的交换机最坏操作条件（温度、芯片处理）下的功耗详情见表4，100%流量混合大包（1.5KB）小包各一半的数据包，以及所有匹配和动作表填满容量的情况下，评估的交换功率详见表4。输入/输出功率相当于一个常规开关。内存泄漏功率与内存比特数成正比，所以如果这个可编程交换机可以实现与传统交换机相同的比特数，功率将是相当的。剩下的部分，总数为30%，比传统的交换机少，因为减少了功能的匹配动作流水线。我们估计，可编程芯片比传统的交换机多消耗12.4%的功率，但执行更实质性的包操作。

与传统交换机的整体竞争评估表明，该交换机可以用相同的存储位数执行相同的功能。这反过来又推动了芯片成本和功率方面的优势。考虑到交换机的更全面的功能，可编程解决方案所承担的额外功耗和面积成本非常小。

6 相关工作

灵活的处理可以通过许多机制实现。在处理器上运行软件是一种常见的选择。我们的设计性能比CPU高出两个数量级[7]，比GPU和NPU高出一个数量级[5,9,12,29]。

现代FPGA，如Xilinx Virtex-7[35]，可以以接近1Tb/s的速度转发流量。不幸的是，FPGA提供更低的总内存容量，模拟TCAM很差，消耗更多的电力，而且非常昂贵。目前最大的Virtex-7设备是Virtex-7 690T，总内存为62Mb，约占我们芯片容量的10%。来自两个匹配阶段的TCAM将消耗用于实现用户逻辑的大部分查找表(LUT)。产品清单价格超过10,000美元，这比我们芯片的预期价格高出一个数量级。这些因素一起排除了FPGA作为解决方案的可能性。

与NPU相关的是PLUG[6]，它提供了许多通用的处理核心，与内存和路由资源配对。将处理过程分解成数据流图，数据流图分布在整个芯片上。PLUG主要关注于实现查找，而不是解析或包编辑。

英特尔FM6000 64端口10Gb/s交换芯片[24]包含一个可编程解析器，由32个阶段构建，每个阶段都有一个TCAM。它还包括一个两级匹配行动引擎，每个级包含12块1K 36b TCAM。这只占总表容量的一小部分，其他表在固定的流水线中。

最新的OpenFlow[31]规范提供了一个MMT抽象，并部分实现了一个RMT模型。但是它的动作能力仍然是有限的，并且它也不确定是否会有一个功能完整的动作标准。

7 总结

理想情况下，交换机或路由器应该使用多年。应对不断变化的世界需要可编程性，允许软件升级在该领域添加新功能和新协议。网络处理器(NPU)被引入来支持这一愿景，但无论是NPU还是GPU都无法接近使用ASIC实现固定功能交换机的速度；我们也没有见过对基于NPU的路由器(如思科的CRS-1)进行重新编程以添加新协议的案例研究。同样地，FPGA最近才达到ASIC转发速度，但仍然非常昂贵。

我们的芯片设计再现了这种古老的可编程性愿景，在RMT模型中表达，在真实芯片的约束条件下实现。可以添加新的字段，可以重新配置查找表，可以添加新的头处理，所有这些都是通过软件重新配置。虽然我们的芯片不能做正则表达式，或操纵包体，但用这种芯片构建的盒子可能会从周二的以太网芯片变成周三的防火墙，周四变成一个全新的设备，所有这些都是通过正确的软件升级。今天的挑战是在接近1万亿比特的容量下做到这一点。我们提出的芯片设计有惊人的规格：它包含7000个处理器数据通道，370 Mb的SRAM和40 Mb的TCAM，跨越32个处理阶段。

就创意而言，我们将RMT模型作为一种强大的方式，将程序员所需的转发行为映射到一个由灵活的解析器构建的流水线上，一个具有任意宽度和深度的存储器的逻辑匹配阶段的可配置安排，以及灵活的包编辑。这些抽象要求以太比特的速度高效地实现新的算法。我们使用的内存块可以在阶段内或跨阶段组合，这是实现可重构匹配表的关键；我们对TCAM的大规模使用，大大提高了匹配的灵活性；最后，我们使用完全并行的VLIW指令是包编辑的关键。我们的设计表明，这种大大提高灵活性的额外成本不到15%的面积和功耗的芯片。最终，我们已经解决的实现挑战对SIGCOMM用户来说可能不是很明显，那就是生产一个可以在芯片上有效连接的架构。

虽然OpenFlow规范暗示RMT和一些研究人员[17]已经积极地追求这个梦想，但RMT模型仍然是理论的，没有存在的证据证明芯片设计工作在太比特的速度。本文提出了一个具体的RMT方案，并证明了其可行性。

显然，我们有可能进一步采取行动，取消我们因为而施加的一些限制。但是现在这个讨论可以开始了。

（正文完）

关键词： SDN 网络