Способ определения оптимального маршрута при IP-маршрутизации Российский патент 2025 года по МПК H04L45/48 H04L45/02 

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

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

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

Известен способ проверки связанности узлов сети сессий («АКР packet processing method, communication system and device» патент US 8542684 B2, H04L 45/745, опуб. 24.09.2013), его недостатком является невозможность построения защищенной сети по причинам: отсутствия проверки подлинности пакетов с информацией, необходимой для построения и обеспечения функционирования сети; возможности подмены записей в ARP-таблицах сторонним подключенным в сеть устройством; осуществления проверки связанности узлов в том же канале, в котором осуществляется передача данных.

Известен аналог - способ маршрутизации в сети связи с высокой вероятностью отказов ее элементов (патент RU 2814686 C1, H04L 45/02, опуб. 04.03.2024), в котором измеряют состояние каналов связи между смежными узами сети связи, методом лавинной рассылки распространяют информацию о состоянии смежных каналов связи между всеми узлами сети связи, на каждом узле связи строят граф, отражающий логическую структуру сети связи, осуществляют периодическое измерение состояния каналов связи и оценку состояний логических структур сети связи, сохраняют в сформированной памяти все множество логических структур, образующихся в процессе эксплуатации сети связи, и определенных для них оптимальных маршрутов, с их извлечением из памяти и использованием вместо повторного вычисления в случае повторения логических структур в процессе дальнейшей эксплуатации сети связи.

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

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

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

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

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

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

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

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

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

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

COST=1'000'000'000'000 / SPEED,

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

на втором этапе определяются маршруты до отдельных подсетей, последовательно перебираются все сети из базы сетей (NDB) и для каждой сети вычисляется стоимость пути до нее (COST_NET), как сумма пути до узла связи, к которому подключена сеть, плюс стоимость выхода в эту сеть, вычисляемая на основе суммы скорости всех интерфейсов узла связи (COST_DNET), которые подключены к этой сети

после вычисления оптимальными маршрутами до каждой подсети будут только оптимальные пути COST_DNET,

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

В предпочтительном варианте изобретения, в случае наличия нескольких путей равной стоимости к одному узлу связи, трафик отправляется через маршрут с меньшим значением уникального идентификатора узла связи - маршрутизатора (Router ID).

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

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

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

Изобретение поясняется следующими графическими материалами:

Фиг.1 - упрощенное представление транзитной сети и сети прямого подключения.

Фиг. 2 - сеть маршрутной информации.

Фиг. 3-блок-схема абстрактной сети маршрутизации.

Фиг. 4 - блок-схема графа связи абстрактной сети маршрутизации.

Фиг. 5-7 - блок-схемы различных примеров сети маршрутизации.

Осуществление изобретения

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

Обмен пакетами протокола ENDP (ENDP - External Network Dynamic Protocol) осуществляется по протоколу IP. IP-адрес соседних маршрутизаторов задает администратор сети. Информация об IP-интерфейсах и МАС-адресах маршрутизаторов на линейных интерфейсах передается по протоколу ENDP через выделенные интерфейсы управления. IP-адрес отправителя пакета ENDP является адресом одного из соседних маршрутизаторов, а IP-адрес получателя - адресом второго из соседних маршрутизаторов. Для передачи пакетов ENDP через выделенный интерфейс управления используется стандартный сетевой протокол IP с указанием кода IP-протокола.

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

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

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

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

Протокол ARP описан в спецификации RFC 826 «User Datagram Protocol)), и включает в себя следующую последовательность шагов: узел, которому нужно выполнить отображение IP-адреса на аппаратный адрес (МАС-адрес), формирует ARP-запрос с IP-адресом получателя, вкладывает его в кадр протокола канального уровня и рассылает всем узлам локальной сети. Все узлы сегмента локальной сети получают ARP-запрос и сравнивают указанный в нем IP-адрес с собственным. В случае совпадения собственного IP-адреса с полученным в ARP-запросе, узел формирует ARP-ответ, в котором указывает свой IP и MAC адреса, после чего отправляет ARP-ответ в адрес отправителя ARP-запроса. Преобразование адресов выполняется путем поиска в таблице ARP соответствия IP и MAC адресов. ARP-таблица хранится в памяти операционной системы и содержит записи для каждого известного ей узла сети. В двух столбцах содержатся адреса IP и Ethernet (MAC), и если требуется преобразовать адрес IP в MAC, то в ARP-таблице ищется запись с соответствующим IP-адресом.

С точки зрения протокола ENDP сеть выглядит следующим образом:

Первые два вида сетей можно изобразить в упрощенной форме (фиг. 1), где подсеть 6.0.0.0/24 является сетью прямого подключения (direct) для маршрутизаторов R1 и R2, а также является транзитной сетью от R1 к R2 и наоборот.

В результате в NDB будут присутствовать следующие записи:

Связи маршрутизаторов в рамках сети описывается направленным графом. Вершинами графов являются маршрутизаторы, плечами графа -транзитные сети, соединяющие маршрутизаторы в сети ENDP. Сети прямого подключения плечами не являются и в построение графа не учитываются.

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

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

Более подробно алгоритм обработки изменений маршрутной информации описан далее.

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

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

Поэтапно процесс построения графа на примере сети из четырех узлов связи - маршрутизаторов показан на фиг. 6.

На первом этапе рассчитываются кратчайшие пути до каждого маршрутизатора внутри сети. Расчет кратчайшего пути выполняется на основе алгоритма Дейкстры.

Математическое описание алгоритма, реализованного в ENDP.

Пусть задан ориентированный взвешенный граф G=(V,E) с неотрицательными весами ребер f(e) и выделенной вершиной-источником и. Обозначим через d(v) кратчайшее расстояние от источника u до вершины v.

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

Пусть

Тогда d(w)=d(v)+f(e), и v лежит на кратчайшем пути от u к w.

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

Вычислительная сложность алгоритма «Дейкстры», реализованного в ENDP.

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

Последовательная сложность алгоритма равна O(C₁m+C₂n), где

C₁ - количество операций уменьшения расстояния до вершины;

С₂ - количество операций вычисления минимума.

Алгоритм использует в качестве внутренней структуры данных списки, для которых C₁=O(l), С2=O(n), так что общая сложность составляла O(n²).

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

Стоимость плеча рассчитывается по формуле:

COST=1'000'000'000'000 / SPEED,

где SPEED - это скорость сетевого интерфейса в битах в секунду.

Примеры соответствий скорости и стоимости представлены в таблице значений стоимости интерфейсов

Цена прохождения каждого плеча равна стоимости прохода через транзитную сеть (вычисляется на основе скорости интерфейса, которому соответствует ARP-запись IP-интерфейса соседа). Далее, начиная с вершины, которая соответствует маршрутизатору, выполняющему вычисления, по алгоритму «Дейкстры» рассчитывается кратчайший путь до всех маршрутизаторов сегмента сети. Стоимость пути до каждого маршрутизатора (COST_R) рассчитывается как сумма стоимости всех плеч (транзитных подсетей COST_tmet), через которые проходит путь до маршрутизатора.

где транзитных подсетей COST_tmet от 1 до N - плеч.

При наличии двух маршрутизатора R1 и R2, которые соединены друг с другом через 100 м, получим следующие записи в таблице стоимости.

Добавим маршрутизатор R3 и соединим его с R1 через 1G канал, а с R2 через 10G канал. Результат расчета стоимости отразим на фиг. 5, и получим следующие записи в таблице стоимости.

Для большей вариативности добавим четвертый маршрутизатор R4 с 1G каналом до R2 и 100М каналом до R3 (фиг. 6), и получим следующие записи в таблице стоимости.

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

На втором этапе определяются маршруты до отдельных подсетей. Последовательно перебираются все сети из базы сетей (NDB) и для каждой сети вычисляется стоимость пути до нее (COST_NET), как сумма пути до маршрутизатора, к которому подключена сеть, плюс стоимость выхода в эту сеть, вычисляемая на основе суммы скорости всех интерфейсов маршрутизатора (COST_DNET), которые подключены к этой сети.

Добавим к каждому маршрутизатору direct сеть (А, В, С, D) и транзитные сети (Е, F, Н, К, М), после чего рассчитаем все маршруты для R1 (фиг. 7), и получим следующие записи в таблице стоимости.

По результатам расчетов, оптимальными маршрутами до каждой подсети будут маршруты 1, 2, 4, 6, 7, 9, 10, 11, 12 и 13.

При наличии нескольких путей равной стоимости к одному адресату, трафик отправляется через маршрут с меньшим значением Router ID. Если сеть подключена более чем к одному маршрутизатору, то выбирается путь через маршрутизатор с наименьшей стоимостью COST_NET- Если таких маршрутизаторов несколько, то будет выбран путь через маршрутизатор с меньшим Router ID.

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

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

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

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

Изобретение относится к cредствам маршрутизации для определения оптимального маршрута. Техническим результатом изобретения является обеспечение эффективного, быстрого и низкозатратного по вычислительным ресурсам определения оптимального маршрута в сетях коммутации и IP-маршрутизации данных. Осуществляют поиск оптимальных маршрутов, где рассчитывают кратчайшие пути до каждого узла связи внутри сети, где стоимость прохождения плеча графа определяется скоростью транзитной сети, соответствующей плечу, где при наличии нескольких путей между узлами связи, будет выбран тот путь, суммарная стоимость пройденных плечей которого будет наименьшей¸ а стоимость плеча определяется COST = 1'000'000'000'000 / SPEED, где SPEED – это скорость сетевого интерфейса в битах в секунду, а цена прохождения каждого плеча равна стоимости прохода через транзитную сеть, начиная с вершины, которая соответствует узлу связи, выполняющему вычисления, определяется кратчайший путь до всех узлов связи сегмента сети, где стоимость пути до каждого узла связи (COSTR) определяется как сумма стоимости всех плеч (транзитных подсетей COSTtrnet), через которые проходит путь до узла связи, COSTR = COSTtrnet1 +COSTtrnet2+ COSTtrnet3 + … +COSTtrnetN , и определяют маршруты до отдельных подсетей, последовательно перебираются все сети из базы сетей (NDB) и для каждой сети определяется стоимость пути до нее (COSTNET) как сумма пути до узла связи, к которому подключена сеть, плюс стоимость выхода в эту сеть, определяемая на основе суммы скорости всех интерфейсов узла связи (COSTDNET), которые подключены к этой сети COSTNET = COSTR + COSTDNET, после определений оптимальными маршрутами до каждой подсети будут только оптимальные пути COSTNET, и добавляют соответствующую запись оптимальных маршрутов в память NDB. 2 з.п. ф-лы, 7 ил.

1. Способ определения оптимального маршрута при IP-маршрутизации, при котором осуществляют:

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

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

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

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

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

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

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

COST = 1'000'000'000'000 / SPEED,

где SPEED – это скорость сетевого интерфейса в битах в секунду,

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

COSTR = COSTtrnet1 +COSTtrnet2+ COSTtrnet3 + … +COSTtrnetN,

на втором этапе определяются маршруты до отдельных подсетей, последовательно перебираются все сети из базы сетей (NDB) и для каждой сети вычисляется стоимость пути до нее (COST_NET), как сумма пути до узла связи, к которому подключена сеть, плюс стоимость выхода в эту сеть, вычисляемая на основе суммы скорости всех интерфейсов узла связи (COST_DNET), которые подключены к этой сети

COST_NET = COST_R + COST_DNET

после вычисления оптимальными маршрутами до каждой подсети будут только оптимальные пути COST_DNET,

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

2. Способ определения оптимального маршрута при IP-маршрутизации по п. 1, отличающийся тем, что в случае наличия нескольких путей равной стоимости к одному узлу связи, трафик отправляется через маршрут с меньшим значением уникального идентификатора узла связи – маршрутизатора (Router ID).

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