Учебно-методическии комплекс дисциплины «Компьютерные сети» для специальности 6М011100 — «Информатика» (стр. 42 )

Листинг 9.2. Дистанционно-векторный алгоритм (на каждом узле X)

1 инициализация:

2 для всех смежных узлов v:

3 Dx(*,v) = ∞  /* оператор * означает “для всех рядов” */

4 Dx(v, v) = c(X, v)

5 для всех адресатов, у

6 послать minwD(y, w) каждому соседу /* w по всем соседям узла X */

7

8 цикл

9 ждать (пока не изменится стоимость линии связи с соседом V

10 или пока не будет получено обновление от соседа V)

11

12 если (стоимость c(X, V) изменилась на d)

13 /* изменить стоимость путей ко всем адресатам через соседа v на d */

14 /* величина d может быть положительной или отрицательной */

15 для всех адресатов у: Dx(y, V) = Dx(y, V) + d

16

17 иначе если (получено обновление от V, адресат Y)

18 /* изменился кратчайший путь от V до некоторого Y */

19 /* Узел V послал свое новое значение minw Dv(Y, w) */

20 /* назовем это новое полученное значение “newval” */

21 для одного адресата у: DX(Y, V) = c(X, V) + newval

22

23 если мы получаем новое значение minw Dx(Y, w) для любого адресата Y

24 послать новое значение minw Dx(Y, w) всем соседям

25

26 конец цикла

При обсуждении записей таблицы расстояний узла Е мы рассмотрели сеть, для которой нам были известны стоимости всех линий. Дистанционно-векторный алгоритм, который мы сейчас рассмотрим, является децентрализованным и не пользуется подобной глобальной информацией. В самом деле, единственной информацией, которой обладает узел, являются стоимости линий, связывающих его с ближайшими соседями, а также сведения, получаемые им от этих ближайших соседей. Дистанционно-векторный алгоритм, который мы сейчас рассмотрим, также называют алгоритмом Беллмана-Форда, по именам его изобретателей. Он применяется на практике во многих протоколах маршрутизации, включая протоколы Интернета RIP и BGP, а также ISO IDRP, Novell IPX и оригинальный протокол сети ARPAnet.

Ключевыми являются строки 15 и 21 алгоритма, в которых узел обновляет свои записи в таблице расстояний либо в ответ на изменение стоимости присоединенной к узлу линии, либо в ответ на получение сообщения об обновлении от соседнего узла. Другим ключевым шагом является строка 24, в которой узел посылает обновленные данные своим соседям, если путь наименьшей стоимости до некоторого адресата изменился.

Рисунок 9.7 иллюстрирует работу дистанционно-векторного алгоритма для простой сети из трех узлов, изображенной в верхней части рисунка. Алгоритм функционирует синхронно, то есть все узлы одновременно получают сообщения от своих соседей, .вычисляют новые значения записей таблицы расстояний и информируют своих соседей о любых изменениях в их путях с наименьшей стоимостью. Когда вы изучите этот пример, вам придется поверить, что данный алгоритм столь же корректно работает и в асинхронном режиме, когда производимые узлами вычисления и обмен данными между узлами происходят в произвольные моменты времени. Обведенные кружками записи в таблицах расстояний на рисунке показывают текущие минимальные значения стоимости пути до адресата. Запись, обведенная двойным кружком, означает, что была вычислена новая минимальная стоимость (в строке 4, 15 или 21 дистанционно-векторного алгоритма). Те случаи, когда соседям посылается сообщение об изменении стоимости (строка 24 дистанционно-векторного алгоритма), отмечены на рисунке стрелками. В самом левом столбце на рисунке показаны записи таблиц расстояний для узлов X, Y и Z после первого шага инициализации.

Рассмотрим теперь, как узел X вычисляет таблицу расстояний, показанную в средней колонке, после получения обновлений от узлов Ки Z. Получив обновления от узлов Yn Z, узел X выполняет строку 21 дистанционно-векторного алгоритма:

Рис. 9.7Пример дистанционно-векторного алгоритма

Важно отметить, что узел X узнает о значениях minw Dz( Y, w) и minw DY(Z, w) только потому, что узлы У и Z посылают ему эти значения (их узел X получает в строке 10 дистанционно-векторного алгоритма). В качестве упражнения проверьте таблицы расстояний, вычисленные узлами Уи Zb средней колонке (см. рис. 9.7).

Значение DX(Z, Y) = 3 во второй таблице расстояний узла Xозначает, что наименьшая стоимость пути от узла X до узла Zизменилась с 7 до 3. Таким образом, узел X посылает новое значение стоимости пути до узла Z узлам У и Z, информируя их об этом. Обратите внимание, что узлу Хне нужно посылать обновления узлам Уи Z о стоимости пути к узлу У, так как она не изменилась. Также обратите внимание, что хотя в результате новых расчетов узел У получает новые значения элементов таблицы расстояний, значения минимальных стоимостей путей к узлам X и Z не изменяются. Поэтому узел Уне посылает обновлений узлам X и Z.

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

Дистанционно-векторный алгоритм при изменении стоимостей и неисправностях линий

Когда узел, на котором работает дистанционно-векторный алгоритм, обнаруживает изменение стоимости линии, направляющейся от него к соседу (строка 12), он обновляет свою таблицу расстояний (строка 15) и, если наименьшая стоимость пути изменяется, он извещает об этом своих соседей (строки 23 и 24). Эту ситуацию иллюстрирует рис. 9.8. В данном примере стоимость линии от узла X до узла У изменяется с 4 до 1. Здесь мы рассматриваем только записи таблиц расстояний узлов У и Z, содержащие стоимости путей до узла X.

1. В момент времени t0 узел У замечает изменение стоимости линии (с 4 до 1) и информирует об этом своих соседей, так как благодаря изменению стоимости линии меняются минимальные стоимости путей.

2. В момент времени t1 узел Z получает сообщение от узла У и обновляет свою таблицу. Затем он вычисляет новое значение минимальной стоимости маршрута до узла X (она уменьшилась с 5 до 2) и извещает об этом своих соседей.

3. В момент времени t2 узел У получает сообщение от узла Z и обновляет свою таблицу. Его значения минимальных стоимостей не изменились (хотя стоимость пути до узла X через узел Z изменилась), поэтому узел Уне посылает сообщений своим соседям. Алгоритм переходит в стационарное состояние.

В примере на рис. 4.8 дистанционно-векторному алгоритму требуется только две итерации, чтобы перейти в стационарное состояние. «Хорошие новости» об изменившейся стоимости линии между узлами X и У быстро распространилась по сети.

Рис. 9.8. Изменение стоимости линии: добрые вести распространяются быстро

Рассмотрим теперь, что произойдет в случае увеличения стоимости линии. Предположим, что стоимость линии между узлами X и У возросла с 4 до 60, как показано на рис. 9.9.

1. В момент времени t0 узел У замечает изменение стоимости линии (с 4 до 60). Узел У вычисляет, что новая наименьшая стоимость пути до узла X равна 6. Этот путь проходит через узел Z. Поскольку мы можем видеть всю сеть сразу (глобально), нам понятно, что это новое значение неверно. Но узлу У известно лишь то, что стоимость его прямого соединения с узлом X равна 60 и что узел Z в последний раз сообщил узлу У, что у узла Zесть путь к узлу Xстоимостью 5. Узел У решает, что теперь ему дешевле посылать пакеты узлу X через узел Z. Таким образом, в момент времени t1 у нас образовалась маршрутная петля — узел У направляет пакеты для узла X через узел Z, а узел Z направляет пакеты для узла X через узел У. Маршрутная петля подобна черной дыре — пакет, предназначенный узлу X, будет «отфутболиваться» узлами У и Z друг другу до тех пор, пока таблицы маршрутизации на этих узлах не изменятся.

2. Так как узел У вычислил новый путь наименьшей стоимости до узла X, он информирует об этом узел Z в момент времени t1.

3. Спустя некоторое время узел Z получает пакет с новой наименьшей стоимостью пути от узла У до узла X (узел У сообщил узлу Z, что новое значение наименьшей стоимости пути от узла У до узла X равно 6). Узел Z знает, что он может добраться до узла У по линии стоимости 1, и вычисляет новое значение стоимости маршрута до узла X (все также через узел У), равное 7. Поскольку наименьшая стоимость пути от узла Z до узла X увеличилась, узел Z извещает об этом узел Y в момент времени t2. 4.

Аналогичным образом узел Y обновляет свою таблицу и информирует узел Z о том, что новое значение минимальной стоимости равно 8. Затем узел Z обновляет свою таблицу и информирует узел Y o том, что новое значение минимальной стоимости равно 9, и т. д.

Рис. 9.9. Изменение стоимости линии: дурные вести распространяются медленно и приводят к образованию маршрутных петель.

Как долго будет продолжаться этот процесс? Вы можете убедиться в том, что маршрутная петля будет сохраняться в течение 44 итераций (необходимых узлам 7и 7 для обмена сообщениями) — пока, наконец, узел Z не определит, что стоимость пути до узла X через узел Yбольше 50. В этот момент узел Z (наконец-то!) выяснит, что путь наименьшей стоимости к узлу X пролегает по прямой линии с узлом X. Таким образом, «дурным вестям» об увеличении стоимости линии между узлами Хи Y для распространения по сети потребовалось очень много времени! Что бы произошло, если бы стоимость линии с( Y, X) увеличилась с 4 до 10 000, а стоимость линии c(Z, X) была бы равна 9999? Подобная проблема иногда называется проблемой «счета до бесконечности».

Дистанционно-векторный алгоритм и обратная коррекция

Обсуждавшегося выше сценария со счетом до бесконечности (см. рис. 4.9) можно избежать, если использовать метод, называемый обратной коррекцией, или «отравлением» обратного пути (poisoned reverse). Идея этого метода проста — если узел Z направляет пакеты узлу X через узел У, тогда узел Z объявит узлу Y, что его (узла Z) расстояние до узла X равно бесконечности. Узел Z будет продолжать говорить узлу Y эту «маленькую ложь» до тех пор, пока узел Z направляет пакеты узлу X через узел Y. Поскольку узел Y полагает, что у узла Z нет пути к узлу X, узел Уникогда не станет пытаться посылать пакеты узлу X через узел Z, пока узел Z продолжает посылать пакеты узлу X через узел Y (и лгать о том, что у него нет пути к узлу X).