Способ вероятностного взвешенного справедливого обслуживания очередей и устройство его реализующее

Изобретения относится к способу справедливого обслуживания очередей в маршрутизаторах транспортной сети связи. Технический результат - уменьшение сложность вычислений при поддержки большого количества классов или потоков обслуживания. Устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных Формируют все варианты (комбинации) активных очередей. Рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM). Формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания. Принимают потоки приоритетного трафика данных на входные порты устройства. Классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. Маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации. Помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, проверяют текущее состояние выходного порта устройства. Проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей. Генерируют случайное число, равномерно распределенное в интервале от 0 до 1. Выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM). Передают пакет в выходной порт устройства, обновляют текущее состояние выходного порта устройства. 2 н. и 1 з.п. ф-лы, 9 ил.

 

Область техники

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

Уровень техники

В настоящее время с развитием глобальной сети Интернет и предоставления пользователям широкого круга мультимедийных услуг важным вопросом является обеспечение качества обслуживании сетевого трафика (Quality of Service, QoS). При обеспечении качества обслуживания в транспортных сетях связи на базе протокола IP множество потоков трафика данных предъявляют различные требования по качеству обслуживания и соответственно разделяют ресурсы маршрутизатора транспортной сети связи. На сегодняшний день в глобальной сети Интернет используется механизм дифференцированного обслуживания, который позволяет «справедливо» распределить ресурсы маршрутизатора транспортной сети связи между отдельными классами трафика и обеспечить приоритетное обслуживание некоторой его части. Дифференцированное обслуживание предполагает разделение всего трафика на несколько классов на основе требований к обслуживанию, предъявляемых каждым из них.

Современная транспортная сеть связи с коммутацией пакетов включает множество узлов (маршрутизаторов, коммутаторов, хостов и т.д.), соединенных каналами связи. Каждый маршрутизатор имеет от 1 до n входных портов, к которым подключены входящие каналы связи, и от 1 до n выходных портов, к которым подключены исходящие каналам связи. При этом маршрутизатор является общим ресурсом транспортной сети связи. Известна проблема, связанная с выделением ограниченного количества совместно используемых ресурсов (буферной памяти и пропускной способности выходного порта) для конкурирующих пользователей, приложений и классов обслуживания. Дисциплина планирования очереди позволяет управлять доступом к фиксированной величине пропускной способности выходного порта, выбирая следующий пакет, который передается по порту. Существует много различных дисциплин планирования очередей, каждая из которых пытается найти правильный баланс между сложностью, контролем и справедливостью. Дисциплина планирования очередей, поддерживаемая поставщиками маршрутизаторов, зависит от реализации, что означает отсутствие реальных отраслевых стандартов. Тем не менее, поставщик иногда ссылается на свою собственную реализацию в качестве стандарта. Сложность с признанием любой реализации в качестве стандарта заключается в том, что каждый поставщик сочетает в себе функции из ряда известных общих дисциплин планирования очередей для обеспечения общей функциональности, которая необходима их клиентам для управления перегрузкой выходного порта.

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

Первые маршрутизаторы использовали планировщик First-in First-out (FIFO) «первый - пришел, первый - ушел» на каждом выходном порту. В FIFO на каждом выходном порту поддерживается одна очередь. Когда поступает новый пакет, то он помещается в конец очереди и пока очередь не пуста, маршрутизатор передает пакеты из очереди, принимая пакет от начала очереди (т.е. принимая «самый старый» пакет). Таким образом, FIFO предоставляет простой сервис наилучших усилий для всех приложений. FIFO имеет ряд серьезных недостатков. Во-первых, «жадный источник», который отправляет пакеты с чрезвычайно высокой битовой скоростью, может вытеснить другие источники и получить большую пропускную способность канала связи, чем другие источники. Во-вторых, если несколько более коротких пакетов находятся позади очень длинных пакетов, то схема FIFO приводит к большей средней задержке (на пакет), чем, если бы более короткие пакеты были переданы до более длинного пакета. В-третьих, в соответствии со схемой FIFO нет никаких механизмов для обеспечения качества обслуживания трафика данных от высокоприоритетных источников, например, чувствительных к задержкам (мультимедийного трафика).

Для обеспечения гарантий по задержкам может быть использован планировщик с приоритетами (Priority queuing, PQ). В классическом планировщике PQ пакеты сначала классифицируются системой, а затем помещаются в различные приоритетные очереди. Пакеты забираются на обслуживание из очереди только в том случае, если все очереди с более высоким приоритетом пустые. В каждой приоритетной очереди пакеты обслуживаются в порядке FIFO. Достоинством данного планировщика является простота реализации и возможность обеспечения низкой задержки для высокоприоритетного трафика данных. Недостатком является отсутствие возможности исключения влияния потоков друг на друга. Если высокоприоритетный трафик данных будет постоянно поступать в очередь с высокой интенсивностью, то трафик данных, поступающий в другие очереди, будет заблокирован.

Для устранения недостатков планировщиков FIFO и PQ была разработана дисциплина планирования очередей - взвешенное справедливое обслуживание очереди (Weighted Fair Queuing, WFQ). WFQ поддерживает справедливое распределение полосы пропускания для пакетов переменной длины с помощью аппроксимации обобщенной системы совместного использования процессоров (Generalized Processor Sharing, GPS). GPS - это идеальный планировщик, который обеспечивает каждому потоку гарантированную скорость передачи битов (пропускную способность) и справедливо распределяет избыточную полосу пропускания между потоками в соответствии с их относительными весами полосы пропускания (см., Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет. - СПб. Наука и Техника, 2004. - 152 с.). В результате GPS может обеспечить сквозные задержки и гарантии справедливости для приоритетных потоков трафика данных до тех пор, пока потоки не превышают выделенную долю пропускной способности исходящего канала связи. К сожалению, дисциплина GPS неосуществима на практике, потому что обслуживает бит за один раз (такт). Реальный планировщик должен завершить обслуживание всего пакета из очереди, прежде чем он перейдет к следующей очереди.

Серьезная проблема WFQ заключается в том, что моделирование GPS может предсказать, что многие пакеты могут в конечном итоге иметь одно и то же виртуальное время окончания. Обновление функции виртуального времени между двумя последовательными поступлениями пакетов может потребовать большого количества вычислений. В частности, если в канале связи одновременно передаются N активных сеансов (потоков трафика данных), то обновление виртуального времени может повлечь за собой вычисление O(N) сеансов или очередей. Количество активных потоков может быть очень большим. Например, могут существовать десятки тысяч или даже сотни тысяч очередей, использующих один канал связи. Это приводит к пропорционально большому количеству вычислений. Эта проблема называется итеративным удалением.

Из-за высокой сложности, связанной с моделированием системы GPS, за последнее время были предложены различные решения данной проблемы. Для упрощения расчетов виртуального времени было предложено множество методов. Некоторые из таких методов - самосинхронизированная справедливая очередь (Self-Clocked Fair Queuing, SCFQ), «виртуальные часы» (Virtual Clock, VC), справедливая очередь начального времени (Start-time Fair Queuing, SFQ), фреймовая справедливая очередь (Frame-Based Fair Queuing, FFQ), самосинхронизированная справедливая очередь с минимальной задержкой (Minimum-Delay Self-Clocked Fair Queuing, MD-SCFQ) и планирование дискретной скорости (Discrete-Rate, DR). В общем случае такие упрощающие подходы приводят к снижению справедливости (изоляция потока), либо к увеличению границы задержки или не решают проблему повторяющегося удаления.

Известно устройство «Планировщик взвешенного справедливого обслуживания» (патент US 7461159 В2 от 2.12.2008 г.), который использует моделирование GPS для определения порядка обслуживания объектов, использует новую динамическую структуру данных со сложным, но простым механизмом обновления указателей. Предпочтительные варианты планировщика выполняют фиксированный объем работы на одно событие планирования. Событие планирования может быть либо вычислением новой виртуальной метки времени завершения при новом поступлении в планировщик, либо определением того, какие объекты должны покинуть систему GPS, поскольку их метка времени завершения истекла. Такой планировщик может использоваться при планировании пакетов в устройстве обработки пакетов, таком как маршрутизатор, планировании доступа программных процессов к компьютерному процессору или тому подобном. Планировщик может реализовать взвешенную справедливую очередь (WFQ).

Известен способ «Справедливое обслуживание очередей с использованием динамических весов (DWFQ)» (патент US 7023866 В2 от 4.04.2006 г.) включающий в себя этапы: запрос входящих пакетов в очередях, связанных с соответствующими классами обслуживания; передача исходящих пакетов из указанных очередей в соответствии с расписанием, определяемым весами, связанными с классами обслуживания, используемыми планировщиком очередей; а также динамическое изменение весов в реальном времени, приводящее к тому, что размер очереди для каждого класса обслуживания перемещается к целевому значению, при котором выполняется задержка передачи, связанная с классом обслуживания.

Известно устройство «Формирователь общей взвешенной справедливой очереди (WFQ)» (патент US 8638664 В2 от 28.01.2014 г.), включающее в себя порт, буфер, модуль управления потоком и модуль дифференциации услуг. Порт сконфигурирован для отправки и приема пакета, причем порт соединен с сетевым объектом. Буфер сконфигурирован для хранения пакета. Модуль управления потоком сконфигурирован для управления передачей пакета внутри сетевого устройства. Модуль дифференциации обслуживания соединен с буфером и модулем управления потоком. Модуль дифференциации услуг сконфигурирован для регулирования хранения пакета в буфере и для регулирования передачи пакета от сетевого устройства к сетевому объекту. Модуль дифференциации услуг также сконфигурирован для определения избыточной полосы пропускания, доступной внутри сетевого устройства, и для распределения избыточной полосы пропускания для передачи пакета сетевому объекту.

Наиболее близким по технической сущности к заявляемому способу и выбранным в качестве прототипа является «Способ и устройство для выполнения взвешенного планирования очередей с использованием набора коэффициентов справедливости» (патент US 10291540 В2 от 14.05.2019 г.), заключающийся в том, что осуществляют прием пакетных данных из нескольких портов источника; классификацию пакетных данных на основе нескольких портов источника и связанных с ними портов назначения; сортировку пакетных данных по нескольким очередям в буфере; планирование каждой из множества очередей для передачи на основе временного веса каждой из множества очередей, который вычисляется на основе набора факторов справедливости, причем набор факторов справедливости включает в себя: бит валидности соответствующей очереди, вес приоритета соответствующей очереди, идентификацию первой позиции, указывающую на позицию соответствующей очереди, и идентификацию второй позиции, указывающую на позицию последней запланированной очереди с наивысшим приоритетом из предыдущего раунда, планирование далее включает выбор из по меньшей мере двух очередей с одинаковым максимальным весом приоритета, и при этом дополнительная сумма добавляется к временному весу соответствующей очереди, если идентификация первой позиции указывает на более низкую позицию, чем идентификация второй позиции, и при этом дополнительная сумма равна количеству очередей, выбранных из по меньшей мере двух очередей с одинаковым максимальным весом приоритета; и обновление статического состояния соответствующей очереди из нескольких очередей, реагирующих на пакет данных, вводимый в соответствующую очередь или выводимый из соответствующей очереди; отправка выходных пакетных данных, снятых с очереди планировщика, к месту назначения.

Наиболее близким по технической сущности к заявляемому устройству и выбранным в качестве прототипа является «Система для выполнения взвешенного планирования очередей с использованием набора коэффициентов справедливости» (патент US 10291540 В2 от 14.05.2019 г.), содержащая: по меньшей мере один процессор; по меньшей мере один материальный нетранзитивный машиночитаемый носитель информации, хранящий инструкции, которые при выполнении по меньшей мере одним процессором заставляют систему выполнять способ использования планировщика для обработки запросов, включающий: прием пакетных данных из нескольких портов источника; классификацию пакетных данных на основе нескольких портов источника и портов назначения, связанных с ними; сортировку пакетных данных в несколько очередей в буфере; планирование каждой из множества очередей для передачи на основе временного веса каждой из множества очередей, который вычисляется на основе набора факторов справедливости, причем набор факторов справедливости включает в себя: бит валидности соответствующей очереди, вес приоритета соответствующей очереди, идентификацию первой позиции, указывающую на позицию соответствующей очереди, и идентификацию второй позиции, указывающую на позицию последней запланированной очереди с наивысшим приоритетом из предыдущего раунда, планирование далее включает выбор из по меньшей мере двух очередей с одинаковым максимальным весом приоритета, и при этом временный вес соответствующей очереди увеличивается на дополнительную сумму, если идентификация первой позиции указывает на более низкую позицию, чем идентификация второй позиции, и при этом дополнительная сумма равна количеству очередей, выбранных из по меньшей мере двух очередей с одинаковым максимальным весом приоритета; и обновление статического состояния соответствующей очереди из нескольких очередей, реагирующих на пакет данных, вводимый в соответствующую очередь или выводимый из соответствующей очереди; и отправка выходных пакетных данных, снятых с очереди планировщика, к месту назначения.

Технической проблемой является высокая сложность вычислений при поддержки большого количества классов или потоков обслуживания. Еще одной технической проблемой является низкая точность аппроксимации обобщенной системы совместного использования процессоров (GPS).

Техническим результатом является уменьшение сложности вычислений при поддержки большого количества классов обслуживания за счет того, что дополнительно включены от 1 до n модулей вероятностного взвешенного справедливого обслуживания очередей, причем каждый включает модуль расчета вектора интенсивностей, модуль расчета вектора интервалов, модуль выбора пакета, генератор случайного числа, модуль формирования комбинаций активных очередей.

Еще одним техническим результатом является то, что настоящее изобретение позволяет более точно осуществить аппроксимацию обобщенной системы совместного использования процессоров (GPS). Данный технический результат достигается за счет того, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных, формируют все варианты (комбинации) активных очередей, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, на втором этапе проверяют текущее состояние выходного порта устройства, проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт устройства, обновляют текущее состояние выходного порта устройства.

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

Раскрытие изобретения

В заявленном способе эта техническая проблема решается тем, что в способе вероятностного взвешенного справедливого обслуживания очередей, заключающемся в том, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных, формируют все варианты (комбинации) активных очередей, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, на втором этапе принимают потоки приоритетного трафика данных на входные порты устройства, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты устройства на основании таблицы маршрутизации, помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, проверяют текущее состояние выходного порта устройства, проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт устройства, обновляют текущее состояние выходного порта устройства.

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

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

В заявленном устройстве эта задача решается тем, что устройство вероятностного приоритетного обслуживания очередей, содержащее от 1 до n входных портов для приема потоков приоритетного трафика данных, классификатор, выполненный с возможностью отнесения потоков трафика данных к классам в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, модуль маршрутизации, выполненный с возможностью продвижения пакета в выходной порт в соответствии с таблицей маршрутизации, от 1 до n модулей очередей для помещения пакетов в очередь соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета; измерения скорости поступления трафика данных и средней длины пакетов соответствующего класса, от 1 до n выходных портов для передачи потоков приоритетного трафика данных в канал связи, отличающийся тем, что дополнительно включены от 1 до n модулей вероятностного взвешенного справедливого обслуживания очередей, причем потоки приоритетного трафика данных поступают на входные порты, затем с входных портов потоки приоритетного трафика данных передаются на вход классификатора, выход классификатора соединен с входом модуля маршрутизации, с выхода модуля маршрутизации потоки приоритетного трафика данных поступают на вход соответствующего модуля очередей, с выхода модуля очередей потоки приоритетного трафика данных передаются в соответствующий модуль вероятностного взвешенного справедливого обслуживания очередей, с выхода модуля вероятностного взвешенного справедливого обслуживания очередей потоки приоритетного трафика данных поступают на выходные порты.

Согласно одному из частных вариантов реализации модуль вероятностного взвешенного справедливого обслуживания очередей содержит модуль расчета вектора интенсивностей, выполненный с возможностью расчета вектора интенсивностей обслуживания (WM), конфигурации параметров, как минимум, абсолютного веса для каждой очереди, скорости поступления потоков приоритетного трафика данных и среднего размера пакетов для каждого потока приоритетного трафика данных, модуль расчета вектора интервалов, выполненный с возможностью формирования вектора интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, модуль выбора пакета, выполненный с возможностью продвижения пакетов из множества очередей соответствующего класса в выходной порт, проверке и обновления текущего состояния выходного порта маршрутизатора, проверки наличия пакетов в очередях, выбора вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, выбора номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), генератор случайного числа, выполненный с возможностью генерации случайного числа, равномерно распределенного в интервале от 0 до 1, модуль формирования комбинаций активных очередей, выполненный с возможностью формирования всех комбинаций активных очередей, при этом все модули в устройстве соединены посредством общей внутренней шины AXI4, которая выступает в качестве средства обмена информацией между модулями.

Все модули могут быть реализованы по известной схеме, например, маршрутизатор Eltex ME 5000 (см. https://eltex-co.ru/catalog/provider_edge_router/marshrutizator_me5000).

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

Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленных способа вероятностного приоритетного обслуживания очередей и устройство его реализующее, отсутствуют. Следовательно, каждое из заявленных изобретений соответствует условию патентоспособности «новизна».

Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, каждое из заявленных изобретений соответствует условию патентоспособности «изобретательский уровень».

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

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

На фиг. 1 - схема работы способа вероятностного взвешенного справедливого обслуживания очередей;

на фиг. 2 - устройство вероятностного взвешенного справедливого обслуживания очередей;

на фиг. 3 - схема модуля вероятностного взвешенного справедливого обслуживания очередей;

на фиг. 4 - фрагмент транспортной сети связи в среде сетевого симулятора OMNet++;

на фиг. 5 - результаты имитационного моделирования, среднего времени ожидания пакетов в планировщиках WFQ, GPS и предлагаемого изобретения;

на фиг. 6 - результаты имитационного моделирования, среднего времени ожидания пакетов первого приоритета в планировщиках WFQ, GPS и предлагаемого изобретения;

на фиг. 7 - результаты имитационного моделирования, среднего времени ожидания пакетов второго приоритета в планировщиках WFQ, GPS и предлагаемого изобретения;

на фиг. 8 - результаты имитационного моделирования, среднего времени ожидания пакетов третьего приоритета в планировщиках WFQ, GPS и предлагаемого изобретения.

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

Реализация заявленного способа заключается в следующем (фиг. 1).

Первый этап.

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

102. Формируют все варианты (комбинации) активных очередей.

103. Рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM).

104. Формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания.

Второй этап.

105. Принимают потоки приоритетного трафика данных на входные порты маршрутизатора.

106. Классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета.

107. Маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации.

108. Помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета.

109. Проверяют текущее состояние выходного порта маршрутизатора.

110. Проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей.

111. Осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей.

112. Генерируют случайное число, равномерно распределенное в интервале от 0 до 1.

113. Выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM).

114. Передают пакет в выходной порт маршрутизатора.

115. Обновляют текущее состояние выходного порта маршрутизатора.

Заявленный способ вероятностного взвешенного справедливого обслуживания очередей позволяет достичь указанного технического результата устранение дискриминации низкоприоритетного трафика данных, а также уменьшение среднесетевой задержки пакетов для низкоприоритетного трафика за счет того, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных, формируют все варианты (комбинации) активных очередей, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, на втором этапе проверяют текущее состояние выходного порта маршрутизатора, проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт маршрутизатора, обновляют текущее состояние выходного порта маршрутизатора.

Устройство вероятностного взвешенного справедливого обслуживания очередей (фиг. 2) состоит из от 1 до n входных портов, классификатора 21, модуля маршрутизации 22, от 1 до n модулей очередей 23, от 1 до n модулей вероятностного взвешенного справедливого обслуживания очередей 24, от 1 до n выходных портов, при этом потоки приоритетного трафика данных поступают на входные порты, затем с входных портов потоки приоритетного трафика данных передаются на вход классификатора, выход классификатора соединен с входом модуля маршрутизации, с выхода модуля маршрутизации потоки приоритетного трафика данных поступают на вход соответствующего модуля очередей, с выхода модуля очередей потоки приоритетного трафика данных передаются в соответствующий модуль вероятностного взвешенного справедливого обслуживания очередей, с выхода модуля вероятностного взвешенного справедливого обслуживания очередей потоки приоритетного трафика данных поступают на выходные порты.

Входные порты от 1 до n выполнены с возможностью приема потоков приоритетного трафика данных.

Классификатор 21 выполнен с возможностью отнесения потоков трафика данных к классам в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета.

Модуль маршрутизации 22, выполненный с возможностью продвижения пакета в выходной порт в соответствии с таблицей маршрутизации.

Модули очередей 23 (от 1 до n) выполнены с возможностью помещения пакетов в очередь соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета; измерения скорости поступления трафика данных и средней длины пакетов соответствующего класса.

Выходные порты от 1 до n выполнены с возможностью передачи потоков приоритетного трафика данных в канал связи.

Модули вероятностного взвешенного справедливого обслуживания очередей 24 (от 1 до n), каждый из которых содержит модуль расчета вектора интенсивностей 24.1, модуль расчета вектора интервалов 24.2, модуль выбора пакета 24.3, генератор случайного числа 24.4, модуль формирования комбинаций активных очередей 24.5 при этом все модули в устройстве соединены посредством общей внутренней шины AXI4, которая выступает в качестве средства обмена информацией между модулями.

Модуль расчета вектора интенсивностей 24.1, выполненный с возможностью расчета вектора интенсивностей обслуживания (WM), конфигурации параметров, как минимум, абсолютного веса для каждой очереди, скорости поступления потоков приоритетного трафика данных и среднего размера пакетов для каждого потока приоритетного трафика данных.

Модуль расчета вектора интервалов 24.2, выполненный с возможностью формирования вектора интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания.

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

Генератор случайного числа 24.4, выполненный с возможностью генерации случайного числа, равномерно распределенного в интервале от 0 до 1.

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

Модуль восстановления приоритетов 27.7, выполненный с возможностью восстановления исходного приоритета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом таблицы соответствия.

Все модули могут быть реализованы по известной схеме, например, маршрутизатор Eltex ME 5000 (см. https://eltex-co.ru/catalog/provider_edge_router/marshrutizator_me5000).

Устройство работает следующим образом.

На первом этапе конфигурируют модуль вероятностного взвешенного справедливого обслуживания очередей 24. В модуле расчета вектора интенсивностей 24.1 устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных. На основании этих данных в модуле формирования комбинаций активных очередей формируют все варианты (комбинации) активных очередей. В модуле расчета вектора интенсивностей 24.1 рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM). В модуле расчета вектора интервалов 24.2 формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания.

На втором этапе принимают потоки приоритетного трафика данных на входные порты маршрутизатора и затем передают в классификатор. В классификаторе 21 классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. После классификатора 21 потоки приоритетного трафика данных поступают в модуль маршрутизации, где осуществляется продвижение пакетов в соответствии с таблицей маршрутизации на соответствующий модуль очередей. В модуле очередей 23 помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. Модуль выбора пакета 24.3 проверяет текущее состояние выходного порта маршрутизатора и проверяет наличие пакетов в очередях соответствующего модуля очередей 23, если очереди не пусты, то в модуле формирования комбинаций активных очередей 24.5 формируют вектор активных очередей, а затем осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей. Одновременно с этим в генераторе случайного числа 24.4 генерируют случайное число, равномерно распределенное в интервале от 0 до 1. С учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM) в модуле выбора пакета выбирают номер активной очереди соответствующего модуля очередей 23 и передают пакет в выходной порт маршрутизатора. После этого в модуле выбора пакета 24.3 обновляют текущее состояние выходного порта маршрутизатора.

Интерактивный процесс функционирования устройства следует рассмотреть на примере. Допустим, в устройство поступают три потока приоритетного трафика данных на разные входные порты, которые необходимо передать на один выходной порт. Скорость поступления пакетов от первого источника - 30 Кбит/с, от второго источника - 21 Кбит/с, от третьего источника - 14,7 Кбит/с. Средний размер пакетов от всех источников равен 500 байт. На выходном порту установлена пропускная способность равная 31,4 Кбит/с.

На первом этапе в устройстве на выходном порту конфигурируют модуль вероятностного взвешенного справедливого обслуживания очередей 24. В модуле вероятностного взвешенного справедливого обслуживания очередей 24, а именно, в модуле выбора пакетов 24.3 устанавливают следующие веса - вес первого потока трафика данных , вес второго потока трафика данных , вес третьего потока трафика данных . На основе абсолютных весов для каждой очереди, скорости поступления потоков приоритетного трафика данных и среднего размера пакетов для каждого потока приоритетного трафика данных в модуле формирования активных очередей формируют варианты (комбинации) активных очередей. Для представленных потоков приоритетного трафика данных получаются следующие варианты (комбинации) активных очередей -

В модуле расчета вектора интенсивностей 24.1 рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), который представлен в таблице 1.

Таблица 1 - Вектор интенсивностей обслуживания (WM)

Варианты (комбинации) активных очередей	Вектор интенсивностей обслуживания (WM)

В модуле расчета вектора интервалов 24.2 для каждого вектора интенсивностей обслуживания формируют вектор интервалов интенсивностей обслуживания (IntWM), представленный в таблице 2.

Таблица 2 - Вектор интервалов интенсивностей обслуживания (IntWM)

Вектор интенсивностей обслуживания (WM)	Вектор интервалов интенсивностей обслуживания (IntWM)

После того как будет сконфигурирован модуль вероятностного взвешенного справедливого обслуживания очередей 24 на входные порты устройства поступают 3 потока приоритетного трафика данных. В классификаторе осуществляется отнесения потоков трафика данных к соответствующим классам на основании значения поля ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. В модуле маршрутизации 22 все потоки трафика данных перенаправляются на выходной порт, который соединен каналом связи с встречным маршрутизатором. Из модуля маршрутизации 22 пакеты приоритетного трафика данных поступают в модуль очередей 23, в котором помещают пакеты в очередь соответствующего класса на основе значений в поле ToS Precedence заголовка IP пакета, либо в поле DSCP заголовка IP пакета. Модуль выбора пакета 24.3 проверяет наличие пакетов в очередях модуля очередей 23, если очереди не пусты, то в модуле формирования комбинаций активных очередей 24.5 формируют вектор активных очередей. Далее в модуле выбора пакета 24.3 осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей (таблица 2). Одновременно с этим в генераторе случайного числа 24.4 генерируют случайное число, равномерно распределенное в интервале от 0 до 1.

В модуле выбора пакета 24.3 выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания и передают пакет в выходной порт маршрутизатора. После обслуживания пакета модуль выбора пакета 24.3 обновляет текущее состояние выходного порта устройства.

Благодаря новой совокупности существенных признаков достигается указанный технический результат за счет дополнительно введенных от 1 до n модулей вероятностного взвешенного справедливого обслуживания очередей 24, при этом каждый модуль вероятностного взвешенного справедливого обслуживания очередей 24 содержит модуль расчета вектора интенсивностей 24.1, модуль расчета вектора интервалов 24.2, модуль выбора пакета 24.3, генератор случайного числа 24.4, модуль формирования комбинаций активных очередей 24.5.

Правомерность теоретических предпосылок проверялась на фрагменте транспортной сети связи в среде сетевого симулятора OMNet++ при следующих исходных данных (фиг. 4):

- число маршрутизаторов в транспортной сети связи

- число источников информации

- скорость поступления пакетов первого потока трафика данных Кбит/с;

- скорость поступления пакетов второго потока трафика данных Кбит/с;

- скорость поступления пакетов третьего потока трафика данных Кбит/с;

- средняя длина пакетов всех потоков трафика данных бит;

- пропускная способность канала связи Кбит/с.

Анализ результатов имитационного моделирования (фиг. 5-8) показывает, что среднее время ожидания пакетов в очереди планировщика GPS и в предложенной группе изобретений практически не отличаются во всем диапазоне коэффициента использования канала связи. Значения среднего времени ожидания пакетов в очереди планировщика WFQ лежат ниже значений среднего времени ожидания пакетов в очереди планировщика GPS в диапазоне коэффициента использования канала связи от 0,6 до 1. Тем самым предложенная группа изобретений позволяет более точно аппроксимировать обобщенную систему совместного использования процессоров (GPS).

Вычислительная сложность планировщика WFQ равна O(N), где N - это число очередей (см. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет. - СПб. Наука и Техника, 2004. - 187 с). В предлагаемой группе изобретений вычислительная сложность уменьшается за счет того, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных, формируют все варианты (комбинации) активных очередей, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, на втором этапе принимают потоки приоритетного трафика данных на входные порты устройства, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации, помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, проверяют текущее состояние выходного порта маршрутизатора, проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт устройства, обновляют текущее состояние выходного порта устройства.

На фигуре 9 А) показано, что для комбинации активных очередей то есть в трех очередях находятся пакеты соответствующего класса, вектор интенсивностей обслуживания WM равен и вектор интервалов интенсивностей обслуживания IntWM равен В случае, если выходной порт устройства свободен, то выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM). Если случайное число попало в диапазон от 0 до 0,51, то передают пакет в выходной порт устройства из очереди 1 класса. Если случайное число попало в диапазон от 0,51 до 0,816, то передают пакет в выходной порт устройства из очереди 2 класса. Если случайное число попало в диапазон от 0,816 до 1, то передают пакет в выходной порт устройства из очереди 3 класса.

На фигуре 9 Б) показано, что для комбинации активных очередей то есть в трех очередях находятся пакеты соответствующего класса, вектор интенсивностей обслуживания WM равен и вектор интервалов интенсивностей обслуживания IntWM равен В случае, если выходной порт устройства свободен, то выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM). Если случайное число попало в диапазон от 0 до 1, то передают пакет в выходной порт устройства из очереди 1 класса. Ввиду того, что диапазон попадания случайного числа для очередей 2 и 3 класса совпадает с диапазоном попадания случайного числа для очереди 1 класса, то они не рассматриваются.

На фигуре 9 В) показано, что для комбинации активных очередей то есть в трех очередях находятся пакеты соответствующего класса, вектор интенсивностей обслуживания WM равен и вектор интервалов интенсивностей обслуживания IntWM равен В случае, если выходной порт устройства свободен, то выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM). Если случайное число попало в диапазон от 0 до 0,735, то передают пакет в выходной порт устройства из очереди 1 класса. Если случайное число попало в диапазон от 0,735 до 1, то передают пакет в выходной порт устройства из очереди 3 класса. Ввиду того, что для очереди 2 класса диапазон попадания случайного числа совпадает с диапазоном попадания случайного числа для очереди 1 класса, то данная очередь не рассматриваются.

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

Заявленные способ вероятностного взвешенного справедливого обслуживания очередей и устройство его реализующее обеспечивают уменьшение сложности вычислений при поддержки большого количества классов или потоков обслуживания, а также позволяет более точно осуществить аппроксимацию обобщенной системы совместного использования процессоров (GPS) за счет того, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных в модуле расчета вектора интенсивностей 24.1, формируют все варианты (комбинации) активных очередей в модуле формирования комбинаций активных очередей 24.5, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM) в модуле расчета вектора интенсивностей 24.1, формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания в модуле расчета вектора интервалов 24.2, на втором этапе принимают потоки приоритетного трафика данных на входные порты маршрутизатора, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета в классификаторе 21, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации в модуле маршрутизации 22, помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета в модуле очередей 23, проверяют текущее состояние выходного порта маршрутизатора, проверяют наличие пакетов в очередях в модуле выбора пакета 24.3, если очереди не пусты, то формируют вектор активных очередей в модуле формирования комбинаций активных очередей 24.5, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей в модуле очередей 23, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, в генераторе случайного числа 24.4, выбирают номер активной очереди в модуле выбора пакета 24.3 с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт маршрутизатора из модуля выбора пакета 24.3, обновляют текущее состояние выходного порта маршрутизатора в модуле выбора пакета 24.3.

1. Устройство вероятностного взвешенного справедливого обслуживания очередей, содержащее от 1 до n входных портов для приема потоков приоритетного трафика данных, классификатор, выполненный с возможностью отнесения потоков трафика данных к классам в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, модуль маршрутизации, выполненный с возможностью продвижения пакета в выходной порт в соответствии с таблицей маршрутизации, от 1 до n модулей очередей для помещения пакетов в очередь соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета; измерения скорости поступления трафика данных и средней длины пакетов соответствующего класса, от 1 до n выходных портов для передачи потоков приоритетного трафика данных в канал связи, отличающееся тем, что дополнительно включены от 1 до n модулей вероятностного взвешенного справедливого обслуживания очередей, причем потоки приоритетного трафика данных поступают на входные порты, затем с входных портов потоки приоритетного трафика данных передаются на вход классификатора, выход классификатора соединен с входом модуля маршрутизации, с выхода модуля маршрутизации потоки приоритетного трафика данных поступают на вход соответствующего модуля очередей, с выхода модуля очередей потоки приоритетного трафика данных передаются в соответствующий модуль вероятностного взвешенного справедливого обслуживания очередей, с выхода модуля вероятностного взвешенного справедливого обслуживания очередей потоки приоритетного трафика данных поступают на выходные порты.

2. Устройство по п. 1, в котором модуль вероятностного взвешенного справедливого обслуживания очередей содержит модуль расчета вектора интенсивностей, выполненный с возможностью расчета вектора интенсивностей обслуживания (WM), конфигурации параметров, как минимум, абсолютного веса для каждой очереди, скорости поступления потоков приоритетного трафика данных и среднего размера пакетов для каждого потока приоритетного трафика данных, модуль расчета вектора интервалов, выполненный с возможностью формирования вектора интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, модуль выбора пакета, выполненный с возможностью продвижения пакетов из множества очередей соответствующего класса в выходной порт, проверке и обновления текущего состояния выходного порта маршрутизатора, проверки наличия пакетов в очередях, выбора вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, выбора номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), генератор случайного числа, выполненный с возможностью генерации случайного числа, равномерно распределенного в интервале от 0 до 1, модуль формирования комбинаций активных очередей, выполненный с возможностью формирования всех комбинаций активных очередей, при этом все модули в устройстве соединены посредством общей внутренней шины AXI4, которая выступает в качестве средства обмена информацией между модулями.

3. Способ вероятностного взвешенного справедливого обслуживания очередей, осуществляемый устройством по п. 1, заключающийся в том, что на первом этапе устанавливают абсолютный вес для каждой очереди, скорость поступления потоков приоритетного трафика данных и средний размер пакетов для каждого потока приоритетного трафика данных, формируют все варианты (комбинации) активных очередей, рассчитывают для каждого варианта (комбинации) активных очередей вектор интенсивностей обслуживания (WM), формируют вектор интервалов интенсивностей обслуживания (IntWM) для каждого вектора интенсивностей обслуживания, на втором этапе принимают потоки приоритетного трафика данных на входные порты устройства, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации, помещают в очередь пакеты трафика данных соответствующего класса в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, проверяют текущее состояние выходного порта устройства, проверяют наличие пакетов в очередях, если очереди не пусты, то формируют вектор активных очередей, осуществляют выбор вектора интервалов интенсивностей обслуживания с учетом вектора активных очередей, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, выбирают номер активной очереди с учетом случайного числа и вектора интервалов интенсивностей обслуживания (IntWM), передают пакет в выходной порт устройства, обновляют текущее состояние выходного порта устройства.