- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •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.2. Постановка задачи оптимальной статической маршрутизации
Рассмотрим классическую постановку задачи статической маршрутизации в ТКС с фиксированной (неизменной) динамикой.
Каждому ребру ri R (т.е. односторонней или двусторонней связи) графовой модели ТКС вида (1.1.1) поставим в соответствие действительное число wi0 и назовём его весом ребра (связи). В конкретных ТКС это число может быть мерой геометрического расстояния между узлами ТКС, времени прохождения данных между соответствующими узлами, стоимости канала связи или другого важного коммуникационного параметра. В случае ТКС с двусторонними связями величина веса ребра может быть, вообще говоря, различной в зависимости от направления передачи данных по соответствующему каналу связи.
Будем считать, что вес ребра (канала связи) графовой модели ТКС обладает следующими свойством аддитивности:
(2.2.1)
В этом случае вес совокупности рёбер графа ТКС, образующих маршрут, равен сумме весов отдельных рёбер.
Величина (2.2.1) может использоваться в качестве критерия оптимальности (целевой функции) маршрута в ТКС при определённых ограничениях на допустимые множества вершин (узлов) ТКС и рёбер (каналов связи) между ними.
Пусть задан ориентированный граф ТКС такой, что между любыми его вершинами (узлами) a1 и ak+1, называемыми соответственно начальным узлом a1=s и конечным узлом ak+1=f , существует, по крайней мере, один связывающий их маршрут передачи данных. Тогда задача поиска оптимального маршрута заключается в нахождении маршрута
P= {r1, r2,…., rk }, (2.2.2)
имеющего минимальный суммарный вес (2.1.2) и удовлетворяющего заданным граничным условиям
a1 = s , ak+1=f .
Очевидно, что при классическом итеративном подходе в процессе решения этой задачи будут получены все кратчайшие маршруты, ведущие из узла a1=s в каждый промежуточный узел aa1 оптимального маршрута.
Таким образом, задача поиска оптимального маршрута передача пакетов данных в статических ТКС сводится к задаче нахождения маршрута из некоторого заданного начального узла a1=s в любой узел ak+1=f ТКС, достижимый из узла a1=s.
2.3. Модели и алгоритмы статической маршрутизации
2.3.1. Дерево кратчайших маршрутов для ткс с односторонними связями
Для решения задачи оптимальной статической маршрутизации на графовой модели ТКС с односторонними связями введём следующие понятия:
a) деревом кратчайших расстояний относительного начального узла a1=s будем называть ориентированное дерево с корнем s такое, что маршрут из s до любой вершины aявляется оптимальным;
b) максимальным деревом кратчайших расстояний T(s) относительно начального узла a1=s является дерево T(s), включающее в себя все узлы графа , достижимые из узла s.
Пусть T(s) - растущее дерево, содержащее все узлы aA графа , достижимые из начального узла s. Обозначим через w(s,a) вес ребра (канала связи) между узлами s и aT(s). Заметим, что
w(s,a) 0, w(s,s)= 0.
Дерево T(s) будет деревом кратчайчих расстояний, т.е. T(s)=, тогда и только тогда, когда
0w(s,a)w(s,b)+ w(a,b), aT(s),bT(s). (2.3.1)
Соотношение (2.3.1) является теоретической основой следующего рекуррентного алгоритма поиска оптимального маршрута:
1. Пусть T1(s) - любое дерево, содержащее все узлы, достижимые из узла s.
2. На i-ом шаге (i2) алгоритма находится дерево кратчайших расстояний , для которого справедливо соотношение (2.3.1). При этом к дереву добавляется ребро (a,b) и вычёркивается ребро (канал связи), ведущее к b.
3. На последнем шаге алгоритма определяется максимальное дерево кратчайших расстояний и соответствующий ему оптимальный маршрут.
В общем случае может быть найдено несколько оптимальных маршрутов. Если положить wi=w(ri)=1 для всех рёбер (каналов связи) riR , то будут найдены оптимальные маршруты, которые являются кратчайшими в том смысле, что они содержат наименьшее число рёбер (каналов связи) между начальным и конечным узлами ТКС с одностороними связями.
Данный алгоритм изначально строился для ТКС с односторонними связями, однако, в силу второго шага алгоритма он подходит и для ТКС со смешанными связями.