Алгоритм поиска наикратчайшего пути (алгоритм Дейкстры)
Алгоритм Дейкстры – алгоритм поиска наикратчайшего маршрута по графу. Применительно к протоколу маршрутизации в виде графа изображается топология сети, где вершинами являются маршрутизаторы сети, а ребрами – связи между ними. Каждое ребро графа имеет вес, определенный на основе способа расчета метрики, применяемого в протоколе маршрутизации.
Данный граф строит каждый маршрутизатор сети на основе знаний о всей сети в целом.
Рассмотрим работу алгоритма Дейкстры на примере. Дана сеть, топология которой изображена на рис. 48 в виде графа.
Рис. 48. Начальная топология сети
Задача алгоритма состоит в нахождении кратчайшего пути до всех вершин графа. Точкой отчета является вершина 1, которая является тем маршрутизатором, на котором производится расчет.
Шаг 1. Всем вершинам, кроме начальной, присваивается бесконечное расстояние от исходной вершины. Начальной – нулевое.
Шаг 2. Определяется расстояние от вершины, в которой алгоритм находится в данный момент, до всех соседних вершин. Расстояние равно сумме расстояния данной вершины от исходной (вершина 0) вершины и веса ребра, по которому возможно пройти до вершины. Если расстояние меньше расстояния, ассоциируемого с данной вершиной, новое расстояние присваивается вершине. Таким образом, расстояние от вершины 1 до вершины 3 равно 3, от вершины 1 до вершины 3 – 7, от вершины 1 до вершины 4 – 4.
Шаг 3. Осуществляется переход в соседнюю непосещенную вершину от исходной с наименьшим расстоянием. Предыдущая вершина помечается, как посещенная (рис. 49).
|
|
|
Рис. 49. Переход в соседнюю вершину с наименьшим расстоянием
Шаг 4. Повторяются шаги 2, 3 (рис. 50).
| | |
| | |
Рис. 50. Пошаговый поиск наикратчайшего маршрута на основе алгоритма Дейкстры
Таким образом, например, до вершины 6 из вершины 1 наикратчайший маршрут проходит через вершины 1-4-6.
Стоит отметить, что в случае существования маршрутов с равным расстоянием у алгоритма Дейкстры нет четкого критерия выбора маршрута. Этот вопрос решается непосредственно самим алгоритмом маршрутизации. Например, протокол OSPF поддерживает балансировку маршрутов, заключающуюся в существовании нескольких, близких по стоимости, маршрутов до пункта назначения. По умолчанию число подобных маршрутов равно 4, но технологии поддерживают до 16.
Балансировка маршрутов быть как потоковая, так и пакетная. Потоковая балансировка обеспечивает пересылку потоков (поток пакетов от одного и того же источника к одному и тому же получателю), а пакетная – отдельных пакетов. Таким образом, в первом случае при передаче, например, от одного и того же источника потока пакетов к двум разным получателям один поток будет направлен по одному маршруту, второй – по другому. При пакетной балансировке пакеты (а не потоки) будут направляться по разным маршрутам, не зависимо от адреса получателя.
|
|
|
Сообщения протокола OSPF
Формат заголовка сообщений OSPF представлен на рис.51. Сообщения протокола OSPF инкапсулируются непосредственно в пакет протокола IP версии 4 и отправляются на групповой адрес 224.0.0.5.
Рис. 51. Формат заголовка сообщения протокола OSPF
Поле «Версия» содержит версию протокола OSPF. На данный момент функционирует 2 версия протокола и, следовательно, в данном поле записано число 2.
Поле «Тип» определяет сообщения, идентифицируя тем самым функционал сообщения:
1. «Hello» – используется для проверки доступности маршрутизатора;
2. «Data State Description» – описание топологической базы данных;
3. «Link State Request» – запрос состояния канала;
4. «Link State Update» – изменение состояния канала;
5. «Link State Acknowledgment» – подтверждение получения сообщения о статусе канала.
Поле «Длина пакета» определяет длину сообщения, включая заголовок.
Поле «Идентификатор маршрутизатора» включает уникальный 32-битный код маршрутизатора, отправившего сообщения, идентифицирующий маршрутизатор в пределах автономной системы.
|
|
|
Поле «Идентификатор области» – 32-битный код идентифицирующий область. Протокол OSPF является иерархическим протоколом, использующим двухуровневую иерархию: автономную систему и область.
Область – группа смежных сетей, логические разделы автономной системы.
Автономная системы – совокупность сетей с общим управлением и общей стратегией маршрутизации.
Использование подобной иерархии (рис. 52) позволяет уменьшить размер топологической базы данных состояния канала и таблиц маршрутизации.
Рис. 52. Понятие автономной системы и области в протоколе OSPF
Поле «Контрольная сумма» включает контрольную сумму всего сообщения.
Поле «Тип аутентификации» определяет наличие и тип аутентификации (0 – отсутствие контроля доступа, 1 – аутентификация открытым текстом, 2 – аутентификация MD5).
Поле «Аутентификация» – поле данных аутентификации.
Дата добавления: 2018-06-01; просмотров: 452; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!