摘要：
识别“heavy hitter”数据流或数据平面中具有大流量的数据流对于多种应用（例如，知道流量大小的路由，DoS检测和流量工程）来说非常重要。
然而，数据平面中的测量受到线速处理（10-100Gb / s）和交换硬件中有限内存需求的限制。
提出了HashPipe，这是一种使用新兴的可编程数据平面的heavy hitter检测算法。HashPipe实现了哈希表的管道，该哈希表保留了重流的计数器，同时随着时间的推移逐出了较轻的计数器。
背景/问题：
许多网络管理应用程序可以从发现对链路贡献大量流的流量中受益：例如，减轻链路拥塞，规划网络容量，检测网络异常和攻击，或缓存转发表条目。
此外，在较小的时间尺度上（与流量变化相比较）识别此类“heavy hitter”可以实现重流的动态路由和动态流量调度。人们希望始终在网络中的所有交换机上运行重流监视，以快速响应短期流量变化。
在交换机中处理数据包时，是否可以识别属于高流量的数据包，以便交换机可以对其进行特殊处理？现有的监视heavy hitter的方法很难以可接受的开销获得合理的准确性。
NetFlow的形式进行数据包采样在软件中处理采样数据包的CPU和带宽开销使其无法以足够高的速率进行采样。而另一种方法，sketch需要大量的内存开销来检索heavy hitter。
新兴的可编程交换机使我们不仅可以进行采样，哈希和计数，还为在交换机上运行新颖算法提供了机会。
当在10-100个端口上以每个端口10-100 Gbps的线速运行时，可以对这些交换机进行编程，以维持多个数据包的状态，例如，将流标识符作为keys带着计数器。
但是交换机受到保持高分组处理吞吐量的需求的约束：
- 确定性的小时间预算（1 ns），用于在每个阶段处理状态和处理数据包
- 每个阶段对内存存储状态的访问次数有限，通常只有一次readmodify-write
- 每个阶段可用的内存量有限
- 需要仅将大部分数据包通过管道移动一次，以避免停顿和降低吞吐量
解决办法：
我们提出了HashPipe，该算法可在可编程交换机的功能和约束范围内以高精度跟踪最重的k个流量。
HashPipe在哈希表的流水线中维护流标识符（“键”）和交换机中的重流计数。
当数据包散列到流水线第一级中的某个位置时，如果有命中（或空插槽），则将更新（或初始化）其计数器。如果有遗漏，则以现有密钥为代价插入新密钥 。
在所有下游阶段，随包一起携带刚刚收回的物品的密钥和数量，在哈希表中查找的与携带的密钥之间，具有较大计数的密钥将保留在哈希表中，而另一个密钥则与数据包一起携带到下一个阶段，或者如果密钥被携带，在最后阶段则将从交换机中完全删除数据包。
因此，HashPipe使用流水线操作对哈希表中的多个位置进行采样，并使用较轻的键代替较重的键，从而在有限的可用内存中“清除”沉重的键，并且每个阶段仅更新一个位置。
Hashpipe算法实现细节：
节省空间：
要跟踪k个最重的项目，节省空间的方法是使用一个具有m个（为O（k））插槽的表，每个插槽都标识一个不同的流的密钥及其计数器
当数据包到达时，如果表中还没有对应的流，并且表中还有剩余空间，则空间节省功能将插入新的流，计数为1。如果表中存在流，算法将更新相应的流计数器。但是，如果表已满，并且在表中找不到流，则该算法将表中具有最小计数器值的流条目替换为传入数据包的流，并递增此最小值计数器。
最小值采样：
我们要做的是查看随机选择的计数器的较小的恒定数量d的最小值，而不是整个表，将每个数据包的最坏情况的存储器访问次数限制为较小的固定常数d。
算法2中显示了修改后的版本HashParallel。
与算法1相比，主要变化在于检查了一组表插槽（在查找或更新任何键时），该表插槽现在是通过对表哈希进行哈希处理而获得的d个插槽集合，使用d个独立哈希函数的传入密钥。
实际上，我们对表进行采样以使用几个位置来估计最小值。但是，只有d个插槽的最小值可能会与整个m个插槽表的最小值相距甚远。最小值的设定值可能会影响有用的错误保证，以节省空间。
哈希表的多个阶段：
为了减少对内存的读取次数，以方便以线路速率进行操作，我们将计数器表T拆分为d个不相交的表，并且每个表正好读取一个插槽。
由于不同的数据包可以同时访问不同的表，因此该设计可以使对d表的内存访问的流水线化，但是，数据包可能需要通过此流水线两次：一次确定d个时隙中最小值的计数器，第二次更新该计数器。
前馈包处理：
现在，我们使用两个关键思想来减轻通过交换管道多次处理数据包的需求。
首先，跟踪滚动最小值：通过将计数器和密钥作为包元数据在管道中移动，我们跟踪当数据包穿过管道时到目前为止看到的最小计数器值（及其密钥）。
其次是始终插入第一阶段：如果在管道的第一个阶段中找不到传入密钥，则没有关联的计数器值可与该表中的密钥进行比较。在这里，我们选择始终在第一个阶段插入新的流，并将现有的密钥和计数器逐出数据包元数据，在该阶段之后，分组可以以上述通常的方式跟踪后续阶段的最小滚动。
其实整个HashPipe的结构都可以用图三的算法表示出来。
