CN102075423A - Hardware multi-level table-based method for controlling output traffic - Google Patents

Abstract

The invention discloses an output flow control method based on a hardware multilevel table, and the technical problem to be solved is to control the flow on the premise of ensuring the integrity of the flow. The technical solution is to build a high-speed network content monitoring system composed of input card, output card, control host, and back-end analysis system, add a priority module to the input card, add a flow control module to the output card, and run flow control software on the control host; The priority module looks up the priority number in the priority table, and sends the message with the priority number to the output card; the flow control module looks up the flow control table corresponding to the priority number of the message, and decides to send the message or discard; the flow control software counts the flow, sets the discard flag bit, and controls the flow control module to perform flow control. By adopting the invention, the flow control can be carried out on the premise of ensuring the integrity of the flow, and the hardware logic is simple, the message processing speed is fast, and the network jitter is small.

Description

Output flow control method based on hardware multilevel table

technical field

The invention relates to the field of high-speed network traffic monitoring, in particular to a method for controlling overloaded traffic on the high-speed network.

Background technique

A high-speed network content monitoring system generally consists of a front-end data capture and distribution device and a back-end analysis system. The overall structure is shown in Figure 1. The front-end data capture and distribution equipment completes functions such as network access, data capture and distribution, data filtering and analysis, and is mainly composed of an input card and an output card including a hardware DPI (DPI: Deep Packet Inspection) module. The input card receives the network data flow, and the hardware DPI module in it performs in-depth message detection processing (such as rule matching), and the processed message is output from the port of the output card to the back-end analysis system, and the output card is based on the load of the back-end analysis system capacity for load balancing. The back-end analysis system further analyzes the packets output by the front-end equipment to realize network behavior audit, network content audit and intrusion detection. With the continuous improvement of the link speed of the backbone network, the main problem faced by the high-speed network content monitoring system is: the huge traffic often exceeds the processing capacity of the back-end analysis system, so the front-end equipment needs to control the output traffic by discarding some packets to make the Traffic conforms to the processing capabilities of the backend system. Since the back-end analysis system usually performs data analysis based on streams (TCP or UDP streams, including all packets in a session of the communication parties), it is required to maintain "flow integrity" as much as possible during flow control, that is, discarded packets are concentrated in In a small number of flows, as many flows as possible do not discard packets, maintaining flow integrity. Therefore, there is a need for a new flow control method that can maintain flow integrity.

The existing flow control methods mainly include:

1. Egress load balancing method. The basic idea is to distribute traffic as evenly as possible to multiple egresses to reduce packet discarding. However, considering that the processing capabilities of the back-end systems connected to each outlet may be different, and the actual flow size is also different, it is difficult to achieve a balanced and flexible distribution in the implementation. More importantly, egress load balancing cannot guarantee flow integrity.

2. congestion control method. Most network devices have a congestion control mechanism. When the packet waiting queue is full, the congestion control mechanism will discard redundant packets, but usually this discard is random and does not maintain the integrity of the flow.

3. QoS (Quality of Service, quality of service) method. The priority of the packets is determined according to the application protocol. When the network is congested, the packets with high priority will not be discarded, and the integrity of the flow cannot be maintained for applications with low priority. At the same time, because the priority is only determined according to the application protocol, the flexibility of flow control is poor. Summarizing the above methods, the biggest defect in common is that they do not guarantee the integrity of the flow, and it is difficult to meet the needs of the high-speed network content monitoring system. Most of the existing network devices use one or more of the above methods to control the flow in combination, but the integrity of the flow is still not guaranteed.

Contents of the invention

The technical problem to be solved by the invention is to perform flow control on the premise of ensuring the integrity of the flow.

In order to solve the above-mentioned specific technical problems, the technical solution includes the following steps:

The first step is to build a high-speed network content monitoring system. The high-speed network content monitoring system consists of an input card, an output card, a control host, and a back-end analysis system. A priority module is added to the input card, and the priority module is connected with the hardware DPI module and the output port of the input card. Level messages are sent to the output card; the output card is connected to the input card, the control host, and the back-end analysis system. An output card has an input port and several output ports. A flow control module is added to each output port of the output card. Each output port The flow control module of the output card is connected with the input port of the output card, the control host and the back-end analysis system, and the flow control module decides to send or discard the message; the control host is connected with the output card, and the flow control software runs on it, and the flow control software counts the flow , and set the discard flag bit according to the flow control policy, so as to control the flow control module to perform flow control. the

Priority module consists of control logic and priority table. The control logic is divided into the message header logic and the message header logic. The message header logic receives the message with the rule ID number in the head output by the hardware DPI module, takes out the rule ID number in the head, and searches The priority table obtains the corresponding relationship between the rule ID and the priority number, finds out the priority number corresponding to the rule ID, and then adds the priority number to the message header by adding the message header logic. Each entry in the priority table includes two fields: the rule ID value and the priority number. The rule ID value is the rule number that this packet matches, and the priority number is the priority corresponding to the rule ID value. A priority number, the smaller the priority number, the higher the priority. The number of items in these two fields is P, and P is a positive integer.

Each output port of the output card corresponds to a flow control module. Each flow control module is composed of flow control logic and P flow control tables, that is, each priority corresponds to a flow control table. Each item in the flow control table consists of three fields: serial number (ID), byte count (bytes) and discard flag (discard). The serial number ID is determined by the last n digits of the source IP and the last k digits of the destination IP, a total of n+k digits (n and k are both positive integers greater than or equal to 1 and less than or equal to 32), so a flow control table has a total of 2 ^{(n +k)} item. The number of bytes indicates the traffic size of a certain entry within the specified time, and the discard flag indicates whether the entry is discarded or forwarded, 0 for forwarding, 1 for discarding. The flow control logic of the flow control module of each output port is connected with the input port of the output card, P flow control tables, and the back-end analysis system. level to determine the flow control table corresponding to the priority of the message, and then look up the entry of the flow control table according to the source IP address and destination IP address of the message, and read the discard flag bit discard to decide whether to forward or discard the message , and update the number of bytes in the entry of the forwarded message.

In the second step, the hardware DPI performs rule matching according to the quintuple of packets flowing into the input card. Each rule has its own rule ID number. When a packet matches a certain rule, the ID of this rule is added to the In the header of the message, it is forwarded to the priority module, and the priority module looks up the corresponding priority number in the priority table according to the ID value of the message header, and adds it to the header of the message, and then adds the priority number The message is sent to the output card.

表示输出端口A_i（1≤i≤Z）的优先级为j（1≤j≤M）的流控表，用

表示输出端口A_i的优先级为j的流控表的第m项的字节数的值；

表示输出端口A_i的优先级为j的流控表的第m项的丢弃标志位的值；用

表示流控表中丢弃标志位为0的表项的集合。流量控制模块的流量控制逻辑按以下步骤对流量进行控制： In the third step, the flow control module of the output card determines the flow control table corresponding to the priority of the message according to the priority number carried in the head of each message, and then according to the last n bits of the source IP address of the message and the destination IP address (n+k) bits in total, look for the second ^(n+k) entry of the flow control table, and then check the discard flag of this entry, if the discard flag is 0, forward the report If the discard flag is 1, the message will be discarded. And update the byte count of the corresponding table entry for the forwarded message. use

Indicates the flow control table with the priority j (1≤j≤M) of the output port A _i (1≤i≤Z), using

Represents the value of the number of bytes of the mth item of the flow control table whose priority of output port A _i is j;

Indicates the value of the discard flag bit of the mth item of the flow control table whose priority is j at the output port A _i ; use

Indicates flow control table A collection of entries whose flag bit is 0 is discarded. The flow control logic of the flow control module controls the flow according to the following steps:

3.1 Determine the flow control table of the priority of the message according to the priority number of the input message.

3.2 Find the 2nd ^(n+k) item of the flow control table described in 3.1 according to the last n bits of the source IP address of the input message and the last k bits of the destination IP address (n+k) bits altogether.

是否为1，如果为1，则丢弃报文；否则，将报文发送出去。3.3 Judgment of item 2 ^(n+k) of the flow control table described in 3.2

Whether it is 1, if it is 1, discard the packet; otherwise, send the packet.

3.4 Add the size of the sent message to the number of bytes of the entry corresponding to the message to make statistics.

In the fourth step, the flow control software regularly reads all the flow control tables of the flow control module of each output port of the output card, sums the byte count fields of all entries whose discard flag is 0, and calculates the current output flow. If the output traffic exceeds the set port traffic limit, the discard flags of several entries in the flow control table will be set to 1 in order of priority from low to high, increasing the traffic discarded by the hardware. If the current traffic is less than the port traffic limit, the discard flags of several entries in the traffic control table will be set to 0 in order of priority from high to low to reduce the traffic discarded by the hardware.

For an output card with Z message output ports such as A ₁ , A ₂ , ... A _z , the limited flows of A ₁ , A ₂ , ... A _z are B ₁ , B ₂ , ... B _z , A ₁ , A ₂ , ... A _z respectively maintain P flow control tables with different priorities. The flow control software flow is:

），S_i是当前输出端口A_i实际输出总流量。若S_i＞B_i，则转步骤4.2，否则转步骤4.3。4.1 After a time interval T (T is set according to the actual flow control needs, generally less than or equal to 60 seconds), the flow control software reads from the flow control tables of P priorities at the output port A _i (1≤i≤Z) Take the value of the number of bytes in each entry whose discard flag is 0 and sum them up (that is,

), S _i is the actual output total flow of the current output port A _i . If S _i >B _i , go to step 4.2, otherwise go to step 4.3.

4.2 At this time, the total output flow of the output port A _i exceeds its load limit, and the strategy of fast discarding is adopted. The execution steps are as follows:

4.2.1 Set priority j to 1.

＝S_i－B_i。在流控表中选择若干表项的丢弃位置1，使得这些表项的字节数之和为

，从而恰好将超过部分的流量丢弃。如何选择表项是一个子集合问题。子集合问题可以表示为一个对偶（G，t），其中G是正整数的一个集合｛X₁,X₂,……X_n｝，t是一个正整数，要求找出G的一个子集，其和既要尽可能大但又不能大于t。由于子集合问题是一个NP完全问题，即只有指数时间的精确解，这里采用算法导论（INTRODUCTION TO ALGORITHMS，高等教育出版社，2002年版，第1046页）公布的多项式时间的近似算法APPROX_SUBSET_SUM（G，t）来求解：算法输入为（G，t），G为流控表表项的集合，t是超负载流量，输出为G的一个子集，使得G中表项的字节数之和尽可能大但不超过t。如果APPROX_SUBSET_SUM(

,

)返回空集，则转4.2.2.1；如果APPROX_SUBSET_SUM(

,)返回

，即全部丢弃也不能满足要求，则转4.2.2.3；否则转4.2.2.2。4.2.2 Let the excess traffic (traffic to be discarded) be

=S _i -B _i . In the flow control table, select the discarding position of several entries to be 1, so that the sum of the bytes of these entries is

, thus discarding exactly the excess traffic. How to select table items is a subset problem. The subset problem can be expressed as a dual (G, t), where G is a set {X ₁ , X ₂ ,...X _n } of positive integers, t is a positive integer, and it is required to find a subset of G whose and must be as large as possible but not larger than t. Since the subset problem is an NP-complete problem, that is, there is only an exact solution in exponential time, the polynomial time approximation algorithm APPROX_SUBSET_SUM (G, t) to solve: the input of the algorithm is (G, t), G is the set of flow control table entries, t is the overload traffic, and the output is a subset of G, so that the sum of the bytes of the entries in G is as small as possible. May be as large as but not larger than t. If APPROX_SUBSET_SUM(

,

) returns an empty set, then turn to 4.2.2.1; if APPROX_SUBSET_SUM(

, )return

, even discarding all of them can not meet the requirements, then go to 4.2.2.3; otherwise, go to 4.2.2.2.

4.2.2.1 No need to discard traffic anymore, go to 4.2.3;

作比较。若Q≥，将APPROX_SUBSET_SUM(

,

)返回的集合（表项的集合）中所有表项的丢弃标志位置1；转4.2.3；否则，执行4.2.2.3；4.2.2.2 Determine whether the current priority flow control table can meet the flow control requirements, that is, sum the number of bytes of all entries whose discard flag is 0, and set this sum as Q. Q and the overloaded traffic

compared to. If Q≥ , will APPROX_SUBSET_SUM(

,

) in the returned collection (a collection of entries), the discarding flag position of all entries is 1; go to 4.2.3; otherwise, execute 4.2.2.3;

＝

－Q，Q为当前优先级的流控表中丢弃标志位为0的所有表项的字节数之和。j＝j+1；转4.2.2。4.2.2.3 If the current priority flow control table cannot fulfill the traffic discarding requirements, first set the discard flags of all entries in the current priority flow control table to 1, thereby discarding all the traffic in the table. The remaining traffic to be discarded needs to be discarded in the higher-level flow control table, so that

=

-Q, Q is the sum of the number of bytes of all entries in the flow control table of the current priority with the discard flag bit set to 0. j=j+1; turn to 4.2.2.

4.2.3 Complete this flow control, go to 4.4.

,……

｝，设为（1≤Y≤L），令此项的丢弃标志位为0，即＝0。转4.4。4.3 At this time, the total output flow of the output port A _i is less than its load capacity, and the strategy of slow recovery is adopted. At this time, the output port A _i has the discard flag bit set to 1 in all flow control tables with the highest priority as H, and Assume that in the flow control table with priority H, there are F ₁ , F ₂ , ... F _L entry discard flags set to 1 (1≤L≤2 ^(n+k) ). Then select the item with the least number of bytes among these entries, that is, min{ ,

,...

}, set to (1≤Y≤L), let the discard flag of this item be 0, namely =0. Go to 4.4.

4.4 Clear the bytes of all flow control table entries, restart the statistics, and go to 4.1.

Adopt the present invention can reach following technical effect:

(a) The hardware logic is simple. The priority module and the flow control module of the present invention are realized by hardware, and only need to maintain the priority table and the flow control table respectively, and the table look-up process is simple to realize, so the message processing speed is fast, which meets the needs of the high-speed network content monitoring system.

(b) Preserve the integrity of the stream. In order to ensure the application of content security, when discarding and restoring packets, the operations are performed based on the priority, source IP address, and destination IP address lookup table entries, that is, it is performed in flow units, and a flow is either completely discarded or completely reserved. The disadvantage of other methods not maintaining the integrity of the stream is overcome.

(c) According to the result of the hardware DPI, determine the flow control table of the priority of a message. The message that the user is interested in can be given a higher priority to avoid packet loss as much as possible.

(d) The network jitter is small. If the total traffic exceeds the limit value, the fast discard strategy is adopted, that is, all the overloaded traffic is discarded in the next time period, so that the actual traffic decreases rapidly; if the actual total traffic is less than the limit value, the slow recovery strategy is adopted, that is, only one recovery A flow to avoid the actual flow exceeding the limit again in a short period of time.

Description of drawings

FIG. 1 is a general structural diagram of the existing high-speed network content monitoring system described in the background art.

Fig. 2 is the overall structural diagram of the high-speed network content monitoring system designed in the first step of the present invention.

Fig. 3 is a structural diagram of the priority module of the present invention.

Fig. 4 is a structural diagram of the flow control module of the present invention.

Fig. 5 is a flow chart of the flow control logic decision of the present invention to send or discard the message.

Fig. 6 is a flowchart of the flow control software of the present invention.

Fig. 7 is an overall flowchart of the present invention.

Fig. 8 is an example of the high-speed network content monitoring system of the present invention.

Detailed ways:

FIG. 1 is a general structure diagram of an existing high-speed network content monitoring system in the background technology. The front-end data capture and distribution equipment completes functions such as network access, data capture and distribution, data filtering and analysis, and is mainly composed of an input card and an output card including a hardware DPI (DPI: Deep Packet Inspection) module. The input card receives the network data flow, and the hardware DPI module in it performs in-depth message detection processing (such as rule matching), and the processed message is output from the port of the output card to the back-end analysis system, and the output card is based on the load of the back-end analysis system capacity for load balancing. The back-end analysis system further analyzes the packets output by the front-end equipment to realize network behavior audit, network content audit and intrusion detection.

Fig. 2 is an overall structural diagram of the high-speed network content monitoring system implemented in the first step of the present invention. The high-speed network content monitoring system consists of an input card, an output card, a control host, and a back-end analysis system. A priority module is added to the input card, and the priority module is connected with the hardware DPI module and the output port of the input card. Level messages are sent to the output card; the output card is connected to the input card, the control host, and the back-end analysis system. An output card has an input port and several output ports. A flow control module is added to each output port of the output card. Each output port The flow control module of the output card is connected to the input port of the output card, the control host, and the back-end analysis system. The flow control module decides to send or discard the message; the control host is connected to the output card, and the flow control software runs on it, and the flow control software counts the flow. , and set the discarding flag bit according to the flow control policy realized in the present invention, so as to control the flow control module to perform flow control. the

Figure 3 is a structural diagram of the priority module. Priority module consists of control logic and priority table. The control logic is divided into the message header logic and the message header logic. The message header logic receives the message with the rule ID number in the head output by the hardware DPI module, takes out the rule ID number in the head, and searches Priority table, find out the corresponding priority number, and then add the priority number to the message header by adding the message header logic. Each entry in the priority table includes two fields: the rule ID value and the priority number. The rule ID value is the rule number that this packet matches, and the priority number is the priority corresponding to the rule number. The smaller the priority, the higher the priority. high. The number of items in these two domains takes a non-negative integer M according to actual needs.

Figure 4 is a structural diagram of the flow control module. The flow control module is composed of flow control logic and flow control table. Each item in the flow control table consists of three fields: serial number (ID), byte count (bytes) and discard flag (discard). Each priority corresponds to a flow control table, and the ID is determined by n+k bits of the last n bits of the source IP and the last k bits of the destination IP, so the flow control table has a total of 2 ^n+k items. The number of bytes indicates the traffic size of a certain entry within the specified time, and the discard flag indicates whether the entry is discarded or forwarded, 0 for forwarding, 1 for discarding. The flow control logic receives the input message and determines the priority flow control table corresponding to the message according to its priority, and then searches the entry of the flow control table according to the source IP address and destination IP address of the message, and reads The discard flag is used to decide whether to forward or discard the packet, and to update the byte count of the entry for the forwarded packet.

Figure 5 is a flow chart of the flow control logic deciding whether to send or discard the message. The flow control logic is based on the priority of each message, the last n bits of the source IP address and the last k bits of the destination IP address, a total of (n+k) bits (n and k are both positive integers greater than or equal to 1 and less than or equal to 32), find the 2nd ^n+k entry in the flow control table of the corresponding priority, check the discard flag of the entry, if the discard flag is 0 , the packet is forwarded; if the discard flag is 1, the packet is discarded. Then update the value of the number of bytes in the entry of the flow control table corresponding to the message.

Figure 6 is a flowchart of the flow control software.

First, the flow control software regularly reads all the flow control tables of the flow control module of each output port of the output card, sums the byte count fields of all entries whose discard flag is 0, and calculates the current output flow.

Then make a judgment: if the current output flow exceeds the set port flow limit, use the subset problem approximation algorithm in order of priority from low to high to solve, set the discard flag position of several entries in the flow control table to 1, increase Traffic dropped by hardware. If the current traffic is less than the port traffic limit, the slow recovery strategy is adopted in order of priority from high to low, and the discard flags of several entries in the multi-level flow control table are set to 0 to reduce the traffic discarded by the hardware.

Finally, the byte count entry is cleared for the next statistics.

Fig. 7 is an overall flowchart of the present invention.

The first step is to build a high-speed network content monitoring system.

In the second step, the hardware DPI performs rule matching according to the quintuple of packets flowing into the input card. Each rule has its own rule ID number. When a packet matches a certain rule, the ID of this rule is added to the In the header of the message, it is forwarded to the priority module, and the priority module looks up the corresponding priority number in the priority table according to the ID value of the header of the message, and adds it to the header of the message. Send the message with the priority number to the output card.

In the third step, the flow control module of the output card searches for (n+k) bits according to the priority number carried by each message header, the last n bits of the message source IP address, and the last k bits of the destination IP address. The second ^(n+k) entry of the flow control table corresponding to this priority, and then check the discarding flag of this table entry, if the discarding flag is 0, then forward the message; if the discarding flag is 1, then discard the message.

In the fourth step, the flow control software regularly reads all the flow control tables of the flow control module of each output port of the output card, sums the byte count fields of all entries whose discard flag is 0, and calculates the current output flow. If the output traffic exceeds the set port traffic limit, the discard flags of several entries in the flow control table will be set to 1 in order of priority from low to high, increasing the traffic discarded by the hardware. If the current traffic is less than the port traffic limit, the discard flags of several entries in the traffic control table will be set to 0 in order of priority from high to low to reduce the traffic discarded by the hardware.

Fig. 8 is an example of a high-speed network content monitoring system designed by the National Defense University using the present invention:

The first step is to build a high-speed network content monitoring system. In the present invention, the input card uses an OC768 (40G) line card, and the output card uses an OC192 (10G) line card. The priority module of the OC768 line card is realized by the FPGA of Stratix EP2SGX130F1508C4, the flow control module and the flow control table are realized by the FPGA of Altera StratixⅡGX EP2S60GX of the OC192 (10G) line card, and the flow control software is realized by C language in the environment of the linux operating system . Each port of the output card is connected with back-end analysis systems such as IDS and content auditing. The OC192 (10G) line card has four output ports, and the limited output traffic of each port is 10G.

In the second step, the message flows through the OC768 (40G) line card, and the priority module of the line card performs quintuple filtering on the message according to the rules set by the user in the hardware DPI to determine its priority.

In the third step, the packets with determined priority flow through the OC192 (10G) line card. The OC192 (10G) line card has four output ports, and each output port has a flow control module. The flow control module of the line card maintains multiple flow control tables with different priorities for each output port, according to the last four bits of the source IP address (n=4) and the last five bits of the destination IP address ( k=5) has nine bits in total, and maps the message to the flow control table of the corresponding priority, and each flow control table has ²⁹ or 512 entries. The flow control module forwards or discards the packets according to the setting of the discarding flag bit in the flow control table of each port.

In the fourth step, the flow control software counts the number of bytes in the flow control table of each port, sets flags and other operations according to the procedures described in 4.1 to 4.4 every 30 seconds.

Claims (1)

1. a kind of output flow control method based on hardware multilevel table, it is characterized in that comprising the following steps: The first step is to build a high-speed network content monitoring system. The high-speed network content monitoring system is composed of an input card, an output card, a control host, and a back-end analysis system; a priority module is added to the input card, and the priority module is connected with the hardware DPI module and the input card It receives the message processed by deep message detection from the hardware DPI, determines the priority of the message, and then transmits the message with the determined priority to the output card; the output card is connected with the input card, the control host, The back-end analysis system is connected. An output card has an input port and several output ports. A flow control module is added to each output port of the output card. The flow control module of each output port is connected to the input port of the output card, the control host, and the back-end analysis system. Connected, the flow control module decides to send or discard the message; the control host is connected to the output card, on which the flow control software runs, the flow control software counts the flow, sets the discard flag, and controls the flow control module to perform flow control; The priority module is composed of control logic and priority table. The control logic is divided into message header logic and message header logic. The message header logic receives the message with the rule ID number output by the hardware DPI module. Take out the rule ID number in its head, and search the priority table to obtain the corresponding relationship between the rule ID and the priority number, find out the priority number corresponding to the rule ID, and then add the priority number to the packet header logic In the message header; each entry in the priority table includes two fields: the rule ID value and the priority number. The rule ID value is the rule number that this message matches, and the priority number is the priority corresponding to the rule ID value. , a rule ID value corresponds to a priority number, the smaller the priority number is, the higher the priority is, the number of items in these two fields is P, and P is a positive integer; Each output port of the output card corresponds to a flow control module, and each flow control module is composed of flow control logic and P flow control tables, that is, each priority corresponds to a flow control table; each item of the flow control table is composed of a serial number ID, the number of bytes, and the discard flag are composed of three fields; the serial number ID is determined by the last n bits of the source IP and the last k bits of the destination IP, a total of n+k bits, and n and k are both greater than or equal to 1 and less than or equal to A positive integer of 32; the number of bytes indicates the traffic size of a certain table item within a specified time, and the discard flag indicates whether the table item is discarded or forwarded, 0 is forwarded, 1 is discarded; the flow rate of the flow control module of each output port The control logic is connected to the input port of the output card, P flow control tables, and the back-end analysis system. It receives the input message from the input port of the output card and determines the corresponding priority of the message according to the priority of the message. Then, according to the source IP address and destination IP address of the message, look up the entry of the flow control table, read the discard flag bit discard to decide whether to forward or discard the message, and update the forwarded message The number of bytes of the entry in the table; In the second step, the hardware DPI performs rule matching according to the quintuple of packets flowing into the input card. Each rule has its own rule ID number. When a packet matches a certain rule, the ID of this rule is added to the In the header of the message, it is forwarded to the priority module. The priority module searches the corresponding priority number in the priority table according to the ID value of the message header, and adds it to the header of the message. The message is sent to the output card; In the third step, the flow control module of the output card determines the flow control table corresponding to the priority of the message according to the priority number carried in the head of each message, and then according to the last n bits of the source IP address of the message and the destination IP address The last k bits of the total n+k bits, look up the second ^(n+k) entry of the flow control table, and then check the discard flag of this entry, if the discard flag is 0, then forward the message; If the discard flag is 1, discard the packet; use

Indicates the flow control table with priority j of the output port A _i , 1≤i≤Z, 1≤j≤M,

Indicates the value of the number of bytes in the mth item of the flow control table with priority j of the output port A _i , Indicates the value of the discard flag bit of the mth item of the flow control table with priority j of the output port A _i , expressed by

Indicates flow control table

The set of entries whose flag bit is 0 is discarded in the set, and the flow control logic of the flow control module controls the flow according to the following steps: 3.1 Determine the flow control table of the priority of the message according to the priority number of the input message; 3.2 Find the 2nd ^(n+k) item of the flow control table described in 3.1 by the last n bits of the source IP address of the input message and the last k bits of the destination IP address altogether n+k bits; 3.3 Judgment of item 2 ^(n+k) of the flow control table described in 3.2

Whether it is 1, if it is 1, discard the message; otherwise, send the message; 3.4 Add the size of the sent message to the number of bytes of the entry corresponding to the message, and make statistics; In the fourth step, the flow control software regularly reads all the flow control tables of the flow control module of each output port of the output card, sums the byte count fields of all entries whose discard flag is 0, and calculates the current output flow. If the output flow exceeds the set port flow limit, the discard flags of several entries in the flow control table will be set to 1 in order of priority from low to high to increase the flow discarded by the hardware; if the current flow is less than the port flow limit, then Set the discard flags of several entries in the flow control table to 0 in order of priority from high to low to reduce the traffic discarded by hardware: For an output card with A ₁ , A ₂ , ... A _z Z message output ports, the limited flows of A ₁ , A ₂ , ... A _z are B ₁ , B ₂ , ... B _z , A ₁ , A ₂ , ... A _z respectively maintain P flow control tables with different priorities, and the flow control software flow is: 4.1 After the time interval T, T is less than or equal to 60 seconds, the flow control software reads the value of the number of bytes in each entry whose discard flag is 0 from the flow control table of the P priorities of the output port A _i and sums them ,Right now

, 1≤i≤Z, S _i is the actual total output flow of the current output port A _i , if S _i >B _i , go to step 4.2, otherwise go to step 4.3; 4.2 At this time, the total output traffic of the output port A _i exceeds its load limit, and the strategy of fast discarding is adopted, and the execution steps are as follows: 4.2.1 Set priority j to 1; 4.2.2 Let the excess flow be

=S _i -B _i , using the polynomial time approximation algorithm APPROX_SUBSET_SUM (G, t) to select the discarding position of several entries in the flow control table, so that the sum of the bytes of these entries is

, so that the excess traffic is just discarded; the input of the algorithm is (G, t), G is the set of flow control table entries, t is the overload traffic, and the output is a subset of G, so that the words of the entries in G The sum of the number of sections is as large as possible but does not exceed t; if APPROX_SUBSET_SUM(

,

) returns an empty set, then turn to 4.2.2.1; if APPROX_SUBSET_SUM(

,

)return

, that is, all discarded can not meet the requirements, then go to 4.2.2.3; otherwise, go to 4.2.2.2; 4.2.2.1 No need to discard traffic anymore, go to 4.2.3; 4.2.2.2 Determine whether the current priority flow control table can meet the flow control requirements, that is, sum the number of bytes of all entries whose discard flag is 0, set this sum as Q, and then add Q and overload traffic

For comparison, if Q≥

, will APPROX_SUBSET_SUM(

,

) The discard flag position of all entries in the returned set is 1; go to 4.2.3; otherwise, execute 4.2.2.3; 4.2.2.3 The current priority flow control table cannot fulfill the traffic discarding requirements. First, set the discarding flags of all entries in the current priority flow control table to 1, thereby discarding all the traffic in this table; the remaining traffic to be discarded needs to be Discarding is performed in the higher-level flow control table, so that

=

-Q, Q is the sum of the number of bytes of all items in the current priority flow control table whose discard flag is 0, j=j+1, go to 4.2.2; 4.2.3 Complete this flow control, go to 4.4; 4.3 At this time, the total output flow of the output port A _i is less than its load capacity, and the strategy of slow recovery is adopted. At this time, the output port A _i has the discard flag bit set to 1 in all flow control tables with the highest priority as H, and Assume that there are F ₁ , F ₂ , ... _FL entry discard flags set to 1 in the flow control table with priority H, and 1≤L≤2 ^(n+k) , then select words in these entries The item with the least number of sections, namely min{

,

,...

}, set to

, 1≤Y≤L, let the discard flag of this item be 0, that is

=0; turn to 4.4; 4.4 Clear the bytes of all flow control table entries, restart the statistics, and go to 4.1.

Images