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

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

2.3 Доказательство полученных результатов.63.

2.4 Заключение.74.

2.5 Приложение: доказательство вспомогательных лемм.78.

Заключение

85.

Список иллюстраций.

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

2 (а) Распределение времени обслуживания процессов с длительностью, превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая — приближению функцией гТк, полученному методом наименьших квадратов.(Ь) Тоже самое распределение в логарифмическом масштабе. Прямая линия покалывает приближение rTfc, где к угол наклона графика. 23.

3 В логарифмическом масштабе показаны: толстой линией наблюдаемое распределение времени обслуживания процесса (исследовано более 13 000 процессов), и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе Pr (x > Т) ~ гхк, второе общепринятой Pr (x > Т) ~ се~АГ.24.

4 Блок-схема модели системы обслуживания. 30.

5 Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К. 50.

6 Вероятность переполнения системы в зависимости от величины выборки К в случае, когда Зп < К: р> N — п. 51.

7 Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К. 75.

8 Вероятность переполнения системы в зависимости от величины выборки К в случае, когда существует решение оптимизационной задачи и р> NК. 76.

9 Эмпирическая плотность распределения вероятностей времени между установлениями TCP/IP соединений во внешнем сегменте сети AT&T.

18 Ноября-8 Декабря 1995. 90.

10 Эмпирическое дополнительное распределения вероятностей времени между установлениями TCP/IP соединений и приближения, полученные методов наименьших квадратов, во внешнем сегменте сети AT&T.

18 Ноября-8 Декабря 1995. 91.

В любой системе обслуживания, состоящей из нескольких обслуживающих приборов, естественным образом возникает задача распределения поступающей нагрузки, с целью эффективного использования имеющихся ресурсов. Существует ряд методов решения этой задачи, одним из которых является динамическая маршрутизация. Алгоритмы динамической маршрутизации распределяют поступающие в систему запросы, опираясь на текущие характеристики загруженности обслуживающих приборов, в соответствии с избранным способом маршрутизации. Выбор способа маршрутизации зависит от специфики решаемой задачи. Например, в случае, когда необходимо обеспечить минимальное время нахождения запросов в системе, способ маршрутизации может заключаться в том, чтобы при поступлении запроса в систему направлять его в обслуживающий прибор с очередью наименьшей длины. В другом случае, когда необходимо чтобы в системе всегда оставалось несколько достаточно свободных очередей, например для быстрого обслуживания приоритетных запросов, может лучше подходить способ маршрутизации в очередь средней длины. Другим важным параметром алгоритмов динамической маршрутизации является сложность их реализации. Очевидно, что чем больше масштаб системы, тем сложнее при маршрутизации учитывать текущее состояние всех обслуживающих приборов, поэтому часто используют упрощенные алгоритмы балансировки нагрузкой. Как правило, динамическая маршрутизация в них производится на основании текущих характеристик некоторого небольшого подмножества множества всех обслуживающих приборов системы. Подмножество обычно выбирается случайно, каждый раз при поступлении новой заявки. Как показывают эмпирические исследования и теоретический анализ, такие упрощенные алгоритмы являются эффективными и, в ряде случаев, не па много уступают более сложному, с выбором на основании характеристик вссй системы. Несмотря на то, что существует довольно развитый аналитический аппарат исследования систем, балансирующих нагрузку, тенденции развития современной техники и архитектуры сетей передачи данных, делают все более актуальным и необходимым проведение новых исследований таких систем. Существующие модели систем с динамической маршрутизацией, в ряде случаев, уже не отражают новые статистические закономерности, обнаруженные на практике, а методы исследования трудно расширить на новые модели. Поэтому необходимо разработать как новую модель, так и новые методы исследования систем, отражающие обнаруженные закономерности. Для пояснения сложившейся ситуации, приведем ниже описание существующих моделей систем с динамической маршрутизацей, кратко изложим полученные ранее аналитические результаты, а затем перечислим ряд систем и обнаруженные в них статистические закономерности, не вписывающиеся в существующую теорию.

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

Для наглядности, рассмотрим вначале простой случай системы, балансирующей нагрузку, сформулируем задачу динамической маршрутизации и приведем ряд алгоритмов ее решения, а далее перечислим некоторые другие алгоритмы, используемые на практике в более сложных системах.

Предположим, что необходимо распределить поступающие в систему заявки между N обслуживающими приборами. При этом, все обслуживающие приборы однотипны, каждый из них может обрабатывать только одну заявку единовременно, заявка может обслуживаться только на одном приборе полностью, и другие приходящие заявки пс могут прервать выполнение текущей и становятся в очередь.

Задача: Необходимо построить алгоритм распределения заявок между приборами, эффективно использующий имеющиеся ресурсы и обладающий приемлемой сложностью реализации.

Методы решения:

• Если при поступлении в систему заявки, выбирать прибор с минимальной во всей системе очередью и направлять заявку в него, то среднее время нахождения в системе заявок будет минимально возможным. Однако, при увеличении количества приборов в системе, реализация этого алгоритма существенно затруднена и требует больших дополнительных усилий.

• Простейшим в реализации, будет алгоритм, когда заявка поступает в очередь на обслуживание случайно выбранного прибора. Интуитивно понятно, что для заявок с одинаковым временем обслуживания при достаточно большом К нагрузка будет равномерно распределяться между всеми обслуживающими приборами в системе. Недостаток этого алгоритма состоит в том, что он недостаточно эффективен для заявок с разным временем обслуживания.

• Компромиссным по сложности реализации и эффективности, выглядит алгоритм, в котором при поступлении заявки в систему, случайным образом выбирается некоторое подмножество всех обслуживающих приборов, внутри него находится прибор с минимальной очередью и заявка направляется в нее. Заметим, что варьируя количество случайно выбираемых приборов, можно гибко настраивать систему по сложности реализации и эффективности.

Анализируя приведенное выше описание алгоритмов, можно заключить, что первый предложенный алгоритм подходит для применения в небольших централизованных системах и обладает наибольшей эффективностью. Второй алгоритм, прост в реализации, но недостаточно эффективен, область его применения — большие распределенные системы с невысокими требованиями к качеству обслуживания. Третий предложенный алгоритм является оптимальным по сложности и эффективности и подходит для применения в различных системах.

Наряду с рассмотренными выше алгоритмами маршрутизации, существуют и другие методы распределения нагрузки, в которых, учитываются специфические требования, возникающие в реальных системах.

Так, в некоторых случаях, предоставление заявке возможности выбирать один из нескольких доступных ресурсов может быть экономически не выгодным. С целыо избежать этого, в пороговом алгоритме при поступлении заявки в систему случайно выбирается одна очередь, и, если ее длина не превышает некоторого порогового значения, заявка направляется в эту очередь, иначе, случайно выбирается другая очередь, и заявка направляется в нее. Существует вариант порогового алгоритма, в котором заявка, после неудачного выбора первой очереди и последующего выбора второй, поступает в минимальную из них.

Кроме того, разработаны методы маршрутизации, которые описывают системы с приоритетами. Типичным предположением для таких алгоритмов является то, что с вероятность р в систему приходят обычные заявки, а с вероятностью 1 — р приоритетные. При этом, считается, что приоритетные заявки имеют право выбора минимальной очереди, а обычные просто направляются в случайно выбранный обслуживающий прибор.

Исходя из рассуждений, приведенных выше, можно заключить, что метод маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей системы является эффективным для широкого круга систем, не требует больших вычислительных затрат и, поэтому, часто применяется на практике. Эмпирические исследования систем с динамической маршрутизацией подтверждают сделанный нами вывод.

В качестве примера приведем результаты эмпирических исследований проведенных в работе [52|. В ходе экспериментов авторы работы производили сравнение эффективности алгоритмов динамической маршрутизации в условиях современного кластера обслуживания. Под кластером обслуживания авторы подразумевали замкнутую подсеть, состоящую из различных серверов, подсоединенную к сети пользователей через высокоскоростной внешний интерфейс. Эмитациопное моделирование производилось на основании статистики трафика, записанного в течении недели в июле 2001 года в двух внутренних кластерах обслуживания поисковой системы Теота. Один кластер системы отвечал за перевод запрашеваемых пользователем слов во внутреннее представление системы. Другой, — за аналогичный перевод описания Web-страниц. В результате исследований трафика, авторы выяснили, что входной поток первого кластера, далее 'Трафик 1″, имеет среднее время обслуживания — 22 мс, а поток второго, называемый далее 'Трафик 2″ , — 208,9 мс. В ходе эмитационного моделирования записанный поток подавался на систему из 16 серверов через коммутатор Lucent Р550 с полосой пропускания 22Гбит/с. Распределение поступающих запросов между серверами производилось в соответствии с различными алгоритмами динамической маршрутизации, балансирующей нагрузку. Авторы сравнивали следующие, рассмотренные нами выше, алгоритмы: динамическая маршрутизации со случайным выбором очереди (random), маршрутизация с выбором минимальной из A-(polling к) случайных очередей, и маршрутизация с выбором минимальной во всей системе очереди (ideal). Исследования проводились для трех различных входных потоков: 'Трафика 1″, 'Трафика 2″ и искусственного Пуассон/Эксп. трафика, в ходе моделирования которого, полагалось, что количество поступающих в систему заявок в каждый момент времени имеет распределение Пуассона, время обслуживания заявки имеет экспоненциальное распределение со средним 50. Результаты эмитационного моделирования приведены на Рис. 1. По оси абсцисс отложен уровень загрузки сервера, по оси ординат среднее время обслуживания заявок.

Опираясь на полученные опытные данные, авторы сделали следующие выводы:

1. Метод выбора минимальной очереди из случайного подмножества всех очередей системы (polling к) значительно превосходит простой метод, когда задача поступает в очередь на обслуживание случайно выбранного cepBepa (random).

Трафик Пуассон/Эксп.

Трафик 1.

50% 60% 70% 60% 00%.

Уровень загрузки сервера О.

50%.

60% 70% В0% 90%.

Уровень загрузки сервера.

Трафик 2.

50% 60% 70% ао% 00%.

Уровень загрузки сервера.

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

2. Оказывается, что ресурсоемкий метод выбора минимальной очереди во всей системе (-1с1еа1) не дает значительного улучшения по сравнению с более простым методом с выбором из случайного подмножества очередей cncTeMbi (polling к).

3. Увеличение длины выборки к в методе с выбором минимальной очереди из иод-множества всех очередей (polling к) не приводит к существенному уменьшению среднего времени обслуживания заявки.

Результаты приведенных выше эмпирических исследований, а также многих других эмитационных работ (нанример [96], [78]) подтверждают эффективность алгоритма динамической маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей. Однако, в некоторых случаях, проведение моделирования может быть затруднено. Так, например, исследование динамической маршрутизации в системах с высокими требованиями к качеству обслуживания, приводит к необходимости моделировать редкие события, с вероятностью появления порядка Ю-6 — 10~9. В этих случаях, предпочтительным способом исследования систем являются аналитические методы. Рассмотрим далее существующие аналитические методы исследования систем с динамической маршрутизацией и приведем полученные в ходе них результаты.

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

Один из подходов, используемый в настоящее время для описания систем с динамической маршрутизацией, называемый методом среднего поля, разработан P.JT. Добрушиным в начале 70-х годов и успешно применен для исследования различных моделей сетей взаимодействующих очередей. Для детального описания рассматривавшихся систем и методов исследования достаточно обратиться к оригинальным статьям [14], [16], [29], [54], [57], [58], [88], [32], обзорам [30|, [55], [59], и работам [63], [75], [76]. Исследования P.JI. Добрушина были вызваны тем, что стандартные методы теории массового обслуживания, разработанные для простых систем с одним обслуживающим прибором, не удавалось использовать для систем взаимодействующих обслуживающих приборов. В ходе своих исследований Р. Л. Добрушин показал, что для рассматриваемых им моделей в асимптотике при бесконечной «сложности» системы, поведение системы становится детерменированным и может быть описано бесконечной системой дифференциальных уравнений. Поэтому, разработанные им методы работают тем лучше, чем «сложнее» система рассматривается. Для определенного класса моделей «сложность» системы может быть измерена через количество N обслуживающих приборов в ней. Показано, что при N —> оо метод среднего поля дает асимптотически точный результат для широкого круга систем.

Для описания систем с динамической маршрутизацией, балансирующей нагрузку, метод среднего поля впервые был применен в работе Н. Д. Введенской, Р.Л. Добруши-на, Ф. И. Карпелевича [92], в которой рассматривалась система с экспоненциальным распределением времени обслуживания заявок и пуассоновским входным потоком их поступления интенсивности NX, состоящая из N обслуживающих приборов, и балансирующая нагрузку по следующему правилу: при поступлении заявки в систему, на удачу выбирается г обслуживающих приборов из N и заявка становится в очередь минимальной, из выбранных, длины. Оказалось, что в приближении N —> оо можно получить асимптотически точную формулу вероятности переполнения системы. Сформулируем основной результат, полученный авторами: если обозначить через tifc-долю приборов, длина очереди в которых не меньше чем к, то верно lim ЕNuk = Х^-Шг-D.

N—> оо.

Если сопоставить полученный ими результат с аналогичной формулой для классического случая, когда в системе имеется N пуассоновских потоков интенсивности Л, и каждый из них обслуживается своим прибором с экспоненциальным распределением времени обслуживания, и в соответствии с формулой Эрланга:

Е Nuk = Afc, то оказывается, что возможность выбора одного из г приборов существенно уменьшает вероятности длинных очередей, а именно, для случая рассмотренного в статье, с ростом длин очередей вероятности длин убывают сверзкспонешщально, в отличие от экспоненциального убывания в классическом случае.

В качестве модели системы, авторы рассматривали однородную по времени цепь Маркова с пространством состояний Хдг = (Z)N, где Z-множество неотрицательных целых чисел. Если через компоненту вектора х = (х,., х^)? Х^, Xобозначить длину очереди г-го прибора, то цепь Маркова задается производящим оператором bnrx) = Ei: ii>i № - еО — /(х))+.

V {Еи"4<�х, (Л* + *) — Л®-)) + Еиw ((Л®- + е,) + f (x + ej))/2 — f (x))}, где ej-вектор, г-я координата которого равна единице, а остальные равны нулю.

Возможность получения явных асимптотических формул, как указали авторы, вызвана тем, что при N —> оо эволюция значений ик становится детерминированной, и систему можно описать бесконечной системой дифференциально-разностных уравнений вида:

-^ = uk+1(t) — uk (t) + АСК.^))2 — (uk (t))2)yk =1,2,., u0(?) = 1.

Развитием идей, предложенных в статье [92], послужила работа Н. Д. Введенской и Ю. М. Сухова [93], в которой рассматривалась обобщенная модель системы с динамической маршрутизацией. Авторы рассматривали систему, состоящую из большого числа идентичных серверов, имеющих бесконечные входные буферы и работающих в соответствии с дисциплиной обслуживания FIFO. Процесс поступления заявок в систему — пуассоиовский с интенсивностью AN, времена обслуживания заявок — независимые случайные величины, независящие от входного потока. Авторы рассматривали следующий алгоритм маршрутизации: каждая приходящая в систему заявка поступает на обслуживание в сервер, который выбирается из некоторого случайно выбранного подмножества обслуживающих приборов т N на основании фиксированного способа маршрутизации. Авторы доказали, что для широкого класса способов маршрутизации статистические свойства предельного при N —" со процесса детерминированы. Разработанный в статье, математический аппарат был использован для исследования конкретных способов маршрутизации. В частности, был рассмотрен случай, когда при маршрутизации заявки случайно выбирается т обслуживающих приборов и заявка направляется в прибор с s-ой по величине длиной очереди. При s = 1 — имеем стандартный способ маршрутизации, когда заявка направляется в очередь минимальной длины из выбранных, при , 1. В статье был рассмотрен также, так называемый, обобщенный пороговый метод динамической маршрутизации. В рамках него полагалось, что при поступлении в систему заявки в каждый последующий момент времени случайно выбирается тестовая очередь, длина которой сравнивается с некоторой фиксированной константой К. Если длина очереди оказалась меньшей или равной К — заявка направляется в нее, иначе тестируется следующая очередь. Если за т испытаний, очередь выбрана не была, то заявка направляется в последнюю очередь, независимо от ее размера. Если обозначить через Ufc — долю приборов в системе с длиной очереди, не превышающей к, а под 7Tfc подразумевать стационарное значение Uk предельной системы, то есть считать тгк = Птдг—эо Ед-иь то результат, полученный авторами, можно представить в следующем виде:

7Tfc = 1гК (тт%~1)к-К где к > К, 0 < тгК < 1.

В зарубежных публикациях для описания систем взаимодействующих очередей был независимо разработан подход, аналогичный методу среднего поля P.JI. Доб-рушина. Для детального описания предложенной методологии можно обратиться к статьям [95], [97], [72], [48], [49], обзорам [60], и последующим работам [43], [44), [45].

Методы управления потоком посредством динамической маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей системы аналитически исследовались Ягером в работах [33], [34], [35], моделирование производилось в работе Зоа [96]. Ягер использовал в своих работах марковскую модель системы, однако в ней он полагал, что состояние каждой очереди системы стохастически независимо от состояния других очередей. Это приближение верно в асимптотике, когда количество очередей стремится к бесконечности. Работы Зоа эмпирически оценивали эффективность методов балансировки нагрузки, предложенных в работах [33], [34], [35], используя при этом так называемое потоковое моделирование, в ходе которого, записанный в течении длительного промежутка времени трафик некоторой реальной системы подавался на моделируемую систему. И Ягер, и Зоа в своих работах пришли к выводу, что алгоритмы динамической маршрутизации, в которых производится выбор из некоторого подмножества доступных обслуживающих приборов, достаточно эффективно балансируют нагрузку. Дальнейшие исследования в этой области продолжил М. Митценмахер.

В своей работе М. Митценмахер [78] рассмотрел пороговый метод динамической маршрутизации, в рамках которого полагалось, что входной ноток заявок в систему из N приборов — пуассоновский с интенсивностью XN, время обслуживания заявокэкспоненциальное со средним равным 1. При поступлении заявки в систему на удачу выбирается один прибор, и длина его очереди сравнивается с пороговым значением Т, если она меньше или равна Т, — заявка поступает в эту очередь. Иначе, случайно выбирается следующая очередь, и заявка поступает в нее. Автором получены следующие результаты: в предыдущих обозначениях ттт+ является единственным решением следующего уравнения на отрезке [0,1] ! (1-А)[((1 + 7ГГ+1)А)Г+1−1] (1 + 7ГГ+1)Л — 1 и для щ = lim/voo Е^Щ верно, что.

7Ti = TTi-1 — А (7Гг2 — TTj—1)(1 + 7Tr+i).

Автор указал, что для порогового метода, рассмотренного в статье, с ростом длин очередей вероятности длин убывают не сверхэкспонепциальио, как в случае системы с выбором минимальной очереди из случайного подмножества всех очередей, а гораздо медленней, хотя скорость может быть достаточно большой, если ттт+ мало. В этой же работе рассмотрен случай пороговой маршрутизации, в котором заявка после выбора второй очереди, становится в минимальную из выбранных. Для этого случая доказано, что с ростом длин очередей вероятности длин убывают сверэкс-поненциалыю.(Лемма 12 [78]). Эмпирические исследования, проведенные в [96], [33], подтвердили этот результат.

Другой алгоритм балансировки нагрузки, в котором заявки при маршрутизации поступают в очередь минимальной во всей системе длины, также хорошо изучен рядом авторов. Результаты и детальное описание модели можно найти в работах [2],.

3], М.

Модели, балансирующие нагрузку, изучались и в статическом случае, когда необходимо распределить фиксированное количество задач на постоянное обслуживание, как в хеш-таблице. Например, в работе [56] авторы показали, что использование для этого двух хеш-фуикций вместо одной, может дать экспоненциальное уменьшение максимальной нагрузки буфера. Дальнейшее исследование и развитие этой идеи было произведено в работе [11].

Большие уклонения в системах с динамической маршрутизацией для случая экспоненциального обслуживания изучались в работе Тернера [90]. В качестве модели автор рассматривал систему обслуживания, состоящую из двух обслуживающих приборов с бесконечными входными буферами и экспоненциальным распределением времени обслуживания заявок, и полагал, что в систему поступает три пуассоновских потока заявок. Два потока фиксировано направляются на разные обслуживающие приборы, а третий состоит из заявок, маршрутизируемых в момент поступления в прибор с наименьшей очередью. В результате проведенного исследования, автором были получены асимптотически точные формулы для логарифма вероятности переполнения системы.

Дальнейшее исследование больших уклонений в системах, балансирующих нагрузку, продолжили Е. А. Печерский, Ю. М. Сухов и Н. Д. Введенская [84]. В своей работе они рассматривали аналогичную приведенной выше модель системы обслуживания с динамической маршрутизацией, состоящую из двух обслуживающих приборов и трех входных пуассоновских потоков заявок. Однако, в отличие от работы Тернера, авторы полагали, что времена обслуживания заявок являются независимыми, одинаково распределенными случайными величинами с неизвестной функцией распределения. В статье получена асимптотически точная формула логарифма вероятности переполнения системы. Сформулируем полученные авторами результаты. Обозначим через A= 0,1,2 интенсивности входных пуассоновских потоков заявок E! o, Hi,!E2 соответственно и положим, что заявки из потока Si фиксированно направляются в первый обслуживающий прибор, заявки из потока Н2 во второй обслуживающий прибор, а заявки из, Но при поступлении в систему направляются в прибор с очередью минимальной длины. Обозначим через S^ случайную величину, соответствующую времени обслуживания заявок из г-го потока, а через = Ee0S (o ее преобразование Лапласа. Через Wi, W2 обозначим длины очередей первого и второго прибора соответственно в момент времени 0, и Wmm — min (Wi, И^). В статье рассматривалось поведение стационарной вероятности переполнения системы в смысле попадания виртуальной заявки после маршрутизации в очередь достаточно большой длины, то есть искалась функция вида.

Ud) = lim — logP (Wm<" > nd), d > 0. n—00 П.

Авторами получены следующие результаты:

A. Если верно, что Лo (p'0(i9) > lAi^i?) — A2(^2(i?)|, то о (d) = 2 dd.

B. Если верно, что 2<р'2($) > + AoVo (^)> то.

I0(d) = d (62 + 0о, i).

C. Если верно, что Aiy? i ($) > А+ AoVoC^), то.

Io (d) = d (fft + 00,2), где 19 положительное решение уравнения = (Е -1)), t=0,l, 2 / a 0i, 0o, 2 и 02,0о, 1 положительные решения следующей системы с i = 2, j = 1 и г = 1, j = 2 соответственно: ft + во j = - 1) + Xj (ipj (e0j) — 1) + A0(^o (^oj) — 1).

A M (6i) = Wj (0oj) + Ao.

Заметим, что для получения аналитических результатов и в работе Тернера и в работе Е. А. Печерского, Ю. М. Сухова и Н. Д. Введенской использовалась аналогичная техника исследований. Так как входной поток в серверы в этой модели не является независимым и пуассоновким, для исследования авторы переходили к рассмотрению вспомогательной системы, в которой маршрутизируемый поток разделялся между серверами в некоторой постоянной пропорции на независимые потокитаким образом, рассматривалась система из двух обслуживающих приборов с независимыми пуассоновскими входными потоками заявок. Затем находилась истинная пропорция, которая возникает в исходной системе в стационарном режиме, и доказывалось, что с ней вероятности переполнения вспомогательной и исходной системы совпадают.

Предложенная техника хорошо работает для системы из двух обслуживающих приборов, но, как указал Тернер [90], применение ее для исследования систем с большим количеством выбираемых приборов затруднено.

Модель системы динамической маршрутизации с выбором из двух обслуживающих приборов, предложенная в работе Тернера [90] и описанная выше, также была изучена в режиме критической нагрузки [91].

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

Несмотря па то, что разработано множество моделей, призванных описывать системы с динамической маршрутизацией, и существует ряд методов исследования таких систем, можно выделить некоторые общие для всех моделей свойства.

Во-первых, в основном, во всех моделях рассматривается пуассоновский поток входных заявок и предполагается, что время обслуживания их распределено экспоненциально. Взятое за основу в этих моделях предположение о статистических закономерностях времени обслуживания не всегда соответствует действительности, хотя и полезно, так как приводит к «простым» марковским системам, которые приближенно описываются системами дифференциально-разностных уравнений.

Рассмотрение систем с другими распределениями времени обслуживания затруднено. Разработанные для этого методы, например в [78], основываются па, так называемом, методе стадий Эрланга, состоящем в том, что функция распределения любой положительной случайной величины может быть произвольно точно приближена счетной композицией 7-распределений. Так, например, чтобы представить постоянное время обслуживания, необходимо рассматривать каждую заявку, как состоящую из г стадий обслуживания, каждая стадия распределена экспоненциально со средним 1 /г. При увеличении г время обслуживания остается равным 1, а дисперсия уменьшается как 1 /г, поэтому при г —> оо полученная композиция ведет себя как константа. Однако па практике, как указывает автор, для того, чтобы задача была вычислима за конечное время, необходимо, чтобы количество 7-распределений в композиции и количество стадий в каждом 7-распределении было мало, что накладывает существенные ограничения на применение этого метода.

Во-вторых, в основном, во всех работах рассматриваются случаи, когда количество обслуживающих приборов в системе либо бесконечно, либо равно двум. В приближении бесконечного количества обслуживающих приборов, поведение системы обслуживания становится детерминированным, а эволюция состояний непрерывной, что позволяет производить ее исследование. Применение такой асимптотики хорошо подходит для описания систем с большим количеством обслуживающих приборов. Изучение же систем небольшого масштаба, не равного двум, вызывает определенные трудности. При переходе к конечному количеству приборов, необходимому для описания таких систем, приближение осуществляется на основании работ Кур-ца [63], [64], [65] и формул, полученных для бесконечного случая. Теоремы Курца в основном представляют собой закон больших чисел и границы типа Чернова для систем с динамической маршрутизацией.

Перечисленные выше общие свойства существующих моделей, являются естественным отражением экспериментальных фактов, лежащих в основе их построения и ранее обнаруженных на практике. Однако, развитие современной техники и сетевых архитектур привело к появлению новых систем взаимодействующих приборов, балансирующих нагрузку, статистические закономерности в которых имеют существенно другой характер, чем в системах рассмотренных ранее, поэтому, проводить исследования таких систем в рамках существующих моделей и методов, оказалось затруднительным. Приведем далее ряд примеров таких систем и укажем новые статистические закономерности, обнаруженные в них.

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

С появлением современных многопроцессорных систем и их последующим успешным применением в научных исследованиях и в бытовых устройствах с все большей актуальностью встает задача построения алгоритмов, эффективно распределяющих поток задач между процессорами и планирующих выполнение программы. Решение этой задачи послужило бы толчком к развитию компиляторов, разработке новых архитектур программ реального времени и операционных систем для многопроцессорных платформ. Очевидно, что такими алгоритмами являются алгоритмы динамической маршрутизации, рассмотренные ранее. Однако получение аналитических результатов, характеризующих их эффективность для мультипроцессорных систем в рамках существующих моделей и методов, оказалось невозможным.

В качестве аргументации сформулированного выше утверждения приведем исследования, проведенные в работе [46]. В этой работе авторы исследовали динамическую маршрутизацию процессов в современных распределенных вычислительных сетях под управлением операционной системы Linux. Целью исследования было сравнение различных способов маршрутизации, необходимых для эффективного использования вычислительных ресурсов. В качестве одного из способов авторы рассматривали следующий: при поступлении в систему нового процесса, из всех узлов выбирается тот, иа котором минимально ожидаемое время исполнения, процесс направляется в этот узел и находится в нем до конца обслуживания. Второй рассматриваемый способ маршрутизации, состоял в том, что при обслуживании некоторого процесса в узле системы, в каждый момент времени на основании текущей длительности исполнения, может быть принято решение о приостановке этого процесса, маршрутизации его в другой узел и перезапуске там. Как показали авторы, ответ на вопрос какой из способов более эффективен существенно зависит от гипотезы о распределении времени исполнения процессов.

Так, в результате ранее проведенных исследований аналогичной системы (Ягер. [35]), был сделан вывод, что маршрутизация с прерыванием обслуживания не дает значительного улучшения эффективности использования распределенных вычислительных ресурсов, по сравнению с маршрутизацией при поступлении, и поэтому ее применение не целесообразно. В своей работе Ягер полагал, что распределение времени обслуживания задачи вырожденное экспоненциальное, и следовательно в системе обычно находится мало задач с ненулевым временем обслуживания. Автор рассчитал, что при дисперсии вырожденного экспоненциального распределения, равной дисперсии наблюдаемого ими трафика, менее 4% всех задач имеют ненулевое время обслуживания, что, естественно, нивелировало выгоду от маршрутизации с прерыванием исполнения. Результаты, полученные в статье, широко цитировались и были применены при разработке системы Utopia [96].

В результате, как указали, основываясь на своих исследованиях, авторы в [46], выводы, сделанные в работе [35], оказались неверными, прежде всего, потому, что время исполнения процессов плохо аппроксимируется экспоненциальным распределением. Поэтому, для исследования динамической маршрутизации в распределенных вычислительных системах крайне важно точно знать закон распределения времени исполнения процессов. Однако, как указывают авторы, результаты исследований распределения времени исполнения процессов, проведенных ранее, крайне неоднозначны.

Так, Розин еще в 1965 году показал, что в вычислительных системах есть много задач, малых по длительности, и мало — с большой длительностьюдисперсия наблюдаемого распределения больше, чем у экспоненциального.

Последующие исследования, проведенные в 1986 году Леландом и Оттом, уточнили вид распределения. Авторы на основании исследования времени исполнения более 9.5 миллионов UNIX процессов, проведенных в период времени с 1984 по 1985, предложили новую функциональную форму распределения времени исполнения процессов. В ходе исследований, они выяснили интересную закономерность, что, чем больше текущее время исполнения процесса, тем больше его ожидаемое оставшееся время исполнения. Оказалось, что для процессов с большим временем исполнения Т > 3 секунд, вероятность того, что процесс будет исполняться более Т секунд, порядка rTk, где гнормализующая константа, и —1.25 < к < —1.05. То есть по их измерениям время обслуживания процесса имеет распределение с тяжелым хвостом.

Однако Роммел в 1991 году, основываясь на своих опытных данных, заключил, что «длинные процессы имеет экспоненциальное распределение времени обслуживания». И снова возникла неоднозначность, в следствии чего при проведении многих новых исследований динамической маршрутизации процессов стали предполагать экспоненциальное время обслуживания.

Чтобы разрешить возникшие разногласия, авторы статьи [46] решили провести свои независимые исследования. При проведении их они измерили длительность порядка миллиона процессов, порожденных различными академическими службами, вычислительными, исследовательскими и администраторскими компьютерами. Время исполнения каждого процесса было получено на основании информации команды lastcomm, выводимой на консоль операционной системой UNIX. В результате, основываясь на эмпирических данных, полученных при различных нагрузках, они пришли к выводу, что предложенная Леландом и Оттом функциональная форма распределения времени обслуживания хорошо описывает процессы с рабочим временем большим 1 секунды. Кроме того, они выяснили, что параметр к, в предложенном распределении меняется в пределах —1.3 < к < —0.8.

Результаты измерения длительности процессов на одном из компьютеров приведены на Рис. 2. На рисунке отражены только процессы с временем выполнения превышающим 1 секунду. Жирная кривая соответствует наблюдаемому распределениютонкая кривая отражает приближение экспериментальных данных методом наименьших квадратов функцией вида Тк. Из графика видно, что время выполнения процесса хорошо аппроксимируется предложенным распределением. Для подтверждения полученного результата авторы исследовали гипотезу о распределении времени выполнения процессов методом х2 и получили достоверность порядка 99%. Авторы также произвели сравнение наблюдаемого распределения времени выпол.

Дополнительное распределение времени выполнения процессов.

Длительность, с.

Дополнительное распределение времени выполнения процессов (log).

2. (а) Распределение времени обслуживания процессов с длительностью, превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая — приближению функцией гТк, полученному методом наименьших квадратов.(Ь) Тоже самое распределение в логарифмическом масштабе. Прямая линия показывает приближение гТк, где к угол наклона графика.

Наблюдаемое распределение и два приближения.

3. В логарифмическом масштабе показаны: толстой линией наблюдаемое распределение времени обслуживания процесса (исследовано более 13 000 процессов), и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе Pr (x > Т) ~ гхк, второе общепринятой.

Pr{x > Т) ~ се~хт. нения процесса с приближениями экспоненциальным и степенным распределением, полупенными методом наименьших квадратов. Результаты сравнения приведены на Рис. 3. Из рисунка видно, что экспоненциальное приближение времени выполнения процессов в распределенных вычислительных системах является слишком грубым по сравнению со степенным.

Приведенный выше пример системы со степенным распределением времени обслуживания, является не единственным. Существует и множество других примеров систем с такими вероятностными характеристиками обслуживания. Так, например, если возвратиться к рассмотренным выше эмпирическим исследованиям динамической маршрутизации в сервис-кластере, проведенным авторами работы [52|, легко обнаружить, что и в них оказалось, что время обслуживания запросов в сервис-кластере плохо описывается экспоненциальным распределением. Для этого достаточно сравнить поведение системы с одним из записанных реальных трафиков с поведением в случае искуственного Пуассон/Эксп. трафика (Рис.1). Авторы в своей работе указали на это, и сделали заключение, что более подходящими для описания процессов динамической маршрутизации в сервис-кластерах являются модели, когда длительность обслуживания и время между поступлением заявок имеют распределения типа Парето, Вейбулловское, степенное.

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

Исходя из изложенного выше анализа существующих моделей систем с динамической маршрутизацией и основываясь на приведенных опытных фактах, становится очевидно, что разработанные ранее модели не охватывают целый ряд новых систем с динамической маршрутизацией, и для описания их требуется построение повой модели. В рамках нее необходимо полагать, что время обслуживания заявок имеет распределение с тяжелым хвостом, а число обслуживающих приборов конечно. К сожалению, существующие методы исследования систем с динамической маршрутизацней не дают возможность точно описать такую модель, поэтому необходимо также разработать новые методы исследования. Как следует из приведенного ранее анализа существующих методов исследования систем с динамической маршрутизацией, иа данный момент времени в теории хорошо разработаны методы исследования либо больших систем (аемптотика по N —> оо), либо систем из двух обслуживающих приборов в асимптотике больших уклонений. Для систем с конечным числом обслуживающих приборов не равным двум, применяются приближения, базирующиеся на результатах, полученных для бесконечного случая. Однако, как правило, рассматриваемые системы с динамической маршрутизацией и конечным числом обслуживающих приборов, являются системами с высокими требованиями к качеству предоставляемого обслуживания, и, поэтому, более подходящей асимптотикой для их описания является асимптотика больших уклонений.

На основании вышесказанного, в работе предложена следующая модель для исследования систем с динамической маршрутизацией.

Система обслуживания состоит из N серверов. Процесс поступления заявки в систему — пуассоновский с интенсивностью NX. Время обслуживания заявок имеет распределение вероятностей с тяжелым хвостом. Рассматриваются случаи степенного и Вейбулловского распределения. Маршрутизация производится следующим образом. При поступлении в систему заявки в момент времени t, случайно выбираются К различных серверов из N, и заявка направляется в очередь сервера с минимальной длинной. Изучается поведение вероятности переполнения системы в асимптотике большого входного буфера, а именно, вероятности попадания виртуальной заявки в очередь с временем обслуживания находящихся в ней заявок большим уровня ~о (~о —> оо), без учета времени обслуживания поступившей заявки, но с учетом заявки, стоящей на обслуживании. Рассматривается модель системы обслуживания дискретного времени.

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

В рамках предложенной модели в диссертационной работе получены следующие основные результаты.

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

• 2. Рассмотрен «промежуточный», между классическим экспоненциальным и степенным, случай, когда время обслуживания заявки имеет распределение Вей-булла. Получены асимптотически точные формулы для вероятности переполнения системы.

3. Разработан метод выбора оптимальных параметров маршрутизации (величины выборки), обеспечивающих требуемое качество обслуживания системы.

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

Работа состоит из введения, двух глав, заключения и библиографического списка.

Во первой главе будет рассмотрена система обслуживания с динамической маршрутизацией и заявками, имеющими степенной закон распределения времени обслуживания. В начале главы, будет предложена и точно сформулироваина модель системы с динамической маршрутизацией и перечислены основные полученные результаты. Далее, будут приведены доказательства полученных результатов. В конце главы, будет дан качественный анализ, основывающийся на полученных результатах, а в приложении приведено доказательство использующихся лемм.

Во второй главе будет рассмотрена система обслуживания с динамической маршрутизацией и заявками, имеющими Вейбулловский закон распределения времени обслуживания. Исследования этого случая, будут проведены в соответствии с методологией, разработанной в первой главе. Для системы будут получены асимптотические точные формулы переполнения системы и приведены соответствующие доказательства. В конце главы, будет произведено обсуждение полученных результатов и качественное сравнение их со случаем, когда время обслуживания заявки имеет степенное распределение.

В заключении будут обсуждены полученные результаты работы и сформулированы направления дальнейшего исследования.

Заключение

.

В заключение сформулируем основные результаты полученные в работе.

В диссертационной работе проведен анализ существующих моделей и методов исследования систем с динамической маршрутизацией. Рассмотрены экспериментальные факты, подтверждающие необходимость разработки новых методов исследования. На основе проведенного анализа построена модель системы, отражающая новые требования, полученные при рассмотрении экспериментальных результатов. Новая модель базируется на предположении о том, что время обслуживания заявок имеет распределение с тяжелым хвостом, учтено требование конечности масштаба системы.

В результате предложена следующая модель системы балансирующей нагрузку — модель обслуживания дискретного времени. Входной процесс поступления заявок в систему — пуассоновский, с интенсивностью NX. Время обслуживания заявок имеет распределение вероятностей с тяжелым хвостом. Заявки, поступающие в систему, распределяются между обслуживающими приборами по следующему правилу маршрутизации: при поступлении j-й заявки в момент времени t из N обслуживающих приборов случайно выбираются К, неповторяющихся и заявка направляется па выбранный прибор с минимальной длиной очереди.

Исследования были проведены в асимптотике большого буфера, что является естественным приближением при исследовании современных систем с высокими требованиями, предъявляемыми к качеству обслуживания, а именно рассматриваются системы с вероятностью переполнения порядка Ю-6 — Ю-9.

Исследовалось стационарное поведение системы. Рассматривалась вероятность переполнения системы в смысле вероятности попадания виртуальной заявки при маршрутизации в очередь сервера с остаточным временем обслуживания находящихся в нем заявок, превышающим уровень г0> для больших zq — без учета времени обслуживания поступившей заявки.

В силу того, что существующие методы исследования систем с динамической маршрутизацией плохо подходят для описания систем такого рода, были разработаны новые методы. Предложенные методы базируются на математическом аппарате, применяемом для исследования систем с вероятностными характеристиками с тяжелым хвостом, и, по сути, представляют собой методы построения и оценки оптимальных конфигураций системы, наиболее вероятно приводящих к переполнению.

В первой главе работы рассмотрена система с динамической маршрутизацией, балансирующая нагрузку в сети, и заявками, имеющими степенное распределение времени обслуживания. Использование предложенных методов исследования систем с динамической маршрутизацией дало возможность получить простые аналитические результаты в виде асимптотически точных формул переполнения системы. Полученные формулы не только позволяют исследовать параметры качества обслуживания существующих систем при текущих характеристиках трафика, что, например, необходимо в сети ATM при поступлении запроса на обслуживание от конкретного пользователя, но и делают возможным выработать ряд рекомендаций по оптимальному конструированию мультипроцессорных систем и сетевых устройств, призванных обеспечить заданные параметры качества обслуживания.

Во второй главе работы рассмотрен важный, как с практической, так и с теоретической точки зрения «переходный случай» между классическими системами с экспоненциальным временем обслуживания и системами с вероятностными характеристиками с тяжелым хвостом-случай Вейбулловского распределения времени обслуживания. Как уже было указано ранее, исследование этого случая затруднено, так как требует использования более точных асимптотических методов. Однако, применение новых разработанных методов исследования систем с динамической маршрутизацией позволило получить и в этом случае простые аналитические результаты в виде асимптотически точных формул переполнения системы. Как и следовало ожидать, вероятность переполнения системы имеет существенно другой вид зависимости от параметров маршрутизации по сравнению со случаем, рассмотренным в первой главе, и описывающим поведение системы со степенным распределением времени обслуживания заявок. В отличие от медленного, степенного убывания вероятности переполнения с увеличением параметра маршрутизации К, полученного ранее, вероятность переполнения в системе с Вейбулловским распределением времени обслуживания заявки убывает значительно быстрееэкспоненциально. Кроме того, в отличие от случая заявок со степенным распределением времени обслуживания, для которых при р < N — К оптимальной была конфигурация, когда в системе в момент t находится К заявок с остаточным временем обслуживания, превышающим пороговое значение го, при Вейбулловском распределении времени обслуживания оптимальной будет конфигурация, когда эти заявки пришли в систему практически одновременно (на отрезке порядка o (zo)). Это является следствием более резкого убывания вероятности возникновения заявки с большим временем обслуживания в распределении Вейбулла по сравнению со степенным.

Построение оптимальной конфигурации переполнения Вейбулловской системы для случая р > N — К гораздо сложнее и приводит к необходимости решать нелинейную оптимизационную задачу. По сравнению с оптимальной конфигурацией для степенного распределения времени обслуживания, когда переполнение происходило, если «большие» заявки стояли в.

Tii = агд min (п) и N—p N — К, оптимальной может быть конфигурация из К заявок с остаточным временем обслуживания, превышающим пороговое значение г0.

Дальнейшие направления исследования и нерешенные задачи.

Несмотря на то, что пакет данных является основной единицей измерения в современных сетях передачи данных, и большинство исследований производится именно в масштабе пакета, конечный пользователь работает не с ним, а с некоторой логической последовательностью пакетов. Действительно, большинство операций пользователя может быть выражено через некоторую последовательность запросов и ответов. Так скачивание файла с удаленного сервера влечет за собой открытие TCP/IP соединения и передачи по нему множества пакетов, открытие Web страницы также приводит к установлению TCP/IP соединения. Логично заключить, что при разработке методов повышения качества обслуживания в сети необходимо руководствоваться вышеизложенными соображениями и реализовывать алгоритмы (например балансировки нагрузки), работающие не на уровне пакета, а на уровне TCP/IP соединения. Задачи повышения качества обслуживания для конкретного соединения возникают часто, например, в мультимедийных сетевых приложениях, когда пользователь хочет установить соединение и потребовать эксклюзивные параметры качества обслуживания для трафика реального времени. Понятно, что алгоритм предоставления их должен работать па уровне TCP/IP сеанса. Поэтому важным является установление вероятностных характеристик трафика сетей, не только на уровне пакетов, но и соединений.

Исследования трафика сетей передачи данных имеют богатую историю. Изначально, общепринятой моделью трафика являлась классическая модель с Пуассо-новским поступлением и экспоненциальным обслуживанием. Однако благодаря работе Leland, Wilson, Willinger и Taqqu [66], исследовавших трафик локальных сетей, было обнаружено явление, невписывавшееся в общепринятую модель. Трафик сетей оказался самоподобным, то есть имеющим одинаковое конечномерное распределение во всех временных масштабах.

Это явление, обнаруженное на пакетном уровне, объяснил Willinger, сделав предположение о том, что трафик локальных сетей является суперпозицией ВКЛ/ВЫКЛ источников с распределением длин ВКЛ/ВЫКЛ периодов с тяжелым хвостом.

Дальнейшее исследование трафика сетей продолжили Paxson & Floyd [83], которые показали, что трафик глобальных сетей (WAN) также самоподобеи. В качестве объяснения явления они предложили модель, в которой пакеты поступают в систему согласно распределению Пуассона, по несут с собой работу, количество которой имеет распределение с тяжелым хвостом вероятности. Однако, они также отметили, что процесс возникновения FTP и SMTP соединений плохо аппроксимируется Пуассоновским процессом.

Новейшие исследования статистических закономерностей трафика на уровне соединений провела A. Feldmann [37] для случая HTTP сеансов. Она указала, что Пуас-соновское распределения входного потока хорошо описывает случай, когда пользователи устанавливают соединения независимо друг от друга и от предыдущих установленных соединений, что было справедливо еще в 1995 году. Однако, последовавший в последнее время бурный рост сетей вывел на лидирующие позиции Web приложения, — более половины пакетов и более двух третой TCP соединений инициировано Web браузерами. Современный сетевые страницы содержат в среднем не один ресурс, а пользователи склонны в течении Wreb соединения просматривать не одну страницу и инициировать не одно связанное с контекстом ftp соединение. То есть запросы пользователя взаимосвязаны. Таким образом оказалось, что с ростом сетей изменяются их вероятностные характеристики, предположение о пуассонов-ском характере трафика становится менее применимо, и появляется необходимость разработки новых моделей сетевого трафика.

A.Feldmann исследовала трафик современных сетей и пришла к выводу, что время между установлениями соединений в современной сети имеет не экспоненциальное распределение, как в случае пуассоновского поступления, а хорошо аппроксимируется распределениями с тяжелым хвостом (Вейбулловское, Парето, степенное). Она.

I I I I I I I I.

ЧСУМ- 10*43 10*-2 10 М 10*0 10*4 10Л2 10*3 time (in seconds}.

9. Эмпирическая плотность распределения вероятностей времени между установлениями TCP/IP соединений во внешнем сегменте сети AT&T.

18 Ноября-8 Декабря 1995. показала, что для случая Web соединений особенно хорошую аппроксимацию дает распределение Вейбулла времени между установлениями новых соединений. Трафик исследовался в течении длительного промежутка времени в разных сегментах сети AT&T. Выло установлено, что как во внешнем сегменте, так и во внутреннем домину-руют пакеты от TCP/IP соединений, порожденных HTTP протоколом. В результате исследований была построена эмпирическая плотность распределения вероятности времени между установлением новых соединений, приведенная на Рис. 9.

По оси абсцисс отложено время возникновения в секундах, по оси ординат количество возникших соединений. Наличие небольшого выброса в районе 0.234 объX о.

А + О measured data.

Weibull с = 0.605, а = 4.477 Д" Pareto к = 0.68, а = 1.289 • exp. mean = 6.68 Д.

Inorm mean = 0.533 var =.

10л-5.

10л-3.

10л-1 time.

10л1 10л2 10л3.

10. Эмпирическое дополнительное распределения вероятностей времени между установлениями TCP/IP соединений и приближения, полученные методов наименьших квадратов, во внешнем сегменте сети AT&T 18 Ноября-8 Декабря.

1995. яснястся существованием зависимостей в протоколах, а именно, при открытии HTTP документа по протоколу необходимо установить несколько TCP/IP соединений для скачивания встроенных в документ объектов (gif-анимации).

На Рис. 10 отражено наблюдаемое дополнительное распределение времени между установлениями соединений и его приближения, распределениями с тяжелым хвостом и экспоненциальным, полученные методом наименьших квадратов,. Из рисунка видно, что распределения Логнормальное, Парето и экспоненциальное — дают значительно менее точное приближение, чем Вейбулловское. Так экспоненциальное распределение дает заниженный результат, как для коротких, так и для длинных времен. Логнормальное, напротив, дает оценку выше действительной в обоих случаях. Парето дает завышенную оценку средних значений времени и очень плохо аппроксимирует короткие промежутки возникновения.

Как легко заключить из приведенных выше результатов исследования трафика сетей, для разработки новых более эффективных систем динамической маршрутизацией, необходимо производить балансировку нагрузки не на уровне пакета, а на уровне соединения. Необходимо построить новые модели систем с динамической маршрутизацией, в которых бы полагалось, что, как распределение времени обслуживания, так и распределение времени между поступлениями заявок являются распределениями вероятностей с тяжелым хвостом. Для исследований новых моделей необходимо разработать математический аппарат, который позволил бы получить аналитические результаты.