RU2678404C2 - Method of dispatching of switch queues with service quality maintaining - Google Patents

Abstract

FIELD: physics.SUBSTANCE: invention relates to the field of telecommunications and can be used in switches with support for quality of service to regulate the access of switch queues to the physical channel. Dispatcher determines the number of the queue to be serviced by the cyclic priority, and the amount of data transmitted to the channel from each queue during one service session, determined by the established credit, proportional to the channel bandwidth allocated for the corresponding traffic class. Service session of each queue is divided into separate sub-sessions of a given duration, and at the end of each session, one transfer frame is selected that is selected from all non-empty queues by the criterion of the longest stay in the queue. Subject to the need for further maintenance of the queue in accordance with the established credit, after the transfer of the separation frame, the next sub session of the previously started queue service session is started.EFFECT: technical result is an improvement in the quality of service to regulate access of the switch queues to the physical channel by reducing variations in the traffic jitter values of different classes, allocating the output channel's bandwidth between traffic of different classes and reducing the burst in transmitting traffic of each class.4 cl, 2 dwg

Description

Application area

The invention relates to the field of telecommunications and can be used in switches supporting quality of service to regulate access of switch queues to a physical channel.

State of the art

In network switches with support for quality of service, an important mechanism for ensuring the required traffic promotion parameters is the scheduling of queues of frames sent to each output port, which determines the transmission delay of the frames and its variation (jitter), the values of which are important when transmitting real-time traffic through packet-switched networks. The frames promoted by the switch are marked with traffic class labels, based on which it places the frames in the queues corresponding to the class specified in the label.

The scheduling mechanism consists in the rule for selecting the queue served, as well as the regulation of the output channel bandwidth allocated to each class.

The cyclic scheduling algorithms that solve this problem are known: weighted cyclic (WRR-Weighted Round Robin), weighted deficit cyclic (WDRR-Weighted Deficit Round Robin) (Curly EA Traffic management and quality of service on the Internet - St. Petersburg: Nauka and Tekhnika, 2004) . A feature of these algorithms is the use of cyclic priority when choosing a serviced queue, and the duration of continuous queue servicing is determined by credit (the permissible amount of data read from each queue during its servicing session), the value of which is proportional to the bandwidth allocated for the output channel bandwidth. The disadvantage of the WRR algorithm is the low accuracy of adjusting the bandwidth value due to the job of the loan in frames. The WDRR algorithm, unlike the WRR, provides high accuracy in setting the bandwidth, because credit is specified in bytes, its value must be not less than the maximum frame size. At the same time, the amount of credit for a new service cycle at the end of the next cycle is adjusted (reduced) by the deficit — excess of the loan in the completed service cycle due to the transfer of the last frame (the frame size cannot be reduced).

Both algorithms have a common drawback - the uncontrolled jitter (delay spread) of the switched frames due to the difference in the waiting time of frames in different queues. In addition, the frame delay of a certain class of quality of service, as well as the size of the corresponding queues, depend on the allocated bandwidth for a particular class. This leads to an increase in frame delay and congestion of queues in channels with a small assigned bandwidth with a pulsating nature of the traffic, since the cyclic maintenance algorithms do not allow efficiently redistributing the unused bandwidth of underloaded channels to expand the bandwidth of overloaded ones.

In addition, the continuous transmission in a single session of large portions of traffic data of one class leads to traffic “corruption”, which in turn increases the load on the buffers of subsequent telecommunication devices.

The existing WFQ fair weighted service algorithm (Sh. Vegeshna. Quality of Service in IP Networks - SPB: Williams Publishing House, 2003), which is characterized to a lesser extent by the above disadvantages of cyclic algorithms. However, this algorithm is highly complex and requires significant computing resources, which limits its use in switches. The closest technical solution is US 2005/0141424 A1 “TIME-INDEPENDENT DEFICIT ROUND ROBIN METHOD AND SYSTEM”, which describes a method for scheduling protocol data units (PDUs) from multiple queues, each of which is characterized by a corresponding credit requirement, the method comprising the steps : allocation of credit for each of the many queues; extracting from the queue at least one PDU from one or more queues having an available credit; subtracting the credit requirement of each PDU extracted from the queue from the available credit associated with the queue from which it was extracted; and also replenishment of the loan available for each of the many queues, when the available loan associated with one of the many queues is not enough to withdraw from the PDU queue, and the loan determines the size of the bandwidth associated with the output of the dispatcher.

Technical result

The technical result of the claimed invention consists in improving the quality of service for regulating access of switch queues to a physical channel by reducing variations in traffic jitter of different classes, allocating the output channel bandwidth between traffic of different classes and reducing the burden in transmitting traffic of each class.

Brief Description of the Drawings

In FIG. 1 shows a diagram of the functioning algorithm of the manager of the output port of the switch that implements the proposed queue management algorithm.

In FIG. Figure 2 shows the preferred version of the hardware implementation of the dispatcher, where 1 is a memory of the FIFO type, divided between queues and containing for each queue: frame queue - 2, service marking queue - 3; 4 - scheduling processor; 5 - classifier of incoming frames and channel direct recording into memory; 6 - timer; 7 - channel for direct reading of frames from queues; 8 - physical interface of the output port: 9, 10 - bus write and read from memory; 11 - bus output channel; 12 - bus receiving frames from the equipment for promoting frames in the destination port of the switch; 13 - signal "queue free"; 14 - signal “output port is free”.

DETAILED DESCRIPTION OF THE INVENTION

The implementation of the proposed scheduling algorithm is to perform the following actions:

1. When starting up the switch, it must be configured to set the parameters: credit value for each queue in bytes, initial values of cyclic priority and quota (in bytes) for the admissible amount of data continuously transmitted during queue servicing, and thereby setting the duration sub-session.

2. Frames transmitted to the destination port of the switch are classified according to the class of traffic and are recorded in the corresponding queues, while being provided with labels indicating the frame size and the time it was received in the queue.

3. The dispatcher starts when the output channel is released and there are non-empty queues.

4. A queue for servicing is selected taking into account the current value of cyclic priority.

5. The transmission of the first frame from the selected queue to the output channel starts.

6. The counter of transmitted data is increased and the credit value is reduced by the size of the frame.

7. At the end of the frame transfer, a sequence of checks is performed:

1) the availability of information in the queue served;

2) whether the quota of continuous service has ended;

3) the presence of a deficit, i.e. excess of the allocated loan;

8. If there is no more information in the served queue, then:

1) the value of cyclic priority changes;

2) credit values and continuous service quotas are set to initial values;

3) go to step 3 to start the service cycle of the next queue;

9. If the queue of continuous service has ended in the served queue, then:

1) the quota value is set to the initial;

2) when releasing the output port, the dispatcher selects, analyzing the time stamps, the queue containing the frame that is waiting for processing for the longest time;

3) for the selected queue, one frame is transferred with credit adjustment for the size of the transmitted frame;

4) proceed to step 5;

10. If there is a deficit, the following actions are performed:

1) the value of the loan for the new service cycle of this queue is set as the difference between the initial value and the deficit;

2) the quota value is set to the initial value;

3) the value of cyclic priority changes;

4) go to step 3 to start the service cycle of the next queue;

11. When transmitting each frame through the output port, the current average value of the frame size in bytes is calculated, the current value of which periodically adjusts the quota value, which limits the time of continuous queuing (sub-session duration).

An example of servicing queue 1, shown in FIGS. 1 and 2, illustrates the sequence of frames transmitted to the output channel. For the first subseas, frames 1-3 from queue 1 are transmitted, then the dispatcher searches for the “oldest” frame in all filled queues, even if this is frame 1 of queue 3, it is transmitted as a separator. After that, the second sub-session is performed, during which frames 4 and 5 of queue 1 are transmitted. At this, the session ends (with a deficit), because credit allocated for queue 1 has been exhausted.

The functioning of the preferred device that implements the proposed method of scheduling, is as follows.

Bus 12 receives frames from the frame advancement equipment to the destination port of the switch directed to this output port. They are classified by device 5 by the label contained in the frame, and are written on bus 9 to the queue 2 corresponding to the traffic class. At the same time, queue 3 is written with the label of the frame length and the time it was received in the queue formed by timer 6.

The processor starts by signals 13 and 14, if the channel is free, and there are no free queues. The processor, interrogating the label of the frame length, selects, according to the algorithm presented in Fig. 1, the service queue and starts the procedure of reading the next frame from this queue and its transmission to the channel. After reading each frame, the processor checks the conditions for the end of the service cycle, and achieve the quota of continuous transmission according to figure 1. If the cycle is completed, then the credit is adjusted and the next queue is selected according to the cyclic priority. If the cycle is not completed, then the timestamps are analyzed and the queue with the lowest value is selected, from which the separation frame is transferred with the corresponding correction of its credit, after which the interrupted service cycle is resumed until its end. At the same time, the scheduling processor periodically calculates the average frame length for a certain number of transmitted frames, for example 1024. The calculated current average length is used to adjust the values of the continuous transmission quotas.

Claims (4)

1. A method of dispatching queues in switches supporting quality of service, which consists in the fact that the dispatcher controls the access of switch queues to the physical channel according to the cyclic priority, the amount of data transferred from each queue in one session of its servicing is determined by the credit proportional to the class the traffic buffered in the corresponding queue, channel bandwidth, the credit can be adjusted by a deficit algorithm, characterized in that the service session is Each of the queues is divided into separate sub-sessions of a given duration, and at the end of each sub-session, subject to the need for further maintenance of the queue in accordance with the established credit, one dividing frame is selected, selected from all currently non-empty queues according to the criterion of the longest queue duration, after which the next subsession of the previously started queue maintenance session is resumed. 2. The method according to p. 1, characterized in that the frame placed in the queue is provided with an additional mark marking the time of its placing in the queue. 3. The method according to p. 1, characterized in that the size of the transmitted separation frame is taken into account in adjusting the size of the loan for subsequent servicing of the queue from which the separation frame was taken. 4. The method according to claim 1, characterized in that the quota determining the duration of the sub-sessions is set equal to the average size of the transmitted frames periodically calculated from the current channel traffic.

Images