Low-overhead Top-k network flow high-precision extraction architecture and method

Abstract

The invention discloses a low-overhead Top-k network flow high-precision extraction architecture and method, and the architecture comprises a small flow filter which is used for filtering most small flows in a network, reducing the resource overhead, and reducing the Hash conflict rate; and the large flow extractor is used for extracting the Top-k flow in the network and improving the identification accuracy of the Top-k flow. According to the method, a self-adaptive updating strategy based on counter over-value proportions is provided, every time when the proportion of the number of counters exceeding a threshold value in the small flow filter is too high, each counter records whether the number of the counters exceeds the threshold value in the current period or not through a flag bit, then the counters are reset to enter the next period, and the continuous effectiveness of the small flow filter is kept. Meanwhile, a large stream extractor is designed by using a segmented Hash algorithm, a plurality of candidate positions are provided for incoming streams, and when all candidate Hash buckets are full, a replacement strategy is carried out through a voting mechanism, so that small streams can be kicked out as much as possible each time, and large streams are stored in the Hash buckets, thereby improving the accuracy of Top-k stream extraction.

Description

technical field [0001] The invention relates to the field of network measurement, in particular to a low-overhead Top-k network flow high-precision extraction architecture and method. Background technique [0002] Top-k flow extraction is mainly used to find out the top k network flows in the number of packets in the network traffic, which can provide support for congestion control, network operation, network charging and anomaly detection, and is a basic task of network measurement. The current mainstream Top-k stream extraction solution is to use the Sketch data structure to record the number of packets of all streams, and then extract the Top-k stream through the Min-heap of the small top heap. However, since the number of network flows is much larger than the number of counters per line in Sketch, many flows may be mapped to the same counter in Sketch, which is prone to the problem of small flows being misjudged as large flows. An effective improvement scheme is to use ...

AI Technical Summary

Problems solved by technology

The sketch-based filter design of the comparison file scheme has the problem of filtering failure, and the extractor based on Cuckoo hash has the problem of low accuracy

Images