Например, Бобцов

ИССЛЕДОВАНИЕ МНОГОКАНАЛЬНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ЭКВИВАЛЕНТНОЙ ПРОИЗВОДИТЕЛЬНОСТЬЮ

УДК 004.41
ИССЛЕДОВАНИЕ МНОГОКАНАЛЬНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ЭКВИВАЛЕНТНОЙ
ПРОИЗВОДИТЕЛЬНОСТЬЮ
В.В. Соснин
В работе с помощью имитационного моделирования анализируются свойства многоканальных систем с эквивалентной суммарной производительностью. Детально исследуется влияние параметров входящего потока заявок на среднее время пребывания заявок в системе. Ключевые слова: теория очередей, многоканальные системы массового обслуживания, неэкспоненциальные законы распределения, оценка эффективности, имитационное моделирование.
Введение
При проектировании компьютерных систем и сетей широко применяются модели массового обслуживания. При этом моделями отдельных устройств и узлов в общем случае служат системы массового обслуживания (СМО) типа G/G/N (в символике Кендалла [1, с. 107]). В такой системе на обработку к N приборам одинаковой производительности поступает произвольный поток заявок, а время обслуживания в каждом приборе описывается произвольным законом распределения (ЗР). Под производительностью прибора понимается интенсивность обслуживания заявок. При N > 1 система называется многоканальной. Зададим для случая N = 1 некоторое значение производительности V1 для обрабатывающего прибора. Тогда класс СМО с N ≥ 1, в которых производительность каждого из N приборов равна VN = V1/N, будем называть системами с эквивалентной производительностью (СЭП), так как суммарная производительность всех приборов в них остается постоянной: V∑ = VN⋅N. При этом все СМО из заданного класса СЭП будут одинаково хорошо справляться с нагрузкой, т.е. обеспечат одинаковый уровень загрузки. В литературе [2, с. 82] описываются присущие СЭП свойства: 1) с увеличением N возрастает отказоустойчивость в СЭП (при выходе из строя k при-
боров суммарная производительность снижается в N/(N – k) раз);
34 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 1(59)

2) с увеличением N возрастают накладные расходы на обеспечение взаимодействия между обслуживающими приборами;
3) с увеличением N среднее время ожидания заявок в очереди уменьшается, так как при большем числе приборов большая часть заявок немедленно поступает на обслуживание;
4) с увеличением N среднее время пребывания заявок в СМО увеличивается. Из пункта 4 этого перечня следует, что для минимизации задержек выгоднее ис-
пользовать системы с меньшим числом каналов. Это свойство является очень важным при выборе оптимального числа N, так как время пребывания характеризует эффективность работы СМО в целом. Заметим, что это свойство получено и доказано в результате аналитического моделирования СЭП М/М/N.
Целью данной работы стало исследование свойств СЭП G/G/N. Применение аналитических методов для этого невозможно, так как при этом понадобилось бы точное задание ЗР входящего потока и ЗР времени обслуживания. Поэтому исследование проводилось на имитационных моделях. В результате многочисленных экспериментов были получены новые свойства СЭП, которые противоречат приведенному выше свойству 4. Таким образом, появилась необходимость более детально исследовать зависимость среднего времени пребывания заявок в системе от числа N для СЭП с неэкспоненциальными потоками. Для этого в работе решались следующие задачи: 1) определение факторов, влияющих на исследуемую характеристику (среднее время
обслуживания заявок); 2) выявление характера влияния на нее каждого из этих факторов; 3) формулирование рекомендаций по оптимизации выбора числа N при проектирова-
нии систем. Модель СЭП разработана в среде имитационного моделирования GPSS World. В
модели предусмотрена возможность варьирования числа приборов и законов распределения времени обслуживания и времени между прибывающими заявками (гаммараспределение, распределение Кокса, экспоненциальное распределение, равномерное распределение).
Постановка задачи
В качестве примера сравним характеристики двух классов СЭП, М/М/N и G/G/N, с некоторым заданным набором параметров. На практике бывает удобно рассматривать не конкретный ЗР, а ограничиться указанием лишь первых двух моментов этого закона, так как именно эти два момента оказывают определяющее влияние на характеристики. Поэтому в рассматриваемых системах зададим среднее время между приходом заявок ТП = 100 единиц времени, коэффициент загрузки Кз = 60%, коэффициент вариации времени обслуживания заявок в приборе (KVTО) и коэффициент вариации времени между приходами заявок (KVTП). Среднее время обслуживания заявок будет определяться в зависимости от N по формуле TO = Кз⋅TП⋅N. Очевидно, что две рассматриваемые СЭП будут отличаться только коэффициентами KVTП и KVTО.
На рис. 1, а представлена зависимость времени пребывания заявок СЭП M/М/N (теоретический расчет) от числа приборов N. Принятые обозначения: U – среднее время пребывания заявки в СМО, W – среднее время ожидания обслуживания заявки. На рис. 1, б показана аналогичная зависимость для СЭП G/G/N (по результатам имитационного моделирования). Здесь и далее на графиках с результатами экспериментов приводится 95 % доверительный интервал (по Стьюденту) всех измеренных характеристик.
График на рис. 1, а иллюстрирует классический случай, когда с точки зрения минимизации задержек наиболее выгодным является использование одноканальной СМО, так как время пребывания U(N) монотонно возрастает. Эксперименты показали, что по-

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 1(59)

35

добный характер поведения системы сохраняется при любой загрузке при условии, что 0≤ KVTО≤ 1 и 0≤ KVTП≤ 1. Однако стоит увеличить оба коэффициента вариации выше этих ограничений, как это правило потеряет силу (рис. 1, б): у функции U(N) теперь наблюдается минимум в точке N = 3. Этот пример доказывает, что эмпирическое правило о предпочтительности минимизации числа каналов в СЭП нельзя распространять на весь класс систем G/G/N.

Время, ед.вр.

U(N) = W(N)+TО(N)

T

(N)
О

=

0,6*100*N

W(N)

N

Время, ед.вр.

T

(N)
О

=U0(N,6)*1=0W0*(NN)+T

(N)
О

W(N)

N

а) б) Рис. 1. Зависимость времени пребывания заявок в СЭП от числа приборов:
а) KVTО = 1, KVTП = 1; б) KVTО = 3, KVTП = 1,5
Таким образом, возникает задача оценки влияния на экстремум функции U(N) следующих параметров: 1) коэффициент вариации времен обслуживания заявок в приборе (KVTО); 2) коэффициент вариации времен между приходами заявок (KVTП); 3) коэффициент загрузки СМО (Кз).

Результаты исследования
В работе исследовалось независимое влияние на U каждого из этих факторов. Ниже приводятся результаты экспериментов, в которых значение исследуемого фактора варьировалось, а значения двух других факторов фиксировались. На рис. 2 приведена зависимость U(KVTO) для трех значений N при ТП = 100 единиц времени, KVTП = 1 и Кз = 60 %. Для N=1 расчет проводился по формуле Поллячека–Хинчина [3, с. 208]. Для N=2 и N=3 приведен 95%-й доверительный интервал измеренной характеристики. На рисунке UN=i означает среднее время обслуживания заявки при числе обслуживающих приборов, равном i. Обозначим через Nopt число приборов, для которого в данном классе СЭП среднее время пребывания заявок является наименьшим. Как видно из рисунка, при KVTO < 2 имеем Nopt = 1, при 2 < KVTO < 3 имеем Nopt = 2, при KVTO > 3 имеем Nopt = 3. Очевидно, существует некоторое значение, при превышении которого коэффициентом вариации KVTO оптимальным числом приборов станет 4, 5, 6 и т.д. Наличие этого эффекта подтверждается многочисленными экспериментами.
На рис. 2 зависимость UN=1(KVTO), согласно формуле Поллячека–Хинчина, имеет параболический вид: UN=1(KVTO) = С1⋅KV2TO + С2, где С1 и С2 – константы, не зависящие от KVTO. Расчеты показали, что и две другие зависимости (UN=2(KVTO) и UN=3(KVTO)) имеют с критерием достоверности аппроксимации R2=0,999 аналогичный вид, с разницей лишь в значении констант C1 и C2. Знание общего вида этой зависимости позволяет использовать следующий алгоритм анализа систем с неизвестным KVTO: 1) на имитационной модели найти несколько пар значений UN=2 и KVTO, а также UN=3 и
KVTO при малых значениях KVTO (так как именно при малых значениях этого коэф-

36 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 1(59)

фициента вариации получаемые характеристики достаточно точны, т.е. имеют узкий доверительный интервал); 2) по найденным парам найти аппроксимирующие функции UN=2 (KVTO) и UN=3(KVTO) – в этом случае аппроксимирующие функции будут определены даже точнее, чем если бы они искалась, в том числе, и по известным парам значений с высоким KVTO, приводящим к значительному разбросу в значении получаемых характеристик; 3) решить уравнение UN=2 (KVTO) = UN=3(KVTO) относительно KVTO; 4) проделать пункты 1–3 для достаточного числа последующих пар (UN=3(KVTO) = UN=4(KVTO), UN=4(KVTO) = UN=5(KVTO) и т.д.).

Рис. 2. Зависимость времени пребывания заявок в СЭП от KVTO
В результате будут найдены значения KVTO, являющиеся границами изменения значения Nopt. Полученные данные удобно использовать при проектировании рассмотренного класса систем.
На рис. 3 приведена зависимость U(KVTП) для трех значений N при ТП = 100 единиц времени, KVTО = 2 и Кз = 60 %. Каждая из UN=i представлена двумя графиками, задающими нижнюю и верхнюю границу 95 %-го доверительного интервала. Очевидно, что ситуация похожа на предыдущую: здесь также наблюдаются точки пересечения, т.е. смена значения Nopt. По рисунку можно с уверенностью сказать, что при KVTП < 2 получаем Nopt = 1, а при KVTП > 2 получаем Nopt > 1.
При исследовании фактора KVTП было замечено, что вообще-то наличие точек пересечения зависит от выбранного значения KVTО (он должен быть больше некоторого числа из промежутка 1–2), тогда как при варьировании самого KVTО такой зависимости от других факторов не отмечено.
По аналогии с предыдущим случаем для каждого из UN=i была получена аппроксимирующая функция. Оказалось, что с критерием достоверности аппроксимации R2 = 0,999 для всех трех случаев она имеет вид UN=i = С3⋅KV2TП + С4⋅KVTП + С5 с разницей лишь в константах С3, С4, С5, которые не зависят от KVTП. Очевидно, что полученная закономерность может быть использована аналогичным образом (можно, например, чисто аналитически узнать значение KVTП, при котором Nopt = 3, так как определить это по рисунку нельзя из-за перекрытия границ доверительных интервалов UN=2 и UN=3).

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 1(59)

37

Рассмотрим, наконец, зависимость U(Kз), которая представлена на рис. 3. На этом рисунке ТП = 100 единиц времени, KVTП = 1, KVTО = 2,5. Снова видим схожую с предыдущими ситуацию: после некоторого значения варьируемого фактора более выгодным становится использовать СМО с большим числом обслуживающих приборов (на рис. 3 при Кз > 0,25 выгоднее использовать 3 прибора, чем 1). Однако и для Кз была замечена зависимость наличия точек смены Nopt от выбранного значения KVTО. Таким образом, независимое влияние оказывает только KVTО, а два других фактора нужно рассматривать в непременной связи с KVTО.
Рис. 3. Зависимость времени пребывания заявок в СЭП от KVTП
Рис. 3. Зависимость времени пребывания заявок в СЭП от Kз
Аппроксимирующие функции для UN=i с критерием достоверности аппроксимации R2=0,999 для всех трех случаев имеют вид UN=i = С6 + С7/(1–Kз) с разницей лишь в константах С6 и С7, которые не зависят от Kз.
Пример Приведем пример использования полученных результатов на практике. Пусть в некоторой фирме используется выделенный канал Интернет со скоростью 100 Мбит/с на витой паре. Предположим, что в связи с расширением фирмы становится необходимым удвоить указанную производительность канала. Возникает две альтернативы решения задачи: 1) проложить дополнительный канал со скоростью 100 Мбит/с на витой паре; 2) отказаться от использования существующего канала (сдать его в утиль), проложить новый, основанный на оптоволокне, и уже по нему оплатить подключение на скорости 200 Мбит/с.
38 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 1(59)

Очевидно, что дешевле будет реализация первой альтернативы. Но, согласно бытовавшим представлениям, с точки зрения минимизации задержек выгоднее должен быть второй вариант. Однако рассмотрим конкретную ситуацию: замер параметров трафика в сети Fast Ethernet, состоящей из 500 компьютеров, в течение часа случайно взятого времени показал, что KVTП = 2,1, KVTО = 1,31. Время прибытия в этом случае – это время между прибывающими пакетами. А время обработки определяется длиной пакета, так как скорость передачи постоянна. Если провести имитационное моделирование для загрузки 0,05–0,15 (при которой характеристики измеряются очень точно), а затем по полученным данным построить аппроксимирующие функции для числа N = 1 и N = 2, то для UN=1 получим С6 = –183 и С7 = 274, для UN=2 получим С6 = –80 и С7 = 208. Если затем составить уравнение UN=1 = UN=2 , то его решением будет Кз = 0,34. Получаем, что при Кз > 0,34 для минимизации задержек выгоднее использовать два канала, а не один. Иначе говоря, при определенной конфигурации передаваемого потока пакетов становится вполне реальной ситуация, когда даже с точки зрения минимизации задержек выгоднее использовать два низкоскоростных канала вместо одного высокоскоростного.
Выводы
На основании проделанной работы можно сделать следующие выводы. 1. Решение задачи выбора оптимального числа каналов (при сохранении их суммарной производительности) с точки зрения минимизации задержек в М/М/N нельзя распространять на весь класс G/G/N. 2. Необходимость увеличения числа приборов в СЭП (для минимизации задержек) возрастает: – с увеличением загрузки; – с увеличением коэффициента вариации времени между приходами заявок; – с увеличением коэффициента вариации времени обслуживания заявок. На понятийном уровне такой эффект означает, что большее число каналов (по сравнению с меньшим числом) сглаживает пульсации входящего потока сообщений, давая им быстрее попасть на обслуживание. 3. Независимое влияние на выбор числа каналов оказывает только коэффициент вариации времени обслуживания заявок. Два других фактора увеличивают скорость его воздействия. 4. Полученные аппроксимирующие функции могут быть использованы при выборе оптимального числа каналов в СЭП G/G/N.
Литература
1. Шнепс М. А. Системы распределения информации. Методы расчета. – М.: Связь, 1979. – 344 с.
2. Клейнрок Л. Коммуникационные сети (стохастические потоки и задержки сообщений). – М.: Наука, 1970. – 256 с.
3. Клейнрок Л. Теория массового обслуживания. – М.: Машиностроение, 1979. – 432 с.

Соснин Владимир Валерьевич

– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, vsosnin@mail.ru

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 1(59)

39