Brief of BeauCoup (SIGCOMM'20)

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：June.20 2021

本作品由 ZobinHuang 采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

    Section 3. Design：阐述了本文方案的设计；
        3.1 问题建模：对本文问题进行建模；
        3.2 基于 Coupon Collector 的数据结构：对 Coupon Collector 问题进行背景介绍，基于此描述了本文设计的数据结构；
        3.3 数据平面算法具体设计：基于 §3.2 描述的数据结构设计，阐述了数据平面的测量算法；
        3.4 参数编译设计：基于 §3.3 描述的数据平面测量算法，阐述了用于计算数据平面参数的编译算法；

Section 4. Prototype：阐述了 BeauCoup 在可编程交换机上的实现方法；

0. 术语约定

attribute (属性)：可以理解为测量任务需要收集的包头字段；
key (键)：测量任务的输入，可以是一个确定的 source IP，或者其它字段。一个测量任务需要观察多个 attribute，其中有一部分 attribute 是 key，测量结果通常是针对各个 key 做出的。比如某个测量任务的 key 是 source IP，那么这次测量分析的就是各个 source IP 的行为。

1. Problem

BeauCoup 要解决的是这样一件事情：如何在数据平面上，在满足内存空间约束和 per-packet 内存访问次数约束的情况下，同时处理多个查询任务。首先我们把这个大问题分解一下，分别为以下两个子问题：

Sub-problem 1: 测量任务的多样性

网络测量的任务可以被模型化为这样一件事情：对一系列数据包中的各个 attribute 的进行计数。对于单一的测量任务，其收集的是单个或者多个 attribute 的数目。不同测量任务要求收集的 attribute 通常是不一样的。因此，多样的测量任务以及他们对 attribute 的不同需求，使得同时运行多个测量任务变得富有挑战性。

Sub-problem 2: 可编程交换机上有限的资源

当下，可编程交换机可以支持直接在数据平面上在数据包流过的时候直接对网络流量进行分析。但是有限的内存空间和计算资源加大了精确测量的难度。

2. Situation

针对在 §1 中提出来的问题，现有的解决方案及问题如下：

针对 Sub-problem 1，为了支持对多种测量任务的同时运行，当下的绝大多数方案都依赖于运行在数据平面之外的测量软件来处理在数据平面的数据包，这样一来就引入了不可避免的时延和通信开销。其中，最简单的方案就是让上层控制器随机在数据平面进行采样，然后让测量软件基于这些采样的数据包去计算测量数据，这样的精确度是最差的；另外的方案还有比如在控制器统计所有可能与测量任务相关的流的信息，这样以来虽然提高了精度，但是却增大了从数据平面提取的数据的体积 (浪费通信资源)，并且使得测量任务的数量变得不可扩展。

针对 Sub-problem 2，为了支持在资源有限的可编程交换机上实现在数据平面上直接对流量进行测量，现有的传统方案通常把关注点放在如何应对数据平面有限的内存空间上，它们方案都是设计了可以用于计算单一测量任务估计值的数据结构，或者是计算多个基于相同包头字段的测量任务的数据结构。然而，这样的方案在遇到需要同时运行多个基于不同包头字段的测量任务时，会变得十分困难，原因有二：

为了支持多个基于不同 attribute 的测量任务，就必须实例化多个数据结构，这样一来就无法满足内存不足的约束；
为了保持线速率，可编程交换机通常仅支持针对一个数据包有较少的几次内存访问，这样一来针对同一个数据包同时更新多个数据结构的操作就显得不可行。

3. Design

(1) 问题建模

BeauCoup 对网络测量问题的建模如下面所示：

测量任务 `q` 会将每一个数据包 `i` 中按照其想观测的键 `key_q(i)` 进行映射，并且对属于同一个键的其他属性 `at tr_q(i)` 的数量进行计数。如果超出了数量超出了预先设置的阈值 `T_q`，则会输出一个针对特定观测任务和键值的警告 `(q,k)`。即，在一定的时间窗口内，测量任务的在满足以下条件时，会发出警告 `(q,k)`：

`|{at tr_q(i)|key_q(i)=k}| > T_q`

BeauCoup 的设计目标是：在 (1)内存的最大存储空间约束 `S` 和 (2)针对每个数据包能够对内存发起访问的次数约束 `\Gamma` 的条件下，系统可以同时执行多个测量任务 `Q={q_1, q_2, ...}`，并且在计数器超过相应阈值时输出警告 `(q_j, k_j)`。

(2) 基于 Coupon Collector 的数据结构

BeauCoup 的设计基于赠券收集问题 (Coupon Collector's Problem)，这边做下背景补充^[1]：

赠券收集问题 (Coupon Collector's Problem)

(1) 问题描述

假设有 `n` 种赠券，每种赠券的收集概率相同，且赠券无限供应。问若取赠券 `t` 张，能够集齐 `n` 种赠券的概率是多少？

(2) 求解

假设 `T` 为集齐所有 `n` 种赠券的次数，`t_i` 是收集了 `i-1` 种赠券后，收集到第 `i` 种赠券的次数。此处可以发现 `T` 和 `t_i` 都是随机变量。

对于 `t_i`，收集到 `i-1` 种赠券后每次抽取能找到一种"新"赠券的概率是：

`p_i=(n-i+1)/(n)`

并且，我们可以发现 `t_i` 服从几何分布，即在收集第 `i` 种赠券的过程中，每次抽取都是相互独立的，并且在第 `k` 次中抽取到第 `i` 种赠券的概率为：

`P_i(ξ=k) = (1-p_i)^(k-1)p_i`

因此我们根据几何分布规律，得到 `t_i` 的期望为：

`E(t_i) = 1/(p_i) = (n)/(n-i+1)`

综上我们可以得到集齐所有 `n` 种赠券的次数 `T` 的期望为：

`E(T) = E(t_1) + E(t_2) + ... + E(t_n) = n/n + n/(n-1) + ... + n/1 = n(1 + 1/2 + ... + 1/n) = nH_n`

其中，等式最后的 `H_n` 是调和数^[2]，由调和数的估算值，我们直接代入得到：

`H_n ~ \lnn + \gamma + 1/(2n) + 1/(2n) - 1/(12n^4) + 1/(120n^4) - ...`，其中 `\gamma \approx 0.5772156649`，为欧拉-马斯刻若尼常数

赠券收集问题期望

`E(T) = n\lnn + n\gamma + 1/2 + O(1)`, 当 `n \rightarrow \infty`

那么可用马尔可夫不等式^[3]来求取概率的上限：

`P(T \geq cnH_n) \leq 1/c`

理解了 Coupon Collector 后，现在我们来看一下 BeauCoup 的基本 Idea。

如上图所示。针对每一个 Query 的每一个 activated 的 Key (之前已经观测过的 Key)，BeauCoup 都会维护一个 Coupons 来记录收集到的 Attributes 的情况。与 Coupon Collector 不同的是，BeauCoup 把一个新的观测到的 Attribute 当作一次对 Coupons 的抽取。这样一来，类比 Coupon Collector，我们就能猜到：BeauCoup 构建的是 Coupons 个数和 Attributes 种数 的关系。当一个数据包到来的时候，首先 BeauCoup 会：

选择一个 Query 任务
提取数据包的 Key
根据数据包的属性 (attributes) 使用 Hash Function 计算并决定是否更新 Coupon；若更新，更新哪一个 Coupon

随后，BeauCoup 抽取 (draw) Table 中的相应位置的 Coupon。当某个 Query 下的某个 Key 拥有的 Coupons 的抽取数量足够时，就会触发告警 `(q_j,k_j)`。相比于传统方法 (i.e. 针对各个 Key，在内存中对观察到的 Attributes 进行计数)，这样的方案对 (1)占用内存数和 (2)per-packet 内存访问次数都比较友好。下面详细分析一下以上三步的具体实现方法。

(3) 数据平面算法具体设计

首先明确一点，BeauCoup 的具体设计都紧紧围绕着严格的 per-packet 内存访问次数展开。

a. 每个 Query 下的每个 Key 的 Coupons 的抽取条件

针对每个 Query 下的每个 Key 的 Coupons (以下简称 Coupons)，当数据包到来时，首先会使用一个 Hash Function 将想要观测的 Attributes 的映射为一个 [0,1) 的数。然后，根据这个算出来的数，决定抽取哪一个 Coupon。以上图为例，若算出来的数位于 [0,1/8)，则抽取 Coupon #1，若位于 [1/8, 1/4)，则抽取 Coupon #2，以此类推。每一个 Query 都有一个 probability 的设置值，意为在一次哈希过程中抽取一个 Coupon 的可能性，如上图的例子，probability 就为 1/8。若算出来的哈希值位于 [1/2, 1)，则不抽取任何 Coupon。这实际上是对一个 Query 内的 per-packet 的内存访问次数做了压缩，我们通过以下模型来理解一下：

我们有 Hash Function：

`h:{at tr_q(i),\foralli}\rightarrow[0,1)`

假设我们有 `m_q=4` 个 Coupons，然后上文提到的 probability 假设我们设定为 `p_q=1/8`，于是我们得到：在一个 Query 中，针对一个数据包平均我们只会抽取 `\gamma_q = m_q*p_q = 1/2` 次 Coupon。也就是说一个 Query 并不会为每一个数据包去抽取 Coupon，而节省出来的 Memory Access Budget 就可以留给另外的 Query 任务。BeauCoup 通过这种方式使得在最大 per-packet 内存访问次数 `\Gamma = O(1)` 的约束下实现了多个 Queries 的并发运行。

因此，对于 `m_q` 和 `p_q` 的取值，我们需要满足下面这个约束，即一个 Query 任务的最大 per-packet 内存访问次数约束：

`m_q*p_q \leq \gamma_q = \Gamma/(|c*Q|)`，其中 `\Gamma` 是 per-packet 内存访问次数约束，`Q` 是 Query 任务数

然而，即使我们有了这样的压缩机制，但是难免会碰到：一个数据包需要去抽取多个 Query 任务的 Coupons，这样一来就违背了严格的常数规模的 per-packet 的内存访问次数约束 `\Gamma`。BeauCoup 对多个 Query 都需要对内存发起访问的情况进行了优化，详看下面。

b. 合并有相同 Attribute 需求的 Queries

对于那些有着相同观测 Attribute 的 Queries，它们的哈希函数是可以合并的。因此，如上图所示，我们把它们的哈希计算和映射放在了一起。这样一来，通过合并一部分哈希函数，我们一定程度减少了多个 Query 同时需要对内存发起访问的情况。

c. 相互竞争的 Query 的选择机制

在我们完成对可以合并的哈希函数的合并后，BeauCoup 就会呈现上面的形态。当一个数据包到来时，会同时触发多个哈希函数的计算 (每个哈希函数对应一组 Attributes，相同 Attributes 需求的 Query 任务的哈希函数已经被合并)。如果只有一个哈希函数需要触发对 Coupons 的抽取，那么就启动对相应内存的访问；如果有两个，那么会有一个抛硬币机制决定谁去抽取 Coupons；如果超过两个哈希函数需要抽取 Coupon，那么此轮将不更新。

(4) 参数编译设计

a. 模型设计

在 §3.3 的讨论中，我们发现数据平面在运行测量算法的时候需要这样几个参数：

参数	含义
`m_q`	测量任务 q 所需要的 coupon 的总数
`n_q`	测量任务 q 用以触发告警的已统计 coupons 所需数量
`p_q`	测量任务 q 中各个 coupon 被抽取的概率

上面这几个数据平面的参数，是编译器在编译阶段根据下面的输入参数计算出来的：

参数	含义
`T_q`	测量任务 q 触发告警所需要观测的 Attribute 的种类数目
`\gamma_q`	测量任务 q 平均 per-packet 的 coupon 抽取次数

也就是说，根据输入 `T_q` 和 `\gamma_q` 约束，编译器会输出一组 `(m_q, n_q, p_q)`。下面我们描述编译器计算出这组 `(m_q, n_q, p_q)` 的过程。

首先我们区分一下 BeauCoup 的模型与传统 Coupon Collector 问题模型的区别。

对于传统 Coupon Collector 问题，有 `n=m`，即只有在 Coupon 全部被抽取才算结束。但在 BeauCoup 的模型中，有 `1 \leq n \leq m`，即 Coupon 无需全部被抽取，仅需抽取 Coupon 的子集即可；
对于传统 Coupon Collector 问题，有 `p=1/m`，即抽取到各个 Coupon 的概率是 Coupon 种类数目的倒数。但在 BeauCoup 的模型中，有 `0 \leq p \leq 1/m`。因为我们的哈希函数导致了有些 Coupon 是"无效的"。

基于此，我们推导一下在 BeauCoup 模型中的抽取次数的期望 (即要多少种类数目的 Attribute，才能够结束抽取)：

BeauCoup 下的赠券收集问题

假设我们已经抽取了 `j-1` 个 Coupons，设那么我们在抽取到一个新的 Coupon 的次数为 `t_j`，抽取到一个新的 Coupon 的可能性为:

`p(m-j+1)=(m-j+1)*p_(each)`，其中`p_(each)` 为抽取到单个 Coupon 的概率

正如我们在 §3.2 中分析的，`t_j` 服从几何分布，因此其期望为：

`E(t_j) = 1/(p(m-j+1)) = 1/((m-j+1)*p_(each))`

我们一共需要抽取 `n` 个 Coupons 才能结束抽取。因此，当我们确定 `m`，`n` 和 `p` 的值时，它们所确定的总共需要抽取次数期望为：

`E(m, n, p) = \sum_{j=1}^{n}1/(p(m-j+1)) = \sum_{j=1}^{n}1/((m-j+1)*p_(each))`

这时我们就能得到了输入和输出的关系了。举例说，假设 Query `q` 给目的 IP 这个 Attribute 定的阈值是 `T_q`，那么我们的编译器就要输出合适的 `m_q`，`n_q` 和 `p_q` 的值，使得 `E(m_q, n_q, p_q)` 与 `T_q` 的偏差最小，同时满足内存访问约束 `m_q*p_q \leq \gamma_q`。

然而，基于上述关系输出的 `(m_q, n_q, p_q)` 潜在组合的数字可能会有很大的方差，因此我们必须定义一个量来评估一个 `(m_q, n_q, p_q)` 组合的 Accuracy，从而挑选出合适的 `(m_q, n_q, p_q)` 组合。定义如下：

假定在观察数据包 `i_1, i_2, ..., i_t`后，应用参数 `(m_q, n_q, p_q)` 的数据平面告警 `(q, k)`。我们令该数据平面真实观察到的 Attribute 的种类数目为：`\tau = |{at tr_q(i)|key_q(i)=k, i \in i_1, i_2, ..., i_t }|`
应用参数 `(m_q, n_q, p_q)` 的数据平面的绝对误差为：`\tau - T_q`
应用参数 `(m_q, n_q, p_q)` 的数据平面的相对误差为：`(\tau - T_q)/T_q`

BeauCoup 会准备一张查找表，里面算出了应用各组 `(m_q, n_q, p_q)` 参数的数据平面的测量平均相对误差。我们在算出 `(m_q, n_q, p_q)` 潜在组合后，从中挑选一个平均相对误差最小的组合作为我们最终生成的参数。

b. 工程实现

结合实际的工程实现，我们总结一下参数编译器根据输入的 `T_q` 和 `\gamma_q` 获取最佳配置参数组合 `(m_q, n_q, p_q)` 的过程。

首先我们约定：

由于交换机内存读取一次性能读 32-bit 数据，因此为了提高效率，实现一次内存访问就实现一次 Coupons 抽取，我们规定 `m_q \leq 32`
为了实现哈希函数的高效映射，我们要求 `p_q` 必须是 2 的幂次方
正如上面一直强调的，我们必须满足内存次数访问约束：`m_q*p_q \leq \gamma_q`

以下是求出参数的过程：

遍历所有可取的 `p_q=2^(-j)`，我们求出最大的可取的 Coupons 数目 `\overline{m_q}=min(32, \gamma_q/p_q)`。如果 `\overline{m_q} < 1`，则编译退出。
对于各个可取的 `p_q=2^(-j)`，我们穷举出所有可取的满足 `1 \leq n_q \leq m_q \leq \overline{m_q}` 的 `n_q` 和 `m_q`，并且求出基于这些配置的期望 `E(m_q, n_q, p_q)`。我们保留那些精读比较高的期望值 (5%偏差：`0.95T_q \leq E(m_q, n_q, p_q) \leq 1.05T_q`) 所对应的 `(m_q, n_q, p_q)` 配置。
根据查找表找出测量平均相对误差最小的 `(m_q, n_q, p_q)` 配置作为编译输出

4. Prototype

基于 §3 中讨论的数据平面算法设计，和参数编译器的计算原理，在本章我们首先介绍一下 BeauCoup 在可编程交换机上的数据平面的工作模式落地，然后介绍编译器是如何配置数据平面的。

(1) 数据平面工作流程

首先我们来看一下 BeauCoup 是如何在数据平面处理 Query 任务的。

a. 选择一个 Query

当数据包到来的时候，BeauCoup 会先抽取它的 Queries 们关心的 Key，并且送进各个 Hash Function，算出来一个 16-bit 的码，通过查询在 TCAM 中为各个 Hash Function 分别设置的 Table，利用掩码机制，就能得出各个 Hash Function 的输出是否映射到了某个 Query 下的某个 Coupon 上，如上图所示。如我们在 §3 中所讨论的，当只有一个 Hash Function 需要更新 Coupon 时，这个阶段就结束了；当有超过两个 Hash Function 需要更新 Coupon 时，这个阶段也结束了；当有两个 Hash Function 需要更新 Coupon 时，BeauCoup 会使用一张 Tie Break Table，利用一个随机数生成器，最终决定执行哪一个 Hash Function 的输出，我们使用下面的论文原图来观察可能会更加直观些。

b. 更新相应 Coupon

在完成上一步对 Query 任务的选择之后，随后就会对位于 SRAM 中的 Coupon 发起更新。在 SRAM 中一共使用了三个寄存器数组 (register array)，在一个寄存器数组中，有 `S` 个 32-bit 寄存器，如下图所示。这三个寄存器数组中，有用于标识对应 Coupon 是否超时的 Timestamp 寄存器 `\Gamma S(·)` ，有用于标识是否发生哈希冲突的 Checksum 寄存器 `QK(·)`，有用于存储真正 Coupon 数据的 Coupon 寄存器 `C C(·)`。下面我们来看更新过程

首先我们会有个 Index Hash Function，其根据 `(q, key_q(i))` 元组输出用于标示寄存器的序号 `idx`。并且我们将我们在上一步中拿到的欲更新的 Coupon 的编号转化为一个 32-bit 热编码 (e.g. 00..010...000)，即 `o n e h o t(c)`，随后：

检查是否存在相应 Coupon：检查 `\Gamma S(idx) < i.t i m e s tamp - W` 是否成立。若成立说明，该 index 上的 Coupon 已经超时被释放掉了。此时我们令：`\Gamma S(idx) = i.t i m e s tamp`，`QK(idx) = check s u m(key_q(i))`，`C C(idx) = o n e h o t(c)`
若上一步的时间戳检查并没有超时，即 `\Gamma S(idx) \geq i.t i m e s tamp - W`，则检查 `\Gamma S(idx) = i.t i m e s tamp` 是否成立，若成立则更新 Coupon：`C C(idx)= C C(idx) | o n e h o t(c)`
若上一步的 Checksum 检查没有通过，则说明有不同的 Key 都映射到了同一个 Coupon 寄存器 `C C(idx)` 中，一个 Coupon 寄存器是只为一个具体的 Key 使用，因此这样显然发生了冲突。这样一来，BeauCoup 只有抛弃这次更新。这样的 Coupon 寄存器冲突代表 Coupn 的数量太多了。

(2) 编译器的对数据平面参数的配置

a. Query Compiler

Query Compiler 根据输入的描述各个 Query 的 yaml 文件 (i.e. Key, Attribute, Exceed)，输出所有根据上面算法求得的哈希函数，输入的哈希函数如下图所示，各个哈希函数合并了同类 Attribute 需求的 Query：

Zobin