Page 411 - 《软件学报》2025年第8期

3834 软件学报 2025 年第 36 卷第 8 期

例如校验和、哈希、随机数、寄存器等. 目前有多种不同的交换机架构以及对应的可编程设备, 例如支持
V1model 的 BMv2 软件交换机, 支持协议无关交换机架构 (protocol independent switching architecture, PISA) 的
[15]
Tofino 交换芯片. 其中, PISA 架构主要由一个可编程的解析器、一个可编程的逆解析器和一个由多个阶段组成
的可编程匹配动作流水线组成. 其中, 解析器主要负责数据包头部信息的提取, 这一模块中允许开发人员通过有限
状态机实现自定义的数据包头解析过程. 可编程匹配动作流水线由多个匹配动作单元组成, 每个单元包含一个或
多个匹配动作表 (match-action table, MAT), 由开发者编写的 P4 程序将在编译器中转化为表的形式并在匹配动作
流水线中执行. 在最后的逆解析器中, 数据及其头部信息以指定的方式重新序列化并离开交换机.
Tofino 交换芯片是第 1 个支持 PISA 架构的以太网交换 ASIC, 其架构如图 2 所示. 在 Tofino 的架构中包括固
定的零阶段与内在元数据模块 (phase-0 and intrinsic metadata, PIM)、分组缓冲与复制模块 (packet buffer and
replication engine, PRE) 以及队列缓冲模块 (buffer queuing engine, BQE). Tofino 中提供基于 PISA 架构的可编程入
口模块与可编程出口模块, 这两个模块中分别包含一组完整的解析器、匹配动作流水线和逆解析器.

逆 逆
解 解
PIM 析 入口模块 解 BRE 析 出口模块 解 BQE
析
析
器 (ingress) 器 (egress)
器 器

… …

可编程入口模块流水线 可编程出口模块流水线
图 2 Tofino 架构示意图

1.2 Count-Min Sketch 数据结构
[16]
Count-Min Sketch 是一种由多个哈希表组成的数据结构, 这一结构用于统计在一组数据中各个不同元素的
出现频次. 这一数据结构在原有基于哈希表的简单计数方法上, 通过同时使用多组哈希表来缓解由于哈希冲突产
生的计数误差. 图 3 展示了 Count-Min Sketch 的工作原理, 该结构首先将会使用多组互不相关的哈希函数计算元
素关键值的哈希结果, 之后在每个哈希表的对应位置将计数值加 1. 当需要进行查询时, Count-Min Sketch 将会依
次查询每一个哈希表中对应位置的计数值, 并输出其中最小的一个作为查询结果.

哈希函数 1 +1

哈希函数 2 +1
关键值 取最小值
哈希函数 3 +1

哈希函数 4 +1

图 3 Count-Min Sketch 工作方式