Алгоритмы маршрутизации. Классификация алгоритмов маршрутизации. Принцип определения оптимальных путей, страница 3

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

Различают кооперированные алгоритмы, которые:

учитывают локальную информацию о состоянии сети и требуют обмен служебными сообщениями только между смежными ЦК;

учитывают глобальную информацию о состоянии сети и требуют обмен служебными сообщениями между всеми ЦК сети.

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

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

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

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

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

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

Определение маршрутов в адаптивных алгоритмах производится в соответствии со следующими критериями оптимальности:

1.  Поиск наиболее короткого по протяженности пути (с наименьшей суммарной длиной составляющих его ребер или ветвей сети);

2.  Поиск пути с минимальными задержками (минимальным временем доставки);

3.  Поиск наиболее протяженного (критического) пути;

4.  Поиск наиболее надежного пути;

5.  Поиск пути с наибольшей пропускной способностью и др.

2. Принцип определения оптимальных путей

Практическая реализация принципа оптимальности основана на последовательном применении к матрице весов тернарной операции. С помощью этой операции элемент матрицы весов заменяется на элемент , вычисляемый в соответствии с выражением:

,  .                              (1)

Символом Â здесь обозначена некоторая обобщенная операция, выполняемая над характеристиками (весами) двух смежных ребер, в результате чего должна получиться характеристика пути, состоящего из этих ребер.

Символ opt характеризует критерий оптимальности, используемый при упорядочении путей. В результате применения операции opt к двум величинам выбирается одна из них – оптимальная.

Конкретное содержание операций opt и Â определяется, в основном, используемым критерием оптимальности. Ниже приведены наиболее часто используемые варианты содержания тернарной операции.

1.  Поиск наиболее короткого (по протяженности) пути.

В данном случае тернарная операция имеет вид   .

Таким образом, операция opt есть операция min, а операция Â - это операция сложения.

2.  Поиск наиболее протяженного (критического) пути.

Для определения такого пути должна использоваться тернарная операция вида

.

3.  Поиск наиболее надежного пути.

Если элементами матрицы весов являются вероятности того, что соответствующие ребра существуют, т.е. то надежность пути между парой вершин будет определяться произведением весов входящих в данный путь ребер (при условии независимости выходов из строя данных ребер). Тогда содержанием операции opt будет определение максимума, а операция Â представляет собой операцию произведения двух чисел. Таким образом, тернарная операция имеет вид  .

4.  Поиск пути с наибольшей пропускной способностью.

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

. Здесь opt = max, а Â = min.

К наиболее эффективным (с точки зрения вычислительной сложности) алгоритмам поиска оптимальных путей доставки информации в сети следует в первую очередь отнести такие алгоритмы, как алгоритм Дейкстры, алгоритм Данцига, алгоритм Флойда, матричный алгоритм и некоторые другие.

Для всех перечисленных алгоритмов исходными данными являются в первую очередь матрица весов  и выбранный критерий оптимальности {opt, Â}. При этом результатом работы алгоритмов является модификация матрицы весов (элементами матрицы являются веса всех оптимальных путей в графе).