CN114884834A - Low-overhead Top-k network flow high-precision extraction framework and method - Google Patents

Abstract

The invention discloses a low-overhead Top-k network flow high-precision extraction architecture and method, including: a small flow filter for filtering most small flows in the network, reducing resource overhead and reducing hash collision rate ; Large stream extractor, which is used to extract Top-k streams in the network and improve the accuracy of Top-k stream recognition. The method of the present invention proposes an adaptive update strategy based on the proportion of counters exceeding the value. Whenever the proportion of the number of counters exceeding the threshold in the small flow filter is too high, each counter records whether it exceeds the threshold in the current cycle through the flag bit. , and then reset into the next cycle to maintain the continued effectiveness of the small flow filter. At the same time, a segmented hash algorithm is used to design a large stream extractor to provide multiple candidate positions for the incoming stream. When all candidate hash buckets are full, the voting mechanism will be used to replace the strategy, which can make every possible kick as much as possible. In addition to small streams, large streams are kept in hash buckets, thus improving the accuracy of Top-k stream extraction.

Description

A Low-Overhead High-precision Extraction Architecture and Method for Top-k Network Streams

technical field

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

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 Sketch to filter small streams, and then use hash structure records to filter Top-k streams to improve the accuracy of Top-k stream extraction. However, as the network packet flow continues to arrive, all the counters in Sketch will continue to increase until they overflow, which will eventually lead to the complete failure of the small flow filter, which will seriously affect the accuracy of subsequent large flow extraction. At the same time, hash collisions may occur when multiple streams are mapped to the large stream extractor, which is prone to the situation that the large stream is kicked out, thereby reducing the accuracy of Top-k stream extraction. In this regard, based on the idea of filtering small flows first and then extracting large flows, this patent proposes a high-precision extraction method for Top-k network flows with low overhead, which solves the problem of ineffectiveness of small flow filters and reduces large flows at the same time. The hash collision rate of the extractor improves the accuracy of Top-k stream extraction.

Comparative document: CN111262756A discloses an accurate measurement method and architecture of high-speed network elephant flow. The sketch-based filter can filter the mouse flow in the data packet, so as to reduce the subsequent calculation and space overhead, and improve the subsequent elephant flow. Measurement accuracy; the extractor based on Cuckoo hash can reduce the probability of elephant flow being kicked out, which not only saves extraction resources but also improves the accuracy of elephant flow measurement. The design of the filter based on sketch of the comparison file scheme has the problem of filtering failure, and the extractor based on Cuckoo hash has the problem of low accuracy. In this regard, this patent designs a compact small flow filter that supports adaptive update, which ensures the continuous effectiveness of the small flow filter in the face of large traffic, and reduces the resource overhead of subsequent processing of small flows. The filter screen removes most of the small flows, so that the flows entering the large flow extractor are basically large flows, thereby improving the extraction accuracy of the Top-k flow.

SUMMARY OF THE INVENTION

This patent is based on the idea of filtering small flows to extract large flows, and then designs an accurate extraction scheme for Top-k flows that is filtered first and then extracted. In this scheme, the small flow filter adopts a compact sketch data structure. When the number of counters with large values in the filter reaches the preset ratio, the flag bit configured for each counter records whether it exceeds the threshold, which will be used as the next cycle. The internal basis for determining whether the incoming stream is released, and then always accurately filter small streams, thereby improving the extraction accuracy of Top-k streams. On this basis, a segmented hash algorithm is used to design a large stream extractor to provide multiple candidate positions for each stream, and when the candidate positions are all full, the smallest stream is selected based on the voting idea, and then it is judged whether to replace it or not. For incoming streams to retain large streams, so as to achieve accurate extraction of Top-k streams.

In order to solve the above-mentioned technical problems, the present invention adopts the following technical solutions:

The present invention provides a low-overhead Top-k network stream high-precision extraction architecture and method, including:

Small flow filter, proposes an adaptive update strategy based on the proportion of counter excess value, each element of which contains a counter and a flag bit, the counter is used to record the number of packets mapped to this position in the current cycle, because the counter It only needs to record the number of packets in one cycle, and the cycle is usually set to be short, so it can be set to a few bits, and the flag bit occupies one bit, which is used to record the state before the corresponding counter is reset, that is, at the end of the previous cycle, that is Whether the threshold is exceeded is used as the basis for judging whether the incoming stream is released in the current cycle. Only when all the flags in the incoming stream mapped to the sketch are 1, or all the counters reach the threshold, the stream is likely to be large. The stream will be released, otherwise it will be discarded, so as to realize the function of filtering small streams. In short, each element only occupies a few bits, which makes the sketch data structure occupy a small space and high space utilization;

The large flow extractor, based on the segmented hash algorithm, designs a large flow extraction structure, each hash bucket contains multiple slots for recording the flow, and each slot contains the flow signature, positive vote counter and negative vote counter, The flow signature is used to identify the flow, the positive ticket counter is used to record the number of packets in the flow, and the negative ticket counter is used to record the number of packets that are mapped to the corresponding hash bucket but do not belong to any one of the flows. The recognizer uses the segmented hash method to provide multiple candidate positions, and selects one of the vacancies for storage. When all the candidate positions are full, it uses the voting idea to select the smallest stream among them, and then judges whether to replace it with the incoming stream. So as to achieve the effect of accurately identifying the Top-k flow;

The small flow filter, a filter used for small flow filtering, filters small flows by setting a threshold, wherein the counter represents the number of packets mapped to this position in the current cycle, and the flag bit indicates that the corresponding counter is reset immediately before it is reset. the state at the end of a cycle;

The large flow extractor, the large flow extractor based on segment hash, uses the segment hash algorithm to extract the large flow, wherein the extracted content field is the signature value sig used to identify the flow, and the counter count is used to record the packets of the flow. The number and counter counter count _n are used to record the number of packets that map to the corresponding hash bucket but do not belong to any one of the flows.

The method of the present invention also provides a method based on the above-mentioned architecture, comprising:

The small stream filter first extracts its stream identifier fid during the insertion process, then maps an element in each array of sketch through d different hash functions, and then reads the corresponding flag bit and counter, Add 1 to the minimum counter value of , if all flag bits are not all 1, and the minimum counter does not reach the threshold, it indicates that the corresponding small flow is a small flow, and the data packet is directly discarded, otherwise it is released, if the counter in the current sketch reaches the threshold If the number exceeds a certain percentage, the corresponding flag bit value is updated according to the counter value. If the counter value reaches the threshold, the flag bit is updated to 1, otherwise it is 0. Finally clear all counter values;

The large flow extractor maps its flow identifier fid to multiple candidate positions through a segmented hash function, and then searches in parallel in the corresponding hash buckets. If a flow is successfully found, the positive votes of the flow are added. 1. If the search fails and there is a vacancy in the candidate position, a vacancy is randomly selected and stored in the stream, and the number of positive votes is set to 1, otherwise the number of negative votes of all candidate positions is increased by 1, and selected from all candidate positions. The stream with the smallest ratio of positive votes to negative votes, if the ratio is greater than the preset threshold, the data packet will be discarded directly, otherwise the incoming stream will be replaced with the smallest stream, and its positive votes will be increased by 1, and the negative votes will be reset to 0;

Further, the efficient method includes the following operations:

1. Stream extraction process;

When a packet is received, it first parses its protocol header, extracts the quintuple field, calculates the flow identifier fid, and then enters the small flow determination process to determine whether the flow is a small flow. If it is a small flow, the packet is directly discarded. Otherwise, enter the Top-k flow extraction process, and record the flow fingerprints and number of groups of all Top-k flows for query;

2. Flow filtration method;

Filter each incoming flow through the small flow filter. If the threshold is reached, it will be released to the large flow extractor. If the threshold is not reached, it will be discarded directly. Each flow only extracts the number of packets;

3. Flow identification method;

The incoming stream is extracted by the large stream extractor, and it is judged according to the stream identifier of the extracted stream whether the incoming stream has been extracted by the large stream extractor, and each stream extracts the stream identifier, the number of packets, and the number of hash collisions. .

4. Stream replacement method;

When the mapping position of the incoming flow is full and the replacement conditions are met, the incoming flow will replace the extracted hash conflict flow, in which each flow extracts the flow ID, the number of packets, and the number of hash collisions.

5. Stream output method;

The large stream extractor traverses all the slots in the hash bucket in parallel, extracts the streams whose number is greater than the threshold, and then outputs the stream id and the number of streams in order from large to small.

The beneficial effects of the present invention are:

1. In view of the fact that the traditional small flow filter is prone to failure when network data packets continue to arrive, this patent proposes an adaptive update strategy based on the proportion of counter excess value for the small flow filter to ensure its continuous effectiveness. When the proportion of the number of counters exceeding the threshold in the small flow filter reaches the preset proportion, each counter uses a flag bit to record its status, that is, whether it exceeds the threshold, and then resets to zero, and starts counting again in the next cycle. In the new cycle, after a data packet is mapped to a counter, its flag bit is used as the basis for judging whether to release the data packet, so as to continuously and effectively filter the small flow;

2. Aiming at the traditional large stream extractor usually only provides a hash candidate position for the incoming stream, which is prone to the problem of hash collision, this patent adopts the segmented hash method, in the large stream extractor, for each incoming stream Streams provide multiple candidate locations to reduce the hash collision rate, thus accommodating all large streams as much as possible. If all the candidate positions are full, this patent uses the voting idea to select the minimum flow from all the candidate positions, and then determines whether the incoming flow replaces the minimum flow, so that the large flow is retained, and the small flow is discarded as much as possible, thereby improving the top flow. -k The precision of stream extraction.

Description of drawings

In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

FIG. 1 is an architecture diagram of a low-overhead Top-k network stream high-precision extraction of the method of the present invention.

Figure 2 is a structural diagram of a small flow filter in the method of the present invention.

FIG. 3 is a structural diagram of a large flow extractor in the method of the present invention.

FIG. 4 is a structural diagram of the flow extraction process in the method of the present invention.

Figure 5 is a flow chart of the flow filtration method in the method of the present invention.

FIG. 6 is a flow chart of the flow identification method in the method of the present invention.

FIG. 7 is a flow chart of the stream replacement method in the method of the present invention.

FIG. 8 is a flow chart of the stream output method in the method of the present invention.

Detailed ways

In order to better illustrate the content of the present invention, the present invention is further verified by specific embodiments below. It is hereby stated that the embodiments are only to describe the present invention more directly, they are only a part of the present invention, and cannot constitute any limitation to the present invention.

As shown in FIG. 1 , an embodiment of the present invention provides a low-overhead Top-k network stream high-precision extraction architecture and method, including:

The small stream filter first extracts its stream identifier fid during the insertion process, then maps an element in each array of sketch through d different hash functions, and then reads the corresponding flag bit and counter, Add 1 to the minimum counter value of , if all flag bits are not all 1, and the minimum counter does not reach the threshold, it indicates that the corresponding small flow is a small flow, and the data packet is directly discarded, otherwise it is released, if the counter in the current sketch reaches the threshold If the number exceeds a certain percentage, the corresponding flag bit value is updated according to the counter value. If the counter value reaches the threshold, the flag bit is updated to 1, otherwise it is 0. Finally, all counter values are cleared, as shown in Figure 2.

The large flow extractor maps its flow identifier fid to multiple candidate positions through a segmented hash function, and then searches in parallel in the corresponding hash buckets. If a flow is successfully found, the positive votes of the flow are added. 1. If the search fails and there is a vacancy in the candidate position, a vacancy is randomly selected and stored in the stream, and the number of positive votes is set to 1, otherwise the number of negative votes of all candidate positions is increased by 1, and selected from all candidate positions. The stream with the smallest ratio of positive votes to negative votes, if the ratio is greater than the preset threshold, the data packet will be discarded directly, otherwise the incoming stream will be replaced with the smallest stream, and its positive votes will be increased by 1, and the negative votes will be reset to 0, as shown in the figure 3 shown.

When the switch receives a data packet p, it first parses the important fields in its header, such as: source/destination IP address, source/destination MAC address, source/destination port number, IP protocol type, etc., and then extracts the flow keyword fid; After that, the data packet enters the first layer, that is, the small flow filter filters the small flow; finally, the data packet passing through the filter enters the second layer, that is, the large flow extractor completes the traffic information statistics;

This embodiment also provides a method based on the above architecture, comprising the following steps:

1. Stream extraction process;

As shown in Figure 4, when a packet is received, it first parses its protocol header, extracts the quintuple field, calculates the flow identifier fid, and then enters the small flow determination process to determine whether the flow is a small flow, if it is a small flow , the packet is discarded directly, otherwise it enters the Top-k flow extraction process, and records the flow fingerprints and the number of packets of all Top-k flows for query use;

2. Flow filtration method;

As shown in Figure 5, the number of counters in the filter (k) reaches the threshold as a mark, when a certain data packet p is received, the data packet is first processed by the filter;

Judge whether flag _i is all 1. If the conditions are met, the flow enters the flow identification process while the counter _min is incremented by 1; otherwise, it is further judged whether the counter _min reaches the threshold. If it is not reached, the counter _min will be incremented by 1;

Determine whether the counter _min at this time reaches the threshold, if not, the operation ends; if it does, add 1 to the number k of full counters;

Determine whether the value of k reaches the threshold, if not, the operation ends; if it does, update the corresponding flag bit value according to the counter value, for example, if the counter value does not reach the threshold value, the flag bit is updated to 0; otherwise, it is 1, and then all The counter value counter _i is reset to 0, and the operation ends.

2. Flow identification method;

As shown in Figure 6, first, the important fields in the header of the data packet are parsed to extract the flow keyword fid; then, the flow keyword fid is used to generate the connection signature value sig by the hash function, and then the hash function Hash is used to calculate the hash value of m bits. The value, n bits are randomly selected for each segment, and each segment corresponds to a position on the w hash tables;

Search for w candidate hash buckets in parallel, when the flow (B _j [index _j ].sig==sig) exists in the hash bucket, add 1 to the counter count of the flow, and the flow identification process ends;

When the hash bucket does not exist in the stream and its corresponding position is empty (B _j [index _j ][i].sig==0), the signature value, counter value, and inverse counter value (sig, 1, 0) will be concatenated Write the empty slot, the stream identification process ends;

When there is a stream in the hash bucket and it is not the stream, create a new cache item item to be replaced, and enter the stream replacement process.

3. Stream replacement method;

As shown in Figure 7, first, input the stream keyword fid and the connection signature value sig of the cache item item to be replaced;

Calculate the w candidate hash bucket positions B _j [index _j ] of the item to be cached, then take out the counter values in all candidate buckets, and compare and find the slot position with the largest ratio of the inverse counter value to the counter value (B _j [ index _j ]), and take out its counter value C _min , and calculate the ratio μ of the inverse counter value to the counter value;

It is judged whether the ratio μ reaches the predetermined threshold. If it does, after clearing the flow information of the slot, write the flow information in the item item to be cached into the hash bucket (sig, C _min +1, 0), and the operation ends.

If it is not reached, delete the item to be cached replacement item, and the operation ends.

4. Stream output method;

As shown in Figure 8, first, we input a threshold for defining a large flow (for example, if a flow greater than 500 is defined as a large flow, then enter 500), and the large flow extractor traverses all the slots in the hash bucket in parallel, and the The streams whose number of streams is greater than the threshold are extracted, and then the stream id and the number of streams are output in order from large to small, and the operation ends.

This patent adopts the idea of filtering small flows and then extracting large flows, and proposes a high-precision extraction method for Top-k network flows with low overhead. The invention has the following advantages: (1) This patent is based on ensuring continuous filtering of small flows. All large streams are stored, thereby reducing the resource overhead occupied by a large number of insertions and replacements of small streams, and achieving accurate extraction of Top-k streams with low overhead. (2) The small flow filter records the state before the corresponding counter is reset, that is, at the end of the previous cycle, through the flag bit, so as to ensure the continuous effectiveness of filtering small flows, and at the same time, the filter occupies a small space and has a high space utilization rate. (3) The large stream extractor reduces the hash collision rate by providing multiple candidate positions for each stream, so as to accommodate all large streams as much as possible, thereby improving the extraction accuracy of Top-k streams.

The specific embodiments described herein are merely illustrative of the spirit of the invention. Those skilled in the technical field of the present invention can make various modifications or additions to the described specific embodiments or substitute in similar ways, but will not deviate from the spirit of the present invention or go beyond the definition of the appended claims range.

Claims (6)

1. a low-cost Top-k network flow high-precision extraction architecture and method, is characterized in that, comprising: Small flow filter, proposes an adaptive update strategy based on the proportion of counter excess value, each element of which contains a counter and a flag bit, the counter is used to record the number of packets mapped to this position in the current cycle, because the counter It only needs to record the number of packets in one cycle, and the cycle is usually set to be short, so it can be set to a few bits, and the flag bit occupies one bit, which is used to record the state before the corresponding counter is reset, that is, at the end of the previous cycle, that is Whether the threshold is exceeded is used as the basis for judging whether the incoming stream is released in the current cycle. Only when all the flags in the incoming stream mapped to the sketch are 1, or all the counters reach the threshold, the stream is likely to be large. The stream will be released, otherwise it will be discarded, so as to realize the function of filtering small streams. In short, each element only occupies a few bits, which makes the sketch data structure occupy a small space and high space utilization; The large flow extractor, based on the segmented hash algorithm, designs a large flow extraction structure, each hash bucket contains multiple slots for recording the flow, and each slot contains the flow signature, positive vote counter and negative vote counter, The flow signature is used to identify the flow, the positive ticket counter is used to record the number of packets in the flow, and the negative ticket counter is used to record the number of packets that are mapped to the corresponding hash bucket but do not belong to any one of the flows. For each incoming flow, the large flow The recognizer uses the segmented hash method to provide multiple candidate positions, and selects one of the vacancies for storage. When all the candidate positions are full, it adopts the voting idea to select the smallest stream among them, and then judges whether to replace it with the incoming stream. So as to achieve the effect of accurately identifying the Top-k flow; The small flow filter, a filter used for small flow filtering, filters small flows by setting a threshold, wherein the counter represents the number of packets mapped to this position in the current cycle, and the flag bit indicates that the corresponding counter is reset immediately before it is reset. the state at the end of a cycle; The large flow extractor, the large flow extractor based on segmented hash, utilizes multi-hash algorithm to extract large flow, wherein the extracted content field is the signature value sig used to identify the flow, and the counter count is used to record the number of packets of the flow, The inverse counter count _n is used to record the number of packets that are mapped to the corresponding hash bucket but do not belong to any one of the flows. 2. a method based on the described framework of claim 1, is characterized in that, comprises the following steps: The small stream filter first extracts its stream identifier fid during the insertion process, then maps an element in each array of sketch through d different hash functions, and then reads the corresponding flag bit and counter, Add 1 to the minimum counter value of , if all flag bits are not all 1, and the minimum counter does not reach the threshold, it indicates that the corresponding small flow is a small flow, and the data packet is directly discarded, otherwise it is released, if the counter in the current sketch reaches the threshold If the number exceeds a certain percentage, the corresponding flag bit value is updated according to the counter value. If the counter value reaches the threshold, the flag bit is updated to 1, otherwise it is 0. Finally clear all counter values; The large flow extractor maps its flow identifier fid to multiple candidate positions through a segmented hash function, and then searches in parallel in the corresponding hash buckets. If a flow is successfully found, the positive votes of the flow are added. 1. If the search fails and there is a vacancy in the candidate position, a vacancy is randomly selected and stored in the stream, and the number of positive votes is set to 1, otherwise the number of negative votes of all candidate positions is increased by 1, and selected from all candidate positions. For the stream with the smallest ratio of positive votes to negative votes, if the ratio is greater than the preset threshold, the data packet will be discarded directly. Otherwise, the incoming stream will be replaced with the smallest stream, and its positive vote count will be increased by 1, and the negative vote count will be reset to 0. 3. The method of claim 2, wherein the efficient method comprises the following operations: a. Stream extraction process; When a packet is received, it first parses its protocol header, extracts the quintuple field, calculates the flow identifier fid, and then enters the small flow determination process to determine whether the flow is a small flow. If it is a small flow, the packet is directly discarded. Otherwise, enter the Top-k flow extraction process, and record the flow fingerprints and number of groups of all Top-k flows for query; b. Flow filtration method; Filter each incoming flow through the small flow filter. If the threshold is reached, it will be released to the large flow extractor. If the threshold is not reached, it will be discarded directly. Each flow only extracts the number of packets; c. Flow identification method; The incoming stream is extracted by the large stream extractor, and it is judged according to the stream identifier of the extracted stream whether the incoming stream has been extracted by the large stream extractor, and each stream extracts the stream identifier, the number of packets, and the number of hash collisions. ; d. Stream replacement method; When the mapping position of the incoming flow is full and the replacement conditions are met, the incoming flow will replace the extracted hash conflict flow, in which each flow extracts the flow ID, the number of packets, and the number of hash collisions; e. Stream output method; The large stream extractor traverses all the slots in the hash bucket in parallel, extracts the streams whose number is greater than the threshold, and then outputs the stream id and the number of streams in order from large to small. 4. method according to claim 3, is characterized in that, this patent proposes a kind of self-adaptive update strategy based on counter excess value ratio for small flow filter, to ensure its continuous validity, when small flow filter in When the proportion of the number of counters exceeding the threshold reaches the preset proportion, each counter uses a flag bit to record its status, that is, whether it exceeds the threshold, and then resets to zero, and starts counting again in the next cycle. In the new cycle, after a certain data packet is mapped to a counter, its flag bit is used as the basis for judging whether to release the data packet, so as to continuously and effectively filter the small flow. 5. The method according to claim 3, characterized in that, this patent proposes a method for extracting a large stream based on a segmented hash algorithm. Each stream can be mapped to several candidate hash buckets, each bucket contains multiple slots, and can be stored in the empty slot of any one of the hash buckets, which greatly reduces the hash collision rate. 6. method according to claim 3, is characterized in that, this patent makes smaller flow be kicked out as far as possible, if candidate position is not full, then randomly selects a candidate slot to insert, otherwise must be in new flow and all. Select one of the candidate streams to be discarded. When all candidate hash buckets are full, the voting mechanism will be used to replace the strategy, so that the small stream can be kicked out each time as much as possible, and the large stream can be saved in the hash bucket. Therefore, the accuracy of Top-k stream extraction is improved.

Images