Маршрутизаторы и алгоритмы маршрутизации

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

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

Основы

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

Основываясь на том, как маршрутизаторы собирают информацию об окружающей сети, можно выделить два главных алгоритма маршрутизации: централизованные(global routing algorithms) и (распределенные) децентрализованные (decentralized routing algorithms). В рамках распределенного алгоритма, у каждого маршрутизатора есть информации о роутерах, с которыми он непосредственно связан, он не знает о всех маршрутизаторах в сети. Этот алгоритм также известен как DV (distance vector). При глобальной, централизованной маршрутизации, у каждого устройства есть информация обо всех маршрутизаторах в сети и состоянии всей сети передачи данных. Другое название этого алгоритма - LS (link state).

LS-алгоритм (централизованная маршрутизация)

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

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

2. Измерить время задержки (или среднюю скорость передачи данных) для соседних устройств. Для того, чтобы сделать это, маршрутизаторы отправляют echo-пакеты в сеть, на которые получают соответствующий ответ. Разделив время запроса в пути на 2 , можно рассчитать время задержки, причем в это время будет заложен также период задержки обработки пакета маршрутизаторами.

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

Плюсы и минусы
+легкость в реализации
-сложность изменения топологии и нагрузки
-нет обмена данными о маршрутизации между роутерами

DV-алгоритм (децентрализованная или распределенная маршрутизация)

Алгортитм распределенной маршрутизации, известный также как алгоритм Беллмана-Форда (Bellman-Ford) и Форда-Фалкерсона (Ford-Fulkerson).

Также известен как Distributed Bellman-Ford Routing или Ford Fulkerson Algorithm. Его можно метафорически описать как: «расскажи своим соседям, как выглядит мир». Каждый маршрутизатор ведет таблицу роутинга с одной записью для каждого узла подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает расстояние (количество переходов между узлами, задержку или длину очереди) до каждого соседнего устройства и рассылает её своим соседям, которые повторяют эти действия. В результате собранной информации каждый роутер снова формирует таблицу маршрутизации.

То есть маршрутизатор совершает следующие действия:

1. Оценивает вес ссылок напрямую связанных с ним устройств

2. В определенное время отправляет эту информацию соседнему маршрутизатору им получает соответствующую информацию от соседнего роутера.

3. На основе этой информации строит или обновляет свою таблицу маршрутизации.

Плюсы и минусы
+самоорганизация
+сравнительная простота реализации
-низкая конвергенция или «сходимость»
-расширение сети связано с некоторыми сложностями

Иерархическая (смешанная) маршрутизация

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

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

Источник: http://computer.howstuffworks.com/