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

ЭЛЕКТРОНИКА, ИЗМЕРИТЕЛЬНАЯ ТЕХНИКА И РАДИОТЕХНИКА

УДК 005.7

DOI 10.21685/2072-3059-2018-4-10

А. О. Семенов, Н. Н. Коннов, Е. И. Гурин

ОБ ИСПОЛЬЗОВАНИИ АЛГОРИТМОВ СТОХАСТИЧЕСКОЙ ДИСПЕТЧЕРИЗАЦИИ ОЧЕРЕДЕЙ В СЕТЕВОМ КОММУТАТОРЕ

Аннотация.

Актуальность и цели. Объектом исследования являются современные телекоммуникационные устройства (коммутаторы). Предметом исследования являются системы диспетчеризации современных телекоммуникационных устройств. Цель работы - создание дисциплины диспетчеризации, удовлетворяющей требованиям обеспечения качества обслуживания.

Материалы и методы. Работа посвящена оценке эффективности алгоритмов диспетчеризации очередей средствами имитационного моделирования с использованием пакета CPNTools, который основан на применении математического аппарата цветных иерархических сетей Петри.

Результаты. Сопоставлены результаты моделирования модификаций стохастического алгоритма и детерминированных алгоритмов.

Выводы. Результаты говорят о лучшем распределении неиспользуемой полосы пропускания при использовании алгоритма St1 в сравнении с классическим DRR.

Ключевые слова: стохастическая диспетчеризация, моделирование, очередь, коммутатор, качество обслуживания.

A. O. Semenov, N. N. Konnov, E. I. Gurin

ON USING ALGORITHMS OF STOCHASTIC DISPATCHING OF QUEUES IN A NETWORK SWITCHER

Abstract.

Background. The research deals with modern telecommunicational devices (switches). The subject of research is a set of modern telecommunicational devices queue dispatching systems. The purpose of the study is the creation of dispatching discipline that meets the requirements of QoS and the lack of determinism.

© Чикрин Д. Е., Егорчев А. А., Голоусов С. В., Савинков П. А., Тумаков Д. Н., 2018. Данная статья доступна по условиям всемирной лицензии Creative Commons Attribution 4.0 International License (http://creativecommons. org/licenses/by/4.0/), которая дает разрешение на неограниченное использование, копирование на любые носители при условии указания авторства, источника и ссылки на лицензию Creative Commons, а также изменений, если таковые имеют место.

Materials and methods. The paper is devoted to the evaluation of the efficiency of queue dispatching algorithms using simulation tools using the CPNTools package, which is based on the application of the mathematical apparatus of color hierarchical Petri nets.

Results. The results of modeling the modifications of the stochastic algorithm and deterministic algorithms are compared.

Conclusions. The results suggest a better allocation of unused bandwidth when using the St1 algorithm in comparison with the classic DRR.

Keywords: Stochastic dispatching system, queueing system, simulation system, CPN Tools, modeling.

На эффективность работы интеллектуальных коммутаторов с поддержкой качества обслуживания (QoS) оказывают значительное влияние реализуемые алгоритмы диспетчеризации очередей, которые, в свою очередь, оказывают существенное влияние на значение задержки передачи кадров и ее вариации (джиттер). Под термином «диспетчеризация очередей» обычно понимаются принятые алгоритмы выбора очередей на обслуживание и управление полосой пропускания, реализуемые как управление непрерывным обслуживанием выбранных очередей [1].

В коммутаторах Ethernet широко применяются циклические алгоритмы диспетчеризации (WRR - взвешенное циклическое обслуживание, DRR - дефицитное циклическое обслуживание), достоинствами которых являются исключение монополизации ресурса и простота реализации. В этих алгоритмах для каждого класса QoS-трафика выделяется своя очередь в буфере выходного порта, кадры обслуживаются в порядке возрастания их номеров, причем при отсутствии кадров в некоторой очереди алгоритм переключается на другую очередь. Количество данных, передаваемых из каждой очереди за один сеанс обслуживания, задается закрепленным за ней весом, пропорциональным выделенной для соответствующего класса полосой пропускания, причем в алгоритме WRR вес задает максимальное количество кадров, передаваемых из очереди за один сеанс обслуживания очереди, а в DRR - максимальное количество байтов данных, что позволяет более точно выделять требуемую полосу при разбросе размеров кадров в очередях [2, 3].

Как было показано в [4], недостатками циклических алгоритмов являются неконтролируемая величина джиттера коммутируемых кадров из-за разброса времени ожидания их обслуживания в различных очередях и зависимость задержки от назначенной полосы для классов трафика полосы пропускания, что вызвано детерминистским порядком обслуживания очередей и невозможностью перераспределения неиспользуемой полосы пропускания недогруженных каналов для расширения полосы пропускания перегруженных.

Известен алгоритм справедливого взвешенного обслуживания (WFQ), который лишен отмеченных выше недостатков, однако для реализации требует значительных ресурсов, что ограничивает его применение в коммутаторах Ethernet. Он чаще используется в реализациях мощных маршрутизаторов с поддержкой QoS [5].

В работе [6] были предложены динамические TSS и адаптивные алгоритмы циклической диспетчеризации DRR-TSS, учитывающие время ожидания и ограничивающие время непрерывного обслуживания очередей, которые обеспечивают меньший разброс значений джиттера при продвижении трафика различных классов QoS, а также более комфортные условия передачи тра-

фика в случае разбалансирования выделяемой для них полосы пропускания. К недостаткам можно отнести необходимость контроля времени нахождения кадров в очередях, что увеличивает затраты памяти и усложняет выбор очереди из-за необходимости поиска очереди с «самым старым» кадром.

В настоящей работе предлагается для управления очередями в коммутаторах использовать стохастические методы, основанные на принципах случайного выбора очереди, которые находят применение при диспетчеризации очередей в операционных системах или коммутаторах [7-9]. Формальное описание стохастического алгоритма диспетчеризации очередей и одна из возможных его реализаций приведены в работах [10-12]. В статье оценена эффективность алгоритмов диспетчеризации очередей средствами имитационного моделирования с использованием пакета CPNTools, который основан на применении математического аппарата цветных иерархических сетей Петри [13]. Сопоставлены результаты моделирования модификаций стохастического алгоритма и детерминированных алгоритмов. При этом были использованы модели сетей Петри, реализующих известные алгоритмы DRR и DRR-TSS [4, 14, 15].

Структура сети Петри, моделирующей алгоритм St1, основанный на принципах стохастического выбора очереди (правило выбора очереди - псевдослучайное равновероятное, выбор осуществляется только среди непустых очередей, производимые выборки возвратны, номинальные объемы обслуживания для каждой очереди различны и пропорциональны выделяемым долям полосы пропускания), - показана на рис. 1.

В сеть Пети, моделирующую алгоритм St1, были введены два условных типа маркеров:

1. «Информационные» маркеры, продвижение которых имитирует обработку кадра в коммутаторе:

• Множество цветов frm отражает структуру передаваемого кадра Ethernet и анализируется на очередном этапе обработки кадра в коммутаторе.

• Множество цветов frame представляет однонаправленный канал, который может быть либо занят передачей кадра (frm), либо свободен (avail), что позволяет выявлять и обрабатывать события, связанные с наличием или отсутствием кадра.

• Маркеры с цветом avail позволяют обеспечить безопасность сети Петри (один маркер в любой позиции) и решить проблему отсутствия в СPN Tools ингибиторных (запрещающих) дуг.

2. «Управляющие» маркеры, цвет которых отображает состояние обработки потока кадров в коммутаторе (размер очереди, количество переданных данных, признак очистки очереди и др.).

Задержки коммутации и сериаллизации коммутатора задаются на исходящем переходе выходного порта. За единицу модельного времени берется время передачи одного бита в входном/выходном портах.

В состав всех представленных моделей стохастических диспетчеров входят:

1. Генератор трафика (SetTraf) - блок, отвечающий за создание и передачу последующим блокам информации в формате, который можно представить в виде кортежа (цвета frame):

о 00

г

[

/рас эЧ \|СоипХ. )

1"

1гт1.

Рис. 1. Блок выходного порта

В формуле (1) number - номер кадра; src - идентификатор отправите-лия; dst - идентификатор получателя; qos - идентификатор класса обслуживания; szfrm - размер кадра; delay - время (задержка) начала формирования кадра.

2. Входной буфер (Bufferin) - позиция-буфер, содержащая накопленные кадры, еще не прошедшие через процедуру классификации.

3. Буфер выходного порта (Buffer) - блок, отвечающий за последовательную классификацию, хранение и продвижение кадров разнородного трафика к выходному каналу согласно заранее определенным правилам диспетчеризации.

4. Выходной буфер (Bufferout) - позиция-буфер, содержащая кадры, отобранные диспетчером и направляемые в выходной канал.

5. Узел передачи кадра в канал связи (OutPort).

6. Позиция-флаг свободного канала связи (OutPortFree).

7. Позиция-агрегатор кадров, поступивших в канал связи (output).

В состав блока Buffer всех представленных моделей стохастического диспетчера входят:

1) входная связующая позиция подсети (Bufferin);

2) классификатор кадров (Classifier);

3) Queue1In...Queue4In - позиции, содержащие кадры, прошедшие процедуру классификации и направляемые в очереди Queue1...Queue5;

4) подсети очередей, содержащие маркеры кадров и очередей, ожидающих обслуживания (Queue1...Queue4 и Sizequeue1out...Sizequeue3out) в виде двух кортежей (цветов frame, см. выше, и QUEUE PROPERTIES):

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

5) Ъе^1, ..., Ъе^4 - подсети, выделяющие полосу пропускания для трафика каждой очереди;

6) выходная связующая позиция подсети (ОмРо^Егее);

7) позиция Cycle, содержащая инструкции для блока randscan в виде кортежа (цвет QUEUE_RESTS):

где nGen - номер очереди, предлагаемой к объективному процессу выборки кадра; nCycleScan - номер цикла (фаза) обслуживания выборки;

8) входная связующая позиция подсети (Output) и другие блоки.

В рамках реализации блока rand scan осуществляется генерация псевдослучайного числа nRand согласно равномерному распределению. Каждой j-й очереди ставится в соответствие числовое значение nCritj : нуль или единица для пустых и непустых очередей соответственно, причем

(n, sz, nIsNtEmpty, nBytesTransmitted),

(nGen, nCycleScan),

nSummCritj+1 = nSummCritj + nCrit

j+1-

Затем вычисляется разность nRand и nSummCritj для каждой j-й очереди. Выбирается на обслуживание очередь с меньшим идентификационным номером, удовлетворяющая требованию знакоотрицательности вышеназванной разности.

Структура сети Петри, моделирующей алгоритм St3, основанный на принципах стохастического выбора очереди, согласно которому сеансы обслуживания очередей разделены на чередующиеся подсеансы первого типа (циклического обслуживания) и второго типа (стохастического обслужива-ний), причем номинальные объемы выборок первого типа различны и пропорциональны выделяемым долям полосы пропускания, сеанс обслуживания согласно выборке первого типа делится на равные по длительности подсеан-сы обслуживания, прерываясь на сеансы обслуживания согласно выборке второго типа, номинальные объемы обслуживания второго типа определяются величиной длины первого кадра в выбранной наугад очереди; правило выборок первого типа - циклическое (сходно с алгоритмом DRR), правило выборок второго типа - псевдослучайное, вероятности каждой из выборок одинаковы, производимые выборки возвратны, сходна со структурой сети Петри, моделирующей алгоритм St1 за исключением некоторых функциональных особенностей. Представленные изменения заложены в тело функции fun ChooseBand(i, n, sz, k, szfrm, nCycleNo, cnNoOfCycles) (рис. 2), осуществляющей разделение большого сеанса на подсеансы путем вызова функции. Краткое описание действий, производимых функцией, приведено в виде системы:

(i = n) з (z2 = 1) (y1 = Z1Z2) з (nCycleNo = 0),

(У2 = Z1 z2 )3(sz = ^ (sz > 0)3(1 = 1) (( - szfrm)> 0)з(2 = 1),

((nCycleNomod2) = 1) з (x3 = 1), (nCycleNo > (cnNoOfCycles -1)) 3 (x4 = 1), yy = X1X3 v X1X2 X3 v X1X3 X4 , yy2 = X1X2 X3 , ууз = X1X3 v X1X2 X3 X4 , rr1 = (i,nCycleNo +1), rr2 =(i,nCycleNo), ггз = (((i + 1)modciMaXQuNo),0),

(yyj = 1)3(rr = rrj),

где nCycleNo - номер текущего подсеанса, причем подсеансы с четным номером обслуживаются циклически (подсеансы первого типа), а подсеансы с нечетным номером обслуживаются случайно (подсеансы второго типа); Xj , yj,

zj, УУj, rr , rrj - управляющие сигналы, предназначенные для управления

полосой пропускания; rr является переменной, содержащей возвращаемое функцией значение.

s

ч

(D

а

(D

О «

о

w л w s -е л

W

о £

О &

&

о

4 о а

(D

5

л «

н

(D О

Ч О

С

о S Рч

Подсеть rand scan (далее - устройство стохастической диспетчеризации в составе коммутатора или маршрутизатора) очередей сетевого коммутатора с поддержкой качества обслуживания содержит: генератор псевдослучайных чисел; узел хранения постоянных величин (ПЗУ); узел подсчета вероятностей выбора очередей на обслуживание; узел сравнения величин; узел подсчета номера обслуживаемой очереди. На рис. 1 показана подсеть диспетчера, принимающая на свои входы длины очередей, а на выходы поступает единственная метка обслуживания очереди.

В качестве критерия оценки эффективности того или иного алгоритма часто используется оценка интегральных функций распределения значений джиттера трафика различных классов QoS для каждого из алгоритмов на одинаковом наборе входных данных. Входной трафик моделируется с помощью специальной сети Петри и представляет комбинацию потока кадров, принадлежащих с равной вероятностью четырем классам QoS и следующих через временные интервалы, распределенные по экспоненциальному закону со средним значением периода поступления, и квазирегулярный поток с редкими кадрами максимальной длительности. Коэффициент загрузки канала равен 0,8. Модельное время, выраженное в тактовых интервалах TI, равно 100 нс для Ethernet или 10 нс для FastEthernet. Случайная длина кадров имеет следующее распределение, соответствующее реальным сетям: по 25 % от всех кадров имеют минимальную и максимальную длину (соответственно TI 512 и 12176), длина остальных равномерно распределена в оставшемся диапазоне.

Кадры имеют равновероятные метки QoS от 0 до 7. Формируются четыре класса трафика, которым выделяются соответствующие очереди, и устанавливаются следующие значения полосы пропускания: очередь с QoS 0-1 - 10 %, QoS 2-3 - 20 %, QoS 4-5 - 30 %, QoS 6-7 - 40 % от выходной полосы, т.е. генерируемый трафик класса QoS 0-1 превышает выделенную для него полосу в два раза, QoS 2-3 согласован с выделенной полосой пропускания, а QoS 4-5 и 6-7 недогружают выделенные полосы. Параметры квот управления полосой пропускания заданы 1, 2, 3, 4 кадрами для WRR-алгоритмов, и 12176, 24352, 36528 и 48704TI для DRR-алгоритмов. Длительности подсеансов устанавливаются равными двум кадрам для WRR-TSS-алгоритмов, а для DRR-TSS-алгоритмов варьируется 3040, 12176, 24352TI.

В качестве критерия справедливости распределения реальной полосы пропускания принимается вариация средних значений джиттера трафика различных классов QoS.

Интегральные функции распределения значения джиттера трафика различных классов обслуживания для алгоритмов диспетчеризации, обеспечивающих управление полосой пропускания, представлены ниже для алгоритмов DRR (рис. 3,а), алгоритма DRR-TSS (с веременной селекцией кадров, рис. 3,б), алгоритма St1 (рис. 3,в) , алгоритма St3 (рис. 3,г).

На графиках, изображаемых на рис. 3, горизонтальная ось отображает задержку кадра, а горизонтальная ось - интегральную функцию распределения значения задержки трафика различных классов обслуживания для алгоритмов диспетчеризации, обеспечивающих управление полосой пропускания.

В табл. 1 и 2 продемонстрированы средние и максимальные значения джиттера по очередям на двух разных наборах входных данных (согласованные и несогласованные).

я

$

о m Ю '

о «

о о

ä

00

Н т

I

м

Н

сл

I

¿0 сл Н

„

a pi

Он

я Q

I

л va

л гз а Ä

<и Q Ё i

«

я я

(D

ч

(D

ч

(D «

а н

а ь

я S

я

©

о Я Рч

Таблица 1

Средние и максимальные значения дашттера по очередям

Несогласованные данные

311 ш БггТйй Бгг

Макс, задержка Ср. знач. Макс, задержка Ср. знач. Макс, задержка Ср. знач. Макс, задержка Ср. знач.

§й|§| 179892 22294 .276808 25492 135998 .21664 418825 34904

2ЙЙШ 23121 254538 2521'3 141382 22Ш ваш 22498

<Зо54-5 158529 23238 211852 21726 199584 26848 96584 31162

до86-7 443497 2X125 222937 29211 196943 27498 141439 21255

Вариация 284968 5830 64956 7484 63586 5:833 322241 13742

Таблица 2 Средние и максимальные значения джиттера по очередйм

Согласованные данные

ж ш БггТ.зз Бгг

Макс, задержка Ср. знач. .Макс, задержка Ср. знач. Макс, задержка Ср. знач. Макс, задержка Ср. знач.

до:м)-1 253725 Й935,4 193802 2.8738,27 149006 25959,8 274113 2899.8

доЭ2-з 245693 25ii52.ii 196212 21431,67 162224 26084,5 235586 29119

Оо84-5 238469 29100,9 213717 24703,69 162442 23690,.3 160710 22478

<3056-7 149534 25851.,:8 2:52426 2:8558,78 156474 2048.9,2 157244 23291

Вариация 104191 5165,46 58624 7306,599 13436 5595,20 116869 6641

Зафиксированы относительно низкие значения вариаций средних значений задержки по разным классам обслуживания у алгоритма St1. Вариация максимальных значений задержек по каждому классу обслуживания ниже у алгоритма DRR-TSS. Можно сделать вывод о незначительно лучшем перераспределении неиспользуемой полосы пропускания таким образом, чтобы снизить задержку в перегружаемых очередях за счет наиболее недогруженных, а также о явно лучшем распределении неиспользуемой полосы пропускания при использовании алгоритма St1 в сравнении с классическим DRR.

В табл. 1, 2 для стохастических алгоритмов зафиксированы вариации средних значений задержек, аналогичные неклассическому алгоритму DRR-TSS, и низкие средние значения вариаций задержек относительно классического циклического алгоритма на наборе несогласованных данных. Это говорит о перераспределении неиспользуемой полосы пропускания таким образом, чтобы снизить задержку в перегружаемых очередях за счет наиболее недогруженных.

Библиографический список

1. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы / В. Г. Олифер, Н. А. Олифер. - 4-е изд. - СПб. : Питер, 2010. - 943 с.

2. Кучерявый, Е. А. Управление трафиком и качество обслуживания в сети Интернет / Е. А. Кучерявый. - СПб. : Наука и техника, 2004. - 336 с.

3. Handbook on Scheduling from Theory to Applications / J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz. - Berlin Heidelberg : Springer-Verlag, 2007. - 654 p.

4. Кизилов, Е. А. Алгоритмы и модели диспетчеризации очередей в компьютерных сетях с поддержкой качества обслуживания : дис. ... канд. техн. наук / Кизилов Е. А. - Пенза, 2017. - 149 с.

5. Barreiros, M. QoS-enabled networks tools and foundations / М. Barreiros, P. Lundqvist. - Wiley : John Wiley & Sons, 2016. - 254 р.

6. Кизилов, Е. А. Моделирование адаптивной диспетчеризации очередей в коммутаторе с поддержкой QoS / Е. А. Кизилов, Н. Н. Коннов, Д. В. Патунин // Модели, системы, сети в экономике, технике, природе и обществе. - 2017. -№ 2 (22). - С. 170-183.

7. Intel Ethernet Switch FM5000/FM6000. 1 Gb/2.5 Gb/10 Gb/40 Gb Ethernet (GbE). L2/L3/L4 Chip Datasheet. Revision 3.5. July 2017. 331496-002. - URL: https:// www.intel.ru/content/www/ru/ru/ethernet-products/switch-silicon/ethernet-switch-fm5000-fm6000-datasheet.html (дата обращения: 15.03.2018).

8. Patent EP 1887742 A1 System and process for QOS-based packet scheduling. - URL: https://worldwide.espacenet.com/publicationDetails/originalDocument (дата обращения: 15.03.2018).

9. Patent 5,247,677 U.S. STOCHASTIC PRIORITY-BASED TASK SCHEDULER. -URL: http://patft.uspto.gov/netacgi/nph-Parser (дата обращения: 15.03.2018).

10. Коннов, Н. Н. Стохастический подход к диспетчеризации очередей в коммутаторах / Н. Н. Коннов, А. О. Семенов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2016. - № 3 (39). - С. 72-83.

11. Семенов, А. О. Стохастический подход к диспетчеризации очередей / А. О. Семенов // Современные инструментальные системы, информационные технологии и инновации : сб. ст. XII Междунар. науч.-техн. конф. (г. Курск, 12-16 мая 2015 г.). - Курск : ЮЗГУ, 2015. - С. 331-333.

12. Семенов, А. О. Имитационная модель устройства, реализующего стохастическую диспетчеризацию очередей коммутатора / А. О. Семенов // Свидетельство о государственной регистрации программы для ЭВМ, заявка № 2017663456. -зарег. 04.12.2007.

13. Jensen, K. Colored Petri Nets - Basic Concepts, Analysis Methods and Practical Use / K. Jensen. - Berlin : Springer-Verlag, 1997. - Vol. 1-3. - 673 p.

14. Никишин, К. И. Генератор трафика Ethernet на основе цветных сетей Петри / К. И. Никишин, Н. Н. Коннов // Модели, системы, сети в экономике, технике, природе и обществе. - 2016. - № 1 (17). - С. 299-307.

15. Семенов, А. О. Моделирование алгоритма стохастической диспетчеризации очередей в пакете / А. О. Семенов, Н. Н. Коннов // Новые информационные технологии и системы (НИТиС-2017) : сб. науч. ст. XI Междунар. науч.-практ. конф. (г. Пенза, 22-24 ноября 2017 г.). - Пенза : Изд-во ПГУ, 2017. - С. 133-135.

References

1. Olifer V. G., Olifer N. A. Komp'yuternye seti. Printsipy, tekhnologii, protokoly [Computer networks. Principles, technologies, protocols]. 4th ed. Saint-Petersburg: Piter, 2010, 943 p.

2. Kucheryavyy E. A. Upravlenie trafikom i kachestvo obsluzhivaniya v seti Internet [Traffic management and service quality on the Internet]. Saint-Petersburg: Nauka i tekhnika, 2004, 336 p.

3. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling from Theory to Applications. Berlin Heidelberg: Springer-Verlag, 2007, 654 p.

4. Kizilov E. A. Algoritmy i modeli dispetcherizatsii ocheredey v komp'yuternykh setyakh s podderzhkoy kachestva obsluzhivaniya: dis. kand. tekhn. nauk [Algorithms and models of queues dispatching in computer networks maintaining the quality of service: dissertation to apply for the degree of the candidate of engineering sciences]. Penza, 2017, 149 p.

5. Barreiros M., Lundqvist P. QoS-enabled networks tools and foundations. Wiley : John Wiley & Sons, 2016, 254 p.

6. Kizilov E. A., Konnov N. N., Patunin D. V. Modeli, sistemy, seti v ekonomike, tekhnike, prirode i obshchestve [Models, systems, networks in economy, technology, nature and society]. 2017, no. 2 (22), pp. 170-183.

7. Intel Ethernet Switch FM5000/FM6000. 1 Gb/2.5 Gb/10 Gb/40 Gb Ethernet (GbE). L2/L3/L4 Chip Datasheet. Revision 3.5. July 2017. 331496-002. Available at: https://www.intel.ru/content/www/ru/ru/ethernet-products/switch-silicon/ethernet-switch-fm5000-fm6000-datasheet.html (accessed March 15, 2018).

8. Patent EP 1887742 A1 System and process for QOS-based packet scheduling. Available at: https://worldwide.espacenet.com/publicationDetails/originalDocument (accessed March 15, 2018).

9. Patent 5,247,677 U.S. STOCHASTIC PRIORITY-BASED TASK SCHEDULER. Available at: http://patft.uspto.gov/netacgi/nph-Parser (accessed March 15, 2018).

10. Konnov N. N., Semenov A. O. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2016, no. 3 (39), pp. 72-83.

11. Semenov A. O. Sovremennye instrumental'nye sistemy, informatsionnye tekhnologii i innovatsii: sb. st. XII Mezhdunar. nauch.-tekhn. konf. (g. Kursk, 12-16 maya 2015 g.) [Modern instrument systems, information technologies and innovations: proceedings of XII International scientific and technical conference (Kursk, May 12th-16th 2015)]. Kursk: YuZGU, 2015, pp. 331-333.

12. Semenov A. O. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM, zayavka № 2017663456 [Certificate of state registration of computer software, application № 2017663456].

13. Jensen K. Colored Petri Nets - Basic Concepts, Analysis Methods and Practical Use. Berlin: Springer-Verlag, 1997, vol. 1-3, 673 p.

14. Nikishin K. I., Konnov N. N. Modeli, sistemy, seti v ekonomike, tekhnike, prirode i ob-shchestve [Models, systems, networks in economy, technology, nature and society]. 2016, no. 1 (17), pp. 299-307.

15. Semenov A. O., Konnov N. N. Novye informatsionnye tekhnologii i sistemy (NITiS-2017): sb. nauch. st. XI Mezhdunar. nauch.-prakt. konf. (g. Penza, 22-24 noyabrya 2017 g.) [New information technologies and systems 2017: proceedings of XI international scientific and practical conference (Penza, November 22nd - 24th, 2017)]. Penza: Izd-vo PGU, 2017, pp. 133-135.

Семенов Андрей Олегович аспирант, Пензенский государственный университет

E-mail: andre20071@yandex.ru

Коннов Николай Николаевич

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

E-mail: knn@pnzgu.ru

Гурин Евгений Иванович доктор технических наук, профессор, кафедра вычислительной техники, Пензенский государственный университет

E-mail: gurin2@yandex.ru

Semenov Andrey Olegovich Postgraduate student, Penza State University

Konnov Nikolay Nikolaevich Candidate of engineering sciences, professor, sub-department of computer engineering, Penza State University

Gurin Evgeniy Ivanovich Doctor of engineering sciences, professor, sub-department of computer engineering, Penza State University

УДК 005.7 Семенов, А. О.

Об использовании алгоритмов стохастической диспетчеризации очередей в сетевом коммутаторе / А. О. Семенов, Н. Н. Коннов, Е. И. Гурин // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2018. - № 4 (48). - С. 105-117. - БОТ 10.21685/2072-3059-2018-4-10.