HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows
HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows
复制标题
DOI：
10.1109/tnet.2019.2933868
复制
发表时间：
2019-10-01
影响因子：
3.7
通讯作者：
Li, Xiaoming
中科院分区：
文献类型：
--
作者：
Yang, Tong;Zhang, Haowei;Li, Xiaoming
发现top-k大象流是网络流量测量中的一项关键任务，在拥塞控制、异常检测和流量工程等领域有着广泛的应用。随着网络中线路速率的不断提高，设计准确、快速的大象流在线识别算法变得越来越具有挑战性。现有的算法严重限制了在实现高流量和小的片上存储器的约束下的精度。我们观察到，这些算法所采用的基本策略，要么需要显着的空间开销来测量所有流的大小，或在决定跟踪哪些流时产生显着的不准确性。在本文中，我们采用了一种新的策略，称为计数与指数衰减，以实现空间精度的平衡，通过衰减主动删除小流量，同时最大限度地减少对大流量的影响，从而实现高精度的发现top-k大象流。此外，所提出的算法称为HeavyKeeper招致小，恒定的处理开销，每个数据包，从而支持高线路速率。实验结果表明，HeavyKeeper算法在占用内存较小的情况下，准确率达到99.99%，与现有算法相比，误差平均降低了3个数量级左右。
Finding top-k elephant flows is a critical task in network traffic measurement, with many applications in congestion control, anomaly detection and traffic engineering. As the line rates keep increasing in today's networks, designing accurate and fast algorithms for online identification of elephant flows becomes more and more challenging. The prior algorithms are seriously limited in achieving accuracy under the constraints of heavy traffic and small on-chip memory in use. We observe that the basic strategies adopted by these algorithms either require significant space overhead to measure the sizes of all flows or incur significant inaccuracy when deciding which flows to keep track of. In this paper, we adopt a new strategy, called count-with-exponential-decay, to achieve space-accuracy balance by actively removing small flows through decaying, while minimizing the impact on large flows, so as to achieve high precision in finding top-k elephant flows. Moreover, the proposed algorithm called HeavyKeeper incurs small, constant processing overhead per packet and thus supports high line rates. Experimental results show that HeavyKeeper algorithm achieves 99.99% precision with a small memory size, and reduces the error by around 3 orders of magnitude on average compared to the state-of-the-art.