автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:G-сети с зависимым обслуживанием

На правах рукописи

ГАВРИЛОВ Евгений Валерьевич

Й-СЕТШ С ЗАВИСИМЫМ ОБСЛУЖЮАММЕМ

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата физико-математических наук

Москва 2004 г.

Работа выполнена в Российском университете дружбы народов

доктор технических наук профессор П.П. Бочаров

вшшишюы: доктор технических наук

профессор В.М. Вишневский

доктор физико-математических наук профессор В.Г. Ушаков

Институт проблем управления РАН

Защита состоится «_» 2004 г. в часов на

заседании диссертационного совета Д.002.077.01 в Институте проблем передачи информации РАН по адресу: 127994, Москва, ГСП-4, Б.Каретный пер., 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан «¿^У» 2004 г.

Ученый секретарь диссертационного совета Д.002.077.01

доктор технических наук, профессор С.Н. Степанов

14 №

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В последнее время наблюдается бурное развитие информационно-телекоммуникационных технологий и сетевых систем. Функционирование сетевых структур связано с бесперебойной передачей и обработкой большого числа информационных потоков. Вероятностная природа этих потоков приводит к появлению целого ряда проблем, возникающих как на этапе проектирования сетевых систем, так и при их эксплуатации и модернизации. Это, в свою очередь, стимулирует математические исследования, направленные на разработку адекватных стохастических моделей и их анализ с целью получения количественных оценок показателей производительности сетевых систем. Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории сетей массового обслуживания.

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

Сравнительно недавно в теории мультипликативных сетей появилось новое перспективное направление, связанное с исследованием СеМО с отрицательными заявками — в-сетей. Зародившаяся около 15 лет назад, теория в-сетей все это время интенсивно развивалась. Были исследованы различные модификации в-сетей, обобщающие сети Джексона, ВСМР-сети и др. Результаты этих исследований опубликованы в десятках работ. Такой интерес к этой проблематике со стороны ученых всего мира показывает практическую необходимость в дальнейшем развитии теории в-сетей.

Одним из важных направлений в исследовании в-сетей является развитие мультипликативной теории для сетей с зависимым обслуживанием и отрицательными заявками — в-сетей с зависимым обслуживанием.

Исследования G-сетей с зависимым обслуживанием ранее в литературе не проводились, поэтому тема диссертационной работы является актуальной.

Целью диссертационной работы является получение мультипликативного представления для стационарного распределения числа заявок в узлах G-сети с зависимым обслуживанием, в которой каждая заявка, поступившая в сеть, характеризуется набором случайных параметров: ее маршрутом по сети (последовательностью проходимых заявкой узлов), длиной маршрута, а также объемом заявки и длительностью ее обслуживания на каждом этапе маршрута, для трех модификаций G-сети:

базовой G-сети с зависимым обслуживанием с ВСМР-узлами;

G-сети с ВСМР-узлами, исключая экспоненциальные узлы, и до-обслуживанием "убитой" заявки;

G-сети с экспоненциальными узлами и изменением типа заявки.

Методы исследования. В диссертационной работе применяются в основном методы теории вероятностей, теории случайных процессов и теории массового обслуживания.

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

Апробация работы. Основные результаты диссертации докладывались на международных конференциях: "Распределенные компьютерные и телекоммуникационные сети" (Москва, 2003 г.); "Современные математические методы анализа и оптимизации телекоммуникационных сетей" Беларусь, Гомель, 2003 г.); "Performance Modelling and Evaluation of Heterogeneous Networks" (FIET-NETs 2003) (Great Britain, Ilkley, 2003 г.); XXIII International Seminar on Stability

Problems for Stochastic Models (Spain, Pamplona, 2003 г.); на XXXIX и XXXX Всероссийских научных конференциях по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин (Москва, РУДН, 2003, 2004 гг.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН.

Публикации. По материалам диссертации опубликовано 8 работ, из них 2 в центральной печати.

Научная новизна работы. Все результаты диссертации являются новыми и состоят в следующем:

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

базовой G-сети с зависимым обслуживанием с ВСМР-узлами;

G-сети с ВСМР-узлами, исключая экспоненциальные узлы, и до-обслуживанием "убитой" заявки;

G-сети с экспоненциальными узлами и изменением типа заявки.

Реализация результатов работы. Исследование сетей массового обслуживания с зависимым обслуживанием и отрицательными заявками проводилось в рамках НИР "Разработка теоретических основ анализа очередей в информационно-вычислительных и телекоммуникационных сетях: алгоритмический подход" (государственный регистрационный номер 01.2.00 105246), выполняемой в соответствии с тематическим планом РУДН на 2001 -2005 гг., а также в рамках гранта Российского фонда фундаментальных исследований № 02-0790147 "Математические методы и программное обеспечение моделирования информационных, вычислительных и телекоммуникационных систем".

Структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы из 83 наименований. Диссертация содержит 119 страниц текста.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается сеть массового обслуживания с зависимым обслуживанием и отрицательными заявками. Подробное описание исследуемой в первой главе СеМО приведено в § 1.

Вводятся следующие обозначения:

М — конечное множество узлов сети; М — число узлов в СеМО; з — номер узла, з — 1,М.

Предполагается, что узлы могут быть следующего типа:

0 — экспоненциальные многолинейные с общим накопителем бесконечной емкости и дисциплиной ИРО;

1 — бесконечнолинейные;

2 — однолинейные с накопителем бесконечной емкости и инверсионной дисциплиной обслуживания с прерыванием обслуживания и дообслуживанием (дисциплина ЬСРБ РЛ);

3 — однолинейные с накопителем бесконечной емкости и дисциплиной равномерного разделения прибора (дисциплина РЭ).

В сеть поступает пуассоновский поток (обычных) заявок интенсивности Л. Каждая поступающая в СеМО заявка характеризуется набором СВ (£, М, Т, X), не зависящих от аналогичных СВ для остальных заявок и предыстории функционирования сети, где:

Ь — случайная длина маршрута заявки;

Ж = {В.\,..., Кь) — случайный маршрут, представляющий собой набор номеров узлов (возможно повторяющихся), последовательно проходимых заявкой на всех Ь этапах;

У — (^ъ • • • ,Уь) — случайные объемы на последовательно проходимых этапах маршрута, вообще говоря, различные на различных этапах;

X = (Х1,..., Хь) — случайные длительности обслуживания на последовательно проходимых этапах маршрута, вообще говоря, различные на разных этапах. Отметим, что если на некотором этапе заявка обслуживается в узле типа 2 или 3, то длительность обслуживания на данном этапе представляет собой то время, которое обслуживалась бы в этом узле заявка, если бы в нем не было других заявок.

Заданы совместные функции распределения (ФР) СВ (Ь, Я, У, Ж)

В(1, г, у, х) = Р{£ = I, Л„ = г„, Уп < уп, Хп <хп, п- 1, /}. Далее обозначим через

0{1, л у) = Р{Ь = I, Пп = гп, У„ < уп, п = ТЛ}

совместную ФР маршрута R длины L и объемов Т заявки на этапах, через

В(х | l,r,y) = P{JSf„ <хп, n = TJ\L-l,R=r, Y= у}

— условную совместную ФР длительностей X обслуживания заявки на этапах при фиксированных маршруте R = г длины L = I и объемах Y= у и через

Bn(x\l,r,y)=¥{Xn<x\L = l,R=r, У= у}, n = lj,

— условную ФР длительности Х„ обслуживания заявки на n-м этапе при фиксированных маршруте Д = г длины L = I и объемах У = у.

Через д(1, г, у) и Ьп(ж | I, г, у) обозначим плотности, т.е.

д1 д 9{1,г,у) = Qyi...QyiG^г>Ьп(х I г>г>У)= fcBn(x I г>г>

Относительно данных ФР делаются следующие предположения. П 1.1. Длительности обслуживания предполагаются условно независимыми вдоль маршрута, т.е.

I

В{х\1,т,у) = Цвп{хп\1,г,у).

п=1

П 1.2. Каждый экспоненциальный узел s является с^-линейной системой массового обслуживания (СМО) с бесконечной емкостью накопителя, интенсивность обслуживания в которой любой заявки каждым прибором равна Таким образом, если rn = s б Мо, то

Вп(х\1,г,у) = 1-е-»>х.

Иными словами, длительность Хп обслуживания в узле rn — s типа О не зависит ни от маршрута R, ни от всех объемов У*, (включая объем У„) и имеет экспоненциальное с параметром (is распределение.

Наряду с потоком обычных (положительных) заявок в узлы СеМО поступают потоки отрицательных заявок, определяемые следующим образом.

П 2.1. Потоки, поступающие в разные узлы, являются независимыми.

П 2.2. Поток, поступающий в узел s типа 2 или 3, является пуассоновским интенсивности 7а.

П 2.3. Поток, поступающий в узел s типа 0 или 1, является марковского типа с интенсивностью ъ(п): тЛп) = пЪ-

П 2.4. Отрицательная заявка, поступающая в узел s и застающая в этом узле к положительных заявок на обслуживании, с одинаковой вероятностью l/к выбирает одну из обслуживаемых положительных заявок. Затем, если узел s типа 0, то отрицательная заявка мгновенно "убивает" (удаляет из СеМО) выбранную заявку. Если же узел s остальных типов, то отрицательная заявка либо с вероятностью изп{х 11, г, у) "убивает" выбранную заявку, либо с вероятностью 1 - ип(х j I, г, у) покидает СеМО, не оказывая на нее никакого воздействия. Здесь (I, г, у) — параметры обслуживания выбранной заявки, определенные ранее, п — номер этапа маршрута, на котором обслуживается эта заявка, х — обслуженная длина заявки. Отрицательная и "убитая" заявки покидают СеМО и больше в нее не возвращаются. Если же в момент поступления отрицательной заявки в некоторый узел в нем отсутствуют положительные заявки, то отрицательная заявка покидает СеМО, не оказывая на нее никакого воздействия. В § 2 вводятся вспомогательные функции. (F(x) = 1 - F(x)). Для узлов типов 1-3 функции задаются формулами

оо

О

О

11, Л у) = 1 - Вп{х 11, г, у) Рп(х I I, г,у). Аналогичные функции для узла г„ типа 0 имеют вид

<"п(1, у) = ;В*п(х \l,r,y) = 1 -

п-1

<(1,г,у)=Цьл{1,г,у)у п= 1,1 + 1,

»» у) = г, у) д{1, г, у), п = 1,1,

со

тп{1, г,у) = ! В*п(ж | г, г, у)йх, п = 171 о

Для узлов типов 2 и 3 В*(х | I, г, у) и тп{1, г, у) определены при условии отсутствия в таких узлах других заявок. Для «-го узла определяется

оо . I

Рз=Л ]С X) Пьзп(1'г>6е~г» (1> г> у) йу>

1=1 1<гх,...,Т1<М~1 п=1

где 6] — символ Кронекера. Для сокращения записи используется обозначение

J... йу = J...J... ¿ух •••йуи к' к1

Предполагается, что для всех узлов з

1=1 1<Г,.....r,<AÍ¿ n=l

Последнее условие означает, что суммарная интенсивность поступающего в узел а потока положительных заявок конечна.

В § 3 вводится марковский процесс, описывающий функционирование введенной сети.

Состояние сети обозначается набором z = (zi,..., Zm), где набор zc = {кs, zsi,..., zâf;a), a = l, M, в свою очередь, описывает состояние s-ro узла следующим образом: к3 — число заявок, находящихся в s-м узле, а набор zB\, s = 1,М, i = 1, fcs, с компонентами zSi = i,hi,rs¡,yai,na¡,xsi) содержит информацию {lai,railysi) об г-й заявке, находящейся в s-м узле, и ее положении (nai,xsi) в сети:

hi ~ длина маршрута; r3i = (rsa,... ,гец3.) — маршрут; y8i = {уsil,-■ • jУзИй{) — объемы заявки на его этапах; ne¡ — номер этапа маршрута, на котором находится (обслуживается или ожидает обслуживания) заявка (ясно, что ns¡ < х¡¡i — выработанная длительность обслуживания заявки на данном этапе.

Очевидно, что в силу принятого обозначения í*s¿nsi = s. Ясно также, что вектор z3 = 0 в случае ка = 0, т.е. когда в s-м узле

отсутствуют заявки, а вектор 2 = О = (0,..., 0) в том случае, когда во всей сети ней нет ни одной заявки. Кроме того, будем считать, что координаты хаг не определяются для экспоненциальных узлов, хотя для единообразия записи аргумент х31- будем указывать. Множество состояний сети обозначается через 2 = {г}. В качестве процесса, описывающего функционирование рассматриваемой СеМО, рассматривается процесс

Z(t) — z, если в момент % сеть находится в состоянии z.

Очевидно, что введенный процесс является марковским.

В § 4 доказывается теорема о мультипликативном представлении стационарных вероятностей состояний для рассматриваемой сети.

Стационарная плотность распределения вероятностей состояний процесса обозначается в виде

Теорема. Если для узлов в типа 0 ре < са) для узлов в типа 1 ра < оо и для узлов з типов 2 и 3 р„ < где р3 определяются формулой (1), то существует предельное (стационарное) распределение вероятностей состояний процесса Z(t) с плотностью распределения вероятностей

м

Р(г) =

8=1

причем:

для узла в типа 0

/ х \к3

РвЫ = р3(о) <г3(/=„) (——) Д ^'' '

где

А \ _ / 1//г«! ПРи к» ^ С"1

Л а] ~ \ 1/(са1 #-<=-) при к3 > с„;

для узла типа 1 рМ = е~р° -ГТ п I «V, Ун) 9па<(*»«•> Ъ,

1=1

для узла в типов 2 и 3

= (1 - р3)Хк' Д в"пя. 11ви ун) д*л1 (1аи га{, ун).

»=1

В § 5 выводятся следствия из доказанной теоремы, в частности, определяются маргинальная стационарная плотность распределения процесса, описывающего функционирование отдельного узла сети, стационарное распределение числа заявок в узле (без учета их параметров), стационарные вероятности того, что заявка с параметрами [I, г, у) не будет "убита" до п-го этапа и будет "убита" на п-м этапе, а также находится стационарная интенсивность А„ входящего в узел з потока.

В главе 2 проводится анализ сети массового обслуживания с зависимым обслуживанием, отрицательными заявками и дообслужи-ванием "убитых" заявок. Узлы предполагаются тех же типов, что и в гл. 1, за исключением экспоненциальных узлов. Все определения и предположения для положительных заявок такие же, как и в гл. 1.

Помимо потока положительных заявок в узлы СеМО поступают потоки отрицательных заявок, определенные таким же образом, как и в гл. 1 (исключая узлы типа 0), и отличные от описанных в гл. 1 следующим свойством.

П 2.4. Отрицательная заявка, поступившая в узел в и заставшая в этом узле к положительных заявок на текущем обслуживании, с одинаковой вероятностью 1 /к выбирает одну из обслуживаемых положительных заявок. Далее отрицательная заявка либо с вероятностью шп(х | 1,г, у) "убивает" выбранную положительную заявку, либо с вероятностью 1 - шп(х 11, г, у), мгновенно покидает СеМО, не оказывая на нее никакого воздействия. Однако, в отличие от СеМО, рассмотренной в гл. 1, "убитая" заявка покинет СеМО только после того, как целиком выработается ее длительность обслуживания на этом этапе. Если же в момент поступления отрицательной заявки в некоторый узел в нем отсутствуют положительные заявки или выбранная положительная заявка уже "убита" ранее поступившей отрицательной заявкой, то вновь поступающая отрицательная заявка покидает СеМО, не оказывая на нее никакого воздействия.

В § 2 вводятся такие же вспомогательные функции, как и в гл. 1., а также:

ВЦх \1,г,у) = I — Вп(х 11, г, у) Рп(х 11, г, у).

В~ (ж 11, г, у) = Вп{х 11, г, у) Рк(а; 11, г, у).

со

со

тп(1,г,у)= / Вп(х 11,г,у)йх, п=1,1,

о

оо

оо

о

оо

тп (I, г, у) = / (ж | г, г, у) = т„(г, г, у) - т+(1, г, у), п = 1,

Для го = О,1ип = 1,? определяется

££ ! л у, №) = (ж | Л у) + (х | т-, у) =

= £шВп(ж 11, г, у)х 11, г, у) + б1_шВп(ж | г, у, у) Рп(х 11, г, у). Для 5-го узла вводятся также следующие величины:

/=>3=А]Г дп(1, г, у) 63-Гпт~(1, г, у) йу = р3 — р*.

1=1 1<Г1,...,Г1<М^1 1

Предполагается, что для любого узла 5 Аа < оо.

В § 3 вводится марковский процесс, описывающий функционирование введенной сети.

Набором г = (21,..., ям) обозначается состояние сети, где, в свою очередь, набор гд = я = 1,М, описывает

состояние з-го узла следующим образом: ка — число заявок, находящихся в 5-м узле, а набор 2з{, й = 1, М, г = 1,ка, с компонентами (¿31) Увг)

п^.ж^.ад^) определяет информацию гз{, уа{) об г-й заявке, находящейся в я-м узле, и ее положении в

сети:

1В1 — длина маршрута; гз{ = (г^г,...,г3«о4) — маршрут; ун = {УзП,'--,УзИя1) — объемы заявки на этапах маршрута; п3; — номер

о

1=1 1<Г],...,Г(<М^1 п=1

со

этапа маршрута, на котором находится (обслуживается или ожидает обслуживания) заявка (ясно, что п3{ < 1^); х^ — выработанная длительность обслуживания заявки на данном этапе; — функция, показывающая состояние заявки, причем полагаем = 0, если заявка не "убита", и чиа{ = 1, если заявка "убита" (но продолжает обслуживаться).

Множество состояний сети обозначается через 2 = {г}. В качестве процесса, описывающего стохастическое поведение рассматриваемой СеМО, рассматривается процесс

= 2, если в момент £ сеть находится в состоянии г.

Нетрудно видеть, что введенный таким образом процесс является марковским.

В § 4 доказывается теорема о мультипликативном представлении стационарных вероятностей состояний для рассматриваемой сети.

Теорема. Если для узлов 8 типа 1 ре < оо и для узлов я типов 2 и 3 р3 < 1, где ре определяются формулой (1), то существует предельное (стационарное) распределение вероятностей состояний процесса И^) с плотностью распределения вероятностей

м

= 1Ь(*).

3=1

причем для узла я типа 1 ДА* *«

Рэ{г*) = е р°7Гт13-В«.Д®8< I *"«> Т<*> 9п.ЛЬи Пи 9«),

Кз' ,=1

а для узла в типов 2 и 3

ь,

Р=Ш = (1 - П Впа (ХГЛ | Ьи пи уа{, «>„■) д*П;11 щ, у^).

1-!

В § 5 выводятся следствия из доказанной теоремы, в частности, определяются маргинальная стационарная плотность распределения процесса, описывающего функционирование отдельного узла се ти, стационарное распределение числа заявок в узле (без учета их

параметров), стационарные вероятности того, что заявка с параметрами (I, г, у) не будет "убита" до n-го этапа и будет "убита" на п-м этапе, а также находится стационарная интенсивность А3 входящего в узел s потока.

В третьей главе исследуется открытая экспоненциальная сеть массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявки.

Рассматривается сеть, состоящая из экспоненциальных многолинейных узлов с бесконечной емкостью накопителя и дисциплиной FIFO.

Поток положительных заявок определяется идентично, как в гл. 1, исключая параметер положительной заявки Х= (Xi,.. . ,-Хь) — длительность обслуживания на узлах маршрута.

Наряду с потоком положительных заявок, в узлы СеМО поступают потоки отрицательных заявок. Эти потоки определяются таким же образом, как в гл. 1 (XI 2.1. и П 2.2.) и отличаются следующим образом:

П 2.3. Отрицательная заявка, поступающая в узел s, выбирает случайным образом (с вероятностью 1 /са) один из приборов этого узла, а затем покидает систему, если прибор свободен. Если же на приборе обслуживается положительная заявка, то отрицательная заявка с вероятностями и мгновенно "убивает" эту заявку или не оказывает на нее никакого воздействия (при этом отрицательная и "убитая" заявки покидают СеМО и больше в нее не возвращаются) и с вероятностью wj = 1 — ws — wf превращает ее в отрицательную, которая затем через экспоненциальное с параметром цо время активизации с вероятностью asi(l,r,y,n) поступает в узел с номером а', где (I, г, у) — параметры обслуживания выбранной заявки, п — номер этапа маршрута, на котором обслуживается эта заявка (очевидно, м

r„ = s). Естественно, £ as'(h г, у,п) = 1. а'=1

В § 2 вводятся вспомогательные функции:

Vrn + +7rn)K„ + Wr„) '

+7гп)"тп

n-1

r, y) = П uf(l, r, y), n = 1,1+1, ¿=1

9п{1> «"> у) = у) 9{l, г, у), п = МТТ,

тп(I, г, у) = (ßrn + — (7г„ + Ъ„)К„ + )) , п = М. \ сГп /

Интенсивности потоков отрицательных заявок, поступающих в узлы СеМО, удовлеторяют следующему уравнению:

с» „ I ¿=11<г,.....г,<М*, п=1

м

Через 7~ = 7Г обозначается суммарная интенсивность допол-

.4=1

нительного потока отрицательных заявок, циркулирующего в сети за счет превращения положительных заявок в отрицательные.

В § 3 вводится марковский процесс, описывающий функционирование введенной сети. Прежде всего, вводится дополнительный бес-конечнолинейный экспоненциальный узел с номером 0. В этом узле происходит активизация заявок, превращающихся из положительных в отрицательные. Интенсивность обслуживания в узле 0 равна /io-

Состояние сети обозначается набором z = (zq, zi, ..., zm)-

Вектор zq = (kg,zoi,...,zofc0) соответствует состоянию процесса активизации заявок, причем ко — число активизируемых заявок, а набор zoi, г — 1, к0, с компонентами z0i = (l0i, r0i, yDi,noi) содержит информацию (Zoi, n«, y0i) о маршруте и объемах на этапах маршрута i-й активизируемой заявки и номере этапа, на котором происходит превращение ее в отрицательную (активизация). Величина р0 = 7~/дго есть загрузка на дополнительный узел 0.

Набор zs = (kt,, zsi,..., z0ka), s — 1,М, в свою очередь, описывает состояние .s-ro узла следующим образом: ks — число заявок, находящихся в s-м узле, а набор zsi, s = 1 ,М, г = 1 ,ке, с компонентами zst = (Ln, rst, y3i,nat) содержит информацию (lSi,rs„yoi) о параметрах г-й заявки, находящейся в s-м узле, и ее положении п„, в сети, где пв, — номер этапа маршрута, на котором находится (обслуживается или ожидает обслуживания) заявка.

Множество состояний сети обозначается через 2 — {z}.

В качестве процесса, описывающего функционирование рассматриваемой СеМО, рассмотривается процесс

Z(t) = z, если в момент t сеть находится в состоянии z.

Нетрудно убедиться, что введенный процесс является марковским.

В § 4 доказывается теорема о мультипликативном представлении стационарных вероятностей состояний для рассматриваемой сети.

Теорема. Если 77, я = 1 ,М, — некоторое (неотрицательное) решение системы уравнений (2), причем при таких значениях 7~ для всех узлов s р3 < са, где ра определяются формулой (1), то существует предельное (стационарное) распределение вероятностей состояний процесса Z(t) с плотностью распределения вероятностей

м

p(z) = П^3)'

a=0

причем

РоЫ = е-ро —-J- Д g*0i(loi, roi, y0i) {loi, r0i, y0i), Ko-Mo ¡=1

где po = 7-/At0) о. для остальных узлов s

PsЫ = Pa(0) da(fc.) ( Л Л X

+ t^3 + + "M /

th

*Jl9nJlsi,rsi,yai), «=1

где

Й (и \ - / VW ПРи к° ^ с">

аз["з) - X 1/(с3! С**"с*) при ka > Ca.

В § 5 выводятся следствия из доказанной теоремы, в частности, определяются стационарные плотности распределения процессов,

описывающих функционирование отдельных узлов сети и совместное функционирование только узлов с положительными заявками; стационарное распределение числа заявок в узле (без учета их параметров); среднее время пребывания положительной заявки в узле сети; интенсивность суммарного потока положительных заявок, поступающих в узел сети и нагрузка на узел сети; суммарная интенсивность потока активизированных отрицательных заявок.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

R диссертационной работе рассматриваются следующие открытые экспоненциальные сети массового обслуживания с зависимым обслуживанием и отрицательными заявками:

базовая G-сеть с зависимым обслуживанием с ВСМР-узлами; G-сеть с ВСМР-узлами, исключая экспоненциальные узлы, и до-обслуживанием "убитой" заявки;

G-сеть с экспоненциальными узлами и изменением типа заявки. В работе получены следующие результаты:

1. Для всех трех типов G-сетей получено мультипликативное представление стационарного многомерного распределения числа заявок в узлах сети.

2. Выведена маргинальная стационарная плотность распределения процесса, описывающего функционирование отдельного узла сети.

3. Найдено стационарное распределение числа заявок в узле (без учета их параметров).

4. Найдена стационарная интенсивность Ха входящего в узел s потока.

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Гаврилов Е.В. Об экспоненциальной сети с зависимым обслуживанием и отрицательными заявками // Тезисы докладов XXXIX Всероссийской научной конференции по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин. Москва, 21-25 апреля 2003 г. С. 30. М.: Изд-во РУДН, 2003.

2. Bocharov P., D'Apice С., Gaurilov Е., Pechinkin A. On queueing networks with negative customers and dependent, serviré ¡ j Proc. of XXIII Seminar on Stability Problems for Stochastic Models. Spain, Pamplona, 12-17 May 2003. P. 19.

3. Бочаров U.U., Гаврилоа Е.В., Печинкин A.B. О декомпозиции G-сетей с зависимым обслуживанием // Труды международного семинара "Распределенные компьютерные и телекоммуникационные сети. Теория и приложения." Т. 2. Москва, 29 июня -4 июля 2003 г. С. 38-48. М.: Техносфера, 2003.

4. Bocharov P., D'Apice С., Gavrilov Е., Pechinkin A. Product form solution for G-networks with dependent service // Proc. of First Int. Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks. U.K., Ilkley, 21-23 July 2003. P. 28/1 -28/11.

5. Бочаров U.U., Гаврилов E.B., Печинкин A.B. Анализ G-сети с изменением типа заявок // Материалы международной конференции "Современные математические методы анализа и оптимизации телекоммуникационных сетей". Беларусь, Гомель, 23-25 сентября 2003 г. С. 34-38. Минск: Изд-во БГУ.

6. Бочаров U.U., Д'Апиче Ч., Гаврилов Е.В., Печинкин A.B. О декомпозиции сетей массового обслуживания с зависимым обслуживанием и отрицательными заявками // Автоматика и телемеханика. 2004. N 1. С. 97-116.

7. Бочаров П.Л., Гаврилов Е.В., Печинкин A.B. О декомпозиции G-сетей с зависимым обслуживанием и дообслуживанием положительных заявок // Информационные процессы. 2004. Т. 4. N 1. С. 58-75.

8. Гаврилов Е.В. О G-сетях с зависимым обслуживанием // Тезисы докладов ХХХХ Всероссийской научной конференции по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин. Москва, 2004 г. С. 59-60. М.: Изд-во РУДН, 2004.

Отпечатано в ООО «Оргссрвис-2000» Подписано в печать пл.

Формат60x90/16. Тираж {00 экз. Заказ № 85/0У~37, 115419, Москва, Орджоникидзе, 3

РНБ Русский фонд

14921

ВВЕДЕНИЕ

ГЛАВА 1. Сети массового обслуживания с зависимым обслуживанием и отрицательными 17 заявками

1. Описание сети

2. Вспомогательные функции

3. Марковский процесс, описывающий функционирование сети

4. Мультипликативное представление стационарного распределения марковского процесса

5. Следствия 45 ВЫВОДЫ

ГЛАВА 2. G-сети с зависимым обслуживанием и дообслуживанием положительных заявок

1. Описание сети

2. Вспомогательные функции

3. Марковский процесс, описывающий функционирование сети

4. Мультипликативное представление стационарного распределения марковского 54 процесса

5. Следствия

ВЫВОДЫ

ГЛАВА 3. Экспоненциальные сети массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявок

1. Описание сети

2. Вспомогательные функции

3. Марковский процесс, описывающий функционирование сети

4. Мультипликативное представление стационарного распределения марковского 80 процесса

5. Следствия 104 ВЫВОДЫ

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

Функционирование сетевых структур связано с передачей и обработкой большого числа информационных потоков. Вероятностная природа этих потоков приводит к появлению целого ряда проблем, возникающих как на этапе проектирования сетевых систем, так и на этапах их эксплуатации и модернизации. Это, в свою очередь, стимулирует математические исследования, направленные на разработку адекватных стохастических моделей и их анализ с целью получения количественных оценок показателей производительности сетевых систем.

Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории сетей массового обслуживания (СеМО). Возможности применения СеМО в качестве моделей сетевых систем и их компонентов отражены, например, в [1,2,10,14,15,21,66,67]. В связи с этим большое внимание в литературе уделяется собственно анализу СеМО (см., например [1,2,10,14,20,31,67,77,83]).

В теории СеМО центральное место занимают так называемые мультипликативные сети, для которых стационарное многомерное распределение марковского процесса, описывающего стохастическое поведение сети, представляется в мультипликативной форме.

Впервые такой результат был получен в работе [75] для открытой однородной экспоненциальной сети с узлами неограниченной емкости, которая затем была названа сетью Джексона по имени автора работы. Базовое условие, которое должно выполняться для получения мультипликативного решения для сети Джексона, предполагает пуассоновость всех входящих в сеть потоков заявок и экспоненциальный характер распределений длительностей их обслуживания в узлах сети.

Следующим наиболее серьезным шагом в развитии теории мультипликативных сетей явилось появление работы [25]. В ней была сформулирована так называемая теорема ВСМР, обосновывающая мультипликативное решение для большого класса открытых сетей, обобщающих сети Джексона. Однако, в отличие от сетей Джексона, времена обслуживания в узлах ВСМР-сетей не обязательно распределены по экспоненциальному закону.

В дальнейшем, развитие теории мультипликативных сетей связано с разного рода обобщениями сетей Джексона и ВСМР-сетей.

Например, в работах [16,77,79,80] рассматривались зависимости интенсивностей входящих потоков от числа заявок в сети, зависимости вероятностей переходов заявок между узлами сети от состояния этих узлов, ограничения на число заявок в сети и обходы узлов. В публикациях [2,10,14,20,31,67,77,83] достаточно полно описаны различные исследования сетей Джексона, ВСМР-сетей и их многочисленных обобщений.

Важные результаты в теории мультипликативных сетей были получены в работах [18,19] для более общего, чем ВСМР-сети, класса сетей с так называемым зависимым обслуживанием. Так, в [18] теорема ВСМР была распространена на случай открытых СеМО с зависимым обслуживанием, в которых каждая заявка, входящая в сеть, характеризуется набором случайных параметров: последовательностью номеров проходимых заявкой узлов — маршрутом заявки, длиной маршрута и объемами и длительностями обслуживания заявки в различных узлах сети. Мультипликативное представление, полученное для СеМО, рассмотренной в [18], расширяет результаты работы [19], где была получена мультипликативная форма для стационарных вероятностей открытых СеМО, маршруты и длительности обслуживания заявок в которых задаются траекториями регенерирующего процесса.

Принципиально новый класс открытых сетей, допускающий мультипликативное решение, был введен Е.Геленбе в работах [48,49] а затем активно изучался в работах Е.Геленбе и других авторов [3,13,17, 23,24,26,27,32-47,50-56,59-65,68-74,76,78,81,82]. Это сети, названные G-сетями в честь их основоположника, в которых вместе с потоком обычных (положительных) заявок на узлы сети поступают также дополнительные пуассоновские потоки отрицательных заявок или/и триггеров.

Отрицательная заявка при поступлении в узел сети может уничтожить одну или несколько положительных заявок, если таковые имеются в наличие в данном узле, и покидает сеть, не получая для себя никакого обслуживания.

Поступивший на узел сети триггер мгновенно перемещает положительную заявку из одного узла с заданной вероятностью в некоторый другой узел сети.

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

Первые работы по исследованию G-сетей [48,49] появились в 1989г. В данных работах была исследована базовая G-сеть — сеть с однолинейными узлами неограниченной емкости, пуассоновскими потоками заявок, поступающими на узлы сети, и экспоненциальными распределениями длительностей обслуживания заявок, при этом дополнительный поток, поступающий в сеть, представляет собой лишь поток отрицательных заявок. Отрицательная заявка, поступившая на узел сети, мгновенно уничтожает положительную заявку в очереди или на приборе, если нет очереди в данном узле, и тут же покидает сеть. Отрицательная заявка, заставшая данный узел пустым, сразу покидает сеть, не оказывая на ее функционирование никакого влияния.

Очевидным обобщением базовой G-сети явилась работа [55], в которой подробно была исследована модель G-сети, когда отрицательная заявка с заданной вероятностью уничтожает не одну, а несколько положительных заявок, при этом количество уничтожаемых заявок случайно и задается некоторым распределением вероятностей.

В 1992 г. в работе [68] Геленбе ввел понятие сигнала, обобщающее понятия отрицательной заявки и триггера. Положительная заявка по окончании обслуживания в узле i направляется в узел j с вероятностью pfj снова как положительная заявка, с вероятностью р~- — м как сигнал и с вероятностью рю = 1 — (jpf. + р~Л уходит из сети;

- J J j=i здесь М — число узлов в сети. Сигнал, поступающий в не пустой узел G-сети, с вероятностью qjs мгновенно перемещает положительную заявку из узла j в узел s, т.е. срабатывает как триггер, или м с вероятностью qjo = ^ qj3 сигнал срабатывает как отрицательная

8=1 заявка и уничтожает в узле j группу положительных заявок размера В{. Исследования G-сети с сигналами представлены также в работах [3,27,38-40,49,73] и ряде других работ (см., например, обзоры [9,22]).

Дальнейшим развитием теории G-сетей стало изучение G-сетей с несколькими классами положительных заявок и сигналов. Этой тематике был посвящен целый цикл работ [34,35,38,39,45,47,56,65,68,73,81].

Первоначально в работах [47,56,68] была исследована G-сеть с несколькими классами положительных и отрицательных заявок в предположении, что число классов обоих типов заявок одинаково. При этом в каждой из этих работ рассматриваются свои собственные варианты взаимодействия отрицательных и положительных заявок различных типов.

Так, в [68] предполагается, что отрицательные заявки одного класса могут уничтожить положительные заявки только того же класса. В работе [56] используется алгоритм случайного выбора типа положительной заявки, т.е. при поступлении отрицательной заявки в узел г, в котором находится к{ > О положительных заявок (без учета их типа), с вероятностью kdjki будет уничтожена положительная заявка типа с.

В [47] рассматривается G-сеть с различными дисциплинами обслуживания положительных заявок в узлах: FIFO — обслуживание в порядке поступления, PS — разделение процессора и LIFO/PR — инверсионный порядок обслуживания с прерыванием обслуживания. Выбор положительной заявки для уничтожения происходит в соответствии с установленной в узле дисциплиной обслуживания, при этом в узле i отрицательная заявка класса m может уничтожить положительную заявку класса к с вероятностью i^tmfc- В [65] результаты [47] были распространены на случай нескольких типов триггеров.

В работах [13,16,17] были рассмотрены различные модификации сетей с отрицательными заявками и обходами. Для G-сетей с обходами в [13,16,17] также было получено мультипликативное решение.

Интересная разновидность G-сети была исследована в работе [36]. Это G-сеть с катастрофами. Ее отличие от базовой G-сети состоит в том, что при поступлении в узел отрицательной заявки-катастрофы она уничтожает все положительные заявки в этом узле.

Во всех предыдущих работах предполагается, что сигнал, поступающий в не пустой узел G-сети, срабатывает мгновенно. Работы

3,27] развивают теорию G-сетей на случай, когда активизация (срабатывание) сигнала, поступившего в сеть, происходит не сразу, а через случайное время.

Цикл работ [4-8,11,12,28,29,30], опубликованных в последние годы, связан с развитием мультипликативной теории для G-сетей с зависимым обслуживанием.

Достаточно полный обзор публикаций по G-сетям, включая G-системы (однофазные и двухфазные), содержат обзоры [9,22,58]. Новые направления в развитии G-сетей излагаются в [57].

Теория G-сетей возникла в связи с необходимостью аналитического моделирования биофизических нейронных сетей [48,49]. В биофизических нейронных сетях циркулируют импульсно-подобные сигналы, которые генерируются через случайные интервалы времени, а движение этих импульсов в нейронной сети имеет очень много похожего на циркуляцию заявок в СеМО. При этом сигнал возбуждения (положительная заявка) в принимающем его нейроне (узле сети) увеличивает его потенциал на единицу, а сигнал торможения (отрицательная заявка) уменьшает потенциал нейрона на единицу.

Позже G-сети нашли свое применение для целого ряда других практических приложений. Например, в работах [33,42,43,46,50,51,54, 56,59,60,64,69-71] описаны самые разнообразные приложения G-сетей при моделировании нейронных сетей, информационно-вычислительных систем и сетей (например, в задачах управления потоками в вычислительных сетях, при моделировании эффекта вируса в сетях и др.), производственных систем и сетей, в задачах распознавания образов, в задачах комбинаторной оптимизации и т.д.

Актуальность работы. В последнее время наблюдается бурное развитие информационно-телекоммуникационных технологий и сетевых систем. Функционирование сетевых структур связано с бесперебойной передачей и обработкой большого числа информационных потоков. Вероятностная природа этих потоков приводит к появлению целого ряда проблем, возникающих как на этапе проектирования сетевых систем, так и при их эксплуатации и модернизации. Это, в свою очередь, стимулирует математические исследования, направленные на разработку адекватных стохастических моделей и их анализ с целью получения количественных оценок показателей производительности сетевых систем. Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории сетей массового обслуживания.

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

Сравнительно недавно в теории мультипликативных сетей появилось новое перспективное направление, связанное с исследованием СеМО с отрицательными заявками — G-сетей. Зародившаяся около 15 лет назад, теория G-сетей все это время интенсивно развивалась. Были исследованы различные модификации G-сетей, обобщающие сети Джексона, ВСМР-сети и др. Результаты этих исследований опубликованы в десятках работ. Такой интерес к этой проблематике со стороны ученых всего мира показывает практическую необходимость в дальнейшем развитии теории G-сетей.

Одним из важных направлений в исследовании G-сетей является развитие мультипликативной теории для сетей с зависимым обслуживанием и отрицательными заявками — G-сетей с зависимым обслуживанием.

Исследования G-сетей с зависимым обслуживанием ранее в литературе не проводились, поэтому тема диссертационной работы является актуальной.

Целью диссертационной работы является получение мультипликативного представления для стационарного распределения числа заявок в узлах G-сети с зависимым обслуживанием, в которой каждая заявка, поступившая в сеть, характеризуется набором случайных параметров: ее маршрутом по сети (последовательностью проходимых заявкой узлов), длиной маршрута, а также объемом заявки и длительностью ее обслуживания на каждом этапе маршрута, для трех модификаций G-сети: базовой G-сети с зависимым обслуживанием с ВСМР-узлами;

G-сети с ВСМР-узлами, исключая экспоненциальные узлы, и дообслуживанием "убитой" заявки;

G-сети с экспоненциальными узлами и изменением типа заявки.

Научная новизна и результаты, выносимые на защиту, состоят в следующем.

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

G-сети с ВСМР-узлами, исключая экспоненциальные узлы, и дообслуживанием "убитой" заявки; G-сети с экспоненциальными узлами и изменением типа заявки.

Методы исследования. В диссертационной работе применяются в основном методы теории вероятностей, теории случайных процессов и теории массового обслуживания.

Обоснованность научных положений. Все полученные в диссертации теоретические результаты обоснованы строгими математическими доказательствами.

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

Реализация результатов работы. Исследование сетей массового обслуживания с зависимым обслуживанием и отрицательными заявками проводилось в рамках НИР "Разработка теоретических основ анализа очередей в информационно-вычислительных и телекоммуникационных сетях: алгоритмический подход" (государственный регистрационный номер 01.2.00 105246), выполняемой в соответствии с тематическим планом РУДН на 2001 -2005 гг., а также в рамках гранта Российского фонда фундаментальных исследований № 02-0790147 "Математические методы и программное обеспечение моделирования информационных, вычислительных и телекоммуникационных систем".

Апробация работы. Материалы диссертации докладывались на международных конференциях: "Распределенные компьютерные и телекоммуникационные сети" (Москва, 2003 г.); "Современные математические методы анализа и оптимизации телекоммуникационных сетей" Беларусь, Гомель, 2003 г.); "Performance Modelling and Evaluation of Heterogeneous Networks" (HET-NETs 2003) (Great Britain, Ilkley, 2003 г.); XXIII International Seminar on Stability Problems for Stochastic Models (Spain, Pamplona, 2003 г.); на XXXIX и XXXX Всероссийских научных конференциях по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин (Москва, РУДН, 2003, 2004 гг.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН.

Публикации. По материалам диссертации опубликовано 8 работ, из них 2 в центральной печати.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Каждая глава состоит из параграфов; формулы, теоремы, леммы и следствия нумеруются внутри каждой главы. При ссылке на формулы, теоремы, леммы и следствия из другой главы указывается также номер главы.

Выводы

В данной главе проведен анализ открытой экспоненциальной сети массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявки. Каждая положительная заявка, поступившая в сеть, характеризуется набором случайных параметров: маршрутом по сети (последовательностью проходимых заявкой узлов) (вектор г), длиной маршрута (Z), а также объемом заявки (вектор у) и длительностью ее обслуживания на каждом этапе маршрута (вектор х). Отрицательная заявка, поступающая в узел сети, выбирает случайным образом один из приборов этого узла, а затем покидает систему, если прибор свободен. Если же на приборе обслуживается положительная заявка, то отрицательная заявка либо мгновенно "убивает" эту заявку, либо не оказывает на нее никакого воздействия (при этом отрицательная и "убитая" заявки покидают СеМО и больше в нее не возвращаются), либо превращает ее в отрицательную, которая затем через определенное время активизации поступает в один из узлов сети. В главе представлены следующие результаты:

1. Доказано, что стационарное распределение числа заявок в узлах G-сети представимо в мультипликативной форме.

2. Выведена маргинальная стационарная плотность распределения процесса, описывающего функционирование отдельного узла сети.

3. Найдено стационарное распределение числа заявок в узле (без учета их параметров).

4. Получена стационарная плотность распределения процесса, описывающего совместное функционирование только узлов с положительными заявками.

5. Найдена суммарная интенсивность дополнительного потока отрицательных заявок, циркулирующего в сети за счет превращения положительных заявок в отрицательные.

6. Получены следующие характеристики сети:

- стационарная вероятность того, что положительная заявка с параметрами (I, г, у) не будет "убита" и не превратится в отрицательную до п-го этапа;

- стационарная вероятность того, что положительная заявка с параметрами (/, г, у), не "убитая" и не превратившаяся в отрицательную до п-го этапа, не будет "убита" и не превратится в отрицательную на этом этапе (в узле гп);

- стационарная вероятность того, что положительная заявка с параметрами (/, г, у), не "убитая" и не превратившаяся в отрицательную до п-го этапа, превратится в отрицательную на этом этапе (в Узле гп).

7. Выведено среднее время пребывания положительной заявки с параметрами (/, г, у) на n-м этапе в узле s = гп.

8. Найдены интенсивность суммарного потока положительных заявок, поступающих в узел s, и нагрузка на узел s.

ЗАКЛЮЧЕНИЕ

В диссертации исследовались следующие открытые экспоненциальные сети массового обслуживания с зависимым обслуживанием и отрицательными заявками: базовая G-сеть с зависимым обслуживанием с ВСМР-узлами;

G-сеть с ВСМР-узлами, исключая экспоненциальные узлы, и дообслуживанием "убитой" заявки;

G-сеть с экспоненциальными узлами и изменением типа заявки.

В работе получены следующие новые результаты:

1. Для всех трех типов G-сетей получено мультипликативное представление стационарного многомерного распределения числа заявок в узлах сети.

2. Выведена маргинальная стационарная плотность распределения процесса, описывающего функционирование отдельного узла сети.

3. Найдено стационарное распределение числа заявок в узле (без учета их параметров).

4. Найдена стационарная интенсивность As входящего в узел s потока.

1. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

2. Бочаров П.П. Сеть массового обслуживания с сигналами со случайной задержкой // АиТ. 2002. N 9. С. 90-101.

3. Бочаров П.П., Д'Апиче Ч., Гаврилов Е.В., Печинкин А.В. О декомпозиции сетей массового обслуживания с зависимым обслуживанием и отрицательными заявками // АиТ. 2004. NIC. 97-116.

4. Бочаров П.П., Гаврилов Е.В., Печинкин А.В. О декомпозиции G-сетей с зависимым обслуживанием и дообслуживанием положительных заявок // Информационные процессы. 2004. Т. 4. N 1. С. 58-75.

5. Бочаров П.П., Гаврилов Е.В., Печинкин А.В. Экспоненциальная сеть массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявок // АиТ. 2004. N8.

6. Бочаров П.П., Вишневский В.М. G-сети: развитие теории мультипликативных сетей // АиТ. 2003. N 5. С. 46-74.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: РИЦ "Техносфера", 2003.

8. Довженок Т.С. Инвариантность стационарного распределения сетей с обходами и "отрицательными" заявками // АиТ. 2002. N 9. С. 97-111.

9. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

10. Клейнрок JI. Вычислительные системы с очередями. М: Мир, 1979.

11. Малинковский Ю.В. Сети массового обслуживания с обходами узлов заявками // АиТ. 1991. N 2. С. 102-110.

12. Малинковский Ю.В., Никитенко О. А. Стационарное распределение состояний сетей с обходами и "отрицательными" заявками // АиТ. 2000. N 8. С. 79-85.

13. Печинкин А.В., Рыков В.В. О декомпозиции сетей массового обслуживания с зависимым обслуживанием. Препринт. М.: Изд-во РУДН, 1997.

14. Толмачев A.JI. Сети обслуживания заявок с регенерирующими траекториями // Проблемы передачи информации. 1986. Т. 22. N 2. С. 59-68.

15. Уолранд Дж. Введение в теорию сетей массового обслуживания. М.: Мир, 1993.

16. Шварц М. Сети связи: протоколы, моделирование и анализ. М.: Наука, 1992.

17. Artalejo J.R. G-networks: a versatile approach for work removal in queueing networks // Europ. J. Oper. Res. 2000. V. 126. P. 233-249.

18. Atalay V., Gelenbe E. Parallel algorithm for colour texture generation using the random neural network model // Int. J. Pattern Recognition Artif. Intell. 1992. V. 6. N 2,3. P. 437-446.

19. Atalay V., Gelenbe E., Yalabik N. Texture generation with the random neural networks model // Artificial Neural Networks. V. 1 / (Ed.) Kohonen T. and al. Amsteredam: North-Holland, 1991. P. 111-117.

20. Baskett F., Chandy K.M., Muntz R.R., Palacios F.G. Open, closed amd mixed networks of queues with different classes of customers // J. ACM. 1975. V. 22. P. 248-260.

21. Bocharov P.P. On queueing networks with signals // Proc. Int. Conference "Applied Stochastic Models and Information Processes". Petrozavodsk, 8-13 September 2002. P. 27-30.

22. Bocharov P.P. On queueing networks with signals // Информационные процессы. 2002. Т. 2. N 2. С. 157-160.

23. Bocharov P., D'Apice C., Gavrilov E., Pechinkin A. On queueing networks with negative customers and dependent service // Proc. of XXIII Seminar on Stability Problems for Stochastic Models. Spain, Pamplona, 12-17 May 2003. P. 19.

24. Bocharov P., D'Apice C., Gavrilov E., Pechinkin A. Product form solution for G-networks with dependent service // RAIRO — Operations Research. 2004. V. 38. N 2. P. 105-120.

25. Boucherie R.J. Product form in queueing networks / Ph. D. Thesis. Free University, Amsterdam. 1992.

26. Boucherie R.J., van Dijk N.M. Local balance in queueing networks with positive and negative customers // Annals Oper. Res. 1994. V. 48. P. 463-492.

27. Bourrely J., Gelenbe E. Memoires associatives: evaluation et architectures // Comptes-Rendus Acad. Sci. 1989. V. 309. Serie II. P. 523-526.

28. Chao X. A note on queueing networks with signals and random triggering time // Prob. Eng. Inf. Sci. 1994. V. 8. P. 213-219.

29. Chao X. Networks of queues with customers, signals and arbitrary service times distributions // Oper. Res. 1995. V. 43. N 3. P. 537-544.

30. Chao X. A queueing network model with catastrophes and product form solution // Oper. Res. Lett. 1995. V. 18. P. 75-79.

31. Chao X., Miyazava M., Serfozo R., Takada H. Markov network processes with product form stationary distributions // Queueing systems. 1998. V. 28. P. 377-401.

32. Chao X., Pinedo M. On generalized networks of queues with positive and negative arrivals // Prob. Eng. Inf. Sci. 1993. V. 7. P. 301-334.

33. Chao X., Pinedo M. Networks of queues with batch services, signals and product form solutions // Oper. Res. Lett. 1995. V. 17. P. 237-242.

34. Chao X., Pinedo M. On queueing networks with signals and history-dependent routing // Prob. Eng. Inf. Sci. 1995. V. 9. P. 341-354.

35. Chao X., Zheng S. A result on networks of queues with customer coalescence and state-dependent signalling J j J. Appl. Prob. 1998. V. 35. P. 151-164.

36. Cramer C., Gelenbe E. Video quality and traffic QoS in learning-based subsampled and receiver-interpolated video sequences // IEEE Journal on Selected Areas in Communications. 2000. V. 18. N 2. P. 150-167.

37. Feng Y., Gelenbe E. Adaptive object tracking and video compression // Network and Information Systems Journal. 1999. V. 1. N 4-5. P. 371-400.

38. Fourneau J.N. Computing the steady state distribution of networks with positive and negative customers // Proc. 13 IMACS World Cong. Comput. Appl. Math. Dublin, 1991.

39. Fourneau J.N., Gelenbe E. Multiple class G-networks // Proc. Conf. ORSA Techn. Committee on Comput. Sci. Williamsburg VA, Pergamon, 1992.

40. Fourneau J.N., Hernandez M. Modelling defective parts in a flow system using G-networks // Proc. Second Int. Workshop on Perfor-mability Modelling of Comput. and Commun. Syst. Le Mont Saint-Michel, June 1993.

41. Fourneau J.N., Gelenbe E., Suros R. G-networks with multiple classes of negative and positive customers // Theoret. Comput. Sci. 1996. V. 155. P. 141-156.

42. Gelenbe E. Reseaux stochastiques ouverts avec clients negatifs and positifs, et reseaux neuronaux // Comptes-Rendus de l'Academie des Sci. 1989. V. 309. Serie II. P. 972-982.

43. Gelenbe E. Random neural networks with negative and positive signals and product form solution // Neural Comput. 1989. V. 1. N 1. P. 502-510.

44. Gelenbe E. Reseaux neuronaux et aleatoires stables // Comptes Rendus de l'Academie Sci. 1990. V. 310. Serie II. P. 177-180.

45. Gelenbe E. Stability of the random neural network model // Neural Comput. 1990. V. 2. P. 239-247.

46. Gelenbe E. Product form queueing networks with negative and positive customers // J. Appl. Prob. 1991. V. 28. P. 656-663.

47. Gelenbe E. G-networks with triggered customer movement // J. Appl. Prob. 1993. V. 30. P. 742-748.

48. Gelenbe E. Learning in the recurrent random neural network J j Neural Comput. 1993. V. 5. N 1. P. 154-164.

49. Gelenbe E. G-networks with signals and batch removal // Prob. Eng. Inf. Sci. 1993. V. 7. P. 335-342.

50. Gelenbe E. G-networks: a unifying model for neural and queueing networks // Ann. Oper. Res. 1994. V. 48. P. 433-461.

51. Gelenbe E. (Ed.) Feature issue on G-networks // Eur. J. Oper. Res. 2000. V. 130.

52. Gelenbe E. The first decade of G-networks. European J. Opns. Res. 2000. V. 126 P. 231-232.

53. Gelenbe E., Batty F. Minimum cost graph covering with the random network model // Proc. Conf. ORSA Techn. Committee Comput. Sci. Williamsburg VA, Pergamon, 1992.

54. Gelenbe E., Fourneau J.M. Random neural networks with multiple classes of signals // Neural Computation. 1999. V. 11 (4). P. 953-963.

55. Gelenbe E., Fourneau J.M. G-Networks with resets // Performance Evaluation. 2002. V. 49. P. 179-192.

56. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals // J. Appl. Prob. 1991. V. 28. P. 245-250.

57. Gelenbe E.} Hussain K. Learning in the multiple class random neural network // IEEE Trans, on Neural Networks. 2002. V. 13 (6). P. 1257-1267.

58. Gelenbe E., Kouhi V., Pekergin F. Dinamical random neural approach to the traveling salesman problem // Elektrik. 1994. N 2. P. 1-10.

59. Gelenbe E., Labed A. G-networks with multiple class of signals and positive customers I j Eur. J. Oper. Res. 1998. V. 108. P. 293-305.

60. Gelenbe E., Mitrani I. Analysis and synthesis of computer systems // New York and London: Academic Press, 1980.

61. Gelenbe E., Pujolle G. Introduction to queueing networks. N.Y.: John Wiley, 1998.

62. Gelenbe E., Schassberger R. Stability of G-networks // Prob. Eng. Inf. Sci. 1992. V. 6. P. 271-276.

63. Gelenbe E., Shachnai H. On G-networks and resource allocation in multimedia systems // European J. Opns. Res. 2000. V. 126. N 2. P. 308-318.

64. Gelenbe, Seref E., Xu Z. Simulation with learning agents // Proceedings of the IEEE. 2001. V. 89. N 2. P. 148-157.

65. Gelenbe E.f Tucci S. Performances d'un systeme informatique duplique // Comptes Rendus de l'Academie Sci. 1991. V. 312. Serie II. P. 27-30.

66. Henderson W. Queueing networks with negative customers and negative queue lengths // J. Appl. Prob. 1993. V. 30. P. 931-942.

67. Henderson W., Northcote B.S., Taylor P. G. State-dependent signalling in queueing networks // Adv. Appl. Probab. 1994. V. 26. P. 436-455.

68. Henderson W., Northcote B.S., Taylor P. G. Geometric equilibrium distribution for queues with interactive batch departures j j Ann. Oper. Res. 1994. V. 48. P. 493-511.

69. Jackson J.R. Networks of waiting lines I j Operations Research. 1957. V. 15. P. 234-265.

70. Jain G. A rate conservation analysis of queues and networks with work removal / Ph. D. Thesis. Indust. Eng. Oper. Res. Columbia Univ., 1996.

71. Kelly F.P. Reversibility and stochastic networks. N.Y.: John Wiley, 1979.

72. Kim K., Seila A.F. A generalized cost model for stochastic clearing systems // Comput. Oper. Res. 1993. V. 20. N 1. P. 67-82.

73. Lam S.S. Queueing networks with population size constraints // IBM J. Res. Develop. 1977. V. 21. N 4. P. 779-793.

74. Noetzel A.S. Generalized queueing discipline for product form network solution // J. ACM. 1979. V. 26. N 4. P. 779-793.

75. Miyazava M. Insensitivety and product form decompasibility of relocatable GSMP // Adv. Appl. Probab. 1993. V. 25. P. 415-437.

76. Northcote B.S. Signalling in product form queueing networks // Ph. D. Thesis. Univ. of Adelaide, 1993.

77. Van Dijk N.M. Queueing networks and product forms. N.Y.: John Wiley & Sons, 1993.