Precise error estimation for sketch-based flow measurement
Precise error estimation for sketch-based flow measurement
复制标题
DOI：
10.1145/3487552.3487856
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Peiqing Chen;Yuhan Wu;Tong Yang;Junchen Jiang;Zaoxing Liu
中科院分区：
文献类型：
--
作者：
Peiqing Chen;Yuhan Wu;Tong Yang;Junchen Jiang;Zaoxing Liu
草图算法作为一类近似测量方法，显著提高了利用有限资源估计网络流量信息的效率。虽然这些算法在最坏的情况下可以进行合理的误差界分析，但它们的实际误差可能会随着传入流量的分布而变化很大，这使得它们的传统误差界过于松散，在实践中无法使用。在本文中，我们提出了一种简单而严谨的误差估计方法，利用草图计数器的知识来更准确地分析后验草图查询的误差。这种方法将使网络运营商能够了解当前测量的精确度，并相应地做出适当的决策(例如，识别潜在的重度用户或回答“假设”问题以更好地提供资源)。理论分析和轨迹驱动实验表明，我们对草图误差的估计界比以前的估计要紧得多，并且在大多数情况下与实际误差界相吻合。
As a class of approximate measurement approaches, sketching algorithms have significantly improved the estimation of network flow information using limited resources. While these algorithms enjoy sound error-bound analysis under worst-case scenarios, their actual errors can vary significantly with the incoming flow distribution, making their traditional error bounds too "loose" to be useful in practice. In this paper, we propose a simple yet rigorous error estimation method to more precisely analyze the errors for posterior sketch queries by leveraging the knowledge from the sketch counters. This approach will enable network operators to understand how accurate the current measurements are and make appropriate decisions accordingly (e.g., identify potential heavy users or answer "what-if" questions to better provision resources). Theoretical analysis and trace-driven experiments show that our estimated bounds on sketch errors are much tighter than previous ones and match the actual error bounds in most cases.