В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 110
Текст из файла (страница 110)
В этом случае задержка~ в линиях ко всем трем соседям одинаковая, так как со всеми тремя соседними маршрутизаторами маршрутизатор Х связывается через сеть 1. Результат по- казан на рис. 15.5, в. Следу акций маршрутизатор Сеть-получатель Г1(Х, й Метрика ЦХ, 1) В С д рис. 15.5. Дистанционно-векторный алгоритм, примененный к сети нв рис. 15.1 Распределенный алгоритм Беллмана — Форда В только что показанном примере алгоритм, вроде бы, работает. Чтобы понять, почему, сравните формулу (15.1) с шагом обновления алгоритма Беллмана — Фор- да, обсуждавгпегося в главе 14.
По существу, зта формула точно такая же. Исполь- зуемый в протоколе К1Р алгоритм маргпрутиэации представляет собой распреде- ленную версию алгоритма Беллмана — Форда, который был первым алгоритмом маршрутизапии в сети с коммутацией пакетов АКРАй(ЕТ. Возможно, прояснить природу алгоритма Беллмана — Форда поможет его син- хронная версия.
Предположим, что каждый маршрутизатор начинает свою работу со следующей операции присваивания: [ш(х, )), если узел х напрямую соединен с сетью, х,л= (15.2) в противном случае. Затем все маршрутизаторы одновременно обмениваются своими векторами Расстояний и рассчитывают время задержки с помощью формулы (15.1). Когда Расчеты закончены, все марн~рутизаторы снова одновременно обмениваются своими векторами расстояний и применяют формулу (15.1). Каждая итерация эквивалентна одной итерации алгоритма Беллмана — Форда (увеличение параметра я на единицу), выполняемой параллельно на каждом узле графа.
Рассмотрим отдельный узел з. После первой итерации узел з получает сведения обо всех кратчайших 482 Глава 15. Протоколы внутренней маршрутизации 15.2. Протокол й! и 483 пугях длиной максимум в один ретрансляционный участок. После второй итера ции узел э получает сведения обо всех кратчайших путях длиной максимум в д ретрансляционных участка и т. д., пока он не обнаружит все кратчайшие пути, Было бы сложно координировать работу всех маршрутизаторов, так чтобы алг ритм выполнялся синхронно.
Вместо этого в протоколе К1Р и во всех остальнь,„ основанных на дистанционно-векторной маршрутизации протоколах примепяетс асинхронный метод. При запуске узел инициализируется в соответствии с форм лой (15.2). Получая новые дистанционные вектора от всех своих соседей, узел об повляет свои сведения при помощи формулы (15.1). Через каждые 30 секунд по собственному таймеру каждый маршрутизатор передаст свой вектор расстояний своим соседям. Можно доказать работоспособность данного метода, то есть что он обеспечивает все узлы правильными результатами. Если изменится стоимость одной или нескольких линий в конфигурации, тогда узел сможет рассчитать новые кратчайшие маршругы за конечное время, пропорциональное количеству маршрутизаторов. Доказательство работоспособности алгоритма длинное, его можно найти в 128] Детали алгоритма й1 Р В предыдущем общем описании алгоритма дистанционно-векторной маршрутизации игнорируются некоторые практические детали его работы, распределенной между несколькими сотрудничающими друг с другом узлами.
В данном подразделе мы рассмотрим эти детали. Инкрементное обновление При использовании формулы (15.1) предполшзется, что узел за короткий интервал времени получает обновленные вектора расстояний от всех своих соседей, а затем на основании полученной информации производит полный перерасчет своих векторов. Это требование является непрактичным по нескольким причинам. Поскольку алгоритм работает асинхронно, нет гарантии, что все обновления будут получены в течение любого заданного интервала времени.
Более того, пакеты протокола К1Р посылаются при помощи протокола ППР, представляющего собой ненадежный транспортный протокол, так что некоторые К1Р-пакеты могут не дойти до получателя. Поэтому протокол К(Р работает инкрементно, обновляя свою таблицу маршрутизации после получения любого вектора расстояний. При этом применяются следующие правила: + Если полученный вектор расстояний содержит информацию о новой сети, эти сведения добавляются к таблице маршрутизации.
+ Если узел получает данные о маршруте с меньпшм значением времени задержки, информация о текущем маршруте заменяется новыми сведениями Например, предположим, что у нас есть конфигурация, представленная па рис. 15.1, и таблица маршрутизации для хоста Х, показанная на рис. 15.5, а. Теперь допустим, что хост Х получает только одно обновление, а именно от хоста В, показанное на рис.
15.5, б. В этом случае единственное изменение таблицы маршрутизации хоста Х заюпочается в том, что ЦХ, 5) = 5 а Л(Х, 5) = В. Если впоследствии прибывает вектор расстояний от хоста А г также показанный на рис. 15.5, 6, тогда таблица маршрутизации хоста Х обновляется до состояния, показанного на рис. 15.5, э.
+ Если узел получает обновленный вектор от маршрутизатора К и у этого узла есть одна или несколько записей в таблице маршрутизации, в которых маршрутизатор К представляет следующий ретрансляционный участок, тогда все эти записи обновляются, чтобы отразить новые данные от маршрутизатора К. Чтобы понять, зачем нужно третье правило, предположим, что на рис.
15,5, в показано текущее состояние таблицы маршрутизации хоста Х, соответствующее конфигурации на рис. 15.1, с той разнице1п что стоимости всех линий, исходящих от маршрутизаторов Е и Р, равны 1. Предположим теперь, что маршрутизатор Р выходит из строя и это обнаруживает маршрутизатор А, Вскоре после этого маршрутизатор А посылает маршрутизатору Х вектор расстояний, в котором сообщается о новом расстоянии до сети 5, равном 3. В данном случае хост Х должен увеличить значение ЦХ, 5) с 3 до 4. Изменениятопологии В предыдущем абзаце мы предположили, что маршрутизатор А узнал о том, что маршрутизатор Р вьппел из строя.
Как это возможно? Механизм, используемый в протоколе К1Р, следующий. Предполагается, что каждые 30 секунд каждый маршрутизатор посылает обновленный вектор своим соседям. Пусть в таблипе маршрутизации узла К есть запись для сети 1, в которую он отправляет пакеты через маршрутизатор )ч'. В этом случае, если маршрутизатор К в течение 180 секунд ие получает обновленного вектора от маршрутизатора )ч, он помечает этот маршрут как недействительный. Можно предположить, что либо маршрутизатор Н вышел из строя, либо сеть, соединяющая узлы К и Н, стала нестабильной. Когда маршрутизатор К узнает от любого своего соседа, что у него есть действительный маршрут к сети 0 он заменяет недействительную запись о маршруте действительной. Маршрут помечается как недействительный установкой расстояния для этого маршрута, равного бесконечности.
На практике по причинам, которые будут объяснены ниже, в протоколе К1Р бесконечность обозначается числом 16. Проблема счета до бесконечности Одним из наиболее серьезных недостатков протокола К)Р является его медленная реакция на изменение топологии. Рассмотрим конфигурацию на рис. 15.6, в которой стоимости всех линий равны 1. Расстояние от маршрутизатора В до сети 5 равно 2, при этом маршрут от маршрутизатора В до сети 5 проходит через маршрутизатор П.
В то же время расстояние от маршрутизато1юв А и С до сети 5 равно 3, а маршруты проходят через маршрутизатор В. Теперь предположим, что маршрутизатор г) выходит из строя. Далее события могут развиваться по следующему сценарию: 1. Маршрутизатор В через маршрутизатор П обнаруживает, что сеть 5 стала недоступной, и устанавливает расстояние до нее равным 4, основываясь на сведениях, полученных от маршрутизаторов А или С.
Это происходит, потому что маршрутизатор В недавно получил от маршрутизаторов А и С сооб- 15.2. Протокол й!Р 488 Формат Й!Р-пакета Ф и и к о Рис. 15.6. Проблема счеталсбескснечнссти им **6 й и о а 8$ с. ч т о а Рис. 16.7. Формат й! Р-лакета 484 Глава 15. Протоколы внутренней маршрутизации щение о доступности маршрутизатора?), в котором указывалось, что расс„ якие до сети 5 равно 3.
Когда подходит срок, маршрутизатор В передает информацию в виде векторов расстояний маршрутизаторам А н С 2. Маршрутизаторы А и С получают информацию об увеличении расстош, ояния до маршрутизатора ?) н корректируют свои данные о расстоянии до сет, 5 УвеличиваЯ его до 5 (4 от маРшРУтизатоРа В до маРшРУтизатоРа ?) плюс 1 от маршрутизаторов А и С до маршрутизатора В). 3, Маршрутизатор В получает от маршрутизаторов А и С сообщение о том, что расстояние до сети 5 равно 5, в связи с чем заключает, что теперь расстоя ние до этой сети равно б, Маршрутизаторы продолжают обмениваться подобными сообщениями до тех пор, пока значение расстояния не достигнет бесконечности, для обозначения которой в протоколе К?Р используется число 18. При ЗО-секундных интервалах между сообщениями этот процесс займет от 8 до 18 минут.
Раздвоенный горизонт и негодный встречный маршрут Проблема счета до бесконечности вызвана взаимным непониманием между маршрутизаторами В и А (и между маршрутизаторами В и С). Каждый полагает, что он может достичь сети 5 через другого. Правило раздвоенного горизонгла (зр?1ь 11опгоп) применяемое в алгоритме ИР, утверждает, что нет смысла посылать информапию о маршруте в тоы направлении, откуда она пришла, так как маршрутизатор, посылающий вам информацию, находится ближе к получателю, чем вы. Это правило ускоряет процесс обнаружения разрыва сети. Данные о недействительном пути будут удалены из таблиц маршрутизации по истечении 180-секундного интервала ожидания. За счет незначительного увеличения размера сообщений, которыми обмениваются маршрутизаторы, протокол В?Р позволяет еще быстрее решить данную про- ~ блему, используя правило негодного встречного маршрута (роЬопед гечеше).
Это правило отличается от простого правила раздвоенного горизонта отправкой соседям обновлений с равным 1б счетчиком ретрансляционных участков для маршрутов, выясненных этими соседями. Если у двух маршрутизаторов есть маршруты, указывающие друг на друга. объявление о встречных маршрутах с расстоянием 1б немедленно прерывает цикл. На рис, 15,7 показан формат пакета протокола К?Р. Каждый пакет содержит заголовок с двумя полями. + Команда. 1 означает запрос, 2 — ответ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
