СПОСОБ МАРШРУТИЗАЦИИ ПАКЕТОВ ДАННЫХ МЕЖДУ МНОЖЕСТВОМ СЕТЕВЫХ КОММУТИРУЮЩИХ УСТРОЙСТВ Российский патент 2016 года по МПК H04L12/28 

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

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

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

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

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

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

Известен способ пакетной маршрутизации и реализующая его система, ориентированная на трассировку путей («Path oriented routing system and method for packet switching networks)), патент US 4736363 A, [1]), не имеющий общих признаков с предлагаемым изобретением, но обладающий схожим функциональным назначением.

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

Известен другой способ динамической маршрутизации по патенту US 7969915 В2 (((Technical enhancements to STP (IEEE 802.ID) implementation)), [2]), включающий в себя: проверку посредством первого сетевого устройства, предназначенного для обеспечения коммутации пакетов, первого сообщения в корневом порте первого сетевого устройства, которое включает в себя идентификатор подсоединенного к корневому порту текущего сетевого устройства и значение приоритета текущего корневого сетевого устройства; после проверки первого сообщения данных первым сетевым устройством и проверки второго сообщения данных во втором порте первого сетевого устройства, которая включает в себя идентификацию и вычисление приоритета второго сетевого устройства; после проверки второго сообщения данных, если значение таймера (давности) сообщений первого сетевого устройства меньше значения, оставшегося до установленного предельного времени ожидания, то блокируется ответ посредством второго порта первого сетевого устройства на второе сообщение данных от второго сетевого устройства, причем, в том числе, первое и второе сетевые устройства настроены в соответствии с протоколом, позволяющим избежать образования петель, протоколом, позволяющим избежать образования петель, является протокол связующего дерева (Spanning Tree Protocol, STP).

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

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

Указанные недостатки преодолены в предлагаемом способе динамической маршрутизации пакетов данных между множеством сетевых коммутирующих устройств, заключающемся в том, что в способ, содержащий признаки прототипа: проверку первым сетевым коммутирующим устройством первого сообщения данных в корневом порту первого сетевого коммутирующего устройства, первое сообщение данных включает в себя идентификатор текущего сетевого коммутирующего устройства, подсоединенного к корневому порту первого сетевого коммутирующего устройства, и значение приоритета текущего сетевого коммутирующего устройства, после проверки первого сообщения данных первым сетевым коммутирующим устройством указанным устройством производится проверка второго сообщения данных во втором порте первого сетевого коммутирующего устройства, которая включает в себя идентификацию и вычисление значения приоритета второго сетевого коммутирующего устройства, подключенного ко второму порту первого сетевого коммутирующих устройства, включены новые признаки: первым сетевым коммутирующим устройством после проверки сообщения данных производится сопоставление значений приоритетов текущего и второго сетевых коммутирующих устройств и для сетевого коммутирующего устройства, обладающего меньшим приоритетом, блокируется ответ посредством сопряженного с указанным сетевым коммутирующим устройством порта первого сетевого коммутирующего устройства, причем значением приоритета сетевого коммутирующего устройства является величина, обратная расстоянию от сетевого коммутирующего устройства до хост-устройства, выраженному в количестве промежуточных сетевых коммутирующих устройств, находящихся между сетевым коммутирующим устройством и хост-устройством, а вычисление значений расстояний для каждого из сетевых коммутирующих устройств производится с помощью дистанционно-векторного алгоритма (Distance Vector Algorithm, DVA).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Использованные источники информации

1. Патент US 4736363 А от 11.10.1985 г. «Path oriented routing system and method for packet switching networks)).

2. Патент US 7969915 B2 от 24.07.2009 г. «Technical enhancements to STP (IEEE 802.1D) implementation.

3. http://www.protocols.ru. Протокол RIP версии 2.

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

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