CN116303585A - A kind of data flow counting method, equipment and storage medium based on Flag flag position - Google Patents

Abstract

The invention provides a Flag bit-based data stream counting method, a Flag bit-based data stream counting device and a storage medium, wherein the Flag bit-based data stream counting method comprises the following steps: setting a parameter initial value; when a data packet arrives, providing key value pair information, and acquiring the position of a calculator mapped by the data packet; when the first data packet arrives, calling a counter value mapped to an insertion function update data packet of the CUS structure to be 1; comparing the counter position of each data packet with the previous data packet from the second data packet, and judging whether the data packet and the previous data packet mapped to the same counter belong to the same data stream or not; and carrying out data stream query, and selecting the minimum value as a query result. The Flag bit is utilized to detect whether the data packets mapped to the same counter belong to the same data stream, and different counting schemes are adopted to improve the accuracy of calculating the number of the data packets in the data stream and improve the measurement accuracy of the data stream; and the Flag bit is of a Bool type, and the memory occupied in the actual environment is negligible.

Description

A kind of data flow counting method, equipment and storage medium based on Flag flag position

technical field

The present invention relates to the technical field of network management, in particular to a method, device and storage medium for counting data streams based on Flag flag bits.

Background technique

In high-speed networks, massive data traffic has brought enormous pressure to network measurement work. As an important means of next-generation network measurement, the network traffic measurement solution based on data flow has been widely used in network billing, traffic engineering, and flow database. , network security and other fields. The network traffic measurement method based on data flow only generates summary information occupying a small amount of storage space, which can meet the routine operation requirements of data processing, especially the data flow technology of Sketch is powerful and flexible, with fast update speed and low complexity. Sketch is a compact data structure and a Hash-based data structure, which can detect large flows and abnormal flows in high-speed networks, and has the characteristics of a balance between memory and estimation accuracy.

Sketch-based data flow methods mainly include Count-Min Sketch (CMS), Count Sketch (CS), Conservative Update Sketch (CUS), Augmented Sketch (AS), etc. These algorithms do not store the elements themselves, but store the count of the elements . CMS is a typical and most widely used sketch structure. It performs hash calculation on the key-value pairs of data packets through the Hash function and stores the mapping in the counter. Each counter bucket mapped to needs to be updated, while CUS only The smallest counter bucket needs to be updated. CS is similar to CMS, the difference is that each array in CS is related to two Hash functions. AS adds an additional filter on the basis of sketch to dynamically capture frequent items. Although the above-mentioned sketches play a role in the frequency counting of network traffic measurement, they have problems such as large number of memory accesses, high consumption of hash calculation resources, low accuracy, and large errors.

Due to the hash conflicts in the hash table, the query result of CMS can only be greater than or equal to the real value, which will only overestimate the frequency of elements, especially for elements with fewer occurrences, the accuracy rate will be relatively low. On the basis of CMS, CUS adopts a conservative update method to improve the accuracy of data flow counting, but it cannot perform deletion operations, because after inserting an element for a period of time, the smallest one in the smallest bucket previously mapped by the element is not necessarily the same By itself, there may be other elements sharing the counting bucket, so if a delete operation is performed, other elements may be affected.

Based on this, aiming at the overestimation problem of CMS, on the basis of CUS proposed in order to improve the accuracy rate of CMS, the present invention proposes a kind of data flow counting method based on Flag flag bit, aims at by setting a Flag flag bit Detect whether the data packets mapped to the same counter belong to the same data flow, and then adopt different counting schemes to improve the counting operation of the counter to improve the measurement accuracy.

Contents of the invention

The purpose of this section is to outline some aspects of embodiments of the invention and briefly describe some preferred embodiments. Some simplifications or omissions may be made in this section, as well as in the abstract and titles of this application, to avoid obscuring the purpose of this section, abstract and titles, and such simplifications or omissions should not be used to limit the scope of the invention.

In view of the problems existing in the above-mentioned existing method for counting data streams based on Flag flag bits, the present invention is proposed.

Therefore, the object of the present invention is to provide a method for counting data streams based on Flag flag bits.

In order to solve the above technical problems, the present invention provides the following technical solutions:

Set the initial value of the parameter;

When a data packet arrives, first propose the health value pair information in the data packet, then carry out hash calculation according to the Hash function of the CUS algorithm, and obtain the calculator position to which the data packet is mapped;

When the first data packet arrives, the insert function of the CUS structure is called, and the counter value to which the data packet is mapped is updated to 1;

Starting from the second data packet that arrives, compare the counter position of each data packet with that of the previous data packet to determine whether the data packet belongs to the same data flow as the previous data packet mapped to the same counter;

Carry out data flow query, determine all the counter positions of the mapping, compare the size of the counter values, and select the smallest value among them as the query result.

As a preferred solution of the method for counting data streams based on the Flag flag bit in the present invention, wherein: setting the initial value of the parameter includes,

Set the width and depth values of the CUS structure to fixed values, initialize all counter values in the CUS structure to 0, and initialize the Flag bit to flag=1.

As a preferred solution of the method for counting data streams based on Flag flag bits in the present invention, wherein: the CUS structure is a two-dimensional matrix array with a width of w and a depth of d, used to store counting information of elements, each The array includes w counters and d hash functions h _j (j=1, 2, . . . , d).

As a preferred solution of the method for counting data streams based on Flag flag bits in the present invention, wherein: the hash calculation is expressed as h _j (key), (j=1, 2, ..., d), through the Obtain the counter position to which the data packet is mapped after hash calculation, denoted as f( _xi , p _i );

Among them, s _i represents the stream to which the data packet belongs, and _pi represents the counter position to which the data packet is mapped.

As a preferred solution of the method for counting data streams based on Flag flag bits in the present invention, wherein: the insertion function of the CUS structure includes,

When the data packet arrives, map and count in the form of key-value pairs, first call the hash function in the CUS structure, perform d times hash calculation on the key field of the data packet, find the corresponding counter, and then only count the mapped counter Increment the smallest value in the counter, that is, update the smallest counter value to the current value plus the value field value of the data packet.

As a preferred scheme of the method for counting data streams based on Flag flag bits in the present invention, wherein: starting from the second data packet arriving, the counter position of each data packet is compared with that of the previous data packet, and judged Whether this packet belongs to the same flow as the previous packet mapped to the same counter includes,

If the counter positions of the two data packets before and after are mapped to be different, it will be counted normally according to the counting rules of CUS;

If the count positions of the two data packet mappings before and after are the same, that is, a hash collision occurs, and they belong to the same data flow, the flag is recorded as 1;

If the count positions of the two data packet mappings before and after are the same, and belong to different and identical data streams, the flag will be recorded as 0;

Finally, update the counter according to the value of the flag;

If flag=1, then increase the packet counter value by 1;

If flag=0, increase the data packet counter value by 0.5.

As a preferred solution of the method for counting data streams based on Flag flag bits in the present invention, wherein: performing the data stream query includes,

Call the CUS query function, first perform hash calculation according to the key field of the data packet to find the corresponding counter of the hash function mapping, then find out the smallest value among these counters as the estimated frequency of the data packet, and finally select the smallest value as the estimated value.

A kind of data flow counting system based on Flag sign position, it is characterized in that, described system comprises:

The data collection module initializes relevant parameters to facilitate subsequent calculations;

The data judgment module utilizes the flag flag to detect whether the data packets mapped to the same counter belong to the same data flow, and then adopts different counting schemes to improve the counting operation of the counter;

The data query module determines the final estimated value and improves the measurement accuracy of the data flow.

A computer device, comprising a memory and a processor, the memory stores a computer program, wherein when the processor executes the computer program, it realizes the steps of the method according to any one of claims 1 to 7 .

A computer-readable storage medium, on which a computer program is stored, wherein, when the computer program is executed by a processor, the steps of the method according to any one of claims 1 to 7 are realized.

Beneficial effects of the present invention: use Flag flag to detect whether the data packets mapped to the same counter belong to the same data flow, and then adopt different counting schemes to improve the counting operation of the counter, which can improve the efficiency of calculating the number of data packets in the data flow Accuracy, reducing the overestimation of CMS, and improving the measurement accuracy of the data stream; and the set Flag flag is of Bool type, which only occupies one byte of memory space, and the additional memory required by the Flag can be ignored in the actual environment.

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following will briefly introduce the accompanying drawings that need to be used in the description of the embodiments. Obviously, the accompanying drawings in the following description are only some embodiments of the present invention. For Those of ordinary skill in the art can also obtain other drawings based on these drawings without any creative effort. in:

FIG. 1 is a schematic diagram of the overall structure of the method for counting data streams based on Flag flag bits in the present invention.

FIG. 2 is a flow chart of inserting data packets in the Flag bit-based data flow counting method of the present invention.

Detailed ways

In order to make the above objects, features and advantages of the present invention more obvious and comprehensible, specific implementations of the present invention will be described in detail below in conjunction with the accompanying drawings.

In the following description, a lot of specific details are set forth in order to fully understand the present invention, but the present invention can also be implemented in other ways different from those described here, and those skilled in the art can do it without departing from the meaning of the present invention. By analogy, the present invention is therefore not limited to the specific examples disclosed below.

Second, "one embodiment" or "an embodiment" referred to herein refers to a specific feature, structure or characteristic that may be included in at least one implementation of the present invention. "In one embodiment" appearing in different places in this specification does not all refer to the same embodiment, nor is it a separate or selective embodiment that is mutually exclusive with other embodiments.

Secondly, the present invention is described in detail in conjunction with schematic diagrams. When describing the embodiments of the present invention in detail, for the convenience of explanation, the cross-sectional view showing the structure of the device will not be partially enlarged according to the general scale, and the schematic diagram is only an example, and it should not be used here. Limit the scope of protection of the present invention. In addition, the three-dimensional space dimensions of length, width and depth should be included in actual production.

Example 1

With reference to Fig. 1 and Fig. 2, a kind of data flow counting method based on Flag flag comprises:

As shown in Figure 1, this method includes two parts: element item and CUS; wherein, the element item is composed of two modules item and flag; item is for recording elements; flag is a flag bit, and flag can be used to determine whether the data packet is Belong to the same data stream; CUS is a two-dimensional array with a width of w and a depth of d, which is used to store the count information of elements; the principle is to detect whether the data packets mapped to the same counter belong to the same data according to the flag bit stream, and then categorized for counting.

Wherein, p in Fig. 1 is a data packet.

Based on the data flow counting method of the Flag flag bit, the CUS structure can count the frequency of the flow corresponding to the data packet. The structure is shown in the right half of Figure 1.

Wherein, the data flow counting method of the Flag flag is denoted as CUSF.

Wherein, the CUS structure is a two-dimensional array with a width of w and a depth of d, and each array contains w counters and d hash functions h _j (j=1, 2, . . . , d).

When a data packet arrives, it is mapped and stored in the form of a key-value pair (key, value), where the key field can be attribute information in the data packet header, such as a five-tuple (source IP address, source port, destination IP address, Destination port and transport layer protocol), the value field can be the number of times the flow occurs or the size of the flow.

When updating the count, first perform d hash calculations on the key field of the arriving data packet, find the mapped counter, and then only increase the smallest one (or those) of the mapped counters, that is, update the smallest counter value to The current value plus the value of the value field of the packet.

When querying, the key-value pairs generated by different data streams are different. Perform hash calculations based on the key fields of the data packets to find the counters mapped by these hash functions, and then find the smallest value of these counters as the frequency of the data packet Estimated value, because of hash conflicts, the query result can only be greater than or equal to the real value, so choosing the minimum value as the estimated value is the most accurate.

Call the above method, as shown in Figure 2, the execution steps are as follows:

S1: Set the initial value of the parameter. It should be noted:

Set the width value and depth value of the CUS structure to fixed values, initialize all counter values in the CUS structure to 0, and initialize the Flag bit to flag=1.

S2: When a data packet arrives, first propose the key-value pair information in the data packet, and then perform hash calculation according to the Hash function of the CUS algorithm to obtain the position of the calculator to which the data packet is mapped. It should be noted:

When a data packet arrives, the key-value pair (key, value) information is first extracted from the data packet, and then the hash calculation is performed according to the Hash function of the CUS algorithm to obtain the counter position to which the data packet is mapped, which is recorded as f(s _i , p _i ).

Wherein, the hash calculation is expressed as h _j (key), (j=1, 2, ..., d), s _i indicates the flow to which the data packet belongs, and p _i indicates the counter position to which the data packet is mapped.

S3: When the first data packet arrives, call the insert function of the CUS structure, and update the counter value to which the data packet is mapped to 1. It should be noted:

The insertion function of the CUS structure is to perform mapping and counting in the form of key-value pairs when the data packet arrives, first call the hash function in the CUS structure, perform d times of hash calculation on the key field of the data packet, and find the corresponding counter, Then only the smallest value in the mapped counter is incremented, that is, the smallest counter value is updated to the current value plus the value field value of the data packet.

S4: Starting from the second arriving data packet, compare the counter position of each data packet with that of the previous data packet, and judge whether the data packet and the previous data packet mapped to the same counter belong to the same data flow. It should be noted:

If the counter positions of the two data packets before and after are mapped to be different, it will be counted normally according to the counting rules of CUS;

If the count positions of the two data packet mappings before and after are the same, that is, a hash collision occurs, and they belong to the same data flow, the flag is recorded as 1;

If the count positions of the two data packet mappings before and after are the same, and belong to different and identical data streams, the flag will be recorded as 0;

Finally, update the counter according to the value of the flag;

If flag=1, then increase the packet counter value by 1;

If flag=0, increase the data packet counter value by 0.5.

S5: Perform data flow query, determine the positions of all counters mapped, compare the counter values, and select the smallest value among them as the query result. It should be noted:

Call the CUS query function, first perform hash calculation according to the key field of the data packet to find the corresponding counter of the hash function mapping, then find out the smallest value among these counters as the estimated frequency of the data packet, and finally select the smallest value as the estimated value.

Example 2

This embodiment is the fourth embodiment of the present invention. What this embodiment is different from the first embodiment is that it provides a verification test of a data flow counting method based on Flag flag bits, and the technical effect adopted in this method Be verified.

When Count-Min Sketch deals with the element counting problem of the data stream, due to the hash conflicts in the hash table, the CMS will only overestimate the frequency of elements, especially for elements with fewer occurrences, the accuracy rate will be relatively low, as The Conservative Update Sketch proposed to improve the accuracy of CMS uses a conservative update method to improve the accuracy of data flow counting, but it cannot perform deletion operations because after inserting an element for a period of time, the minimum bucket previously mapped by the element The smallest one is not necessarily itself, there may be other elements sharing the counting bucket, so if the delete operation is performed, other elements may be affected. On the basis of CMS and CUS, this invention proposes a data flow counting based on the Flag flag The method CUSF adds a Bool-type Flag flag, and adopts different counting schemes to improve the counting operation of the counter to improve the measurement accuracy.

Experimental comparison between CUSF and CUS: Assume that within a certain period of time, there are two data streams a and b that need to be updated to the counter, and the arrival sequence of data packets is a, b, a, b, b, a, a, b, a , a, the counter is initialized to 0, flag=1, the CUS width w=10, depth d=2, at least one of the positions mapped to the counter by the two streams a and b is the same.

There are two cases here: in the first case, the positions of the two streams a and b mapped to the counter are the same, that is, h ₁ (a)=h ₁ (b), h ₂ (a)=h ₂ (b ),.

In the second case, only one position of the two streams a and b mapped to the counter is the same, that is, h ₁ (a)=h ₁ (b), h ₂ (a)≠h ₂ (b) or h ₁ (a )≠h ₁ (b), h ₂ (a)=h ₂ (b).

Taking the first case as an example here, assuming that h1(a)=h1(b)=2, h2(a)=h2(b)=5, the counting results of CUS and CUSF are shown in Table 1 and Table 2.

Table 1: Counting results of data flows on CUS

Table 2: Counting results of data flows on CUSF

In the CUS algorithm, the estimated value of data stream a and b is queried, and the query result is 10 packets, but the actual number of data packets of flow a is only 6 packets, and that of flow b is only 4 packets. The query accuracy rates are 60% and 40%, respectively. The query results in the CUSF algorithm are 7 packets. The query accuracy rate of data stream a reaches 86%, and the accuracy rate of data stream b is 57%. Compared with the CUS algorithm Compared with that, the query accuracy of CUSF algorithm is increased by about 22%. It can be seen that the accuracy of the CUSF algorithm is higher, and it is more suitable for flow measurement in a high-speed network environment.

To sum up, the present invention proposes a kind of data flow counting method based on the Flag flag bit, by setting a Flag flag bit of Bool type (the Flag flag bit of setting is Bool type, only takes the memory space of one byte, In the actual environment, the additional memory required by Flag can be ignored), which is used to detect whether the data packet mapped to the same counter belongs to the same data flow as the previous data packet, and if the counter positions of the two data packets before and after the mapping are the same (that is, a Hash conflict), and belong to the same data stream, the flag is recorded as 1, if it belongs to different data streams, the flag is recorded as 0, and then updated in the counter according to the value of the flag, the data can be calculated more accurately The number of packets in the flow, reducing the overestimation of CMS and improving the measurement accuracy of data flow.

It should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention without limitation, although the present invention has been described in detail with reference to the preferred embodiments, those of ordinary skill in the art should understand that the technical solutions of the present invention can be carried out Modifications or equivalent replacements without departing from the spirit and scope of the technical solution of the present invention shall be covered by the claims of the present invention.

Claims (10)

1. A data flow counting method based on Flag bit is characterized in that: comprising the steps of (a) a step of,

setting a parameter initial value;

when a data packet arrives, firstly providing key value pair information in the data packet, then carrying out Hash calculation according to a Hash function of a CUS algorithm, and obtaining a calculator position mapped to the data packet;

when the first data packet arrives, calling an insertion function of the CUS structure, and updating a counter value mapped by the data packet to be 1;

comparing the counter position of each data packet with the previous data packet from the second data packet, and judging whether the data packet and the previous data packet mapped to the same counter belong to the same data stream or not;

and carrying out data flow inquiry, determining all mapped counter positions, comparing the sizes of counter values, and selecting the minimum value as an inquiry result.

2. The Flag-based data stream counting method according to claim 1, wherein: the initial values of the set parameters include,

setting the width value and the depth value of a CUS structure to fixed values, initializing all counter values in the CUS structure to 0, and initializing flag bit to flag=1.

3. The Flag-based data stream counting method according to claim 2, wherein: the CUS structure is a two-dimensional matrix array with width w and depth d and is used for storing the counting information of elements, and each array comprises w counters and d hash functions h _j (j＝1，2，...，d)。

4. The Flag-based data stream counting method according to claim 1, wherein: the hash computation is denoted as h _j (key), (j=1, 2, …, d) and obtaining the counter position mapped by the data packet after the hash calculation, and marking as f(s) _i ，p _i )；

Wherein s is _i Representing the flow to which the packet belongs, p _i Indicating the counter location to which the packet is mapped.

5. The Flag-based data stream counting method according to claim 1, wherein: the insertion function of the CUS structure includes,

when the data packet arrives, mapping and counting are carried out according to the key value pair mode, firstly, a hash function in the CUS structure is called, d times of hash calculation are carried out on the key field of the data packet, a corresponding counter is found, then only the minimum value in the mapped counter is subjected to increasing operation, namely, the minimum counter value is updated to be the current value plus the value field value of the data packet.

6. The Flag-based data stream counting method according to claim 1, wherein: from the second packet that arrives, the counter position of each packet is compared with the previous packet to determine whether the packet belongs to the same data stream as the previous packet mapped to the same counter,

if the positions of the counters mapped by the front data packet and the rear data packet are different, normally counting according to the counting rule of the CUS;

if the counting positions of the front data packet map and the rear data packet map are the same, namely hash collision occurs and the data packets belong to the same data stream, marking the flag as 1;

if the counting positions of the front and back data packet mappings are the same and belong to different identical data streams, marking the flag as 0;

finally, updating in a counter according to the value of the flag;

if flag=1, the packet counter value is incremented by 1;

if flag=0, the packet counter value is incremented by 0.5.

7. The Flag-based data stream counting method according to claim 6, wherein: making the data stream query includes,

calling a CUS query function, firstly carrying out hash calculation according to key fields of a data packet to find out corresponding hash function mapped counters, then finding out the minimum value in the counters to serve as a frequency estimated value of the data packet, and finally selecting the minimum value to serve as an estimated value.

8. A Flag bit based data stream counting system, the system comprising:

the data collection module initializes related parameters and facilitates subsequent calculation;

the data judging module is used for detecting whether the data packets mapped to the same counter belong to the same data stream or not by using the flag bit, and then adopting different counting schemes to improve the counting operation of the counter;

and the data query module determines a final estimated value and improves the measurement accuracy of the data stream.

9. A computer device comprising a memory and a processor, the memory storing a computer program, characterized in that the processor, when executing the computer program, is the step of implementing the method of any one of claims 1 to 7.

10. A computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when being executed by a processor, implements the steps of the method of any of claims 1 to 7.

Images