Содержание к диссертации
Введение
РАЗДЕЛ I. АНАЛИЗ МЕТОДОВ УПРАВЛЕНИЯ В БС РСТД И ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 9
1.1. Используемые объекты и предположения . 10
1.2. Оптимальная маршрутизация: формальная постановка задачи 17
1.3. Оптимальная маршрутизация: анализ методов решения 19
1.4. Структурная устойчивость оптимального управления 27
Заключение 36
РАЗДЕЛ 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ДИНАМИКО-СТАТЕСТИЧЕСКОЙ МАРШРУТИЗАЦИИ 38
2.1. Динамика маршрутных потоков для пары источник-адресат 39
2.2. Примеры вычисления точек бифуркации и обобщение результатов 49
2.3. Взаимодействие потоков и катастрофы . 57
2.4. Переходные процессы при взаимодействии потоков ; 71
2.5. Формальное описание методов ДСМ 90
Заключение 102
РАЗДЕЛ 3. АЛГОРИТМЫ ДИНАМИКО-СТАТЕСТИЧЕСКОЙ МАРПРУТИЗАЦИИ . 105
3.1. Исходные предпосылки 106
3.2. Алгоритм ДСМ-І III
3.3. Алгоритм ДСМ-2 120
3.4. Некоторые свойства алгоритмов ДСМ-I,ДСМ-2 . 125
Заключение 129
РАЗДЕЛ 4. ИМИТАЦИОННЫЕ МОДЕЛИ И РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ 131
4.1. Описание данных и общая структура моделей . 132
4.2. Результаты моделирования 138
4.3. Оценки алгоритмов ДОМ, полученные на моделях 167
Заключение 176
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 178
ЛИТЕРАТУРА 181
СПИСОК СОКРАЩЕНИЙ 192
ПРИЛОЖЕНИЕ I 193
ПРИЛОЖЕНИЕ II 221
- Используемые объекты и предположения .
- Динамика маршрутных потоков для пары источник-адресат
- Исходные предпосылки
- Описание данных и общая структура моделей
Используемые объекты и предположения .
По сравнению с традиционными сетевыми моделями /60,61,63, 64,81/ анализ коммуникационных подсистем РСТД осложняется стохастическим и дискретным характером входных потоков сообщений и/или пакетов. В настоящее время известны модели БС, учитывающие эти оба обстоятельства, но, из-за чрезвычайной сложности их анализа, такие модели имеют только теоретический интерес /101/. Наиболее содержательные и важные с практической точки зрения результату получены с использованием ряда упрощающих предположений. Явно, как в работе /104/,или неявно, как в большинстве других работ, суть вводимых предположений заключается в том, что реальные информационные потоки в БС заменяются усредненными непрерывными потоками в смысле Форда-Зшш ер с она /61/. Наиболее полно вопрос о допустимости и последствиях введения упрощающих предположений исследуется в работах Л.Клейнрока (см., например, /33,36,95/). Вводимые предположения не всегда соответствуют физическим процессам в реальных сетях (скажем "предположение о независимости"). Однако результаты, полученные в этих предположениях, достаточно точно описывают поведение сети, что подтверждается результатами моделирования и измерениями на реальных сетях. Предположения, используемые в данной работе, являются общепринятыми, поэтому приводятся ниже без обсуждения.
1. Потоки на входах сети описываются независимыми пуассоновскими процессами.
2. Выполняется предположение Клейнрока о независимости длин сообщений.
3. Каждая линия связи моделируется системой массового обслуживания (СМО) типа M/M/I.
4. Источниками задержки в сети являются только линии связи, задержка в которых является неубывающей функцией интенсивности потока.
5. Все элементы сети абсолютно надежны, шумы в каналах связи отсутствуют.
Указанные предположения накладывают весьма жесткие ограничения на класс исследуемых сетей. Однако в ряде случаев эти преположения можно существенно ослабить и доказать справедливость полученных результатов для более широкого класса сетей, чем экспоненциальные. Возможность таких обобщений в работе указывается особо.
Динамика маршрутных потоков для пары источник-адресат
Сложность анализа динамики оптимальных распределений при изменении нескольких входных потоков заключается в том, что для большинства АП в соответствующие множества PH(s,d) входит некоторое число общих дуг. Это означает взаимное влияние распределений потоков различных АП друг на друга, которое существенно усложняет оценку свойств алгоритма маршрутизации.
Для исследования динамики маршрутных потоков одной АП не обязательно отсутствие всех остальных потоков. Достаточно предположить, что все входные потоки, кроме Ascf , стационарны и на их распределение не влияет интенсивность потока jlS(j . Тогда в установившемся режиме для потока Aso/ сеть будет представляться множеством путей PH(std), образованным из дуг графа G с пропускными способностями 21=с1- , где / - линейный поток в дуге Єї , вычисленный без учета маршрутных потоков tfsef . Приняв в качестве пропускных способностей дуг величины г , можно анализировать распределение Xsoi без учета остальных потоков.
Исходные предпосылки
Непосредственная реализация обобщенного алгоритма ДСМ предполагает, что в каждом узле БС хранится перечень маршрутов от данного узла до всех остальных. Число маршрутов для сетей средней связности очень быстро растет с увеличением числа УК, что создает трудности формирования и хранения маршрутных таблиц. Вторым недостатком маршрутизации по путям доставки является необходимость обмена СИ между УК по принципу "каждый с каждым". Объем СИ и время ее доставки оказываются весьма значительными даже для БС, содержащих несколько десятков УК.
Несмотря на большое число возможных путей доставки для АЛ (s,cf) все они содержат одну из дуг, выходящих из узла-источника S . В разделе 2 показано, что дифференциальная длина пути Psc[ существенно зависит от его длины в единичной метрике. Поэтому пути, имеющие большое число переприемов используются при оптимальном распределении потоков только в области высоких нагрузок. Однако естественно предположить, что общая нагрузка на сеть распределяется по ее входам более или менее равномерно. Тогда с ростом нагрузки в линейном потоке каждой дуги все большая доля будет приходиться на маршрутный поток tpS(/ , где d - узел, соседний с S . Общая доля транзитных потоков в БС, использующей ДСМ, уменьшается с ростом нагрузки, а средняя длина пути стремится к единице. Здесь /,. -Ж. 4й - сумма линейных потоков сумма входных потоков.
Из сказанного выше следует, что: а) в области малых нагрузок оптимальное распределение использует только пути с малым числом переприемов, б) в случае сбалансированной нагрузки также используются в основном пути с малым числом переприемов, в) одновременно использовать все пути из множества РЦ($,с1) могут только несколько АП при условии, что интенсивности входных потоков этих АП близки к предельно допустимым и попарные пересечения множеств активных путей пусты.
Таким образом, учитывая, что все пути любой АП (s,d) содержат одну из инцидентных узлу S дуг, оптимальное распределение входных потоков с учетом только исходящих линий дает хорошее приближение к оптимальному распределению потоков с учетом всех возможных путей доставки. Последующие итерации, неизбежные и при маршрутизации по множеству путей, приводят к полному совпадению оптимальных распределений.
Переход от наглядного и простого в постановочном плане способа маршрутизации по множеству путей доставки к маршрутизации по исходящим линиям дает два очевидных преимущества при построении алгоритмов управления потоками. Во-первых, резко сокращается объем служебных таблиц и объем СИ, т.к. информация собирается и хранится только о состоянии соседних узлов. Во-вторых, сокращается объем и время вычислений на каждой итерации распределения потоков. Причина такого сокращения в переходе от распределения потоков по нескольким десяткам путей доставки к распределению по нескольким (не более 4-6) выходным линиям.
Недостаток способа распределения потоков по исходящим линиям проявляется в том, что для формирования оптимального распределения потоков в случае значительного "перекоса" в входного трафика требуется несколько итераций. В общем случае число итераций зависит от величины кратчайшего в единичной метрике пути между источником и адресатом перегруженного направления.
Описание данных и общая структура моделей
Имитация функционирования алгоритмов ДСМ-І, ДСМ-2 заключается в поочередном выполнении действий, предписываемых алгоритмом, для каждого из узлов моделируемой БС. При этом, естественно, не имеет смысла хранить полный набор служебных таблиц для каждого УК в отдельности. Каждый УК хранит информацию о текущем состоянии соседних узлов. Поэтому формирование отдельных для каждого УК таблиц со служебной информацией привело бы к дополнительным затратам памяти на хранение дубликатов. Кроме того, при изменении состояния одного из узлов пришлось бы корректировать таблицы всех соседних узлов, что требует дополнительного времени на реализацию модели.
Поэтому в моделирующих программах используются служебные таблицы, описывающие всю БС в целом. Но при реализации алгоритмов маршрутизации каждому из узлов доступна только информация о состоянии соседних с ним узлов.
Способ организации и состав информационных массивов во многом определяет структуру моделирующей программы и удобство в работе с ней. В рассматриваемой модели выделяются данные четырех типов:
- скаляры, определяющие параметры БС в целом;
- массив параметров УК;
- массив параметров линий связи;
- массивы данных, ассоциируемых одновременно и с линией связи, и с некоторым УК.
В таблице 4.1 приведен перечень идентификаторов и описание назначения основных объектов моделирующей программы. Тип переменных (вещественный, целый) определяется по умолчанию в соответствии с правилами языка программирования FORTRAN
Число узлов /I/ и число линий М определяют размерность информационных массивов модели. Предполагается, что все узлы БС пронумерованы в произвольном порядке целыми числами от I до /К . Явная нумерация линий связи не производится. Эквивалентом номера линии является номер строки, отводимой данной линии в информационных массивах. Напомним, что граф сети предполагается неориентированным, т.е. если существует дуга (LA) , то всегда существует и дуга (J, I) , называемая обратной по отношению к дуге (»J) . Емкости прямой и обратной дуг в общем случае различны.
Линии связи БС описываются с помощью двух матриц размерностью М Ъ : матрицы топологических характеристик /I/OML и матрицы PARLIfi/ , содержащие данные о текущей загрузке линии. При формировании этих матриц требуется выполнение одного ограничения: параметры линий, исходящих из одного УК, должны располагаться в последовательных строках матриц.
Похожие диссертации на Разработка методов и алгоритмов адаптивного управления базовой сети распределенных систем телеобработки
