MIME: Fast and Accurate Flow Information Compression for Multi-Spread Estimation

Spread estimation is an essential issue in high-speed networks with wide applications, such as network billing, quality of service, anomaly detection, etc. As a promising technique, sketch can efficiently estimate per-flow spread with only a small memory cost. Many studies focus on improving the performance of sketches. However, these works primarily focus on optimizing the counter level or sketch level without considering the scenario of multi-spread estimation, which is crucial for improving memory utilization and detecting anomalies. In this paper, we propose an efficient flow information compression algorithm based on the on-chip/off-chip hybrid framework to estimate multiple flow spreads. In the on-chip memory, we filter out non-duplicates and sample them to the off-chip space for recording. In the off-chip memory, we compress each sampled non-duplicate to a carefully designed bit-cube. When the measurement is finished, we separate corresponding KV-flows from a specific flow based on the user query. Then, we rebuild this flow to a subset group based on the duplicate number of each KV-flow. Finally, according to the Multi-set theory, we derive an accurate multi-spread estimate formula to solve this issue with a high throughput and small on-chip memory usage. Furthermore, we evaluate the performance of our proposed estimator using real Internet traffic traces downloaded from CAIDA. Experiments show that, compared to the state-of-the-art, our proposal achieves a 97.2% lower average relative error in per-destination source flow spread estimation with a tight on-chip memory, e.g., 320KB. And our proposed method achieves 31.86 higher processing throughput.