СПОСОБ ВЕРОЯТНОСТНОГО ПРИОРИТЕТНОГО ОБСЛУЖИВАНИЯ ОЧЕРЕДЕЙ И УСТРОЙСТВО ЕГО РЕАЛИЗУЮЩЕЕ Российский патент 2022 года по МПК H04L47/50 

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

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

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

В настоящее время с развитием глобальной сети Интернет и предоставления пользователям широкого круга мультимедийных услуг важным вопросом является обеспечение качества обслуживании сетевого трафика (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). Данный технический результат достигается за счет того, что устанавливают вес для каждой промежуточной очереди, принимают потоки приоритетного трафика данных на входные порты маршрутизатора, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации, помещают в промежуточную очередь пакеты приоритетного трафика данных соответствующего класса в соответствии с исходным полем ToS Precedence заголовка IP пакета, либо в соответствии с исходным полем DSCP заголовка IP пакета, измеряют скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса, формируют таблицу соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета, формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, изменяют исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы интервалов и случайного числа, передают пакет в приоритетную очередь в соответствии с изменённым полем ToS Precedence заголовка IP пакета, либо в соответствии с изменённым полем DSCP заголовка IP пакета, помещают в конец соответствующей приоритетной очереди пакеты трафика данных соответствующего класса в соответствии с изменённым полем ToS Precedence заголовка IP пакета, либо в соответствии с изменённым полем DSCP заголовка IP пакета, осуществляют обслуживание пакетов в приоритетных очередях планировщиком с приоритетами PQ, восстанавливают исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы соответствия, передают приоритетный трафика данных в выходной порт маршрутизатора.

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

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

В заявленном способе эта техническая проблема решается тем, что в способе справедливого вероятностного приоритетного обслуживания очередей заключающемся в том, что устанавливают вес для каждой промежуточной очереди. Принимают потоки приоритетного трафика данных на входные порты маршрутизатора. Классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. Маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации. Помещают в промежуточную очередь пакеты приоритетного трафика данных соответствующего класса в соответствии с исходным полем ToS Precedence заголовка IP пакета, либо в соответствии с исходным полем DSCP заголовка IP пакета. Измеряют скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса. Формируют таблицу соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета. Формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди. Генерируют случайное число, равномерно распределенное в интервале от 0 до 1. Изменяют исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы интервалов и случайного числа. Передают пакет в приоритетную очередь в соответствии с изменённым полем ToS Precedence заголовка IP пакета, либо в соответствии с изменённым полем DSCP заголовка IP пакета. Помещают в конец соответствующей приоритетной очереди пакеты трафика данных соответствующего класса в соответствии с изменённым полем ToS Precedence заголовка IP пакета, либо в соответствии с изменённым полем DSCP заголовка IP пакета. Осуществляют обслуживание пакетов в приоритетных очередях планировщиком с приоритетами PQ. Восстанавливают исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы соответствия. Передают приоритетный трафика данных в выходной порт маршрутизатора.

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

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

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

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

Согласно одному из частных вариантов реализации модуль вероятностного обслуживания содержит модуль промежуточных очередей, выполненный с возможностью помещения пакетов в очередь соответствующего класса в соответствии с исходным полем ToS Precedence заголовка IP пакета, либо в соответствии с исходным полем DSCP заголовка IP пакета; измерения скорости поступления потоков приоритетного трафика данных и средней длины пакетов соответствующего класса; изменения исходного приоритета пакета в поле ToS Precedence заголовка IP пакета, либо в поле DSCP заголовка IP пакета с учетом матрицы интервалов и случайного числа, модуль приоритетных очередей, выполненный с возможностью помещения пакетов в приоритетную очередь в соответствии с измененным полем ToS Precedence заголовка IP пакета, либо в соответствии с измененным полем DSCP заголовка IP пакета, генератор случайного числа, выполненный с возможностью генерации случайного числа, равномерно распределенного в интервале от 0 до 1, модуль формирования матрицы интервалов, выполненный с возможностью формирования матрицы интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов соответствующего класса и веса для каждой промежуточной очереди, модуль формирования таблицы соответствия, выполненный с возможностью формирования таблицы соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета, планировщик, выполненный с возможностью приоритетного обслуживание пакетов PQ, модуль восстановления приоритетов, выполненный с возможностью восстановления исходного приоритета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом таблицы соответствия, причем потоки приоритетного трафика данных поступают на первые k входов модуля промежуточных очередей, k+1 вход модуля промежуточных очередей соединен с генератором случайного числа, k+2 вход модуля промежуточных очередей соединен с модулем формирования матрицы интервалов, с первых k выходов модуля промежуточных очередей потоки приоритетного трафика данных поступают на m входов модуля приоритетных очередей, k+1 выход модуля промежуточных очередей соединен с модулем формирования таблицы соответствия, с m выходов модуля приоритетных очередей потоки трафика данных передаются на вход планировщика с приоритетами PQ, выход планировщика с приоритетами PQ соединен с первым входом модуля восстановления приоритетов, второй выход модуля формирования таблицы соответствия соединен с вторым входом модуля восстановления приоритетов, с выхода модуля восстановления приоритетов потоки приоритетного трафика данных передаются на выходной порт.

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

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

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

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

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

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

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

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

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

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

на фиг. 5 - схема расчёта добавочной части веса для поступающих потоков трафика данных;

на фиг. 6 - схема формирования матрицы интервалов и изменения приоритета пакетов трафика данных;

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

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

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

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

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

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

101. Устанавливают вес для каждой промежуточной очереди.

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

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

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

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

106. Измеряют скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса.

107. Формируют таблицу соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета.

108. Формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди.

В качестве примера поясним обобщенный алгоритм, который включает следующие шаги.

Шаг 1. Формируют матрицу с характеристиками потоков трафика данных , где - вектор-столбец скоростей поступления потоков трафика данных, - вектор-столбец среднего размера пакетов для каждого потока трафика данных, - вектор-столбец весов для каждого потока трафика данных.

Шаг 2. Пересчитывают скорости поступления потоков приоритетного трафика данных в значение интенсивности поступления пакетов для каждого потока трафика данных

, (1)

где - вектор-столбец интенсивности поступления пакетов для каждого потока трафика данных.

Шаг 3. Рассчитывают средний вес поступающих потоков трафика данных.

Шаг 4. Рассчитывают относительное значение интенсивности поступления пакетов для каждого потока трафика данных с учетом среднего веса поступающих потоков трафика данных.

Шаг 5. Сортируют в порядке не убывания относительные значения интенсивности поступления пакетов для каждого потока трафика данных.

Шаг 6. Рассчитывают добавочную часть веса для поступающих потоков трафика данных.

Шаг 7. Рассчитывают матрицу интервалов с учетом интенсивности поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждого потока трафика данных.

Шаг 8. Сортируют в порядке не убывания приоритета относительные значения интенсивности поступления пакетов для каждого потока трафика данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

Модули вероятностного обслуживания 23 (от 1 до n), каждый из которых содержит модуль промежуточных очередей 23.1, генератор случайного числа 23.2, модуль формирования матрицы интервалов 23.3, модуль приоритетных очередей 23.4, модуль формирования таблицы соответствия 23.5, планировщик 23.6, модуль восстановления приоритетов 23.7, причем потоки приоритетного трафика данных поступают на первые k входов модуля промежуточных очередей, k+1 вход модуля промежуточных очередей соединен с генератором случайного числа, k+2 вход модуля промежуточных очередей соединен с модулем формирования матрицы интервалов, с первых k выходов модуля промежуточных очередей потоки приоритетного трафика данных поступают на m входов модуля приоритетных очередей, k+1 выход модуля промежуточных очередей соединен с модулем формирования таблицы соответствия, с m выходов модуля приоритетных очередей потоки приоритетного трафика данных передаются на вход планировщика с приоритетами PQ, выход планировщика с приоритетами PQ соединен с первым входом модуля восстановления приоритетов, выход модуля формирования таблицы соответствия соединен с вторым входом модуля восстановления приоритетов, с k выходов модуля восстановления приоритетов потоки приоритетного трафика данных передаются на выходные порты и далее в канал связи.

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

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

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

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

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

Планировщик с приоритетами PQ 23.6, выполненный с возможностью приоритетного обслуживание пакетов.

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

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

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

На входные порты (от 1 до n) поступают потоки приоритетного трафика данных и затем передаются в классификатор. В классификаторе 21 осуществляется отнесение потоков трафика данных к классам в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета. После классификатора 21 потоки приоритетного трафика данных поступают в модуль маршрутизации 22, где осуществляется продвижения пакетов в соответствии с таблицей маршрутизации на соответствующий модуль вероятностного обслуживания 23. В модуле вероятностного обслуживания 23 потоки приоритетного трафика данных поступают в модуль промежуточных очередей 23.1, где помещают пакеты в очередь соответствующего класса в соответствии с исходным полем ToS Precedence заголовка IP пакета, либо в соответствии с исходным полем DSCP заголовка IP пакета. В этом же модуле промежуточных очередей 23.1 для каждой очереди соответствующего класса измеряют скорость поступления трафика данных и среднюю длину пакетов. При этом на каждом такте поступления потоков приоритетного трафика данных в генераторе случайного числа 23.2 генерируют случайное число, равномерно распределенное в интервале от 0 до 1, которое передается в модуль промежуточных очередей 23.1. Вместе с этим в модуле формирования матрицы интервалов 23.3 формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди. Далее в модуле промежуточных очередей 23.1 изменяют исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы интервалов и случайного числа. После этого передают пакет в соответствующую приоритетную очередь в модуль приоритетных очередей 23.4 на основе изменённого поля ToS Precedence заголовка IP пакета, либо на основе изменённого поля DSCP заголовка IP пакета. Одновременно с этим передают идентификатор соответствующего потока в модуль формирования таблицы соответствия 23.5, в котором формируют таблицу соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета. В модуле приоритетных очередей 23.4 помещают пакеты трафика данных в конец приоритетной очереди соответствующего класса в соответствии с изменённым полем ToS Precedence заголовка IP пакета, либо в соответствии с изменённым полем DSCP заголовка IP пакета. Планировщик с приоритетами PQ 23.6 осуществляет обслуживание пакетов в приоритетных очередях и передает приоритетный трафика данных в модуль восстановления приоритетов 23.7 с целью восстановления исходного приоритета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом таблицы соответствия. С выхода модуля восстановления приоритетов 23.7 приоритетный трафик данных передается в выходной порт. С выходных портов (от 1 до n) передают потоки приоритетного трафика данных в канал связи.

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

В устройстве на выходном порту сконфигурирован модуль вероятностного приоритетного обслуживания очередей 23, причем в модуле промежуточных очередей 23.1 установлены следующие настройки весов: вес первого потока трафика данных , вес второго потока трафика данных , вес третьего потока трафика данных .

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

Все потоки трафика данных поступают в модуль промежуточных очередей 23.1, в котором пакеты первого приоритета помещают в очередь 1 класса, пакеты второго приоритета помещают в очередь 2 класса, пакеты третьего приоритета помещают в очередь 3 класса. Одновременно с этим в модуле промежуточных очередей 23.1 измеряют скорость поступления трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса. Результаты измерения представлены в таблице 1.

Таблица 1. Результаты скорости поступления потоков трафика данных

Номер
приоритета Скорость поступления потока трафика данных, Кбит/с Средняя длина пакетов потока трафика данных, бит 1 30 4000 2 21 4000 3 14,7 4000

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

В модуле промежуточных очередей 23.1 формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди. Рассмотрим более подробно данное действие, которое включает следующие шаги:

Шаг 1. Формируют матрицу с характеристиками потоков трафика данных

.(2)

Шаг 2. Пересчитывают скорости поступления потоков приоритетного трафика данных в значение интенсивности поступления пакетов для каждого потока трафика данных

.(3)

Шаг 3. Рассчитывают средний вес всех потоков трафика данных

.(4)

Шаг 4. Рассчитывают относительное значение интенсивности поступления пакетов для каждого потока трафика данных с учетом среднего веса потоков трафика данных

.(5)

Как видно из выражения (5), относительное значение интенсивности поступления пакетов для первого приоритета уменьшилось с учетом среднего веса потоков трафика данных относительно измеренного значения, а относительное значение интенсивности поступления пакетов для третьего приоритета увеличилось с учетом среднего веса потоков трафика данных относительно измеренного значения, а относительное значение интенсивности поступления пакетов для третьего приоритета увеличилось с учетом среднего веса потоков трафика данных относительно измеренного значения, при этом относительное значение интенсивности поступления пакетов для второго приоритета практически не изменилось.

Шаг 5. Рассчитывают добавочную часть веса для поступающих потоков трафика данных (фиг. 5). Для данного примера добавочный вес для трафика данных первого приоритета равен , для трафика данных второго приоритета равен , для трафика данных третьего приоритета равен .

Шаг 6. Рассчитывают матрицу интервалов с учетом интенсивности поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждого потока. Для рассматриваемого случая матрица интервалов имеет следующий вид

,

где первая строка матрицы означает, что пакеты трафика данных первого приоритета имеют один интервал от 0 до 1; вторая строка матрицы означает, что пакеты трафика данных второго приоритета имеют два интервала: первый интервал от 0 до 0,857, второй интервал от 0,857 до 1; третья строка матрицы означает, что пакеты трафика данных третьего приоритета имеют три интервала: первый от 0 до 0,735, второй интервал от 0,735 до 0,857, третий интервал от 0,857 до 1.

В момент поступления пакета в модуль промежуточных очередей 23.1 (очередь k-го класса) генератор случайного числа 23.2 генерирует случайное число, которое равномерно распределено в интервале от 0 до 1. В случае если одновременно поступают два пакета в разные очереди соответствующих классов, то сначала выбирают очередь соответствующего класса, а затем номер интервала.

Изменяют исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы интервалов и случайным числом (фиг. 6). На фиг. 6 показано, что для пакетов трафика данных первого приоритета сформирован один интервал от 0 до 1 и значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета не изменяется, причем все пакеты передают в очередь первого приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с).

Для пакетов трафика данных второго приоритета сформировано два интервала, причем если случайное число попадает в первый интервала от 0 до 0,857, то изменяют значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета и пакеты передают в очередь 1 приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с). Если случайное число попадает во второй интервал от 0,857 до 1, то значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета не изменяется и пакеты передают в очередь 2 приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с).

Для пакетов трафика данных третьего приоритета сформировано три интервала, причем если случайное число попадает в первый интервала от 0 до 0,735, то изменяют значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета и пакеты передают в очередь 1 приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с). Если случайное число попадает во второй интервал от 0,735 до 0,857, то изменяют значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета и пакеты передают в очередь 2 приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с). Если случайное число попадает в третий интервал от 0,857 до 1, то значение поля ToS Precedence заголовка IP пакета, либо поля DSCP заголовка IP пакета не изменяется и пакеты передают в очередь 3 приоритета модуля приоритетных очередей 23.4 с интенсивностью (пак/с).

В модуле приоритетных очередей 23.4 принятые пакеты трафика данных помещают в конец очереди соответствующего приоритета. Все приоритетные очереди обслуживаются планировщиком с приоритетным обслуживанием 23.6. Пакеты обслуживаются из заголовка заданной очереди только в том случае, если все очереди с более высоким приоритетом пустые. В каждой из очередей приоритетов пакеты обслуживаются в порядке FIFO.

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

Благодаря новой совокупности существенных признаков достигается указанный технический результат за счет дополнительно введенного модуля вероятностного обслуживания, который содержит модуль промежуточных очередей 23.1, генератор случайного числа 23.2, модуль формирования матрицы интервалов 23.3, модуль приоритетных очередей 23.4, модуль формирования таблицы соответствия 23.5, планировщик 23.6, модуль восстановления приоритетов 23.7.

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

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

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

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

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

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

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

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

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

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

Заявленные способ вероятностного приоритетного обслуживания очередей и устройство его реализующее обеспечивает уменьшение сложности вычислений при поддержки большого количества классов обслуживания на портах маршрутизатора, а также позволяет более точно осуществить аппроксимацию обобщенной системы совместного использования процессоров (GPS) за счет того, что устанавливают вес для каждой промежуточной очереди в модуле промежуточных очередей 23.1, принимают потоки приоритетного трафика данных на входные порты маршрутизатора, классифицируют потоки приоритетного трафика данных на классы в соответствии с полем ToS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета в классификаторе 21, маршрутизируют потоки приоритетного трафика данных на соответствующие выходные порты маршрутизатора на основании таблицы маршрутизации в модуле маршрутизации 22, помещают в промежуточную очередь пакеты приоритетного трафика данных соответствующего класса в соответствии с исходным полем ToS Precedence заголовка IP пакета, либо в соответствии с исходным полем DSCP заголовка IP пакета в модуле промежуточных очередей 23.1, измеряют скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса в модуле промежуточных очередей 23.1, формируют таблицу соответствия идентификатора потока с полем ToS Precedence заголовка IP пакета, либо с полем DSCP заголовка IP пакета в модуле формирования таблицы соответствия 23.5, формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди в модуле формирования матрицы интервалов 23.3, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, в генераторе случайного числа 23.2, изменяют исходный приоритет пакета в поле DSCP заголовка IP пакета, либо в поле ToS Precedence заголовка IP пакета с учетом матрицы интервалов и случайного числа в модуле промежуточных очередей 23.1, передают пакет в приоритетную очередь в соответствии с изменённым полем ToS Precedence заголовка IP пакета либо в соответствии с изменённым полем DSCP заголовка IP пакета из модуля промежуточных очередей 23.1, помещают в конец соответствующей приоритетной очереди пакеты трафика данных соответствующего класса в соответствии с изменённым полем ToS Precedence заголовка IP пакета либо в соответствии с изменённым полем DSCP заголовка IP пакета в модуле приоритетных очередей 23.4, осуществляют обслуживание пакетов в приоритетных очередях планировщиком в планировщике с приоритетами PQ 23.6, восстанавливают исходный приоритет пакета в поле DSCP заголовка IP пакета либо в поле ToS Precedence заголовка IP пакета с учетом матрицы соответствия в модуле восстановления приоритетов 23.7, передают приоритетный трафика данных в выходной порт маршрутизатора.

Изобретение относится к области телекоммуникаций. Техническим результатом является уменьшение сложности вычислений при поддержки большого количества классов обслуживания. Способ вероятностного приоритетного обслуживания очередей, в котором измеряют скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса, формируют матрицу интервалов с учетом скорости поступления потоков приоритетного трафика данных, средней длины пакетов и веса для каждой промежуточной очереди, генерируют случайное число, равномерно распределенное в интервале от 0 до 1, изменяют исходный приоритет пакета с учетом матрицы интервалов и случайного числа, передают пакет в приоритетную очередь, осуществляют обслуживание пакетов в приоритетных очередях планировщиком с приоритетами PQ, восстанавливают исходный приоритет пакета в поле DSCP заголовка IP пакета либо в поле ToS Precedence заголовка IP пакета с учетом матрицы соответствия, передают приоритетный трафик данных в выходной порт маршрутизатора. 2 н. и 3 з.п. ф-лы, 10 ил., 1 табл.

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

2. Способ по п. 1, в котором после помещения в промежуточную очередь пакетов трафика данных устанавливают скорость поступления потоков приоритетного трафика данных соответствующего класса и среднюю длину пакетов соответствующего класса.

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

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

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