ByteCuts
1 启示
2 摘要
3 基础知识
3.1 预备知识
3.2 文中基础概念
4 Introduction
5 Background
6 方案
B. 树状选择
基于树的方法，包括 ByteCuts，存在着一个叫做规则复制的问题。规则复制是由于通配符造成的规则落入多个分区，迫使它们被多次复制。这可以从图 5 中看出，规则 ra 和 rb 都被复制到了多个分区。现有的方法，如 EffiCuts[3]和 SmartSplit[4]，试图通过对规则进行分区，使同一分区的所有规则具有类似的特征来缓解这一问题。这大大减少了所需的复制量，因为更容易找到不触发任何通配符的好切割。
我们还根据规则的特征将规则列表 \(L\) 划分为一个树的列表 \(T\)。我们试图将具有相似特征的规则放在同一棵树上，因为这将导致更短的树。我们通过确保同一棵树上的所有规则都使用相同的核心比特集来做到这一点。这确保了至少有一个好的切割会存在。使用一个更大的核心将允许更多的良好切割，减少树的高度，但会排除不符合更严格要求的规则，增加树的数量。我们通过在排除的规则数量和给定切割的预期最大分区大小之间取得平衡来处理这个问题。为了提高效率，我们只使用连续的比特（以小数点为单位）作为核心；对于前缀字段，这相当于测量该特定字段的长度。
我们定义了两个阈值：一个是切割效率，一个是树的大小。我们定义 \(c\) 为最大碰撞率，\(n_c=c-n_L\)，其中 \(n_L\) 是 \(L\) 中尚未被放入树中的规则数量。同样地，我们定义\(χ\)为最大排除率，\(n_χ=χ-n_L\) 。\(n_c\) 和 \(n_χ\) 在以后的树中都会变小，因为 \(n_L\) 会变小；\(n_c\) 定义了可接受的碰撞极限，而 \(n_χ\) 定义了所需的最大排除规则数。
我们的目标是在满足某些平衡要求的情况下，使规则数量最大化（从而使树的数量最小化）。如果任何 filed 长对 \((f, w_f)\) 的碰撞限制低于 \(n_c\)，那么我们选择使排除的规则数量最小化的对。否则，从那些最多排除 \(n_χ\) 条规则中，我们选择碰撞限制最小的一对。如果这两个目标都无法达到，我们就选择 碰撞大小+排除规则 (collision size + rules excluded) 之和最小的一对。
一旦选择了一个字段长度对（f，wf），我们就从字段 f 的前缀长度至少为 wf 的所有规则中创建一棵树，如下一节所述。然后我们在剩下的规则上重复树的选择过程。
一旦剩余规则的数量低于某个阈值 \(τ\)（在我们的实验中为5%），我们就宣布剩余的规则为 "坏"（并推而广之，以前的规则为 "好"）。坏规则 通常在两个地址字段中都有相对较少的比特。如果 TCAM 是可用的，我们就把坏规则放到 TCAM 中。对于一个纯粹的 ByteCuts 解决方案，我们试图用所有的坏规则建立一个单一的树，只有当规则在切割阶段需要太多的规则复制时才会被移除（见第三部分-C）。具体来说，如果一条规则在树上的任何单独的切割中具有 5 个或更多的通配符位，我们才会因为规则复制而将其从树上删除。
对于每个字段，我们考虑每个可能的最左边的位，并为每个 \(0 < δ ≤ k\) 选择下一个可能的\(δ\) 位，这给我们一个 \(δ\) 位的选择。从每个规则 \(r_i\) 中，我们然后提取这些比特，并将其解释为一个数字。带有通配符的规则计算多个数字（通过用 0 和 1 替换 * ）。我们计算每个数字出现多少次。我们选择具有最小的最大频率的切割。这种切割将使最大的子树最小化。在出现平局的情况下，我们倾向于选择δ较小的切割，因为这样可以节省内存。
一旦选择了一个切割，我们就对规则进行分区。我们创建 \(2^δ\) 个分区。与上面类似，从每个规则 \(r_i\) 中，我们提取选定的 \(δ\) 位，将其解释为一个数字，然后将 \(r_i\) 放入与该数字对应的分区中。带有通配符的规则将被放置到多个分区中。然后我们对每个分区进行递归，创建一个新的子树。有些列表包含相同的规则集（因为有通配符）。我们检测到这一点，并只创建一个子节点，为这些子列表中的每一个共享。
例如，考虑分类器 I 的规则。在第三部分 B 中，我们选择了规则 r1 到 r7。如果我们选择源字段的前两位，那么一个分区将包含规则 r3、r4 和 r4，但如果我们选择最后两位，那么每个分区至多有 2 条规则，使其成为更好的选择。命运字段上的切割都没有那么好，因为它们需要将 r6 和 r7 复制到所有分区。因此，我们选择（011，000）作为我们切割的掩码。这就产生了四个孩子，其中 00 部分包含 r1 和 r6，01 包含 r2，10 包含 r3 和 r7，11 包含 r4 和 r5。在这种切割之后，每个分区只有 \(2≤n_{leaf}\) 规则，所以我们为每个部分创建一个叶子结点。
我们有两个优化，使切割选择更快。首先，如果一个规则在选择的位上有超过 4 个通配符，我们就认为它最终会出现在每个分区中。我们将这种规则的数量作为惩罚，而不是将其计入各个分区。这就避免了为有许多通配符的规则增加成千上万的频率。
第二个优化是，我们把所有的切割都对准了 nybble 边界：我们的最小切割尺寸是 1 nybble ，我们把切割长度增加 1 nybble ，在我们的实验中，我们的最大切割长度是 \(k=4\) nybbles （16 位）。这限制了子数组的大小，最多只能有 65536 个节点；增加这个限制会使数组大小增加，从而使潜在的内存使用量呈指数增长。我们只选择 nybbles ，因为在实践中，这些长度明显比其他长度更常见。因此，更精细的切割带来的好处很少，而时间成本却很高。