- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •1. Эволюция глобальных ткс и принципов управления потоками данных
- •1.1. Рост объема и изменение структуры трафика в глобальных ткс
- •1.2. Современные тенденции развития глобальных ткс
- •1.3. Pазвитие ip-технологий маршрутизации и передачи потоков данных
- •1.4. Архитектура глобальных ткс и роль сетевой системы управления
- •1.5. Принципы построения адаптивных и интеллектуальных систем сетевого управления
- •1.6. Анализ ткс как информационного объекта управления
- •1.6.1. Графовые модели ткс
- •1.6.2. Матричные модели ткс и их взаимосвязь
- •1.6.3. Критерии коммуникабельности ткс
- •2. Методы статической маршрутизации потоков данных в мульти-агентных ткс
- •2.1. Задачи маршрутизации потоков данных и их роль в сетевом управлении ткс
- •2.2. Постановка задачи оптимальной статической маршрутизации
- •2.3. Модели и алгоритмы статической маршрутизации
- •2.3.1. Дерево кратчайших маршрутов для ткс с односторонними связями
- •2.3.2. Каталог узлов и оптимальных маршрутов для статических ткс
- •2.3.3. Метод статической лавинной маршрутизации
- •2.3.4. Методы вероятностной маршрутизации
- •2.3.5. Метод оптимальной маршрутизации, основанный на построении остова минимальной стоимости графовой модели ткс
- •2.4. Групповая маршрутизация в статических ткс
- •2.6. Оптимальная статическая маршрутизация в глобальных мульти-агентных ткс
- •3. Методы и средства динамической маршрутизации в глобальных ткс
- •3.1. Постановка задачи динамической маршрутизации
- •3.2. Основные алгоритмы динамической маршрутизации
- •3.2.1. Алгоритм Беллмана-Форда и его модификации
- •3.2.2. Алгоритм Дейкстры
- •3.3. Критерии существования оптимальных маршрутов передачи данных в динамических ткс на основе простых карт и таблиц маршрутизации
- •3.3.1. Критерий маршрутизируемости
- •3.3.2. Оптимальные таблицы и карты маршрутизации и вычисление оптимальных маршрутов
- •3.5. Много-адресная маршрутизация в динамических ткс
- •3.6. Многопотоковая маршрутизация в динамических ткс
- •3.7. Алгоритм 2-потоковой динамической маршрутизации
- •4. Модели и методы адаптивной и нейросетевой маршрутизации в мульти-агентных ткс
- •4.1. Особенности адаптивной маршрутизации в ткс с неопределённой днамикой
- •4.2. Принципы и модели централизованной, децентрализованной и мульти-агентной маршрутизации
- •4.3. Особенности организации распределительных таблиц и карт для адаптивной маршрутизации
- •4.4. Критерии корректности распределяющих карт маршрутизации
- •4.5. Расширение карт маршрутизации и интенсивность потоков данных
- •4.6. Централизованная и распределённая маршрутизации в мульти-агентных ткс
- •4.7. Нейросетевая маршрутизация в мульти-агентных ткс
- •Список литературы
- •Сведения об авторах
2.3.5. Метод оптимальной маршрутизации, основанный на построении остова минимальной стоимости графовой модели ткс
Задача статической маршрутизации для остовного алгоритма полагает, что в качестве решения задачи маршрутизации алгоритм прокладывает от заданного узла-источника до каждого узла-получателя ТКС ровно один маршрут. При этом структура ТКС считается фиксированной, т.е. не изменяющейся с течением времени, и не учитываются такие параметры, как интенсивность потоков данных и текущая загрузка каналов связи ТКС.
Постановка задачи оптимальной маршрутизации пакетов данных в статических (фиксированных) ТКС для остовного алгоритма следующая. Пусть статическая модель ТКС представлена графом G(A,R,W) и задана пара узлов , первый из которых является узлом-источником, а второй – узлом-получателем. Требуется найти маршрут передачи пакетов данных из s в f минимальной стоимости.
Так как любой подмаршрут оптимального маршрута является оптимальным, то для решения задачи оптимальной маршрутизации достаточно построить дерево кратчайших маршрутов для каждого узла-источника . В случае симметричных статических ТКС, у которых веса каналов связи (ребер графа) одинаковы в обоих направлениях и не изменяются с течением времени, любое дерево кратчайших маршрутов для одного узла будет деревом кратчайших маршрутов для всех остальных узлов. Это означает, что в симметричных ТКС задача оптимальной маршрутизации сводится к задаче построения остова минимальной стоимости, т.е. максимального связного подграфа T графа G, не содержащего циклов, сумма стоимостей ребер которого минимальна.
Рассмотрим алгоритм построения такого остова.
Работа алгоритма:
Алгоритм выполняется итеративно за конечное число шагов. Сначала выбираем произвольный узел и полагаем, что
T =({s}, Ø, W). (2.3.4)
Шаг алгоритма: выбираем ребро с минимальным весом такое, что его начальный узел, принадлежит графу T, а конечный узел – не принадлежит T, и добавляем его вместе с конечным узлом в T, т.е.
. (2.3.5)
Алгоритм выполняется до тех пор, пока в T не войдут все вершины графа G.
Теорема 2.3.1: Граф T, построенный по остовному алгоритму, будет остовом минимальной стоимости графовой модели G симметричной статической ТКС.
Для доказательства этой теоремы потребуется следующая лемма.
Лемма 2.3.1: Для любого узла aiA графа G(A,R,W) симметричной ТКС инцидентные ему ребра (ai,aj)R минимальной стоимости содержатся в графе T вида (2.3.4), (2.3.5).
Доказательство леммы 2.3.1: При построении графа T возникает два случая, когда на очередном шаге алгоритма существует возможность включения ребра (ai,aj) в T:
1) ;
2) .
Рассмотрим первый случай. Так как ai принадлежит T, то либо ai=s (тогда согласно (2.3.5) ребро (ai,aj) будет включено в T на первом шаге), либо на каком-то шаге узел ai включен в T вместе с ребром, чья стоимость, с одной стороны, меньше стоимостей всех остальных ребер, которые не принадлежат T и инцидентны узлам, входящим в T, а, с другой стороны, – больше, чем стоимость ребра (ai,aj). Тогда из (2.3.5) следует, что ребро (ai,aj) будет включено в T на следующем шаге.
Во втором случае будем рассматривать шаг алгоритма, на котором в T будет включен узел ai. Согласно (2.3.5) этот узел войдет в T вместе с ребром (ai,aj), так как его стоимость среди всех инцидентных ai ребер – минимальна.
Таким образом, лемма 2.3.5 доказана.
Доказательство теоремы 2.3.5. Так как граф G симметричной ТКС – связный, то на каждом шаге алгоритма множество ребер, начало которых принадлежит T, а конец – нет, будет непустым. Таким образом, процесс построения не закончится, пока в T не войдут все вершины графа G.
Так как на каждом шаге алгоритма к графу T добавляется по одному узлу и одному ребру, а в начале он содержит только один узел и одно ребро, то в конце он будет состоять из N узлов и N-1 ребра (где N – число узлов в графе G). Это означает, что T будет остовом графовой модели G ТКС. Докажем, что его стоимость будет минимальной.
Рассуждая от противного, предположим, что существует остов T1 такой, что сумма весов его рёбер меньше суммы весов рёбер остова T. Тогда справедливо соотношение
. (2.3.6)
Однако это соотношение противоречит утверждению леммы 2.3.1. Следовательно, соотношение (2.3.6) неверно и стоимость T действительно минимальна.
Теорема 2.3.1 доказана. Она является теоретическим обоснованием остовного алгоритма оптимальной маршрутизации.
Пример работы этого алгоритма приведен на рис.2.3.4., где остов с минимальной стоимостью выделен жирными линиями.
Error: Reference source not found
Рис. 2.3.4. Пример симметричного графа ТКС с построенным в нем остовом минимальной стоимости.