Содержание к диссертации
Введение 4
Алгоритмы распределения нагрузки 5
Известные аналитические результаты 10
Анализ существующих моделей 18
Экспериментальные данные 19
Модель и методы исследования 25
Результаты, полученные в диссертационной работе 27
Структура работы 27
1 Система с динамической маршрутизацией и степенным законом рас
пределения времени обслуживания заявок 29
Введение , . 29
Модель и предварительные результаты 30
Доказательство полученных результатов 35
Заключение 49
Приложение: доказательство вспомогательных лемм 52
2 Система с динамической маршрутизацией и Вейбулловским законом
распределения времени обслуживания заявок 58
Введение 58
Модель и предварительные результаты 59
Доказательство полученных результатов 63
Заключение 74
Приложение: доказательство вспомогательных лемм 78
Заключение 85
Список иллюстраций
Среднее время обслуживания заявок в сервис-кластере с различными алгоритмами динамической маршрутизации 9
(а) Распределение времени обслуживания процессов с длительностью, превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая - приближению функцией rTk , полученному методом наименьших квадратов.(Ь) Тоже самое распределение в логарифмическом масштабе. Прямая линия покапывает приближение гТ*, где А: угол наклона графика 23
В логарифмическом масштабе показаны: толстой линией наблюдаемое распределение времени обслуживания процесса(исследовано более 13000 процессов), и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе. Рг{х > Т) ~ гхк, второе об [непринятой Рг(х > Т) ~ се~хт 24
Блок-схема модели системы обслуживания 30
Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К , 50
G Вероятность переполнения системы в зависимости от величины выбор
ки К" в случае, когда Эп < К : р > N — п 51
Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К 75
Вероятность переполнения системы в зависимости от исличинм выборки К в случае, когда существует решение оптимизационной задачи и
р> N -К 76
9 Эмпирическая плотность распределения вероятностей времени между
установлениями TCP/IP соединений во внешнем сегменте сети AT&T
18 Ноября-8 Декабря 1995 90
10 Эмпирическое дополнительное распределения вероятностей времени
между установлениями TCP/IP соединений и приближения, получен
ные методов наименьших квадратов, во внешнем сегменте сети AT&T
18 Ноября-8 Декабря 1995 91
Введение к работе
В любой системе обслуживания, состоящей из нескольких обслуживающих приборов, естественным образом возникает задача распределения поступающей нагрузки, с целью эффективного использования имеющихся ресурсов. Существует ряд методов решения этой задачи, одним из которых яилястся динамическая маршрутизация. Алгоритмы динамической маршрутизации распределяют поступающие в систему запросы, опираясь на текущие характеристики загруженности обслуживающих приборок, в соответствии с избранным способом маршрутизации. Выбор способа маршрутизации зависит от специфики решаемой задачи. Например, is случае, когда необходимо обеспечить минимальное время нахождения запросов в системе, способ маршрутизации может заключаться в том, чтобы при поступлении запроса в систему направлять его в обслуживающий прибор с очередью наименьшей длины. В другом случае, когда необходимо чтобы в системе всегда оставалось несколько достаточно свободных очередей, например для быстрого обслуживания приоритетных запросов, может лучше подходить способ маршрутизации в очередь средней длины. Другим важным параметром алгоритмов динамической маршрутизации является сложность их реализации. Очевидно, что чем больше масштаб системы, тем сложнее при маршрутизации учитывать текущее состояние всех обслуживающих приборов, поэтому часто используют упрощенные алгоритмы балансировки нагрузкой. Как правило, динамическая маршрутизация в них производится на основании текущих характеристик некоторого небольшого подмножества множества всех обслуживающих приборов системы. Подмножество обычно выбирается случайно, каждый раз при поступлении
новой заявки. Как показывают эмпирические исследования и теоретический анализ, такие упрощенные алгоритмы являются эффективными и ,в ряде случаев, не на много уступают более сложному, с выбором на основании характеристик всей системы. Несмотря на то, что существует довольно развитый аналитический аппарат исследования систем, балансирующих нагрузку, тенденции развития современной техники и архитектуры сетей передачи данных, делают все более актуальным и необходимым проведение новых исследований таких систем. Существующие модели систем с динамической маршрутизацией, в ряде случаев, уже не отражают новые статистические закономерности, обнаруженные па практике, а методы исследования трудно расширить на новые модели. Поэтому необходимо разработать как новую модель, так и новые методы исследования систем, отражающие обнаруженные закономерности. Для пояснения сложившейся ситуации, приведем ниже описание существующих моделей систем с динамической маргарутизацей, кратко изложим полученные ранее аналитические результаты, а затем перечислим ряд систем и обнаруженные в них статистические закономерности, не вписывающиеся в существующую теорию.
