Анализ сетей с положительными и отрицательными заявками в переходном режиме | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2013. № 4(25).

Анализ сетей с положительными и отрицательными заявками в переходном режиме

Рассматривается сеть массового обслуживания в переходном режиме с положительными и отрицательными заявками, которая может использоваться при моделировании поведения вирусов в информационно-телекоммуникационных системах и сетях. Выведена система разностно-дифференциальных уравнений для вероятностей состояний сети. Для их нахождения предложена методика, основанная на использовании аппарата многомерных производящих функций. Получены приближенные выражения для определения вероятностей состояний в любой момент времени. Проводится также исследование такой сети с доходами, описана методика нахождения ожидаемых доходов систем сети.

Analysis of networks with positive and negative messages at transient behavior.pdf Современные информационно-телекоммуникационные системы и сети становятся все более сложными, что обусловлено необходимостью повышения надежности передачи и обработки информации. Построение и исследование математических моделей для оценки качества их функционирования является важной задачей. Применение для этой цели классических моделей теории массового обслуживания (МО) не всегда дает адекватные результаты, поскольку необходимо, чтобы модели учитывали как характерные особенности систем, так и возможное влияние различных дестабилизирующих факторов, как например, внезапные сбои, попадание вирусов, потеря передаваемых или обрабатываемых данных. Для учета подобных факторов была предложена концепция отрицательных заявок и связанных с ними сетей и систем МО, принципиально новый класс сетей МО был введен Е. Геленбе в [1]. Это G-сети, в которых помимо потоков обычных (положительных) заявок рассматриваются также дополнительные пуассоновские потоки отрицательных заявок. При поступлении в систему сети отрицательная заявка уничтожает одну положительную заявку, если таковая имеется в данной системе, тем самым уменьшая число положительных заявок в системе на единицу. Затем отрицательная заявка исчезает из сети, не получив никакого обслуживания. Например, в компьютерных сетях «положительными» заявками являются задания (программы), а «отрицательными» - компьютерные вирусы. При поступлении в компьютерную сеть вирус уничтожает или наносит вред, заражает одну из исполняемых программ, уменьшая количество действующих программ или запросов в системе на единицу. Следует отметить, что исследование G-сетей в стационарном режиме проведено в работах [2, 3]. При попадании вируса в информационную систему из-за потери информации или ее искажения система и вся информационно-телекоммуникационная сеть несет некоторые расходы или убытки. При переходе положительной заявки из одной СМО в другую последняя СМО получает некоторый доход, а доход первой СМО уменьшается соответственно на эту величину. Кроме того, учет этого можно осуществить, применив в качестве модели сеть МО с доходами (HM-сеть) с положительными и отрицательными заявками. Во второй части данной статьи описана методика нахождения ожидаемых доходов в системах такой сети. Методика анализа HM-сетей без учета отрицательных заявок и их применения при прогнозировании ожидаемых доходов различных объектов описаны в работе [4]. 1. Постановка задачи Рассмотрим открытую G-сеть МО с n однолинейными СМО. В СМО Si извне (из системы S0) поступает поток положительных (обычных) заявок интенсивности Я+ и пуассоновский поток отрицательных заявок интенсивности Я,— , i = 1, n . Все поступающие в сеть потоки заявок являются независимыми. Длительности обслуживания положительных заявок в СМО Si распределены экспоненциально с параметром , i = 1, n . Отрицательная заявка, поступающая в некоторую систему сети, в которой имеется, по крайней мере, одна положительная заявка, мгновенно уничтожает одну из них и наносит убыток этой СМО. При предположении экспоненциального распределения времени обслуживания положительных заявок можно не заботиться о том, какая именно заявка уничтожается. После этого она сама сразу же покидает сеть или уничтожается в замкнутой сети, не получая в данной СМО никакого обслуживания. Таким образом, в каждой СМО-сети могут обслуживаться только положительные заявки, поэтому в дальнейшем, говоря об обслуживании положительных заявок, обычно для краткости называют их просто заявками [1]. Положительная заявка при переходе из одной СМО в другую приносит последней системе некоторый доход и соответственно доход первой системы уменьшается на эту величину. Каждая положительная заявка направляется в СМО Si с вероятностью p+, n n _ а отрицательная - с вероятностью pw , ^ p+ = ^ pw = 1, i = 1, n . Положительная i =1 i=1 заявка, обслуженная в СМО Si, с вероятностью p+ направляется в СМО Sj как положительная заявка, а с вероятностью p- - как отрицательная заявка и с вероn ятностью pi0 = 1 _X(p+ + p- ) уходит из сети во внешнюю среду (СМО S0), j=1 i, j = 1,n. Под состоянием сети будем понимать вектор k (t ) = (к, t) = = (k1,k2,...,kn,t), где ki - число заявок в момент времени t в системе Si, i = 1,n . Пусть P (k, t) - вероятность состояния k в момент времени t. Обозначим через vi (k, t) - полный ожидаемый доход, который получает система Si за время t, если в начальный момент времени сеть находится в состоянии k, и предположим, что эта функция дифференцируема по t; ri (k) - доход системы Si в единицу времени, когда сеть находится в состоянии k ; r0i (k + I, t) - доход системы Si, когда сеть совершает переход из состояния (k, t) в состояние (k + Ii, t + At) за время At, где Ii - вектор размерности n , состоящий из нулей, за исключением компоненты с номером i, которая равна 1, i = 1, n ; -R0 (k - Ii, t) -доход этой системы, если сеть совершает переход из состояния (k, t) в состояние (k - It, t + At); rj (k + Ii - Ij , t) - доход системы Si (расход или убыток системы SJ), когда сеть изменяет свое состояние из (k, t) на (k + It - Ij , t + At) за время At; rj (k + Ii +1 j , t) - доход системы Si (убыток системы Sj ), когда сеть изменяет свое состояние из (k, t) на (k + Ii + Ij , t + At) за время At, i, J = 1, n . Требуется найти вероятности состояний сети и ожидаемые (средние) доходы систем сети за время t при условии, что нам известно ее состояние в начальный момент t0 . Теорема. Вероятности состояний рассматриваемой сети удовлетворяют системе разностно-дифференциальных уравнений (РДУ): dP(k, t) + Y £««(ki )P(k - Ii, t) + x i=1 i=1 P (k + Ir, t) + ^0iP0i + *i £[^+iPo+ +x-iPo-i + l ]u (ki )P(k,t) dt i=1 Pio +Z P- (( u (k j ^ J=1 yj +E i [ p+u (kj )P (k+Ii - ij , t)+P-P (k+Ii + ^, 0], (1) i, J=1 где u (x) = {0 X 0 , Vt > 0, i = 1, n , тогда система РДУ (1) примет вид dP(k, t) (2) "£((+■ +Я 0ip-i + h ))(k, t)dt bJ 4p+iP(k - 1г, t) + J ( 0 +Я -i p-i )P (k + It, t) + + J h [p+P (k +1i - Ij, t) + p-P(k +1, + Ij, t)] . i, j =1 Обозначим через Tn(z,t), где z = (z1,z2,...,zn), n-мерную производящую функцию ад ад ад T n (z, t) = J J ... J P(k1, k2,.., kn , t) zk z22 •.... zkn" = k1 =0 k2=0 kn =0 ад ад ад = J J ... J P(k,t) П?. k1 =0 k2=0 kn=0 i=1 n Умножив (2) на П zr l и просуммировав по всем возможным значениям kl от i=1 1 до +ад , l = 1, n, получим линейное неоднородное дифференциальное уравнение (ДУ) i, j=1 n n n d Tn (z, t) dt h1p10+ Ktp- J ( Я +i p+i + Я0i p-i + hi ) - J Я +i p+i zi - J n z ■ n 1 - J hp+ — - J hp° — T n ( z, t) i, j =1 i i, j=1 .. у, I л у,- ^ад n -jhpi°+Я 0 ip 0 i J P(k1,...,k-1,0,k!+1..,kn,t)nzki kj=1 j=1, n, j l =1 l ад -Jhp+- J P(k1,...,k-1,0,k+1,...,kn,t)nzk i, j=1 z k^_=1 m=1, n, ШФ j n l=1 l n 1 да n -XhP-- X P(k1,...,ki-1,0,ki+1,...,kn,t)nzkl . (3) l=1 l i, J=1 ZiZJ km= 1 m=1, n, m Ф j Поскольку все СМО-сети функционируют в условиях высокой нагрузки, то последние три выражения в виде сумм в уравнении (3) будут равны нулю и оно становится однородным: n n n X ( +i P0+i + Я-i P0-i + *i) - X Я+i P0+i zi - X n z ■ n 1 - X *iPi+~- X *iP- — Y n (Z, t). "j ^ r-ifij ... Z- ■ , Z Z ■ i,J=1 i i,J=1 i J d Y n (z, t) dt IP 0 + P0i n n n 1 X ((i P0i + X-i P0-i + *i ) - X Я0i P0+i zi - X — (*i Pi0 + X-i P0i i=1 i=1 " Z n n 1 Y -*i X p+zj -*i X р.-— t f. j=1 j=1 zj Jj Будем считать, что в начальный момент времени сеть находится в состоянии (а1,а2,...,аn,0), ar > 0, i = 1,n , P(a1,a2,...,an,0) = 1, P(k1,k2,...,kn,0) = 0, Var ^ k , i = 1, n . Тогда начальным условием для последнего уравнения будет n n Yn(z,0) = P(a1,a2,...,an,0)Пzfl = Пzfl . Используя его, получаем Cn = 1. 1=1 i=1 Таким образом, выражение для производящей функции Yn (z, t) с учетом разложения входящей в него экспоненты в ряд Маклорена имеет вид n да да да да да да да да у ( +q + r +u ) Yn(z,t)=00(t)X...XX... XX...XX... X t~ r r x l1 =0 ln =0 q1 =0 qn =0 r1=0 rn =0 u1=0 un =0 / / \u n w n a.+l. - q- - r + R-u-- У *n i=1 (4) со- X+ilnp0i3 ( +X-iP0i)qi ir+ui Пp+ ПP- ( j=1 J ( j=1 J Интенсивности обслуживания заявок ц, равны ц1 = ц2 = ц3 = 2, ц4 = l, ц5 = 3 . Пусть также вероятности p+ , с которыми положительная заявка направляется в СМО Si, равны p+ = 2/15, p+2 = 1/5, p+3 = 1/15, p+4 = 4/15, p+5 = 1/3, а аналогичные вероятности для отрицательных заявок равны p- = 1/3, po2 = po3 = po4 = 0 , po5 = 2/3. Вероятности p+ того, что положительные заявки, обслуженные в СМО Si, направятся в СМО Sj как положительные заявки, равны: p+2 = p+3 = p+4 = p+1 = p+3 = p+4 = p+1 = p3+2 = p3+4 =1/3 , p+41 = P+2 = p+3 = P+5 =1/4 , p+4 = 1/2 . C вероятностью p50 = 1/2 заявка уходит из сети во внешнюю среду. 7П Тогда выражение a0 (t) примет вид a0(t) = exp——51} = Пусть нам надо найти, например, вероятность состояния P(1,1,...,1,t). Она является коэффициентом при z1 z2 •...• zn в разложении функции Тn(z,t) в многократный ряд (4), поэтому степени при zi должны удовлетворять соотношению ai + li - qi - ri + R - ui - U = 1, i = 1, n , отсюда следует, что n n _ q, = ai + 1, +Z ri- Z ui- ^ i =1 n, j=1 j=1 i i n n _ qt + r + u, = a + +Zri -Zui-^ i =1,n, i=1 i=1 n n _ h + qt + r + u, = a + 21, +Zri -Zui-1, i = 1n, i=1 i=1 Z(( + qt + r + u ) = Z ( + Ц) + n(R - U -1). i=1 i=1 Тогда из соотношения (4) получаем, что Решение его имеет вид Yn (z, t) = Cn exp j- ZK+21, )+ n( R-U-1) P(1,1,1,1,1,t)=* 5 z...ZZ...ZZ...Z ** l1 =0 ln =0 r1 =0 rn=0 u1 =0 un =0 K'np+l ( +^-,p0-,)+li+iZ1r/^ 1 tf+ui frip+ Пp- V j=1 7 V j=1 7

Ключевые слова

transient behavior, HM-network with positive and negative messages, G-network with negative messages, переходный режим, HM-сеть с положительными и отрицательными заявками, G-сеть с отрицательными заявками

Авторы

ФИООрганизацияДополнительноE-mail
Науменко Виктор ВикторовичГродненский государственный университет им. Я. Купалыаспирант факультета математики и информатикиvictornn86@gmail.com
Маталыцкий Михаил АлексеевичГродненский государственный университет им. Я. Купалыпрофессор, доктор физико-математических наук, заведующий кафедрой стохастического анализа и эконометрии факультета математики и информатикиm.matalytski@gmail.com
Всего: 2

Ссылки

Колузаева Е.В., Нахождение ожидаемых доходов в открытой двух узловой HM-сети с помощью z-преобразований // Вестник ГрГУ. Сер. 2. 2010. № 3. С. 9-14.
Маталыцкий М.А., Тихоненко О.М., Колузаева Е.В. Системы и сети МО: анализ и применения. Гродно: ГрГУ, 2011. 817 с.
Маталыцкий М.А., Колузаева Е.В. Анализ ожидаемых доходов в открытой сети с помощью z-преобразований // Вестник ГрГУ. Сер. 2. 2008. № 1. С. 20-30.
Ge'enbe E., SchassbergerR. Stability of product-form G-networks // Probab. Eng. and Inf. Sci. 1992. V. 6. P. 271-276.
Маталыцкий М.А. О некоторых результатах анализа и оптимизации марковских сетей с доходами и их применении // Автоматика и телемеханика. 2009. № 10. С. 97-113.
Ge'enbe E. Product form queueing networks with negative and positive customers // J. Appl. Prob. 1991. V. 28. P. 656-663.
Бочаров П.П., Вишневский В.М. G-сети: развитие теории мультипликативных сетей // Автоматика и телемеханика. 2003. № 5. С. 46-74.
 Анализ сетей с положительными и отрицательными заявками в переходном режиме | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2013. № 4(25).

Анализ сетей с положительными и отрицательными заявками в переходном режиме | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2013. № 4(25).

Полнотекстовая версия