QPipe: quantiles sketch fully in the data plane
QPipe: quantiles sketch fully in the data plane
复制标题
DOI：
10.1145/3359989.3365433
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Nikita Ivkin;Zhuolong Yu;V. Braverman;Xin Jin
中科院分区：
文献类型：
--
作者：
Nikita Ivkin;Zhuolong Yu;V. Braverman;Xin Jin
有效的网络管理需要收集数据包流的各种统计信息。直接监控数据平面中的流允许系统更快地检测异常。然而，监控算法必须处理每秒109个数据包的吞吐量，并保持非常低的内存占用。广泛采用的基于采样的方法遭受估计的低准确性。因此，很自然地会问：“是否有可能使用小内存占用在数据平面中维护重要的统计数据？".在本文中，我们肯定地回答这个问题的一个重要情况下的分位数。我们介绍QPipe，这是第一个完全可以在数据平面中实现的分位数绘制算法。我们的主要技术贡献是SweepKLL [27]算法变体的平面实现。具体来说，我们给出了argmin（）的新实现，它是SweepKLL的主要构建块，通常在商品交换机的数据平面中不支持。我们在P4中原型QPipe，并将其性能与基于采样的基线进行比较。我们的评估表明，对于固定的近似误差，内存减少了10倍，对于固定的内存量，误差提高了90倍。我们的结论是，QPipe可以是一个有吸引力的替代基于采样的方法。
Efficient network management requires collecting a variety of statistics over the packet flows. Monitoring the flows directly in the data plane allows the system to detect anomalies faster. However, monitoring algorithms have to handle a throughput of 109 packets per second and to maintain a very low memory footprint. Widely adopted sampling-based approaches suffer from low accuracy in estimations. Thus, it is natural to ask: "Is it possible to maintain important statistics in the data plane using small memory footprint?". In this paper, we answer this question in affirmative for an important case of quantiles. We introduce QPipe, the first quantiles sketching algorithm that can be implemented entirely in the data plane. Our main technical contribution is an on-the-plane implementation of a variant of SweepKLL [27] algorithm. Specifically, we give novel implementations of argmin(), the major building block of SweepKLL which are usually not supported in the data plane of the commodity switch. We prototype QPipe in P4 and compare its performance with a sampling-based baseline. Our evaluations demonstrate 10× memory reduction for a fixed approximation error and 90× error improvement for a fixed amount of memory. We conclude that QPipe can be an attractive alternative to sampling-based methods.