Введение
1. Описание задач планирования вычислений в распределенных системах реального времени 12
1.1. Задача планирования вычислений в распределенных системах 12
1.2. Задача планирования вычислений в ЦОД с моделью обслуживания IaaS 13
1.2.1. Постановка задачи 14
1.3. Задача построения сетей AFDX
1.3.1. Описание сетей AFDX 17
1.3.2. Постановка задачи 20
1.4. Выводы 23
2. Обзор различных подходов к построению алгоритмов решения близких задач 25
2.1. Подходы к решению задачи отображения запросов в ЦОД 26
2.2. Упаковка в контейнеры 29
2.3. Построение маршрутов виртуальных каналов 32
2.4. Подходы к проектированию сетей AFDX 34
2.5. Вычисление оценки длительности передачи сообщений в сетях AFDX 36
2.6. Выводы 37
3. Алгоритм планирования вычислений в ЦОД с моделью обслуживания IaaS 39
3.1. Общая схема алгоритма 39
3.2. Назначение виртуальных машин и storage-элементов
3.2.1. Процедура ограниченного перебора 40
3.2.2. Жадные критерии 42
3.3. Построение маршрутов виртуальных каналов 44
3.3.1. Общая схема процедуры построения маршрутов виртуальных каналов 44
3.3.2. Жадные критерии 45
3.3.3. Построение маршрута для одного виртуального канала 45
3.3.4. Процедура ограниченного перебора 46
3.3.5. Процедура репликации 47
3.4. Свойства и теоретическое обоснование алгоритмов 47
3.4.1. Оценка сложности этапов алгоритма 47
3.4.2. Зависимость сложности алгоритма от глубины ограниченного перебора 49
3.4.3. Корректность алгоритма 51
3.4.4. Свойства процедуры ограниченного перебора при решении задачи упаковки в контейнеры 52
3.4.5. Свойства процедуры ограниченного перебора при построении маршрутов виртуальных каналов 54
3.4.6. Достаточные условия оптимальности алгоритма планирования вычислений в ЦОД 55
3.5. Выводы 59
4. Алгоритм построения сетей AFDX 60
4.1. Общая схема алгоритма 60
4.2. Описание процедур, используемых в алгоритме
4.2.1. Настройка параметров виртуальных каналов 61
4.2.2. Процедура агрегации 64
4.2.3. Построение маршрутов виртуальных каналов. 68
4.2.4. Процедура ограниченного перебора виртуальных каналов 70
4.2.5. Вычисление максимальной длительности и джиттера передачи сообщений. 70
4.2.6. Процедура переконфигурации виртуального канала. 72
4.3. Свойства алгоритмов и теоретическое обоснование 73
4.3.1. Оценка сложности этапов алгоритма 73
4.3.2. Корректность 77
4.3.3. Свойства процедуры ограниченного перебора при поиске маршрутов виртуальных каналов 78
4.3.4. Оценка точности процедуры построения маршрутов виртуальных каналов
4.3.5. Достаточные условия оптимальности алгоритма построения сетей AFDX 80
4.3.6. Выводы 83
5. Экспериментальное исследование свойств алгоритмов 85
5.1. Методика проведения экспериментального исследования 85
5.2. Экспериментальные исследования для алгоритма планирования вычислений в ЦОД
5.2.1. Схема проведения экспериментов 86
5.2.2. Исследование используемых эвристик 87
5.2.3. Исследование точности алгоритма 92
5.2.4. Зависимость от метода выбора физического ресурса 94
5.2.5. Исследование процедуры репликации 96
5.2.6. Выводы 97
5.3. Экспериментальные исследования для задачи построения сетей AFDX 97
5.3.1. Схема проведения экспериментов 97
5.3.2. Эффективность использования процедур алгоритма 98
5.3.3. Исследование процедуры агрегации 100
5.3.4. Исследование работы алгоритма в случае высоких требований к длительности передачи сообщений 102
5.3.5. Выводы 104
6. Инструментальная система построения сетей AFDX 106
6.1. Требования к системе 106
6.2. Описание системы 107
6.2.1. Пользовательский интерфейс 107
6.2.2. Модуль построения виртуальных каналов 108
6.3. Выводы 110
Заключение 111
Литература 113
