Hierarchical Sketch: An Efficient Solution for Threshold-t Flows Measurement in High-Speed Networks

Per-flow size measurement has wide applications in data center networks, such as flow scheduling, anomaly detection, and traffic engineering. To fit the module into limited on-chip memory and catch up with the line speed, existing works either use the bit sharing scheme to compress the flow information or require complex calculations to screen out large flows, resulting in substantial accuracy loss or heavy memory accesses, especially failing to measure medium-sized flows accurately, which are meaningful for practical applications such as usage accounting and billing. In light of this, we propose a new Hierarchical Sketch that adopts a hybrid on-chip/off-chip architecture to detect and estimate the flows whose size exceeds the threshold t (threshold-t flows for short) to cover both large and medium-sized flows. In Hierarchical Sketch, we design an on-chip bucket array together with an adaptive update scheme to record potential candidates for threshold$-t$ flows within one memory access as well as filter out unwanted flows. Besides, the flow records are downloaded to off-chip space for high memory efficiency and supporting online queries. We also implement a prototype on the NetFPGA development platform. Experimental results show that Hierarchical Sketch is up to 72.61% more accurate and 245% faster than the best baseline.