Исследование процессов маршрутизации (стр. 3 из 6)
При h= Кдля каждой вершины-получателя палгоритм сравнивает потенциальный путь от вершины sдо вершины пдлиной К + 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает меньшей стоимостью, то он сохраняется. В противном случае сохраняется новый путь от вершины s до вершины п длиной К + 1. Этот путь состоит из пути длиной Кот вершины Кдо некоей вершины j и прямого участка от вершины jдо вершины п. В этом случае используемый путь от вершины sдо вершины j представляет собой путь, состоящий из Кретрансляционных участков.
В табл. 2 показан результат применения этого алгоритма к графу, представленному на рис. 8, в котором в качестве вершины s выбираем: вершину V1.На каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно h. После последней итерации алгоритм находит путь с минимальной стоимостью к каждой вершине, а также вычисляется стоимость этого пути. Та же процедура может быть применена к вершине V2и т. д. Результаты работы алгоритмов Дейкстры и Беллмана - Форда совпадают.
Рисунок.8
V2
V1
V3Таблица№2
| № | 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-21-6-2 | 5  6 | 1-31-5-3 | 11 | 1-3-4 | 19 |  1-51-3-5 | 5 | 1-6 |
| 3 | 6  12  1714 |  1-5-21-6-21-3-4-21-3-5-2 | 56 | 1-4-31-5-3 | 1112149 | 1-41-6-2-41-6-2-4 | 1913 | 1-51-3-51-6-2-5 | 5 9 |  1-61-5-2-6 |
| 4 | 6 18 | 1-5-21-5-3-4-2 | 5  6  181510 |  1-31-5-31-6-2-5-31-6-2-4-31-5-2-4-3 | 9  17 | 1-5-2-41-3-5-2-4 | 10  20 | 1-6-2-51-3-4-2-5 | 1  23 | 1-61-3-5-2-6 |
1.4.Расчет пути с минимальным количеством переходов
Преобразуем исходный граф в неориентированный невзвешенный граф.
Рисунок.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-21-6-2 | 5 6 | 1-31-5-3 | 11 | 1-3-4 | 19 | 1-51-3-5 | 5 | 1-6 |
| 3 | 6 12 1714 | 1-5-21-6-21-3-4-21-3-5-2 | 56 | 1-4-31-5-3 | 1112149 | 1-41-6-2-41-6-2-4 | 1913 | 1-51-3-51-6-2-5 | 5 9 | 1-61-5-2-6 |
| 4 | 6 18 | 1-5-21-5-3-4-2 | 5 6 181510 | 1-31-5-31-6-2-5-31-6-2-4-31-5-2-4-3 | 9 17 | 1-5-2-41-3-5-2-4 | 10 20 | 1-6-2-51-3-4-2-5 | 1 23 | 1-61-3-5-2-6 |
1.5 Выводы
В итоге оба алгоритма поиска кратчайшего пути привели нас к одинаковому результату. Но по алгоритму Беллмана-Форда результата мы достигли быстрее.
Достоинством алгоритма Дейсктры является то, что на каждом шаге мы находим кратчайшее расстояние еще до одной вершины, а по алгоритму Беллмана- Форда кратчайшее расстояние до любой вершины определяется только после прохождения всего алгоритма.
Расчет пути с минимальным количеством переходов привел к другим результатам, так как исходный граф был преобразован в неориентированный невзвешанный граф.
2. Маршрутизация
Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.
2.1 Основы маршрутизации
Алгоритмы маршрутизации можно дифференцировать, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи, которые решает разработчик алгоритма. Во-вторых, существуют различные типы алгоритмов маршрутизации, и каждый из них по-разному влияет на сеть и ресурсы маршрутизации. И наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов.
Алгоритмы маршрутизации включают процедуры:
- измерение и оценивание параметров сети;
- принятие решения о рассылке служебной информации;
- расчет таблиц маршрутизации (ТМ);
- реализация принятых маршрутных решений.
В зависимости от того, используется ли при выборе направления информация о состоянии только данного узла или всей сети, различают алгоритмы изолированные и глобальные. Если ТМ реагирует на изменения состояния сети, то алгоритм адаптивный (динамический), иначе фиксированный (статический), а при редких корректировках - квазистатический. В статических маршрутизаторах изменения в ТМ вносит администратор сети.
Простейший алгоритм - изолированный, статический. Алгоритм кратчайшей очереди в отличие от простейшего является адаптивным, пакет посылается по направлению, в котором наименьшая очередь в данном узле. Лавинный алгоритм - многопутевой, основан на рассылке копий пакета по всем направлениям, пакеты сбрасываются, если в данном узле другая копия уже проходила. Очевидно, что лавинный алгоритм обеспечивает надежную доставку, но порождает значительный трафик и потому используется только для отдельных пакетов большой ценности.
Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.