Analysis of a queuing system with correlated arrival flows and variable priorities.pdf Теория массового обслуживания представляет собой хороший математический аппарат для решения проблем оптимального распределения некоторого ограниченного ресурса между конкурирующими пользователями. В большинстве существующих работ предполагается, что пользователи являются однородными, в то время как во многих реальных системах имеются потоки пользователей, разнородных по требованиям к времени обслуживания и их важности для системы. Например, в моделях функционирования приемных покоев учреждений здравохранения пациенты делятся на требующих неотложной помощи, скорой помощи и менее срочной помощи [1]. В сетях когнитивного радио имеются потоки лицензированных пользователей и нелицензированных (когнитивных) пользователей [2, 3]. Последние подразделяются на пользователей, требующих и не требующих обслуживавния в режиме реального времени, вновь поступивших и вытесненных с обслуживания и т.д. В моделях функционирования интеллектуальных транспортных систем потоки информации, критичной для безопасности движения, заведомо более важны, чем потоки информационно-развлекательные. Работа таких систем может быть описана в терминах приоритетных систем массового обслуживания. Наряду с рассмотрением различных разновидностей статических относительных и абсолютных приоритетов в последние годы появились исследования систем с динамически изменяющимися приоритетами, в которых во время ожидания запросов пользователей в очереди некоторым детерминированным или рандомизированным образом может происходить изменение изначально назначенного пользователю приоритета. Системам с динамическими изменениями приоритетов запросов посвящены, например, работы [4-11]. Стоит отметить, что в большинстве работ делается практически нереалистичное в современных системах, включая сети телекоммуникаций, предположение о том, что потоки запросов являются стационарными пуассоновскими, в то время как во многих реальных системах потоки не являются стационарными, а имеют высокие коэффициенты корреляции и вариации длин интервалов между моментами поступления. В данной статье исследуется однолинейная система массового обслуживания с коррелированным входным потоком разнотипных запросов с приоритетами. При выборе следующего запроса на обслуживание приоритеты являются относительными. Прерывание текущего обслуживания в случае прихода более приоритетного запроса не допускается. Система имеет конечный буфер, общий для запросов всех типов. При поступлении новых запросов приоритет является рандомизированно абсолютным. В случае заполненности буфера поступающий запрос удаляет из него запрос более низкого приоритета, если таковой имеется, с фиксированной вероятностью, зависящей от типа поступающего запроса. Поступление запросов описывается ММАР-потоком (маркированный марковский входной поток) [12], позволяющим учитывать характерные черты многих реальных потоков, в частности потоков информации в современных телекоммуникационных сетях. Важнейшей особенностью рассмотренной системы является возможность повышения приоритета произвольного запроса во время его пребывания в буфере. Учтена возможность ухода запросов из системы из-за нетерпеливости. В работе [13] была исследована система массового обслуживания с динамически изменяемыми приоритетами и коррелированным входным потоком. Однако в [13] сделано предположение, что запросы всех типов имеют одинаковые требования к обслуживанию. Данное предположение существенно упрощает исследование системы, но в то же время значительно сужает область применения модели. В реальных системах запросы разных типов могут иметь совершенно разный объем данных или работы, что приводит к разному времени обслуживания. В данной статье предусмотрена зависимость интенсивности обслуживания от типа запроса. 22 Дудин А.Н., Дудин С.А., Дудина О.С. Анализ системы обслуживания с коррелированными входными потоками 1. Математическая модель Рассматривается однолинейная система массового обслуживания с конечным буфером, структура которой представлена на рис. 1. Рис. 1. Структура исследуемой системы Fig. 1. Structure of the system under study p*dt=l,K. Входной поток запросов K типов задается MMAP-потоком. Этот процесс является обобщением более известного марковского входного потока [14-18] на случай разнотипных запросов. Использование такой модели входного потока вместо широко популярной модели суперпозиции стационарных пуассоновских потоков, являющейся очень частным случаем MMAP-потока, позволяет учитывать флуктуацию мгновенной интенсивности потока, корреляцию длин последовательных интервалов между моментами поступления и их вариацию. Запросы к, к = 1, K, типов поступают в MMAP-потоке, который определяется неприводимой цепью Маркова ѵ,, t > 0, с непрерывным временем и конечным пространством состояний {1,2,...,W}, а также набором квадратных матриц Dk, к = 0, K. Обозначим через X среднюю интенсивность поступления запросов, а через Xk среднюю интенсивность поступления запросов типа к, к = 1, K, Формулы для нахождения данных величин, а также таких характеристик MMAP-потока, как коэффициеты корреляции и вариации, приведены в [18]. Если в момент поступления запроса любого типа в систему прибор свободен, то этот запрос сразу начинает обслуживание. Для хранения запросов различных типов, поступающих, когда прибор занят, в системе имеется буфер емкостью R. Если прибор занят, но буфер не заполнен, запрос любого типа помещается в буфер. Конкретного ограничения на число запросов каждого типа, находящихся в буфере одновременно, нет, но общее количество запросов, находящихся в буфере, не должно превышать его емкость R. Очевидно, что в системе одновременно может находится не более R + 1 запросов (один запрос на обслуживании и R запросов в буфере). Запросы разных типов имеют разные приоритеты. Считаем, что приоритет типов запросов уменьшается с увеличением номера типа. То есть запросы первого типа имеют наивысший приоритет среди всех типов запросов, а запросы типа K имеют самый низкий приоритет. Приоритет определяет порядок приема запроса в систему, когда буфер заполнен, и порядок выбора запроса из буфера на обслуживание. При выборе запроса из буфера на обслуживание приоритет предполагается относительным. Если в момент завершения обслуживания в буфере присутствуют запросы первого типа, то один из этих запросов начинает обслуживание. Запрос типа к, к > 2, может начать обслуживание, только если в буфере отсутствуют запросы типов 1, 2,..., k-1. Обслуживание любого запроса не может быть прервано в случае поступления запроса, имеющего более высокий приоритет. Предполагается также, что при принятии в систему запросы типа к, к = 1, K, имеют рандоми-зированно абсолютный приоритет над запросами типа l, l = к +1,K. То есть если в момент прихода запроса типа к прибор занят, число запросов в буфере равно R и нет запросов типа l, l = к +1, K, то поступивший запрос покидает систему (теряется). Если же в буфере есть запросы типа l, l = к +1,K, то поступивший запрос с вероятностью qk принимается в буфер, а один из запросов из буфера с самым низким приоритетом теряется. С дополнительной вероятностью 1 - qk поступивший запрос 23 Математическое моделирование /Mathematical modeling покидает систему, несмотря на наличие в буфере запросов с более низким приоритетом. Такая рандомизация имеет целью уменьшить потери низкоприоритетных запросов. Считаем, что во время пребывания в буфере запросы типа к, к = 2, K, могут увеличить свой приоритет. Полагаем, что после экспоненциально распределенного с параметром ак времени запрос типа к становится запросом типа l - к-1 с вероятностью pkl, l = 1, к -1, £ рк1 = 1, к = 2, K. ’ і=1 Запросы, находящиеся в буфере, могут проявлять нетерпеливость и покидать систему без обслуживания независимо от других запросов, если время ожидания слишком велико. Запрос типа к покидает систему без обслуживания по истечении экспоненциально распределенного с параметром jk времени ожидания, ук> 0. Предполагается, что если запрос меняет приоритет, то отсчет его времени «терпеливости» начинается с самого начала с параметром, соответствующим новому приоритету. Время обслуживания запроса типа к, к = 1,K, прибором имеет экспоненциальное распределение с параметром ^к ,0 0, где it, it = 0,R + 1, - число запросов в системе ; mt, mt = 1, K, - тип обслуживающегося запроса; vt,vt = 1,W, - состояние управляющего процесса MMAP-потока; nf) - число запросов типа к в буфере, п(к) = 0, max{0,it -1}, K £ n(l) = max{0, i -1}, к = 1, K, в момент времени t. і=1 Цепь Маркова \\t, t > 0, является неприводимой и имеет конечное пространство состояний. Следовательно, стационарные вероятности состояний системы существуют при любых значениях параметров системы: я(і, m, v, n*1,..., ПK)) = limP{it = i, m = m, vt= v, nf1 = n*1,..., n\\K= ПK)},i = 0,R +1, m = 1, K, v = 1, W, n^k) = 0,max{0, i -1}, £n® = max{0, i -1}, к = 1, K. і=1 Из этих вероятностей, перенумерованных в обратном лексикографическом порядке компонент п^\\...,п.(К\\сформируем вектор-строки п(і.т.ѵ). ѵ = І.ІѴ. и векторы л, следующим образом: K я(і,m) = (я(і,m,1),я(і,m,2),...,я(і,m,W)), m = 1,K, л, = (я(і,1),я(і,2),...,я(і,K)), i = 2,R +1, Я0 = (я(0, 0,1,0), я(0, 0,2,0),., я(0, 0, W, 0)), я(1, m) = (л(1, m, 1,0), л(1, m, 2,0),., я(1, m, W, 0)), Я1 = (я(1, 1), я(1, 2),., я(1, K)). Векторы я удовлетворяют следующей системе линейных алгебраических уравнений: (^ЯИ- • .ЯД+1 + = 0, (+ЯИ- • ^+++ = + где Q - инфинитезимальный генератор цепи Маркова St, t > 0, e - вектор-столбец, состоящий из единиц, 0 - вектор-строка, состоящая из нулей. Для решения данной системы может быть применен, например, алгоритм, описанный в [17]. Теорема 1. Инфинитезимальный генератор Q = (Q, j). ^-^ имеет блочно-трехдиагональную структуру, где ненулевые блоки Qt j, |i - j| < 1, определяются следующим образом: 24 Дудин А.Н., Дудин С.А., Дудина О.С. Анализ системы обслуживания с коррелированными входными потоками Qo,o - Do, Q1,1 -1к ® D0 С ® Iw, Qjj - Ік ® D0 ® It C ® i -1 lWT. i -1 +1 KW ®(Ү-1 к qr+i,r+i - Ік ® Do ® -T C ® iwtr + ikw ® (yr +1 r ) + rк ® 2( Rk ® (1 qk ) It R R k-Л L 1 Q0,1 - 2 (hk ® Dk ), Qi,i+1 - IK ® 2 (Dk ® Д-1 Фк )X i - 1 R k-1 k-1 I i-1), i - 2, R, +qkEk ), Здесь Ii -L (y), i -1, R, Q1,0 - Ce ® -W, Qi,i-1 - C ® -W ® Ei-1 + -KW ® Li-1(y), І - 2,R + 1 единичная матрица размера i; ® - символ Кронекера произведения матриц [18]; - матрица, элементы которой определяют интенсивности переходов, когда запрос покидает буфер из-за нетерпеливости; Y - Y (H), i -1, R, - матрица, элементы которой определяют интенсивности переходов, происходящих, когда запрос повышает свой приоритет. Матрица H размера K х K определяет интенсивность возрастания приоритетов и имеет все нулевые элементы, кроме элементов (H) j - pt jаг-,i - 2,K , j - 1,i -1; Ai(hk), i - 0,R -1, - матрица, элементы которой определяют вероятности перехода в момент поступления в систему нового запроса типа k, когда в буфере находится i, 0 < i 1, являются нулевыми матрицами. Диагональные элементы матриц Qu, i - 0, R +1, отрицательны, а модули этих элементов определяют суммарную интенсивность выхода цепи из соответствующего состояния. Если система пуста (i - 0) , то цепь Маркова ^, t > 0, может выйти из своего состояния только тогда, когда: (а) управляющий процесс MMAP-потока совершает выход из текущего состояния; интенсивности таких выходов определяются модулями диагональных элементов матрицы D0. Если i -1, т.е. запрос находится на обслуживании, а буфер пуст, то цепь Маркова ^, t > 0, может выйти из своего состояния только в случае (а), описанном выше; (б) в случае окончанияния обслуживания. Интенсивности таких выходов определяются модулем диагональных элементов матрицы Ік ® D0 в случае (а) и матрицы C ® IW в случае (б). Если i - 2,R, прибор занят и в буфере есть хотя бы одно свободное место, то цепь Маркова ^, t > 0, может выйти из своего состояния по тем же причинам, что и в предыдущем случае (интенсивности таких переходов определяются модулями диагональных элементов матриц А- ®D0 ®Іг для случая (а) и матриц C ®IWT для случая (б)). Также возможно, что (в) какой-то запрос из буфера может изменить свой приоритет или покинуть буфер из-за нетерпеливости, интенсивности таких переходов задаются модулями диагональных элементов матриц IKW ® 11. Если 25 Математическое моделирование /Mathematical modeling i = R +1, то прибор занят и буфер заполнен полностью. Значит, цепь Маркова \\t, t > 0, может покинуть свое состояние по причинам (а), (б) и (в) (интенсивности таких переходов определяются модулями диагональных элементов матриц Ік ®D0 ®ІТ , C® IWT и IKW ® IR соответственно). Также R R возможны ситуации (г), когда приходит запрос типа k и уходит из системы, несмотря на возможное наличие в буфере запросов с более низким приоритетом, или (д) - этот запрос пытается попасть в буфер и вытеснить запрос с самым низким приоритетом. Интенсивности таких выходов определяются диагональными элементами матрицы ^K=i(1- 4k )(Ік ® Dk ® Іт ) в случае (г) и матрицы 2 K=i4k(Ік ® Dk ® Ek) в случае (д). Недиагональные элементы матриц Q ., i = 0, R +1, неотрицательны и определяют интенсивности переходов цепи Маркова ^, t > 0, не приводящие к изменению числа запросов i в системе. Такими переходами являются: переходы управляющего процесса MMAP-потока без генерации запроса (интенсивности определяются недиагональными элементами матрицы D0, если i = 0, матрицы Ік ® D0 при i = 1, матрицы Ік ®D0 ®Іт при i = 2, R +1); переходы из-за смены приоритета неко- 1i-1 торым запросом в буфере (интенсивности определяются элементами матрицы IKW ® Yi-1, i = 2,R +1); переходы, когда запрос при поступлении застает заполненный буфер и покидает систему или вытесняет запрос с наименьшим приоритетом из буфера (интенсивности определяются недиагональными элементами матрицы XK=1(IK ® Dk) ® [(1 - qk)Іт + qkEk ], i = R +1). Таким образом, после некоторых R алгебраических преобразований с учетом приведенных выше объяснений мы получаем вид диагональных блоков Qu, i = 0, R +1, генератора Q. Элементы матриц Qii+1, i = 0, R, неотрицательны и определяют интенсивности переходов цепи Маркова 41, t > 0 приводящих к увеличению количества запросов в системе на единицу. Такие переходы происходят, когда в систему поступает запрос любого типа. Интенсивности этих переходов определяются матрицей XkK=1(hk ® Dk), если система пуста, и матрицей XK=1IK ® Dk ® Ai-1(hk), если в системе находится i, i = 1,R, запросов. Элементы матриц Qu-1, i = 1, R +1, неотрицательны и определяют интенсивности переходов цепи Маркова 4t, t > 0, приводящих к уменьшению количества запросов в системе на единицу. Такое уменьшение может произойти из-за (а) успешного обслуживания запроса или (б) ухода запроса из буфера из-за нетерпеливости. В случае (а) интенсивности переходов задаются матрицей Ce ® IW, если буфер пуст, и матрицей C ® IW ® E--1, иначе. В случае (б) интенсивности переходов определены только для случая i = 2, R + 1, и задаются элементами матриц ІKW ® Li-1(y). Теорема доказана. 3. Характеристики производительности R+1 Среднее число запросов в системе вычисляется по формуле L R+1 X inie. Среднее число запросов i=1 в буфере вычисляется по формуле Nbuf = X (i - 1)я;е. Среднее число запросов типа k в буфере i=2 вычисляется как N( k) = Nbuf = R+1 X ni (IKW i=2 ® L,-1(hk ))e, k = 1, к. Средняя интенсивность выходного потока R+1 к успешно обслуженных запросов определяется как Yserv = X X^-mn(i, m)e. Средняя интенсивность i=1 m=1 выходного потока запросов, которые покинули буфер из-за нетерпеливости, вычисляется по формуле 26 Дудин А.Н., Дудин С.А., Дудина О.С. Анализ системы обслуживания с коррелированными входными потоками R+1 X Xleave = 2 Я(Ikw ®L_1(у))е. Вероятность потери произвольного запроса находится как Ploss = 1----. i=2 X Вероятность потери произвольного запроса из-за нетерпеливости находится как р X X leave X leave_loss Интенсивность выходного потока запросов типа к, которые покинули буфер из-за нетерпеливости, определяется как X\\elve = 2 Яi (IkW ® Li_1 ІУк )) е = УkNbuf, к = 1K, где ук - вектор-строка размера K І=2 со всеми нулевыми элементами, кроме k-го, который равен ук. Средняя интенсивность переходов запросов типа l, l = к +1,K, в тип к, к = 1,K _ 1, вычисляется как X^ = 2 ^iNbUfPik. Вероятность l=к+1 U , потери произвольного запроса типа k из-за нетерпеливости вычисляется по формуле х(к) _ Pieave-ioss =-, к = 1,K. Здесь предполагается, что X= 0. Вероятность потери произвольного хк +X(2 запроса типа k по прибытии без попытки вытеснить запрос с более низким приоритетом равна Pu02_nO_pUsh = (1 _ Ук )X~k'KR+1(IK ® Dk ® р )е, к = 1, K. Вероятность потери произвольного запроса типа к по прибытии, несмотря на неудачную попытку вытеснить запрос с более низким приоритетом, равна P^_push=qkXklTiR+l(IK ®Dk®Ek)e, к = \\,К, где матрица Ёк имеет все нулевые элементы, кроме диагональных элементов, которые равны диагональным элементам матрицы Ек. Вероятность потери пр°извольног° запр°са по прибытии равна Parr _loss =X 1 2Хк (Pl0SS_no_ push + P0S_ push У Вероятк=1 ность потери произвольного запроса типа к по прибытии равна P0rr_loss = P0oSS_push + Phl_no_push, к = 1,К. Вероятность того, что запрос произвольного типа к по прибытии встретит полный буфер >_1. и вытеснит запрос с более низким приоритетом, равна P^h-out =

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