Конспект лекций

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

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

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

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

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

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

По области своего действия алгоритмы делятся на  Внутридоменные и междоменные

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

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

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

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

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

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

По методу определения всего пути пакета алгоритмы делятся на алгоритмы

С интеллектом в главной ВМ или в маршрутизаторе , то есть на алгоритмы одношаговой маршрутизации и маршрутизации от источника.

Синтеллектом в главной ВМ или в маршрутизаторе

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

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

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

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

Общая иерархия алгоритмов маршрутизации

Если рассмотреть наиболее общую иерархию алгоритмов маршрутизации, то

можно определить место каждого уже рассмотренного типа алгоритма

а также помимо рассмотренных алгоритмов можно выделить целый класс алгоритмов, так называемых простых.

Простые алгоритмы маршрутизации

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

Среди алгоритмов простой маршрутизации выделяют:

случайную

лавинную

и по предыдущему опыту

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

Существует конечная вероятность того, что пакет через определённый момент времени достигнет адресата.

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

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

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

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

Недостатки метода – существенное снижение пропускной способности сети.

Методы борьбы

Видеальном случае счетчик транзитных участков должен в начале устанавливаться равным длине пути от отправителя до получателя. Если отправитель не знает расстояние до получателя, он может установить

значение счётчика равным длине максимального пути(диаметру) в данной подсети.

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

Дальнейшим развитием способа простой маршрутизации следует считать

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

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

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

Лекция 12. Протоколы маршрутизации

Определение маршрута передачи данных происходит программно. Соответствующие программные средства носят название протоколов.

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

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

Routing Information Protocol (RIP)

Open Shortest Path First (OSPF)

Integrated Intermediate System to Intermediate System( IS-IS)

Exterior Gateway Protocol (EGP)

Border Gateway Protocol (BGP)

Типы протоколов

Классификация протоколов на основе типа реализуемого алгоритма определения оптимального маршрута:

протоколы вектора расстояний (RIP IP,RIP IPX, AppleTalk RTMP, Cisco IGRP)

протоколы состояния канала(OSPF, IS-IS, Novell NLSP, Cisco EIGRP)

протоколы политики маршрутизации(BGP , EGP)

протоколы на статических алгоритмов (LAT(Local Area Transport),протокол подключения терминала и NetBIOS. Обычно с этими протоколами работают мосты)

Внутренние и внешние протоколы маршрутизации Internet

•В структуре сети Internet изначально выделяют магистральную сеть

(core backbone network) и автономные системы (AS – autonomous systems).

•Шлюзы (маршрутизаторы), используемые для образования сетей и подсетей внутри автономной системы, называют внутренними (interior gateways), а шлюзы, с помощью которых автономные системы подсоединяются к магистрали сети – внешними (exterior gateways).

•Протоколы маршрутизации внутри автономных систем называются протоколами внутренних шлюзов (interior gateway protocol, IGP), а протоколы, определяющие обмен маршрутной информацией между внешними шлюзами и шлюзами магистральной сети – протоколами

внешних шлюзов (exterior gateway protocol, EGP и border gateway protocol, BGP)

Протокол RIP

Этот протокол маршрутизации предназначен для сравнительно небольших и относительно однородных сетей (алгоритм Белмана-Форда). Протокол разработан в университете Калифорнии (Беркли), базируется на разработках фирмы Ксерокс и реализует те же принципы, что и программа маршрутизации routed, используемая в ОC Unix (4BSD). Маршрут здесь характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описания этих маршрутов хранится в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP содержит по записи на каждую обслуживаемую машину (на каждый маршрут). Запись должна включать в себя:

 IP-адрес места назначения.

Метрика маршрута (от 1 до 15; число шагов до места назначения).

IP-адрес ближайшего маршрутизатора (gateway) по пути к месту назначения.

Таймеры маршрута.

Первым двум полям записи мы обязаны появлению термина вектор расстояния (место назначение - направление; метрика - модуль вектора). Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседяммаршрутизаторам, с которыми связан непосредственно. Маршрутизаторполучатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. Протокол RIP должен быть способен обрабатывать три типа ошибок:

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

2.Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (<16).

3.Медленное распространение маршрутной информации по сети создает проблемы при динамичном изменении маршрутной ситуации (система не поспевает за изменениями). Малое предельное значение метрики улучшает сходимость, но не устраняет проблему.

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

Рис. 12.1. Иллюстрация, поясняющее возникновение циклических маршрутов при использовании вектора расстояния.

На верхней части рисунка показана ситуация, когда маршрутизаторы указывают маршрут до сети в соответствии со стрелками. На нижней части связь на участке GW1 <Сеть a> оборвана, а GW2 по-прежнему продолжает оповещать о ее доступности с числом шагов, равным 2. При этом GW1, восприняв эту информацию (если GW2 успел передать свою маршрутную информацию раньше GW1), может перенаправить пакеты, адресованные сети А, на GW2, а в своей маршрутной таблице будет характеризовать путь до

сети А метрикой 3. При этом формируется замкнутая петля маршрутов. Последующая широковещательная передача маршрутных данных GW1 и GW2 не решит эту проблему быстро. Так после очередного обмена путь от gw2 до сети А будет характеризоваться метрикой 5. Этот процесс будет продолжаться до тех пор, пока метрика не станет равной 16, а это займет слишком много циклов обмена маршрутной информацией.

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

Но даже усовершенствование, изложенное выше, не всегда срабатывает. На рис. 4.4.11.1а приведен пример, когда переходной процесс, несмотря на усовершенствование будет идти долго. При обрыве связи В-Г узлы А и Б сообщают узлу В, что они потеряли связь с узлом Г. Узел В делает вывод, что Г не достижим, о чем и сообщает узлам А и Б. К сожалению А знает, что Б имеет проход к Г длиной 2, из чего он делает вывод о достижимости Г за три шага. Аналогично рассуждает Б о возможности достижимости Г через А. Далее при последующих рассылках метрика доступности Г, характеризуется все большими значениями, до тех пор пока не станет равной "бесконечности".

Рис. 12.2. Пример топологии, где переходной процесс осуществляется медленно, даже при усовершенствовании алгоритма.

В RIP сообщения инкапсулируются в udp-дейтограммы, при этом передача осуществляется через порт 520. В качестве метрики RIP использует число шагов до цели. Если между отправителем и приемником расположено три маршрутизатора (gateway), считается, что между ними 4 шага. Такой вид метрики не учитывает различий в пропускной способности или загруженности отдельных сегментов сети. Применение вектора расстояния не может гарантировать оптимальность выбора маршрута, ведь, например, два шага по сегментам сети ethernet обеспечат большую пропускную способность, чем один шаг через последовательный канал на основе интерфейса RS-232.

Маршрут по умолчанию имеет адрес 0.0.0.0 (это верно и для других протоколов маршрутизации). Каждому маршруту ставится в соответствие таймер тайм-аута и "сборщика мусора". Тайм-аут-таймер сбрасывается каждый раз, когда маршрут инициализируется или корректируется. Если со времени последней коррекции прошло 3 минуты или получено сообщение о том, что вектор расстояния равен 16, маршрут считается закрытым. Но запись о нем не стирается, пока не истечет время "уборки мусора" (2мин). При появлении эквивалентного маршрута переключения на него не происходит, таким образом, блокируется возможность осцилляции между двумя или более равноценными маршрутами. Формат сообщения протокола RIP имеет вид, показанный на рис. 4.4.11.2. Поле команда определяет выбор согласно следующей таблице:

Поле версия для RIP равно 1 (для RIP-2 двум). Поле набор протоколов сети i определяет набор протоколов, которые используются в соответствующей сети (для Интернет это поле имеет значение 2). Поле

расстояние до сети i содержит целое число шагов (от 1 до 15) до данной сети. В одном сообщении может присутствовать информация о 25 маршрутах. При реализации RIP можно выделить следующие режимы:

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

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

Получен отклик. Проводится коррекция таблицы маршрутизации (удаление, исправление, добавление).

Рис. 12.3. Формат сообщения RIP.

Регулярные коррекции. Каждые 30 секунд вся или часть таблицы маршрутизации посылается всем соседним маршрутизаторам. Могут посылаться и специальные запросы при локальном изменении таблицы. RIP достаточно простой протокол, но, к сожалению не лишенный недостатков:

a.RIP не работает с адресами субсетей. Если нормальный 16-бит идентификатор ЭВМ класса B не равен 0, RIP не может определить является ли не нулевая часть cубсетевым ID, или полным IP-адресом.

b.RIP требует много времени для восстановления связи после сбоя в маршрутизаторе (минуты). В процессе установления режима возможны циклы.

c.Число шагов важный, но не единственный параметр маршрута, да и 15 шагов не предел для современных сетей.

Когда сообщения об обновлении маршрута приходят на маршрутизатор, он обновляет свою таблицу маршрутизации в соответсвии со следующими правилами:

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

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

Протокол RIP-2 (RFC-1388, 1993 год) является новой версией RIP, которая в дополнение к широковещательному режиму поддерживает мультикастинг; позволяет работать с масками субсетей. На рис. 4.4.11.3 представлен формат сообщения для протокола RIP-2. Поле маршрутный демон является идентификатором резидентной программымаршрутизатора. Поле метка маршрута используется для поддержки внешних протоколов маршрутизации, сюда записываются коды автономных систем. При необходимости управления доступом можно использовать первые 20 байт с кодом набора протоколов сети 0xFFFF и меткой маршрута =2. Тогда в остальные 16 байт можно записать пароль.

Рис. 12.4. Формат сообщений протокола RIP-2

Протокол OSPF (алгоритм Дейкстры)