《可编程数据平面：抽象、架构、算法与应用》是TechRxiv上一篇关于网络数据面编程的一篇综述性文章，内容非常全面详实。本译文有删改。

原始论文链接如下：https://doi.org/10.36227/techrxiv.12894677.v1

快速链接：

4 抽象

数据平面之间的差异通常反映在暴露给控制平面的包处理原语和可用于组合这些原语以实现所需流水线的编程语言结构中。基于这种固有的体系结构耦合性，我们接下来讨论可编程数据平面系统中使用和公开的常见抽象。在深入研究包解析和调度的抽象之前，我们首先讨论可编程包处理流水线。最后，我们介绍了可编程数据平面的编程语言和编译器。

4.1可编程网络包处理流水线

灵活的包处理是可编程数据平面的核心能力。今天的可编程包处理流水线通常建立在三个基本抽象之上：

数据流图抽象和相关的交换机架构
Match-Action流水线抽象
状态机交换架构(允许在之前的抽象之上实现有状态工作负载)。

接下来我们详细介绍每一个抽象。

数据流图

数据包处理系统的早期设计很大程度上借鉴了通用系统设计[190]和机器学习[7]，采用数据流图抽象来架构可编程交换机[147]。这个模型在流处理框架(如Apache Flink或Spark)中也被大量使用。数据流图将处理逻辑描述为一个图，节点表示基本计算阶段，边表示数据从一个计算阶段移动到另一个计算阶段的方式。这种抽象的特点是它的简单性，允许程序员使用熟悉的面向图形的模型将一组定义良好的处理节点组装成有意义的程序。这样，计算原语(节点)只开发一次，然后可以根据需要自由重用多次，以生成新的模块化功能，从而创建一个具有平滑学习曲线的快速开发平台。

最早采用数据流图抽象的可编程交换机框架可能是Click模块化软件路由器[147]。通过Click图移动的数据单元是一个网络数据包，节点可以在数据包上执行简单的数据包处理操作，如包头解析、校验和计算和验证、字段重写或根据ACL进行检查。一些节点提供特定于网络协议的功能，如处理ARP请求和响应，而另一些节点提供更一般的数据流控制功能，如负载均衡、排队或分支(从几个备选方案中选择下一个处理阶段)。

ClickOS [135]， FastClick[20]，矢量包处理(VPP) （来自FD.io项目[56] ），Berkeley可扩展软件交换机(BESS，[77])和NetBricks[157]采用了类似的设计。不同的是，沿着数据流图移动的基本数据单元现在是数据包的Vector，而不是单个数据包。这种发展源于对批处理将I/O成本平摊到多个包上的观察和分析，以及使用现代CPU内置的SIMD指令集可以产生更高效的软件实现[20,78,87]。此外，NetBricks引入了一个新的框架，使用新颖的语言级构造和零成本的编译时抽象来隔离潜在的不可信的包处理节点[157]。

用户定义的功能抽象为数据流图节点，具有很大的灵活性和可扩展性[117,135]。与此同时，这种灵活性往往使最终的设计变得零碎，异构性使高层次的网络范围抽象复杂化，并阻碍性能优化[120,121]。

Match-Action处理

Match-Action抽象描述了使用一系列查找表(流表)组织成一个层次结构的数据平面程序[30,138,144,160,178]。包头字段的子集是用来执行流表查找来确定相应的数据包处理动作，然后指示交换机重写数据包的内容,封装/解封装隧道包头、丢弃或转发数据包，或推迟数据包处理后续流表。开发人员通过标准化的API[159]动态设置流表的内容，添加、删除或修改带有相关匹配规则和处理动作的单个条目来配置包处理动作。这样做的好处是，可以向操作人员公开可重构的数据平面功能，这些操作人员使用熟悉的流概念，该概念由在某些包头字段上定义的匹配规则描述(在防火墙和ACL中广泛使用的一种抽象)。查找表的层次结构，也被传统的固定功能路由器ASIC所使用，用于合成更复杂的L2/L3/L4流水线。

通过OpenFlow协议[138]，Match-Action抽象在编程交换机中得到普及，而OpenFlow协议又极大地借鉴了Ethane[36]。OpenFlow的第一个版本只允许使用比较有限的报头字段集来定义单个流表；这个抽象后来被扩展为在一个预定义的包头字段数组上定义的多个流表的流水线。随着OpenFlow v1.1规范中多表的Match-Action流水线的引入，数据流图和Match-Action抽象之间的区别变得越来越模糊[138]。如图5的示例所示，可以很容易地将分层的Match-Action流水线定义为一个特殊的数据流图，查找表作为处理节点，“goto-table”指令作为边缘。

WeChat Image_20210322095525.png

图5 基本路由器的简单的Match-Action表依赖图 (通过图3推导出[30])

目前Open vSwitch[160]仍然是最流行的OpenFlow软件交换机，使用基于流缓存的通用数据路径来实现Match-Action流水线。ESwitch[144]对该设计进行了改进，引入了数据平面专门化和基于模板的动态数据路径编译，以实现行速率OpenFlow软件交换。尽管OpenFlow被广泛采用，但它在匹配任意报头字段方面受到了限制。这引发了对具有丰富语义、可配置控制流和特定于平台扩展的灵活查找表的研究。

在切换ASIC技术进步的驱动下，可重构匹配表(RMT)抽象[31]通过两种方式克服了OpenFlow ASIC中的主要限制：

即允许在任意报头字段上定义Match-Action表；
并扩展以前相当有限的可用包处理Action集。

虽然RMT允许在包报头内的任意位范围上进行匹配，并以可编程的方式对包头进行修改，但用于该体系结构的应用程序仍然受到该体系结构严格的顺序设计的限制。dRMT[39]放松了一些顺序处理约束，并通过将用于匹配数据包的内存库从处理阶段分离出来，提供了更灵活的体系结构。这种设计允许更有效地使用硬件资源，并且与RMT相比，增加了可映射到线速硬件架构的程序集。近年来，P4[30]及其配套的软硬件交换项目[1,21,178]受到了设备供应商、运营商和服务提供商等方面越来越多的关注[113,191]。

4.2 有状态的包处理

在互联网的早期，大多数有状态数据包处理发生在主机侧(例如,终止TCP连接)，而大多数数据包转发和处理网络中则为无状态方式(例如,设备不需要跟踪数据包之间的任何状态)。今天，有状态网络功能很常见，包括防火墙、网络地址转换器、入侵检测系统、负载均衡器和网络监控设备[198]。随着软件中高性能包处理能力的出现，网络功能越来越多地在服务器软件中实现，这种方法被称为网络功能虚拟化(NFV)。现在，可编程线速交换机允许更全面的可编程性。因此，这些设备通常用于交换和路由以外的任务。我们将在第6节中讨论新的用例和应用程序的示例。

有状态包处理的编程抽象

为可编程数据平面设备上的有状态包处理，提供灵活且与平台无关的编程抽象，仍然是当今的一个挑战。由于与大多数平台相关的复杂性和约束，有状态包处理通常仍然在SDN控制器中实现，显著降低了整体网络性能。

针对这个问题，一些著作提出了围绕有限状态机(FSM)的抽象，以简化有状态包处理管道的编程。然后，使用FSM抽象定义的数据平面程序可以被编译到线速硬件设备上[23,24,148,163]。其他更侧重于语言的方法包括Domino[185]，它引入了包事务的抽象，允许用类c的语言表达有状态数据平面算法，而不必定义Match-Action表或其他与体系结构相关的细节。硬件设计人员可以通过称为原子的小处理单元来指定它们的指令集，Domino编译器根据应用程序代码配置原子。Domino上的工作还为可编程线速交换机(称为Banzai machine)提供了一个机器模型，它可以用作Domino程序的目标，并可供社区使用。Domino程序的目标是单个交换机，而SNAP[15]允许程序员在“单个交换机”的网络抽象之上开发有状态的网络程序。SNAP编译器处理如何跨多个硬件目标分发、放置和优化对状态数组的访问。最后，SwingState[131]是一个状态管理框架，它通过将状态更新附加到常规的网络数据包，使可编程数据平面之间能够进行一致的状态迁移。P4语言的静态分析器检测需要迁移的状态，并相应地扩充用于带内状态传输的代码。

虚拟网络功能的状态管理

NFV承诺简化中间件部署，提高弹性和容错性，同时降低成本。然而，在实践中，由于NFV环境中状态和处理的紧密耦合，实现这些承诺仍然具有挑战性。状态需要在NF实例之间共享，或者为网络流的某个子集保留在本地。无论采用哪种方式，在分配流量以实现动态扩展或面对故障时，保持网络范围内的状态一致，从而使NF的行为正确都是很重要的。有几项工作旨在缓解这一问题。一般来说，它们可以被分类为：

将所有本地状态保存到NF，并在需要时传输状态[156,165,176]；
混合本地和远程状态[65,166]；
使用集中式或分布式远程状态[97,202]。

在这种情况下，与SwingState[131]相关的是statalyzr[106]，一个用于数据平面程序的静态分析框架。给定网络功能代码，它将确定需要迁移和克隆的状态，以确保在面临流量重分配或故障时的状态一致性。作者发现，对于许多网络函数，他们的系统可以大大减少需要迁移的状态量。

4.3 可编程Parser

也许每个网络设备最基本的操作是解析数据包头，以决定应该如何处理数据包。例如，路由器使用IP目的地址来决定下一个包发送到哪里，而防火墙将几个字段与访问控制列表进行比较，以决定是否丢弃一个包。由于包头的复杂性，包解析可能是高速网络的主要瓶颈之一[67]。包有不同的长度，并由包有效载荷前的几个级别的包头组成。在封装的每个步骤中，都有一个标识符指明下一个报头的类型，或者在解析数据包时指明下一个报头之后的数据类型，从而导致长顺序的依赖关系。此外，报头通常只提供部分信息(如MPLS)，而不完全指定后续报头类型，需要进一步的表查找或推测执行。

为高速网络实现低延迟的解析器尤其具有挑战性。为了减少开销，交换机经常使用统一的包解析器。这样的解析器使用一种算法，在一次传递中解析所有支持的包报头字段。虽然这可以提高性能，但它也增加了复杂性，并可能成为一个安全问题，特别是对于虚拟交换机[194]。可编程性是另一个关键需求，因为包头格式可能会随着时间的推移而改变，例如，由于新的标准或由于希望支持自定义包头。最近出现的头结构包括PBB、VxLAN、NVGRE、STT或OTV等等。为了支持新的或不断发展的协议，可编程解析器可以使用在运行时指定的解析图，例如，利用RAM和/或TCAM中实现的状态表[67]。

4.4 可编程调度器

把调度和排队策略的可编程接口暴露给开发人员是可编程网络环境中的另一个核心功能。Sivaraman等人[186]提出了一种解决方案，允许已知的和未知的调度算法被编程到交换机，而不需要重新设计硬件。所提出的设计使用了如下一些特性，调度算法作出两个决定：以什么顺序调度包和什么时候调度包。此外，在许多调度算法中，当数据包进入队列时，在处理的早期阶段就可以对这两个问题作出明确的决定，作者利用了这一特性。最终的设计使用了一个抽象：推入先出队列(PIFO)，这是一个优先级队列，用于维护调度顺序或时间。Mittal等人提出了另一种可编程包调度器的设计[142]。作者证明，虽然不可能设计一个通用的分组调度算法，但经典的最小松弛时间优先(LSTF)调度算法提供了一个很好的近似，并能满足各种网络范围内的目标。

在高速交换机中实现公平排队机制通常是昂贵的，因为复杂的流分类、缓冲区分配和调度需要在每个包的基础上。Sharma等人[181]为解决如何在链路上的所有流之间实现公平带宽分配的问题，提出了一种离行调度程序，称为旋转严格优先级，它模拟了一种理想的循环方案，即每个活动流在每轮中传输一个比特数据。这允许以近似排序的顺序从多个队列传输数据包。

增加链路速度和降低CPU速度的趋势，导致软件中的包调度的精度降低，以及更高的CPU利用率。虽然这个缺点可以通过将包调度卸载给硬件(如NIC)来克服，但这样做会损害软件包调度程序的灵活性。因此，理想情况下，硬件中的包调度应该是可编程的。“在硬件加速计算的时代,每个人都应该识别和卸载常见的抽象和原语，而不是单独的算法和协议”，基于这个判断，Shrivastav[183]提出了一种泛化的PIFO原始使用最先进的硬件包调度程序：Push-In-Extract-Out(PIEO)维护一个有序的元素列表，但在退出队列时通过支持可编程的基于谓词的过滤，允许从列表中的任意位置退出队列。PIEO支持大多数调度(工作保持和非工作保持)算法，可以抽象为以下调度策略：为每个元素(包/流)分配一个资格谓词和一个Rank。每当链接空闲时，在所有谓词为真的元素中，调度Rank最小的元素。谓词决定某个元素何时符合调度条件，而Rank则决定在符合条件的元素中按照什么顺序进行调度。通过PIEO调度器的硬件设计(也在[183]中提出)，证明了这种方法的可伸缩性。

4.5 编程语言和编译器

可编程数据平面的一个重要方面是用来实现数据平面功能的编程语言和编译器。在过去的几年里，我们看到了一些超越底层SDN协议的有影响力的尝试，比如OpenFlow、ForCES或NETCONF。新的高级数据平面编程语言允许根据抽象、通用和模块化语言来构造，用于在特定交换机体系结构中指定包处理策略。这些尝试在很大程度上是由于运营商对更复杂的SDN应用的需求。此外，现代的、更灵活的和可编程的线速网络硬件的能力，也激发了通过编程语言的途径来确定交换处理架构(即在解析阶段支持的Match-Action表和协议的布局)。图6描述了目前可编程数据平面系统中这两类语言抽象在概念上的差异。

WeChat Image_20210322095532.jpg

图6 应用在可编程数据面的语言和协议比较

SDN规则定义

SDN编程语言通常在SDN中提供的可见性数量上有所不同(请参阅[44]了解有关这方面的讨论)。一种众所周知的语言叫做Frenetic，它是一种采用高级拓扑和包处理抽象编写组合SDN应用程序的编程语言。Pyretic[62]通过添加对顺序组合、更高级的拓扑抽象和将虚拟字段引入包中的抽象包模型的支持来改进Frenetic。模块化应用可以使用静态策略语言NetCore[1445146]编写，它提供了基本动作、匹配谓词、查询策略和策略。Maple[199]简化了SDN编程：

允许程序员使用标准编程语言来设计任意的、集中的算法，控制整个网络的行为；
提供了抽象，将程序员定义的、集中的策略应用于网络处理中的每一个包。

为网络提供坚实的数学基础是SDN的基本要求之一。NetKAT[13]是实现这一目标的主要努力之一。NetKAT提出了用于过滤、修改和传输数据包的原语，用于并行和顺序组合程序的运算符，以及用于迭代的Kleene星形运算符。NetKAT提供了可以证明的语言是健全和完整的保证。一般来说，函数式语言已经变得流行起来，以提供这种更高层次的抽象，还包括PFQ-Lang[28]这样的语言，它允许利用多队列网卡和多核架构。

底层数据面定义

今天的可编程数据面的核心是如何指定和重新配置的问题，可编程交换芯片的底层架构和配置(例如布局和匹配操作序列表、协议理解的协议解析器和动作支持)的表达和灵活的方式。此外，在编译器的设计和基于语言的抽象的目标硬件架构方面也出现了挑战。

P4[30]是第一个也是最突出的用于在可编程数据平面内指定低级包处理功能的语言抽象和编译器。由于现有SDN控制协议的限制，如OpenFlow，它只允许一组固定的包头字段和动作，P4可以定义硬件包处理流水线包头解析器、逆解析器、匹配动作表，以及底层的动作。通过匹配任意位范围和用户定义的操作，这种语言抽象允许独立于协议的包处理。然后在单独的步骤中为底层数据平面目标编译P4程序。P4的起源源自Lavanya等人[95]，他们研究如何将逻辑查找表映射到物理表，同时满足程序中的数据和控制依赖关系。作者还提出了算法来生成延迟、流水线占用或功耗优化的解决方案。编译后的数据平面程序用于配置底层的硬件或软件目标，并且在运行时使用特定的控制接口(如P4运行时)填充P4定义的匹配操作表[74]。

P4在研究界迅速获得了广泛的欢迎，并被用于无数的项目中。特别是，从软件切换到完全可重构ASIC的广泛支持目标，以及广泛的行业采用，使P4成为全面和灵活的数据平面可编程的关键实现技术。例如，P4FPGA[200]是FPGA上P4程序的开源编译器和运行时。通过将P4提供的高级编程抽象与灵活而强大的硬件目标相结合，P4FPGA允许开发人员快速创建和部署新的数据平面应用程序。在这个方向上的另一项工作是P4->NetFPGA[84]，它在NetFPGA处理流水线中集成了P4描述的功能。其他编译器适用于不同的软件交换体系结构、智能网卡和可重构ASIC。

在数据层面上扩展的可编程性也为引入BUG或编写不安全代码打开了大门。因此，确保程序的正确性对于数据平面程序来说也非常重要。网络验证和程序分析方法旨在缓解这些问题。尽管在传统的网络范式中广泛使用，但全可编程数据平面系统的网络验证仍然是一个正在进行的研究领域。为此，Dumitrescu等人[52]提出了一种新的工具和算法，称为netdiff，用来检查相关P4程序和FIB更新的等价性，以便检测数据平面实现中的不一致行为和bug。同样，为了简化P4开发，更好地测试程序，并尽早发现bug，Bai等人提出了NS-4[17]，一个针对P4定义的数据平面的综合仿真框架。NS-4集成了流行的网络模拟器ns-3，可以有效地模拟运行P4编写的数据平面的大型多节点网络。

5 算法和硬件实现

可编程数据平面的各种算法，往往要在硬件上实现。在本节中，我们将讨论在可编程数据平面中使用的一些主要算法和硬件构建块。

5.1 可重配置的Match-Action表

传统的OpenFlow硬件交换机实现只允许在一组固定字段上进行包处理。像RMT[31]这样的可重构匹配表，允许程序员匹配和修改所有包头字段(或任意位范围)，使设备变得更加灵活和强大。例如，RMT是一种受RISC启发的用于交换芯片的流水线架构，它提供了一组最小的动作原语来指定包头如何在硬件中处理。这使得改变转发平面成为可能，而不需要更改硬件设计。

精确匹配表

大型网络(例如运行数百万VM的数据中心)需要高效的算法和数据结构来实现它们的转发信息库(FIB)，以便在交换芯片上达到数百万条目的规模。在软件交换机中实现这种高效内存和快速精确匹配FIB操作的一个高效的方法是使用高并发哈希表。例如，基于布谷鸟哈希(CuckooSwitch[208])的解决方案已经被证明能够在硬件的PCI总线上高效处理数据包，并且同时维护10亿表项的转发表。

前缀匹配表

在硬件中实现Match-Action表的可编程交换通常需要支持不同类型的操作和表。除了精确匹配外，IP地址查找和前缀匹配也是频繁的操作，因此受到了学术界的广泛关注。除了优化查找时间之外，考虑到这些设备上资源的严重限制，提高硬件中Match-Action表实现的内存效率也是一个重要的问题。为了提高IP转发表的内存效率，一种自然的解决方案是采用FIB聚合(FIB aggregation)，即用一个等价但更小的表示来替换现有的规则集。这种聚合可以静态执行(如ORTC[50])，也可以动态执行(如FIFA[129]、SMALTA[197]或SAIL[204])。Rétvári等人[168]探讨了利用压缩数据结构将FIB表大小减小到理论的最佳值，同时又不牺牲最长前缀匹配和FIB更新等标准操作的效率。他们的方法在Linux内核中的实现(使用重新设计的IP前缀树)显示了这种方法的可行性和好处。

受Zipf定律的启发，即某些规则比其他规则使用得更频繁，缓存代表了另一个优化机会。例如，在快速昂贵的硬件快速路径上缓存一小部分规则可能就足够了；不经常使用的规则可以移动到不那么昂贵的存储空间；例如，路由处理器或软件定义控制器的DRAM。不同的FIB缓存方案使用不同的算法来最小化缓存需要更新的次数[25,26]。

在用于灵活网络服务(如特定于客户和基于策略的路由)的虚拟路由器环境中，与资源约束有关的进一步挑战越来越多。特别是，为每个虚拟路由器支持单独的FIB可能会导致严重的内存扩展性问题。Fu等人[63]提出使用共享的数据结构和快速查找算法，该算法利用了虚FIB实例之间IP前缀的共性。

通配符包分类

包分类是实现网络服务(如防火墙包过滤和流量统计)的核心机制，通常使用三元TCAM或软件实现。TCAM和基于软件的方法通常都需要在(内存)空间和(查找)时间之间进行权衡。

内容可寻址存储器(CAM)和三元CAM (TCAM)芯片是可编程交换ASIC中最重要的组成部分，对可配置的包头字段进行分组分类。使用专用电路，规则可以按照优先级顺序匹配，并且只在单时钟周期内匹配。特别地，TCAM通过将数据包与所有三元编码分类规则并行比较，在恒定时间内对数据包进行分类。

大容量CAM的一个主要设计挑战是减少与大量并行有源电路相关的功耗，同时不牺牲速度或存储密度，并支持(通常需要)多维包分类[96]。尽管TCAM速度很高，但它也会遇到范围扩展的问题：当数据包分类规则的字段指定为一个范围时，将这些规则转换为与TCAM兼容的规则可能会导致规则数量激增。

一种降低TCAM高维分类功耗的方法是使用预分类器，例如，只考虑两个字段，如源和目的IP地址。因此，高维问题对于给定的数据包只能使用TCAM的一小部分。Ma等人[133]展示了如何设计预分类器，使每个包最多匹配预分类器中的单个条目，避免规则复制。SAX-PAC反过来利用了许多实用分类器包含大量独立规则的观察结果，允许以任意顺序进行相应的匹配，通常只考虑维度的一个小的子集[109]。此外，TCAM Razor[124]努力生成一个语义等价的报文分类器，该分类器需要非常少的TCAM表项。我们也知道，在分类器设计中固有的负时空权衡有时可以克服，例如，范围约束[109]。

Open vSwitch快速路径包分类器[160]可能是通用通配符包分类器最突出的应用，它结合了广泛的多层次流缓存和古老的元组空间搜索方案(Tuple Space Search scheme, TSS)[189]。TSS利用了实际规则数据库通常只使用少量不同字段长度的观察结果，因此，通过将规则映射到元组，即使对元组空间进行简单的线性搜索，也可以提供显著的加速，而不是在过滤器上进行简单的线性搜索。在TSS中，每个元组被维护为一个哈希表，可以在恒定的时间内搜索。虽然TSS在实践中被广泛使用，但最近有研究表明，在恶意算法复杂度攻击中可以利用线性搜索阶段来耗尽数据面资源并发动拒绝服务攻击[41,42]。

5.2 快速的表更新

匹配操作表不仅应该支持快速查找，还应该支持插入、修改或删除规则的快速更新。这种更新可以通过对TCAM进行分区和优化来加速。例如，Hermes[38]为了保证改进的性能，牺牲了一定数量的TCAM空间。此外，像ShadowSwitch[27]这样的软硬件混合交换机可以帮助降低流表入口的安装时间。特别是，由于软件表的更新非常快，所以在将转发表更新传播到TCAM之前，应该首先在软件中进行转发表更新，以卸载软件转发并实现更高的总体吞吐量。只有在没有条目与硬件中的数据包相匹配的情况下，才执行软件中的查找。像ShadowSwitch这样的解决方案进一步利用了从TCAM中删除条目比添加条目快得多这一事实，因此将一个条目安装转换为在软件表中安装和从硬件表中删除的混合。