Принципы и алгоритмы маршрутизации

В архитектуре TCP/IP сети соединяются друг с другом коммутаторами IP-пакетов, которые называются шлюзами или IP-маршрутизаторами.

Основная задача IP-маршрутизатора — определение по специальному алгоритму адреса следующего IP-маршрутизатора.

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

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

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

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

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

Кроме перечисленных выше задач IP-маршрутизатор должен обеспечивать эффективное распределение собственных ресурсов как по пропускной способности каналов, так и по объёму буферных ЗУ, используемых для хранения пакетов, ожидающих передачу. Самая очевидная стратегия «первым пришёл — первым обслужен» (FCFS — First Come First Served) может оказаться неприемлемой в условиях перегрузки сети.

Так, например, нельзя допустить, чтобы высокоскоростной канал захватил весь объём буферных ЗУ, ничего не оставив низкоскоростному каналу. В хороших алгоритмах обязательно должно учитываться поле «Тип сервиса» заголовка IP-пакета; IP-маршрутизатор может назначить больший приоритет IP-пакетам, передающим управляющую или служебную информацию.

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

По техническим, административным, географическим, а также иногда и политическим соображениям IP-маршрутизаторы группируются в так называемые «автономные системы».

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

Конкретный вариант протокола маршрутизации, действующий внутри одной автономной системы, называется внутренним протоколом маршрутизации (IGP — Interior Gateway Protocol).

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

Протокол для обмена служебной информацией между автономными системами называется внешним протоколом маршрутизации (EGP — Exterior Gateway Protocol).

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

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

Просмотр таблицы маршрутизации происходит в три этапа:

· - ищется соответствие адреса, записанного в IP-пакете, адресу места назначения в маршрутной таблице. В случае успеха пакет посылается соответствующему IP-маршрутизатору или непосредственно хост-ЭВМ;

· - ищется соответствие адреса, записанного в IP-пакете, адресу некоторой региональной сети места назначения. В случае успеха система действует так же, как и в предыдущем пункте;

· - ищется маршрут «по умолчанию», если таковой предусмотрен; дейтаграмма посылается в соответствующий маршрутизатор.

Существуют статические и динамические алгоритмы обновления таблицы.

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

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

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

Шлюзы, входящие в состав одной автономной системы, могут выполнять алгоритм динамической маршрутизации — протоколы на основе алгоритма Беллмана-Форда и протоколы на основе алгоритма Дейкстры.

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

Шлюзы, работающие по алгоритму Беллмана-Форда, хранят вектор длин кратчайших маршрутов для всех сетей, входящих в состав объединённой сети.
Периодически каждый шлюз передаёт свой вектор соседним шлюзам автономной системы, а элементы вектора, принятого от соседнего шлюза, складываются с длинами исходящих линий связи.

На основе полученной таблицы строится новый вектор длин кратчайших маршрутов — алгоритм Беллмана-Форда (DV — алгоритм Distance Vector).

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

Шлюзы, работающие по алгоритму Дейкстры (Shortest Path First — SPF-алгоритм), сначала определяют кратчайшие маршруты по всем сетям автономной системы. Для этого в каждом шлюзе строится полное дерево кратчайших путей с корнем в данном шлюзе.

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

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

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

В целом, алгоритм Дейкстры, по сравнению с алгоритмом Беллмана-Форда, обеспечивает более реальную оценку ситуации в сети, более быструю реакцию на важные изменения в сети (такие, как включение новой линии связи) и уменьшает зацикливание пакетов; однако алгоритм Дейкстры сложнее в реализации и требует в несколько раз больше памяти.