CN110149282A - Traffic scheduling method and device - Google Patents

Abstract

The present application provides a traffic scheduling method and device, by obtaining the weight of the first receiving queue according to the classification attribute of the first receiving queue, and obtaining the traffic arrival of the first receiving queue according to the historical packet receiving status and weight of the first receiving queue Rate, obtain the additional bandwidth of the first receiving queue from the total bandwidth of HTB according to the weight, obtain the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and additional bandwidth of the first receiving queue, and perform speed limit operation according to the allocated bandwidth , that is, in the process of bandwidth allocation, bandwidth allocation can be performed without visiting the parent node. Therefore, no node jump and data maintenance of the parent node are required, thereby improving the efficiency of bandwidth allocation, simplifying the packet scheduling process, and improving the It improves the efficiency of message scheduling and reduces the processing delay of the message.

Description

Flow scheduling method and device

technical field

The present application relates to the field of computer technology, and in particular to a flow scheduling method and device.

Background technique

Network as a Service (NaaS) is the mainstream direction of network technology development at present. Different tenants and applications of cloud networks have different requirements for the Quality of Service (QoS) of network packets. This "multiple The realization of "Model of Level QoS" requires a traffic scheduling method. The traffic scheduling method can set the messages received by the network card into the memory of the server, and store different types of messages in queues in the memory. The queues include enqueue queues and queues. Dequeue the queue.

In the prior art, the hierarchical token bucket (Hierachical Token Bucket, HTB) algorithm is used to realize the traffic scheduling of the messages in the queue, which can limit and integrate the network traffic of a certain type of messages at a certain rate. The HTB algorithm organizes the enqueue queues into a tree according to the bandwidth sharing relationship. The enqueue operation classifies the packets according to the network configuration. If the queue is not full, the enqueue is successful; The running status of the token bucket determines whether the packet is successfully dequeued or fails to dequeue. If the bandwidth required by the child node exceeds the guaranteed bandwidth (Assured Rate, AR) but does not exceed the maximum bandwidth (Ceil Rate, CR), it can borrow tokens from the parent node. token, and use the token to borrow bandwidth from the parent node queue until the total bandwidth of the node reaches CR. In the existing HTB technology, when a child node queue of the parent node queue borrows tokens from the parent node queue, the parent node queue needs to be locked, so that other child node queues of the parent node queue will not be able to borrow tokens from the parent node queue after locking. The queue borrows bandwidth. Since the parent node queue is set in the server memory, if the memory is locked too many times, the performance of the stream server will be reduced. In addition, the child node queue borrows a token from the parent node queue and uses the token When borrowing bandwidth from the parent node queue, memory switching operations are involved, and too many memory switching operations will also affect the performance of the server.

Therefore, the efficiency of traffic scheduling is not high in the way of the prior art.

Contents of the invention

The present application provides a traffic scheduling method and device to improve traffic scheduling efficiency.

In the first aspect, the present application provides a traffic scheduling method, which obtains the weight of the first receiving queue according to the classification attribute of the first receiving queue, wherein the first receiving queue corresponds to the first receiving queue of the hierarchical token bucket HTB A leaf node; obtain the traffic arrival rate of the first receiving queue according to the historical packet receiving situation of the first receiving queue and the weight; obtain the first receiving queue from the total bandwidth of the HTB according to the weight receiving the extra bandwidth of the queue; obtaining the allocated bandwidth of the first receiving queue according to the traffic arrival rate, the guaranteed bandwidth and the extra bandwidth of the first receiving queue; and performing a speed limit operation according to the allocated bandwidth.

That is, in the process of bandwidth allocation, bandwidth allocation can be performed without visiting the parent node. Therefore, no node jump and data maintenance of the parent node are required, thereby improving bandwidth allocation efficiency, simplifying the packet scheduling process, and improving packet Scheduling efficiency.

In an implementation manner of the present application, the classification attribute includes billing information and tenant reputation, and the obtaining the weight of the first receiving queue according to the classification attribute of the first receiving queue includes:

Calculate the billing information and the tenant reputation to obtain the weight of the first receiving queue.

Since the weight of the receiving queue is determined according to the billing information and the tenant reputation, different weights can be determined for the receiving queues of different billing information and the tenant reputation, and the weight is considered when performing bandwidth allocation, so that the bandwidth allocation is more reasonable .

In another implementation manner of the present application, the calculating the charging information and the tenant reputation, and obtaining the weight of the first receiving queue includes:

Weighted averaging is performed on the billing information and the tenant reputation to obtain the weight of the first receiving queue.

The weighted average of the billing information and the tenant reputation is obtained to obtain the weight of the receiving queue, which makes the determination of the weight of the receiving queue more reasonable, and the calculation method is simple and efficient, which can further improve the efficiency of traffic scheduling.

In another implementation manner of the present application, the historical packet reception conditions include the number of first packets received by the first receiving queue at the first time point and the number of packets received by the first receiving queue at the second time point The number of the second packets received, the said first receiving queue according to the historical packet receiving status and the weight, to obtain the traffic arrival rate of the first receiving queue, including:

Acquiring a difference in the number of messages between the second number of messages and the first number of messages;

Acquiring a time difference between the second time point and the first time point;

Obtain the traffic arrival rate of the first receiving queue according to the message quantity difference, the time difference and the weight of the first receiving queue.

The traffic arrival rate of the queue is determined by historical message reception, without node jump and parent node data maintenance, thereby avoiding memory switching and memory locking, improving bandwidth allocation efficiency, simplifying the message scheduling process, and improving message scheduling efficiency and reduce packet processing delay.

In another implementation manner of the present application, the acquiring the traffic arrival rate of the first receiving queue according to the packet quantity difference, the time difference and the weight of the first receiving queue includes:

Obtaining the ratio of the packet quantity difference to the time difference as the average traffic arrival rate;

Acquiring the traffic arrival rate of the first receiving queue according to the weight and the average traffic arrival rate.

By determining the traffic arrival rate of the queue based on the average traffic arrival rate received by historical packets, no node jump and parent node data maintenance are required, thereby avoiding memory switching and memory locking, improving bandwidth allocation efficiency, and simplifying packet scheduling process, improve packet scheduling efficiency, and reduce packet processing delay.

In another implementation manner of the present application, the obtaining the traffic arrival rate of the first receiving queue according to the weight and the average traffic arrival rate includes:

The traffic arrival rate of the first receiving queue is obtained by multiplying the weight by the average traffic arrival rate.

The traffic arrival rate of the first receiving queue is obtained by multiplying the weight by the average traffic arrival rate. It makes the determination of the traffic arrival rate of the receiving queue more reasonable, and the calculation method is simple and efficient, which can further improve the efficiency of traffic scheduling.

In another implementation manner of the present application, the obtaining the additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight includes:

Select the smaller value in the guaranteed bandwidth of the receive queue corresponding to the leaf node of the HTB and the traffic arrival rate as the candidate bandwidth of the leaf node corresponding to the receive queue;

Accumulate the candidate bandwidth of each leaf node to obtain the candidate bandwidth accumulation value;

Obtaining the difference between the total bandwidth and the accumulated value of the candidate bandwidth as the shared bandwidth;

Acquire the additional bandwidth of the first receiving queue according to the ratio of the weight to the sum of the weights of all leaf nodes requiring additional bandwidth and the shared bandwidth.

In another implementation manner of the present application, the obtaining the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue includes:

The allocated bandwidth of the first receiving queue is obtained according to the sum of the smaller value of the traffic arrival rate and the guaranteed bandwidth and the additional bandwidth.

In another implementation of the present application, obtaining the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth, and the additional bandwidth of the first receiving queue includes:

The allocated bandwidth of the first receiving queue is obtained according to the sum of the traffic arrival rate and the guaranteed bandwidth, the additional bandwidth, and the bandwidth rate allowed to burst.

In another implementation manner of the present application, the speed limit operation according to the allocated bandwidth includes:

Obtain parameters related to speed limit operation;

A speed limit operation is performed according to the allocated bandwidth and the parameters related to the speed limit operation.

In another implementation manner of the present application, the parameters related to the speed limit operation include at least one of the following:

Allowable burst bandwidth rate in packet forwarding;

Maximum limit rate;

The processing method for packets exceeding the maximum rate limit.

In a second aspect, the present application provides a traffic scheduling device, including:

The obtaining module is used to obtain the weight of the first receiving queue according to the classification attribute of the first receiving queue, wherein the first receiving queue corresponds to any leaf node of the hierarchical token bucket HTB;

The obtaining module is also used to obtain the traffic arrival rate of the first receiving queue according to the historical message receiving situation of the first receiving queue and the weight;

The obtaining module is also used to obtain the additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight;

The obtaining module is further configured to obtain the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue;

A control module, configured to perform a speed limit operation according to the allocated bandwidth.

The second aspect or any implementation of the second aspect is a device implementation corresponding to the first aspect or any implementation of the first aspect, and the descriptions in the first aspect or any implementation of the first aspect are applicable to the third aspect Or any implementation manner of the third aspect, which will not be repeated here.

In a third aspect, the present application provides a computer device, including:

a storage unit for storing instructions; and

at least one processor coupled to the storage unit;

Wherein, when the at least one processor executes the instruction, the instruction causes the processor to execute the method described in the first aspect of the claim or any implementation manner of the first aspect, which will not be repeated here. .

In a fourth aspect, the present application provides a computer-readable storage medium, the storage medium is used to store a computer program, and the computer program is used to implement the method described in the first aspect or any implementation manner of the first aspect, I won't repeat them here.

Description of drawings

FIG. 1 is a schematic diagram of a traffic distribution tree structure provided by the present application;

FIG. 2 is a schematic diagram of a traffic scheduling architecture provided by the present application;

FIG. 3 is a schematic diagram of a tree structure corresponding to the traffic scheduling architecture shown in FIG. 2;

FIG. 4 is a schematic diagram of a tree structure provided by the present application;

FIG. 5 is a schematic flow diagram of a traffic scheduling method provided by the present application;

FIG. 6 shows a schematic diagram of a system structure of a traffic scheduling system according to an embodiment of the present invention;

FIG. 7 is a schematic structural diagram of an embodiment of a traffic scheduling device provided by the present application;

Fig. 8 is a schematic diagram of a device structure of a computer device according to an embodiment of the present invention

Detailed ways

According to the constraints of all nodes in the traffic distribution tree structure, this application performs normalization processing through mathematical modeling to obtain the constraints of all leaf nodes, thereby normalizing the multi-level token buckets to the order on the leaf nodes card bucket. For the convenience of description, this application defines the following parameters: the effective demand bandwidth of leaf nodes (Demandrate, D), the available bandwidth of leaf nodes (Supply rate, S), AR and CR, where the effective demand bandwidth is also called For the traffic arrival rate, the entitlement bandwidth is also called the allocated bandwidth. The token bucket can determine a set of size relationships between D and S (D≤S). In the prior art, D of a leaf node appears in multiple inequalities and needs to go through multiple token buckets. This application simplifies constraints, reducing the number of token buckets.

Figure 1 is a schematic diagram of a traffic distribution tree structure provided by this application. Taking Figure 1 as an example, the implementation of normalizing the multi-level token buckets to the token buckets on the leaf nodes is as follows:

The solution goal of this application is to maximize the allocated bandwidth (deserving bandwidth) of all leaf nodes, that is, the objective function is:

MaxZ＝S1+S3+S4+S5+S6+S21+S22+S23+S24

The existing constraints must satisfy the level recursively traversing the sum of all the bandwidth of the child nodes that should be less than the CR of the parent node, that is, the constraints are as follows:

min{D1, AR1}≤S1≤CR1

min{D3, AR3}≤S3≤CR3

min{D4, AR4}≤S4≤CR4

min{D5, AR5}≤S5≤CR5

min{D6, AR6}≤S6≤CR6

min{D21, AR21}≤S21≤CR21

min{D22, AR22}≤S22≤CR22

min{D23, AR23}≤S23≤CR23

min{D24, AR24}≤S24≤CR24

S21+S22+S23+S24≤CR2

S1+S3+S4+S5+S6+S21+S22+S23+S24≤CRroot

A token bucket corresponds to an inequality, the number of leaf nodes is L, and the number of internal nodes is K. The constraints of the prior art are (L+K) inequalities, and (L+K) token buckets are required. This application is approved L inequalities represent, therefore, this application needs L token buckets, and the parameter of the normalized token bucket is defined as Mi, through the iterative calculation of the above objective function and existing constraints, the following L inequalities of this application can be obtained:

S1≤M1

S3≤M3

S4≤M4

S5≤M5

S6≤M6

S21≤M21

S22≤M22

S23≤M23

S24≤M24

Based on the above theoretical basis, the embodiment of the present invention can realize the normalization of multi-level token buckets to the token buckets on the leaf nodes.

This application separates the message sending process from the bandwidth allocation process. According to the historical message receiving situation, the bandwidth is allocated to the leaf nodes, and the speed limit operation is performed according to the allocated bandwidth during the message sending process, without the need to visit the parent node during the message sending process. Therefore, no node jumping and The data maintenance of the parent node does not require memory switching and memory locking, thereby simplifying the message scheduling process and improving message scheduling efficiency.

FIG. 2 is a schematic diagram of a traffic scheduling architecture provided by the present application, which includes: enqueue interface, receiving queue 0, receiving queue 1, receiving queue 2, classifier 0, classifier 1, classifier 2, receiving queue 01, Receiving queue 02 and receiving queue 03, receiving queue 11, receiving queue 12 and receiving queue 13, receiving queue 21, receiving queue 22, receiving queue 23, sending queue and dequeue interface, wherein, the enqueue interface is for example a network card for receiving The interface of the message, the dequeue interface is, for example, the interface used by the network card to send the message, and all queues are set in the memory of the physical server. Fig. 3 is a schematic diagram of a tree structure corresponding to the traffic scheduling architecture shown in Fig. 2, as shown in Fig. 3, wherein, the enqueue interface corresponds to the root node Root, and receiving queue 0, receiving queue 1, and receiving queue 2 correspond to the child nodes of the root node. Nodes, receiving queue 01, receiving queue 02, receiving queue 03, receiving queue 11, receiving queue 12, receiving queue 13, receiving queue 21, receiving queue 22, and receiving queue 23 correspond to leaf nodes.

After the enqueuing interface receives the message, it is assigned to receiving queue 0, receiving queue 1 or receiving queue 2 through distributed hashing, and the classifier (including classifier 0, classifier 1 or classifier 2) receives the message from receiving queue 0, Obtain the messages to be processed in the receiving queue 1 or receiving queue 2, and perform classification enqueue operations according to the classification attributes of the messages (that is, write the messages to receiving queue 01, receiving queue 02, receiving queue 03, receiving queue 11, receiving queue 12 and receiving queue 13, receiving queue 21, receiving queue 22 or receiving queue 23); in the process of enqueuing operation, the traffic scheduling device in the embodiment of the present invention can measure the load situation of each receiving queue, for example: queue Length, queue packet arrival rate, classification attributes and other information.

Wherein, the classifier can classify and enter the queue according to the classification attribute of the message, and the classification attribute can include: message destination IP address, message destination port, virtual local area network identification (Virtual Local Area Network Identify, VLAN ID) of the message, message Text source IP address, packet source port, packet type, billing information, and tenant reputation.

The VLAN ID of the message can be used to identify different tenants of the cloud network, and different tenants can have different billing information and tenant reputation, and the billing information and tenant reputation can be preset through the cloud platform.

The classifier may send the classification attributes to the traffic dispatcher.

The traffic scheduling device provides rate limit configuration information to the classifier, wherein the rate limit configuration information includes the allocated bandwidth of the queue, and the classifier limits the rate of the corresponding receiving queue according to the allocated bandwidth.

The classifier performs operations such as queue selection and packet dequeue. Specifically, the classifier performs a weighted round-robin operation from the non-empty queue list according to the queue priority, queue weight and other information, selects a queue from the non-empty queue, and then operates according to the allocated bandwidth and speed limit of the queue Relevant parameters determine whether the queue can be dequeued. If the dequeue operation can be performed, the message is read from the memory and processed. If the dequeue operation cannot be performed, the next queue is selected until the number of attempts reaches the maximum limit.

After the packet dequeue operation is completed, the classifier transmits control information to the traffic scheduling device, which includes but is not limited to the number of the empty queue, the number of the queue with insufficient speed (the queue number that is not empty but cannot perform the outbound operation), etc.

The traffic scheduling device summarizes the queue information given by the classifier, thereby obtaining information such as the queue length (including empty queue and full queue), message arrival rate and message sending rate of each queue, and calculates according to the pre-configured bandwidth allocation Rule, recalculate the due bandwidth of some queues or all queues, and send the due bandwidth to the relevant module (not shown in Figure 2) used to control the dequeue operation of messages in the receiving queue to perform message dequeue speed limit.

The process of calculating the bandwidth allocation from the message arrival rate measured by the classification scheduling receiving module is as follows:

To simplify the description of the calculation process, it is assumed that all queues have the same priority. Number each node in the tree structure (as shown in FIG. 4 ). Figure 4 is a schematic diagram of a tree structure provided by this application, the root node number is 0, and the child nodes of the root node are numbered (0,1), (0,2)...(0,N), (0,1 )'s child nodes are numbered (0,1,1), (0,1,2)... In this way, the node number can determine the parent node of the node and the depth of the node. Any node (0,x ₁ ,....,x _n ) has AR and CR respectively recorded as AR(0,x ₁ ,....,x _n ), CR(0,x ₁ ,.... ,x _n ); record the required bandwidth of this node as d'(0,x ₁ ,x ₂ ,…,x _n ), and the effective required bandwidth as d(0,x ₁ ,x ₂ ,…,x _n ), should The obtained bandwidth is s(0,x ₁ ,x ₂ ,…,x _n ).

First, update the effective required bandwidth from the leaf node upwards, and then perform the due bandwidth calculation update downward from the root node.

When updating and calculating the effective required bandwidth, the required bandwidth of the leaf node is the measurement result of the classification scheduling packet receiving module, the required bandwidth of the internal node is the sum of the effective required bandwidth of its child nodes; the minimum between the required bandwidth of the node and the maximum bandwidth The value is the effective demand bandwidth of the node. Calculated as follows:

d(0,x ₁ ,x ₂ ,…,x _n )=min{d’(0,x ₁ ,x ₂ ,…,x _n ),CR(0,x ₁ ,x ₂ ,…,x _n ) }

According to this formula, the effective demand from the leaf node up to the root node is calculated. This update scheme relies on the effective required bandwidth of the child node to calculate the effective required bandwidth of the parent node without going through the measurement module (such as: token bucket)

Measures the effective demand bandwidth of the parent node.

Calculate the due bandwidth of each node from the root node down according to the calculation result of the effective demand. The bandwidth (total bandwidth) of the root node is pre-configured information, and other nodes calculate according to the relationship between the effective demand and the deserved bandwidth. If the effective demand of the node does not exceed the guaranteed bandwidth of the node or the total demand of the parent node of the node does not exceed the allocated bandwidth of the parent node, the due bandwidth allocated to the node is its effective required bandwidth; otherwise, sufficient bandwidth (guaranteed bandwidth and After the smaller value of the effective demand bandwidth), the remaining bandwidth is allocated among nodes that need to borrow bandwidth. The mathematical expression calculation formula is as follows:

S(0) = configuration information

d _e (0,x ₁ ,…,x _n )=max{d(0,x ₁ ,x ₂ ,…,x _n )-AR(0,x ₁ ,x ₂ ,…,x _n ),0}

d”(0,x ₁ ,x ₂ ,…,x _n-1 )=∑ _i=1,2,…k d _e (0,x ₁ ,x ₂ ,…,x _n-1 ,i)k is The number of child nodes of this node Others According to the above calculation formula, the bandwidth resource can be accurately allocated to each node.

and it can be derived that:

Suppose queue i is a leaf node.

according to Obtain the shared bandwidth, where R is the shared bandwidth, AR(i) is the guaranteed bandwidth of queue i, d(i) is the traffic arrival rate of queue i, min(a, b) returns the smaller value among a and b , k is the number of leaf nodes.

according to (if d(i)>AR(i), p _i =1, otherwise, p _i =0, wherein, w _i is the weight of queue i) to obtain additional bandwidth, where e(i) is the additional bandwidth of queue i .

For ease of description, please refer to FIG. 5. FIG. 5 is a schematic flowchart of a traffic scheduling method provided by the present application, as shown in FIG. 5, wherein S501-S505 are executed by the traffic scheduling device in FIG. as follows:

S501: Obtain the weight of the first receiving queue according to the classification attribute of the first receiving queue.

Wherein, the first receiving queue corresponds to any leaf node of the hierarchical token bucket HTB.

Optionally, classification attributes may include billing information and tenant reputation. The weight corresponding to the first receiving queue can be obtained by calculating the billing information and tenant reputation. For example: by weighting the billing information and tenant reputation, the weight corresponding to the first receiving queue can be obtained. The weighted average method can be, for example: A=x*B+y*C, where A is the weight and B is the billing information, C is the tenant reputation, x is the normalization coefficient of billing information, y is the normalization coefficient of the tenant reputation, the normalization coefficient x is used to ensure that the result of x*B is within a certain value range, The normalization coefficient y is used to ensure that the result of y*C is within a certain value range, and x and y can be set according to actual needs.

Optionally, some or all of the attributes in the classification attribute can be obtained by measuring the first receiving queue, for example: a measurement module can be added to the packet header and payload of the packet in the packet enqueuing operation Measurement.

When determining the weight corresponding to the first receiving queue, some or all attributes of the classification attributes may be considered, which is not limited in this application.

Since some or all of the attributes in the classification attributes are related to the operation of the first receiving queue, when some or all of the attributes in the classification attributes change, the weight of the first receiving queue may also change accordingly .

S502: Obtain the traffic arrival rate of the first receiving queue according to the historical packet receiving status and weight of the first receiving queue.

Wherein, the historical packet receiving status of the first receiving queue can be obtained by measurement or by other methods, which is not limited in this application.

Obtaining the traffic arrival rate of the first receiving queue includes but is not limited to the following possible implementations:

One possible implementation:

The number of received packets within a period of time can be obtained by direct measurement, and the average traffic arrival rate of the first receiving queue can be obtained according to the ratio of the number of packets received within a period of time to a period of time ;

The traffic arrival rate of the first receiving queue is obtained by multiplying the average traffic arrival rate of the first receiving queue by the weight of the first receiving queue.

For example: Assume that queue i is the first receiving queue, and the number of packets received by queue i within ΔT within a period of time is B _i , then the average traffic arrival rate of queue i Obtained by the following formula:

The traffic arrival rate d(t) of queue i is obtained by the following formula:

Among them, w _i is the weight of queue i.

This situation is suitable for the situation that the queue i is empty before ΔT, and the influence of historical data on the present can be ignored at this time.

Another possible implementation:

The first number of packets received by the first receiving queue at the first time point and the second number of packets received by the first receiving queue at the second time point can be obtained by direct measurement. Obtain the message quantity difference between the first message quantity and the second message quantity by calculation, and obtain the time difference between the second time point and the first time point, according to the message quantity difference, time difference and The weight of the first receiving queue and the traffic arrival rate of the first receiving queue at the first time point are used to obtain the traffic arrival rate of the first receiving queue at the second time point.

Optionally, the ratio of the packet quantity difference to the time difference is obtained as the average traffic arrival rate, and the traffic arrival rate of the first receiving queue is obtained according to the weight and the average traffic arrival rate. For example: the traffic arrival rate of the first receiving queue can be obtained by multiplying the weight and the average traffic arrival rate.

For example: assume that queue i is the first receiving queue, the total number of messages received by queue i at time t is B _i (t), and the total number of messages received at time t+ΔT is B _i (t+ΔT), B _i (t+ΔT)-B _i (t) is the number of packets received within the ΔT time period, and the average traffic arrival rate of queue i Obtained by the following formula:

The traffic arrival rate d(t+ΔT) of queue i at time t+ΔT is obtained by the following formula:

Among them, w _i is the weight of queue i, α(0<α<1) represents the weight coefficient of d(t+ΔT) at time t+ΔT to the historical measurement value d(t) at time t, and its value The closer to 1, the lower the weight dependence on past measurement values, which determines the ability of EWMA to track sudden changes in actual data.

The measurement method in this embodiment refers to the exponentially weighted moving average (Exponentially Weighted Moving Average, EWMA) algorithm, EWMA is a kind of commonly used sequence data exponentially weighted moving average processing method (sliding window method in the network), at time t , according to the actual observed value (or measured value), the estimated value EWMA(t) at time t can be calculated:

EWMA(t)=λ*Y(t)+(1-λ)*EWMA(t-1), t=1`,2,...n

Among them, Y(t) is the measured value at time t, n is the number of observed values, λ(0<λ<1) represents the weight coefficient of EWMA for historical measured values, and the closer the value is to 1, the greater the weight of past measured values The weight dependence is low, which determines the ability of EWMA to track sudden changes in actual data, and its instantaneity.

That is, the traffic arrival rate of the first receiving queue can be obtained according to the historical measurement results of the first receiving queue at the first moment and the measurement results at the second moment.

S503: Obtain additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight.

Among them, a possible implementation:

Select the smaller value of the guaranteed bandwidth and traffic arrival rate of the receiving queue corresponding to the leaf node of HTB as the candidate bandwidth of the receiving queue corresponding to the leaf node, and accumulate the candidate bandwidth of each leaf node to obtain the cumulative value of the candidate bandwidth. The difference between the total bandwidth of the HTB minus the cumulative value of the candidate bandwidth, and use the difference as the shared bandwidth, obtain the sum of the weights of all leaf nodes that require additional bandwidth, obtain the weight of the first receive queue and the second sum The ratio of values according to which the extra bandwidth of the first receive queue is obtained from the shared bandwidth.

This method is expressed through a mathematical formula as follows:

according to Obtain the shared bandwidth, where R is the shared bandwidth, AR(i) is the guaranteed bandwidth of queue i, d(i) is the traffic arrival rate of queue i, min(a, b) returns the smaller value among a and b , k is the number of leaf nodes, a=one of AR(i) and d(i), b=the other of AR(i) and d(i).

Wherein, d(i) is d(t+ΔT) indicated above, and d(i) is the traffic arrival rate of queue i at time t+ΔT.

according to (if d(i)>AR(i), p _i =1, otherwise, p _i =0, wherein, w _i is the weight of queue i) to obtain additional bandwidth, where e(i) is the additional bandwidth of queue i .

S504: Acquire the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and extra bandwidth of the first receiving queue.

Among them, a possible implementation method: obtain the allocated bandwidth of the first receiving queue according to the sum of the smaller value of the traffic arrival rate and the guaranteed bandwidth and the extra bandwidth.

For example: assuming that the first receiving queue is queue i, the allocated bandwidth of the first receiving queue is obtained according to min{AR(i), d(i)}+e(i).

Another possible implementation manner: obtain the allocated bandwidth of the first receiving queue according to the sum of the traffic arrival rate and the guaranteed bandwidth, the sum of the additional bandwidth and the allowed burst rate.

For example: Assuming that the first receiving queue is queue i, according to min{AR(i), d(i)}+e(i)+Burst, the allocated bandwidth of the first receiving queue is obtained. Among them, Burst is the allowed burst rate, and Burst is used to ensure that the queue can support a sudden increase in the number of packets under special circumstances.

In the bandwidth allocation process of S501-S504, the bandwidth allocation of the receiving queue corresponding to one of the leaf nodes is described as an example, and the bandwidth allocation of the receiving queues corresponding to the other leaf nodes is similar, and this application will not repeat them one by one.

Bandwidth allocation is performed on the receiving queue corresponding to a leaf node, that is, according to the message receiving status and weight of the receiving queue corresponding to all leaf nodes, the traffic arrival rate of the receiving queue corresponding to each leaf node is estimated, and according to the corresponding The traffic arrival rate, guaranteed bandwidth, and weight of the receiving queue can be used to allocate bandwidth to a leaf node.

S505: Perform a speed limit operation according to the allocated bandwidth.

Specifically, a token rate of the first receiving queue is set according to the allocated bandwidth, and a speed limit operation is performed on dequeue operations of messages in the first receiving queue according to the token rate.

One possible implementation:

Obtain the relevant parameters of the speed limit operation, and perform the speed limit operation according to the allocated bandwidth and the relevant parameters of the speed limit operation.

Among them, the parameters related to the speed limit operation include but are not limited to at least one of the following:

The bandwidth rate allowed for bursts in packet forwarding, the maximum rate limit, and the processing method for packets exceeding the maximum rate limit. In this embodiment, the existing HTB tree is used to manage the receiving queue, but the token bucket of the HTB tree is not used for bandwidth borrowing, but the weight of the first receiving queue is obtained according to the classification attribute of the first receiving queue, according to According to the historical message receiving status and weight of the first receiving queue, obtain the traffic arrival rate of the first receiving queue, obtain the additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight, and obtain the traffic arrival rate and guarantee of the first receiving queue according to the weight Bandwidth and additional bandwidth, obtain the allocated bandwidth of the first receiving queue, and perform speed limit operation according to the allocated bandwidth, that is, in the process of bandwidth allocation, bandwidth allocation can be performed without visiting the parent node, so there is no need for node jumping and The data maintenance of the parent node avoids memory switching and memory locking, improves bandwidth allocation efficiency, simplifies the message scheduling process, improves message scheduling efficiency, and reduces message processing delay.

FIG. 6 shows a schematic diagram of the system structure of the traffic scheduling system of the embodiment of the present invention. The embodiment of the present invention can be applied to an open source data plane development kit (Data Plane Development Kit, DPDK) platform to redesign the QoS module to realize the bandwidth of HTB distribution principle. As shown in Figure 6, in the DPDK framework, the traffic scheduling system involved in this implementation includes network cards, CPU cores 1-4, and memory, wherein CPU3 runs the packet receiving function and the packet sending function, and both CPU1 and CPU2 run the enqueue function and Out of the queue function, CPU4 implements the above-mentioned traffic scheduling device, the packet receiving function can be realized by the DPDK packet receiving function (rte_eal_rx_burst), the packet sending function can be realized by the DPDK packet sending function (rte_eal_tx_burst), and the queue entry function includes: Classifier (Classifier) implementation function , the rate measurement (sensor) function and the DPDK lock-free ring queue enqueue function (rte_ring_enqueue), the dequeue function includes: DPDK lock-free ring queue dequeue function (rte_ring_dequeue) and the control dequeue operation module (actioner), the receiving queue and Send queues are set up in memory. In order to improve the operating efficiency of the multi-core platform, the above functional functions and traffic scheduling devices are bound to the CPU cores, and the scheduling of threads between multiple cores is omitted.

FIG. 7 is a schematic structural diagram of an embodiment of a traffic scheduling device provided by the present application. The device in this embodiment includes: an acquisition module 901 and a processing module 902. In this embodiment, the acquisition module 901 is used to classify according to the first receiving queue The attribute acquires the weight of the first receiving queue, wherein the first receiving queue corresponds to any leaf node of the hierarchical token bucket HTB; the acquiring module 901 is also configured to According to the packet receiving situation and the weight, the traffic arrival rate of the first receiving queue is obtained; the obtaining module 901 is further configured to obtain the additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight The obtaining module 901 is also used to obtain the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue; the control module 901 is used to obtain the allocated bandwidth according to the allocated bandwidth Perform speed limit operation.

Optionally, the classification attributes include charging information and tenant reputation, and the obtaining module 901 is specifically configured to perform weighted average on the charging information and the tenant reputation to obtain the weight.

Optionally, the historical packet reception conditions include the number of first packets received by the first receiving queue at a first time point and the number of second packets received by the first receiving queue at a second time point quantity;

The acquiring module 901 is specifically configured to acquire a message quantity difference between the second message quantity and the first message quantity; acquire a time difference between the second time point and the first time point; Obtain the traffic arrival rate of the first receiving queue according to the packet quantity difference, the time difference, and the weight of the first receiving queue.

Optionally, the obtaining module 901 is specifically configured to obtain a ratio of the packet quantity difference to the time difference, and use the ratio as an average traffic arrival rate; according to the weight and the average traffic arrival rate , to obtain the traffic arrival rate of the first receiving queue.

Optionally, the acquisition module 901 is specifically configured to select the smaller value of the guaranteed bandwidth and traffic arrival rate of the receiving queue corresponding to the leaf node of the HTB as the candidate bandwidth of the receiving queue corresponding to the leaf node; Accumulate the candidate bandwidth of the leaf node to obtain the cumulative value of the candidate bandwidth; obtain the difference between the total bandwidth and the cumulative value of the candidate bandwidth as the shared bandwidth; Ratio and the shared bandwidth to obtain the additional bandwidth of the first receive queue.

Optionally, the obtaining module 901 is specifically configured to obtain the allocated bandwidth of the first receiving queue according to the sum of the smaller value of the traffic arrival rate and the guaranteed bandwidth and the additional bandwidth.

Optionally, the obtaining module 901 is specifically configured to obtain the first received traffic according to a smaller value of the traffic arrival rate and the guaranteed bandwidth, the additional bandwidth, and a bandwidth rate that allows bursts. The allocated bandwidth of the queue.

The device of this embodiment can be used to implement the technical solution of the method embodiment shown in Figure 5 correspondingly, and its implementation principle and technical effect are similar, and will not be repeated here.

The present application also provides a computer device, including: a storage unit for storing instructions; and at least one processor coupled to the storage unit; wherein, when the at least one processor executes the instructions, the The instructions cause the processor to perform the method described in FIG. 5 .

Refer to FIG. 8 for details. FIG. 8 is a schematic structural diagram of a computer device according to an embodiment of the present invention. In FIG. 8 , the computer device may include a processing unit 201 and a communication interface 202, and the processing unit 201 is used to perform operations running on the computer device The functions defined by the system and various software programs, for example, the functions of the above-mentioned flow scheduling device. The communication interface 202 is used to communicate and interact with other computing nodes, and other devices may be other physical servers, specifically, the communication interface 202 may be a network card. Optionally, the computer device may also include an input/output interface 203, and the input/output interface 203 is connected with an input/output device for receiving input information and outputting operation results. The input/output interface 203 can be a mouse, a keyboard, a monitor, or an optical drive. Optionally, the computer device may further include an auxiliary storage 204, generally also called external storage, and the storage medium of the auxiliary storage 204 may be a magnetic medium (for example, a floppy disk, a hard disk, or a magnetic tape), an optical medium (such as an optical disk), or a semiconductor media (such as solid-state drives), etc. The processing unit 201 may have multiple specific implementation forms. For example, the processing unit 201 may include a processor 2011 and a memory 2012. The processor 2011 performs related operations according to the program unit stored in the memory 2012. The processor 2011 may be a central processing unit (CPU) ) or an image processor (English: graphics processing unit, GPU), the processor 2011 may be a single-core processor or a multi-core processor. The processing unit 201 can also be implemented solely by a logic device with built-in processing logic, such as a field programmable gate array (English full name: Field Programmable Gate Array, abbreviation: FPGA) or a digital signal processor (English: digital signal processor, DSP), etc. .

The present application also provides a computer-readable storage medium, which is used to store a computer program, and the computer program is used to implement the method described in FIG. 5 .

In the several embodiments provided in this application, it should be understood that the disclosed systems, devices and methods can be implemented in other ways. For example, the device embodiments described above are only illustrative. For example, the division of the units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components can be combined or May be integrated into another system, or some features may be ignored, or not implemented. In addition, the mutual coupling or direct coupling or communication connection shown or discussed may be indirect coupling or communication connection through some interfaces, devices or units, and may also be electrical, mechanical or other forms of connection.

Claims (16)

1. A flow scheduling method, characterized in that, comprising: Acquiring the weight of the first receiving queue according to the classification attribute of the first receiving queue, wherein the first receiving queue corresponds to any leaf node of the hierarchical token bucket HTB; Acquiring the traffic arrival rate of the first receiving queue according to the historical packet receiving situation of the first receiving queue and the weight; acquiring the additional bandwidth of the first receive queue from the total bandwidth of the HTB according to the weight; Acquiring the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue; The rate limiting operation is performed according to the allocated bandwidth. 2. The method according to claim 1, wherein the classification attribute includes billing information and tenant reputation, and obtaining the weight of the first receiving queue according to the classification attribute of the first receiving queue includes: Performing a weighted average on the billing information and the tenant reputation to obtain the weight. 3. The method according to claim 1 or 2, characterized in that, the historical packet reception conditions include the number of first packets received by the first receiving queue at the first time point and the number of first packets received by the first receiving queue. The number of second packets received by the queue at the second time point; The obtaining the traffic arrival rate of the first receiving queue according to the historical message receiving situation of the first receiving queue and the weight includes: Acquiring a difference in the number of messages between the second number of messages and the first number of messages; Acquiring a time difference between the second time point and the first time point; Obtain the traffic arrival rate of the first receiving queue according to the packet quantity difference, the time difference, and the weight of the first receiving queue. 4. The method according to claim 3, wherein the flow rate of the first receiving queue is acquired according to the message quantity difference, the time difference and the weight of the first receiving queue Arrival rate, including: Obtain the ratio of the packet quantity difference to the time difference, and use the ratio as the average traffic arrival rate; Acquiring the traffic arrival rate of the first receiving queue according to the weight and the average traffic arrival rate. 5. The method according to any one of claims 1 to 3, wherein the obtaining the additional bandwidth of the first receive queue from the total bandwidth of the HTB according to the weight comprises: Selecting the smaller value of the guaranteed bandwidth and traffic arrival rate of the receiving queue corresponding to the leaf node of the HTB as the candidate bandwidth of the receiving queue corresponding to the leaf node; Accumulate the candidate bandwidth of each leaf node to obtain the candidate bandwidth accumulation value; Obtaining the difference between the total bandwidth and the accumulated value of the candidate bandwidth as the shared bandwidth; Acquiring the extra bandwidth of the first receiving queue according to the ratio of the weight to the sum of the weights of all leaf nodes requiring extra bandwidth and the shared bandwidth. 6. The method according to any one of claims 1 to 4, characterized in that, according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue, the information of the first receiving queue is obtained. Allocate bandwidth, including: The allocated bandwidth of the first receiving queue is obtained according to the sum of the smaller value of the traffic arrival rate and the guaranteed bandwidth and the additional bandwidth. 7. The method according to any one of claims 1 to 4, wherein the allocated bandwidth of the first receiving queue is obtained according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue ,include: The allocated bandwidth of the first receiving queue is obtained according to a smaller value of the traffic arrival rate and the guaranteed bandwidth, the additional bandwidth, and a bandwidth rate allowed to burst. 8. A flow scheduling device, characterized in that it comprises: An obtaining module, configured to obtain the weight of the first receiving queue according to the classification attribute of the first receiving queue, wherein the first receiving queue corresponds to any leaf node of the hierarchical token bucket HTB; The acquiring module is further configured to acquire the traffic arrival rate of the first receiving queue according to the historical message receiving situation of the first receiving queue and the weight; The obtaining module is further configured to obtain the additional bandwidth of the first receiving queue from the total bandwidth of the HTB according to the weight; The obtaining module is further configured to obtain the allocated bandwidth of the first receiving queue according to the traffic arrival rate, guaranteed bandwidth and the additional bandwidth of the first receiving queue; A control module, configured to perform a speed limit operation according to the allocated bandwidth. 9. The device according to claim 8, wherein the classification attributes include billing information and tenant reputation, and the acquisition module is specifically configured to perform a weighted average on the billing information and the tenant reputation , to get the weights. 10. The device according to claim 8 or 9, characterized in that, the historical packet reception conditions include the number of first packets received by the first receiving queue at the first time point and the number of first packets received by the first receiving queue. The number of second packets received by the queue at the second time point; The obtaining module is specifically configured to obtain a difference in the number of messages between the second number of messages and the first number of messages; obtain a time difference between the second time point and the first time point; according to The packet quantity difference, the time difference, and the weight of the first receiving queue obtain the traffic arrival rate of the first receiving queue. 11. The device according to claim 10, wherein the acquiring module is specifically configured to acquire the ratio of the message quantity difference to the time difference, and use the ratio as the average traffic arrival rate; according to The weight and the average traffic arrival rate are used to obtain the traffic arrival rate of the first receiving queue. 12. The device according to any one of claims 8 to 11, wherein the acquisition module is specifically configured to select the smaller value of the guaranteed bandwidth and traffic arrival rate of the receiving queue corresponding to the leaf node of the HTB As the candidate bandwidth of the leaf node corresponding to the receiving queue; accumulate the candidate bandwidth of each leaf node to obtain the candidate bandwidth cumulative value; obtain the difference between the total bandwidth and the candidate bandwidth cumulative value as the shared bandwidth; according to the The ratio of the weight to the sum of the weights of all leaf nodes requiring additional bandwidth and the shared bandwidth is used to obtain the additional bandwidth of the first receiving queue. 13. The device according to any one of claims 8 to 12, wherein the acquisition module is specifically configured to calculate the additional bandwidth according to the sum of the traffic arrival rate and the guaranteed bandwidth and the smaller value value to obtain the allocated bandwidth of the first receive queue. 14. The device according to any one of claims 8 to 12, wherein the obtaining module is specifically configured to use the smaller value of the traffic arrival rate and the guaranteed bandwidth, the additional bandwidth, and the allowed The sum of the bandwidth rates of the bursts is used to obtain the allocated bandwidth of the first receiving queue. 15. A computer device, characterized in that it comprises: a storage unit for storing instructions; and at least one processor coupled to the storage unit; Wherein, when the at least one processor executes the instruction, the instruction causes the processor to execute the method according to any one of claims 1-7. 16. A computer-readable storage medium, wherein the storage medium is used to store a computer program, and the computer program is used to implement the method according to any one of claims 1-7.