- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •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. Нейросетевая маршрутизация в мульти-агентных ткс
- •Список литературы
- •Сведения об авторах
4.3. Особенности организации распределительных таблиц и карт для адаптивной маршрутизации
На практике чаще всего (особенно в АТМ-сетях) приходится решать задачу оптимального распределения потоков данных в ТКС, когда передача пакетов данных ведется не по одному, а по нескольким маршрутам одновременно. При этом информацию о текущем состоянии ТКС целесообразно хранить в локальных БД и БЗ. Рассмотрим модели таких БД и БЗ на примере распределенных таблиц и карт маршрутизации.
Благодаря параллелизму при передаче потоков данных и распределённости сетевого управления значительно увеличивается производительность и отказоустойчивость ТКС. При этом в каждом узле ТКС обычно учитывается суммарная интенсивность потоков данных (т.е. суммарный объем пакетов потока, подлежащих пересылке за единицу времени), проходящих к фиксированному узлу-получателю ТКС, независимо от того, откуда эти потоки пришли.
Интенсивностью потока данных, инициированного некоторым узлом-источником ТКС, будем называть интенсивность этого потока в узле-источнике (при отсутствии других потоков). Из сказанного видно, что в каждый момент времени каждый узел ТКС решает следующую задачу: каким образом для каждого узла-получателя распределить текущий к нему суммарный поток между соседними узлами. При этом каждый узел-получатель рассматривается в отдельности.
Важно определить правила распределения потоков данных таким образом, чтобы при совместной работе всех узлов ТКС обеспечивалась гарантированная доставка пакетов данных от узлов-источников к узлам-получателям за конечное число шагов (т.е. маршруты, по которым идет передача данных, должны быть ацикличны).
Пусть узлы графа G(A,R,W), определяющего структуру и параметры ТКС, упорядочены, т.е.A={ai}Ni=1. Для каждого узла графа упорядочим множество его соседних узлов. С этой целью введем индексное множество:
I={ij|(ai,aj)}R}, (4.3.1)
где ij порядковый номер узла,aj как соседа узла ai
Распределяющей таблицей маршрутизации (РТМ) узла ai назовем отображение
. (4.3.2)
Здесь r – число соседних узлов узла ai, aj – узел-получатель, x – интенсивность суммарного потока к узлу-получателю aj.
При использовании РТМ узла ai поток данных к узлу-получателю aj будет разбиваться на множество потоков к соседям узла ai, причем интенсивность этих потоков, согласно (4.3.2), будет равна x·δk(x).
Пусть для каждого узла ТКС задана РТМ. Карту маршрутизации, определяемую этими таблицами, будем называть распределяющей картой маршрутизации (РКМ).
Если в РТМ распределение потоков не зависит от их интенсивностей, т.е. для любыхсправедливы соотношения
при всех k,
то такие таблицы будем называть статическими РТМ (СРТМ), а РКМ, определяемую множеством таких таблиц, – статической РКМ (СРКМ).
Простые таблицы и карты маршрутизации могут рассматриваться как частный случай статических распределяющих ТМ и КМ, в которых положителен только один элемент вектора распределения.
Заметим, что РКМ для каждой пары узлов “источник-получатель” распределяет поток по некоторому набору маршрутов. При этом если маршрут, по которому протекает поток, конечен, то в силу (4.3.2) он будет заканчиваться в узле-получателе.
Таким образом, маршрутом распределения потока x1>0, определяемым РКМ для узла-источника и узла-получателя , является любая последовательность узлов , удовлетворяющая следующим соотношениям:
(4.3.3)
РКМ назовем корректной, если для каждой пары узлов ТКС, состоящей из узла-источника и узла-получателя , верно, что маршруты, определяемые распределяющей картой маршрутизации для любого потока данных этой пары, являются конечнозвенными и будут заканчиваться в узле-получателе .