Выбор наикратчайшего пути в сети по методу Дейкстры

1 2 3

2.1.1 Выбор варианта:

- исходные данные для топологии сети IP, представленной на рисунке 2.1 приведены в приложении В;

Рисунок 2.1 – Исходная топология сети

- выбор варианта заданий осуществляется по списку журнала преподавателя:

- определить наикратчайшие пути в сети IP между маршрутизаторами методом Дейкстры;

- описать работу сетевых протоколов. Варианты представлены в приложении Г.

2.1.2 Методические указания к выполнению работы 2.1.1. Алгоритм Дейкстры – это алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF (Open Shortest Path First) и IS-IS (Intermediate System to Intermediate System).

При этом в этом алгоритме каждой вершине графа, где установлен маршрутизатор сопоставим метку – минимально известное расстояние от одной вершины до другой. Алгоритм работает пошагово – на каждом шаге он посещает одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершины посещены.

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

Кружками на графе обозначены вершины, линиями - пути между вершинами. В кружках обозначены номера вершин.

Рисунок 2.2 – Граф сети

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

Рисунок 2.3 – Нулевой этап

Нулевой этап фиксируется только с целью указать конечный узел с вершиной "1", метка которого равна нулю.

Минимальную метку имеет вершина 1. Ее соседями являются вершины 2 и 3 (рисунок 2.4).

Рисунок 2.4 – Первый шаг

Первый по очереди сосед вершины 1- вершина 2, так как путь до нее минимален (5). При этом длина пути равна сумме кратчайшего расстояния до вершины 1, то есть 0+5=5. Это значение меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-1 вершины равна 5 (рисунок 2.5).

Рисунок 2.5 – Новая метка первой вершины

Продолжим аналогичные операции с вершиной 3 (рисунок 2.6)

Рисунок 2.6 – Новая метка третьей вершины

Все соседи вершины 1 проверены. Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена (рисунок 2.7).

Рисунок 2.7 – Новая метка третьей вершины

Снова находим ближайшую из непосещенных вершин. Это вершина 2 с текущим кратчайшим расстоянием до нее равным пяти (рисунок 2.8).

Рисунок 2.8 – Посещение вершины 2

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через вторую вершину. Соседями вершины 2 являются 3 и 4. Первый по очереди сосед вершины 2- вершина 1, но она уже посещена, поэтому с первой вершиной ничего не делаем. Следующий сосед это вершина 3, так как она имеет минимальную метку из вершин (8), отмеченных как непосещенные. Если идти в нее через вершину 2, то длина такого пути будет равна 16 (5+11). Но текущая метка 3 вершины равна 8<16, поэтому метка не меняется.

Рисунок 2.9 – Посещение вершины 2 (метка не меняется)

Еще один сосед вершины 2 это вершина 4. Путь до нее через вершину 2 составит 14. Так как 14< , устанавливаем метку вершины 4 равной 14 (рисунок 2.10).

Рисунок 2.10 – Посещение вершины 4

Все соседи вершины 2 проверены. Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена (рисунок 2.11).

Рисунок 2.11 – Отметка вершины 2 как помеченной

Повторяем аналогично выбрав вершину 3 (рисунок 3.12). В результате обработки она будет вычеркнута.

Рисунок 2.12 – Отметка вершины 3 как помеченной

Повторяем для оставшейся вершины 4 (рисунок 2.13).

Рисунок 2.13 – Отметка вершины 4 как помеченной

Завершение выполнения алгоритма происходит тогда, когда все вершины вычеркнуты. В результате получили кратчайшие пути от вершины 1 до 2 составляет 5, до 3 составляет 8 и 4 составляет 14.

2.1.2 Методические указания к выполнению работы 2.1.2. В соответствии варианта изучить и описать работу сетевого протокола.

Контрольные вопросы

1.2.1 В чем состоит основная идея алгоритма Дейкстры?

1.2.2 В каких протоколах маршрутизации применяется алгоритм Дейкстры?

1.2.3 Какие протоколы маршрутизации вы знаете?

1.2.4 Протокол IP версии 4?

1.2.5 Протокол IP версии 6?

1.2.6 Чем отличается IP-адрес класса А от класса В?

1.2.7 Чем отличается IP-адрес класса В от класса С?

1.2.8 Чем отличается IP-адрес класса С от класса А?

1.2.9 Особенности протокола UDP?

1.2.10 Особенности протокола TCP?