- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •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. Методы статической маршрутизации потоков данных в мульти-агентных ткс
Целью маршрутизации является планирование, оптимизация (по заданному критерию оптимальности) и адаптация маршрута передачи пакетов от источника запроса или данных к их получателю, которые в общем случае могут находиться в различных автономных подсетях глобальной ТКС. Для достижения этой цели маршрутизатор должен обладать информацией о топологии и стоимости каналов связей подсетей глобальной ТКС, об адресах узлов-источников и узлов-получателей данных, о критериях оптимальности маршрутов и т.п [1–4].
Целью управления является оптимизация передачи пакетов данных между соседними узлами маршрута и адаптация к перегруженному или неизвестному сетевому трафику, непредсказуемо изменяющемуся в реальном времени в широких пределах [1–3, 17–20].
В глобальных ТКС маршруты передачи потоков данных могут проходить как через узлы автономных подсетей, так и через узлы магистральных сетей, связывающих между собой эти подсети. В этом случае решение о выборе того или иного маршрута передачи пакетов внутри подсети принимают внутренние (локальные) маршрутизаторы этой подсети, а вне подсети – внешние (магистральные) маршрутизатор. Такая схема маршрутизации потоков данных по существу является распределённой (децентрализованной).
При централизованной схеме маршрутизации планирование и выбор маршрутов передачи пакетов возлагается на специальный магистральный маршрутизатор, который иерархически связан с остальными маршрутизаторами и координирует их работу.
Значительный интерес представляет также схема маршрутизации от узла-источника или ближайшего к нему маршрутизатора, так как в этом случае критерий оптимальности маршрута непосредственно задает клиент (пользователь) как внешний агент ТКС.
2.1. Задачи маршрутизации потоков данных и их роль в сетевом управлении ткс
Общая задача управления потоками данных в глобальных ТКС с пакетной коммутацией или маршрутизацией передаваемой информации распадается на две взаимосвязанные задачи:
1) планирование (вычисление), оптимизация и адаптация маршрутов передачи потоков данных от узла-источника (отправителя) запроса или данных к узлу-получателю (адресату) ТКС;
2) управление передачей потока данных по заданному маршруту с адаптацией к изменяющему трафику и возможным перегрузкам в ТКС.
Первая задача решается на сетевом уровне с помощью маршрутизаторов глобальной ТКС, которые обычно устанавливаются в узлах автономных подсетей глобальной ТКС или связывающих их магистральных сетей.
Вторая задача решается на уровне передачи данных с помощью систем адаптивного управления передачей пакетов данных от узла к узлу по спланированному маршруту.
Формализация и методы решения задач маршрутизации и управления потоками данных зависят от реального трафика и конкретных типов приложений, режимов эксплуатации ТКС, числа внешних агентов-пользователей и т.п. При этом потоком данных называется последовательность пакетов, обладающими некоторыми общими свойствами. Например, все потоки данных между узлом-источником и узлом-получателем ТКС должны иметь общие (одинаковые) IP-адреса этих узлов, определяющих начальный и конечный узлы маршрута передачи потока данных.
Простейшая статическая постановка задачи планирования и оптимизации маршрутов передачи данных основывается на предположении, что структура (число узлов, топология и стоимость каналов связи) ТКС известна и неизменна, а в роли внешнего агента-пользователя ТКС выступает один клиент, формирующий запрос к одному из узловых компьютеров сети.
Динамическая постановка задачи маршрутизации по запросу клиента исходит из того, что структура ТКС может изменяться с течением времени, но остаётся известной. При этом сетевая информация автоматически обновляется через определённые интервалы времени, что приводит к соответствующему изменению оптимальных маршрутов. Эти интервалы времени называются временем жизни маршрутов (Time to Live, TTL).
При адаптивной постановке задачи маршрутизация осуществляется в условиях неопределённости, когда топология каналов связи и трафик ТКС могут непредсказуемо изменяться, а доступная информация имеет локальный характер. Обновление сетевой информации позволяет скорректировать маршруты, приспосабливая их к изменяющимся условиям эксплуатации ТКС (сетевая перегрузка, отказы и т.п.).
Необходимость в динамической и адаптивной маршрутизации потоков данных в глобальных ТКС возникает в следующих случаях:
1) изменение стоимости каналов связи ТКС (например, при их замене);
2) отказ (выход из строя) в ТКС одного или нескольких каналов связи;
3) добавление в ТКС новых каналов связи;
4) отказ (выход из строя) одного или нескольких узлов ТКС;
5) добавление в ТКС новых узлов;
6) перегрузка каналов связи ТКС;
7) перегрузка (переполнение) буферов узлов ТКС.
В первом случае необходимо обновить данные о весах (стоимости) ребер графа ТКС, а во втором и третьем – исключить или добавить соответствующие ребра в графе ТКС. В четвертом и пятом случаях нужно изменить данные об узлах ТКС путем исключения или добавления соответствующих вершин (узлов) в графе ТКС. В шестом и седьмом случаях соответствующие ребра и вершины графа ТКС рассматриваются как “запретные” каналы связи и узлы, играющие роль непреодолимых препятствий для маршрутизации и передачи потоков данных.
Все указанные изменения структуры или параметров ТКС вносятся вручную (операторами или администраторами ТКС) или автоматически в локальные базы данных (БД) или базы знаний (БЗ) узлов ТКС. При этом узлы ТКС должны обмениваться информацией об изменениях своих БД или БЗ, используя доступные каналы связи и протоколы передачи данных. Поэтому все узлы, имеющие собственные (локальные) БД и БЗ и каналы связи между собой для обмена информацией, могут рассматриваться как информационные агенты ТКС, осуществляющие мониторинг ТКС и обновление информации о её текущем состоянии.
Изменения первого типа характеризуют динамику (нестационарность) ТКС (без изменения их структуры), а изменения второго-пятого типа приводят к изменению структуры (топологии) ТКС как объектов управления. Для учета и компенсации этих изменений необходима динамическая или адаптивная маршрутизация потоков данных в нестационарных ТКС.
Изменения (перегрузки) шестого и седьмого типов требуют адаптивной маршрутизации с обратной связью о текущем состоянии каналов связи и буферов узлов ТКС, обеспечивающей обход “запретных” (перегруженных) каналов и узлов.
Наконец, мульти-агентная постановка задачи требует разработки методов статической, динамической и адаптивной маршрутизации в условиях много-адресной передачи и коллективного использования ТКС, когда число внешних агентов-клиентов ТКС и количество их запросов может непредсказуемо изменяться с течением времени. В этом случае могут возникать сетевые перегрузки и конфликты, для предотвращения или разрешения которых нужны специальные алгоритмы и средства их реализации [29–34].
Предлагаемые методы решения указанных задач основываются как на развитии традиционных подходов к планированию и оптимизации маршрутов передачи пакетов данных в глобальных ТКС, так и на разработке адаптивных, нейросетевых и мульти-агентных маршрутизаторов нового поколения, обладающих высоким параллелизмом и быстродействием при обработке и передаче цифровой информации в реальном времени.
Аналогичным образом в статической, динамической, адаптивной и мульти-агентной постановке могут ставиться и решаться задачи управления передачей потоков данных по ранее спланированным маршрутам с учетом динамических особенностей и неопределенности трафика в ТКС [38–45].