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

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

Ключевые слова: маршрутизация, адаптивная модель, IР-сеть, динамическая маршрутизаци

Abstract: this article describes the methods of adaptive routing, which are used in computer networks. The basic routing methods and algorithms that are used in the Internet are analyzed

Keywords: routing, adaptive model, IP network, dynamic routing

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

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

Задачи исследования:

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

Маршрутизатор – это узел сети с несколькими IР-интерфейсами, которые подключены к разным IР-сетям, осуществляющие на основании решения задачи маршрутизации направление из одной сети в другую с целью доставки от отправителя к получателю.

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

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

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

Даже в динамически маршрутизируемой сети, самый прямой и короткий путь бывает найден не с первой попытки. Используя протоколы, данные собирают топографию сети когда они движутся по сети, чтобы определить, какие маршруты являются жизнеспособными и какой маршрут является самым быстрым. Эта информация зависит от состояния сети. Государственная информация передается через адаптивные протоколы маршрутизации на каждом узле. Несколько адаптивных протоколов маршрутизации были разработаны для различных целей. Промежуточная система к промежуточной системе — этот протокол предназначен для перенаправления данных через большие сети, такие как Интернет-магистрали. Информация протокола маршрутизации (Rip) идеально подходит для небольших расстояний. Некоторые экспериментальные протоколы могут увеличить скорость и эффективность движения пакетов без полного знания состояния сети. Те же концепции, которые используются, чтобы найти путь от одного узла сети к другому также могут применяться в приложениях, таких как системы глобального позиционирования. С информацией о состоянии города и его улиц, эффективный маршрут из одного места в другое можно изобразить графически. Добавление информации в реальном времени, трафик может добавить вес к каждому узлу, или на улице, в городе, позволяя построить быстрый курс который может быть определён в этой сети.

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

Разработка методов адаптивной маршрутизации

Одним из перспективных направлений для решения такой задачи являются развитие методов распределения информации [2, 3, 7]. В связи с этим следует остановиться на видах маршрутизации информации.

Наиболее простыми являются локальные методы маршрутизации. Управляющие решения по выбору маршрута строятся здесь только на основе локально доступной в каждом узле информации. Информация представляет собой заранее загруженные в узлы таблицы маршрутизации, сведения о текущем состоянии входных каналов (открыты — закрыты) и длинах очередей пакетов, ожидающих передачи по каждому из каналов. В частности, для сети [1], работающей в виртуальном (лат. virtualis — возможный) режиме, каждая строка таблицы маршрутов определяет порядок выбора исходящих из данного узла логических линий при установлении виртуального маршрута к заданному узлу. В случае дейтаграммного режима строка таблицы маршрутов может задавать вероятности, на основе которых каждый пакет, предназначенный для  узла, направляется в тот или иной канал.

Распределенная адаптивная маршрутизация является до настоящего времени наиболее распространенной в сети связи. Достоинства и недостатки этого метода можно проследить на примере сети АRРА [5, 6].

Цель алгоритма АRРА — это отыскание путей с минимальным временем задержки передаваемого трафика. Каждый узел сети формирует таблицы маршрутов по всем узлам назначения, минимизирующие задержки с указанием текущего времени передачи к каждому адресату. До начала работы сети эти времена оценивались, исходя из топологии сети, однако в процессе работы эти времена заменялись временами фактической передачи, полученными в результате измерений на сети. Конкретные модификации алгоритмов маршрутизации в сети АRРА подробно описаны в литературе [6, 9]. Версия АRРА описана в [6, 8]. Отметим особенности более поздней известной версии АRРА. Это асинхронный вариант с дополнительной адаптацией интервала обмена информации о задержках в зависимости от состояния сети. Кроме этого, служебная информация по маршрутизации «волной» рассылалась по всей сети и в каждом узле вырабатывалась результирующая матрица маршрутов по алгоритму Дейкстры, т.е. в каждом узле использовалась информация обо всей сети [8]. Практика показала, что этот метод обеспечивает эффективную маршрутизацию при различных распределениях трафика.

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

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

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

 К гибридной маршрутизации относится «дельта — маршрутизация», разработанная Н. Рудиным [6].

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

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

В работах [5] разработан еще один метод маршрутизации: упреждающий метод — это сочетание гибридной маршрутизации с прогнозированием в центральном пункте управления. Особенностью данного метода маршрутизации с прогнозированием является применение иерархической маршрутизации с использованием оперативных методов статистического прогнозирования в центре управления. Достоинством этого метода маршрутизации является учет всех положительных черт ранее указанных методов. Прогнозирование в центральном узле обеспечивает координацию управления на разных уровнях иерархии. Отличие данного метода маршрутизации от предшествующих методов заключается в прогнозировании работоспособности всех узлов сети и наличие каналов связи между узлами. Недостатком данного метода является то, что он разрабатывался для широкомасштабных сетей, в которых идея создания строилась на организации связи между регионами (локальными сетями) и в которых предусматривалась потеря части информации. При использовании D — метода с прогнозированием в трактах локальных информационных сетей при передаче больших объемов информации проявляются недостатки метода и отсутствует возможность самостоятельного принятия решения узлами связи об организации передачи трафика или отказе от выполнения работ, а также выдаче рекомендации центральному органу управления о прогнозе своей работоспособности на ближайший определенный промежуток времени. Кроме того, при отказе центрального узла управления с учетом условий любых воздействий на тракты в сети отсутствует учет состояния тракта и изолированные части работают в режиме неопределенности информации. Следовательно, стоит задача разработки новых адаптивных методов маршрутизации, которые в условия внешних воздействий учтут положительные черты рассмотренных адаптивных методов и учтут специфику использования трактов локальных сетей связи.

Критерии маршрутизации

Определим критерии маршрутизируемости для информационных потоков.

Пусть ТКС задается графовой моделью. Пусть она будет называться простой таблицей маршрутизации τ_iузла а_i∈ А отображение множества узлов А ТКС на множество соседских узлов А_i∈А узла а_iτ_i:А ® А_i

С каждым узлом ТКС а_i ∈ А свяжем локальную базу данных и локальную базу знаний маршрутизации.

База данных определяется в качестве результата отображения τi, т.е. как набор пар узлов из Аi х τi (Аi)

База знаний является отображением τ_i.

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

Пусть для каждого узла ТКС задается связанная с ним база данных – это простая таблица маршрутизации. Множество таких таблиц называется простая маршрутизация ТКС.

Формально карта маршрутизации глобальной сети можно представить в форма набора локальных баз данных:

Т=( τ_i.)_i=1

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

Сетевое управление прокладкой маршрутов производится таким образом:

Фиксируется узел-получатель информации f и на него от узла-источника S с помощью последовательных отображений строится последовательность узлов ТКС, которые определяют маршрут передачи информации в следующем виде:

S=а₀,а₁,а₂…а_К=f

При этом для любого i=1,2…К. для маршрута используется отношение следующего вида:

 τ_i—₁(f)=а_i

Карту маршрутизации ТКС и соответствующей ей базу данных называют конкретной в том случае, если по ней возможно прокладывание маршрута передачи информации между любыми двумя узлами G (А,R,W).

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

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

Теорема выглядит следующим образом: карта маршрутизации ТКС только в тех случаях, когда для любого узла f ∈ А и для любого разбиения множества на непустые множества А₁ и А₂ и, такие что f ∈ А₁, найдутся узлы: а_i ∈ А₁ и а_i ∈ А₂., для которых справедливо соотношение.

Из данной теоремы следует, что для любого узла-источника данных S и любого узла –получателя данных f из множества А узлов ТКС существует маршрут передачи пакетов данных, иными словами последовательность узлов, что для всех i=1,2…К справедливым является соотношение.

Вывод

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

– обеспечение работоспособности и надежности ССУ или непредсказуемых изменениях структуры или параметров ТКС;

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

– упрощает управление потоками информации при сетевых перегрузках или сетевых конфликтах;

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

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

Модели адаптивной маршрутизации и управления потоками информации можно разделить на следующие группы:

– иерархическая маршрутизация;

– распределенная маршрутизация;

– гибридная маршрутизация.

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

Принцип децентрализованной маршрутизации базируется на обмене локальной информацией между узлами ТКС с целью определения локально-оптимального маршрута.

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

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

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

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

Список литературы

1. Балыбердин В.А. Оценка и оптимизация характеристик систем обработки данных. — М.: Радио и связь, 2017
2. Лукашин Ю.П. Адаптивные методы краткосрочного прогнозирования. — М.: Статистика, 2015
3. Морозов В.К., Долганов А.В. Основы теории информационных сетей. — М.: Высшая школа, 2017
4. Муралилдхаб К.Х., Сундарешан Н.И. Иерархический способ многоуровневой адаптивной маршрутизации в больших системах // ТИИЭР. — 2017. — Т. 721. — № 12.
5. Присяжнюк С.П. Оперативное перераспределение каналов. Сети, узлы связи и распределение информации. — Л.: ЛЭИС, 2017
6. Шварц М. Сети ЭВМ. Анализ и проектирование. Пер с англ. — М.: Радио и связь, 2017
7. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. — М.: Радио и связь, 2017.
8. Клейнрок Л. Вычислительные сети с очередями. — М.: Мир, 2016

Referenses

1. Balyberdin V. A. Evaluation and optimization of characteristics of data processing systems. — M.: Radio and communication, 2017
2. Lukashin Yu. P. Adaptive methods of short-term forecasting. — Moscow: Statistics, 2015
3. Morozov V. K., Dolganov A.V. Fundamentals of the theory of information networks. — Moscow: Higher school, 2017
4. Muralidhar, K. H., Sundaresan N. And. The hierarchical multilevel method, adaptive routing in large systems // TIIER. — 2017. — Vol. 721. — No. 12.
5. Prysiazhniuk S. P. rapid redistribution channels. Networks, communication nodes and information distribution. — L.: Leningrad electrical engineering Institute, 2017
6. Schwartz, M. computer Network. Analysis and design. Per with English. — M.: Radio and communication, 2017
7. Lazarev V. G., Lazarev Yu. V. Dynamic management of information flows in communication networks. — M.: Radio and communication, 2017.
8. Kleinrok L. computer networks with queues. — Moscow: World, 2016