Jigsaw-Sketch:a fast and accurate algorithm for finding top-k elephant flows in high-speed networks  

作　　者：Boyu ZHANG He HUANG Yu-E SUN Yang DU Dan WANG 

机构地区：[1]School of Computer Science and Technology,Soochow University,Suzhou 215006,China [2]School of Rail Transportation,Soochow University,Suzhou 215006,China

出　　处：《Science China(Information Sciences)》2024年第4期109-126,共18页中国科学（信息科学）（英文版）

基　　金：supported in part by National Natural Science Foundation of China(Grant Nos.62332013,62072322,U20A20182,62202322);Natural Science Foundation of Jiangsu Province(Grant No.BK20210706);Jiangsu Planned Projects for Postdoctoral Research Funds(Grant No.2021K165B)。

摘　　要：Finding top-k elephant flows in high-speed networks is one of the most fundamental network measurement tasks.It is more challenging than per-flow size estimation since the IDs and sizes of top-k flows must be tracked simultaneously.Most existing studies only record the IDs of a small number of elephant flows to fit their estimators in the extremely limited high-speed on-chip memory.However,these solutions need too many memory accesses when a packet arrives to track the elephant flows with high accuracy,which limits their practicability.Therefore,this paper proposes Jigsaw-Sketch,a new algorithm to find the top-k elephant flows with much fewer memory accesses while achieving high memory efficiency and accuracy.In this design,we propose a novel two-stage jigsaw storage scheme,which can capture the candidate top-k flows from massive network steams efficiently,and further find the top-k elephant flows with high memory efficiency and only a few memory accesses for each packet.Extensive experimental results based on real network traces show that Jigsaw-Sketch improves the packet processing throughput by at least 86%,while achieving smaller memory footprints and higher accuracy compared to the SOTA.

关 键 词：SKETCH TOP-K network measurement elephant flow high-speed networks 

分 类 号：TP393.06[自动化与计算机技术—计算机应用技术]