A Memory-Compact and Fast Sketch for Online Tracking Heavy Hitters in a Data Stream
Network traffic measurement is important for network man-agement,including bandwidth management to mitigate net-work congestion,and security management to detect DDOS attacks and worm spreading.However,with the explosive volume of network data and the fast transmission speed of network packets(in giga or even tera bps),it is a challenging task to measure the size of each network flow both accurately and memory-efficiently,using the size-limited SRAM mem-ory of line card.Therefore,many sublinear space algorithms for processing data streams have been proposed,such as CountMin(CM),Count Sketch(CS)and Virtual Active Coun-ters(VAC),which achieve extreme memory compactness by providing probabilistic guarantees on flow size measure-ment accuracy.However,these existing algorithms can still be greatly improved as to the performance of both online recording and querying the per-flow size,which is needed for online tracking heavy hitters.Our paper proposes a highly compact and efficient counter architecture,called CountMin virtual active counter(CM-VAC),which provides more ac-curate measurement results than CM and CS under a very tight memory space.We also achieve higher query speed than VAC by modifying its query policy.We demonstrate the superior performance of our algorithm by both experimental results and theoretical analysis based on CAIDA network traces.
Zhiying Tang Qingjun Xiao Junzhou Luo
School of Computer Science and Engineering,Southeast University Nanjing,China School of Cyber Science and Engineering,Southeast University Nanjing,China
国际会议
2019国图灵大会(ACM Turing Celebration conference-China 2019 )
成都
英文
377-382
2019-05-17（万方平台首次上网日期，不代表论文的发表时间）