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

Рассмотрим подробно несколько первых шагов.

1. На шаге инициализации текущие наименьшие стоимости для путей от узла А до напрямую соединенных с ним соседних узлов В, С и D равны 2, 5 и 1 соответственно. Обратите, в частности, внимание, что стоимость пути до узла С установлена равной 5 (хотя вскоре мы увидим, что существует путь с меньшей стоимостью), так как этой величине равна стоимость прямой (один ретрансляционный участок) линии от узла А до узла С. Стоимости путей до узлов Ей Fустанавливаются равными бесконечности, так как эти узлы не связаны напрямую с узлом А.

2. На первой итерации из узлов, не входящих в множество N, мы выбираем узел с наименьшим по стоимости путем от узла А. Это узел D со стоимостью пути 1. Таким образом, узел D добавляется к множеству N. Затем выполняется строка 12 алгоритма, чтобы вычислить новое значение D(v) для всех узлов v и получить результаты, показанные во второй строке (шаг 1) табл. 4.2. Стоимость пути к узлу В не изменилась. Стоимость пути к узлу С (которая вначале была равна 5) через узел D оказалась равной 4. Таким образом, выбирается этот путь, имеющий наименьшую стоимость, а для узла С указывается, что путь с наименьшей стоимостью к нему проходит через узел D. Аналогично вычисляется стоимость пути до узла Е (через узел D), равная 2, что отражается в таблице.

3. На второй итерации следующими узлами с путями минимальной стоимости (равной 2) оказываются узлы В и Е. Мы произвольным образом выбираем из двух равноудаленных узлов один (узел Е) и добавляем его в набор N Теперь множество содержит узлы A, DhE. Стоимости путей до остальных узлов, еще не вошедших в множество N, то есть узлов В, Си F, вычисляются заново в строке 12 алгоритма. Результаты этих вычислений показаны в строке 3 табл. 9.2.

4. И т. д.

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

Какова вычислительная сложность этого алгоритма? То есть сколько потребуется произвести вычислений в худшем случае, чтобы найти пути с наименьшей стоимостью от источника до всех п адресатов? На первой итерации мы должны просмотреть все п узлов, чтобы найти узел w, не принадлежащий множеству N, стоимость пути до которого минимальна. На второй итерации мы должны просмотреть n — 1 узлов, чтобы найти узел с путем наименьшей стоимости. На третьей итерации нам придется просмотреть n – 2 узлов, и т. д. Всего нам придется просмотреть n(n + 1)/2 узлов. Таким образом, количество вычислений в алгоритме, основанном на состоянии линий, растет пропорционально квадрату узлов сети: 0(n2). Существует и более сложный вариант этого алгоритма, в котором используется структура данных, называемая «кучей» (heap). Данному алгоритму для нахождения минимума в строке 9 требуется время, пропорциональное логарифму от числа рассматриваемых узлов, что снижает суммарное время выполнения алгоритма.

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

Когда в очередной раз запускается LS-алгоритм, узел С определяет (на основании стоимостей линий, показанных на рис. 9.5, а), что путь к узлу А по часовой стрелке обладает стоимостью 1, тогда как стоимость пути к этому же узлу против часовой стрелки (которым он пользовался до сих пор) равна 1 + е. Таким образом, путь наименьшей стоимости от узла С к узлу А теперь имеет направление по часовой стрелке. Аналогично, узел В определяет, что его новый путь к узлу А с наименьшей стоимостью также направлен по часовой стрелке, в результате чего вычисляются новые стоимости путей, показанные на рис. 9.5, б. При следующем запуске LS-алгоритма узлы В, С и D обнаруживают путь нулевой стоимости к узлу А в направлении против часовой стрелки, поэтому все узлы направляют свой трафик против часовой стрелки. В следующий раз эти же узлы обнаруживают, что дешевле направлять трафик по часовой стрелке, так как в этом направлении никакого трафика нет.

Что можно предпринять, чтобы предотвратить подобный колебательный процесс? Осцилляция может возникнуть в любом алгоритме (не только в LS-алгоритме), использующем уровень загруженности линий или задержку в линиях в качестве параметра определения стоимости линий. Один из методов решения данной проблемы заключается в том, чтобы стоимость линий не зависела от текущего объема трафика, проходящего по ним. Однако такое решение является неприемлемым, так как наша цель состоит в том, чтобы алгоритм мог пускать потоки данных в обход сильно загруженных линий (например, с высокой задержкой). Другое возможное решение могло бы гарантировать, что не все маршрутизаторы запустят LS-алгоритм в одно и то же время. Это решение кажется более разумным, так как есть надежда, что даже если маршрутизаторы запускают LS-алгоритм с одной и той же периодичностью, исполняемые экземпляры алгоритма не будут одинаковыми на каждом узле. Исследователи недавно отметили, что маршрутизаторы Интернета могут самосинхронизироваться. То есть даже если изначально они выполняют один и тот же алгоритм с одним и тем же периодом, но с разной фазой, со временем алгоритмы на разных узлах синхронизируются и остаются синхронными. Один из способов избежать синхронизации состоит в том, чтобы намеренно сделать случайными интервалы времени между запусками алгоритма на каждом узле.

Итак, мы обсудили алгоритм маршрутизации, основанный на состоянии линий. Рассмотрим теперь другой важный алгоритм маршрутизации, применяемый сегодня на практике, — алгоритм дистанционно-векторной маршрутизации.

6. Алгоритм дистанционно-векторной маршрутизации

В отличие от алгоритма, основанного на состоянии линий и использующего глобальную информацию, дистанционно-векторный (Distance Vector, DV) алгоритм является распределенным, итерационным и асинхронным. Он является распределенным, так как каждый узел получает порцию информации от одного или нескольких напрямую соединенных с ним соседей, выполняет вычисления, а затем может разослать результаты своих вычислений своим соседям. Он является итерационным, так как этот процесс продолжается до тех пор, пока соседние узлы не перестанут обмениваться информацией. (Интересно отметить, что, как мы увидим, этот алгоритм сам завершает свою работу — он не получает «сигнала», требующего остановить работу; он просто останавливается.) Алгоритм является асинхронным, так как он не требует, чтобы все узлы работали в жесткой взаимосвязи друг с другом.

Главной структурой данных в дистанционно-векторном алгоритме является таблица расстояний, содержащаяся на каждом узле. В каждой таблице расстояний есть по строке для каждого адресата в сети и по столбцу для каждого ближайшего соседа. Рассмотрим узел X, который заинтересован в маршрутизации к адресату Y через ближайшего соседа Z. Запись в таблице расстояний Dx( YyZ) узла X представляет собой сумму стоимостей прямой линии между узлами X и Z, то есть c(X, Z) и известного на данный момент соседу Z пути наименьшей стоимости до узла У:

Второе слагаемое, минимальное значение стоимости пути, определяется по всем ближайшим соседям узла Z (включая, как мы скоро увидим, узел X).

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

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

□ Обратите внимание на столбец для адресата А. Очевидно, путь с наименьшей стоимостью до узла Л идет по прямой линии, соединяющей узлы Ем А. Стоимость такого пути равна 1. Таким образом, DE(A, A) = 1.

□ Рассмотрим теперь значение DE(A, D) — стоимость пути от узлаЈ до узла Л, проходящего через узел D. В этом случае запись в таблице расстояний представляет собой стоимость пути от узла Е до узла D (2) плюс минимальную стоимость пути узла D до узла А. Обратите внимание, что минимальная стоимость пути узла D до узла А равна 3. Это путь, проходящий снова через узел Е! Тем не менее мы отмечаем, что минимальная стоимость пути от узла Е до узла Л, проходящего через узел Д равна 5. У нас, однако, остается подозрение, что этот путь «зацикливается», проходя дважды через узел Е, и может стать источником проблем в дальнейшем.

□ Аналогично, мы можем определить, что стоимость пути от узла Ј до узла Л, проходящего через узел В, равна 14. Обратите внимание, что стоимость этого пути равна именно 14, а не 15. (Почему?)

Рис. 9.6Таблица расстояний для узла-источника Е

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