System flow control method
Technical Field
The present technology belongs to the technical field of Quality of Service (QoS) for data communication, and particularly relates to a technique for implementing system flow control in Differentiated Service (Diffserv).
Background
In the data network of today, as the trend of network evolution of triple play (voice, video, data) is further deepened and the de facto standard of TCP/IP network technology is established, providing service quality on the original best effort data network is more and more urgent for operators to demand IP network equipment. The IP network device is to distinguish voice, video and data services, and provide different forwarding qualities according to the characteristics of these different services, which becomes an important research subject of IP QoS. Meanwhile, because network resources are limited, management and utilization of network resources are important in network planning and operation management, and are also important in the research subject of QoS. Network resources (cache, bandwidth) are limited, and data network traffic is random and bursty, so that congestion inevitably occurs in the network. The congestion management (congestion avoidance and congestion control) of ip qos requires that network devices can provide a mechanism under which the system can have a higher throughput rate (resource utilization rate), and can distinguish traffic classes under the condition that the system is overloaded with resources, and perform different actions on messages of different priority levels, thereby ensuring that the forwarding of traffic of high priority levels is not affected. The WRED (Weighted Random Early Discard) method is a common congestion management approach.
WRED (Weighted Random Early Discard) discards according to the linear Discard curve: at the timing of the control plane system, for example, weighted statistics of idle resources (generally buffer queue resources) are performed every t time interval periods:
queue(t)=queue(t)+(1-w)queue(t′)
where queue (t) represents the free queue length at time t, queue (t') represents the free queue length at the previous time, and W is a weighting factor between [0, 1 ].
The congestion degree of the system in the time slot is determined according to the weighted statistic value, and the Discard probability of forwarding in the time slot T is determined according to the congestion degree, i.e. the DPT (Discard probability Table) is refreshed. The flow control curve derived by the WRED method is shown in fig. 1, in the graph, the ordinate is the discarding probability, the value range [0, 1], and the maximum discarding probability value of the discarding probability diagonal line on the graph is maxp; the abscissa is the free queue length, above which the minimum free queue threshold (minq) value and the maximum free queue threshold (maxq) value of the slash correspond.
And in the forwarding plane, whether the reached message is forwarded or discarded is determined according to the current discarding probability.
The general system realizes the effect of regulating congestion control by fine adjustment of time interval t and weighting primer w, and meanwhile, in a Diffserv (Differentiated services) QoS model, the flow control curves of different Service classes are different, that is, under the same queue congestion degree, the probability of discarding a message with a high priority level is small, and the probability of discarding a message with a low priority level is large, so as to ensure different Service levels.
Most of the existing devices implement a basic WRED method, i.e., a 0, 1 model shown in fig. 1, when the length of an idle queue is smaller than a lower limit value, 100% of the idle queue is discarded, and when the length of the idle queue is larger than an upper limit value, 100% of the idle queue is forwarded. The model can work well on low-speed equipment through the configuration of w, t and the upper limit value of the lower limit value of the idle queue. However, for high-speed network devices, such as GSR (Gigabit Switch Route Gigabit) and TSR (Trilbit Switch Route Gigabit) because the interface link rate is greatly increased but the buffer amount is limited, the 0/1 model and the congestion management of the system by w/t adjustment cannot be well performed, because when a large burst is continuously overloaded, the system buffer will be exhausted in a short time and the system will reach 100% drop point quickly; due to the fact that the exchange and forwarding rates are improved, the cache can be emptied quickly, the system can reach 100% of forwarding points quickly, and the forwarding probability is frequently fluctuated between 0 and 1 repeatedly, so that the queue utilization rate is greatly fluctuated, and the cumulative throughput rate of a link is low.
Meanwhile, in a Diffserv (Differentiated services) QoS model, although different Service types can be distinguished and different flow Control curves are designed, not all message types are sensitive to discard, and for a transmission layer protocol with built-in flow Control, such as tcp (transport Control protocol), packet loss can be responded, so that the effect of back pressure is achieved, and a connectionless transmission layer protocol, such as UDP, does not respond to packet loss, so that the model range has certain limitation on the message types.
Disclosure of Invention
The invention aims to overcome the defects of the prior art that the message type is limited to a certain extent and the system flow control is not ideal, and provides a system flow control method which can improve the throughput rate and the flow control effect of the system during overload in a flow model in high-end equipment; meanwhile, different flow control curve configurations can be carried out according to different message types, and a more optimal flow control effect is achieved.
The invention provides a system flow control method, which comprises two parts of processing when a system is initialized and processing a message reaching equipment at a certain moment; wherein,
the processing steps during system initialization are as follows: calculating a discretized discarding probability table according to flow control parameters of different priority levels and different message types configured by a user;
the processing of a message arriving at a device at a time comprises the following steps:
calculating the final comprehensive average idle queue length;
searching the discarding probability table according to the final comprehensive average idle queue length and the message type to obtain the transmission probability of the message at the time interval;
comparing the transmission probability of the message with the random number generated currently, and if the transmission probability is smaller than the random number, discarding the message; otherwise, the message is forwarded.
The flow control parameters of the different types of messages may include: a minimum discard free queue threshold, a maximum discard probability.
The processing steps during system initialization may further include: and adjusting flow control parameters of messages with different priority levels and different types, and discretizing the level of the discarding probability table.
The calculating the final composite average free queue length may include the steps of:
calculating the arrival rate of the messages in a certain time interval;
calculating the average queue length of the idle queue at the moment through a weighted random early discard formula;
the average idle queue length synthesized at the moment is the product of the average queue length of the idle queue, the message arrival rate and the adjustment factor;
the final composite average free queue length may be a difference between the average queue length of the free queue and the composite average free queue length.
The calculating of the rate of arrival of the messages within a certain time interval may comprise the steps of:
dividing the count of the message reached in the time interval by the time interval;
then discretizing the calculation result value into several intervals according to the capacity of the system;
mapping the discretized interval into a [0, 1] interval.
The discard probability table may be a three-dimensional array composed of message grades, message types, and final integrated idle queue length, and the step of calculating the discretization discard probability table may be:
obtaining a corresponding discarding probability curve according to the minimum discarding idle queue threshold, the maximum discarding idle queue threshold and the maximum discarding probability of the flow control parameters of the message;
and dividing the minimum discarded idle queue threshold to the maximum discarded idle queue threshold of the discarded probability curve according to the discretization grade number, wherein the average value of the discarded probabilities corresponding to each divided interval is the discarded probability of the message when the idle queue length is in the interval.
The invention has the characteristics that:
(1) the invention takes Packet Arrival Rate (Packet Arrival Rate) of the stream as a control factor to calculate the discarding probability. By introducing the factor, the dropping probability of forwarding can be dynamically adjusted according to the input rate of the flow and on the basis of determining the dropping probability according to the average queue originally, so that a better system flow control effect is achieved.
(2) The existing WRED method will discard 100% when the average queue depth reaches a certain threshold. For high-end equipment of line-speed forwarding, when the system is not congested (line-speed forwarding), only a small amount of system cache is needed, and once the line-speed forwarding capacity is exceeded, the system can quickly congest to reach the lowest threshold of the system cache, so that the queue utilization rate presented by the system has large jitter, and the cumulative throughput rate of a link is also low. Therefore, the invention carries out optimization calculation on the maximum discarding probability when the network is congested aiming at messages with different flow control levels and discarding levels, and the maximum discarding probability is less than 1, so that the system has better throughput rate when being overloaded.
(3) The invention carries out different flow control parameter (grade, category and granularity grade) configuration on four types of messages (TCP SYN message, TCP message, UDP message and other IP message) to obtain different flow control curves so as to achieve better flow control effect.
(4) The experimental simulation and the actual operation of the method show that under the condition that the network is changed violently or the network has larger overload, the system adopting the method has higher queue utilization rate and system accumulated throughput than the prior method.
Drawings
Fig. 1 is a graph of a conventional weighted random early drop flow control.
Fig. 2 is a schematic diagram illustrating a discretization principle of a weighted random early drop fluidics curve.
Fig. 3 is a graph of weighted random early discard flow control after optimization by the method of the present invention.
Detailed Description
The embodiment of the system flow control method provided by the invention is explained in detail as follows:
the embodiment comprises two parts of processing during system initialization and processing of messages reaching equipment at a time t; wherein,
the processing steps during system initialization comprise:
(1) according to the flow control parameters of different priority levels and different types of messages (TCP SYN, other IP, UDP, TCP) configured by a user (or defaulted by a system): performing discretized DPT table calculation on flow control parameters such as a minimum discard idle queue threshold, a maximum discard probability and the like; because the discard probability curve of WRED is an oblique line (as shown in fig. 1), it needs to be represented in a discretized manner as needed in a digital system, the principle is shown in fig. 2, that is, the minimum threshold to the maximum threshold of the idle queue of the oblique line is divided into a plurality of value intervals, and the number of discretized stages can be selectively set according to the system resource condition. Taking the TCP SYN level 1 message and the discretization level 128 as an example, the discretization calculation is performed as follows: the interval [ minq, maxq ] from the minimum threshold to the maximum threshold of the idle queue is divided into 128 equal parts, then the average value of the small inclined line of the interval is calculated in each interval, and the result is the discarding probability of the message when the value of the idle queue falls in the interval.
(2) In practical application, the priority level of system configuration, the numerical value of a message type and the discretization granularity level of a discarding probability table can be adjusted according to actual needs, in the embodiment, a DPT (data processing) table is formed by a three-dimensional array P [ class ] [ type ] [ queue _ depth ] composed of a message level class, a type and an idle queue length queue _ depth, wherein the class level is the forwarding level of the message and is used as an input and represents the discarding priority level of the message, the higher the priority level is, the more the message is not easy to be discarded, and a general system is designed into 4 or 6 priority levels; the type message type is the protocol type carried by the user data, and generally comprises four types of TCP SYN, TCP, UDP and Other IP as described above; the final value of the idle queue length queue _ depth and the discretization series of the idle queue length are in a functional relationship, and the WRED parameters of each CLASS and TYPE, such as the minimum discard idle queue threshold MINTH, the maximum discard idle queue threshold MAXTH and the maximum discard probability MAXP, are configured by a user, and the system can calculate the values of all three-dimensional arrays according to the proportional relationship. .
(3) The maximum discarding probability value can be adjusted according to different types of messages, in this embodiment, the maximum discarding probability of the ef (expected forwarding) message with the highest priority level is adjusted to 0.1 to 0.3; for the message with lower priority, the maximum discarding probability is adjusted to 0.7 to 0.9.
The message processing of the arriving device at time t comprises the following steps:
(1) calculating the rate o (t) of arrival of the message in the time interval from the previous time t ' to t, which can be obtained by dividing the time interval by the count (t) of arrival of the message, i.e. o (t) ═ f (count (t) — count (t ')/(t-t ')); generally, the packet arrival rate is discretized according to the capacity of the system, for example, if the possible packet arrival rate of the system is 0bps (bit per second) to 3Gbps (1G ═ 10^9), the interval can be divided into 8 parts, [0, 375M ] is the interval 0, and so on, …, and [2.625M, 3G ] is the interval 7. Then o (t) takes the function f () of the discretized interval, where the function model in this embodiment is 2^ (x-a), x is the interval index, and a is the number of discretized intervals, i.e., the discretized series, and as above, a is 8.
(2) Calculating the average queue length queue (t) of the idle queue at the moment, wherein the value is calculated by the formula queue (t) + (1-w) queue (t');
(3) and calculating the comprehensive average idle queue length queue (t') at the time t and a discretization interval of the value. The method comprises the following steps: queue (t) o (t) M, where M is an adjustment factor, the adjustment factor M mainly acts to restrict the influence of the message arrival rate o (t) on the final average queue length calculation, and the discretization value interval is [0, 1 ];
(4) calculating the final integrated average free queue length queue _ depth, queue _ depth ═ queue (t) -queue '(t), where queue (t) and queue' (t) are calculated by steps (2) and (3), respectively, and then obtaining the corresponding DPT table index value of the free queue, and the index value calculation method of this embodiment exemplifies: if the free queue length of the system is 128K (1K ^ 10^3) buffer units, discretizing the free queue length into 128 intervals, and if the calculated queue _ depth is 4K, corresponding to the discarding probability is that the array index value of the DPT table is 4;
(5) according to the class of the message, the type of the message and the discretization value of the comprehensive average idle queue length queue _ depth calculated in the step (4), as input, a DPT table is searched, namely the array P [ class ] [ type ] [ queue _ depth ] described above is obtained, so that the transmission probability P (t) of the message is obtained, and the relation between the transmission probability P (t) and the discarding probability is as follows: 1-discarding probability;
(6) comparing the transmission probability of the message obtained in the step (5) with the random number P generated currently, and if P (t) is less than P, discarding the message; if p (t) > ═ p, the message is forwarded.
The optimized flow control curves of different messages obtained by the method of this embodiment are shown in fig. 3.
Wherein: curve 4 is the original WRED curve; the rest, from left to right (curves 1, 2, 3 and 5) are: TCP SYN, other IP, UDP, TCP modified WRED flow control curves. The ordinate is the discarding probability, and the value range [0, 1] is the different value of the maximum discarding probability (maxp) of each curve corresponding to the value range; the abscissa is the length of the free queue, and the minimum free queue threshold (minq) value and the maximum free queue threshold (maxq) value of each curve are corresponding to the length of the free queue.