sketchPro：基于可编程数据平面上的概率更新来识别前k项

《IEEE Transactions on Network and Service Management》：sketchPro: Identifying Top-k Items Based on Probabilistic Update on Programmable Data Plane

检测可编程数据平面（PDP）上高精度前k大流量物品的轻量级算法sketchPro，通过动态概率更新机制优化内存使用，在10KB SRAM下实现95%+检测精度。

　　

摘要：

在网络流量中检测前k个最重的数据包对于流量工程、拥塞控制和安全分析至关重要。基于控制器的解决方案存在较高的通信延迟和较大的资源开销，这促使人们将这项任务转移到可编程数据平面（PDP）上。然而，PDP硬件（例如Tofino ASIC）每个流水线阶段仅提供几兆字节的片上SRAM，并且不支持循环操作或复杂的算术运算，这使得精确地检测前k个数据包变得非常具有挑战性。本文提出了一种基于草图的解决方案——sketchPro，它采用概率更新机制来保留较大的数据包，从而在有限的内存条件下实现前k个数据包的准确识别。sketchPro根据数据包的当前统计大小和哈希冲突的频率动态调整更新概率，从而有效地检测出前k个数据包。我们已在PDP上实现了sketchPro，包括P4软件交换机（即BMv2）和硬件交换机（Intel Tofino ASIC）。广泛的评估结果表明，sketchPro仅需10KB的内存即可达到超过95%的精确度。