Diamond Sketch: Accurate Per-flow Measurement for Big Streaming Data
Diamond Sketch: Accurate Per-flow Measurement for Big Streaming Data
复制标题
Diamond Sketch：大流数据的精确每流测量
DOI：
10.1109/tpds.2019.2923772
复制
发表时间：
2019-12
影响因子：
5.3
通讯作者：
Li Xiaoming
中科院分区：
文献类型：
--
作者：
Yang Tong;Gao Siang;Sun Zhouyi;Wang Yufei;Shen Yulong;Li Xiaoming
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 (for big streaming data). 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 that are of the same size to record the number of packets in a flow, thus the counters are forced to be large enough to accommodate the size of the largest flow. Unfortunately, as most flows are small (i.e., mice flows) and only a very few flows are large (i.e., elephant flows), many counters represent very small values, which is a waste of memory. Sketches are often stored in fast but expensive memory (e.g., SRAM), thus it is critical to achieve high memory efficiency. To address this issue, we propose a novel sketch, namely the Diamond sketch. The Diamond sketch 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, thus 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. We made the source code of all the six sketches available on GitHub [1] .
登录
查看更多内容
DOI：
10.1109/iccnc.2015.7069350
发表时间：
2015-02
期刊：
2015 International Conference on Computing, Networking and Communications (ICNC)
影响因子：
--
作者：
Gil Einziger;R. Friedman
通讯作者：
Gil Einziger;R. Friedman
影响因子：
2.8
作者：
Tong Yang;Gaogang Xie;Yanbiao Li;Qiaobin Fu;A. Liu;Qi Li;L. Mathy
通讯作者：
Tong Yang;Gaogang Xie;Yanbiao Li;Qiaobin Fu;A. Liu;Qi Li;L. Mathy
DOI：
10.1002/spe.576
发表时间：
2004-02
期刊：
Software: Practice and Experience
影响因子：
--
作者：
A. Rousskov;D. Wessels
通讯作者：
A. Rousskov;D. Wessels
DOI：
10.1109/tpds.2017.2766633
发表时间：
2018-04
影响因子：
5.3
作者：
Da Tong;V. Prasanna
通讯作者：
Da Tong;V. Prasanna
DOI：
10.1109/tnet.2012.2192447
发表时间：
2012
期刊：
IEEE/ACM Trans. Netw.
影响因子：
--
作者：
Tao Li;Shigang Chen;Y. Ling
通讯作者：
Tao Li;Shigang Chen;Y. Ling