Investigation of the queuing system HIGI|GI|?.pdf Модели теории массового обслуживания возникли [1] как адекватное математическое описание телекоммуникационных процессов и в настоящее время используются для описания и анализа процессов, возникающих в различных областях деятельности человека. Одной из важнейших областей применения моделей массового обслуживания являются компьютерные сети [2]. В связи с бурным ростом телекоммуникационных технологий объемы данных, передаваемых по сетям связи, очень велики и зачастую намного превышают возможности систем их обработки. В силу этого, нам представляется актуальным введение понятия «высокоинтенсивный поток» [3] и использование его для представления входящего потока требований в системе обработки информации, модель которой представлена в виде системы массового обслуживания. 1. Постановка задачи. Метод просеянного потока Рассмотрим систему массового обслуживания с неограниченным числом приборов [4], на вход которой поступает высокоинтенсивный рекуррентный (HIGI) поток заявок [3]. Длины т интервалов между последовательным поступлением заявок из этого потока независимы и одинаково распределены. Функция распределения значений т описывается следующим образом. Представим т в виде т = / N, где - некоторая неотрицательная случайная величина с функцией распределения A(z), а параметр N> 0 имеет смысл большой величины (в теоретических исследованиях предполагается, что N ^ t не зависит от значений n(t1) и z(tj) для моментов t1 < t. Компонента z(t) в момент времени t + z принимает случайное значение, равное длине интервала до момента наступления следующего события во входящем потоке. Так как интервалы между наступлениями событий во входящем рекуррентном потоке являются независимыми случайными величинами, то значения компоненты z(t) в моменты времени t1 > t также не зависят от значений n(t1) и z(t1) для моментов t1 < t. Таким образом, указанное выше основное марковское свойство для рассматриваемого двумерного процесса {n(t), z(t)} полностью выполняется, т.е. указанный процесс является марковским. Обозначим распределение вероятностей значений этого процесса через P(n, z, t) = P {n(t) = n, z(t) < z / N} . Применяя формулу полной вероятности, для этого распределения можно записать равенство P(n, z, t + At) = P(n, z + N At, t) - P(n, N At, t) + P(n -1, N At, t) A( z )S (t) + +P(n, N At, t) A( z) - P(n, N At, t) A( z )S (t) + o(At). Отсюда получаем уравнение Колмогорова 1 dP(n, z, t) dP(n, z, t) dP(n, 0, t). -[A( z) -1 - A( z)S (t)] + N dt dz dz + ^A(z)S(t) (2) dz z=0 dP(n, 0, t) dP(n, z, t) (здесь и далее используется обозначение dz dz Просуммируем уравнение (2) по n = 0, да, получим 1 д да д да д да S P(n, z, t) = — X P (n, z, t) + [ A( z) -1 - A( z )S (t) ]—S P(n, 0, t) + N 5tn=0 5zn=0 5zn=0 5 да +A(z)S(t)—S P(n -1,0, t). (3) 5zn=1 Здесь S P(n, z, t) = P {z(t) ) = 1, а f(1 -A(x))dx = —. В результате-= X и решение уравне- 0 X dz ния (4) имеет вид z R(z) = X|(1 -A(x))dx. для этой функции получим 1 dH(u,z,t) = dH(u,z,t) , dU(м,0,t) [A(z) - A(z)S(t) -1] + e* dH(UMA(z)S(t) = dH (u, z, t) + dH (u,0, t)[ N dt dz dz dz A(z) -1 + A(z)S(t) (ej -1)]. dz dz В этом уравнении выполним замену H (u, z, t) = H2(u, z, t)exp ! juNXj S (x)dx I h j получим уравнение относительно функции H2(u, z, t): 1dH 2(u,z,t) + juXS (t) H 2(u, z, t) = N dt = dH2(«,z,t) + ая^о^[A(z)-1 + A(z)S(t)( -1)] . (5) Уравнение (5) будем решать методом асимптотического анализа [5]. Введем 21 обозначение е = — и выполним замены u = ew и H2(u, z, t) = F(w, z, t, e). Тогда N уравнение (5) перепишется в виде 2 dF(w, z, t, е) + jswXS (t) F (w, z, t, е) = t dF (w, z, t, е) dF (w,0, t, е) + (w,u,t,е) [A(z) -1 + A(z)S(t) ( -1)] . (6) dz dz Докажем следующее утверждение. Теорема. Предельное при e ^ 0 значение F(w, z, t) решения F(w, z, t, e) уравнения (6) имеет вид S (x)dx + к j S 2( x)dx) F (w, z, t) = R( z )exp -j где к = Х9(ст2 - a2), (7) a и с2 - математическое ожидание и дисперсия случайной величины с функцией распределения A (x). Доказательство выполним в три этапа. Этап 1. Положим в (6) e ^ 0, получим dFOwM+dFOwM a z) -1] = 0. dz dz Это уравнение имеет такой же вид, как и (4), поэтому очевидно, что функция F(w, z, t) может быть представлена как F (w, z, t) = R( z) Ф^, t), (8) где Ф^, t) - некоторая функция, не зависящая от z. Этап 2. Решение уравнения (6) будем искать в виде разложения F(w, z,t, е) = Ф(w, t) [R(z) + jswS(t) f (z)] + 0(е2), (9) где fz) - некоторая функция, O(e10) - бесконечно малая величина порядка e2. Подставим это выражение в (6), получим jewXS (tmw, t)R(z) = Ф^, t) + jewdf(z) S (t) + dR0) [A(z) -1] + (. dz dz dz + Ж(0) jewA(z) S (t) + jewdf(0) S (t) [A(z) -1]} + O(e2) dz dz (здесь было использовано разложение ejw = 1 + jew + O(e2)). Учитывая (4), приведя подобные и сократив обе части на jew, запишем df (z) , df (0). XR( z) = - -[A(z) - 1] + XA(z) + O(e). dz dz Отсюда при e ^ 0 получаем дифференциальное уравнение относительно неизвестной функции f(z) ddz) = f» [1 - A( z)]-X[A( z) - R( z)], dz dz решение которого дает следующий результат [3]: f0.-Xf (да) 4 f z 2 dA( z) -X = K dz 2 i 2 (10) где величина к определяется по формуле (7). Этап 3. В (6) сделаем предельный переход при z ^ да. В силу способа построения функции F(w, z, t, e) она является монотонно возрастающей и ограниченной сверху функцией по z. Следовательно, lim 5F(w,z,t,e) = 0. г^да dz ( ' )2 Учитывая это и применяя разложение ejew = 1 + jew +---+ O(e11), получаем: Подставим сюда разложение (9) функции F(w, z, t, e) при z = да, имеем e2 t) + jewXS(t)Ф(w, t) + (jew)2 XS(t) f (да)Ф^, t) = 5t X + ( jew)2 S (t) (jew)2 df (0) dz + O(e3). = Ф^, t )S (t) jewX + Приводя подобные и сокращая на e , получаем XS (t) + 2S 2(t) -Xf (да) dz t) (jw)2 + O(e). ^(w, t) 5t Учитывая (10) и переходя к пределу при e ^ 0, имеем дифференциальное уравнение относительно неизвестной функции Ф^, t): t) = (jw)2 5t " 2 ^(w, t) [XS(t) + ks2(t)] . Решение этого уравнения с учетом начального условия Ф^, t0) = 1, которое получается из условия |R(z) при n = 0, P(n, z, t0) = { 0 при n > 0, имеет вид X j S (x)dx + к| S 2 (x)dx (jwy Ф(w, t) = exp где величина к определяется формулой (7). Отсюда в силу (8) xj S (x)dx + к| S 2 (x)dx (jw)2 F (w, z, t) = R (z )exp что и требовалось доказать. 4. Стационарное распределение вероятностей числа занятых приборов Возвращаясь к функции H(u, z, t), получаем, что при достаточно больших значениях N X j S (x)dx + ^ S 2 (x)dx H(u, z, t) И R(z)exp j juNxjs(x)dx + j- N Функция h(u, t) = lim H (u, z, t) есть характеристическая функция для процесса n(t) - числа событий, наступивших в просеянном потоке к моменту времени t. При достаточно больших значениях N она имеет вид характеристической функции га-уссовского распределения: X j S(x)dx + к j S2 (x)dx h(u, t) и expj juNX^S(x)dx + (jj--N то есть распределение для n(t) в момент времени t аппроксимируется нормальным распределением с математическим ожиданием N xj S (x)dx и дисперсией N X j S (x)dx + N к j S 2( x)dx . Полагая t = T, t0 = -ж, используя (1) и произвольность выбора момента T, получаем, что распределение вероятностей числа занятых приборов в рассматриваемой системе в стационарном режиме аппроксимируется нормальным распределением с математическим ожиданием NU и дисперсией (NU + NkP), где T да b = | S(x)dx = J(1 - В(т) )dт -да 0 есть среднее время обслуживания, а T да Р= | S2(x)dx = J(1 -В(т) )2 dT. -да 0 5. Численные результаты Наиболее интересным является вопрос применимости полученной гауссовской аппроксимации на практике. Очевидно, что точность данной аппроксимации определяется величиной параметра N и улучшается по мере его увеличения. Поскольку получение аналитических формул, явно выражающих или оценивающих точность данного приближения, затруднено, будем производить сравнение асимптотических результатов с результатами имитационного моделирования. В качестве величины для оценки точности аппроксимации распределения выберем расстояние Колмогорова [7] Dq = sup | Fq (x) - F (x)|. x Здесь q - объем выборки, полученной по результатам имитационного моделирования, Fq(x) - эмпирическая функция распределения для данной выборки, F(x) -функция распределения для нормальной случайной величины с найденными выше характеристиками. Указанное моделирование и расчеты были выполнены для различных примеров. Приведем здесь результаты для одного из них. Рассматривается система массового обслуживания с неограниченным числом приборов, на вход которой поступает высокоинтенсивный рекуррентный поток. Длины интервалов между поступлением заявок в этом потоке равны (см. п.1) т = / N, где - случайная величина, имеющая гамма-распределение с математическим ожиданием равным 1 и дисперсией равной 3. Время обслуживания заявки в системе является случайной величиной, имеющей гамма-распределение с математическим ожиданием 1 и дисперсией 2. В таблице приведено сравнение результатов аналитических расчетов и имитационного моделирования для различных значений параметра N: N Аналитический расчет Имитационное моделирование Расстояние Колмогорова среднее ср. кв. отклонение среднее ср.кв. отклонение 1 1 1,442 0,9887 1,330 0,3604 10 10 4,559 9,908 4,392 0,0892 30 30 7,896 30,15 7,824 0,0399 100 100 14,42 100,3 14,55 0,0227 1000 1000 45,59 1001 45,21 0,0119 10000 10000 144,2 9986 143,1 0,0094 На графиках (рис. 1) представлено сравнение полигона относительных частот, построенного по результатам имитационного моделирования, и ряда распределения, полученного на основе гауссовской аппроксимации, для значений N = 1, 10, 30, 100. Рис. 1. Сравнение полигона относительных частот (1) и аппроксимирующего ряда распределения (2) График на рис. 2 демонстрирует убывание расстояния Dq в зависимости от параметра N. Рис. 2. Изменение расстояния Колмогорова Dq в зависимости от параметра N (шкала по N - логарифмическая) На основе сравнения полученных результатов можно сделать вывод, что полученные в работе асимптотические формулы дают достаточно хорошую (Dq < 0,05) аппроксимацию при значениях параметра N от 30 и выше. Заключение Итак, в работе проведено исследование системы массового обслуживания с неограниченным числом приборов, произвольным временем обслуживания и высокоинтенсивным входящим рекуррентным потоком. Показано, что в условии неограниченно растущей интенсивности входящего потока стационарное распределение числа занятых приборов аппроксимируется нормальным распределением, получены характеристики этого распределения. Анализ результатов, полученных по асимптотическим формулам и на основе имитационного моделирования, свидетельствует о достаточно низкой погрешности представленной в работе гауссов-ской аппроксимации при значениях N > 30 .

Скачать электронную версию публикации