RU2684581C2 - Method of stochastic dispatching of switch queues, and device its implementation - Google Patents

Abstract

FIELD: wireless communication equipment.

SUBSTANCE: invention relates to telecommunications. Stochastic dispatching device as part of a switch or a router comprises a shared memory, a queue selection unit, comprising a supervisory unit, a constant values storage unit, a pseudorandom number generator, a value comparison unit, service queue number determining unit, headers and indicators memory, memory controller, classifier, input and output ports, also includes set of connections, connection (1) is the control input of the queue selection unit, through which the queue management unit initiates the procedure for counting the queue number and the new operation cycle of the device, connection (2) is an information input, through which queue control unit at the moment of receipt at control signal connection (1) should be transmitted queue lengths and parameters, and the values comparison unit compares values calculated by the queue selection calculation unit, and a unit for counting the serviced queue number based on the comparison data received from the value comparison unit, outputs to the processing units, the frame sampling scheme of the processing block, as well as the service enable or prohibit signal supervision node for each of the service classes.

EFFECT: wider range of tools for the same purpose.

1 cl, 2 dwg

Description

The invention relates to the field of telecommunications, namely, switches and routers with support for quality of service, and is intended to regulate the access of the switch and router queues to the physical channel.

Among the mechanisms to ensure the quality of service, the most important is the queue dispatching algorithm, i.e. rules for selecting a queue for reading data from it and the amount of data to be read per call, which directly determines the delay of frames and the probability of their loss.

In traditional deterministic systems for dispatching queues in network devices, the choice of a queue has a deterministic character defined by the rules of prioritization (rigid, cyclic, etc.) [Olifer V.G. , Olifer N.A. Computer networks. Principles, technologies, protocols. 4th ed. - St. Petersburg: Publishing House "Peter", 2010, - S. 943]. In such systems, the waiting time for servicing a certain frame depends not only on the place of the frame in the queue, the congestion of the queues and other arguments, but also on the rules for the sequence of servicing nodes, which leads to unpredictability of frame delay.

There is a method of packet dispatching, designed to control access of queues to the hardware resources of the output channel, based on the quality of service and its device that implements the fact that the parameter of quality of service is included in the packet header; repeated updating of the value of a random variable; a priority key is assigned to the packet, depending on the quality of service parameter and the random variable generated, in accordance with predefined rules [Patent EP 1 887 742 A1 System and process for QOS-based packet scheduling]. The scheduling system, assigning hardware resources of the output channel to pass packets processed by various service providers, includes:

random generator;

- a programmable attributing device that assigns a priority key to a packet, depending on the quality of service parameter and the generated random variable, in accordance with the reprogrammable rules;

- dispatch device containing a control device that generates packet switching commands in the order depending on the value of the priority key assigned to each packet header;

- a switching device that advances packets in the direction of the hardware resources of the output channel in the generated order of packet switching commands.

As follows from the claims, in the known method of packet dispatch, designed to control access of queues to the hardware resources of the output channel, based on the quality of service, packet switching commands are generated in the order depending on the value of the priority key assigned to each packet header and the value of a random number independent of packet delay values, queue lengths, accumulated service times; packets advance towards the hardware resources of the output channel in the generated order of packet switching commands.

The disadvantages of this method of packet scheduling, designed to control access of queues to the hardware resources of the output channel, are:

1) A large dependence of the magnitude of the spread of the length of the queues and the time spent by the queues on the magnitude of the spread of the number of requests received by the queues per unit time due to the independence of the access control of the queues to the output channel on the packet delay values, queue lengths, accumulated service times and fractions of the passband for each class of service, quickly evaluated in the scheduling process.

2) Frames with the same values of the priority bitfield can be distributed in different queues with different fractions of the bandwidth, which leads to frame loss [2, 3].

Closest to the proposed invention is a method of stochastic dispatching, based on priority, designed to sample tasks for execution [Patent 5,247,677 U.S. STOCHASTIC PRIORITY-BASED TASK SCHEDULER / Welland et al. (1993)], which consists in the fact that it selects tasks from queues by comparing the values of a multiple-updated random number and the sum of the constant probabilities of samples of queues whose numbers are less than or equal to the numbers of these queues, makes it possible to service low priority queues by allocating a guaranteed share service.

From the analysis of the claims of the known method, it follows that the method is intended for distributing processor time between tasks in operating systems by one or more processors, as well as in any other digital computer systems where such scheduling is necessary. The probability values of the queue samples are constant and do not depend on the length of the queues and the share of bandwidths for each class of service, which are quickly evaluated in the scheduling process. The priority-based stochastic dispatcher selects tasks based on a random number weighted by the priority of the task. Since each task has a nonzero final probability of being selected, all tasks, including low priority ones, have a chance to be selected, thus eliminating the deadlock problem.

The disadvantages of stochastic priority-based dispatching are:

1) The lack of the ability to control the values of the lengths of the queues, the time spent on finding applications for performing tasks in separate queues.

2) A large dependence of the magnitude of the dispersion of the lengths of the queues and the time spent by applications in the queues on the magnitude of the dispersion in the number of applications accepted by the queues per unit time.

The objective of the invention is the alignment of the main characteristics of the channel, manifested in reducing variations in the average value and standard deviation of the queue lengths, reducing variations in the average values of frame delays of different classes.

The task is achieved by creating the discipline of scheduling, combining the satisfaction of adaptability to dynamically changing network parameters, as well as the lack of determinism.

A device that implements a method of stochastic adaptive dispatching of queues of a network switch with support for quality of service includes a shared memory, a memory controller, a classifier, a queue management node, a memory for headers and pointers, a queue selection block containing an surveillance node, a node for calculating the probabilities of selecting queues for servicing, a node storage of constant values, a pseudo-random number generator, a node for comparing values, a node for determining the number of the queue served.

New in the proposed technical solution, in contrast to the prototype, is that the relationships that transfer the values of the arguments of the probability dependence function in the direction from the queue management node to the queue selection block are defined.

The foregoing allows us to conclude that there is a causal relationship between the totality of essential features and the achieved technical result.

The drawings attached to the description show:

figure 1 - diagram of the algorithm of the cycle of the block selection of queues that implements the method of stochastic dispatching of queues in the switches;

figure 2 is a block that implements a method for stochastic dispatching of queues in switches.

A device that implements this method of stochastic dispatch of queues in switches (FIG. 2) comprises: the following nodes: a pseudo-random number generator with a unit for comparing values; constant storage unit; a node for calculating the probabilities of choosing queues for servicing, containing subnodes: multiplication and division, addition and subtraction, logical operations, comparison of numbers by zero, increments, conditional transitions, constants; node counting the numbers of the queue served; supervision unit.

A device that implements the proposed method for stochastic adaptive dispatching of queues of a network switch supporting quality of service works as follows. The device is intended for direct control and supervision of the distribution of channel time between different queues.

A stochastic dispatch device as part of a switch or router contains a set of connections.

Connection 1 is the control input of the queue fetch block, by which the queue management node initiates the start of the procedure for calculating the queue number and a new cycle of operation of the stochastic dispatch device. Connection 2 is an information input through which the queue management node at the time of receipt of the control signal at connection 1 should be transferred the length of the queues and other parameters necessary for calculating the queue number. Connection 3 is the control output, through which the control signal is transmitted to the queue management node, indicating the end of the queue number calculation procedure. Connection 4 is an information output through which the queue management node must receive the calculated queue number that must be served at the time the control signal 3 arrives at connection 3.

Connection 5 transfers frames from the input port to the classifier in order to classify traffic in accordance with various requirements specified by the quality of service, for example, frame delays, etc.

Through connection 6, frames are transferred to the shared memory controller from the classifier, while the address of the beginning of the frames is recorded in the memory of pointers and headers (see below).

At connection 7, operations are performed to write the contents of the shared memory by the shared memory controller.

At connection 20, read operations of the contents of the shared memory are performed by the shared memory controller.

Connection 8 is used to record frames extracted from shared memory by the memory controller to the output port.

Connection 9 transfers the control signal from the output port to the memory controller about the end of the frame transfer procedure from the output port to the transmission medium.

Connection 21 transfers the control signal from the output port to the memory controller about the upcoming end of the frame transfer procedure from the output port to the transmission medium.

Connection 10 transmits a request, a control signal, to check information about the queue emptiness. If two queues and are no longer empty, a request is sent to determine the number of the queue being served on connection 1.

At connection 11, a control signal is transmitted - a request from the queue management node addressed to the memory controller to retrieve a frame whose address and length are transmitted via connection 12 from the shared memory.

Connection 13 transfers the control signal from the classifier addressed to the queue management node to record the frame header, the header of which is transmitted via connection 14, and the queue number assigned by the classifier via connection 15.

On connection 22, a control signal is transmitted for connection 21. On connection 21, the frame address necessary for writing is transferred to the memory of pointers and headers.

The supervision node monitors the arguments, that is, the length of the queues, the service times transmitted via information connection 2. If, for example, the sum of the lengths of the queues is greater than the size of the shared memory, then the procedure for calculating the number of the queue being served is not performed; the number of the queue served is sent to output 4 , acquires the value corresponding to the previous number of the served queue.

The supervision node is connected by connection 1 and connection 2 to the queue management node, and also has an output connected to the probability calculation node.

The node for calculating the probabilities of selecting service queues provides the calculation of probability values carried out according to the algorithm shown in Fig. 1.

The node for calculating the probabilities of choosing service queues has inputs from the supervision node, the constant storage node (ROM), and also has an output connected to the node for comparing values.

The procedure for calculating the number of the serviced queue is cyclic; it is initiated by the frame sampling scheme with the permission of the supervision unit of the stochastic scheduling device at the time corresponding to the remainder of the time until the end of the frame transmission necessary for calculating the desired number. The transfer of arguments for calculating the probabilities is carried out from the transfer queues of the headers and pointers of the personnel processor to the supervision unit and to the probability calculation unit of the stochastic dispatch device. The supervision node checks the arguments for correctness and enables or disables the calculation. The calculation of probabilities for each of the queues is carried out in parallel and independently of the calculation of the probabilities of choosing other queues. However, in accordance with the proposed method, the calculation of the sums of probabilities (cumulative probabilities). This calculation is also carried out in the node for calculating the probabilities of choosing queues for servicing.

The constant storage node contains some numerical constants intended for calculating probabilities, such as: allocated service shares for each type of traffic, default priorities (initial probability values), seed of the pseudo random number generator.

The constant storage unit has an output associated with the comparison unit.

During initialization, the pseudo-random number generator receives the key code from the constant storage node, generates a random number through a fixed number of clock ticks so that at least one pseudo-random number calculation is necessary for each dispatch cycle. The generated sequence of pseudorandom numbers obeys a uniform distribution. Any number from this sequence has a non-negative value less than one.

The unit for comparing values compares the values calculated by the unit for calculating the probabilities of choosing a service queue, i.e. the so-called cumulative probabilities, and a random variable generator. For each type of traffic, either a truth value or a lie value is set depending on the difference in values.

The node for counting the number of the serviced queue, based on the comparison data received from the node for comparing the values, provides the processing nodes, the frame sample frame of the processing unit, as well as the surveillance node for the enable or disable service signals for each of the service classes in accordance with the algorithm presented in FIG. 2.

The method is implemented by the algorithm shown in FIG. 1. Its execution occurs cyclically.

необходимо решить уравнение (1), где

- произвольная константа,

- автоматное время работы устройства (для блока, реализующего расчёт номера очереди на обслуживание, согласно способу предназначен один источник синхронных импульсов),

- накопленное время обслуживания

-той очереди за всё время работы, m – общее число очередей,

- длина i - той очереди в битах,

- столбцовая матрица размером

, характеризующая доли разрешённых полос пропускания, выделенных для каждой

-той очереди при

, при этом

является постоянной величиной,

– поправочные величины, нахождение значений которых является промежуточным этапом, необходимым в процессе вычисления вероятностей выборок очередей на обслуживание согласно уравнению (1). The node for calculating the probabilities of selecting service queues provides the calculation of probability values carried out according to the algorithm shown in Fig. 1. To calculate probabilities

it is necessary to solve equation (1), where

is an arbitrary constant,

- automatic operating time of the device (for a unit that implements the calculation of the service queue number, according to the method, one source of synchronous pulses is intended),

- accumulated service time

of this queue for the entire time of work, m is the total number of queues,

- the length of i is that queue in bits,

- column matrix size

characterizing the shares of allowed bandwidths allocated for each

this queue at

, wherein

is a constant

- correction values, the determination of the values of which is an intermediate step necessary in the process of calculating the probabilities of samples of service queues in accordance with equation (1).

The probabilities are calculated based on the solution of equation (1) on the basis of the available data on the loading of queues, the current strip, etc. with unknown x being a column matrix. If the i - th queue is empty, the calculation of the probability for the i - that class of service does not make sense, because it will become zero.

согласно формуле (2). After finding the value of x, it is necessary to find the desired values of the probabilities of the choice of queues

according to the formula (2).

выбора очередей на обслуживание согласно формуле (3). Таким образом, уравнение (1) можно записать в виде (4). Значения

не являются постоянными и переменны во времени. Значение

является постоянной величиной. Т.о., для решения уравнения (1) необходимо вычислить, в т.ч. значения числовых критериев

выбора очередей на обслуживание согласно формуле (3). Таким образом, уравнение (1) можно записать в виде (4). Значения

не являются постоянными и переменны во времени. Уравнение (1) можно записать в виде (6). Решением уравнения (6) является выражение (7). Для каждой очереди вычисляется значение

согласно формуле (7). На основе полученных значений

подсчитываются значения вероятностей выбора очередей на обслуживание согласно формуле (2). На основе полученных значений осуществляется подсчёт значений кумулятивных вероятностей

согласно формуле (8). К моменту окончания подсчёта кумулятивных вероятностей значение (псевдо-) случайного числа Rand должно быть сгенерированным и известным. Затем осуществляется сравнение кумулятивных вероятностей

со значением Rand согласно алгоритму, показанному на фиг.2. To solve equation (1), it is necessary to calculate several values, including values of numerical criteria

selection of service queues according to formula (3). Thus, equation (1) can be written in the form (4). Values

are not constant and variable over time. Value

is a constant. Thus, to solve equation (1), it is necessary to calculate, incl. values of numerical criteria

selection of service queues according to formula (3). Thus, equation (1) can be written in the form (4). Values

are not constant and variable over time. Equation (1) can be written in the form (6). The solution to equation (6) is expression (7). For each queue, the value is calculated.

according to the formula (7). Based on the obtained values

the values of the probabilities of choosing service queues are calculated according to formula (2). Based on the obtained values, the cumulative probability values are calculated

according to the formula (8). By the end of the cumulative probability calculation, the value of the (pseudo-) random number Rand should be generated and known. Then the cumulative probabilities are compared.

with a Rand value according to the algorithm shown in FIG. 2.

(1),

(one),

(2),

(2)

(3)

(3)

(4)

(four)

(5)

(5)

(6)

(6)

(7)

(7)

(8)

(8)

Claims (1)

A stochastic scheduling device as part of a switch or router containing shared memory, a queue selection unit, including a surveillance unit, a constant storage unit, a pseudo-random number generator, a unit for comparing values, a unit for determining the number of the serviced queue, memory headers and pointers, a memory controller, a classifier, the input and output ports also includes a set of connections, connection (1) is the control input of the queue fetch block, through which the queue management node initiates the procedure for calculating the queue number and a new operation cycle of the device is started, the connection (2) is an information input through which the queue management node at the moment of receipt of the control signal at the connection (1) must receive the queue lengths and parameters for calculating the queue number, connection (3 ) is a control output, through which a control signal is transmitted to the queue management node, indicating the end of the queue number calculation procedure, connection (4) is an information output, through which At the moment of receipt of the control signal to the connection (3), the counting queue number must be transmitted to the queue management node, it must be serviced, connection (5) transfers frames from the input port to the classifier, connection (6) transfers the frames to the controller shared memory from the classifier, while the address of the beginning of the frames is recorded in the memory of the pointers and headers, connection (7) is used to write the contents of the shared memory to the controller ohm of shared memory, through connection (20), operations are performed to read the contents of shared memory by the shared memory controller, through connection (8), frames are extracted from the shared memory by the memory controller to the output port, connection (9) transfers the control signal from the output port to the memory controller about the end of the frame transfer procedure from the output port to the transmission medium, connection (21) transfers the control signal from the output port to the memory controller about At the end of the procedure for transferring a frame from the output port to the transmission medium, via connection (10), a control signal is sent to check the information about the queue’s emptiness; if two queues are no longer empty, a request is sent to determine the number of the serviced queue by connection (1 ), via connection (11), a control signal is transmitted - a request from the queue management node addressed to the memory controller to retrieve a frame whose address and length are transmitted via connection (12) from the shared memory, through connection (13), a control signal is transmitted from the classifier addressed to the queue management node to record the frame header, the title of which is transmitted via connection (14), and the queue number assigned by the classifier is transmitted through connection (15), through connection (22 ) the control signal for connection (21) is transmitted, connection (21) transfers the address of the frame necessary for writing to the memory of pointers and headers, the surveillance unit monitors the length of the queues and the service time transmitted via the information system together (2), if the sum of the queue lengths is greater than the size of the shared memory, then the procedure for calculating the number of the serviced queue is not performed, the number of the serviced queue supplied to the output (4) acquires the value corresponding to the previous number of the serviced queue, while the pseudo random number generator in the initialization process, receives a key code from the constant storage node, periodically generates a random number, the constant storage node has an output associated with the value comparison node, distinguishing The fact that the queue selection block contains a node for calculating the probabilities of selecting queues for servicing, which has input connections to the nodes of supervision and storage of constant values, and also has an output connected to the node for comparing values, while the node for calculating the probabilities of choosing queues for servicing provides a count the probability values of the selection of service queues according to the following cyclic procedure, which is initiated by the frame sampling scheme with the permission of the device’s supervision node at a time corresponding to the remainder As the time until the end of the frame transfer necessary for calculating the desired number is completed, the arguments for the probability calculation node are transmitted from the queues of headers and pointers through the queue management and supervision nodes, while the value comparison node compares the values calculated by the probability calculation node for choosing the service queue and the indicated total probabilities of the choice of the queue, and the node for counting the number of the queue served, based on the comparison data received from the node for comparing the values, produces brabatyvayuschim nodes scheme frame sample processing unit, as well as site supervision signals enable or disable the service on each of the classes of service.

Images