Open Markov queueing networks with control queues and quarantine node.pdf Системы и сети массового обслуживания позволяют моделировать и анализировать функционирование различных реальных объектов, осуществляющих обслуживание: сети связи, телекоммуникационные и информационные сети и т.д. В настоящее время весьма актуальным является вопрос защиты информации, использования антивирусного программного обеспечения, которое обнаруживает и обезвреживает вредоносные объекты и угрозы для систем и сетей. Ранее исследованы сети массового обслуживания, позволяющие учитывать ситуации, когда ожидающие в очереди заявки, обладая некоторым дефектом, становятся временно неактивными [1, 2] или обслуживающий прибор реагирует на вредоносные заявки сменой режима обслуживания [3]. В настоящей работе исследуются сети массового обслуживания, позволяющие описать функционирование подобного программного обеспечения с помощью введения очередей, в которых производится проверка всех поступающих объектов с последующим обезвреживанием вредоносных объектов в карантине. В работе [4] рассматривается модель с карантинным узлом, в который направляются заявки, признанные нестандартными в очередях узлов, при этом возможна ситуация, когда заявка будет направлена на обслуживание в узле, не успев пройти проверку. В настоящей работе контрольная очередь присутствует в каждом узле, что позволяет учитывать ситуацию, когда все поступающие заявки проходят предварительную проверку, сканирование до того, как они будут допущены к обслуживанию. Исследуется открытая марковская сеть, в которую поступает пуассоновский поток заявок. Узлы состоят из двух очередей: контрольной очереди и очереди для обслуживания. Заявки, поступая в узел, увеличивают длину контрольной очереди узла на единицу. В контрольной очереди узла производится проверка поступивших заявок, при обнаружении опасности заявка направляется в карантинный узел для устранения проблемы, в противном случае заявка присоединяется к обычной очереди узла. 1. Изолированный узел 1.1. Изолированный узел с контрольной очередью Рассмотрим систему массового обслуживания, в которую поступает пуассоновский поток заявок с параметром X. В системе формируются две однолинейные очереди: контрольная очередь и очередь к обслуживающему прибору. Каждая поступающая заявка присоединяется к контрольной очереди, где проверяется экспоненциальным прибором на стандартность. Времена проверки независимы, не зависят от процессов поступления, обслуживания и имеют показательное распределение с параметром v, v -некоторая положительная постоянная. Дисциплина проверки заявок произвольная. Каждая заявка после окончания проверки либо с вероятностью p признается нестандартной и покидает систему, либо с вероятностью 1 - p присоединяется к очереди стандартных заявок. Времена обслуживания заявок в системе независимы, не зависят от процессов поступления, проверки и имеют показательное распределение с параметром ц. Порядок обслуживания заявок произвольный. Функционирование рассматриваемой системы массового обслуживания в момент времени t описывается случайным процессом x(t) = (m(t), n(t)), где m(t) - количество заявок в контрольной очереди в момент времени t, n(t) - количество заявок в обычной очереди в момент времени t. Тогда x(t) - однородный марковский процесс с непрерывным временем и счетным пространством состоянийX = {x = (m, n): m, n > 0}. Предположим, что {p(x), x e X} - стационарное распределение вероятностей состояний процесса x(t). Уравнения равновесия для стационарных вероятностей имеют следующий вид: p(m, n) X- -vI, = p(m -1, n)U{m^0} + p(m,n + 1)ц- _ц1{и*0} ^ vl{m*0) +p(m +1, n)vp + p(m +1, n -1)v(1 - p)I{^0}, (m, n) e X. Теорема 1. При выполнении неравенств X < 1, Wzp. < 1 V ц марковский процесс x(t) эргодичен, а стационарное распределение вероятностей состояний системы имеет следующий вид: p(m,n) =| -lmf^ V J | Ц f Л 1 - X V X(1 - p) ц 1 - Доказательство проводится стандартным образом - подстановкой стационарных вероятностей в уравнения равновесия. Условие эргодичности получено из эргодической теоремы Фостера. 1.2. Изолированный карантинный узел Рассмотрим систему массового обслуживания, в которую поступает пуассоновский поток нестандартных заявок с параметром X. Времена обслуживания заявок в системе независимы, не зависят от процессов поступления и имеют показательное распределение с параметром ц. Порядок обслуживания заявок произвольный. Функционирование рассматриваемой системы массового обслуживания в момент времени t описывается случайным процессом n(t), где n(t) - количество заявок в системе в момент времени t. Тогда n(t) - однородный марковский процесс с непрерывным временем и счетным пространством состояний X = {n, n > 0}. Предположим, что {p(n), ne X} - стационарное распределение вероятностей состояний процесса n(t). Уравнения равновесия для стационарных вероятностей имеют следующий вид: p(n) X + ц1{и^0} = p(n - 1)XI{^0}+ p(n + 1)ц, n e X. Теорема 2. При выполнении неравенства X < 1 ц марковский процесс n(t) эргодичен, а стационарное распределение вероятностей состояний системы имеет следующий вид: f X >n 1-- . ц j f Л X p(n) = ц Доказательство проводится стандартным образом - подстановкой стационарных вероятностей в уравнения равновесия. Условие эргодичности получено из эргодической теоремы Фостера. 2. Открытая сеть Рассмотрим открытую сеть, состоящую из N узлов первого типа со структурой, описанной в пункте 1.1, и (N + 1)-го узла второго типа со структурой, описанной в пункте 1.2. В сеть поступает пуас-соновский поток заявок с параметром X. Каждая заявка независимо от других заявок направляется в i-й узел с вероятностью p0i (i = 1, N). Очевидно, что £/=1 p0i = 1. Каждая заявка, поступающая в i-й узел первого типа, присоединяется к контрольной очереди, где проверяется на стандартность. Времена проверки независимы, не зависят от процессов поступления, обслуживания и имеют показательное распределение с параметром vi, vi - некоторая положительная постоянная (i = 1, N). Каждая заявка после окончания проверки в i-м узле с вероятностью pi признается нестандартной и независимо от других заявок мгновенно направляется в очередь (N + 1)-го узла, а с вероятностью 1 - pi присоединяется к очереди стандартных заявок в i-м узле. Стандартные заявки обслуживаются экспоненциальным прибором, времена обслуживания заявок прибором i-го узла независимы, не зависят от процесса поступления и имеют показательное распределение с параметром ц,- (i = 1, N). Порядок обслуживания заявок произвольный. Каждая заявка после завершения обслуживания в i-м узле независимо от других заявок мгновенно направляется в j-й узел с вероятностью pij, а с вероятностью pi0 покидает сеть (£N= р^ + pi0 = 1, i = 1, N). В (N + 1)-м узле, который назовем карантином, осуществляется восстановление качеств (лечение) нестандартных заявок или их обезвреживание. Время такого обслуживания имеет показательное распределение с параметром ц№1. Порядок обслуживания произвольный. Каждая заявка после обслуживания в (N + 1)-м узле независимо от других заявок мгновенно направляется в очередь j-го узла с вероятностью pN+ij, т.е. «вылечивается» и продолжает движение по сети, а с вероятностью pN+i0 обезвреживается, т.е. покидает сеть (£ N= Pn+1 j + Pn+10 = 1). Состояние сети в момент времени t характеризуется вектором x(t) = (X1(t), X2(t), ..., XN+1(t)), где xi(t) = (mi(t), ni(t)) - состояние узла первого типа в момент времени t, mi(t) - число заявок в контрольной очереди, ni(t) - число заявок очереди на обслуживание в i-м узле в момент времени t (i = 1, N); xN+1(t) = nN+1(t) - число заявок в карантинном (N + 1)-м узле в момент времени t. Процесс x(t) - однородный марковский процесс с непрерывным временем и не более чем счетным пространством состояний X = X1 х X2 х ... х XN+1, где Xi = {x,- = (mi, n) mi, ni > 0, i = 1, N }, XN+1 = {xN+1 = = nN+1: nN+1 > 0}. Уравнения трафика имеют вид е,- = P0i + £ е j(1" P})P}1 + еn+1 Pn+1i, i = Ъ N, j=1 N еN+1 = £ S jPj . j=1 Введем следующие обозначения: Р 0i = Р 0i, Р* = (1 " Pj )Рji, О PjN+1 = pj , * PN+1i = PN+1i. Покажем, что матрица P* =(p* , i, j = 0,N +1) является стохастической. N N £ p * = £ P0, =1, i=1 i=1 N+1 N N N £ P*i =£ (1" Р] )Pj, + Pj =£ Pj, " Pj £ Р ji + Pj = 1 i=1 i=0 i=0 i=0 N * N £ p IN+1i =£ pN+1i = 1. i=0 i=0 Будем предполагать, что матрица маршрутизации P , где p00 = poN+\ = 0, неприводима. Записав уравнения трафика через введенные обозначения вероятностей переходов, получаем систему уравнений трафика сети Джексона, для которой доказано существование единственного положительного решения при условии неприводимости матрицы маршрутизации [5]. Таким образом, система уравнений трафика для исследуемой сети имеет единственное положительное решение (вг-, 1, N +1). Пусть {p(x), x е X} - стационарное распределение вероятностей состояний процесса x(t). Уравнения равновесия для стационарных вероятностей имеют вид f N N p(x) I Х+Ъ Ц 1I{n,iФ0} + ^N+1 I{nN+1Ф0} + Ъ V,I{miФ 0} i=1 (1) i=1 = Ъ p( x - eг1)ХPolI{ mtФ 0} + Ъ p( x + e2)^.1p10 + p( x + eN+1)ц N+1pN+10 + i=1 i=1 N 1 N 1 2 + Ъ p(x + e, - eN+1)v,p,I{nN+1 Ф0} + Ъ p(x + e, - e, )Vi (1 - pi )1{Ф0} + NN 2 , N . +Ъ Ъ p(x + e2. - e\)vJ.pj, Ф0} + Ъ p(x + eN+1 ei)^N+1 pN+1iI{m-Ф 0}, x е X . i=1 j=1 1 i S i=1 1 i 1 Здесь ei - единичный вектор размерности (2N + 1) с единицей в (2(i - 1) + к)-й позиции, i = 1, N, к = 1, 2; eN+1 - единичный вектор размерности (2N + 1) с единицей в (2N + 1)-й позиции. Теорема 3. Пусть для любых i = 1, N выполняются неравенства Хе i < 1 Хе i(1 - pi ) < 1 ХеN+1 v i Ц i Ц N+1 тогда марковский процесс x(t) эргодичен, а финальное стационарное распределение вероятностей состояний сети имеет следующий вид: p(x) = p1(x{)p2(x2)... pm^m^, xеX, (3) где (2) < 1, f Хе i ^ m f Хе i (1 - pt)Л n' f Хеi - Хе i (1 - pi) > (4) (5) 1 i = 1, N, V i v i i \nN+1 f 1 - ХеN+1 pi(xi) = v v i у Хе N+1 pN+1 ( xN+1 ) Ц N+1 (е^ 1, N +1) - решение системы уравнений трафика. Доказательство. Докажем, что марковский процесс x(t) эргодичен при выполнении условий (2), а (3) является решением уравнений равновесия (1). Согласно эргодической теореме Фостера достаточно доказать, что существует нетривиальное решение {p(x), x е X} системы уравнений равновесия p( x)q( x) = Ъ p( y)q( У, x), x е X, (6) y Ф x, yeX такое, что ряд ЪxeXq(x)p(x) сходится. Здесь q(x) - интенсивность выхода из состояния x. Докажем, что (3) удовлетворяет уравнениям равновесия (1). Воспользуемся методом локального баланса. Разобьем (1) на уравнения локального равновесия (7) (8) N p( Ф = Ъ p( x+ef )ц ,p, 0 + p( x+e n+1 )ц n+1 pn+10; i=1 f N p(x) I Ъ п, Ф 0} + М- N+1^{nN +1Ф 0} N 1 N 1 2 = ъ p(x+e,- eN+1)v,p,I{nN+1 ф 0} + ъ p(x+e,- e,)y,(1 - p,) ф0}; Ц N+1 N N 1 p(x) Ъ ViI{m.ф0} = Ъ p(x - e,-i=1 1 i 1 N Ъ i=1 1{mi Ф 0} NN 2 , N . + I I p(x + e, - ej ,PljI{m.*0} + I P(x + eN+1 - e, W+1 PN+UI{mi*0} • "ц N+1p N+10 = 1 j= Разделим обе части уравнения (7) наp(x) = pi(x)p2(x)... pN+i(x), подставим (4), (5), получим Л N Xei(1 - Р г ) + 1г N+1 X = I-Цг Pi0 +i=1 цг Ц N+1 \ ( = X. I Et (1 - p j) - I (e j - Р0 j - E N+1Pn+1 j ) + В N+1PN+10 vi=1 j =1 Разделим обе части уравнения (8) наp(x) = p1(x)p2(x)... pN+1(x), подставим (4), (5), получим N Xe г Mw+1 I ц I = I- {nN+1 * 0} i=1 N {«,.* 0} ^ ЦN+1I{nN +1 * 0} " I v Л в i=1 V . Xe n+1 = X j Vt(1 pt )I{nt.* 0} = N+1 2 EtptI{nN+1 * 0} + 2 ^tI{ni* 0} i=1 V. Xe. (1 - pt) N = I Цгк t=1 N XE +I t=1 t=1 -N+1 ' Ц N+1I{n Разделим обе части уравнения (9) наp(x) = p1(x)p2(x)... pN+1(x), подставим (4), (5), получим N Xej(1 - Pj) Vi N N N I VtI{m/* 0} = ^T^XР0гI^ ц jPjtI{mi *0} {mt- * 0} XE: + II t=1 ' t=1 XEi ' ' ' t=1 j=1 + Z N+1 „ : цN+1 pN+1tI{mi * 0} = t=1 ц N+1 XEi N v. = I ~ г =1 Ej N N P0t + I E j(1 - Pj)Pji + En+1 Pn+1t h V jl t=1 m*0! f-; 'г {mi*0}' j=1 Из требования теоремы Фостера о сходимости ряда IxeXq(x)p(x), где интенсивность выхода из состояния x N N q( x) = X + I Mi^n.* 0} + ЦN+1I{nN+1 * 0} + Z VtI{mi*0} , учитывая (3), получим условие (2). При этом (3) задает единственное стационарное распределение вероятностей состояний сети. Теорема доказана. Заключение В настоящей работе исследована открытая марковская сеть массового обслуживания с поступающим пуассоновским потоком заявок. Сеть состоит из узлов, в которых находятся две очереди: очередь для проверки заявок на стандартность и обычная очередь для обслуживания. Времена проверки и времена обслуживания независимы и имеют показательное распределение. В сети также имеется карантинный узел, в который направляются заявки, не прошедшие проверку. Установлены условия эргодичности и аналитический вид стационарного распределения состояний сети. Рассматриваемая в работе модель является обобщением модели сети, исследуемой в [5] на случай наличия карантинного узла и контрольных очередей в узлах.

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