Monitoring Heavy-Hitter Flows in High-Speed Network Concurrently

Identifying heavy-hitter flows in high-speed network link is important for some applications. This paper studied the approach of measuring various heavy-hitter flows simultaneously. We proposed a novel scheme, named TS-LRU (Two-Stage Least Recently Used), which process arriving packets through two stages to extract heavy-hitter flows. New packets are aggregated into FGFs (Fine-Grained Flow) and preserved in Stage1. The FGFs with no arrival packets for a relative long time are evicted from Stage1 using LRU replacement. The replaced FGFs are added into Stage2 and aggregated into RGFs (Rough-Grained Flow) further. The replacement scheme used in Stage2 is based on LRU with considering RGF size, named LRU-Size. There could be several similar data structures in Stage2 to extract different types of RGFs concurrently. Mathematical analysis indicates that this algorithm can save memory space and improve processing speed efficiently through exploiting the distribution characteristics of flows. We also examined TS-LRU with simulated experiments on real packet traces. Other than the proportional increasing of common approaches, the average processing time per packet of TS-LRU increases more slowly when measure multiple types of flows concurrently. Compared to the well-known multi-stage filters algorithm, TS-LRU achieves superior performance in terms of measurement accuracy in constrained memory space.