Алгоритм Беллмана-Форда

сеть граф маршрутизация алгоритм

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

Этот алгоритм также работает поэтапно, формально он может быть определен следующим образом. Введем обозначения:

s –вершина-источник;

w(i,j) – стоимость линии от вершины i до вершины j, причем w(i, j) = 0 или w(i,j) = ¥, если две вершины не соединены напрямую, и w(i, j) => 0, если две вершины соединены напрямую;

h – максимальное количество ребер в пути на текущем шаге алгоритма;

Lh(n) – минимальная стоимость пути от вершины s до вершины п при условии, что этот путь состоит не более чем из h ребер.

Алгоритм состоит из двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться.

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

L0(n) = ¥ для всех п ¹ s,

Lh(s) = 0 для всех h.

2. Обновление. Для каждого последовательного h >= 0 и для каждого п¹s вычислить

Lh+1(n) - min[Lh(j) + w(j, n)].

Соединить вершину п с предыдущей вершиной j, для которой находится минимальное значение, и удалить любое соединение вершины п с предыдущей вершиной, образованное на более ранней итерации. Путь от вершины s до вершины п заканчивается линией связи от вершины j до вершины п.

При h = К для каждой вершины-получателя п алгоритм сравнивает потенциальный путь от вершины s до вершины п длиной К + 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает меньшей стоимостью, то он сохраняется. В противном случае сохраняется новый путь от вершины s до вершины п длиной К + 1. Этот путь состоит из пути длиной К от вершины К до некоей вершины j и прямого участка от вершины j до вершины п. В этом случае используемый путь от вершины s до вершины j представляет собой путь, состоящий из К ретрансляционных участков, найденный на предыдущей итерации. По завершении работы алгоритма вычисляется связующее дерево графа.

В таблице 2 и на рисунке 4 показан результат применения этого алгоритма к графу, представленному на рисунке 2.1.

Таблица 2 – Результаты работы алгоритма Беллмана-Форда для заданного графа

Рисунок 4 – Применение алгоритма Беллмана-Форда к графу, приведенному на рис. 2.1

5. Компоненты маршрутизации

Маршрутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. При этом, как правило, на пути встречается, по крайней мере, один узел.

Маршрутизация включает в себя два основных компонента: определение оптимальных трактов маршрутизации и транспортировка информационных групп (обычно называемых пакетами) через объединенную сеть. Коммутацией – это транспортировка информационных групп через объединенную сеть.

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

6. Алгоритмы маршрутизации

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

Цели разработки алгоритмов маршрутизации

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

1. Оптимальность

2. Простота и низкие непроизводительные затраты

3. Живучесть и стабильность

4. Быстрая сходимость

5. Гибкость

1. Оптимальность

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

2. Простота и низкие непроизводительные затраты

Алгоритмы маршрутизации разрабатываются как можно более простыми. Другими словами, алгоритм маршрутизации должен эффективно обеспечивать свои функциональные возможности, с минимальными затратами программного обеспечения и коэффициентом использования. Особенно важна эффективность в том случае, когда программа, реализующая алгоритм маршрутизации, должна работать в компьютере с ограниченными физическими ресурсами.

3. Живучесть и стабильность

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

4. Быстрая сходимость

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

К типам алгоритмов маршрутизации относят:

1. статический или динамический;

2. одномаршрутный или многомаршрутный;

3. одноуровневый или иерархический;

4. с интеллектом в главной вычислительной машине или в роутере;

5. внутридоменный и междоменный;

6. алгоритм состояния канала или вектора расстояний.

Рассмотрим подробнее каждый тип алгоритма маршрутизации.

1. Статические или динамические алгоритмы

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

Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации.

2. Одномаршрутные или многомаршрутные алгоритмы

Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения; одномаршрутные алгоритмы не могут делать этого.

3. Одноуровневые или иерархические алгоритмы

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

4. Алгоритмы с интеллектом в главной вычислительной машине или в роутере

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

Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов роутеры определяют маршрут через объединенную сеть, базируясь на своих собственных расчетах – это алгоритмы с интеллектом в роутере.

5. Внутридоменные или междоменные алгоритмы

Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие – как в пределах доменов, так и между ними.

6. Алгоритмы состояния канала или вектора расстояния

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

К основным показателям алгоритмов (метрики) относят:

· длина маршрута;

· надежность;

· задержка;

· ширина полосы пропускания;

· нагрузка;

· стоимость связи.

Длина маршрута

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

Надежность

Надежность, в контексте алгоритмов маршрутизации, относится к надежности каждого канала сети.

Задержка

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

Полоса пропускания

Полоса пропускания является оценкой максимально достижимой пропускной способности канала.

7. Протокол обмена маршрутной информацией

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

· дистанционно-векторный алгоритм (Distance Vector Algorithms, DVA),

· алгоритм состояния связей (Link State Algorithms, LSA).

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

Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP.

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

Протоколом, основанным на алгоритме состояния связей, в стеке TCP/IP является протокол OSPF.