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

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

Глава 1. ПРОБЛЕМА УЧЕТА ВРЕМЕНИ НА ПЕРЕДАЧУ ТРЕБОВАНИЙ ПРИ РАСЧЕТЕ ХАРАКТЕРИСТИК СИСТЕМ И СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

1.1. О необходимости учета времени на передачу требований в СМО и СеМО.

1.2. Анализ некоторых результатов по СМО и СеМО.

1.3. Задача исследования СМО и СеМО с учетом времени на передачу требований

1.4. Краткие выводы по главе.

Глава 2. СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С КОНЕЧНЫМ ИСТОЧНИКОМ И КАНАЛОМ ПЕРЕДАЧИ ТРЕБОВАНИЙ.

2.1. Постановка задачи.».,,,.>;.*.v.

2.2. Асимптотическое разложение стационарных вероятностей состояний для СМО с конечным источником и однолинейным КПТ (случай зависимости параметров от состояния СМО с КПТ).

2.3. Асимптотическое разложение стационарных вероятностей состояний для СМО с конечным источником и многолинейным КПТ (случай зависимости параметров от состояния СМО с КПТ).

2.4. Аналитическое решение задачи нахождения стационарного распределения вероятностей состояний СМО с конечным источником и КПТ (случай зависимости параметров от состояний соответствующих узлов СМО с КПТ).

2.4.1. Постановка задачи.

2.4.2. СМО с конечным источником и однолинейным КПТ (случай зависимости параметров от состояния соответствующего узла).

2.4.3. СМО с конечным источником и многолинейным КПТ (случай зависимости параметров от состояния соответствующего узла).

2.5. Краткие выводы по главе.

Глава 3. СЕТЬ МАССОВОГО ОБСЛУЖИВАНИЯ С КАНАЛОМ ПЕРЕДАЧИ ТРЕБОВАНИЙ БЕЗ БЛОКИРОВОК.

3.1. Постановка задачи.

3.2. Стационарное распределение вероятностей состояний.

3.3. Асимптотическое разложение стационарного распределения вероятностей состояний рассматриваемой СеМО с многолинейным КПТ (случай зависимости параметров от состояния сети).

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

3.5. Частные случаи.

3.6. Краткие выводы по главе.

Глава 4. СЕТЬ МАССОВОГО ОБСЛУЖИВАНИЯ С БЛОКИРОВКОЙ В КАНАЛЕ ПЕРЕДАЧИ ТРЕБОВАНИЙ.

4.1. Постановка задачи.

4.2. Стационарное распределение вероятностей состояний.

4.3. Асимптотическое разложение стационарного распределения вероятностей состояний рассматриваемой замкнутой СеМО с блокировкой в многолинейном КПТГ

4.4. Случай замкнутой СеМО с блокировкой в КПТ и параметрами (1,1).

4.5. Случай замкнутой СеМО с блокировкой в КПТ и единичными емкостями КИТ.

4.6. Краткие выводы по главе.

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

1. Горизонтальному направлению, под которым понимается создание ИВС в различных отраслях и объектах промышленности, сельского хозяйства, образования, культуры и т. д.

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

3. Создание глобальных ИВС типа Internet, которые предназначены для информационного обслуживания населения всего земного шара по всем возможным информационным вопросам.

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

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

Исследованию СеМО посвящены работы Г.П. Башарина, А.А. Боровкова, П.П. Бочарова, О.И. Бронштейна, Р. Бушери, В.М. Вишневского, Дж. Волранда, Н. Дайка, Р.Л. Добрушина, Дж. Джексона, В.А. Ивницкого, В.В. Калашникова, Ф.П. Келли, М.Я. Кельберта, Д. Кенига, Л. Клейнрока, И.Н. Коваленко, С. Лавенберга, А.И. Ляхова, Ю.В. Малинковского, В.А. Малышева, Б. Меламеда, М. Мия-зава, Е.В. Морозова, Р. Мюнтца, Б. Питтеля, А.Н. Рыбко, Р.Ф. Серфозо, Ю.М. Сухова, А.Л. Толмачева, Д. Тоусли, В.Г. Ушакова, С. Фосса, Дж. Ховарда, К. Чен-ди, Р. Шассбергера, С.Ф. Яшкова и многих других.

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

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

Исследование СеМО с учетом времени передачи требования (СеМО с УВПТ) является новой проблемой. Поэтому возникает необходимость расчета характеристик СеМО с УВПТ, что является новой и весьма актуальной научной проблемой, требующей разработки соответствующих математических методов.

Цель диссертационной работы заключается в разработке математических методов и алгоритмов расчета характеристик СеМО с УВПТ.

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

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

Научная новизна работы заключается в разработке математических методов расчета характеристик новых объектов исследования — СМО и СеМО с УВПТ. Причем учитывались некоторые особенности функционирования реальных ИВС (например, наличие конечного числа источников пакетов, возможности блокировки пакетов в процессе передачи и т. д.).

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

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

Полученная для ряда СеМО с КПТ мультипликативная форма, важная сама по себе, имеет значение и в качестве тестов при отработке программ имитационного моделирования реальных ИВС.

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

Апробация работы. Основные положения работы докладывались и обсуждались на: XI, XII и XIV Международных зимних школах-семинарах по теории массового обслуживания, проводимых в республике Беларусь; IV Международном форуме по информатизации и Международной конференции по информационным сетям и системам; XI Международной конференции по проблемам теоретической кибернетики; Международной конференции и Чебышевских чтениях, посвященных 175-летию со дня рождения П.Л.Чебышева; II Международной конференции по новым информационным технологиям в образовании; XXX Конференции молодых ученых ИППИ РАН; семинаре "Информационные сети и системы"; International conference of Distributed Computer Communication Networks (Theory and Applications) 1996 and 1997 years; Bulgarian-Russian Seminar. Methods and Algorithms for Distribution Information Systems Design: Theory and Application. Результаты диссертации докладывались на научных семинарах в ИППИ РАН, в частности, на научном семинаре Добрушинской математической лаборатории под руководством Р.А. Минлоса, на научном семинаре под руководством Б.С. Цыбакова, на научном семинаре ВМК МГУ под руководством В.М. Золотарева, В.В. Калашникова, В.М. Круглова, на научном семинаре Института прикладных математических исследований Карельского научного центра РАН (ИПМИ КНЦ РАН).

Публикации. По теме диссертации опубликовано 15 печатных работ, из них 3 статьи в реферируемом научно-техническом журнале (Проблемы передачи информации).

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, изложенных на 130 страницах, содержит 3 рисунка и список цитируемой литературы из 139 наименований на 11 страницах. Структура и содержание глав отражены в оглавлении диссертации

ЗАКЛЮЧЕНИЕ

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

1. Дан аналитический обзор литературы по сетям массового обслуживания. Из анализа литературы сделан вывод о новизне и актуальности проблемы учета немгновенной передачи требований в реальных системах обслуживания. Из этого анализа вытекает необходимость разработки математических методов расчета характеристик СМО и СеМО с учетом времени передачи требований.

2. Разработана в общем виде постановка задачи определения характеристик сети массового обслуживания с каналами передачи требований, осуществляющими немгновенную передачу требований.

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

В совместных работах [135] и [136] вклад диссертанта состоит в разработке метода асимптотического разложения стационарного распределения вероятностей состояний рассматриваемой замкнутой СеМО с блокировкой в однолинейном и многолинейном КПТ, соответственно, а также разработке алгоритма расчета коэффициентов такого разложения для произвольного числа шагов. Для СеМО с блокировкой в КПТ и параметрами (1,1) в работе [135] диссертантом дополнительно предложен алгоритм непосредственного расчета стационарного распределения с использованием рекуррентных формул.

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

2. Башарин Г.П., Толмачев А.Л. Некоторые результаты теории сетей массового обслуживания//Методы развития теории телетрафика. ИППИ АН СССР. М.: Наука, 1979, С. 52 -65.

3. Башарин Г.П., Чумаев А.В. Условия частичного и детального баланса для моделирования гибкой производственной системы//АиТ. 1989. №4. С. 109-115.

4. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей ограниченной емкости с потерями//В кн.: Тез. докл. IX Всесоюз. школы-семинара по вычислительным сетям. М.: ВИНИТИ, 1984, С. 88 — 94.

5. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей массового обслуживания конечной емкости с потерями или блоки-ровками//АиТ. 1987. №1. С. 55 -65.

6. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: Издат. У нив. дружбы народов, 1995.

7. Бронштейн О.И., Якобсон Г.Р. Имитация и расчет замкнутых сетей массового обслуживания. Методы и структура систем телетрафика. М.: Наука, 1979.

8. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. М.: Сов. радио, 1973.

9. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978.

10. Вишневский В.М., Герасимов А.И. Исследование потоков в замкнутых экспоненциальных сетях массового обслужива,ния//Проблемы управления и теории информации. 1983. Т. 12. №6. С. 391 -404.

11. Вишневский В.М., Твердохлебов А.С. Модели замкнутых сетей с блокировками для анализа мультипрограммных вычислительных систем//АиТ. 1980.5. С. 172- 179.

12. Гихман Н.И., Скороход А.В. Введение в теорию случайных процессов. М.: Наука, 1977.

13. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1964.

14. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. М.: Физматгиз, 1963.

15. Денисьева О.М. Системы массового обслуживания с ограниченным ожиданием. М.: Радио и связь, 1986.

16. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973.

17. Добрушин Р.Д., Сухов Ю.М. Асимптотическое исследование звездообразных сетей коммутации сообщений с большим числом радиальных лучей //Проблемы передачи информации. 1976. Т. 12. вып. 1, с. 70 — 94.

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

19. Ивницкий В.А. Сети массового обслуживания и их применение в ЭВМ//Зарубежная радиоэлектроника. 1977. №7. С. 33 — 70.

20. Ивницкий В.А. Об условии независимости стационарных вероятностей состояний разомкнутой сети однолинейных систем с потерями от вида распределений длительностей обслуживания//Изв. АН СССР. Техн. кибернетика. 1981. Т. 19. №4. С. 136- 140.

21. Ивницкий В.А. Об условии инвариантности стационарных вероятностей для сетей массового обслуживания//Теор. вероятн. и ее примен. 1982. Т. 27. вып. №1. С. 188- 192.

22. Ивницкий В.А., Шрайберг Я.Л. Аналитическое исследование разомкнутых многоцентровых сетей массового обслуживания с рекуррентным входящим потоком и ограниченными бункерами//АиТ. 1984. №3. С. 87 — 96.

23. Ивницкий В.А. Об условии инвариантности стационарных вероятностей состояний для сетей однолинейных систем массового обслуживания//Теор. вероятн. и ее примен. Т. 34. 1989. С. 576 580.

24. Ивницкий В.А. О стационарных вероятностях состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния//Автоматика и вычисл. техника. 1994. №6. С. 29 — 37.

25. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния//Теор. вероятн. и ее примен. Т. 42. 1997. Вып. 1. С. 179 184.

26. Ивницкий О.В. Об одной многолинейной системе массового обслуживания с многолинейным каналом передачи требований//Труды семинара "Информационные сети и системы". Материалы лекций, докладов и сообщений.— Москва — Суздаль. — 1995. — с. 71 — 75.

27. Ивницкий О.В. Замкнутая сеть массового обслуживания с многолинейным каналом передачи требований//Труды XXX Конференции молодых ученых ИППИ РАН. Москва. - 1995. - с. 10 - 17.

28. Ивницкий О.В. Замкнутая сеть массового обслуживания с многолинейным каналом передачи требований//Проблемы передачи информации. 1996. Т. 32. вып. 3, с. 72 — 81.

29. Ивницкий О.В. Замкнутая сеть массового обслуживания с переменным числом классов требований в узлах//Пробл. передачи информ. 1998. Т. 34. №3. С. 81-95.

30. Ивницкий О.В. Асимптотическое разложение стационарного распределения вероятностей состояний замкнутой сети массового обслуживания с каналом передачи требований//Пробл. передачи информ. 2000. Т. 36. №3. С. 65 — 82.

31. Китаев М.Ю. Системы обслуживания с пуассоновским выходящим потоком//А-иТ. 1980. №11. С. 40-45.

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

33. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение,1979.

34. Климов Г.П. Стохастические системы обслуживания. М.: Наука, 1966.

35. Ковалев Е.А. Сети массового обслуживания с ограниченным временем ожидания в очередях//Автоматика и вычисл. техника. 1985. №2. С. 50 — 55.

36. Ковалев Е.А. О поведении нетерпеливых требований в сетях массового обслуживания с ограниченным временем ожидания в очередях//Автоматика и вы-числ. техника. 1987. №2. С. 88 90.

37. Ковалев Е.А., Малинковский Ю.В. Сети массового обслуживания с резервными приборами//Автоматика и вычисл. техника. 1987. №2. С. 64 — 70.

38. Коваленко И.Н. Об условии независимости стационарных распределений от вида закона распределения времени обслуживания//Проблемы передачи информации. 1962. Т. 11. вып. 2, С. 147-151.

39. Коваленко И.Н. Исследования по анализу надежности сложных систем. Киев: Наукова думка, 1975.

40. Коваленко И.Н. Вероятностный расчет и оптимизация. Киев: Наук, думка, 1989.

41. Коган Я.А., Нерсесян С.Г. Асимптотические методы анализа замкнутых сетей в условиях большой нагрузки//АиТ. 1984. №8. С. 93 — 103.

42. Коган Я.А. Об асимптотике стационарного распределения длин очередей в замкнутых сетях в условиях большой нагрузки//АиТ. 1991. №10. С. 112-120.

43. Малинковский Ю.В. Сети массового обслуживания с симметричными резервными каналами//Изв. АН СССР. Техн. кибернетика. 1986. №4. С. 69 — 77.

44. Малинковский Ю.В. Мультипликативность стационарного распределения состояний для одного класса сетей массового обслуживания//АиТ. 1988. №2. С. 108-119.

45. Малинковский Ю.В. Мультипликативное представление стационарного распределения в замкнутых марковских сетях//Автоматика и вычисл. техника. 1990. №3. С. 34 — 39.

46. Малинковский Ю.В. Критерий точечной независимости состояний узлов в открытой стационарной марковской сети обслуживания с одним классом зая-вок//Теор. вероятн. и ее примен. 1990. Т. 35. вып. №4. С. 779 — 784.

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

48. Малинковский Ю.В. Критерий представимости стационарного распределения состояний открытой марковской сети обслуживания с несколькими классами заявок в форме произведения//АиТ. 1991. №4. С. 75 — 83.

49. Малинковский Ю.В. Ограниченная квазиобратимость и факторизациястационарного распределения замкнутых сетей обслуживания//Автоматика и вы-числ. техника. 1991. №5. С. 49 54.

50. Малинковский Ю.В. Выходные потоки в модифицированных сетях Джек-сона//АиТ. 1992. №9. С. 134- 138.

51. Рыбко А.Н. Стационарные распределения однородных во времени марковских процессов, моделирующих сети связи с коммутацией сообщений//ППИ. 1981. Т. 17. Вып. 1. С. 71-89.

52. Рыбко А.Н. Условия существования стационарного режима для двух типов сетей связи с коммутацией сообщений//ППИ. 1982. Т. 18. Вып. 1. С. 94 — 103.

53. Толмачев А.Л. Некоторые характеристики замкнутых экспоненциальных сетей//Теория телетрафика и информационные сети. ИППИ АН СССР. М.: Наука, 1977, С. 3 6.

54. Толмачев А.Л. Сети обслуживания заявок с регенерирующими траекто-риями//ППИ. 1986. Т. 22. Вып. 2. С. 59 68.

55. Хомичков И.И. Об оптимальном управлении в сети передачи данных со случайным множественным доступом//АиТ. 1991. №8. С. 176 — 188.

56. Хомичков И.И. Исследование моделей локальной сети с протоколом множественного доступа//АиТ. 1993. №12. С. 89 100.

57. Яшков С.Ф. Анализ очередей в ЭВМ. М.: Радио и связь, 1989.

58. Кельберт Б., Сухов Ю.М. Обзор математических вопросов, встречающихся в сетях массового обслуживания//Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М.: ВИНИТИ, 1988. Т. 26.

59. Barbour, A.D. Networks of queues and the method of stages. Adv. Appl. Prob. 8 (1976), 584-594.

60. Bartlett. M.S. Some evolutionary stochastic processes. J. R. Statist. Soc. В 11, 1949, 211 -229.25.

61. Baskett, F. Mathematical models of multi-programmed systems. Ph.D. Diss., Comptr. Ctr. Rep. TSN-17, Comptr. Sci. Dep., U. of Texas at Austin, Austin, Tex., 1970.

62. Baskett, F., Chandy, K.M., Muntz, R.R., and Palacios, F.G. Open, closed and mixed networks of queues with different classes of customers. J. ACM 22, 2 (April 1975), 248 -260.

63. Boucherie, R.J. Product-form in queueing networks. Thesis Publishers Amsterdam. 1992.

64. Bronstein, 0., and Gertsbakh, I. An open exponential queueing network with limited waiting spaces and losses: a method of approximate analysis. Perform. Eval., 4, 1984, 31 -43.

65. Burke, P.J. The output of a queueing system. Operat. Res. 4, 1956, 699 704. 30.

66. Buzen, J. Computational algorithms for closed queueing networks with exponentional servers. Comm. ACM 16, 9 (1973), 527 — 531.

67. Chandy, K.M. The analysis and solutions for general queueing networks. Proc. Sixth Annual Princeton Conf. on Inform. Sci. and Systems, Princeton U., Princeton, N.J., March 1972, 219 -224.

68. Chandy, K.M., Herzog, U., and Woo, L. Parametric analysis of queueing networks. IBM J. Res. and Develop. 19, 1 (Jan. 1975), 36 -42.

69. Chandy, K.M., Herzog, U., and Woo, L. Approximate analysis of general queueing networks. IBM J. Res. and Develop. 19, 1 (Jan. 1975), 43 — 49.

70. Chandy, K.M., Howard, J., Keller, T.W., and Towsley, D.J. Local balance, robustness, Poisson departures and product form in queueing networks. Res. Rep., Compt.r. Sci. Dep., U. of Texas at Austin, Austin, Tex., 1973.

71. Chandy, K.M., Howard. J.H., and Towsley, D.F. Product form and local balance in queueing networks. J. ACM 24, 2 (Apr. 1977), 250 263.16.

72. Chandy, K.M., and Neuse, D. Linearizer: A heuristic algorithm for queueing network models of computer systems. Comm. ACM 25, 2 (1982), 126 134.

73. Chandy, K.M., and Martin, A.J. A characterization of product-form queueing networks. J. ACM 30, 2 (Apr. 1983), 286 299.17.

74. Cox, D.R. A use of complex probabilities in the theory of stochastic processes. Proc. Cambridge Phil. Soc. 51 (1955), 313 — 319.

75. Cox, D.R. The analysis of non-Markov stochastic processes by the inclusion of supplementary variables. Proc. Cambridge Phil. Soc. 51 (1955), 433 — 441.

76. Van Dijk, N.M. On Jackson's product form with "jump-over' blocking. Operat. Res. Lett. 7, 1988, 233 -235.37.

77. Disney, R.L. Random flow in queueing networks: a review and critique. Trans. A HE. 7, No. 3. 1975.

78. Disney, R.L., and Konig, D. Queueing networks: A survey of their randomprocesses. SIAM Rev. 27 (1985), 335 -403.

79. Gelenbe, E., and Pujolle, G. The behaviour of a single queue in a general queueing network. Acta Informatica 7, 2 (1976), 123 — 136.

80. Gelenbe, E., and Pujolle, G. Introduction to Queueing Networks. N.Y.: John Wiley к Sons, 1987.

81. Gelenbe, E., Glynn, P., and Sigman, K. Queues with negative arrivals. J. Appl. Prob. 28 (1991), 245-250.

82. Gelenbe, E. Product-form networks with negative and positive customers. J. Appl. Prob. 28 (1991), 656 663.

83. Gordon, W.J., and Newell, G.F. Closed queueing systems with exponentional servers. Oper. Res. 15, 2 (1967), 252-267.

84. Gordon, W.J., and Newell, G.F. Cyclic queueing systems with restricted queue lengths. Oper. Res. 15, 2 (1967), 268 278.

85. Henderson, W., and Taylor, P.G. Product form in networks of queues with batch arrivals and batch services. Queueing Syst. 6, (1990), 71 —88.

86. Henderson, W., Pearce, C.E.M., Taylor, P.G., and van Dijk, N.M. Closed queueing networks with batch services. Queueing Syst. 6, (1990), 59 — 70.

87. Henderson, W., and Taylor, P.G. Some new results on queueing networks with batch movement. J. Appl Prob. 28, (1991), 409-421.

88. Ivnitskii, V.A. Invariance of stationary probabilities of states for network of multiserver queues. Queueing Syst. 19, 1995, 319-329.

89. Jackson, J.R. Networks of waiting lines. Operat. Res. 5, 1957, 518 —521.21.

90. Jackson, J.R. Job-shop like queueing systems. Manag. Sci. 10 (1963), 131 142.

91. Jackson, R.R.P. Queueing systems with phase-type service. Operat. Res. Q.5, 1954, 109- 120.22.

92. Jackson, R.R.P. Random queueing processes with phase-type service. J. R. Statist. Soc. В 18, 1956, 129 132.(23.

93. Kelly, F.P. Markov processes and Markov random fields. Bull. Inst. Int. Statist. 46, 1975, 397-404.(36.

94. Kelly, F.P. Networks of queues with customers of different types. J. Appl. Prob. 12, 1975, 542-554.(32.

95. Kelly, F.P. Networks of queues. Adv. Appl. Prob. 8, 1976, 416-432.(33.

96. Kelly, F.P. Reversibility and stochastic networks. Wiley, 1979.(34.

97. Kingman, J.F.C. Markov population processes. J. Appl. Prob. 6, 1969, 1-18.(31.

98. Kleinrock, L. Communication nets. McGraw-Hill, New York, 1964.(26.

99. Kobayashi, H. System design and performance analysis using analytic models. In: Current Trends in Programming Methodology, III. Software Modeling, K.M. Chandy, and R.T. Yeh, Eds., Prentice Hall, Englewood Cliffs, N.J., 1978, 72- 114.(18.

100. Koenigsberg, E. Cyclic queues. Operat. Res. Q. 9, 1958, 22-35.(24.

101. Krzesinski, A.E. Multiclass queueing networks with state-dependent routing. IBM Res. Rept. RC-9761. Yorktown Heights, N.J., December 1982.

102. Krzesinski, A.E., and Teunissen, P. An approximate solution method for multiclass queueing networks with adaptive routing. Rept. ITR 85-04-00. Inst, for Applied Computer Science Univ. of Stellenbosch, South Africa, 1985.

103. Krzesinski, A.E. Multiclass queueing networks with state-dependent routing. Perform. Eval. 7, 1987, 125 143.

104. Labetoulle, J., Manning, E.G., and Peebles, R.W. Analysis and simulation of a homogeneous computer network. Res. Rep., Dep. Comptr. Sci., U. of Waterloo, Waterloo, Ont., Canada.

105. Lemoine, A.I. Networks of queues — a survey of equilibrium analysis. Manag. Sci. 24, 1977, No. 4.

106. Martin, A.J. Queueing network models with product form: Characterization and computation. Ph.D. Diss., Comptr. Sci. Dep., U. of Texas at Austin, Austin, Tex., 1980.

107. Muntz, R.R. Poisson departure processes and queueing networks. IBM Res. Rep. RC-4145, IBM Thomas J. Watson Research Center, Yorktown Heights, N.J.,1972.13.

108. Noetzel, A.S. A generalized queueing discipline for product-form network solutions. J. A CM 26, 4 (Oct. 1979), 779 -793.20.

109. Pittel, B. Closed exponentional networks of queues with blocking: the Jackson-type stationary distribution and its asymptotic analysis. IBM Res. Rep. RC 6176. IBM Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y., Aug. 1976.

110. Pittel, B. Closed exponentional networks of queues with saturation: the Jackson-type stationary distribution and its asymptotic analysis. Math. Operat. Res. 4, 1979, 357 378.35.

111. Regis, R.C. Multiserver queueing models of multiprocessing systems. IEEE Trans. Computers C-22, 8 (1973), 736-745.

112. Reiser, M., and Kobayashi, H. Queueing networks with several closed subchains: Theory and computational algorithms. IBM J. Res. and Develop. 19, 3 (May 1975), 283 -294.

113. Reiser, M., and Kobayashi, H. Horner's rule for the evaluation of general closed queueing networks. Comm. ACM. 18, 10 (October 1975), 5.92 -593.

114. Reiser, M., and Lavenberg, S.S. Mean value analysis of closed multichain queueing networks. J. ACM. 27, (1980), 313-322.

115. Reiser, M. Mean value analysis and convolution methods for queue dependent servers in closed queueing networks. Perform. Eval. 1, 1 (1981), 7 — 18.

116. Serfozo, R.F. Markovian network processes: congestion-dependent routing and processing. Queueing Syst. 5, (1989), 5 — 36.

117. Serfozo, R.F. Queueing networks with dependent nodes and concurrent movements. Queueing Syst. 13, (1993), 143 — 182.

118. Serfozo, R.F. Introduction to Stochastic Networks. (Springer, 1999).

119. Serfozo, R.F. Introduction to Stochastic Networks. (Springer, 1999).

120. Taylor, J., and Jackson, R.R.P. An application of the birth and death process to the provision of spare machines. Operat. Res. Q. 5, 1954, 95 — 108.29.

121. Towsly, D.F. Local balance models of computer systems. Tech. Rep. TR-60. Dept. of Comptr. Sci. U. of Texas, Austin, Texas. 1975.

122. Towsly. D.F. Queueing network models with state-dependent routing. J. ACM. 27, No. 2, April 1980, 323 337.

123. Whittle, P. Nonlinear migration processes. In: Proc. of the 36th Session of the Internat. Statistical Inst., 1967, 642 647.27.

124. Whittle, P. Equilibrium distributions for an open migration processes. J. Appl. Prob. 5, 1968, 567-571.28.

125. Whittle, P. Systems in stochastic equilibrium. (Wiley, 1986).