Методы исследования систем массового обслуживания с динамической маршрутизацией

• Автор: Аленичев, Алексей Вячеславович
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

Введение

Алгоритмы распределения нагрузки

Известные аналитические результаты.

Анализ существующих моделей

Экспериментальные данные.

Модель и методы исследования.

Результаты, полученные в диссертационной работе

Структура работы.

1 Система с динамической маршрутизацией и степенным законом распределения времени обслуживания заявок

1.1 Введение.

1.2 Модель и предварительные результаты

1.3 Доказательство полученных результатов
1.4 Заключение.
1.5 Приложение доказательство вспомогательных лемм
2 Система с динамической маршрутизацией и Всйбулловским законом распределения времени обслуживания заявок
2.1 Введение.
2.2 Модель и предварительные результаты
2.3 Доказательство полученных результатов
2.4 Заключение.
2.5 Приложение доказательство вспомогательных лемм
Заключение
Список иллюстраций
1 Среднее время обслуживания заявок в сервискластере с различными
алгоритмами динамической маршрутизации
2 а Распределение времени обслуживания процессов с длительностью,
превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая приближению функцией гТк , полученному методом наименьших квадратов.Ь Тоже самое распределение в логарифмическом масштабе. Прямая линия показывает приближение гТк, где к угол наклона графика
3 логарифмическом масштабе показаны толстой линией наблю
даемое распределение времени обслуживания процоссаисследовано болсс 0 процессов, и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе x Т , второе общепринятой x Т ссхт
4 Блоксхема модели системы обслуживания
о Вероятность переполнения системы в зависимости от величины выборки К в случае р К
Вероятность переполнения системы в зависимости от величины выборки К в случае, когда 3 п К р п
7 Вероятность переполнения системы в зависимости от величины выборки К и случае р К
8 Вероятность переполнения системы в зависимости от величины выборки К в случае, когда существует решение оптимизационной задачи и
р К
9 Эмпирическая плотность распределения вероятностей времени между установлениями I соединений во внешнем сегменте сети
Ноября8 Декабря .
Эмпирическое дополнительное распределения вероятностей времени между установлениями I соединений и приближения, полученные методов наименьших квадратов, во внешнем сегменте сети
Ноября8 Декабря .
Введение


Заметим, что варьируя количество случайно выбираемых приборов, можно гибко настраивать систему по сложности реализации и эффективности. Анализируя приведенное выше описание алгоритмов, можно заключить, что первый предложенный алгоритм подходит для применения в небольших централизованных системах и обладает наибольшей эффективностью. Второй алгоритм, прост в реализации, по недостаточно эффективен, область его применения большие распределенные системы с невысокими требованиями к качеству обслуживания. Третий предложенный алгоритм является оптимальным по сложности и эффективности и подходит для применения в различных системах. Наряду с рассмотренными выше алгоритмами маршрутизации, существуют и другие методы распределении нагрузки, в которых, учитываются специфические требования, возникающие в реальных системах. Так, в некоторых случаях, предоставление заявке возможности выбирать один из нескольких доступных ресурсов может быть экономически НС выгодным. С целью избежать этого, в пороговом алгоритме при поступлении заявки в систему случайно выбирается одна очередь, и, если ее длина не превышает некоторого порогового значения, заявка направляется в эту очередь, иначе, случайно выбирается другая очередь, и заявка направляется в нес. Существует вариант поро ового алгоритма, в котором заявка, после неудачного выбора первой очереди и последующего выбора второй, поступает в минимальную из них. Кроме того, разработаны методы маршрутизации, которые описывают системы с приоритетами. Типичным предположением для таких алгоритмов является то, что с вероятность р в систему приходят обычные заявки, а с вероятностью 1 р приоритетные. При этом, считается, что приоритетные заявки имеют право выбора минимальной очереди, а обычные просто направляются в случайно выбранный обслуживающий прибор. Исходя из рассуждений, приведенных выше, можно заключить, что метод маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей системы является эффективным для широкою круга систем, не требует больших вычислительных затрат и, поэтому, часто применяется па практике. Эмпирические исследования систем с динамической маршрутизацией подтверждают сделанный нами вывод. В качестве примера приведем результаты эмпирических исследований проведенных в работе . В ходе экспериментов авторы работы производили сравнение эффективности алгоритмов динамической маршрутизации в условиях современного кластера обслуживания. Эмитацноипоо моделирование производилось на основании статистики трафика, записанного в течении недели в июле года в двух внутренних кластерах обслуживания поисковой системы Теота . Один кластер системы отвечал за перевод запрашеваемых пользователем слов во внутреннее представление системы. Другой, за аналогичный перевод описания страниц. В результате исследований трафика, авторы выяснили, что входной поток первого кластера, далее Трафик 1, имеет среднее время обслуживания мс, а поток второго, называемый далее Трафик 2, 8,9 мс. В ходе эмитационного моделирования записанный поток подавался на систему из 1 серверов через коммутатор Р0 с полосой пропускания Гбитс. Распределение поступающих запросов между серверами производилось в соответствии с различными алгоритмами динамической маршрутизации, балансирующей нагрузку. Авторы сравнивали следующие, рассмотренные нами выше, алгоритмы динамическая маршрутизации со случайным выбором очереди , маршрутизация с выбором минимальной из i к случайных очередей, и маршрутизации с выбором минимальной во всей системе очереди i. Исследования проводились для трех различных входных потоков Трафика 1, Трафика 2 и искусственного ПуассоиЭксн. Пуассона, время обслуживания заявки имеет экспоненциальное распределение со средним . Результаты эмитационного моделирования приведены на Рис. Но оси абсцисс отложен уровень загрузки сервера, по оси ординат среднее время обслуживания заявок. Метод выбора минимальной очереди из случайного подмножества всех очередей системы i к значительно превосходит простой метод, когда задача поступает в очередь на обслуживание случайно выбранного сервсрагапбот.