Способ управления очередями в маршрутизаторах транспортной сети связи Российский патент 2019 года по МПК H04L12/801 

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

Изобретение относится к области телекоммуникационных сетей связи, в частности, к способам борьбы с перегрузками в транспортных сетях связи.

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

В настоящее время остро стоит проблема перегруженности транспортных сетей связи с коммутацией пакетов. Учитывая тот факт, что к 2020 году к сетям общего пользования будут подключено более 50 миллиардов устройств Интернета вещей и Промышленного интернета, есть риск, что транспортные сети связи не справятся с трафиком, генерируемым таким количеством узлов. В существующих транспортных сетях связи реализуется ряд механизмов, позволяющих предотвратить перегрузки: маршрутизация с учетом состояния трафика (traffic-aware routing), управление доступом (admission control), регулирование трафика (traffic throttling), сброс нагрузки (load shedding). Данные процедуры реализуются в маршрутизаторах транспортной сети связи или сети доступа. Чтобы избежать перегрузок при пульсирующем (пачечном) трафике достаточно эффективны активные алгоритмы управления очередями, которые предполагают сброс пакетов, такие как произвольное раннее обнаружение перегрузки RED (Random Early Detection), взвешенный WRED (Weighed Random Early Detection), активный ARED (Adaptive Random Early Detection).

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

Известен способ «Случайное раннее отбрасывание пакетов в соответствии с классом пошаговой маршрутизации PHB» (патент US 7349336 В2 от 25.05.2008 г.), включающий в себя получение пакета с соответствующим классом трафика, создание специализированного класса RED для регулирования различных классов трафика с пошаговой маршрутизацией PHB (Per Hop Behavior) в пределах одной очереди, управление соответствующим пакетом на основе параметров RED, специализированного класса RED и класса пошаговой маршрутизации PHB, установление минимального и максимального порога очереди с учетом специализированного класса RED и класса пошаговой маршрутизации PHB, определение вероятности маркировки пакета и вероятности постановки пакета в очередь на основе специализированного класса RED и класса пошаговой маршрутизации PHB, маркировку пакета в соответствии с рассчитанной вероятностью когда пакет находится между минимальным и максимальным порогом очереди, либо ставят в очередь согласно рассчитанной вероятности, если средняя длина очереди больше максимального порога очереди, то производится сброс пакета.

Наиболее близким по технической сущности к заявляемому способу и выбранным в качестве прототипа является «Способ дифференцированного сброса пакетов на основе алгоритма WRED и устройство его реализующее» (патент US 2017/0134282 A1 от 11.05.2017 г.), заключающийся в том, что принимают входящие пакеты, при отсутствии перегрузки в сети ставят пакет в очередь или очереди, при наличии перегрузки в сети либо ставят пакет в очередь, либо сбрасывают пакет на основе вероятности сброса пакета и приоритета услуги. Перегрузка в сети определяется в случае, если средняя длина очереди больше, чем минимальный порог. Пакет, возможно, поставить в очередь, если средняя длина очереди больше минимального порога и меньше максимального порога, иначе если средняя длина очереди больше максимального порога все пакеты сбрасываются. При этом входящие пакеты могут иметь приоритеты услуг, определяемые через идентификаторы в заголовке пакета первого, второго и третьего уровней.

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

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

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

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

Согласно одному из частных вариантов реализации определяют приоритета пакета в принятом потоке трафика данных согласно поля TOS (Type of Service) Precedence заголовка IP пакета, либо на основе поля DSCP (Differentiated Service Code Point) заголовка IP пакета.

Согласно одному из частных вариантов реализации формируют весовые коэффициенты для каждого приоритета в соответствии полем TOS Precedence заголовка IP пакета, либо в соответствии с полем DSCP заголовка IP пакета.

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

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

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

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

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

на фиг. 2 – заголовок IP пакета;

на фиг. 3 – таблица соответствия значений весовых коэффициентов со значениями поля TOS и поля DSCP заголовка IP пакета;

на фиг. 4 – имитационная модель в сетевом эмуляторе NS-2;

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

на фиг. 6 – закон распределения числа пакетов в очередях для разных приоритетов.

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

10. Принимают входной поток трафика данных, состоящий из пакетов разного приоритета.

11. Определяют приоритет пакета в принятом потоке трафика данных. Приоритет пакета определяется согласно поля TOS Precedence заголовка IP пакета (фиг. 2), в котором выделено три бита под значение приоритета, либо в соответствии с полем DSCP заголовка IP пакета.

12. Формируют весовые коэффициенты для каждого приоритета. Так как в поле TOS Precedence заголовка IP пакета и в поле DSCP заголовка IP пакета выделено три бита под приоритет пакетов, следовательно можно реализовать различных вариантов значений весовых коэффициентов для различных приоритетов. Формирование весовых коэффициентов производят по следующему правилу:

, (1)

где – весовой коэффициент -го приоритета, .

Например, , ,…, .

13. Сопоставляют весовые коэффициенты для каждой очереди в соответствии с ее приоритетом (фиг. 3). При этом весовой коэффициент сопоставляют для очереди, в которой обслуживаются пакеты наивысшего приоритета, а весовой коэффициент сопоставляют для очереди, в которой обслуживаются пакеты наименьшего приоритета.

14. Вычисляют среднюю длину очереди для каждого приоритета. Вычисление средней длины очереди для каждого приоритета производят по следующему правилу:

, (2)

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

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

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

– экспоненциальный весовой фактор, который определяет администратор транспортной сети связи, при этом значения находится в диапазоне от 0 до 10. Большое значение этого коэффициента сильнее сглаживает разные изменения мгновенного значения длины очереди пакетов -го приоритета в текущий момент времени. По этой причине средняя длина очереди будет изменяться медленнее, чем мгновенное значение длины очереди. Как следствие алгоритм взвешенного раннего обнаружения перегрузки WRED не сразу начнет отбрасывать пакеты при резком изменении мгновенного значения длины очереди пакетов -го приоритета, или же может продолжать отбрасывать пакеты даже когда присутствуют незначительные изменения мгновенного значения длины очереди пакетов -го приоритета. В случае если , алгоритм взвешенного раннего обнаружения перегрузки WRED перестанет реагировать на мгновенную перегрузку в канале связи. В случае, если значение   ежит в диапазоне , среднее значение длины очереди практически совпадает c текущим значением длины очереди. В этом случае реакция алгоритма взвешенного раннего обнаружения перегрузки WRED на резкие изменения длины очереди становится практически мгновенной. Если значение  , алгоритм взвешенного раннего обнаружения перегрузки WRED становится чрезвычайно чувствителен к резким изменениям числа пакетов в очереди, в этом случае значение средней длины очереди численно совпадает с мгновенным значением длины очереди.

15. Определяют перегрузку в транспортной сети связи по следующему правилу:

, (3)

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

(4)

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

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

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

, (5)

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

17. Принимают решение о действии над пакетом -го приоритета: пакет сбрасывают с вероятностью , либо ставят в очередь с вероятностью . Для того, чтобы принять решение о действии над пакетом -го приоритета необходимо сгенерировать случайное число , равномерно распределенное в диапазоне от 0 до 1, если , то пакет -го приоритета сбрасывают, если , то пакет -го приоритета ставят в очередь.

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

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

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

- число магистральных маршрутизаторов в сети связи ;

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

- скорость поступления пакетов -го приоритета с Мбит/с;

- пропускная способность магистрального канала Мбит/с.

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

Таблица 1 – Результаты имитационного моделирования фрагмента транспортной сети связи в сетевом эмуляторе NS-2

Номер
приори-тета Скорость поступления потоков
трафика данных,
Мбит/с Весовой
коэффициент Часть
пропускной
способности в
исходящем
канале связи, Мбит/с Среднесетевая
задержка пакетов, мс Средняя
длина
очереди,
пакеты Коэффициент
потерь
пакетов 1 2,4 0,125 1 92 22,894 0,583 2 2,4 0,143 1 94 23,577 0,583 3 2,4 0,167 1 99 24,631 0,583 4 2,4 0,2 1 105 26,328 0,583 5 2,4 0,25 1 117 29,306 0,583 6 2,4 0,333 1 139 34,635 0,583 7 2,4 0,5 1 177 44,187 0,583 8 2,4 1 1 243 60,833 0,583

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

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

Изобретение относится к области телекоммуникационных сетей связи. Техническим результатом изобретения является уменьшение среднесетевой задержки пакетов для приоритетного трафика во время перегрузки канала связи. Технический результат достигается за счет того, что при управлении очередями в маршрутизаторах: принимают входящий поток трафика данных, определяют приоритет пакета в принятом потоке трафика данных, вычисляют среднюю длину очереди для каждого приоритета, определяют перегрузку в канале связи осуществляют постановку пакета в очередь соответствующего приоритета при отсутствии перегрузки в транспортной сети связи. Дополнительно формируют весовые коэффициенты для каждого приоритета, сопоставляют весовые коэффициенты для каждой очереди в соответствии с приоритетом пакетов, которые обслуживаются в этой очереди. После определения перегрузки в канале связи вычисляют вероятность сброса пакета P_сброса P_сброса, учитывая весовой коэффициент очереди и среднюю длину очереди. Принимают решение о действии над пакетом: пакет сбрасывают с вероятностью P_сброса либо ставят в очередь с вероятностью 1-P_сброса. 2 з.п. ф-лы, 1 табл., 6 ил.

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

2. Способ по п.1, в котором определение приоритета пакета осуществляется согласно полю TOS Precedence заголовка IP пакета либо на основе поля DSCP заголовка IP пакета.

3. Способ по п.1, в котором весовые коэффициенты формируются в соответствии полем TOS Precedence заголовка IP пакета либо в соответствии с полем DSCP заголовка IP пакета.