16. Маршрутизация пакетов. Маршрутная таблица. Алгоритмы маршрутизации. Понятие метрики.

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

Ограничения взаимодействия сетей на канальном уровне.

1. Не поддерживается единая система физической адресации.

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

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

Функции маршрутизаторов:

1. Поддержание актуальной информации о возможных маршрутах в сети.

2. Определение оптимального маршрута пересылки.

3. Собственно пересылка пакетов.

Маршрутная информация хранится в форме таблиц и может содержать:

1. информацию о всех существующих и доступных в данный момент маршрутах.

2. Информация хранится только о ближайших маршрутах.

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

Выбор маршрутизатора осуществляется в соответствии с алгоритмом маршрутизации.

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

• Статические и динамические (адаптивные)

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

• Одно- и многомаршрутные

Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого. Многомаршрутные алгоритмы могут обеспечить значительно большую пропускную способность и надежность.

• Одноуровневые и иерархические

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

• Внутри и междоменные

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

• Дистанционно-векторные (пример в стеке TCP/IP – RIP; в д-в алгоритмах осуществляется обмен большими объёмами маршрутной информации, но только между ближайшими соседями) и алгоритмы состояния каналов (в TCP/IP – OSPF; рассылка небольших порций маршрутной информации, но по всем маршрутизаторам)

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

Адаптивная маршрутизация включает:

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

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

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

- передачу информации о состоянии сети, используемую для корректировки таблиц маршрутов

- корректировку маршрутов

Метрика – показатель, используемый программами маршрутизации для определения оптимального маршрута.

Пример метрики: 1) длина маршрута, она измеряется в количестве переходов («хоп»).

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