Diamond Sketch: Accurate Per-flow Measurement for Big Streaming Data

Authors:
Publisher website
Google Scholar
Abstract
Per-flow measurement is a critical issue in computer networks, and one of its key tasks is to count the number of packets in each flow. The literature has demonstrated that sketch is the most memory-efficient data structure for the counting task, and is widely used in distributed systems. Existing sketches often use many counters of the same size to record the number of packets in a flow, thus the counters need to be large enough to accommodate the size of the largest flow. Unfortunately, as most flows are small and only a very few flows are large, many counters represent small values, which is a waste of memory. Sketches are often stored in fast but expensive memory, thus it is critical to achieve high memory efficiency. To address this issue, we propose the Diamond sketch, which is composed of atom sketches, and each atom sketch uses small counters. The key idea of Diamond is to dynamically assign an appropriate number of atom sketches to each flow on demand, optimizing memory efficiency. Experimental results show that the Diamond sketch outperforms the best of the five typical sketches by up to 508.3 times in terms of relative error while keeping comparable speed.
Funding Information
  • Primary Research & Development Plan of China (2018YFB1004403, 2016YFB1000304)
  • National Natural Science Foundation of China (61672061)

This publication has 24 references indexed in Scilit: