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

Рис. 9.4Абстрактная модель сети

Для формулирования алгоритмов маршрутизации сеть рассматривается как граф (рис. 9.4). Узлы графа представляют маршрутизаторы — точки, в которых принимаются решения о продвижении пакетов, — а линии (в соответствии с терминологией теории графов называемые «ребрами»), соединяющие эти узлы, представляют физические линии между маршрутизаторами. Каждой линии связи соответствует некоторое значение, представляющее «стоимость» пересылки пакета по этой линии. Стоимость может зависеть от физической длины линии (например, стоимость передачи кадра по трансокеанскому кабелю может быть выше, чем по короткому кабелю, проложенному по суше), скорости передачи данных по линии или финансовой стоимости линии. Для наших текущих целей мы просто примем стоимости линий как данное и не станем беспокоиться о том, как они определяются.

При рассмотрении сети в виде графа для решения задачи определения пути от отправителя к получателю с минимальной стоимостью необходимо найти последовательность линий такую, что:

□ первая линия пути соединена с источником;

□ последняя линия пути соединена с адресатом;

□ для всех i линии с номерами i и i – 1 соединены с одним и тем же узлом;

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

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

В качестве простого упражнения попытайтесь найти путь с минимальной стоимостью от узла А до узла F. Скорее всего, вы будете искать путь от узла А до узла F, изучая рис. 9.4 и пробуя несколько маршрутов от узла Л до узла F, каким-то образом определяя, что стоимость выбранного вами пути минимальна из всех возможных путей (вряд ли вам удастся проверить все 17 возможных путей между узлами А и F). Подобные вычисления представляют собой пример централизованного алгоритма маршрутизации — алгоритм маршрутизации рассчитывался в одном месте (вашем мозгу) при наличии полной информации о сети. Обобщая, скажем, что все алгоритмы маршрутизации можно разбить на два класса: глобальные и децентрализованные.

□ Глобальный алгоритм маршрутизации находит путь с наименьшей стоимостью от отправителя до получателя с помощью полной информации о сети. Таким образом, в качестве входных данных алгоритм использует информацию о том, какой узел с каким соединен напрямую линией связи, и о стоимости всех линий. Прежде чем начать сами вычисления, данный алгоритм должен каким-то образом получить эту информацию. Сами вычисления могут производиться на каком-либо одном компьютере (централизованный глобальный алгоритм маршрутизации) или тиражироваться в разных местах. Однако ключевой особенностью здесь является то, что глобальный алгоритм обладает полной информацией о топологии сети и стоимости линий. На практике алгоритмы, обладающие глобальной информацией о состоянии сети, часто называют алгоритмами, основанными на состояниях линий, так как алгоритм должен знать стоимость каждой линии в сети. Мы рассмотрим глобальный алгоритм, основанный на состояниях линий, в подразделе «Алгоритм маршрутизации, основанный на состояниях линий» раздела «Основы маршрутизации».

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

Кроме того, все алгоритмы маршрутизации можно разделить на статические и динамические. В статическом алгоритме маршрутизации маршруты изменяются со временем очень медленно, часто в результате вмешательства человека (например, администратор сети может вручную отредактировать таблицу продвижения данных маршрутизатора). Динамический алгоритм может либо запускаться периодически, либо в ответ на изменения топологии или стоимости линий. Хотя динамические алгоритмы обладают большей чувствительностью к изменениям в сети, они также более восприимчивы к таким проблемам, как петли в маршрутах и осцилляция. Данные проблемы будут рассматриваться в подразделе «Алгоритм дистанционно-векторной маршрутизации» данного раздела.

Третий способ классификации алгоритмов маршрутизации определяется по тому, чувствителен ли алгоритм к перегрузке. В чувствительном к перегрузке алгоритме стоимости линий динамически изменяются, отражая текущий уровень перегрузки в соответствующей линии. Если с временно перегруженной линией ассоциируется высокая стоимость, алгоритм маршрутизации будет стараться выбирать маршруты в обход перегруженной линии. Первые алгоритмы сети ARPAnet были чувствительными к перегрузке, однако попытки использования чувствительных к перегрузке алгоритмов натолкнулись на ряд проблем. Сегодня в Интернете применяются алгоритмы, нечувствительные к перегрузке (такие как RIP, OSPF и BGP), так как стоимость линии, как правило, не отражает ее текущего (или недавнего) уровня перегрузки.

В Интернете, как правило, используются только два типа алгоритмов маршрутизации: динамический глобальный алгоритм, основанный на состояниях линий, и динамический децентрализованный дистанционно-векторный алгоритм.

5. Алгоритм маршрутизации, основанный на состоянии линии для сети        

Как уже отмечалось, алгоритм, основанный на состоянии линий (Line State, LS), знает стоимость всех линий, то есть все эти данные можно подать на вход LS-алго-ритма. На практике, чтобы собрать эту информацию, каждый узел путем широковещательной рассылки отправляет свой идентификатор и стоимости всех присоединенных к нему линий всем остальным маршрутизаторам сети. Чтобы выполнить эту операцию, узлам не нужно знать идентификаторы всех остальных узлов сети. Узел должен лишь знать идентификаторы своих ближайших соседей, а также стоимости линий, соединяющих его с ними. О топологии остальной сети ему станет известно, когда он получит широковещательные пакеты с информацией о состоянии линий от других узлов. (В главе 5 мы узнаем, как маршрутизатор узнает идентификаторы своих ближайших соседей.) В результате всех этих широковещательных рассылок все узлы сети получают идентичное и полное представление о сети. Затем каждый узел может запустить алгоритм, основанный на состояниях линий, и вычислить пути к каждому из узлов.

Ниже мы рассмотрим пример алгоритма, основанный на состояниях линий, на примере алгоритма Дейкстры, названного по имени его создателя. Близко связан с ним алгоритм Прима. Алгоритм Дейкстры вычисляет путь с наименьшей стоимостью от одного узла (источника, который мы будем называть узлом Л) до всех остальных узлов сети. Алгоритм Дейкстры является итерационным и после k итераций он определяет пути с наименьшей стоимостью до k узлов-адресатов, и среди путей с наименьшей стоимостью до всех узлов-адресатов у этих k путей будут k наименьших стоимостей. Определим систему обозначений:

□ c(i, j) — стоимость линии от узла г до узла/ Если узлы i и j не соединены напрямую, тогда c(i, j) = ∞. Чтобы упростить нашу систему обозначений и примеры, мы будем предполагать, что c(i, j) = c(j, i). Однако следует отметить, что данный алгоритм будет работать и в случае, когда стоимости c(i, j) и c(j, i) не равны.

□ D(v) — стоимость пути от узла-источника до узла-адресата v, у которого на данный момент (на текущей итерации алгоритма) стоимость минимальна.

□ p(v) — предыдущий узел (соседний с узлом v) на текущем пути с наименьшей стоимостью от источника до узла v.

□ N — множество узлов, для которых на данной итерации известны пути с наименьшей стоимостью.

Алгоритм, основанный на состоянии линий, состоит из этапа инициализации, за которым следует цикл. Количество итераций этого цикла равно числу узлов в сети. По завершении алгоритм вычислит кратчайший путь от узла-источника (А) до всех остальных узлов сети.

Листинг 9.1. Алгоритм, основанный на состоянии линий для узла-источника А

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

2 N = {А}

3 для всех узлов v

4 если v смежный с А

5 тогда D(v) = c(A. v)

6 иначе D(v) = ∞

8 цикл

9 найти w, не входящий в N. такой что D(w) минимальна

10 добавить w к N

11 обновить D(v) для всех v. смежных с w и не входящих в N:

12 D(v) = min(D(v). D(w) + c(w. v))

13 /* новая стоимость пути к v равна старой стоимости к v или стоимости

14 известного кратчайшего пути к w плюс стоимость пути от w к v */

15 по всем узлам в N

В качестве примера рассмотрим сеть, показанную на рис. 4.4, и найдем пути с минимальной стоимостью от узла А до всех возможных адресатов. В табл. 4.2 показаны поэтапные результаты работы алгоритма. В каждой строке таблицы приведены значения переменных алгоритма в конце очередной итерации.

Таблица 9.2Результаты работы алгоритма, основанного на состоянии линий, для сети с рис. 9.4