СПОСОБ МАРШРУТИЗАЦИИ В СЕТИ СВЯЗИ С ВЫСОКОЙ ВЕРОЯТНОСТЬЮ ОТКАЗОВ ЕЕ ЭЛЕМЕНТОВ Российский патент 2024 года по МПК H04L45/02 

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

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

Сеть связи с коммутацией пакетов представляет собой множество узлов связи (маршрутизаторов), соединенных линиями связи. Каждый маршрутизатор (порт маршрутизатора) имеет уникальный идентификатор (IP-адрес) и функционирует в соответствии с принятыми на сети способами (протоколами) взаимодействия.

Способы взаимодействия элементов сети связи составляют ее архитектуру. Архитектура сетей связи с коммутацией пакетов предполагает сохранение связи (непрерывность процесса информационного обмена) между корреспондентами в случае отказов элементов сети, при условии, что остается физическая связанность (рабочий физический путь) между корреспондентами [D.D. Clark, “The Design Philosophy of the DARPA Internet Protocols,”ACM SIGCOMM Computer Communication Review, vol. 18, no. 4, 1988, pp. 106–114].

Процесс поиска пути для транспортировки пакетов называется маршрутизацией. Задача маршрутизации состоит в поиске оптимального пути (маршрута) между корреспондентами.

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

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

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

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

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

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

Известен способ маршрутизации пакетов данных между множеством коммутирующих устройств [патент РФ №2598322, H04L 12/28, опубл. 20.09.2016 г. Бюлл. № 26], заключающийся в том, что между множеством сетевых устройств коммутации пакетов, первое сетевое устройство после проверки сообщения данных производит сопоставление значений приоритетов текущего и второго сетевых устройств и для сетевого устройства с меньшим приоритетом блокирует ответ посредством сопряженного с указанным сетевым устройством порта первого сетевого устройства, причем значением приоритета сетевого устройства является величина, обратная расстоянию от сетевого устройства до хост-устройства, выраженная в количестве промежуточных сетевых устройств, находящихся между сетевым устройством и хост-устройством, а вычисление значений расстояний для каждого из сетевых устройств производится с помощью дистанционно-векторного алгоритма.

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

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

Известен способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений [патент РФ №2765810, H04L 12/64, опубл. 03.02.2022 г. Бюлл. № 4], заключающийся в том, что в узлах связи осуществляют контроль качества входящих в них каналов связи, результаты этого контроля передают на другие доступные узлы связи, формируют одномерные маршруты передачи, которые объединяют в многомерные маршруты передачи, и определяют целевые функции многомерных маршрутов передачи, при этом для осуществления управления многомерной динамической маршрутизацией назначают методы разделения смежных каналов связи между узлами связи, предусматривающие использование различных физических полей, сред распространения сигналов и способов временного, частотного, поляризационного, кодового разделения; а также разделение по мощности, по пространственному кодированию, по модуляции, по скорости передачи, по форме сигнала, по протоколам обмена, для каждого канала связи в каждом узле связи и в каждом маршруте.

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

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

Наиболее близким по технической сущности и выполняемым функциям к заявленному (прототипом) является способ маршрутизации по протоколу OSPF (Open Shortest Path First, сначала открыть кратчайший путь).

OSPF – протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала и использующий для нахождения кратчайшего пути алгоритм Дейкстры [J. Moy RFC 2328 «OSPF Version 2», ISOC, 1998 244 p., https://www.ietf.org/rfc/rfc2328.txt.pdf].

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

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

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

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

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

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

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

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

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

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

1. Способ маршрутизации в сети связи с высокой вероятностью отказов ее элементов.

Заявленный способ поясняется чертежами:

фиг. 1 – блок-схема способа маршрутизации в сети связи с высокой вероятностью отказов ее элементов;

фиг. 2 – структура области памяти;

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

фиг. 4 – пример таблицы текущего состояния логической структуры сети связи после получения информации от всех узлов связи;

фиг. 5 – хронологическая схема изменения состояния сети связи.

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

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

Важным является предельное количество хранящихся записей (объема памяти), которое должно быть не более, чем m log n, где m – количество линий связи, а n – количество узлов связи. Пояснение данного ограничения представлено далее, в части описания, посвященной оценке эффективности.

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

Область памяти может быть сформирована на базе оперативной (RAM) или постоянной памяти (NVRAM) маршрутизатора. Например, маршрутизатор Cisco 1941 может иметь от 512 Мб до 2 Гб постоянной памяти [Cisco 1941 Series Integrated Services Routers Data sheet, 14 p. – 2017, www.cisco.com].

Также на узле связи может быть установлена дополнительные модули памяти, например, «MEM3800-256U1024D» или «MEM-C6K-CPTFL2GB».

1.2 Дальнейшие действия осуществляются в процессе эксплуатации сети связи, который на блок-схеме показан циклом (фиг. 1, блок 2-16), в котором: обнуляют служебную переменную t – текущее время эксплуатации (фиг. 1, блок 2), в теле цикла (фиг. 1, блоки 3-15) переменную t увеличивают на величину Δt соответствующую заданному периоду (фиг. 1, блок 3), проверяют условие выхода из цикла, соответствующее окончанию времени эксплуатации T (фиг. 1, блок 16).

С заданным периодом выполняют следующие действия.

1.3 Измеряют состояние каналов связи между смежными узлами сети связи (фиг. 1, блок 4).

Действие осуществляется в отношении каждой линии связи смежными с ней узлами связи (маршрутизаторами).

Одним из вариантов измерения состояния каналов связи является обмен служебными сообщениями по этим каналам по схеме запрос-ответ. Канал считается работоспособным в случае получения ответа в течение заданного времени и неработоспособным, в противном случае [J. Moy RFC 2328 «OSPF Version 2», ISOC, 1998 244 p., https://www.ietf.org/rfc/rfc2328.txt.pdf; Олифер В., Олифер Н. Компьютерные сети. Принципы, технологии, протоколы: Юбилейное издание. – СПб.: Питер, 2020. – 1008 с.: ил.].

Помимо этого, измерения состояния каналов связи могут быть осуществлены по методикам в соответствии с протоколами измерений сетей связи [RFC-2544; RFC-5357; Y.1564], с использованием программно-аппаратных комплексов, реализующих указанные методики, например, МАКС-ЕМК [Официальный сайт производителя: https://kometeh.ru/], M716-10G [Официальный сайт производителя: https://stc.metrotek.ru/] или ShinewayTech SWT-DTA-100D-ETH-SDH [Официальный сайт производителя: https://shinewaytech.com/].

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

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

Результаты измерений записывают в таблицу текущего состояния логической структуры (фиг. 3).

1.4 Распространяют информацию о появившихся или исчезнувших каналах связи (фиг. 1, блок 5) [J. Moy RFC 2328 «OSPF Version 2», ISOC, 1998 244 p., https://www.ietf.org/rfc/rfc2328.txt.pdf; Олифер В., Олифер Н. Компьютерные сети. Принципы, технологии, протоколы: Юбилейное издание. – СПб.: Питер, 2020. – 1008 с.: ил.].

Распространение информации осуществляется в соответствии с принятыми на сети способами, например, по протоколу TCP/IP, для чего формируется соответствующие пакеты, которые направляются через соединенные линией связи порты маршрутизаторов.

Образование каналов связи может быть осуществлено, например, с использованием оптических «MOXA SFP-1GLHLC-T», радио «Ruggedcom WiN7225» и «MAXBrridge CPE 50 SME» и других модулей, установленных на узлах связи.

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

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

Таким образом каждый маршрутизатор сети связи узнает состояние каналов всей сети связи.

1.5 Перестраивают граф, отражающий логическую структуру сети связи (фиг. 1, блок 6).

Граф – модель сети связи, отражающая ее структуру на уровне взаимных отношений узлов и линий связи и традиционно используемая для определения оптимальных маршрутов.

Граф, отражающий логическую структуру сети связи, – модель сети связи, отражающая не физическое соединение узлов связи, а их отношение (взаимодействие) на логическом уровне.

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

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

1.6 Осуществляют проверку, изменилась ли логическая структура сети.

1.7 Если логическая структура сети связи изменилась, то управление передается блоку 8 (фиг. 1) для выполнения процедур поиска оптимальных маршрутов для новой структуры, в противном случае управления передается блоку 3 (фиг. 1) для повторного выполнения процедур оценки состояния логической структуры сети связи.

1.8 В случае изменения логической структуры сети связи проверяют записи в сформированной области памяти (фиг. 1, блок 8).

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

Проверка записей в сформированной области памяти осуществляется поиском совпадения текущей логической структуры сети с записями в столбце «Логическая структура сети».

Если запись имеется, то управление передается блоку 9 (фиг. 1) для извлечения из памяти хранящихся оптимальных для текущей логической структуры маршрутов, в противном случае (запись отсутствует) управление передается блоку 12 (фиг. 1) для определения оптимальных для текущей логической структуры маршрутов.

1.9 Если запись имеется, то в качестве искомых маршрутов выбирают маршруты из хранящегося в памяти перечня оптимальных маршрутов, соответствующих текущему состоянию логической структуры сети связи (фиг. 1, блок 9).

Увеличивают счетчик состояния логической структуры на единицу (фиг. 1, блок 10) и сортируют записи в области памяти по убыванию (фиг. 1, блок 11).

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

1.10 Если записи не имеется, то определяют оптимальные маршруты для текущей логической структуры сети связи (фиг. 1, блок 12). Определение маршрутов может быть осуществлено как традиционно используемым в протоколе OSPF алгоритмом Дейкстры, так и любым другим [М. Нидхем, Э. Ходлер Графовые алгоритмы. Практическая реализация на платформах Apache Spark и Neo4j. / пер. с англ. В. С. Яценкова – М.: ДМК Пресс, 2020. – 258 с.: ил.].

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

При этом удаляют наименее часто встречающиеся записи (записи с наименьшим значением счетчика), в случае если их количество превышает m log n, где m – количество линий связи, а n – количество узлов связи.

Определенные маршруты используют в качестве искомых (фиг. 1, блок 15).

1.11 Таким образом, в блоках 12, 15 (фиг. 1) осуществляется поиск маршрутов традиционным способом, который заключается в определении оптимальных маршрутов каждый раз, когда изменяется логическая структура сети связи. В свою очередь, действия, непосредственно направленные на решение технической проблемы и достижение технического результата (фиг. 1, блоки 1, 4, 7, 8, 9, 10, 11, 13, 14) обобщенно состоят в том, что сохраняют в память логические структуры, формирующиеся в процессе эксплуатации сети и определенные для них оптимальные маршруты, оценивают логическую структуру, используют определенные оптимальные маршруты, хранящиеся в памяти, повторно в случае повторения логической структуры сети связи.

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

Технической проблемой является длительное время пребывания сети связи в неработоспособном состоянии.

На фиг. 5 представлена хронологическая схема изменения состояния сети связи. Так, время пребывания сети связи в неработоспособном состоянии (T_нер) складывается из времени измерения состояния каналов связи (t_изм.) времени распространения информации о состоянии каналов связи (t_распр.) и времени поиска оптимальных маршрутов (t_поиск.) для текущей логической структуры сети связи:

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

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

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

Вычислительная сложность алгоритма Дейкстры, используемого в способе-прототипе, является O(n²) при его классической реализации и m log n при его оптимизированной реализации, где m – количество ребер графа, а n – количество вершин графа [В.А. Козмидиади, А.Н. Маслов, Н.В. Петри Сложность вычислений и алгоритмов Издательство Мир, 1974, - 392 с.].

Вычислительная сложность поиска элемента в массиве составляет O(l), где l – количество записей в массиве [В.А. Козмидиади, А.Н. Маслов, Н.В. Петри Сложность вычислений и алгоритмов Издательство Мир, 1974, - 392 с.].

Учитывая ограничение на количество хранящихся в памяти записей l < m log n, то количество операций, выполняемых при поиске оптимальных маршрутов в памяти, а, следовательно, затрачиваемое время (t_поиск.) и затрачиваемая энергия будут меньше, чем при их повторном вычислении, согласно способа-прототипа.

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

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

Предварительные вычисления позволяют дополнительно сократить время поиска оптимальных маршрутов.

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

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

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

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

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

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

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

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

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

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

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