Способ и система для оптимизации иерархической многоуровневой транспортной сети связи
METHOD AND SYSTEM FOR OPTIMIZATION HIERARCHICAL MULTILEVEL TRANSPORT COMMUNICATION NETWORK

Область техники
Предлагаемые технические решения объединены единым изобретательским замыслом и относятся к области телекоммуникационных сетей связи, в частности, к оптимизации транспортной сети связи с коммутацией пакетов.
Уровень техники
В настоящее время остро стоит проблема перегруженности сетей связи, основанных на традиционных технологиях. Учитывая тот факт, что к 2020 году к сетям общего пользования будут подключено более 50 миллиардов устройств Интернета вещей и Промышленного интернета, есть риск, что сети не справятся с трафиком, генерируемым таким количеством узлов. Кроме этого, появится сложность в управлении и конфигурировании сетей такого масштаба.
Известен «Способ управления перегрузкой и распределение ресурсов в сетях с разделением архитектуры на подсети» (патент US 8730806 В2 от 20.05.2014 г.), включающий в себя набор коммутаторов, набор каналов связи, контроллер управления подсетью, при этом коммутаторы соединены между собой каналом связи, и состоящий из этапов: получение контроллером подсети статистики о трафике данных, обнаружение перегруженного канала связи в подсети, идентификация маршрутов, которые перегружают канал связи, вычисление вероятности перераспределения трафика данных по другим маршрутам на основе вероятности перераспределения трафика данных, управление интенсивностью поступления трафиком данных.
Известен «Способ управления трафиком между множеством взаимосвязанных сайтов» (патент US 20170012827 A1 от 12.01.2017 г.), включающий в себя сайты, которые связаны между собой через кольцевые элементы и сегменты логического кольца, реализованные сетевым контроллером по физической транспортной сети связи, причем способ содержит этапы: получение информации о трафике в логическом кольце, определение в соответствии с полученной информацией потребности в изменении кольцевой топологии, выполнение оптимизации в соответствии с определенной потребностью топологии с учетом изменения трафика, при этом оптимизация топологии включает в себя, по меньшей мере, одно из: увеличение пропускной способности сегмента кольца, уменьшение пропускной способности сегмента кольца, создание маршрута трафика и удаление существующего маршрута трафика, а также передачу обновленной информации маршрутизации узлам кольца, информацию о маршрутизации, отражающую изменение кольцевой топологии.
Известен «Способ вычисления маршрута в режиме реального времени и инжиниринг трафика сегмента маршрутизации» (патент US 20160294700 A1 от 6.09.2016 г.), включающий в себя этапы: определение множества каналов связи с двойными переменными ; получение нового потока трафика данных, при этом при определении промежуточного узла k, обеспечивающего минимальный вес для двух маршрутов сегмента от входного узла до выходного узла для нового потока, основанного на потоке, который заканчивается на канале связи l от нового потока до промежуточного узла k и двойного веса, оценивают  за канал связи l; и маршрутизацию нового потока к промежуточному узлу k по маршруту с минимальным весом, когда у минимального маршрута вес, меньше или равный одному.
Наиболее близким по технической сущности к заявляемому способу и выбранным в качестве прототипа является «Способ для транспортной программно-конфигурируемой сети с инжинирингом трафика использующей двойственные переменные» (патент US 20170195230 A1 от 06.07.2017 г.), заключающийся в том, что получают информацию о трафике в транспортной сети связи, определяют изменение или ожидаемое изменение трафика в транспортной сети связи, идентифицируют один или несколько перегруженных каналов связей в транспортной сети связи путем решения задачи оптимизации с целью максимизации эффективности функционирования сети с учетом изменения или ожидаемого изменения трафика в транспортной сети связи, при котором решение задачи оптимизации включает в себя решения задач с учетом набора ограничений по каналам связи с двумя переменными, корректируют пропускную способность одного или нескольких каналов связи с целью уменьшения перегрузки, по меньшей мере, перегруженного канала связи, обновляют конфигурацию транспортной сети связи.
Наиболее близкой по технической сущности к заявляемой системе и выбранной в качестве прототипа является «Система для транспортной программно-конфигурируемой сети с инжинирингом трафика  использующая двойственные переменные» (патент US 20170195230 A1 от 06.07.2017 г.), заключающаяся в том, что содержит контроллер сетевого программного обеспечения, сконфигурированный для управления трафиком транспортной сети связи, который идентифицирует один или несколько перегруженных каналов связей в транспортной сети путем решения задачи оптимизации для максимизации эффективности функционирования сети с учетом изменения или ожидаемого изменения трафика в транспортной сети связи, при котором решение задач оптимизации включает в себя решения задач с учетом набора ограничений по каналам связи с двумя переменными. Транспортная сеть связи строится по технологии OTN, IP/MPLS – TE.
Технической проблемой данных аналогов и прототипа является высокая сложность и большое количество вычислений при реализации оптимизации иерархической многоуровневой транспортной сети связи, а также низкая надежность уровня управления иерархической многоуровневой транспортной сети связи. Это связано с тем, что алгоритмы решающие задачу оптимизации транспортной сети связи в большинстве своем имеют полиномиальную или экспоненциальную оценку вычислительной сложности.
Создание способа и системы для оптимизации иерархической многоуровневой транспортной сети связи направлено на решение данной технической проблемы, которые сокращают сложность и количество вычислений оптимизации иерархической многоуровневой транспортной сети связи за счет декомпозиции общей задачи оптимизации на задачи структурной и параметрической оптимизации иерархической многоуровневой транспортной сети связи в отдельных подсетях иерархической многоуровневой транспортной сети связи, повышают надежность уровня управления иерархической многоуровневой транспортной сети связи за счет соединения каждого контроллера подсети иерархической многоуровневой транспортной сети связи физическими/логическими каналами управления, по меньшей мере, с сетевыми элементами двух смежных по иерархии подсетями иерархической многоуровневой транспортной сети связи.
Логический канал – путь, по которому данные передаются от одного порта к другому (см. Якубайтис, Э.А. Информационные сети и системы: справочная книга / Э.А. Якубайтис. – Москва: финансы и статистика, 1996. – 118 с.).
Под смежной по иерархии подсетью иерархической многоуровневой транспортной сети связи будем понимать R подсеть иерархической многоуровневой транспортной сети связи для R+1 и R-1 подсети иерархической многоуровневой транспортной сети связи.
Раскрытие изобретения
В заявленном способе эта техническая проблема решается тем, что в способе для оптимизации иерархической многоуровневой транспортной сети связи, заключающемся в том, что после разбиения иерархической многоуровневой транспортной сети связи на подсети иерархической многоуровневой транспортной сети связи получают информацию об уровнях обслуживания пользователей, информацию о параметрах трафика от сетевых элементов соответствующей подсети иерархической многоуровневой транспортной сети связи, таких как среднее время задержки блоков данных, коэффициенты готовностей физических/логических каналов связи, загрузка физических/логических каналов связи соответствующей подсети иерархической многоуровневой транспортной сети связи. После заполнения таблиц коммутации, топологии и управления ресурсом для соответствующей подсети иерархической многоуровневой транспортной сети связи передают сетевым элементам соответствующей подсети иерархической многоуровневой транспортной сети связи таблицы коммутации/маршрутизации, топологии и управления ресурсом, дополнительно разбивают иерархическую многоуровневую транспортную сеть связи на R подсетей иерархической многоуровневой транспортной сети связи. Находят связные структуры для соответствующей подсети иерархической многоуровневой транспортной сети связи по критерию минимума среднего времени задержки блоков данных для соответствующей связной структуры. Вычисляют оптимальную логическую структуру для соответствующей подсети иерархической многоуровневой транспортной сети связи, с использованием среднего времени задержки блоков данных и коэффициентов готовностей физических/логических каналов связи для соответствующей подсети иерархической многоуровневой транспортной сети связи, информации о сетевых элементах соответствующей подсети иерархической многоуровневой транспортной сети связи, информации о найденных связных структурах по критерию минимума среднего времени задержки для соответствующих связных структур соответствующей подсети иерархической многоуровневой транспортной сети связи. Находят связные структуры на оптимальной логической структуре соответствующей подсети иерархической многоуровневой транспортной сети связи по критерию максимума коэффициента готовности физических/логических каналов связи для соответствующих связных структур соответствующей подсети иерархической многоуровневой транспортной сети связи. Вычисляют оптимальное распределение пропускной способности физических/логических каналов связи соответствующей подсети иерархической многоуровневой транспортной сети связи, с использованием информации полученной от смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи, как минимум средний размер блоков данных и интенсивность поступления блоков данных, требования к качеству обслуживания. Заполняют таблицы коммутации/маршрутизации, топологии и управления ресурсом для соответствующей подсети иерархической многоуровневой транспортной сети связи. Повторяют этапы оптимизации для смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи до момента, пока не наступит, по меньшей мере, следующее условие проверки: соответствующая подсеть иерархической многоуровневой транспортной сети связи не имеет смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи.
Согласно одному из частных вариантов реализации при изменении топологии, по меньшей мере, в одной подсети иерархической многоуровневой транспортной сети связи, либо обнаружении хотя бы одного перегруженного физического/логического канала связи в любой подсети иерархической многоуровневой транспортной сети связи повторяют этапы оптимизации, начиная с соответствующей подсети иерархической многоуровневой транспортной сети связи, при этом нижележащие подсети иерархической многоуровневой транспортной сети связи остаются без изменения.
Согласно одному из частных вариантов реализации дополнительным условием является то, что этапы оптимизации начинаются с подсети иерархической многоуровневой транспортной сети связи, которая не имеет смежной нижней по иерархии подсети иерархической многоуровневой транспортной сети связи, при этом информация о коэффициентах готовностей физических/логических каналов связи задана оператором иерархической многоуровневой транспортной сети связи.
Новая совокупность существенных признаков позволяет достичь указанного технического результата за счет декомпозиции общей задачи оптимизации на задачи структурной и параметрической оптимизации иерархической многоуровневой транспортной сети связи в отдельных подсетях иерархической многоуровневой транспортной сети связи.
В заявленной системе эта техническая проблема решается тем, что в системе для оптимизации иерархической многоуровневой транспортной сети связи, содержащей, R подсетей иерархической многоуровневой транспортной сети связи, предназначенные для передачи трафика данных от узла отправителя до узла получателя, R контроллеров подсетей иерархической многоуровневой транспортной сети связи, предназначенные для управления и конфигурирования соответствующими подсетями иерархической многоуровневой транспортной сети связи. Контроллер подсети иерархической многоуровневой транспортной сети связи включает в себя: модуль приема/передачи параметров управления для приема информации о трафике данных от сетевых элементов, передачи таблиц коммутации/маршрутизации, топологии и управления ресурсом сетевым элементам, модуль статистического анализа трафика, предназначенный для анализа загруженности физических/логических каналов связи и сетевой задержки блоков данных, модуль нахождения связных структур, выполненный с возможностью нахождения связных структур подсети иерархической многоуровневой транспортной сети связи по критерию минимума среднего времени задержки блоков данных для соответствующей связной структуры и по критерию максимума коэффициента готовности для соответствующих связных структур, модуль структурной оптимизации, выполненный с возможностью вычисления оптимальной логической структуры подсети иерархической многоуровневой транспортной сети связи, с использованием информации о параметрах трафика от сетевых элементов соответствующей подсети иерархической многоуровневой транспортной сети связи, как минимум среднего времени задержки блоков данных и коэффициентов готовностей физических/логических каналов связи, информации о сетевых элементах соответствующей подсети иерархической многоуровневой транспортной сети связи, информации о найденных связных структурах по критерию минимума среднего времени задержки для соответствующих связных структур, модуль параметрической оптимизации, выполненный с возможностью вычисления оптимального распределения пропускной способности физических/логических каналов связи подсети иерархической многоуровневой транспортной сети связи, с использованием полученной от смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи информации, как минимум среднего размера блоков данных и интенсивности поступления блоков данных, требований к качеству обслуживания, модуль данных, предназначенный для хранения таблицы коммутации/маршрутизации, топологии и управления ресурсом, сетевых событий, модуль пользовательского интерфейса, предназначенный для подключения к контроллеру соответствующей подсети иерархической многоуровневой транспортной сети связи, и вывода информации, модуль интерфейса прикладных программ, позволяющий контроллеру подсети иерархической многоуровневой транспортной сети связи взаимодействовать с одной или несколькими подсетями иерархической многоуровневой транспортной сети связи, например, для проверки состояния подсети иерархической многоуровневой транспортной сети связи, добавления/удаления новых связных структур.
Согласно одному из частных вариантов реализации подсеть иерархической многоуровневой транспортной сети связи включает в себя, по меньшей мере, три сетевых элемента соединенные между собой физическими/логическими каналами связи, при этом общее количество сетевых элементов подсетей иерархической многоуровневой транспортной сети связи равно количеству сетевых элементов в иерархической многоуровневой транспортной сети связи в целом.
Согласно одному из частных вариантов реализации контроллер подсети иерархической многоуровневой транспортной сети связи соединен физическими/логическими каналами управления, по меньшей мере, с сетевыми элементами соответствующей подсети иерархической многоуровневой транспортной сети связи и смежной нижней/верхней по иерархии подсетями иерархической многоуровневой транспортной сети связи.
Согласно одному из частных вариантов реализации сетевые элементы одной подсети иерархической многоуровневой транспортной сети связи взаимодействуют с сетевыми элементами смежных по иерархии подсетями иерархической многоуровневой транспортной сети связи с помощью интерфейсных соединений.
Благодаря новой совокупности существенных признаков за счет соединения каждого контроллера подсети иерархической многоуровневой транспортной сети связи физическими/логическими каналами управления, по меньшей мере, с сетевыми элементами двух смежных по иерархии подсетями иерархической многоуровневой транспортной сети связи достигается указанный технический результат.
Уровень инфраструктуры (Infrastructure Layer), представляет собой набор сетевых элементов и устройств, которые обеспечивают коммутацию и маршрутизацию пакетов (см. Open Networking Foundation, OpenFlow-enabled SDN and Network Functions Virtualization ONF Solution Brief February 17, 2014 г.)
Уровень управления (Control Layer) обеспечивает функции логически централизованного управления системой и контролирует сетевые характеристики маршрутизации через открытый интерфейс (см. Open Networking Foundation, OpenFlow-enabled SDN and Network Functions Virtualization ONF Solution Brief February 17, 2014 г.)
Под интерфейсным соединением будем понимать совокупность методов и правил взаимодействия между сетевыми элементами смежных подсетей иерархической многоуровневой транспортной сети связи.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленной системы для иерархической многоуровневой транспортной сети связи, отсутствуют. Следовательно, заявленное изобретение соответствует условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Для более понятной иллюстрации технических решений согласно вариантам осуществления настоящего изобретения ниже приведено краткое описание сопроводительных чертежей.
На фиг. 1 – схема способа оптимизации иерархической многоуровневой транспортной сети связи;
на фиг. 2 – оптимальные логические структуры подсети иерархической многоуровневой транспортной сети связи;
на фиг. 3 – схема системы для оптимизации иерархической многоуровневой транспортной сети связи;
на фиг. 4 – схема контроллера подсети иерархической многоуровневой транспортной сети связи.
Ниже будут полностью и четко описаны технические решения для вариантов осуществления настоящего изобретения со ссылками на сопроводительные чертежи. Должно быть, очевидно, что варианты осуществления, описанные ниже, являются только частью настоящего изобретения, а не всеми возможными вариантами осуществления настоящего изобретения. Все другие варианты осуществления, полученные специалистами в данной области техники на основе вариантов осуществления настоящего изобретения и не использующие творческий подход, попадают под объем охраны настоящего изобретения.
Реализация заявленного способа заключается в следующем (фиг. 1).
101. Разбивают иерархическую многоуровневую транспортную сеть связи на R подсетей иерархической многоуровневой транспортной сети связи, при этом R изменяется в диапазоне от 3 до 100. Количество сетевых элементов N в каждой подсети иерархической многоуровневой транспортной сети связи изменяется в диапазоне от 3 до 30.
102. Получают информацию об уровнях обслуживания пользователей, информацию о параметрах трафика от сетевых элементов каждой подсети иерархической многоуровневой транспортной сети связи, таких как среднее время задержки блоков данных, коэффициенты готовностей физических/логических каналов связи, загрузка физических/логических каналов связи подсети иерархической многоуровневой транспортной сети связи.
103. Находят связные структуры для соответствующей подсети иерархической многоуровневой транспортной сети связи по критерию минимума среднего времени задержки блоков данных для соответствующих связных структур.
104. Вычисляют оптимальную логическую структуру для соответствующей подсети иерархической многоуровневой транспортной сети связи, с использованием среднего времени задержки блоков данных и коэффициентов готовностей физических/логических каналов связи для соответствующей подсети иерархической многоуровневой транспортной сети связи, информации о сетевых элементах подсети иерархической многоуровневой транспортной сети связи, информации о найденных связных структурах по критерию минимума среднего времени задержки для соответствующих связных структур соответствующей подсети иерархической многоуровневой транспортной сети связи.
В качестве примера поясним обобщенный алгоритм, реализующий вычисление оптимальной логической структуры методом ветвей и границ, который включает четыре действия.
104.1. Формируется список комбинаций, который содержит только одну пустую комбинацию (состояние, когда ни одному элементу сети связи не приписан ни один ресурс). Для этой комбинации в неиспользованном ресурсе определяется самый надежный и самый ненадежный ресурс и производится расчет верхней и нижней границы значение коэффициента готовности соответствующей подсети иерархической многоуровневой транспортной сети связи.
104.2. Из списка комбинаций выбирается очередная комбинация, на основании которой формируются новые комбинации путем рассмотрения всех возможных вариантов назначения очередному элементу соответствующей подсети иерархической многоуровневой транспортной сети связи того или иного ресурса из списка ресурсов, но с учетом уже использованного ресурса.
104.3. Для каждой новой комбинации находится неиспользованный ресурс, в котором определяется самый надежный и самый ненадежный ресурс, и производится расчет верхней и нижней границы значение коэффициента готовности соответствующей подсети иерархической многоуровневой транспортной сети связи.
104.4. Если есть не рассмотренные комбинации в списке комбинаций, тогда возврат к 104.2. Если все комбинации в списке рассмотрены, тогда в новом списке комбинаций определяется наибольшее значение нижней границы коэффициента готовности соответствующей подсети иерархической многоуровневой транспортной сети связи. После чего с этим значением сравниваются все значения верхних границ коэффициента готовности соответствующей подсети иерархической многоуровневой транспортной сети связи, при этом комбинации, у которых значение верхних границ меньше удаляются из нового списка комбинаций как не перспективные.
Расчет верхней и нижней границы значения коэффициента готовности соответствующей подсети иерархической многоуровневой транспортной сети связи производится по методике описанной в ГОСТ Р 55111-2008 г.
Для наглядности на фиг. 2 представлены оптимальные логические структуры соответствующей иерархической многоуровневой транспортной сети связи, полученные с помощью кратчайших маршрутов (фиг. 2а), остовых деревьев (фиг. 2б), гамильтоновых цепей (фиг. 2в) и циклов (фиг. 2г), при условии организации иерархической многоуровневой транспортной сети связи с арендой канального ресурса от двух операторов связи, по пять каналов связи от каждого оператора Каналы связи от одного оператора связи имеют пунктирные линии, а от другого оператора связи сплошные линии.
105. Находят связные структуры на оптимальной логической структуре соответствующей подсети иерархической многоуровневой транспортной сети связи по критерию максимума коэффициента готовности физических/логических каналов связи, для соответствующих связных структур соответствующей подсети иерархической многоуровневой транспортной сети связи.
106. Вычисляют оптимальное распределение пропускной способности логических физических/логических каналов связи соответствующей подсети иерархической многоуровневой транспортной сети связи, с использованием полученной от верхней по иерархии подсети иерархической многоуровневой транспортной сети связи информации, как минимум среднего размера блоков данных и интенсивности поступления блоков данных, требований к качеству обслуживания.
В качестве примера поясним обобщенный алгоритм, реализующий вычисление оптимального распределение пропускной способности физических/логических каналов связи соответствующей подсети иерархической многоуровневой транспортной сети связи, который включает пять действий.
106.1. Расчет начальных значений пропускных способностей физических каналов связи (ФКС) или пропускных способностей логических каналов (ЛК)  по формуле
,
(1)
где  – интенсивность потока БД -го приоритета для ЛК или ФКС с номером ;
– средний размер БД для ЛК или ФКС с номером ;
– интенсивность потока БД -го приоритета для ЛК или ФКС с номером ;
– стоимость аренды в расчете на единицу пропускной способности ЛК или КС с номером ;
– средний размер БД для ЛК или ФКС с номером ;
– допустимое значение математического ожидания задержки БД -го приоритета для подсети иерархической многоуровневой транспортной сети связи;
– это сумма интенсивностей потоков БД -го приоритета для подсети иерархической многоуровневой транспортной сети связи;
– задержка распространения БД для ЛК или ФКС с номером ;
– стоимость аренды в расчете на единицу пропускной способности ЛК или ФКС с номером ;
– число сетевых элементов (СЭ) для соответствующей подсети иерархической многоуровневой транспортной сети связи;
– общее число СЭ, ЛК или ФКС для соответствующей подсети иерархической многоуровневой транспортной сети связи.
106.2. Определение начального значения среднего взвешенного математического ожидания задержки блоков данных -го приоритета для физического канала связи или логического канала и для подсети иерархической многоуровневой транспортной сети связи в целом (на основе начальных значений, полученных в 106.1).
Средневзвешенное значение математического ожидания задержки БД -го приоритета для подсети иерархической многоуровневой транспортной сети связи в целом рассчитывается по формуле
,
(2)
где   – математическое ожидание задержки БД -го приоритета для подсети иерархической многоуровневой транспортной сети связи;
– сумма интенсивностей потоков БД -го приоритета для подсети иерархической многоуровневой транспортной сети связи;
– интенсивность потока БД -го приоритета для ИН источник которого -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи, а адресат – -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи;
– математическое ожидание задержки БД -го приоритета для ИН источник которого -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи, а адресат – -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи;
– задержка БД -го приоритета для информационного направления (ИН) источник которого -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи, а адресат – -й СЭ соответствующей подсети иерархической многоуровневой транспортной сети связи;
– задержка БД -го приоритета для соответствующей подсети иерархической многоуровневой транспортной сети связи;
– интенсивность потока БД -го приоритета для ФКС или ЛК или ФКС с номером ;
– число СЭ для соответствующей подсети иерархической многоуровневой транспортной сети связи;
– общее число СЭ, ФКС или ЛК для соответствующей подсети иерархической многоуровневой транспортной сети связи.
Математическое ожидание задержки БД -го приоритета в логическом канале рассчитывается по формулам
, ;
(3)
, .
(4)
Математическое ожидание задержки БД -го приоритета в ФКС рассчитывается по формулам
, ;
(5)
, .
(6)
106.3. Распределение пропускных способностей физических каналов связи:
,
(7)
или
,
(8)
Распределение пропускных способностей логических каналов:
,
(9)
или
,
(10)
106.4. Определение значения среднего взвешенного математического ожидания задержки БД -го приоритета для физических каналов связи или логических каналов и для соответствующей подсети иерархической многоуровневой транспортной сети связи в целом (используются значения , полученные в 106.3).
106.5. Если значение среднего взвешенного математического ожидания задержки БД -го приоритета, полученное в 106.4, не отличается от начального значения, тогда работа алгоритма заканчивается. В противном случае начальные значения пропускных способностей физических каналов связи или пропускных способностей логических каналов принимаются равными тем, что были получены в 106.3. Начальное значение среднего взвешенного математического ожидания задержки БД -го приоритета принимается равным тому, что было получено в 106.4 и осуществляется переход к 106.3.
107. Заполняют таблицы коммутации/маршрутизации, топологии и управления ресурсом для соответствующей подсети иерархической многоуровневой транспортной сети связи.
Таблицы коммутации подсети иерархической многоуровневой транспортной сети связи заполняют с использованием связных структур, найденных по критерию максимума коэффициента готовности для соответствующей связной структуры. Таблицы топологии подсети иерархической многоуровневой транспортной сети связи заполняют с использованием вычисленных оптимальных логических структур подсети иерархической многоуровневой транспортной сети связи. Таблицы управления ресурсом заполняют с использованием вычисленного оптимального распределения пропускной способности логических каналов подсети иерархической многоуровневой транспортной сети связи.
108. Передают сетевым элементам соответствующей подсети иерархической многоуровневой транспортной сети связи таблицы коммутации/маршрутизации, топологии и управления ресурсом по физическим/логическим каналам управления.
109. Повторяют этапы 102-108 для смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи до момента, пока не наступит, по меньшей мере, следующее условие проверки: соответствующая подсеть иерархической многоуровневой транспортной сети связи не имеет смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи.
При изменении топологии, по меньшей мере, в одной из подсетей иерархической многоуровневой транспортной сети связи, либо обнаружении хотя бы одного перегруженного физического/логического канала связи в любой подсети иерархической многоуровневой транспортной сети связи повторяют этапы оптимизации, начиная с соответствующей подсети иерархической многоуровневой транспортной сети связи, при этом нижележащие подсети иерархической многоуровневой транспортной сети связи остаются без изменения.
Этапы оптимизации иерархической многоуровневой транспортной сети связи начинаются с подсети иерархической многоуровневой транспортной сети связи, которая не имеет смежной нижней по иерархии подсети иерархической многоуровневой транспортной сети связи, при этом информация о коэффициентах готовностей физических/логических каналов связи задана оператором иерархической многоуровневой транспортной сети связи, либо может быть получена от оператора связи транспортной сети связи общего пользования.
Заявленный способ для оптимизации иерархической многоуровневой транспортной сети связи позволяет достичь указанного технического результата за счет декомпозиции общей задачи оптимизации на задачи структурной и параметрической оптимизации иерархической многоуровневой транспортной сети связи в отдельных подсетях иерархической многоуровневой транспортной сети связи, что сокращает сложность и количество вычислений оптимизации иерархической многоуровневой транспортной сети связи.
Система для оптимизации иерархической многоуровневой транспортной сети связи (фиг. 3) содержит, R подсетей иерархической многоуровневой транспортной сети связи, предназначенных для передачи трафика данных от узла отправителя до узла получателя, R контроллеров подсетей иерархической многоуровневой транспортной сети связи, предназначенных для управления и конфигурирования подсетей иерархической многоуровневой транспортной сети связи. Контроллер подсети иерархической многоуровневой транспортной сети связи включает в себя (фиг. 4): модуль приема/передачи параметров управления 406 для приема информации о трафике данных от сетевых элементов, передачи таблиц коммутации/маршрутизации, топологии и управления ресурсом сетевым элементам, модуль статистического анализа трафика 407, предназначенный для анализа загруженности физических/логических каналов связи и сетевой задержки блоков данных, модуль нахождения связных структур 401, выполненный с возможностью нахождения связных структур подсети иерархической многоуровневой транспортной сети связи по критерию минимума среднего времени задержки блоков данных для соответствующих связных структур и по критерию максимума коэффициента готовности для соответствующих связных структур, модуль структурной оптимизации 402, выполненный с возможностью вычисления оптимальной логической структуры подсети иерархической многоуровневой транспортной сети связи, с использованием информации о параметрах трафика от сетевых элементов подсети иерархической многоуровневой транспортной сети связи, как минимум среднего времени задержки блоков данных и коэффициентов готовностей физических/логических каналов связи, информации о сетевых элементах подсети иерархической многоуровневой транспортной сети связи, информации о найденных связных структурах по критерию минимума среднего времени задержки для соответствующих связных структур, модуль параметрической оптимизации 403, выполненный с возможностью вычисления оптимального распределения пропускной способности физических/логических каналов связи подсети иерархической многоуровневой транспортной сети связи, с использованием полученной от верхней по иерархии подсети иерархической многоуровневой транспортной сети связи информации, как минимум среднего размера блоков данных и интенсивности поступления блоков данных, требований к качеству обслуживания, модуль данных 408, предназначенный для хранения таблицы коммутации/маршрутизации, топологии и управления ресурсом, сетевых событий, модуль пользовательского интерфейса 409, предназначенный для предоставления сетевому администратору пользовательского интерфейса, с помощью которого можно подключится к контроллеру подсети иерархической многоуровневой транспортной сети связи, и вывести информацию, модуль интерфейса прикладных программ 404, позволяющий контроллеру подсети иерархической многоуровневой транспортной сети связи взаимодействовать с одной или несколькими подсетями иерархической многоуровневой транспортной сети связи, например, для проверки состояния подсети иерархической многоуровневой транспортной сети связи, добавления/удаления новых связных структур.
Подсеть иерархической многоуровневой транспортной сети связи включает в себя, по меньшей мере, три сетевых элемента соединенные между собой физическими/логическими каналами связи, при этом общее количество сетевых элементов всех подсетей иерархической многоуровневой транспортной сети связи равно количеству сетевых элементов в иерархической многоуровневой транспортной сети связи в целом.
Контроллер подсети иерархической многоуровневой транспортной сети связи соединен каналами управления, по меньшей мере, с сетевыми элементами данной и смежной нижней/верхней по иерархии подсетью иерархической многоуровневой транспортной сети связи. При этом каналы управления могут быть как физическими (выделенными), так и логическими. Физический канал управления – это физическая линия, соединяющая контроллер подсети иерархической многоуровневой транспортной сети связи с сетевым элементом. Логический канал управления – это логическое соединение, соединяющее контроллер подсети иерархической многоуровневой транспортной сети связи и сетевой элемент.
Сетевые элементы одной подсети иерархической многоуровневой транспортной сети связи взаимодействуют с сетевыми элементами соответствующей подсети иерархической многоуровневой транспортной сети связи и смежной нижней/верхней по иерархии подсетями иерархической многоуровневой транспортной сети связи с помощью интерфейсных соединений.
Сетевой элемент подсети иерархической многоуровневой транспортной сети связи может быть реализован по известной схеме, например, как коммутатор Programmble Flow PF5340-48XP-6Q ( см. www.nstor.ru/ru/news/lenta/nec_pf5340_48xp_6q_32qp.html).
Контроллер подсети иерархической многоуровневой транспортной сети связи может быть реализован по известной схеме, например, как контроллер NEC PF6800 Programmable Flow SDN Controller (см. https://www.nec.com/en/global/prod/pflow/images_documents/ProgrammableFlow_Brochure.pdf)
Интерактивный процесс системы для оптимизации иерархической многоуровневой транспортной сети связи описан ниже.
Сетевые элементы подсети иерархической многоуровневой транспортной сети связи передают через физический/логический канал управления информацию о параметрах трафика и своем статусе в контроллер подсети иерархической многоуровневой транспортной сети связи.
Контроллер подсети иерархической многоуровневой транспортной сети связи через модуль приема/передачи параметров принимает по физическому/логическому каналу управления информацию о параметрах трафика от сетевых элементов соответствующей подсети иерархической многоуровневой транспортной сети связи, таких как среднее время задержки блоков данных, коэффициенты готовностей физических/логических каналов связи, загрузка физических/логических каналов связи подсети иерархической многоуровневой транспортной сети связи.
В модуле статистического анализа трафика проводят анализ загруженности физических/логических каналов связи, коэффициента потерь блоков данных и сетевой задержки блоков данных в подсети иерархической многоуровневой транспортной сети связи.
Параметры трафика передаются в модуль нахождения связных структур с целью нахождения связных структур подсети иерархической многоуровневой транспортной сети связи таких, как кратчайшие маршруты, остовые деревья, гамильтоновы цепи и циклы по критерию минимума среднего времени задержки блоков данных для соответствующей связной структуры.
В модуле структурной оптимизации вычисляют оптимальную логическую структуру подсети иерархической многоуровневой транспортной сети связи, с использованием информации о параметрах трафика от сетевых элементов подсети иерархической многоуровневой транспортной сети связи, как минимум среднего времени задержки блоков данных и коэффициентов готовностей физических/логических каналов связи, информации о сетевых элементах подсети иерархической многоуровневой транспортной сети связи, информации о найденных связных структурах по критерию минимума среднего времени задержки для соответствующих связных структур. Оптимальная логическая структура соответствующей подсети иерархической многоуровневой транспортной сети связи передается в модуль нахождения связных структур, модуль параметрической оптимизации и модуль данных. В модуле данных на основе оптимальной логической структуры заполняют таблицы топологии подсети иерархической многоуровневой транспортной сети связи.
В модуле нахождения связных структур на основе оптимальной логической структуры подсети иерархической многоуровневой транспортной сети связи находят связные структуры подсети иерархической многоуровневой транспортной сети связи таких, как кратчайшие маршруты, остовые деревья, гамильтоновы цепи и циклы по критерию максимума коэффициента готовности для соответствующих связных структур. Данные связные структуры передают в модуль данных для заполнения таблиц коммутации/маршрутизации подсети иерархической многоуровневой транспортной сети связи.
В модуле параметрической оптимизации вычисляют оптимальное распределение пропускной способности физических/логических каналов связи подсети иерархической многоуровневой транспортной сети связи, с использованием полученной от верхней по иерархии подсети иерархической многоуровневой транспортной сети связи информации, как минимум среднего размера блоков данных и интенсивности поступления блоков данных, требований к качеству обслуживания. Оптимальное распределение пропускной способности физических/логических каналов связи передают в модуль данных для заполнения таблиц управления ресурсом подсети иерархической многоуровневой транспортной сети связи.
Модуль данных получает информацию о связных структурах, найденных по критерию максимума коэффициента готовности для соответствующих связных структур, и заполняет таблицы коммутации/маршрутизации, принимает информацию об оптимальной логической структуре соответствующей подсети иерархической многоуровневой транспортной сети связи и заполняет таблицы топологии, получает информацию об оптимальном распределении пропускной способности физических/логических каналов подсети иерархической многоуровневой транспортной сети связи и заполняет таблицы управления ресурсом. Таблицы коммутации/маршрутизации, топологии и управления ресурсом подсети иерархической многоуровневой транспортной сети связи через модуль приема/ передачи параметров передают по физическим/ логическим каналам управления сетевым элементам подсети иерархической многоуровневой транспортной сети связи.
Сетевые элементы подсети иерархической многоуровневой транспортной сети связи принимают по физическому/логическому каналу управления таблицы коммутации/маршрутизации, топологии и управления ресурсом для соответствующей подсети иерархической многоуровневой транспортной сети связи и заполняет свои таблицы коммутации, топологии и управления ресурсом.
Сетевые элементы подсети иерархической многоуровневой транспортной сети связи взаимодействуют с сетевыми элементами смежной нижней/верхней по иерархии подсетями иерархической многоуровневой транспортной сети связи с помощью интерфейсных соединений, в которых определены правила взаимодействия между сетевыми элементами смежных по иерархии подсетей иерархической многоуровневой транспортной сети связи.
При выходе из строя контроллера любой подсети иерархической многоуровневой транспортной сети связи, либо физических/логических каналов управления сетевыми элементами соответствующей подсети иерархической многоуровневой транспортной сети связи, управление сетевыми элементами соответствующей подсети иерархической многоуровневой транспортной сети связи переходит к контроллеру смежной нижней по иерархии подсети иерархической многоуровневой транспортной сети связи. Если не окажется смежной нижней по иерархии подсети иерархической многоуровневой транспортной сети связи, тогда управление переходит к контроллеру смежной верхней по иерархии подсети иерархической многоуровневой транспортной сети связи. Таким образом, надежность уровня управления иерархической многоуровневой транспортной сети связи повысилась, при том же количестве контроллеров подсетей иерархической многоуровневой транспортной сети связи.
Заявленная система для оптимизации иерархической многоуровневой транспортной сети связи позволяет достичь указанного технического результата за счет соединения каждого контроллера подсети иерархической многоуровневой транспортной сети связи физическими/логическими каналами управления, по меньшей мере, с сетевыми элементами двух смежных по иерархии подсетями иерархической многоуровневой транспортной сети связи, что повышает надежность уровня управления иерархической многоуровневой транспортной сети связи.
Большинство известных алгоритмов решения базовых структурно-сетевых задач применяемых в процессе оптимизации иерархической многоуровневой транспортной сети связи имеют полиномиальную или экспоненциальную оценку вычислительной сложности. Таким образом, вычислительная сложность задачи оптимизации иерархической многоуровневой транспортной сети связи такова, что даже для относительно простой сети может потребоваться значительные временные затраты. С увеличением числа сетевых элементов в иерархической многоуровневой транспортной сети связи вычислительная сложность отдельных задач увеличивается полиноминально, а других задач – экспоненциально.
В данном варианте осуществления изобретения общая задача оптимизации иерархической многоуровневой транспортной сети связи декомпозирована на несколько более простых задач структурной и параметрической оптимизации в отдельных подсетях иерархической многоуровневой транспортной сети связи, при этом число сетевых элементов в каждой такой подсети значительно меньше, чем общее число сетевых элементов. Это в свою очередь позволяет снизить сложность и количество вычислений при оптимизации иерархической многоуровневой транспортной сети связи.
Правомерность теоретических предпосылок проверялась ан примере решения задачи поиска связных структур методом двойного поиска. Допустим, что иерархическая многоуровневая транспортная сеть связи включает 80 сетевых элементов, 10 информационных направлений, в каждом информационном направлении используется по три кратчайших маршрута. Произведем разбиение иерархической многоуровневой транспортной сети связи на отдельные подсети используя следующее выражение:
Так как , то производим округление до целого числа в большую сторону и получаем три подсети, образующие иерархическую многоуровневую транспортную сеть связи. В первой подсети иерархической многоуровневой транспортной сети связи количество сетевых элементов равно , во второй подсети иерархической многоуровневой транспортной сети связи , в третьей подсети иерархической многоуровневой транспортной сети связи .
Теперь оценим вычислительную сложность нахождения трех кратчайших маршрутов по алгоритму двойного поиска (см. Филлипс, Д. Методы анализа сетей: пер. с англ. / Д. Филлипс, А. Гарсия-Диас. – М:Мир, 1984. – 102 с.).
,
где  – количество кратчайших маршрутов,  – число сетевых элементов.
Для прототипа получаем  количество вычислений.
Вычислительная сложность нахождения трех кратчайших маршрутов по алгоритму двойного поиска согласно изобретению с учетом разбиения иерархической многоуровневой транспортной сети связи на три подсети иерархической многоуровневой транспортной сети связи будет иметь вид:
Получаем вычислительную сложность согласно осуществления изобретения количество вычислений. Как видим, согласно предполагаемого изобретения в 9 раз снижается количество вычислений только на этапе нахождения связных структур в процессе структурной оптимизации иерархической многоуровневой транспортной сети связи. Таким образом, за счет декомпозиции общей задачи оптимизации иерархической многоуровневой транспортной сети связи на задачи структурной и параметрической оптимизации в отдельных подсетях иерархической многоуровневой транспортной сети связи достигается решение данной технической проблемы.
В данном варианте надежность уровня управления иерархической многоуровневой транспортной сети связи повысилась за счет соединения каждого контроллера подсети иерархической многоуровневой транспортной сети связи физическими/логическими каналами управления, по меньшей мере, с сетевыми элементами двух смежных нижней/верхней по иерархии подсетями иерархической многоуровневой транспортной сети связи.
Необходимо заметить, что вышеописанные варианты осуществления предоставлены только для описания технических решений настоящего изобретения, но не ограничивают настоящее изобретение. Специалисты в данной области техники должны понимать, что несмотря на то, что настоящее изобретение было подробно описано со ссылками на примерные варианты осуществления, могут быть сделаны модификации и эквивалентные замены технических решений настоящего изобретения до тех пор, пока такие модификации и замены не отклоняются от идеи и объема технических решений настоящего изобретения.