Numerical investigation of queuing models with delayed feedbacks.pdf Модели систем массового обслуживания (СМО) с обратными связями [1, 2] адекватно описывают процессы передачи информации в телекоммуникационных сетях. Это объясняется тем, что в этих сетях ошибочно переданные данные (пакеты, кадры и т.д.) требуют повторной передачи. При этом в зависимости от принятого протокола эти данные могут быть повторно переданы либо мгновенно, либо с некоторой задержкой. В первом случае потребуется использовать модели СМО с мгновенной обратной связью [3-14], а во втором - СМО с отсроченной обратной связью [15-22]. Анализ указанных работ показал, что для стационарного распределения вероятностей состояний СМО с обратными связями не удается получить простые расчетные формулы даже для моделей систем с числом каналов больше двух. Поэтому разработка эффективных методов для численного анализа многоканальных СМО с обратными связями является актуальной проблемой. В данной работе предлагаются точный и приближенный методы анализа характеристик модели многоканальной СМО с отсроченной обратной связью. Подобная модель ранее была изучена в [22], где предполагалось, что если в момент поступления первичного вызова (т.е. вызова, который поступает извне) все каналы системы заняты, то он теряется с вероятностью, равной единице. В настоящей работе предполагается, что в этих случаях такие вызовы, согласно схеме Бернулли, либо отправляются в орбиту для повторения своего запроса для обслуживания, либо теряются. Кроме того, здесь же корректируются технические ошибки, допущенные в работе [22]. 1. Описание модели системы и постановка задачи На вход многоканальной системы, которая содержит N, 1 < N >^. В силу указанного допущения получаем, что интенсивности переходов между состояниями внутри строк в диаграмме переходов модели намного превышают интенсивности переходов между ними (см. рис. 2). На основе этого факта в работе [22] используется следующее расщепление исходного ПС: R E = У Er , Erр|Er, = 0,если r * r', (11) r=0 где Er = Кn,r) e E :n = 0,1,...,N j,r = 0,1,...,R. Иными словами, осуществляется расслоение графа переходов по строкам (см. рис. 1). На основе расщепления (11) вводится следующая функция укрупнения: U ((n, r)) =< r >, (n, r)e Er, где < r > является укрупненным состоянием, которое включает в себе все состояния из класса Er и обозначается как Q = |< r >:r = 0,1,...,Rj. Согласно алгоритму приближенного расчета стационарного распределения 2D MC [22] находим, что вероятности состояний исходной модели определяются следующим образом: p (n, r)«pr (n)p(< r >), (12) где pr (n) - вероятность состояния (n, r) внутри расщепленной модели с пространством состояний Er, а p(< r >) - вероятность укрупненного состояния < r >eQ. Из схемы разбиения (11) видно, что все расщепленные модели представляют собой идентичные одномерные процессы размножения и гибели (One-Dimensional Birth Death Process, 1-D BDP), так как в классе состояний Er вторая компонента является постоянной. Поэтому при изучении расщепленной модели с ПС Er микросостояние (n, r)e E исходной модели может быть задано лишь одной компонентой n, n = 0,1,...,N . Интенсивность перехода между состояниями n и n' в расщепленных моделях с ПС Er обозначается через qr (n,n'), n,n' = 0,1,...,N,n * n'. Из (2) и (3) заключаем, что для всех расщепленных моделей с ПС Er,r = 0,1,...,R -1, при этом эти величины определяются одинаковым образом как А, если n' = n +1, qr (n,n') = ) = -j vn N v' Pr (n) = ZT, n = 0,1,...,N. (16) n\\/ t0 i! Тогда с учетом (2), (3), (15) и (16) после определенных математических выкладок получаем Л( r1), если r2 = r +1, r1M(r ), если r2 = r -1, (17) 0 в остальных случаях, где Л( r ) = „Z na( n )p( n ) + Xc( r )p( N), M( r ) = ^(1 -(1 -P( r ))pr ( N)). n=1 Из (17) видно, что вероятности укрупненных состояний вычисляются как вероятности состояний 1-D BDP с переменными параметрами, т.е. p(< r >) = - П Л( 1 - 1)Р(< 0 >), r = 1,...,R, (18) V } r \\ if M(i) V ' R где p(< 0 >) находится из условия нормировки, т.е. Z^(< r >) = 1. r=0 Тогда с учетом соотношений (7)-(10), (12), (15), (16) и (18) после определенных математических выкладок получим следующие приближенные формулы для расчета искомых характеристик системы: PBp «P(N)Z(1 -°(i))p() + Eb (v,N)p(< R >) ; (19) i=0 PB r *p(N)ZP( r )p(< r >) + Eb (v, N)p(< R >)p(R); (20) r=1 N R N N Nav nZPr (n )P(< r >) = (1 -P(< R >))Z ПР(п ) + P(< R >)Z npR (n ) = n=1 r=0 n=1 n=1 (21) N = (1 - p(< R >))Znp(n) + v (1 - Eb (v,N))p(< R >); n=1 Lo «Zгр(< r >) . (22) r =1 В (19)-(22) и далее EB (v,N) означает В-формулы Эрланга для системы M/M/N/N с нагрузкой v , т.е. EB (v,N) = pR (N) . Отметим, что при выводе формулы (21) учитывается, что множитель N ZkpR (k) представляет собой среднее число занятых каналов в системе M/M/N/N с нагрузкой v erl, k=1 которое равно v(1 -EB (v,N)) . Отметим, что когда вероятности a( n), a( r) и P( r) являются постоянными величинами, т.е. если a( n ) = a для всех n = 1,..., N, Р( r ) = Р и с( r ) = ^ для всех r = 1,..., R, то полученные выше формулы упрощаются. Действительно, в этом случае вероятности состояний pr (n) не зависят от индекса r при 0 < r < R -1 и совпадают с вероятностями состояний классической модели Эрланга M/M/N/N с нагрузкой v = v/(1 - a) , т.е. эти вероятности определяются так: N, v' n (23) р( п)= -J I т' п = 0'1'-' N. п! i=0 Вероятности состояний pR(n), п = 0,1,...,N,внутри расщепленной модели с ПС ER вычисляются с помощью (16). Тогда с учетом (2), (3), (16) и (23) после определенных математических выкладок получаем, что в этом случае интенсивности переходов между укрупненными состояниями определяются как Л1, если r2 = r +1, r1M1 (r), если r2 = r -1, (24) 0 M1 ( r ) = q(< r >< r2 >) = в остальных случаях, где Л1 =^av (1 - EB (v, N)) + A,aEB (v, N), IM1, если 1 < r < R -1, |М 2, если r = R, M1 = л(1 -(1 -P)Eb (v,N)), M2 =л(1 -(1 -P)Eb (v,N)). Из (24) заключаем, что в этом случае вероятности укрупненных состояний вычисляются так: если 1 < r < R -1, p(), M1 ^ Л V p(< r >) = (25) 1 R! vM1 j •Mlp(< 0 >), если r = R, M2 V 7 где p(< 0 >) находится из условия нормировки. В такой модели характеристика (10) вычисляется с помощью (22) с учетом формулы (25), а остальные характеристики (7)-(9) определяются из следующих простых формул: PBp « (1 -a)p(N)(1 - p()) + Eb (v,N)p(< R >) ; (26) PB r« P(p(N)(1 - p(< 0 >) - p(< R >)) + Eb (v,N)p()); (27) Nav « v(1 - Eb (v,N))(1 - p(< R >)) + v(1 - Eb (v,N))p(< R >). (28) Важно отметить, что в случаях, когда указанные выше вероятности являются постоянными величинами, удается получить явные формулы и для расчета характеристик моделей с бесконечным размером орбиты (т.е. R = да). Заметим, что в отличие от модели с конечным размером орбиты, здесь вызовы, которые требуют повторного обслуживания, всегда принимаются в орбиту. Это означает, что все расщепленные модели с ПС Er, r = 0,1,..., являются идентичными, т.е. вероятности состояний внутри расщепленных моделей определяются из формулы (23). С учетом (23) из (17) получим, что в данной модели интенсивности переходов между состояниями укрупненной модели определяются так: Л1, (29) если r2 = r +1, q (< r > < r2 >) = если r2 = r -1, 0 в остальных случаях, Из соотношений (29) видно, что вероятности укрупненных состояний определяются как вероятности состояний модели Эрланга M/M/да с нагрузкой Т = Л1/M1 Т r p(< r >) =-, r = 0,1,... V ) r! Таким образом, с учетом соотношений (7)-(10), (23) и (25) после определенных математических выкладок получим следующие приближенные формулы для расчета искомых характеристик системы с бесконечным размером орбиты: PBp =(1 -a) EB (V, N) ; (31) PBr «PEb (v, N)(1 - e"*) ; (32) Nav «V(1 -eb (v,N)); (33) La « T . (34) В отличие от системы с конечным размером орбиты, здесь вероятность потери первичных вызовов и среднее число занятых каналов системы не зависят от интенсивности поступления повторных вызовов с орбиты (см. формулы (31) и (33)). Это объясняется тем, что согласно нашему допущению интенсивность поступления первичных вызовов существенно больше, чем интенсивность поступления повторных вызовов. Вместе с тем эти величины зависят от интенсивности ухода вызовов в орбиту, так как на них косвенно влияет число вызовов в орбите. Вероятность потери повторных вызовов и их среднее число в орбите зависят от всех структурных и нагрузочных параметров системы (см. формулы (32) и (34)). Выше мы рассматривали случай линейной интенсивности поступления повторных вызовов с орбиты, т.е. считали, что если суммарное число таких вызовов в орбите равно r, то интенсивность их поступления равна rq . Вместе с тем можно исследовать и модель с постоянной интенсивностью поступления повторных вызовов с орбиты, т.е. предположить, что лишь вызов, который стоит в очереди повторных вызовов, может генерировать запрос для обслуживания. В таком случае интенсивность поступления повторных вызовов с орбиты не зависит от числа вызовов в ней и всегда равна q. В этой модели элементы ПМ также определяются из формул (2) и (3), однако здесь в правой части данных формул в последних строках следует учитывать, что r = 1. При точном подходе соответствующие замены должен быть учтены и в СУР (4)-(6). Аналогичные изменения необходимо учитывать и в полученных приближенных формулах в случае орбиты конечного размера. Однако в случае бесконечного размера орбиты требуется выполнение условия эргодичности модели, т.е. необходимо выполнение условия T < 1. Отметим, что выполнение последнего условия трудно проверить на практике. Вместе с тем можно показать, что если выполняется легко проверяемое условие Xmax , 0. Иными словами, если время пребывания r-вызова превышает допустимое предельное значение, то он покидает орбиту с вероятностью, равной единице. Для этой модели элементы ПМ соответствующей двумерной цепи Маркова с ПС (1) определяются аналогично (2) и (3), но при этом следует учесть, что здесь появляются новые переходы из состояния типа (n, r), r > 0, в состояние (n, r -1) с интенсивностью rx . Из-за ограниченности объема статьи эта модель здесь не рассматривается. 4. Численные результаты Полученные формулы позволяют изучить поведение характеристик системы относительно изменения всех ее параметров. Из-за ограниченности объема статьи здесь предполагается, что параметры P(r), r = 1,2,...,R, имеют релейный характер изменения, т.е. они определяются так: 1, если r > K, [0, если r < K, где K, 1 < K < R, является известной величиной. Соотношение (35) описывает схему, согласно которой повторные вызовы покидают орбиту, если в моменты их генерации все каналы системы оказываются занятыми и при этом число вызовов в орбите больше некоторой величины K, 1 < K < R. Этой схеме адекватно соответствует реальное поведение вызовов в СМО с обратной связью. Проведено большое количество вычислительных экспериментов для изучения зависимости характеристик системы от порогового параметра K при различных комбинациях изменения исходных данных. Результаты этих экспериментов показаны на рис. 3, где постоянные исходные данные выбирались так: N = 10,R = 50, ц = 30,^ = 4,с = 0,3. P( r ) = (35) Т-1-1-1-Г1- О 10 Я М Ч W lg(PB 14 М И 4» №' a й b с d Рис. 3. Зависимость характеристик системы от параметра K Fig. 3. Dependence of system characteristics on parameter K м.. Рассмотрены четыре серии экспериментов для пары параметров (А, а) : 1) (А,а) = (120; 0,7); 2) (А,а) = (120; 0,3); 3) (А,а) = (40; 0,7); 4) (А,а) = (40; 0,3). На графиках символ 0 соответствует первой серии, ° - второй серии, ♦ - третьей серии, • - четвертой серии. Из графиков видно, что для выбранных исходных данных только вероятность потери повторных вызовов (PBr) существенно зависит от значения порогового параметра K (см. рис. 3, а), а остальные характеристики для трех серий экспериментов, кроме первой, являются почти постоянными величинами. Во всех сериях экспериментов вероятность потери повторных вызовов является убывающей относительно порогового параметра K, что вполне логично, ибо увеличение параметра K приводит к уменьшению шансов вызовов с орбиты быть потерянными. При этом с ростом нагрузки системы (v) и вероятности возвращения вызовов в орбиту после окончания обслуживания (а) растет и вероятность потери повторных вызовов. Отметим, что при а = 0,3 для обеих нагрузок эта функция практически равна нулю для больших значений параметра K. Среднее число повторных вызовов в орбите (Lo) зависит от значения порогового параметра K только в первой серии экспериментов и при этом лишь при его критических значениях, близких к максимально возможному значению R (см. рис. 3, b). Для указанной серии экспериментов при критических значениях K орбита оказывается почти полной. Как и для функции PBr, здесь также с ростом нагрузки системы (v) и вероятности возвращения вызовов в орбиту после окончания обслуживания (а) растет и среднее число повторных вызовов в орбите. В первой серии экспериментов несколько неожиданным является поведение функции Nav относительно параметра K (см. рис. 3, с). Так, при критических значениях параметра K она, хоть и с очень малой скоростью, начинает уменьшаться. Этот факт объясняется тем, что поскольку в этой серии экспериментов орбита оказывается почти полной (см. рис. 3, а), то при критических значениях параметра K вызовы с орбиты теряются часто и потому получается малая интенсивность поступления с орбиты, иными словами, при критических значениях параметра K функция Nav начинает уменьшаться. Уменьшение значений функции PBp (с очень малой скоростью) относительно параметра K при его критических значениях (см. рис. 3, d) объясняется тем, что при этих значениях уменьшается и среднее число занятых каналов (т.е. функция Nav). Отметим, что с ростом нагрузки системы (v) и вероятности возвращения вызовов в орбиту после окончания обслуживания (а) растут обе функции - Nav и PBp . Заключение В работе изучаются математические модели многоканальных СМО с отсроченными обратными связями. Поступающие извне вызовы принимаются для обслуживания при наличии хотя бы одного свободного канала, иначе они, согласно схеме Бернулли, либо покидают систему, либо уходят в орбиту. После завершения обслуживания вызовы, согласно схеме Бернулли, либо покидают систему, либо уходят в орбиту и оттуда генерируют запросы в случайные моменты времени. Изучены модели с конечными и бесконечными размерами орбиты для пребывания повторных вызовов. Разработаны точный и приближенный методы расчета характеристик рассмотренных моделей и даны результаты численных экспериментов. В качестве направлений дальнейших исследований можно указать изучение моделей с коррелированными потоками, а также моделей с раздельными орбитами для первичных и повторных вызовов. Благодарность. Автор выражает искреннюю благодарность члену-корреспонденту НАН Азербайджана, доктору технических наук, профессору А.З. Меликову за постановку задачи и полезные обсуждения результатов работы.

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