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

ОБЗОР АЛГОРИТМОВ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНЫХ СЕТЯХ Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Федотова Л.Д.

Описываются статические и динамические виды маршрутизации. Приводится сравнение нескольких видов алгоритмов маршрутизации : алгоритм Дейкстры, алгоритм Беллмана-Форда и алгоритм Флойда-Уоршелла. Рассматривается проблема доставки информации при удаленных процессах. Приводится обзор существующих программных средств для моделирования передачи данных.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Федотова Л.Д.

Совершенствование комбинированной метрики маршрутизации в IP-телефонии на примере транспортно-логистического центра

OVERVIEW OF ROUTING ALGORITHMICS IN COMPUTER NETWORKS

Static and dynamic routing types are described. A comparison of several types of routing algorithms is given: Dijkstra’s algorithm, Bellman-Ford algorithm and Floyd-Worshell algorithm. The problem of information delivery during remote processes is considered. Provides an overview of existing software tools for data transfer modeling.

Текст научной работы на тему «ОБЗОР АЛГОРИТМОВ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНЫХ СЕТЯХ»

ОБЗОР АЛГОРИТМОВ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНЫХ СЕТЯХ

Л. Д. Федотова Научный руководитель — А. А. Кузнецов

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Описываются статические и динамические виды маршрутизации. Приводится сравнение нескольких видов алгоритмов маршрутизации: алгоритм Дейкстры, алгоритм Беллмана-Форда и алгоритм Флойда-Уоршелла. Рассматривается проблема доставки информации при удаленных процессах. Приводится обзор существующих программных средств для моделирования передачи данных.

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

OVERVIEW OF ROUTING ALGORITHMICS IN COMPUTER NETWORKS

L. D. Fedotova Scientific Supervisor — A. A. Kuznetsov

Reshetnev Siberian State University of Science and Technology 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

Static and dynamic routing types are described. A comparison of several types of routing algorithms is given: Dijkstra’s algorithm, Bellman-Ford algorithm andFloyd-Worshell algorithm. The problem of information delivery during remote processes is considered. Provides an overview of existing software tools for data transfer modeling.

Keywords: IT, computer networks, routing algorithms, software.

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

Алгоритмы маршрутизации — это набор алгоритмов, которые определяют наилучший путь пакетов от источника к приемнику [1]. Они рассматриваются как граф и являются основой любого протокола маршрутизации.

Есть статические и динамические виды маршрутизации. Статический алгоритм заключается в построении конечной таблицы маршрутов при генерации сети. А в динамической маршрутизации таблица маршрутов изменяется в зависимости от состояния и загрузки каналов передачи данных и узлов коммутации [2].

Рассмотрим три классических вида алгоритмов маршрутизации:

3. Алгоритм Флойда-Уоршелла. и проведем сравнение между ними.

Секция «Прикладная математика»

Алгоритм Дейкстры находит кратчайшие пути от одной из вершин графа до всех остальных. Он используется только для графов без ребер отрицательного веса. Применяется он в программировании и технологиях, например, используется в протоколах маршрутизации OSPF и IS-IS. Алгоритм Беллмана-Форда находит кратчайший путь во взвешенном графе. За определенное время он находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает ребра с отрицательным весом. Этот алгоритм маршрутизации RIP (алгоритм Беллмана-Форда) был разработан, как основой для сети ARPANET. Алгоритм Флойда-Уоршелла находит кратчайшие расстояния межу вершинами взвешенного ориентированного графа. Он применяется для расчета всех кратчайших путей в плотных графах, когда есть большое количество пар ребер между парами вершин. Алгоритм Дейкстры более эффективен в случае разреженных графов с ребрами неотрицательного веса для каждого возможного узла [3].

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

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

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

Пакет, в компьютерных сетях — это оформленный блок данных, передаваемый по сети в пакетном режиме. Пакетом можно назвать любое сообщение, форматированное для него. «Надёжная» служба уведомляет пользователя о том, что доставка не удалась, как «ненадёжная» служба не уведомляет пользователя. Например, IP и UDP с IP не обеспечивает надёжного сервиса, в отличии от TCP и IP. Все эти протоколы используют пакеты, а UDP-пакеты называют дейтаграммами, которые используется для пакетов «ненадёжных» служб. Компьютерная сеть ARPANET не может надёжно определить все неудачные доставки пакетов.

Пакет протокола IPX имеет более простую структуру по сравнению с пакетом IP, и может пересечь до 15 маршрутизаторов. Сетевой протокол ICMP, входящий в стек протоколов TCP/IP, используется для передачи сообщений об ошибках и других исключительных ситуациях, возникших при передаче данных. ICMP-сообщения генерируются маршрутизатором при отсутствии маршрута к адресату и строятся из IP-пакетов, сгенерировавших ICMP-ответ. Для того, чтобы отправить ICMP-сообщение обратно отправителю, IP инкапсулирует соответствующее ICMP-сообщение с новым заголовком IP и передает полученные пакеты дальше. Протокол OSPF динамической маршрутизации, основанный на алгоритме Дейкстры, распространяет информацию о доступных маршрутах между маршрутизаторами одной автономной системы [5].

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

1. Семенов, Ю. А. Алгоритмы телекоммуникационных сетей. Часть 2. Протоколы и алгоритмы маршрутизации в Internet / Ю. А. Семенов // М.: Бином. Лаборатория знаний, 2016. — 829 с.

2. Руководство Cisco по междоменной многоадресатной маршрутизации. — М.: «Вильямс», 2004. — 320 с.

3. Алгоритмы: построение и анализ. 2-е изд. / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн // М.: «Вильямс», 2006. — 1296 с.

4. Коньков, К. А. Основы операционных систем / К. А. Коньков, В. Е. Карпов // Бишкек: МА-УПФиБ, 2015. — С. 144-159.

5. Dean, T. Network+ Guide to Networks / T. Dean // Boston, Massachusetts: Thomson Course Technology, 2006. — 896 с.

Источник

4.7. Маршрутизация. Виды и алгоритмы маршрутизации.

Маршрутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. Маршрутизация часто противопоставляется объединению сетей с помощью моста, которое, в популярном понимании этого способа, выполняет точно такие же функции. Основное различие между ними заключается в том, что объединение с помощью моста имеет место на Уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на Уровне 3. Этой разницей объясняется то, что маршрутизаторы используют логические адреса (например, IP-адреса), а мосты — аппаратные адреса.

С коммерческой точки зрения маршрутизация приобрела популярность только в 1970 гг.

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

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

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

4.7.1. Алгоритм поиска маршрута в таблице маршрутизации

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

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

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

В стеке TCP/IP не только маршрутизаторы, но и конечные узлы принимают решения о том, кому передавать пакет для его успешной доставки узлу назначения, на основании так называемых таблиц маршрутизации (routing tables).

Рассмотрим следующий пример организации небольшой сети класса С, соединенной с провайдером Internet через маршрутизатор, который в то же время, обеспечивает связь между этими двумя сегментами. Пусть сетевой номер, выделенный этой организации – 210.20.30, а адрес Internet-шлюза – 210.20.30.254.

Сеть разбита на три сегмента. Адреса первого могут принимать значения с 210.20.30.0 по 210.20.30.63, второго с 210.20.30.64 по 210.20.30.127, третьего с 210.20.30.192 по 210.20.30.255. маской данной сети будет – 255.255.255.192..

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

Источник