рис.1 Обмен маршрутной информацией по протоколу RIP
2.1. Построение таблиц маршрутизации
В этом протоколе все сети имеют номера (способ образования номера зависит от используемого в сети протокола сетевого уровня), а все маршрутизаторы - идентификаторы. Протокол RIP широко использует понятие "вектор расстояний". Вектор расстояний представляет собой набор пар чисел, являющихся номерами сетей и расстояниями до них в хопах(количествах пересылок).
Вектора расстояний итерационно распространяются маршрутизаторами по сети, и через несколько шагов каждый маршрутизатор имеет данные о достижимых для него сетях и о расстояниях до них. Если связь с какой-либо сетью обрывается, то маршрутизатор отмечает этот факт тем, что присваивает элементу вектора, соответствующему расстоянию до этой сети, максимально возможное значение, которое имеет специальный смысл - "связи нет". Таким значением в протоколе RIP является число 16.
Каждая запись данных в таблице маршрутизации RIP обеспечивает разнообразную информацию, включая конечный пункт назначения, следующую пересылку на пути к этому пункту назначения и показатель (количество пересылок). Показатель обозначает расстояние до пункта назначения, выраженное числом пересылок до него. В таблице маршрутизации может находиться также и другая информация, в том числе различные таймеры, связанные с данным маршрутом.
RIP поддерживает только самые лучшие маршруты к пункту назначения. Если новая информация обеспечивает лучший маршрут, то эта информация заменяет старую маршрутную информацию. Изменения в топологии сети могут вызывать изменения в маршрутах, приводя к тому, например, что какой-нибудь новый маршрут становится лучшим маршрутом до конкретного пункта назначения. Когда имеют место изменения в топологии сети, то эти изменения отражаются в сообщениях о корректировке маршрутизации. Например, когда какой-нибудь маршрутизатор обнаруживает отказ одного из каналов или другого маршрутизатора, он повторно вычисляет свои маршруты и отправляет сообщения о корректировке маршрутизации. Каждый маршрутизатор, принимающий сообщение об обновлении маршрутизации, в котором содержится изменение, корректирует свои таблицы и распространяет это изменение.
На рисунке (рис.1) приведен пример сети, состоящей из шести маршрутизаторов, имеющих идентификаторы от 1 до 6, и из шести сетей от A до F, образованных прямыми связями типа "точка-точка".
На рисунке (рис.1) приведена начальная информация, содержащаяся в топологической базе маршрутизатора 2, а также информация в этой же базе после двух итераций обмена маршрутными пакетами протокола RIP. После определенного числа итераций маршрутизатор 2 будет знать о расстояниях до всех сетей интерсети, причем у него может быть несколько альтернативных вариантов отправки пакета к сети назначения. Пусть в нашем примере сетью назначения является сеть D.
При необходимости отправить пакет в сеть D маршрутизатор просматривает свою базу данных маршрутов и выбирает порт, имеющий наименьшее расстояния до сети назначения (в данном случае порт, связывающий его с маршрутизатором 3). Для адаптации к изменению состояния связей и оборудования с каждой записью таблицы маршрутизации связан таймер. Если за время тайм-аута не придет новое сообщение, подтверждающее этот маршрут, то он удаляется из маршрутной таблицы.
При использовании протокола RIP работает эвристический алгоритм динамического программирования Беллмана-Форда, и решение, найденное с его помощью является не оптимальным, а близким к оптимальному. Преимуществом протокола RIP является его вычислительная простота, а недостатками - увеличение трафика при периодической рассылке широковещательных пакетов и неоптимальность найденного маршрута.
На рисунке (рис.2) показан случай неустойчивой работы сети по протоколу RIP при изменении конфигурации - отказе линии связи маршрутизатора M1 с сетью 1. При работоспособном состоянии этой связи в таблице маршрутов каждого маршрутизатора есть запись о сети с номером 1 и соответствующим расстоянием до нее.
При обрыве связи с сетью 1 маршрутизатор М1 отмечает, что расстояние до этой сети приняло значение 16. Однако получив через некоторое время от маршрутизатора М2 маршрутное сообщение о том, что от него до сети 1 расстояние составляет 2 пересылки, маршрутизатор М1 наращивает это расстояние на 1 и отмечает, что сеть 1 достижима через маршрутизатор 2. В результате пакет, предназначенный для сети 1, будет циркулировать между маршрутизаторами М1 и М2 до тех пор, пока не истечет время хранения записи о сети 1 в маршрутизаторе 2, и он не передаст эту информацию маршрутизатору М1.
Для того, чтобы избежать образования петель(зацикливания), в алгоритм рассылки векторов расстояний вносятся следующие дополнения.
1.Если дейтаграммы, адресованные в сеть Х, посылаются через маршрутизатор G, находящийся в сети N, то в векторе расстояний, рассылаемом в сети N, расстояние до сети Х не указывается.
2. Если маршрутизатор G объявляет новое расстояние до сети Х, то это расстояние вносится в таблицы маршрутов узлов, отправляющих дейтаграммы в сеть X через G, независимо от того, больше оно или меньше уже внесенного в таблицы расстояния.
Очевидно, что при выполнении вышеуказанных условий зацикливания, рассмотренного в примере, не образуется и строятся корректные маршруты. Однако таким образом устраняются далеко не все случаи зацикливания.
Существует модификация дополнения 1, позволяющая ликвидировать более сложные особые ситуации, в том числе, некоторые случаи счета до бесконечности:
1а. Если дейтаграммы, адресованные в сеть Х, посылаются через маршрутизатор G, находящийся в сети N, то в векторе расстояний, рассылаемом в сети N, расстояние до сети Х полагается равным бесконечности.
Тем не менее и в этом случае особые ситуации все еще остаются.
Рассмотрим следующую систему сетей:
Первоначально сеть А была подсоединена к маршрутизатору2 , но в какой-то момент времени произошла авария и сеть А оказалась изолированной. До момента аварии маршрутизаторы имели следующие записи относительно сети А:
маршрутизатор2: А достижима за 1 переход через маршрутизатор2
маршрутизатор3: А достижима за 2 перехода через маршрутизатор2
маршрутизатор4: А достижима за 2 перехода через маршрутизатор2
Немедленно после аварии запись в таблице маршрутов маршрутизатора 2 изменяется на А достижима за 16 переходов через маршрутизатор2 это говорит о том, что сеть А недостижима, а точнее, что сеть А через маршрутизатор2 недостижима.
Вектор расстояний, рассылаемый из маршрутизатора2 с элементом A=16 достигает маршрутизатора3, но по какой-то причине задерживается на пути в маршрутизатор4.
Маршрутизатор3 вносит в свою таблицу запись А достижима за 16 переходов через маршрутизатор2 и рассылает вектор с элементом А=16. В этот момент маршрутизатор4, до которого сообщение от маршрутизатора2 о недостижимости сети А еще не дошло, рассылает в сети Е свой вектор с элементом А=2. маршрутизатор3 получает этот вектор, прибавляет к расстоянию 1 и замечает, что оно меньше записанного в таблице (бесконечность), следовательно, в таблице маршрутов маршрутизатора3 появляется запись А достижима за 3 перехода через маршрутизатор4. Вектор расстояний с элементом А=3 рассылается маршрутизатором3 в сети С и достигает маршрутизатора2. Маршрутизатор2, руководствуясь теми же соображениями, что и маршрутизатор3 ранее, модифицирует свою таблицу: А достижима за 4 перехода через маршрутизатор3. Примерно в это время маршрутизатор4 получает наконец-то вектор А=16, отправленный после аварии маршрутизатором2, но вслед за этим из маршрутизатора2 приходит вектор А=4, который маршрутизатор2 рассылает в сети D. Поскольку маршрутизатор4 отправляет дейтаграммы в сеть А через маршрутизатор2, он обязан реагировать на любые объявления маршрутизатором2 расстояния до сети А. Поэтому в таблице маршрутизатора4 появляется А достижима за 5 переходов через маршрутизатор2. Соответствующий вектор от маршрутизатора4 с элементом А=5 достигает по сети Е маршрутизатор3, в таблице маршрутов которого указано, что дейтаграммы в сеть А он отправляет через маршрутизатор4. Следовательно, маршрутизатор3 обязан реагировать на любые объявления маршрутизатором4 расстояния до сети А. Поэтому в таблице маршрутизатора3 появляется А достижима за 6 переходов через маршрутизатор4. Вектор от маршрутизатора3 с элементом А=6 достигает по сети С маршрутизатор2, в таблице маршрутов которого указано, что дейтаграммы в сеть А он отправляет через маршрутизатор3. Следовательно, маршрутизатор2 обязан реагировать на любые объявления маршрутизатором3 расстояния до сети А. Поэтому в таблице маршрутизатора2 появляется А достижима за 7 переходов через маршрутизатор3.
Далее все повторяется по кругу до тех пор, пока расстояние до А не станет равным бесконечности в таблицах всех трех маршрутизаторов. Несмотря на это в течение "счета до бесконечности" сеть А считается достижимой, поскольку расстояние до нее считается конечным, и все дейтаграммы, адресованные в сеть А, отправляются маршрутизаторами согласно их таблицам, то есть по кругу, что нельзя признать разумной и корректной маршрутизацией.
Существуют и другие, более сложные случаи нестабильного поведения сетей, использующих протокол RIP, при изменениях в состоянии связей или маршрутизаторов сети.
назад содержание вперед