Протокол RIP является дистанционно-векторным протоколом внутренней маршрутизации. Процесс работы протокола состоит в рассылке, получении и обработке векторов расстояний до IP-сетей, находящихся в области действия протокола, то есть в данной RIP-системе. Результатом работы протокола на конкретном маршрутизаторе является таблица, где для каждой сети данной RIP-системы указано расстояние до этой сети (в хопах) и адрес следующего маршрутизатора. Информация о номере сети и адресе следующего маршрутизатора из этой таблицы вносится в таблицу маршрутов, информация о расстоянии до сети используется при обработке векторов расстояний.
4.1. Алгоритм построения таблицы маршрутов
В этом разделе для простоты будем называть таблицей маршрутов таблицу, являющуюся результатом деятельности протокола RIP, как описано выше, т.е. состоящую из строк с полями "Сеть", "Расстояние", "Следующий маршрутизатор". Записывать строку в таблице маршрутов будем следующим образом:
А=2à ƒ
Это означает, что расстояние от данного маршрутизатора до сети А равно 2, а дейтаграммы, следующие в сеть А, надо пересылать маршрутизатору ƒ.
Вектором расстояний
называется набор пар ("Сеть", "Расстояние до этой сети"), извлеченный из таблицы маршрутов. Каждую такую пару мы назовем элементом вектора расстояний. Мы будем записывать вектор расстояний в виде (А=2,В=1): это означает, что расстояние от данного маршрутизатора до сети А равно 2, до сети В - 1.Расстояние до сети, к которой маршрутизатор подключен непосредственно, примем равным 1.
Каждый маршрутизатор, на котором запущен модуль RIP, периодически широковещательно распространяет свой вектор расстояний. Вектор распространяется через все интерфейсы маршрутизатора, подключенные к сетям, входящим в RIP-систему.
Каждый маршрутизатор также периодически получает векторы расстояний от других маршрутизаторов. Расстояния в этих векторах увеличиваются на 1, после чего сравниваются с данными в таблице маршрутов, и, если расстояние до какой-то из сетей в полученном векторе оказывается меньше расстояния, указанного в таблице, значение из таблицы замещается новым (меньшим) значением, а адрес маршрутизатора, приславшего вектор с этим значением, записывается в поле "Следующий маршрутизатор" в этой строке таблицы. После этого вектор расстояний, рассылаемый данным маршрутизатором, соответственно изменится.
4.1.1. Пример построения таблицы маршрутов
Рассмотрим этот процесс на примере следующей сети.
Рис. 4.1.1. Пример RIP-системы
Здесь
, ‚ , ƒ , „ - маршрутизаторы, A, B, C, D, E - сети. Хосты в сетях не показаны за ненадобностью. Мы будем следить за формированием таблицы маршрутов в узле .В начальный момент времени (например, после подачи питания на маршрутизаторы) таблица маршрутов в узле выглядит следующим образом (т.к. узел знает только о тех сетях, к которым подключен непосредственно):
A=1à
B=1à
Следовательно, узел рассылает в сети А и В вектор расстояний (А=1,В=1).
Аналогично узел ‚ рассылает в сети A, C, D вектор (A=1,C=1,D=1). Узел получает этот вектор из сети А, увеличивает расстояния на 1 (A=2,C=2,D=2) и сравнивает с данными в своей таблице маршрутов. Новое расстояние до сети А оказывается больше, чем уже внесенное в таблицу (А=1), следовательно, новое значение игнорируется. Поскольку сети C и D вовсе не фигурируют в его таблице маршрутов, они туда вносятся. В узле имеем:
A=1à
B=1à
C=2à ‚
D=2à ‚
Узел „ в свою очередь рассылает вектор (D=1,E=1) в сети D и E. Узел ‚ получает этот вектор из сети D, увеличивает расстояния на 1, после чего добавляет себе в таблицу данные о сети Е (Е=2à „ ). Ранее из узла он получил информацию о сети В и добавил себе в таблицу строку В=2à . Узел ‚ рассылает в сети A, C, D свой обновленный вектор расстояний (A=1,B=2,C=1,D=1,E=2).
Узел получает этот вектор от ‚ из сети А, увеличивает расстояния на 1: (A=2,B=3,C=2,D=2,E=3) и замечает, что все указанные расстояния, кроме расстояния до сети Е, больше либо равны значениям, имеющимся в его таблице. Сеть Е в таблице узла отсутствует, следовательно, она туда вносится, и в узле мы получаем:
A=1à
B=1à
C=2à ‚
D=2à ‚
Е=3à ‚
Далее маршрутизатор ƒ , ранее не работавший по каким-либо причинам, рассылает в сети В, С, Е свой вектор (В=1,С=1,Е=1). Узел получает этот вектор из сети В, увеличивает расстояния на 1 и обнаруживает, что расстояние Е=2 меньше имеющегося в таблице Е=3, следовательно запись о сети Е в таблице заменяется на Е=2à ƒ. Остальные элементы полученного от ƒ вектора не вызывают обновления таблицы.
Итоговая таблица маршрутов маршрутизатора :
A=1à
B=1à
C=2à ‚
D=2à ‚
Е=2à ƒ
На этом алгоритм сходится, то есть при неизменной топологии системы никакие векторы расстояний, получаемые маршрутизатором , больше не внесут изменений в таблицу маршрутов. Аналогичным образом алгоритм составления таблицы маршрутов работает и сходится на других маршрутизаторах. Отметим, что несмотря на то, что таблицы маршрутов построены, векторы расстояний продолжают периодически широковещательно рассылаться каждым маршрутизатором. Это требуется для оперативного реагирования на внезапные изменения топологии системы (см. п. 4.1.2).
Очевидно, что вид построенной таблицы маршрутов может зависеть от порядка получения маршрутизатором векторов расстояний. Например, если бы узел получил вектор от узла ƒ раньше, чем от узла ‚ , то дейтаграммы в сеть С посылались бы от через ƒ.
4.1.2. Изменение состояния RIP-системы
Выясним, что происходит в случае, когда состояние системы неожиданно изменяется, например, маршрутизатор отключается от сети А.
Рис. 4.1.2. Изменение состояния RIP-системы
Узел обнаруживает свое отсоединение от сети А и меняет таблицу маршрутов, устанавливая бесконечное расстояние до всех сетей, ранее достижимых через маршрутизаторы, подключенные к сети А (то есть ‚ ). В протоколе RIP значение бесконечности равно 16.
A=16à
B=1à
C=16à ‚
D=16à ‚
Е=2à ƒ
Вектор расстояний, построенный на основании этой таблицы, рассылается в сеть В, чтобы маршрутизаторы, направлявшие свои данные через в ставшие недоступными сети, если таковые маршрутизаторы существуют, соответственно изменили свои маршрутные таблицы.
Допустим, в узле ƒ имелась следующая таблица маршрутов:
A=2à ‚
B=1à ƒ
C=1à ƒ
D=2à „
Е=1à ƒ
Узел ƒ периодически и широковещательно рассылает в сети В, С, Е свой вектор расстояний (А=2,В=1,С=1,D=2,E=1). Узел получает этот вектор, увеличивает расстояния на 1: (А=3,В=2,С=2,D=3,E=2) и замечает, что расстояния А=3, С=2 и D=3 меньше бесконечности следовательно, соответствующие записи таблицы маршрутов модифицируются и она принимает вид:
A=3à ƒ
B=1à
C=2à ƒ
D=3à ƒ
Е=2à ƒ
Таким образом, узел построил маршруты в обход поврежденного участка и восстановил достижимость всех сетей.
4.2. Особые случаи
4.2.1. Зацикливание
К сожалению, поведение дистанционно-векторных протоколов (и в частности, протокола RIP) при изменении топологии системы не всегда корректно и предсказуемо.
Рассмотрим вышеописанную ситуацию с отсоединением узла от сети А.
Рис. 4.2.1. Изменение состояния RIP-системы
Мы предполагали, что узел ƒ не отправлял дейтаграмм через узел (и, следовательно, изменение таблицы маршрутов в узле не повлияло на таблицу узла ƒ ). Предположим теперь, что ƒ отправлял дейтаграммы в сеть А через , то есть таблица в узле ƒ имела вид:
A=2à
B=1à ƒ
C=1à ƒ
D=2à „
Е=1à ƒ
После отсоединения от сети А узел ƒ получает от вектор (A=16,B=1,C=16,D=16,E=2). Проанализировав этот вектор, ƒ делает вывод, что все указанные в нем расстояния больше значений, содержащихся в его маршрутной таблице, на основании чего этот вектор узлом ƒ игнорируется.
В свою очередь узел ƒ рассылает в сети В, С, Е вектор (A=2,B=1,C=1,D=2,E=1). Узел получает этот вектор, увеличивает расстояния на 1: (А=3,В=2,С=2,D=3,E=2) и замечает, что расстояния А=3, С=2 и D=3 меньше бесконечности, следовательно, соответствующие записи таблицы маршрутов в узле модифицируются и она принимает вид:
A=3à ƒ
B=1à
C=2à ƒ
D=3à ƒ
Е=2à ƒ
Очевидно, после этого содержимое таблиц узлов и ƒ стабилизируется.
Рассмотрим теперь записи о достижении сети А в таблицах маршрутизаторов и ƒ .
В узле : A=3à ƒ
В узле ƒ : A=2à
Таким образом, возникло зацикливание: данные, адресованные в сеть А, будут пересылаться между узлами и ƒ до тех пор, пока не истечет время жизни дейтаграмм и они не будут уничтожены.
Для того, чтобы избежать зацикливания, в алгоритм рассылки векторов расстояний вносятся следующие дополнения.
1. Если дейтаграммы, адресованные в сеть Х, посылаются через маршрутизатор G, находящийся в сети N, то в векторе расстояний, рассылаемом в сети N, расстояние до сети Х не указывается.
В нашем примере узел ƒ будет рассылать в сети В вектор (B=1,C=1,D=2,E=1). Элемент А=2 не будет включен в этот вектор, потому что дейтаграммы в сеть А отправляются узлом ƒ через узел , а узел находится в сети В. При рассылке узлом ƒ вектора расстояний в другие сети элемент A=1 будет указан (но не будут указаны какие-то другие элементы).
2. Если маршрутизатор G объявляет новое расстояние до сети Х, то это расстояние вносится в таблицы маршрутов узлов, отправляющих дейтаграммы в сеть X через G, независимо от того, больше оно или меньше уже внесенного в таблицы расстояния.
В нашем примере это означает, что если в маршрутной таблице узла ƒ записано А=1à и ƒ получает от вектор с элементом А=16, то несмотря на то, что 1 меньше бесконечности, узел ƒ модифицирует запись в таблице: А=16à .
Очевидно, что при выполнении вышеуказанных условий зацикливания, рассмотренного в примере, не образуется и строятся корректные маршруты. Однако таким образом устраняются далеко не все случаи зацикливания.
Существует модификация дополнения 1, позволяющая ликвидировать более сложные особые ситуации, в том числе, некоторые случаи счета до бесконечности (см. также следующий пункт):
1А. Если дейтаграммы, адресованные в сеть Х, посылаются через маршрутизатор G, находящийся в сети N, то в векторе расстояний, рассылаемом в сети N, расстояние до сети Х полагается равным бесконечности.
Тем не менее и в этом случае особые ситуации все еще остаются.
4.2.2. Счет до бесконечности
Рассмотрим следующую систему сетей:
Рис. 4.2.2. Пример RIP-системы (иллюстрация счета до бесконечности)
Первоначально сеть А была подсоединена к узлу ‚ , но в какой-то момент времени произошла авария и сеть А оказалась изолированной.
До момента аварии маршрутизаторы имели следующие записи относительно сети А:
Узел ‚ А=1à ‚
Узел ƒ А=2à ‚
Узел „ А=2à ‚
Немедленно после аварии запись в таблице маршрутов узла А изменяется на А=16à ‚ , это говорит о том, что сеть А недостижима, а точнее, что сеть А через узел ‚ недостижима.
Вектор расстояний, рассылаемый из ‚ , с элементом A=16 достигает узла ƒ , но по какой-то причине задерживается на пути в „ . Согласно дополнениям к алгоритму рассылки векторов расстояний, приведенным в предыдущем пункте, узел ƒ вносит в свою таблицу запись А=16à ‚ и рассылает вектор с элементом А=16.
В этот момент узел „ , до которого сообщение от узла ‚ о недостижимости сети А еще не дошло, рассылает в сети Е свой вектор с элементом А=2. Узел ƒ получает этот вектор, прибавляет к расстоянию 1 и замечает, что оно меньше записанного в таблице (бесконечность), следовательно, в таблице маршрутов узла ƒ появляется запись А=3à „ . Вектор расстояний с элементом А=3 рассылается узлом ƒ в сети С и достигает узла ‚ .
Узел ‚ , руководствуясь теми же соображениями, что и узел ƒ ранее, модифицирует свою таблицу: А=4à ƒ .
Примерно в это время узел „ получает наконец-то вектор А=16, отправленный после аварии узлом ‚ , но вслед за этим из узла ‚ приходит вектор А=4, который узел ‚ рассылает в сети D. Поскольку „ отправляет дейтаграммы в сеть А через ‚ , он обязан реагировать на любые объявления узлом ‚ расстояния до сети А. Поэтому в таблице узла „ появляется А=5à ‚ .
Соответствующий вектор от узла „ с элементом А=5 достигает по сети Е узел ƒ , в таблице маршрутов которого указано, что дейтаграммы в сеть А он отправляет через „ . Следовательно, узел ƒ обязан реагировать на любые объявления узлом „ расстояния до сети А. Поэтому в таблице узла ƒ появляется А=6à „ .
Вектор от узла ƒ с элементом А=6 достигает по сети С узел ‚ , в таблице маршрутов которого указано, что дейтаграммы в сеть А он отправляет через ƒ . Следовательно, узел ‚ обязан реагировать на любые объявления узлом ƒ расстояния до сети А. Поэтому в таблице узла ‚ появляется А=7à ƒ .
Далее все повторяется по кругу до тех пор, пока расстояние до А не станет равным бесконечности в таблицах всех трех маршрутизаторов. Несмотря на это в течение "счета до бесконечности" сеть А считается достижимой, поскольку расстояние до нее считается конечным, и все дейтаграммы, адресованные в сеть А, отправляются маршрутизаторами согласно их таблицам, то есть по кругу, что нельзя признать разумной и корректной маршрутизацией.
Существуют и более сложные ситуации, когда возникает необходимость "счета до бесконечности". Чтобы уменьшить отрицательный эффект этого явления, значение бесконечности не должно быть велико. В протоколе RIP оно равно 16, что в свою очередь ограничивает размер RIP-системы.
4.3. Реализация протокола RIP
Существуют две версии протокола RIP: RIP-1 и RIP-2. Версия 2 имеет некоторые усовершенствования, как то: возможность маршрутизации сетей по модели CIDR (кроме адреса сети передается и маска), поддержка мультикастинга, возможность использования аутентификации RIP-сообщений и др.
4.3.1. Типы и формат сообщений
В протоколе RIP имеются два типа сообщений, которыми обмениваются маршрутизаторы:
- ответ (response) - рассылка вектора расстояний;
- запрос (request) - маршрутизатор (например, после своей загрузки) запрашивает у соседей их маршрутные таблицы или данные об определенном маршруте.
Обмен сообщениями происходит по порту 520 UDP.
Формат сообщений обоих типов одинаков:
Поля, помеченные знаком *, относятся к версии 2; в сообщениях RIP-1 эти поля должны быть обнулены.
Сообщение RIP состоит из 32-битного слова, определяющего тип сообщения и версию протокола (плюс "Routing Domain" в версии 2), за которым следует набор из одного и более элементов вектора расстояний. Каждый элемент вектора расстояний занимает 5 слов (20 октетов) (от начала поля "Address Family Identifier" до конца поля "Metric" включительно). Максимальное число элементов вектора - 25, если вектор длиннее, он может разбиваться на несколько сообщений.
Поле "Command" определяет тип сообщения: 1 - request, 2 - response; поле "Version" - версию протокола (1 или 2).
Поле "Address Family Identifier" содержит значение 2, которое обозначает семейство адресов IP; другие значения не определены. Поля "IP address" и "Metric" содержат адрес сети и расстояние до нее.
Дополнительно к полям версии 1 во второй версии определены следующие.
"Routing Domain" - идентификатор RIP-системы, к которой принадлежит данное сообщение; часто - номер автономной системы. Используется, когда к одному физическому каналу подключены маршрутизаторы из нескольких автономных систем, в каждой автономной системе поддерживается своя таблица маршрутов. Поскольку сообщения RIP рассылаются всем маршрутизаторам, подключенным к сети, требуется различать сообщения, относящиеся к "своей" и "чужой" автономным системам.
"Route Tag" - используется как метка для внешних маршрутов при работе с протоколами внешней маршрутизации.
"Subnet Mask" - маска сети, адрес которой содержится в поле IP address. RIP-1 работает только с классовой моделью адресов.
"Next Hop" - адрес следующего маршрутизатора для данного маршрута, если он отличается от адреса маршрутизатора, пославшего данное сообщение. Это поле используется, когда к одному физическому каналу подключены маршрутизаторы из нескольких автономных систем и, следовательно, некоторые маршрутизаторы "чужой" автономной системы физически могут быть достигнуты напрямую, минуя пограничный (логически подключенный к обеим автономным системам) маршрутизатор. Об этом пограничный маршрутизатор и объявляет в поле "Next Hop".
Адрес 0.0.0.0 в сообщении типа "ответ" обозначает маршрут, ведущий за пределы RIP-системы. В сообщении типа "запрос" этот адрес означает запрос информации о всех маршрутах (полного вектора расстояний). Указание в сообщении типа "запрос" адреса конкретной сети означает запрос элемента вектора расстояний только для этой сети - такой режим используется обычно только в отладочных целях.
Аутентификация может производиться протоколом RIP-2 для обработки только тех сообщений, которые содержат правильный аутентификационный код. При работе в таком режиме первый 20-октетный элемент вектора расстояний, следующий непосредственно за первым 32-битным словом RIP-сообщения, является сегментом аутентификации. Он определяется по значению поля "Address Family Identifier", равному в этом случае 0xFFFF. Следующие 2 октета этого элемента определяют тип аутентификации, а остальные 16 октетов содержат аутентификационный код. Таким образом, в RIP-сообщении с аутентификацией может передаваться не 25, а только 24 элемента вектора расстояний, которые следуют за сегментом аутентификации. К настоящему моменту надежного алгоритма аутентификации для протокола RIP не разработано; стандартом определена только аутентификация с помощью обычного пароля (значение поля "Тип" равно 2).
4.3.2. Работа протокола RIP
Для каждой записи в таблице маршрутов существует время жизни, контролируемое таймером. Если для любой конкретной сети, внесенной в таблицу маршрутов, в течение 180 с не получен вектор расстояний, подтверждающий или устанавливающий новое расстояние до данной сети, то сеть будет отмечена как недостижимая (расстояние равно бесконечности). Через определенное время модуль RIP производит "сборку мусора" - удаляет из таблицы маршрутов все сети, расстояние до которых бесконечно.
При получении сообщения типа "ответ" для каждого содержащегося в нем элемента вектора расстояний модуль RIP выполняет следующие действия:
- проверяет корректность адреса сети и маски, указанных в сообщении;
- проверяет, не превышает ли метрика (расстояние до сети) бесконечности;
- некорректный элемент игнорируется;
- если метрика меньше бесконечности, она увеличивается на 1;
- производится поиск сети, указанной в рассматриваемом элементе вектора расстояний, в таблице маршрутов;
- если запись о такой сети в таблице маршрутов отсутствует и метрика в полученном элементе вектора меньше бесконечности, сеть вносится в таблицу маршрутов с указанной метрикой; в поле "Следующий маршрутизатор" заносится адрес маршрутизатора, приславшего сообщение; запускается таймер для этой записи в таблице;
- если искомая запись присутствует в таблице с метрикой больше, чем объявленная в полученном векторе, в таблицу вносятся новые метрика и, соответственно, адрес следующего маршрутизатора; таймер для этой записи перезапускается;
- если искомая запись присутствует в таблице и отправителем полученного вектора был маршрутизатор, указанный в поле "Следующий маршрутизатор" этой записи, то таймер для этой записи перезапускается; более того, если при этом метрика в таблице отличается от метрики в полученном векторе расстояний, в таблицу вносится значение метрики из полученного вектора;
- во всех прочих случаях рассматриваемый элемент вектора расстояний игнорируется.
Сообщения типа "ответ" рассылаются модулем RIP каждые 30 с по широковещательному или мультикастинговому (только RIP-2) адресу; рассылка "ответа" может происходить также вне графика, если маршрутная таблица была изменена (triggered response). Стандарт требует, чтобы triggered response рассылался не немедленно после изменения таблицы маршрутов, а через случайный интервал длительностью от 1 до 5 с. Эта мера позволяет несколько снизить нагрузку на сеть.
В каждую из сетей, подключенных к маршрутизатору, рассылается свой собственный вектор расстояний, построенный с учетом дополнения 1 (1А), сформулированного выше в п. 4.2.1. Там, где это возможно, адреса сетей агрегируются (обобщаются), то есть несколько подсетей с соседними адресами объединяются под одним, более общим адресом с соответствующим изменением маски.
В случае triggered response посылается информация только о тех сетях, записи о которых были изменены.
Информация о сетях с бесконечной метрикой посылается только в том случае, если она была недавно изменена.
При получении сообщения типа "запрос" с адресом 0.0.0.0 маршрутизатор рассылает в соответствующую сеть обычное сообщение типа ответ. При получении запроса с любым другим значением в поле (полях) "IP Address" посылается ответ, содержащий информацию только о сетях, которые указаны. Такой ответ посылается на адрес запросившего маршрутизатора (не широковещательно), при этом дополнение 1(1А) из п. 4.2.1 не учитывается.
4.3.3. Конфигурирование RIP
Общий порядок действий при конфигурировании модуля RIP следующий:
указать, какие сети, подключенные к маршрутизатору, будут включены в RIP-систему;
указать "nonbroadcast networks", т.е. сети со статической маршрутизацией (например, тупиковые сети, подсоединенные к внешнему миру через единственный шлюз), куда не нужно рассылать векторы расстояний;
указать "permanent routes" - статические маршруты, например, маршрут по умолчанию за пределы автономной системы.
4.3.4. Обсуждение
Протокол RIP очень прост и до сих пор продолжает использоваться в системах с простой топологией, но обладает недостатками, которые не позволяют применять его в обширных и сложных системах.
Во-первых, малое значение бесконечности (из-за эффекта "счет до бесконечности") ограничивает размер RIP-системы четырнадцатью промежуточными маршрутизаторами в любом направлении. Кроме того, по той же причине весьма затруднительно использование сложных метрик, учитывающих не просто количество промежуточных маршрутизаторов, но и скорость и качество канала связи (чем хуже (медленнее) канал, тем больше метрика).
Во-вторых, само явление счета до бесконечности вызывает сбои в маршрутизации.
В-третьих, широковещательная рассылка векторов расстояний каждые 30 секунд ухудшает пропускную способность сети.
В-четвертых, время схождения алгоритма при создании маршрутных таблиц достаточно велико (по крайней мере, по сравнению с протоколами состояния связей).
В-пятых, несмотря на то, что каждый маршрутизатор начинает периодическую рассылку своих векторов, вообще говоря, в случайный момент времени (например, после включения), через некоторое время в системе наблюдается эффект синхронизации маршрутизаторов, сходный с эффектом синхронизации аплодисментов. Все маршрутизаторы рассылают свои вектора в один и тот же момент времени, что приводит к большим пикам трафика и отказам в маршрутизации дейтаграмм во время обработки большого количества одновременно полученных векторов.
Протокол RIP описан в RFC-1058 (версия 1) и RFC-1388 (версия 2).