RU2696218C1 - Method of managing queues in routers of transport communication network - Google Patents

Abstract

FIELD: communication equipment.

SUBSTANCE: invention relates to telecommunication networks. When controlling queues in routers: receiving an incoming stream of data traffic, determining packet priority in the received data traffic stream, calculating the average queue length for each priority, congestion in a communication channel is determined by placing a packet into a queue of the corresponding priority in the absence of overload in the transport communication network. In addition, weight coefficients are formed for each priority, weighting factors are compared for each queue in accordance with priority of packets serviced in this queue. After determining overload in communication channel calculating probability of packet P_resetting resetting P_resetting, considering queue weight coefficient and queue average length. Decision is made on action on packet: packet is reset with probability P_resetting or put in queue with probability 1-P_resetting.

EFFECT: reduced average packet latency for priority traffic during communication channel overload.

3 cl, 1 tbl, 6 dwg

Description

Technical field

The invention relates to the field of telecommunication communication networks, in particular, to methods of dealing with congestion in transport communication networks.

State of the art

Currently, there is an acute problem of congestion of transport communication networks with packet switching. Given the fact that by 2020 more than 50 billion Internet of Things and Industrial Internet devices will be connected to public networks, there is a risk that transport communication networks will not cope with the traffic generated by so many nodes. The existing transport communication networks implement a number of mechanisms to prevent congestion: routing based on the state of traffic (traffic-aware routing), access control (admission control), traffic regulation (traffic throttling), load shedding. These procedures are implemented in routers of a transport communication network or access network. To avoid congestion during pulsating (packet) traffic, active queue management algorithms are quite effective, which include packet rejection, such as random early detection of RED congestion (Random Early Detection), weighted WRED (Weighed Random Early Detection), active ARED (Adaptive Random Early Detection) )

A device is known "Random early drop of packets and differential control of packet flows in the queues of the switch" (patent US 7756977 B2 dated 07/13/2010), which includes many ports in which at least one port receives an incoming packet stream, packet classifier, which classifies incoming packets by priority based on the packet header, the module for calculating the time that the packet has been in the queue, the packet reset module.

The known method of "Random early drop packets in accordance with the class of step-by-step routing PHB" (US patent 7349336 B2 dated 05/25/2008), which includes receiving a packet with an appropriate traffic class, creating a specialized RED class for regulating various classes of traffic with step-by-step routing PHB (Per Hop Behavior) within the same queue, managing the appropriate package based on the RED parameters, the specialized RED class and the PHB step-by-step routing class, setting the minimum and maximum queue threshold taking into account the specialized RED class and the PHB step-by-step routing class, determining the probability of packet marking and the probability of queuing a packet based on the specialized RED class and the PHB step-by-step routing class, marking the packet in accordance with the calculated probability when the packet is between the minimum and maximum queue threshold, or queue according to the calculated probability, if the average queue length is greater than the maximum queue threshold, then the packet is discarded.

The closest in technical essence to the claimed method and selected as a prototype is the "Method of differential packet rejection based on the WRED algorithm and its device that implements" (patent US 2017/0134282 A1 of 05/11/2017), which consists in accepting incoming packets, if there is no congestion in the network, put the packet in a queue or queues, if there is congestion in the network, they either queue the packet or drop the packet based on the probability of packet dropping and the priority of the service. Network congestion is determined if the average queue length is greater than the minimum threshold. It is possible to queue a packet if the average queue length is greater than the minimum threshold and less than the maximum threshold; otherwise, if the average queue length is greater than the maximum threshold, all packets are discarded. In this case, incoming packets may have service priorities defined through identifiers in the packet header of the first, second, and third levels.

The technical problem of these analogs and prototypes is the high average network delay of packets for priority traffic during communication channel congestion. The reason this happens is that in the WRED weighted early congestion detection algorithm, packet loss functions of different priorities change linearly with increasing congestion.

, принимают решение о действии над пакетом: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

.The creation of a queue management method in the routers of the transport communication network is aimed at solving this technical problem, which reduces the average network packet delay for priority traffic during communication channel overload due to the fact that weighting factors for each priority are formed, weighting factors for each queue are compared in accordance with priority packets that are served in this queue, calculate the probability of packet dropping

, decide on the action on the packet: the packet is discarded with probability

, or queue with probability

.

Disclosure of invention

, учитывая весовой коэффициент очереди и среднюю длину очереди. Принимают решение о действии над пакетом: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

.In the claimed method, this technical problem is solved by the fact that in the queue management method in the routers of the transport communication network, which consists in receiving an incoming data traffic stream, determining the priority of the packet in the received data traffic stream, calculating the average queue length for each priority, determining the congestion in the communication channel, the packet is queued with the corresponding priority in the absence of congestion in the transport communication network. Additionally, weights are formed for each priority, and weights for each queue are compared in accordance with the priority of the packets that are served in this queue. After determining the congestion in the communication channel, the probability of packet dropping is calculated

given the weight of the queue and the average length of the queue. Make a decision about the action on the packet: the packet is discarded with probability

, or queue with probability

.

According to one particular embodiment, the priority of the packet in the received data traffic stream is determined according to the TOS (Type of Service) Precedence field of the IP packet header, or based on the DSCP (Differentiated Service Code Point) field of the IP packet header.

According to one particular embodiment, weights are generated for each priority in accordance with the TOS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header.

, учитывая весовой коэффициент очереди и среднюю длину очереди, принимают решение о действии над пакетом: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

.A new set of essential features allows you to achieve the specified technical result due to the fact that weights are formed for each priority, weights are compared for each queue in accordance with the priority of the packets that are served in this queue, and the probability of packet dropping is calculated

, taking into account the weight coefficient of the queue and the average length of the queue, they decide on the action on the packet: the packet is discarded with probability

, or queue with probability

.

The analysis of the prior art made it possible to establish that there are no analogues that are characterized by a combination of features that are identical to all the features of the claimed method of queue management in routers of a transport communication network. Therefore, each of the claimed inventions meets the condition of patentability “novelty”.

Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the prior art. The prior art also did not reveal the popularity of the impact provided by the essential features of the claimed invention, the transformations on the achievement of the specified technical result. Therefore, each of the claimed inventions meets the condition of patentability "inventive step".

To more clearly illustrate technical solutions according to embodiments of the present invention, a brief description of the accompanying drawings is given below.

In FIG. 1 is a flow diagram of a method for managing queues in routers of a transport communication network;

in FIG. 2 - IP packet header;

in FIG. 3 - a table of correspondence of the values of weighting coefficients with the values of the TOS field and the DSCP field of the IP packet header;

in FIG. 4 - simulation model in a network emulator NS-2;

in FIG. 5 are functions describing the probability of packet loss for various weights;

in FIG. 6 - the law of distribution of the number of packets in the queues for different priorities.

Implementation of the claimed method is as follows (Fig. 1).

10. Accept the input data traffic stream, consisting of packets of different priority.

11. Determine the priority of the packet in the received data traffic stream. The priority of the packet is determined according to the TOS Precedence field of the IP packet header (Fig. 2), in which three bits are allocated for the priority value, or in accordance with the DSCP field of the IP packet header.

для каждого приоритета. Так как в поле TOS Precedence заголовка IP пакета и в поле DSCP заголовка IP пакета выделено три бита под приоритет пакетов, следовательно можно реализовать

различных вариантов значений весовых коэффициентов для различных приоритетов. Формирование весовых коэффициентов производят по следующему правилу: 12. Form weight factors

for each priority. Since in the TOS Precedence field of the IP packet header and in the DSCP field of the IP packet header three bits are allocated for the priority of the packets, therefore, it is possible to implement

different weighting options for different priorities. The formation of weights is carried out according to the following rule:

, (one)

– весовой коэффициент

-го приоритета,

.Where

- weight coefficient

priority

.

,

,…,

. For example,

,

, ...,

.

сопоставляют для очереди, в которой обслуживаются пакеты наивысшего приоритета, а весовой коэффициент

сопоставляют для очереди, в которой обслуживаются пакеты наименьшего приоритета. 13. Compare the weights for each queue in accordance with its priority (Fig. 3). In this case, the weight coefficient

match for the queue in which packets of the highest priority are served, and the weight coefficient

map to the queue in which the lowest priority packets are served.

14. Calculate the average queue length for each priority. The calculation of the average queue length for each priority is performed according to the following rule:

, (2)

– вычисленное значение средней длины очереди для пакетов

-го приоритета;Where

- the calculated value of the average queue length for packets

priority;

– значение средней длины очереди в предыдущий момент времени для пакетов

-го приоритета;

- value of the average queue length at the previous moment in time for packets

priority;

– мгновенное значение длины очереди для пакетов

-го приоритета в текущий момент времени;

- instant queue length for packets

priority at the current time;

– экспоненциальный весовой фактор, который определяет администратор транспортной сети связи, при этом значения

находится в диапазоне от 0 до 10. Большое значение этого коэффициента

сильнее сглаживает разные изменения мгновенного значения длины очереди пакетов

-го приоритета в текущий момент времени. По этой причине средняя длина очереди будет изменяться медленнее, чем мгновенное значение длины очереди. Как следствие алгоритм взвешенного раннего обнаружения перегрузки WRED не сразу начнет отбрасывать пакеты при резком изменении мгновенного значения длины очереди пакетов

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

-го приоритета. В случае если

, алгоритм взвешенного раннего обнаружения перегрузки WRED перестанет реагировать на мгновенную перегрузку в канале связи. В случае, если значение 

  ежит в диапазоне

, среднее значение длины очереди практически совпадает c текущим значением длины очереди. В этом случае реакция алгоритма взвешенного раннего обнаружения перегрузки WRED на резкие изменения длины очереди становится практически мгновенной. Если значение 

 , алгоритм взвешенного раннего обнаружения перегрузки WRED становится чрезвычайно чувствителен к резким изменениям числа пакетов в очереди, в этом случае значение средней длины очереди численно совпадает с мгновенным значением длины очереди.

- exponential weighting factor, which is determined by the administrator of the transport communication network, while the values

is in the range from 0 to 10. The large value of this coefficient

smoothes out different changes in the instantaneous value of the packet queue length

priority at the current time. For this reason, the average queue length will change more slowly than the instantaneous queue length. As a result, the WRED weighted early congestion detection algorithm does not immediately start dropping packets when there is a sharp change in the instantaneous value of the packet queue length

priority, or it may continue to drop packets even when there are slight changes in the instantaneous value of the packet queue length

priority. If

, the WRED weighted early congestion detection algorithm will no longer respond to instantaneous congestion in the communication channel. In case the value

hedgehog in the range

, the average value of the queue length practically coincides with the current value of the queue length. In this case, the response of the weighted early detection algorithm for WRED congestion to sudden changes in the queue length becomes almost instantaneous. If the value

, the WRED weighted early congestion detection algorithm becomes extremely sensitive to sudden changes in the number of packets in the queue, in which case the average queue length is numerically the same as the instantaneous queue length.

15. Determine the overload in the transport communication network according to the following rule:

, (3)

– минимальный порог для очереди, в которой обслуживаются пакеты

-го приоритета. Если выражение (2) выполняется, то определяют что перегрузки нет и пакет

-го приоритета ставят в очередь , в которой обслуживаются пакеты соответствующего приоритета. Иначе определяют факт наличия перегрузки и проверяют следующее условие:Where

- minimum threshold for the queue in which packets are served

priority. If expression (2) is satisfied, then it is determined that there is no overload and the packet

-th priority is put in the queue in which packets of the corresponding priority are served. Otherwise, the fact of the presence of overload is determined and the following condition is checked:

(four)

– максимальный порог для очереди, в которой обслуживаются пакеты

-го приоритета. Если выражение (3) выполняется, то вычисляют вероятность сброса пакета, иначе сбрасывают пакет.Where

- maximum threshold for the queue in which packets are served

priority. If expression (3) is satisfied, then the probability of packet dropping is calculated, otherwise the packet is discarded.

The values of the maximum threshold of the queue and the minimum threshold of the queue are determined by the administrator of the transport communication network for each queue in which packets of the corresponding priority are served.

-го приоритета с учетом весового коэффициента очереди, в которой обслуживаются пакеты и ранее вычисленной средней длины очереди:16. The probability of packet dropping is calculated.

-th priority taking into account the weight coefficient of the queue in which the packets are served and the previously calculated average queue length:

, (five)

– весовой коэффициент очереди, в которой обслуживаются пакеты

 - го приоритета.Where

- weight of the queue in which packets are served

- first priority.

-го приоритета: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

. Для того, чтобы принять решение о действии над пакетом

-го приоритета необходимо сгенерировать случайное число

, равномерно распределенное в диапазоне от 0 до 1, если

, то пакет

-го приоритета сбрасывают, если

, то пакет

-го приоритета ставят в очередь.17. Decide on action on the package

priority: the packet is discarded with probability

, or queue with probability

. In order to decide on the action on the package

priority must generate a random number

uniformly distributed in the range from 0 to 1 if

then the package

priority are reset if

then the package

queue priority.

-го приоритета

, значение случайного числа

, поскольку

, следовательно пакет

-го приоритета сбрасывают.For example, the probability of a packet dropping

priority

random number value

, insofar as

therefore package

priority are reset.

, учитывая весовой коэффициент очереди и среднюю длину очереди, принимают решение о действии над пакетом: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

.The claimed method of queue management in routers of a transport communication network allows to achieve the indicated technical result by reducing the average network delay of a packet for priority traffic during communication channel overload due to the fact that weighting factors for each priority are formed, weighting factors for each queue are compared in accordance with the priority of the packets, who are served in this queue calculate the probability of a packet dropping

taking into account the weight coefficient of the queue and the average length of the queue, they decide on the action on the packet: the packet is discarded with probability

, or queue with probability

.

The validity of the theoretical assumptions was checked on a fragment of the transport communication network using the NS-2 network emulator with the following initial data (Fig. 4):

; - the number of trunk routers in the communication network

;

;- number of information sources

;

-го приоритета с

Мбит/с;- packet arrival rate

priority with

Mbps

Мбит/с.- throughput of the main channel

Mbps

поступают

потоков трафика данных, имитируя

приоритетов. На узле

настроен модифицированный алгоритм взвешенного раннего обнаружения перегрузки WRED со следующими настройками для каждой очереди: длина очереди равна

пакетов, минимальный порог очереди равен

пакетов, максимальный порог очереди равен

пакетов. Все

потоков трафика данных направлены в магистральный узел

. Планировщик (scheduler) настроен с учетом принципа справедливого распределения ресурса в выходном канале связи WFQ (Weighed Fair Queuining), то есть каждому приоритету выделено по 1 Мбит/с от общей пропускной способности канала связи. В таблице 2 представлены результаты имитационного моделирования фрагмента транспортной сети связи в сетевом эмуляторе NS-2. Задержка пакетов восьмого приоритета с весовым коэффициентом

эквивалентна задержке полученной при реализации алгоритма взвешенного раннего обнаружения перегрузки WRED описанном в способе, выбранном в качестве прототипа.To the trunk router

arrive

data traffic flows by simulating

priorities. On the node

A modified algorithm for weighted early detection of WRED congestion is configured with the following settings for each queue: queue length is

packets, the minimum queue threshold is

packets, the maximum queue threshold is

packages. Everything

data traffic flows are routed to the trunk node

. The scheduler is configured taking into account the principle of fair distribution of resources in the output WFQ (Weighed Fair Queuining) communication channel, that is, 1 Mbps of the total communication channel bandwidth is allocated to each priority. Table 2 presents the results of simulation modeling of a fragment of a transport communication network in a network emulator NS-2. Eight priority packet delay with weight

equivalent to the delay obtained by implementing the weighted early detection algorithm WRED overload described in the method selected as a prototype.

Table 1 - The results of simulation of a fragment of a transport communication network in a network emulator NS-2

room
priori theta Flow rate
data traffic
Mbps Weight
coefficient Part
bandwidth
abilities in
outgoing
communication channel, Mbps Medium network
packet delay, ms Average
length
queues
packages Coefficient
of losses
packages one 2,4 0.125 one 92 22,894 0.583 2 2,4 0.143 one 94 23,577 0.583 3 2,4 0.167 one 99 24,631 0.583 four 2,4 0.2 one 105 26,328 0.583 five 2,4 0.25 one 117 29,306 0.583 6 2,4 0.333 one 139 34,635 0.583 7 2,4 0.5 one 177 44,187 0.583 eight 2,4 one one 243 60,833 0.583

раз меньше по сравнению с прототипом, а среднесетевая задержка пакетов для приоритетного трафика данных (седьмого приоритета) в

раз меньше по сравнению с прототипом. На фиг. 5 представлены функции, описывающие вероятность потери пакетов для различных весовых коэффициентов. Так, например, при весовом коэффициенте

функция, описывающая вероятность сброса пакетов линейна и соответствует алгоритму взвешенного раннего обнаружения перегрузки WRED, описанную в способе прототипе, остальные функции, позволяющие осуществить вероятность сброса пакетов имеют нелинейный характер. На фиг. 6 показаны законы распределения числа пакетов в очереди для различных весовых коэффициентов, полученные в результате имитационного моделирования.An analysis of the simulation results shows that the average network delay of packets for priority data traffic (first priority) in

times less than the prototype, and the average network delay of packets for priority data traffic (seventh priority) is

times less compared to the prototype. In FIG. 5 shows functions describing the probability of packet loss for different weights. So, for example, with a weight coefficient

the function that describes the probability of packet dropping is linear and corresponds to the algorithm for weighted early detection of WRED congestion, described in the prototype method, other functions that allow the probability of dropping packets are non-linear. In FIG. Figure 6 shows the laws of the distribution of the number of packets in a queue for various weights obtained as a result of simulation.

, учитывая весовой коэффициент очереди и среднюю длину очереди, принятия решения о действии над пакетом: пакет сбрасывают с вероятностью

, либо ставят в очередь с вероятностью

.The claimed method of queue management in routers of a transport communication network provides a reduction in the average network delay of packets for priority traffic during communication channel congestion by generating weights for each priority, matching weights for each queue in accordance with the priority of the packets that are served in this queue, computing packet drop probabilities

, taking into account the weight coefficient of the queue and the average length of the queue, deciding on the action on the packet: the packet is discarded with probability

, or queue with probability

.

Claims (3)

1. A method for managing queues in routers of a transport communication network in which an incoming data traffic stream is received, packet priority in a received data traffic stream is determined, the average queue length for each priority is calculated, congestion in the communication channel is determined, the packet is queued for the corresponding priority when the absence of congestion in the communication channel, characterized in that after determining the priority of the packet in the received data traffic stream, weights are formed for each priority, corresponded weighting coefficients each queue according to priority of packets are serviced in the queue after determining an overload in the transport network connection calculated probability reset packet P _reset, given weighting queue coefficient and an average queue length, taking a decision on the action on the packet: dropping a packet with probability P of a _reset , or queue with a probability of 1-P _reset . 2. The method according to claim 1, in which the determination of the priority of the packet is carried out according to the TOS Precedence field of the IP packet header or based on the DSCP field of the IP packet header. 3. The method according to claim 1, in which the weights are generated in accordance with the TOS Precedence field of the IP packet header or in accordance with the DSCP field of the IP packet header.

Images