CN114785741B - Data stream classification device - Google Patents

Abstract

A data stream classification device includes a forwarding circuit and a setting circuit. The forwarding circuit queries a lookup table based on the identification information of an input data stream to obtain the classification of the input data stream, and then marks its packets accordingly, and then outputs these packets to a buffer circuit; if the identification information of the input data stream is not included in the lookup table, the forwarding circuit marks the packets of the input data stream according to a default classification and then outputs them, and adds the identification information of the input data stream to the lookup table. The setting circuit determines a large flow flow threshold based on the queue length of the buffer circuit and a target length. The setting circuit also obtains the flow of multiple data streams based on the flow information of the forwarding circuit recorded in the lookup table, and then determines the classification of these data streams based on the comparison between the flow of these data streams and the large flow flow threshold, and stores the classification of these data streams in the lookup table. These data streams include the input data stream.

Description

Data flow classification device

Technical Field

The present invention relates to a classification device, and in particular to a data stream classification device.

Background technique

Buffer bloat refers to the phenomenon that the forwarding device buffers packets excessively, resulting in high forwarding delay and delay variation in the network. To solve this problem, the most common solutions are the following three:

(1) Class of Service (CoS) queue scheduling: Packets are classified and associated with different queues. Different queues are given different service levels using a scheduling mechanism.

(2) Active Queue Management (AQM): does not classify packets, but actively discards packets based on a probability before the packet queue is full to reduce the average queue length of the queue.

(3) Weighted AQM: Classifies packets and assigns different packet discard rates to packets of different classifications, so as to discard low-priority packets first and reserve buffer space for high-priority packets.

However, how to classify packets has always been a big problem. The most common way is to let users set it by themselves, but this method not only causes inconvenience to users, but also makes it difficult to accurately classify packets. Although the AQM method of not classifying packets can reduce the average delay, since the packets are not classified, this method will discard high-priority packets and low-priority packets at the same probability, which will equally affect the traffic of high-priority packets (for example: Internet Voice Protocol (VoIP) packets, real-time video streaming packets, game packets) and affect the user experience.

Summary of the invention

One of the purposes of the present application is to provide a data stream classification device that can avoid the problems of the prior art.

An embodiment of the data stream classification device of the present application includes a forwarding circuit and a setting circuit. Each of the forwarding circuit and the setting circuit can be implemented by hardware, or by hardware executing software and/or firmware.

The forwarding circuit includes a recording circuit, a classification circuit and a data flow information supplementation circuit. The recording circuit is used to calculate the flow of each of the multiple data flows to obtain the flow information of the multiple data flows, and includes a lookup table. The lookup table includes identification information of the multiple data flows, flow information of the multiple data flows and classification of the multiple data flows. The classification circuit is coupled to a data flow input terminal and the recording circuit, and is used to receive a first data flow from the data flow input terminal to query the identification information of the multiple data flows included in the lookup table according to the first identification information of the first data flow. When the lookup table includes the first identification information, the classification circuit uses the lookup table to determine the classification of the first data flow and outputs the first data flow to a buffer circuit; when the lookup table does not include the first identification information, the classification circuit classifies the first data flow into a default classification and outputs the first data flow to the buffer circuit. The data flow information supplement circuit is coupled to the recording circuit and the classification circuit; when the lookup table does not include the first identification information, the data flow information supplement circuit obtains at least a part of the first data flow to obtain the first identification information, and then the data flow information supplement circuit adds the first identification information to the lookup table as part of the identification information of the multiple data flows, wherein the recording circuit calculates the flow of the first data flow to obtain first flow information as part of the flow information of the multiple data flows.

The setting circuit includes a large elephant flow flow threshold adjustment circuit and a classification decision circuit. The large elephant flow flow threshold adjustment circuit is coupled to the buffer circuit, and is used to determine a large elephant flow flow threshold according to the change of the relationship between a target queue characteristic value (for example, queue length or queue delay) and a current queue characteristic value (for example, queue length or queue delay) of the buffer circuit. The classification decision circuit is coupled to the large elephant flow flow threshold adjustment circuit and the recording circuit, and is used to determine the classification of the multiple data flows included in the lookup table according to the change of the relationship between the flow information of the multiple data flows and the large elephant flow flow threshold.

As described above, this embodiment controls the elephant flow flow threshold to classify more/fewer data flows as elephant flows, so that the buffer circuit can avoid buffer expansion by reducing the transmission priority of the elephant flow or discarding the packets of the elephant flow.

The features, implementation and effects of the present invention are described in detail below with reference to the accompanying drawings for preferred embodiments.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 shows an embodiment of a data stream classification device of the present application;

FIG. 2 shows an embodiment of the forwarding circuit of FIG. 1 ;

FIG3 shows an embodiment of the setting circuit of FIG1 ;

FIG. 4 shows an embodiment of how the elephant flow threshold adjustment circuit of FIG. 3 determines the state of the buffer circuit;

FIG5 shows another embodiment of how the elephant flow threshold adjustment circuit of FIG3 determines the state of the buffer circuit;

FIG6 shows an embodiment of how the elephant flow threshold adjustment circuit of FIG3 adjusts the elephant flow threshold;

FIG. 7 shows an example of an implementation of how the classification decision circuit of FIG. 3 determines the classification of the first data stream;

FIG. 8 shows another implementation example of how the classification decision circuit of FIG. 3 determines the classification of the first data stream;

FIG. 9 shows another implementation example of how the classification decision circuit of FIG. 3 determines the classification of the first data stream;

FIG10 shows another embodiment of the data stream classification device of the present application;

FIG. 11 shows an embodiment of the forwarding circuit of FIG. 10 ; and

FIG. 12 shows an embodiment of the setting circuit of FIG. 10 .

Detailed ways

The present application includes a data flow classification device that can classify multiple data flows based on the comparison between the flow rate of multiple data flows and an elephant flow flow threshold. When the queue characteristics (e.g., queue length or queue delay) of a back-end buffer circuit are longer (or shorter) than a target threshold, the data flow classification device of the present application can correspondingly reduce (increase) the elephant flow flow threshold to classify more (fewer) data flows as elephant flows, so that the back-end buffer circuit can avoid buffer expansion by reducing the transmission priority of the elephant flow or discarding the packets of the elephant flow. The data flow classification device can be applied to a network packet forwarding device (e.g., a switch), in which case the data flow is a data flow composed of continuous packets and/or discontinuous packets; for ease of understanding, the following description takes the network packet forwarding application as an example, but this is not an implementation limitation of the present invention.

FIG1 shows an embodiment of a data stream classification device of the present application. The data stream classification device 100 of FIG1 includes a forwarding circuit 110 and a setting circuit 120. The forwarding circuit 110 is used to receive and classify a data stream, and then forward the classified data stream to a buffer circuit 10; the forwarding circuit 110 also provides the flow information of the data stream to the setting circuit 120. The setting circuit 120 is used to determine the classification of the data stream based on the queue information of the buffer circuit 10 and the flow information, and provide the classification of the data stream to the forwarding circuit 110. The forwarding circuit 110 or the setting circuit 120 can be implemented by hardware, or by hardware executing software and/or firmware.

Fig. 2 shows an embodiment of the forwarding circuit 110 of Fig. 1. The forwarding circuit 110 of Fig. 2 includes a recording circuit 210, a classification circuit 220 and a data stream information supplementation circuit 230, wherein the recording circuit 210 and the classification circuit 220 can be integrated into a lookup table circuit (not shown in the figure), but this is not an implementation limitation of the present invention.

Please refer to FIG. 1 and FIG. 2. The recording circuit 210 is used to calculate the flow rate of each of the multiple data flows to obtain the flow rate information of the multiple data flows. For example, the recording circuit 210 obtains the identity of the data flow according to the identification information of the data flow, and then counts the number of packets and/or the number of bytes of the data flow to obtain the flow rate information of the data flow. The recording circuit 210 further includes (or stores) a lookup table 212, and the lookup table 212 includes the identification information of the multiple data flows, the flow rate information of the multiple data flows, and the classification of the multiple data flows. In an implementation example, the identification information of each of the multiple data flows is a set of values, and the set of values is, for example, a five-tuple, including a destination IP address, a source IP address, a protocol, a destination port, and a source port, but this is not an implementation limitation of the present invention; in the case where the implementation is feasible, any information that can be used to identify the identity of the data flow can be used as the identification information. Since the aforementioned counting of the number of packets/number of bytes and the implementation of the lookup table can be achieved using known or self-developed technologies, the details are omitted here.

Please refer to FIG. 1 and FIG. 2. The classification circuit 220 is coupled to a data stream input terminal (i.e., the starting end of the "data stream" arrow shown in the figure) and the recording circuit 210, and is used to receive a first data stream from the data stream input terminal, so as to query the identification information of the multiple data streams recorded in the lookup table 212 according to the first identification information of the first data stream, wherein the term "first" is for the convenience of explanation and has no specific meaning; in other words, the first data stream can be any data stream received by the data stream input terminal. When the lookup table 212 includes the first identification information, the lookup table 212 also includes the classification of the first data stream associated with the first identification information. Therefore, the classification circuit 220 uses the lookup table 212 to determine the classification of the first data stream and outputs the first data stream to the buffer circuit 10. When the lookup table 212 does not include the first identification information, the classification circuit 220 classifies the first data stream as a default classification and outputs the first data stream to the buffer circuit 10. It is worth noting that when the lookup table 212 does not include the first identification information, the classification circuit 220 can send a signal or other known/self-developed means (e.g., control of a switch) to enable the data stream information supplementation circuit 230 to obtain at least a portion of the first data stream from the output of the classification circuit 220 (such as the "classified data stream" shown in the figure) or the data stream input terminal (not shown in the figure), so that the data stream information supplementation circuit 230 can selectively update the lookup table 212 according to the at least a portion of the first data stream. It is also worth noting that the buffer circuit 10 shown in FIG. 1 can be included in the data stream classification device 100, or can be independent of the data stream classification device 100.

In an implementation example, the classification of the multiple data flows included in the lookup table 212 includes an elephant flow type and a non-elephant flow (e.g., mouse flow) type; the flow rate of any data flow of the elephant flow type is higher than the flow rate of any data flow of the non-elephant flow type; in the operation of the buffer circuit 10, an elephant flow transmission priority associated with the elephant flow type is lower than a non-elephant flow transmission priority associated with the non-elephant flow type, or an elephant flow packet discard rate associated with the elephant flow type is higher than a non-elephant flow packet discard rate associated with the non-elephant flow type; the aforementioned preset classification is the non-elephant flow type. In an implementation example, the elephant flow type includes a first type and a second type; the flow rate of any data flow of the first type is higher than the flow rate of any data flow of the second type; in the operation of the buffer circuit 10, a first transmission priority associated with the first type is lower than a second transmission priority associated with the second type, or a first packet discard rate associated with the first type is higher than a second packet discard rate associated with the second type. Depending on the implementation requirements, the elephant flow type may include more types.

In an implementation example, each packet of the first data stream includes the first identification information, and the classification circuit 220 is used to query the identification information of the multiple data streams included in the lookup table 212 according to the first identification information included in each packet of the first data stream. When the lookup table 212 includes the first identification information, the lookup table 212 also includes the classification of the first data stream. Therefore, the classification circuit 220 can mark each packet of the first data stream according to the classification of the first data stream included in the lookup table 212, and then the buffer circuit 10 can know whether the packet is an elephant stream packet or a non-elephant stream packet according to the marking of each packet. In an implementation example, the classification circuit 220 marks the classification of the packet by determining the value of a metadata (e.g., color description metadata) of each packet of the first data stream. Since marking packets can be implemented by known/self-developed technologies, the details are omitted here.

Please refer to FIG. 1 and FIG. 2. The data flow information supplementing circuit 230 is coupled to the recording circuit 210 and the classification circuit 220. When the lookup table 212 does not include the first identification information, the data flow information supplementing circuit 230 selectively obtains at least a portion of the first data flow from the output of the classification circuit 220 or the data flow input terminal to obtain the first identification information, and then the data flow information supplementing circuit 230 adds the first identification information to the lookup table 212 as a part of the identification information of the multiple data flows, and the recording circuit 210 calculates the flow of the first data flow to obtain the first flow information as a part of the flow information of the multiple data flows. If the lookup table 212 is full before adding the first identification information and the first flow information, the data flow information supplementing circuit 230 removes the information of a certain data flow (for example, a data flow determined by the least recently used (LRU) strategy) in the lookup table 212, but this is not an implementation limitation of the present invention. In an implementation example, considering that the size of the lookup table 212 is limited, the data stream information supplementation circuit 230 performs a sampling operation according to a default probability (P%, where P is a number between 0 and 100). Therefore, the probability that the data stream information supplementation circuit 230 obtains the at least a portion of the first data stream is the default probability (that is, the data stream information supplementation circuit 230 may not sample each data stream and record the identification information and flow rate). Since the sampling operation and the operation of obtaining specific information of the packet can be implemented by known/self-developed technologies, the details are omitted here.

FIG3 shows an embodiment of the setting circuit 120 of FIG1 . The setting circuit 120 of FIG3 includes a large elephant flow rate threshold adjustment circuit 310 and a classification decision circuit 320 .

Please refer to FIG. 1 to FIG. 3. The elephant flow flow threshold adjustment circuit 310 is coupled to the buffer circuit 10, and is used to determine an elephant flow flow threshold (ELE_TH) according to the change of the relationship between a target queue characteristic value (e.g., fixed queue length or fixed queue delay) and a current queue characteristic value (e.g., variable queue length or variable queue delay) of the buffer circuit 10; in other words, the elephant flow flow threshold changes dynamically with the current queue characteristic value. In an implementation example, after the current queue characteristic value (Curr_QL) is greater than the target queue characteristic value (Target_QL) for N times, the elephant flow flow threshold adjustment circuit 310 determines that the state of the buffer circuit 10 changes from a non-congested state to a congested state (as shown in FIG. 4 and FIG. 5), and lowers the elephant flow flow threshold at least once, so as to find more data flows that may be elephant flows, so that the buffer circuit 10 can relieve congestion by discarding at least a portion of the elephant flows, wherein N is a positive integer (e.g., an integer greater than one).

In an implementation example, packets of different categories are associated with the same queue, and the buffer circuit 10 can adopt a known/self-developed weighted active queue management (Weighted AQM) technology to discard packets in the queue with a certain probability; when the buffer circuit 10 is in the congested state, after the current queue characteristic value is less than one-Kth of the target queue characteristic value for M times, the elephant flow flow threshold adjustment circuit 310 determines that the buffer circuit 10 returns to the non-congested state (as shown in Figure 4), and increases the elephant flow flow threshold at least once to reduce the chance of the data flow being judged as an elephant flow; the K and the M are both positive integers determined according to implementation requirements (for example: the K and the M are both integers greater than one).

In an implementation example, packets of different categories are associated with different queues, and the buffer circuit 10 adopts a known/self-developed class of service (CoS) queue scheduling technology to give different service levels to packets of different queues; the buffer circuit 10 includes a non-elephant flow buffer queue and at least one elephant flow buffer queue (for example: a first elephant flow buffer queue and a second elephant flow buffer queue, wherein the first elephant flow buffer queue has a lower transmission priority or a higher packet discard rate than the second elephant flow buffer queue), and the current queue characteristic value is a current queue characteristic value of the non-elephant flow buffer queue (for example: CurrG_QL in Figure 5); a non-elephant flow transmission priority associated with the non-elephant flow buffer queue is higher than any elephant flow transmission priority associated with the at least one elephant flow buffer queue, or the non-elephant flow buffer queue The packet discard rate of a non-elephant flow associated with the row is lower than the packet discard rate of any elephant flow associated with the at least one elephant flow buffer queue; when the buffer circuit 10 is in the congested state, after each current queue characteristic value of the at least one elephant flow buffer queue (for example, CurrY_QL and CurrR_QL in FIG. 5) is less than one-Kth of the target queue characteristic value for M times, the elephant flow flow threshold adjustment circuit 310 determines that the buffer circuit 10 returns to the non-congested state (as shown in FIG. 5), and increases the elephant flow flow threshold at least once to reduce the chance of the data flow being judged as an elephant flow; the K and the M are both positive integers determined according to the implementation requirements (for example, the K and the M are both integers greater than one). It is worth noting that the settings of "N times", "M times" and "one-Kth" in the above embodiments are used to control the sensitivity of the elephant flow flow threshold adjustment circuit 310 to the judgment of the congested state or non-congested state of the buffer circuit 10 to avoid too frequent state switching, and these values can be flexibly set according to the application scenario.

FIG6 is a flow chart showing an embodiment of how the elephant flow flow threshold adjustment circuit 310 adjusts the elephant flow flow threshold (ELE_TH) in a congested state. The steps of FIG6 can be repeatedly performed, including:

S610: The elephant flow rate threshold adjustment circuit 310 determines that the buffer circuit 10 is in a congested state.

S620: The elephant flow threshold adjustment circuit 310 determines whether the current queue characteristic value (Curr_QL) is greater than the target queue characteristic value (Target_QL); if so, proceed to step S632; if not, proceed to step S634.

S632: The elephant flow rate threshold adjustment circuit 310 determines that the congestion state has not been alleviated, and proceeds to step S642.

S634: The elephant flow rate threshold adjustment circuit 310 determines that the congestion state has been relieved, and enters step S644.

S642: The elephant flow threshold adjustment circuit 310 determines whether the current queue characteristic value (Curr_QL) is greater than a previous queue characteristic value (Old_QL); if so, proceed to step S652; if not, proceed to step S654. In this step, a queue characteristic value (e.g., queue length or queue delay) of the buffer circuit 10 at a current time point is the current queue characteristic value; the queue characteristic value of the buffer circuit 10 at a previous time point is the previous queue characteristic value.

S644: The elephant flow flow threshold adjustment circuit 310 determines whether the current queue characteristic value (Curr_QL) is greater than a previous queue characteristic value (Old_QL); if so, proceed to step S654; if not, proceed to step S656. In this step, a queue characteristic value (e.g., queue length or queue delay) of the buffer circuit 10 at a current time point is the current queue characteristic value; the queue characteristic value of the buffer circuit 10 at a previous time point is the previous queue characteristic value.

S652: The elephant flow flow threshold adjustment circuit 310 determines that the congestion state becomes more serious, and enters step S662.

S654: The elephant flow flow threshold adjustment circuit 310 determines that the congestion state does not change much, and proceeds to step S664.

S656: The elephant flow rate threshold adjustment circuit 310 maintains the elephant flow rate threshold unchanged.

S662: The elephant flow flow threshold adjustment circuit 310 lowers the elephant flow flow threshold by an adjustment value. For example, since the background of step S662 is that the congestion state becomes more serious (step S652) and the background of step S664 is that the congestion state does not change much (step S654), the adjustment value of step S662 may be greater than the adjustment value of step S664.

S664: The elephant flow rate threshold adjustment circuit 310 lowers the elephant flow rate threshold to an adjustment value.

In an implementation example, the adjustment value (Rate_adj) of steps S662 and S664 of FIG. 6 can be determined by the following formula:

Rate_adj＝A×(Curr_QL-Target_QL)+B×(Curr_QL-Old_QL)

Wherein A and B are constants that can be adjusted according to implementation requirements, and are used to strengthen or weaken the adjustment range of the elephant flow threshold (ELE_TH) (for example: ELE_TH = ELE_TH-Rate_adj, and ELE_TH is not less than 0). If A and B are both 0, the elephant flow threshold remains unchanged. In addition, the adjustment value can selectively change with the level of the elephant flow threshold, as shown in the example of Table 1 below; however, the implementation of the present invention is not limited thereto.

Table 1

ELE_TH Rate_adj ELE_TH<1Mbps Rate_adj＝Rate_adj/128 ELE_TH<2Mbps Rate_adj＝Rate_adj/64 ELE_TH<4Mbps Rate_adj＝Rate_adj/32 ELE_TH<8Mbps Rate_adj＝Rate_adj/16 ELE_TH<16Mbps Rate_adj＝Rate_adj/8 ELE_TH<32Mbps Rate_adj＝Rate_adj/4 ELE_TH<64Mbps Rate_adj＝Rate_adj/2 ELE_TH≥64Mbps Rate_adj＝Rate_adj

As mentioned above, when the elephant flow flow threshold adjustment circuit 310 determines that the buffer circuit 10 returns to the non-congested state (as shown in Figures 4 and 5), the elephant flow flow threshold adjustment circuit 310 increases the elephant flow flow threshold. In an implementation example, the elephant flow flow threshold has an upper limit. When the elephant flow flow threshold does not reach the upper limit, the elephant flow flow threshold (ELE_TH) can be determined by the following formula:

The above formula is only an example, and ordinary technicians in this field can modify the formula according to their implementation requirements.

Please refer to Figures 1 to 3. The classification decision circuit 320 is coupled to the elephant flow flow threshold adjustment circuit 310 and the recording circuit 210. The classification decision circuit 320 obtains the flow information of the multiple data flows from the recording circuit 210 to determine the classification of the multiple data flows included in the lookup table 212 according to the change of the relationship between the flow information of the multiple data flows and the elephant flow flow threshold; in other words, the classification of the multiple data flows will change with the flow information of the multiple data flows and the elephant flow flow threshold. For example, the classification decision circuit 320 calculates the flow of the first data flow based on the first flow information of the aforementioned first data flow (for example: the number of packets or the number of bytes of the first data flow counted by the recording circuit 210 within a counting time period) (for example: dividing the number of packets/number of bytes indicated by the first flow information by the counting time period), and then determines whether the flow of the first data flow is greater than the elephant flow flow threshold; when the flow of the first data flow is greater than the elephant flow flow threshold, the classification decision circuit 320 determines that the first data flow is classified as a elephant flow type; when the flow of the first data flow is less than the elephant flow flow threshold, the classification decision circuit 320 determines that the first data flow is classified as a non-elephant flow type.

FIG7 shows an implementation example of how the classification decision circuit 320 determines the classification of the first data flow, wherein the horizontal axis represents the flow rate of the data flow (Flow[i].Rate), and each vertical arrow line represents a data flow. As shown in FIG7 , the elephant flow flow threshold is higher than a first threshold (RED_MIN[i]), therefore, the classification decision circuit 320 determines the elephant flow type to be a first type; when the flow rate of the first data flow is greater than the elephant flow flow threshold, the classification decision circuit 320 determines the classification of the first data flow to be the first type (the two data flows on the right side of ELE_TH in the figure); when the flow rate of the first data flow is less than the elephant flow flow threshold, the classification decision circuit 320 determines the classification of the first data flow to be the non-elephant flow type (the seven data flows on the left side of ELE_TH in the figure). FIG8 shows another implementation example of how the classification decision circuit 320 determines the classification of the first data flow. As shown in FIG8 , the elephant flow flow threshold is less than the first threshold (RED_MIN[i]) but greater than a second threshold (YEL_MIN[i]), wherein the first threshold is greater than the second threshold, therefore, the classification decision circuit 320 determines that the elephant flow type includes the first type and a second type; if the flow of the first data flow is greater than the first threshold, the classification decision circuit 320 determines that the first data flow is classified as the first type (the three data flows on the right side of RED_MIN[i] in the figure); if the flow of the first data flow is less than the first threshold but greater than the elephant flow flow threshold, the classification decision circuit 320 determines that the first data flow is classified as the second type (the two data flows between RED_MIN[i] and ELE_TH in the figure); if the flow of the first data flow is less than the elephant flow flow threshold, the classification decision circuit 320 determines that the first data flow is classified as the non-elephant flow type (the four data flows on the left side of ELE_TH in the figure). FIG9 shows another implementation example of how the classification decision circuit 320 determines the classification of the first data flow. As shown in FIG9 , the elephant flow flow threshold is lower than the second threshold (YEL_MIN[i]), therefore, the classification decision circuit 320 determines that the elephant flow type includes the first type and a second type; if the flow of the first data flow is greater than the first threshold (RED_MIN[i]), the classification decision circuit 320 determines that the first data flow is classified as the first type (the three data flows on the right side of RED_MIN[i] in the figure); if the flow of the first data flow is less than the first threshold and greater than the second threshold and greater than the elephant flow flow threshold, the classification decision circuit 320 determines that The first data stream is classified as the second type (two data streams between RED_MIN[i] and YEL_MIN[i]); if the flow of the first data stream is less than the second threshold, regardless of whether it is greater than the elephant flow flow threshold, the classification decision circuit 320 determines that the first data stream is classified as the non-elephant flow type (the four data streams on the left side of YEL_MIN[i] in the figure), that is, after the elephant flow flow threshold is adjusted to be lower than the second threshold (YEL_MIN[i]), the second threshold is used as the standard for judging non-elephant flows, and any data stream less than the second threshold is judged as a non-elephant flow type. It is worth noting that the setting of the first threshold and/or the second threshold can be changed according to the classification of the data stream according to the implementation requirements; the first threshold and/or the second threshold can be stored in the classification decision circuit 320, or input to the classification decision circuit 320 by an external circuit (not shown in the figure).

In an implementation example, the classification decision circuit 320 may further determine whether the first data stream belongs to a special data stream group (e.g., a peer to peer (P2P) data stream group) based on the identification information of the multiple data streams and the traffic information of the multiple data streams, wherein the condition of the special data stream group may be determined according to implementation requirements and may include multiple data streams. For example, the traffic information of the multiple data streams may include packet length information and packet interval information; if the traffic information of the multiple data streams shows that the average packet length is greater than X bytes (e.g., 500 Bytes) and/or the average packet interval is less than Y milliseconds (e.g., 1 ms), wherein X and Y are both positive numbers greater than 0, the classification decision circuit 320 determines that the first data stream belongs to a P2P data stream group. It is worth noting that the present invention mainly uses the traffic statistics characteristics of the data stream to make judgments, and the above examples are not implementation limitations of the present invention. For example, characteristics such as packet interval variation may also be used. If the first data flow belongs to the special data flow group, the classification decision circuit 320 determines the classification of the first data flow based on the total flow of the special data flow group (that is, the sum of the flows of all data flows included in the special data flow group) and the elephant flow flow threshold; to be more specific, even if the flow of the first data flow is less than the elephant flow flow threshold, if the total flow of the data flow group to which the first data flow belongs is greater than the elephant flow flow threshold, the classification decision circuit 320 will still determine that the first data flow is a elephant flow (that is, it is determined that all data flows in the data flow group are elephant flows).

FIG. 10 shows another embodiment of the data stream classification device of the present application. The data stream classification device 1000 of FIG. 10 includes a forwarding circuit 1010 and a setting circuit 1020. Each of the forwarding circuit 1010 and the setting circuit 1020 can be implemented by hardware, or by hardware executing software and/or firmware. Although the embodiments of FIG. 1 and FIG. 10 are both used to classify data streams, the forwarding circuit 110 of FIG. 1 includes a function of obtaining flow information (e.g., number of packets/number of bytes) of a data stream, while the forwarding circuit 1010 of FIG. 10 does not need to include such a function; the setting circuit 120 of FIG. 1 does not need to include a function of recording the flow information (e.g., packet sequence number and its corresponding packet acquisition time) of the data stream, but the setting circuit 1020 of FIG. 10 includes such a function. In short, the setting circuit 120 of FIG. 1 can selectively have fewer functions, and the forwarding circuit 1010 of FIG. 10 can selectively have fewer functions, so the implementer of the present invention can adopt the architecture of FIG. 1 or FIG. 10 according to his needs. It is worth noting that a person of ordinary skill in the art can refer to the application of the embodiment of FIG. 1 to understand the details and changes of the embodiment of FIG. 10 , which means that the technical features of the embodiment of FIG. 1 can be applied to the embodiment of FIG. 10 in a reasonable manner. Therefore, the description of the embodiment of FIG. 10 does not repeat the parts already described in the embodiment of FIG. 1 in principle.

Fig. 11 shows an embodiment of the forwarding circuit 1010 of Fig. 10. The forwarding circuit 1010 of Fig. 11 includes a first storage circuit 1110, a classification circuit 1120 and a data stream information acquisition circuit 1130, wherein the first storage circuit 1110 and the classification circuit 1120 can be integrated into a lookup table circuit (not shown in the figure), but this is not an implementation limitation of the present invention.

Please refer to FIG. 10 and FIG. 11. The first storage circuit 1110 is used to store a lookup table 1112. The lookup table 1112 includes identification information of multiple data streams and classifications of the multiple data streams. In an implementation example, the identification information of each of the multiple data streams is, for example, a 5-tuple, but this is not a limitation of the present invention; in a feasible implementation, any information that can be used to identify the identity of a data stream can be used as the identification information.

Please refer to FIG. 10 and FIG. 11. The classification circuit 1120 is coupled to a data stream input terminal (i.e., the starting end of the "data stream" arrow shown in the figure) and a first storage circuit 1110, and is used to receive a first data stream from the data stream input terminal, so as to query the identification information of the multiple data streams recorded in the lookup table 1112 according to the first identification information of the first data stream, wherein the first data stream can be any data stream received by the data stream input terminal. An embodiment of the way in which the classification circuit 1120 queries the lookup table 1112 is the same as the way in which the classification circuit 220 of FIG. 2 queries the lookup table 212. When the lookup table 1112 includes the first identification information, the classification circuit 1120 uses the lookup table 1112 to determine the classification of the first data stream, and outputs the first data stream to a buffer circuit 11; an embodiment of the way in which the classification circuit 1120 determines the classification of the first data stream is the same as the way in which the classification circuit 220 of FIG. 2 determines the classification of the first data stream. When the lookup table 1112 does not include the first identification information, the classification circuit 1120 classifies the first data stream into a default classification (e.g., non-elephant stream type) and outputs the first data stream to the buffer circuit 11. It should be noted that the buffer circuit 11 may be included in the data stream classification device 1000, or may be independent of the data stream classification device 1000.

In an implementation example, an example of the classification of the multiple data streams included in the lookup table 1112 is the same as the classification of the multiple data streams included in the lookup table 212 of FIG. 2 (that is, the multiple classifications include elephant flow types and non-elephant flow types), and the buffer circuit 11 is similar to the buffer circuit 10, and will give different transmission priorities or packet discard rates to packets of data streams of different classifications. In an implementation example, when the lookup table 1112 includes the first identification information, the lookup table 1112 also includes the classification of the first data stream associated with the first identification information, so that the classification circuit 1120 can mark each packet of the first data stream according to the classification of the first data stream included in the lookup table 1112, and then the buffer circuit 90 can know the classification of the packet according to the marking of each packet.

Please refer to FIG. 10 and FIG. 11. The data stream information acquisition circuit 1130 is used to acquire at least a portion of the first data stream from the data stream input terminal or the output of the classification circuit 1120 to obtain and output the first identification information (e.g., the aforementioned five-value group) and the first flow information (e.g., the sequence number and sampling time of the packet) of the first data stream. It is worth noting that in this embodiment, regardless of whether the lookup table 1112 includes the first identification information, the data stream information acquisition circuit 1130 will be used to acquire at least a portion of the first data stream. In an implementation example, the data stream information acquisition circuit 1130 performs a sampling operation according to a default probability to try to acquire the at least a portion of the first data stream, thereby acquiring the first identification information and the first flow information; in other words, the probability of the data stream information supplementation circuit 1130 acquiring the at least a portion of the first data stream is the default probability, so the data stream information supplementation circuit 1130 may not sample packets of some data streams.

FIG12 shows an embodiment of the setting circuit 1020 of FIG10 . The setting circuit 1020 of FIG12 includes a second storage circuit 1210 , a large elephant flow rate threshold adjustment circuit 1220 and a classification decision circuit 1230 .

Please refer to Figures 10 to 12. The second storage circuit 1210 is coupled to the data stream information acquisition circuit 1130, and is used to store a data stream information table 1212. The data stream information table 1212 is used to store the identification information and flow information of the multiple data streams from the data stream information acquisition circuit 1130, wherein the identification information of the multiple data streams includes the first identification information, and the flow information of the multiple data streams includes the first flow information.

Please refer to FIG. 10 to FIG. 12. The elephant flow flow threshold adjustment circuit 1220 is coupled to the buffer circuit 11, and is used to determine an elephant flow flow threshold according to a change in the relationship between a target queue characteristic value (e.g., a fixed queue length or a fixed queue delay) and a current queue characteristic value (e.g., a variable queue length or a variable queue delay) of the buffer circuit 11. An embodiment of the elephant flow flow threshold adjustment circuit 1220 is the same as the elephant flow flow threshold adjustment circuit 310 of FIG. 3, and details are shown in FIG. 3 to FIG. 6 and related descriptions.

Please refer to FIG. 10 to FIG. 12. The classification decision circuit 1230 is coupled to the elephant flow flow threshold adjustment circuit 1220, the second storage circuit 1210 and the first storage circuit 1110. The classification decision circuit 1230 is used to determine the classification of the multiple data flows included in the lookup table 1112 of the first storage circuit 1110 according to the change of the relationship between the flow information of the multiple data flows and the elephant flow flow threshold. For example, the classification decision circuit 1230 first calculates the flow of the first data flow according to the first flow information of the first data flow included in the data flow information table 1212, and then determines the classification of the first data flow according to the flow of the first data flow and the elephant flow flow threshold, and then updates the classification of the first data flow in the lookup table 1112. An embodiment of the method for the classification decision circuit 1230 to determine the classification of the first data flow is the same as the method for the classification decision circuit 320 to determine the classification of the first data flow.

In an implementation example, when a packet protocol of the first data flow is the transmission control protocol (TCP), the data flow information acquisition circuit 1130 performs a sampling operation according to a default probability to obtain a previous packet and a current packet of the first data flow, and then the classification decision circuit 1230 obtains the flow of the first data flow according to the sequence numbers of the two packets and the sampling time of the two packets. For example, the sequence number (Pre_SN) and the sampling time (Pre_Time) of the previous packet are stored in the second storage circuit 1210, and the sequence number (Cur_SN) and the sampling time (Cur_Time) of the current packet are provided in real time by the data flow information acquisition circuit 1130, and the classification decision circuit 1230 divides a sequence number difference (deltaSN=Cur_SN-Pre_SN) of the sequence numbers of the two packets by an interval time (deltaTime=Cur_Time-Pre_Time) of the sampling time of the two packets to obtain the flow of the first data flow (Flow[i].rate), as shown in the following formula:

It should be noted that the sequence number and sampling time of the latest packet provided by the data stream information acquisition circuit 1130 will be used to update the sequence number and sampling time of the previous packet.

In an implementation example, when a packet protocol of the first data stream is not the transmission control protocol, the data stream information acquisition circuit 1130 performs a sampling operation according to a default probability to obtain two packets of the first data stream including a previous packet and a current packet, and then the classification decision circuit 1230 obtains the flow of the first data stream according to the length of the current packet, the preset probability and the sampling time of the two packets. For example, the sampling time (Pre_Time) of the previous packet is stored in the second storage circuit 1210, and the sampling time (Cur_Time) and length (Cur_Length) of the current packet are provided in real time by the data stream information acquisition circuit 1130, and the classification decision circuit 1230 divides the length of the current packet by the preset probability (P%), and then divides it by an interval (deltaTime=Cur_Time-Pre_Time) of the sampling time of the two packets to estimate the flow of the first data stream (Flow[i].rate), as shown in the following formula:

In an implementation example, the classification decision circuit 1230 can further determine whether the first data flow belongs to a special data flow group (for example, a peer to peer (P2P) data flow group) based on the identification information of the multiple data flows and the traffic information of the multiple data flows. The classification decision circuit 1230 and the classification decision circuit 320 use the same method to determine whether the first data flow belongs to a special data flow group.

Please note that, under the premise that implementation is possible, ordinary technicians in this technical field may selectively implement some or all of the technical features in any of the aforementioned embodiments, or selectively implement a combination of some or all of the technical features in the aforementioned multiple embodiments, thereby increasing the flexibility of the implementation of the present invention.

In summary, the present invention can classify multiple data streams based on the comparison between the flow rates of the multiple data streams and the flow rate threshold of a large data stream, thereby avoiding the problems of the prior art.

Although the embodiments of the present invention are described above, these embodiments are not intended to limit the present invention. A person skilled in the art may make changes to the technical features of the present invention according to the explicit or implicit contents of the present invention. All these changes may fall within the scope of patent protection sought by the present invention. In other words, the scope of patent protection of the present invention shall be subject to the scope defined by the claims.

Description of Reference Numerals

100: Data flow classification device

110: Forwarding circuit

120: Setting circuit

10: Buffer circuit

210: Recording circuit

212: Lookup Table

220: Classification Circuit

230: Data stream information supplement circuit

310: Elephant flow flow threshold adjustment circuit

320: Classification decision circuit

ELE_TH: Elephant flow flow threshold

Curr_QL: Current queue characteristic value

Target_QL: target queue characteristic value

CurrG_QL: Current queue characteristic value of non-elephant flow buffer queue

CurrY_QL: Current queue characteristic value of the elephant flow buffer queue

CurrR_QL: Current queue characteristic value of the elephant flow buffer queue

S610～S664: Steps

Old_QL: previous queue characteristic value

Flow[i].Rate: The rate of the data flow

RED_MIN[i]: first threshold

YEL_MIN[i]: second threshold

1000: Data flow classification device

1010: Forwarding circuit

1020: Setting circuit

11: Buffer circuit

1110: first storage circuit

1112: Lookup table

1120: Classification Circuit

1130: Data stream information acquisition circuit

1210: Second storage circuit

1212: Data flow information table

1220: Elephant flow flow threshold adjustment circuit

1230: Classification decision circuit

Claims (10)

1. A data stream classification device, comprising:

a forwarding circuit, comprising:

a recording circuit for calculating the flow rate of each of a plurality of data streams to obtain flow rate information of the plurality of data streams, and including a lookup table including identification information of the plurality of data streams, flow rate information of the plurality of data streams, and classification of the plurality of data streams;

The classifying circuit is coupled with a data stream input end and the recording circuit and is used for receiving a first data stream from the data stream input end, inquiring the identification information of the plurality of data streams included in the lookup table according to the first identification information of the first data stream, determining the classification of the first data stream by using the lookup table when the lookup table comprises the first identification information, outputting the first data stream to a buffer circuit, classifying the first data stream into a default classification when the lookup table does not comprise the first identification information, and outputting the first data stream to the buffer circuit; and

a data stream information supplementing circuit coupled to the recording circuit and the classifying circuit, wherein when the lookup table does not include the first identification information, the data stream information supplementing circuit obtains at least a portion of the first data stream to obtain the first identification information, and then the data stream information supplementing circuit adds the first identification information to the lookup table as a portion of the identification information of the plurality of data streams, wherein the recording circuit calculates a flow of the first data stream to obtain first flow information as a portion of the flow information of the plurality of data streams; and

A setting circuit, comprising:

an elephant flow threshold adjusting circuit, coupled to the buffer circuit, for determining an elephant flow threshold according to a change in a relationship between a target queue characteristic value and a current queue characteristic value of the buffer circuit; and

and the classification decision circuit is coupled with the elephant flow threshold adjustment circuit and the recording circuit and is used for determining the classification of the multiple data flows included in the lookup table according to the change of the relation between the flow information of the multiple data flows and the elephant flow threshold.

2. The data stream sorting apparatus of claim 1, wherein each packet of the first data stream includes the first identification information, the sorting circuit is configured to query the identification information of the plurality of data streams included in the lookup table according to the first identification information included in each packet of the first data stream, and when the lookup table includes the first identification information, the lookup table also includes the sorting of the first data stream associated with the first identification information, and the sorting circuit marks each packet of the first data stream according to the sorting of the first data stream included in the lookup table.

3. The data stream sorting apparatus of claim 1, wherein the data stream information supplement circuit performs a sampling operation with a default probability such that the data stream information supplement circuit obtains a probability of the at least a portion of the first data stream as the predetermined probability.

4. The data stream sorting apparatus of claim 1 wherein said elephant stream flow threshold adjustment circuit determines that said buffer circuit is in a congested state and lowers said elephant stream flow threshold at least once after said current queue characteristic value is greater than said target queue characteristic value by N times, said N being a positive integer.

5. The data stream sorting apparatus of claim 4, wherein a queue characteristic value of the buffer circuit at a current point in time is the current queue characteristic value, and the queue characteristic value of the buffer circuit at a previous point in time is a previous queue characteristic value; the characteristic value of the queue is a queue length or a queue time delay; and under the condition that the buffer circuit is judged to be in the congestion state by the elephant flow threshold adjusting circuit, if the current queue characteristic value is larger than the target queue characteristic value, the elephant flow threshold adjusting circuit further adjusts the elephant flow threshold according to the change of the relation between the current queue characteristic value and the previous queue characteristic value.

6. The data stream sorting apparatus of claim 4, wherein a queue characteristic value of the buffer circuit at a current point in time is the current queue characteristic value, and the queue characteristic value of the buffer circuit at a previous point in time is a previous queue characteristic value; the characteristic value of the queue is a queue length or a queue time delay; and under the condition that the buffer circuit is judged to be in the congestion state by the elephant flow threshold adjusting circuit, if the current queue characteristic value is smaller than the target queue characteristic value, the elephant flow threshold adjusting circuit further adjusts the elephant flow threshold or maintains the elephant flow threshold unchanged according to the change of the relation between the current queue characteristic value and the previous queue characteristic value.

7. The data flow classification device of claim 4 wherein said elephant flow threshold adjustment circuit determines that said buffer circuit is in a non-congested state and increases said elephant flow threshold at least once after said current queue characteristic value is less than K-th of said target queue characteristic value by up to M times; and K and M are positive integers.

8. The data stream sorting apparatus of claim 4, wherein said buffer circuit comprises a non-elephant stream buffer queue and at least one elephant stream buffer queue, said current queue characteristic value being a queue characteristic value of said non-elephant stream buffer queue; a non-elephant flow transmission priority associated with the non-elephant flow buffer queue is higher than any elephant flow transmission priority associated with the at least one elephant flow buffer queue, or a non-elephant flow packet discarding rate associated with the non-elephant flow buffer queue is lower than any elephant flow packet discarding rate associated with the at least one elephant flow buffer queue; after each current queue characteristic value of the at least one elephant flow buffer queue is less than one K times of the target queue characteristic value for M times, the elephant flow threshold adjusting circuit judges that the buffer circuit is in a non-congestion state and increases the elephant flow threshold at least once; and K and M are positive integers.

9. The data stream classification apparatus of claim 1, wherein said classification decision circuit determines that said first data stream is classified as an elephant stream type when said classification decision circuit determines that the flow of said first data stream is greater than said elephant stream flow threshold based on said first flow information; when the classification decision circuit judges that the flow of the first data flow is smaller than the elephant flow threshold according to the first flow information, the classification decision circuit decides that the first data flow is classified into a non-elephant flow type.

10. The data stream classification apparatus according to claim 1, wherein the classification decision circuit determines whether the first data stream belongs to a specific data stream group according to the identification information of the plurality of data streams and the traffic information of the plurality of data streams; if the first data stream belongs to the special data stream group, the classification decision circuit decides the classification of the first data stream according to the total flow of the special data stream group and the elephant flow threshold.