Расчет пути с минимальным количеством переходов

Преобразуем исходный граф в неориентированный невзвешенный граф.

 

Рисунок.9 Неориентированный, невзвешенный граф

V2

V1  V3

 

Произведем поиск кратчайшего пути по алгоритму Дейкстры.

Таблица№3

№	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(6)	Путь
1	∞	-	5	1-3	∞	-	1	1-5	5	1-6
2	6  12	1-5-2 1-6-2	5  6	1-3 1-5-3	11	1-3-4	1 9	1-5 1-3-5	5	1-6
3	6 12 17 14	1-5-2 1-6-2 1-3-4-2 1-3-5-2	5 6	1-4-3 1-5-3	11 12 14 9	1-4 1-6-2-4 1-6-2-4	1 9 13	1-5 1-3-5 1-6-2-5	5  9	1-6 1-5-2-6
4	6 18	1-5-2 1-5-3-4-2	5 6 18 15 10	1-3 1-5-3 1-6-2-5-3 1-6-2-4-3 1-5-2-4-3	9 17	1-5-2-4 1-3-5-2-4	10 20	1-6-2-5 1-3-4-2-5	1 23	1-6 1-3-5-2-6

 

Выводы

В итоге оба алгоритма поиска кратчайшего пути привели нас к одинаковому результату. Но по алгоритму Беллмана-Форда результата мы достигли быстрее.

Достоинством алгоритма Дейсктры является то, что на каждом шаге мы находим кратчайшее расстояние еще до одной вершины, а по алгоритму Беллмана- Форда кратчайшее расстояние до любой вершины определяется только после прохождения всего алгоритма.

Расчет пути с минимальным количеством переходов привел к другим результатам, так как исходный граф был преобразован в неориентированный невзвешанный граф.

 

Маршрутизация

Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.

 

Основы маршрутизации

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

Алгоритмы маршрутизации включают процедуры:

- измерение и оценивание параметров сети;

- принятие решения о рассылке служебной информации;

- расчет таблиц маршрутизации (ТМ);

- реализация принятых маршрутных решений.

В зависимости от того, используется ли при выборе направления информация о состоянии только данного узла или всей сети, различают алгоритмы изолированные и глобальные. Если ТМ реагирует на изменения состояния сети, то алгоритм адаптивный (динамический ), иначе фиксированный (статический), а при редких корректировках - квазистатический. В статических маршрутизаторах изменения в ТМ вносит администратор сети.

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

Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.

Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла а каждому из остальных узлов отводится одна строка со следующей информацией:

- узел назначения;

- длина кратчайшего пути;

- номер N ближайшего узла, соответствующего кратчайшему пути;

- список рельефов от а к d через каждый из смежных узлов.

Хотя алгоритм Беллмана-Форда сходится медленно, для сетей сравнительно небольших масштабов он вполне приемлем. В больших сетях лучше себя зарекомендовал алгоритм OSPF. Он основан на использовании в каждом маршрутизаторе информации о состоянии всей сети. В основе OSPF лежит алгоритм Дейкстры поиска кратчайшего пути в графах. При этом сеть моделируется графом, в котором узлы соответствуют маршрутизаторам, а ребра - каналам связи. Веса ребер - оценки (расстояния) между инцидентными узлами.

Находит применение еще один алгоритм маршрутизации - IGRP (Interior Gateway Routine Protocol), разработанный фирмой Cisco. Он аналогичен алгоритму RIP, но развивает его в направлениях: а) возможны различные метрики (целевые функции); б) трафик может распределяться по нескольким каналам с близкими значениями метрики.

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