- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •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.5. Расширение карт маршрутизации и интенсивность потоков данных
Рассмотрим очень важное свойство матриц вида (4.4.2) для корректных СРКМ.
Зафиксируем узел-получатель и запустим из каждого узла в aj поток с соответствующей интенсивностью xi. Из (4.3.3) и (4.4.4) следует, что для того, чтобы определить, с какой интенсивностью совокупность этих потоков проходит через узлы ТКС, достаточно рассмотреть соответствующие элементы следующего вектора “интенсивностей”:
. (4.5.1)
Рассмотрим обычные РТМ и РКМ. Расширим РТМ и РКМ согласно (4.4.1) в следующем виде:
, (4.5.2)
. (4.5.3)
Назовем расширением карты маршрутизации T. Заметим, что такое расширение РКМ не приведет к изменению в распределении информационных потоков в ТКС.
Рассмотрим узлы и зафиксируем узел-получатель . Будем говорить, что узел ak доминирует над узлом ai по отношению к узлу aj (в контексте карты маршрутизации T), если при управлении потоками данных, задаваемом РКМ T, существует такая совокупность потоков данных, при которой поток данных, направленный к узлу-получателю aj узлом ak, будет протекать через узел ai. Обозначим это отношение доминирования соотношением
. (4.5.4)
Заметим, что отношение доминирования не транзитивно, т.е. из соотношений
(4.5.5)
не следует, что
. (4.5.6)
В качестве примера рассмотрим граф, соответствующий некоторой ТКС, приведенный на рисунке 4.5.1. Пусть для него задана РКМ T. Рассмотрим таблицы маршрутизации из её расширения для узла-получателя a5=f
Пусть эти таблицы заданы следующим образом:
(4.5.7)
Из (4.5.7) видно, что
и . (4.5.8)
Однако при этом
. (4.5.9)
Будем говорить, что узел ak транзитивно доминирует над узлом ai по отношению к узлу aj (в контексте карты маршрутизации T), если существует последовательность узлов вида
, (4.5.10)
такая, что , , и для любых справедливо соотношение
. (4.5.11)
Обозначим такой тип доминирования следующим образом:
. (4.5.12)
Рассмотрим несколько свойств, связанных с отношениями доминирования и транзитивного доминирования узлов ТКС.
Лемма 4.5.1: Пусть задан орграф G(A,W,R), соответствующий некоторой ТКС, и на нем определена корректная РКМ T и её расширение . Тогда для любого узла-получателя и пары отличных от него узлов справедлива импликация вида:
если , то . (4.5.13)
Докажем утверждение Леммы 4.5.1. Пусть доминирование узла ak над узлом ai проявляется при интенсивности потока xk в ak и xi в ai (будем рассматривать только этот один поток, направленный от ak к aj и проходящий через ai, для которого xi≤xk. Тогда такое доминирование будет проявляться при любой интенсивности x>xi. в узле ai Это происходит в силу того, что всегда можно создать поток данных, направленный от ai к aj. Заметим, что любой поток от узла ai к узлу-получателю aj с интенсивностью x≥xi не может проходить через узел ak, поскольку в этом случае появился бы циклический маршрут, что соответствовало бы существованию бесконечного маршрута и противоречило бы условию корректности РКМ.
Теперь докажем, что любой поток от узла ai к узлу aj с интенсивностью x<xi не будет проходить через узел ak. Действительно, если это не так, то такой поток с интенсивностью меньшей, чем xi, будет протекать через ak с интенсивностью, не превосходящей xi, и, следовательно, не превосходящей xk. Тогда можно создать новый поток от ak к aj с такой интенсивностью, чтобы суммарная интенсивность потоков на узле ak была равна xk. Оба эти потока будут проходить через ai, что приведет к появлению циклических, а, значит, бесконечных маршрутов, что противоречит условию корректности РКМ. Таким образом, поток любой интенсивности, направленный от узла ai к узлу aj через ak протекать не может, и, следовательно,
. (4.5.14)
Лемма 4.5.1. доказана. Из неё вытекает следующее следствие.
Следствие 4.5.1: В условиях леммы 4.5.1 для любого узла , отличного от узла-получателя, справедливо следующее соотношение:
. (4.5.15)
Лемма 4.5.2: Пусть выполнены условия леммы 4.5.1, задан узел-получатель и существуют три узла такие, что
, а (т.е., ). (4.5.16)
Рассмотрим потоки, направленные к узлу-получателю от узлов ai и ak. Пусть максимальная интенсивность таких потоков от ak, при которой они будут протекать через узел am, равна xk (если верхнего ограничения нет, то полагаем, что xk = ∞), а минимальная положительная интенсивность, с которой проходят через ak потоки от ai равна xi (если минимума нет, то в качестве значения xi принимаем инфимум положительных значений). Тогда, следующие утверждения равносильны:
-
xi ≤ xk., (4.5.17)
-
. (4.5.18)
Докажем, что из первого утверждения следует второе. Из леммы 4.5.1 следует, что
и . (4.5.19)
Запустим от узла ai поток к узлу-получателю aj, который будет протекать через ak с интенсивностью xi или, если xi=0, с любой интенсивностью меньшей, чем xk (далее под xi будем подразумевать эту интенсивность). Из узла ak запустим поток к aj с интенсивностью (xk – xi). Тогда интенсивность суммарного потока, протекающего через узел ak, будет равна xk, и этот поток будет проходить через am, минуя ai и не возвращаясь в ak, так как
и . (4.5.20)
Таким образом, справедливо второе утверждение леммы 4.5.2.
Следствие первого утверждения из второго очевидно.
Лемма 4.5.2. доказана.
Лемма 4.5.3: В условиях леммы 4.5.1 справедливо следующее утверждение: любой узел , выбранный при фиксированном узле-получателе , не может транзитивно доминировать сам над собой, т.е.
. (4.5.21)
Докажем эту лемму методом от противного. Пусть существует такой узел , для которого имеется циклическая последовательность узлов , доминирующих друг над другом, т.е.
. (4.5.22)
В соответствии со следствием 4.5.1 из леммы 4.5.2 без потери общности можно считать, что элементы этой последовательности обладают следующим свойством:
. (4.5.23)
Рассмотрим три подряд идущих узла данной последовательности . Пусть максимальная интенсивность потоков от узла к узлу-получателю, при которой он будет протекать через узел , равна (если верхнего ограничения нет, то полагаем, что ), а минимальная положительная интенсивность, с которой через узел проходят потоки от равна (если минимума нет, то в качестве значения принимаем инфимум положительных значений). Тогда из леммы 4.5.2 следует, что . В то же время, нетрудно убедиться, что .
Таким образом, справедлива следующая цепочка соотношений:
. (4.5.24)
откуда следует, что . Получили противоречие, из которого следует справедливость леммы 4.4.3.
Следствие 4.5.2: В условиях леммы 4.5.1 при фиксированном узле-получателе существует отличный от него узел такой, что для любого узла , отличного от aj и ai, справедливо сочетание
. (4.5.25)
Иными словами, согласно следствию 4.5.2 для любого узла-получателя существует отличный от него узел такой, что при любой интенсивности x>0 справедливо уравнение
. (4.5.26)
Доказательство этого следствия поведем методом от противного. Предположим, что такого узла нет. Тогда существует узел-получатель такой, что для любого отличного от него узла существует узел такой, что
. (4.5.27)
Тогда можно построить последовательность вида (4.5.22) со свойством (4.5.23). Но из леммы 4.5.3 следует, что такой последовательности не существует. Поэтому сделанное предположение неверно, что доказывает справедливость следствия 4.5.2.
Следствие 4.5.3: В условиях леммы 4.5.1 при фиксированном узле-получателе справедливо следующее утверждение: если узел транзитивно доминирует над узлом , то ai не может доминировать над ak, т.е.,
. (4.5.28)
Утверждение следствия 4.5.3 очевидно, так как в противном случае узел ak транзитивно доминировал бы над самим собой, что противоречит утверждению леммы 4.5.3.
Зафиксируем узел-получатель . Построим для него матрицу доминирования (j). Рассмотрим расширение РКМ T. Каждой расширенной РТМ сопоставим вектор с компонентами
(4.5.29)
Тогда матрица доминирования будет выглядеть следующим образом:
. (4.5.30)
Рассмотрим связь матрицы доминирования с отношениями доминирования узлов ТКС в форме импликации вида:
. (4.5.31)
Из соотношения (4.5.31) следует эквивалентность следующих соотношений
. (4.5.32)
Критерий корректности для РКМ можно сформулировать в виде следующей теоремы.
Теорема 4.5.5: Распределяющая карта маршрутизации T корректна тогда и только тогда, когда для любого узла-получателя верно, что его матрица доминирования (j) удовлетворяет следующему требованию:
(4.5.33)
Докажем сначала необходимость. Пусть РКМ корректна. Зафиксируем узел-получатель . Предположим, что существует число k такое, что
. (4.5.34)
Тогда из (4.5.34) следует, что
, (4.5.35)
а это противоречит утверждению леммы 4.5.3.
Теперь докажем достаточность. Рассмотрим РКМ. Так как все прокладываемые этой картой маршруты будут заканчиваться в узле-получателе aj, то нам остается доказать, что все определяемые РКМ маршруты будут конечнозвенными.
Предположим, что РКМ некорректна. Тогда будут существовать бесконечные маршруты, т.е., маршруты, содержащие циклы. В этом случае будут существовать узлы, транзитивно доминирующие сами над собой. Но из (4.5.33) в силу (4.5.32) следует, что для любой узел не может транзитивно доминировать сам над собой, т.е.
. (4.5.36)
Полученное противоречие доказывает корректность РКМ и справедливость теоремы 4.5.5.