Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.2. МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЕТЕРМИНИРОВАННЫХ ПРОЦЕДУР ВЫБОРА МАРШРУТОВДля реализации детерминированной процедуры маршрутизации программное обеспечение узлов коммутации должно включать программу вычисления вектора кратчайших маршрутов. Наиболее совершенными методами решения этой задачи являются методы Флойда и Дийкстры, базирующиеся на принципе оптимальности. Метод Флойда основан на двух понятиях [35]: базисной липни связи и тернарной операции. Линия связи Метод обеспечивает выявление базисных линий сети путем сравнения веса каждой линии связи В процессе поиска базисных линий связи для всех
При этом вес каждой линии связи При выполнении тернарных операций по всем парам узлов полученные значения
Рис. 3.1.
Векторы кратчайших маршрутов заполняются в процессе вычислений. При этом одновременно можно строить векторы для всех узлов сети. Вначале все элементы векторов полагаются нулевыми для несмежных узлов
Таким образом, алгоритм, реализующий метод Флойда, состоит в выполнении для всех пар узлов Достоинства данного метода — простота реализующего алгоритма и возможность получения маршрутной информации сразу для всех узлов сети. Последнее делает целесообразным его использование при централизованных структурах управления внутренними потоками. Для децентрализованного управления, когда каждый узел строит маршруты только от себя, метод Флойда неэкономичен. Метод Дийкстры [35] состоит в поэтапном наращивании дерева кратчайших маршрутов от исходного узла. При этом необходимо, чтобы после добавления на каждом этапе линии связи и узла вновь образуемый кратчайший маршрут был минимально возможным по всем оконечным узлам, еще не вошедшим в дерево. В процессе построения дерева кратчайших маршрутов вычисляются «векторы весов маршрутов и корректируются векторы начальных Компонент кратчайших маршрутов. Введем ряд понятий и обозначений, используемых при описании алгоритма, реализующего метод Дийкстры. Некоторую часть дерева кратчайших маршрутов Как и ранее, Теперь рассмотрим сам алгоритм для некоторого узла Шаг 0. Ввод исходных данных: номер исходного узла Шаг 1. Присвоение начальных значений переменным и массивам:
Шаг 2. Находится такая линия связи В соответствии с определением Узел Далее производится перерасчет значения Шаг 3. Проверяется окончание процесса построения дерева кратчайших маршрутов. Так как любое остовное дерево графа с М узлами имеет Если это условие выполняется, то процесс заканчивается и следует переход к шагу 5, иначе переход к шагу 4. Шаг 4. Осуществляется перерасчет значений
Рис. 3.2
Рис. 3.3 Если в результате выполнения тернарной операции изменяется значение
т. e. в качестве начальной компоненты маршрута из Шаг 5. Вывод значений Алгоритм, основанный на методе Дийкстрк, является неулучшаемым по числу операций для вычисления кратчайших маршрутов. Для сети с М узлами он требует выполнения не более Пример. Для сети, изображенной на рис. 3.4, а, вычислить вектор начальных компонент кратчайших маршрутов и вектор весов кратчайших маршрутов от узла
Рис. 3.4
(кликните для просмотра скана)
Переход к шагу 2. Шаг 2 (рис. 3.4,д).
Шаг 3. Так как
Переход к шагу 2. Шаг 2 (рис. 3.4,е).
Шаг 3 Так как
Переход к шагу 2. Шаг 2 (рис. 3.4,ж),
Шаг 3. Так как
Конец.
|
1 |
Оглавление
|