Анализ систем массового обслуживания с марковским потоком и марковским обслуживанием в дискретном времени тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Вискова, Елена Валерьевна

• Вискова, Елена Валерьевна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Вискова, Елена Валерьевна

ВВЕДЕНИЕ

ГЛАВА 1. ОДНОЛИНЕЙНАЯ СИСТЕМА КОНЕЧНОЙ

ЕМКОСТИ С МАРКОВСКИМ ПОТОКОМ И

МАРКОВСКИМ ОБСЛУЖИВАНИЕМ В ДИСКРЕТНОМ ВРЕМЕНИ

§ 1. Марковский поток заявок и марковское обслуживание в дискретном времени

§ 2. Описание системы

§3. Система уравнений равновесия

§ 4. Матрично-рекуррентное решение системы уравнений 31 равновесия

§5. Связь с непрерывным временем

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

§ 7. Стационарное распределение времени ожидания

§ 8. Численный анализ

ВЫВОДЫ

ГЛАВА 2. ОДНОЛИНЕЙНАЯ СИСТЕМА КОНЕЧНОЙ 51 ЕМКОСТИ С МАРКОВСКИМ ПОТОКОМ И МАРКОВСКИМ ОБСЛУЖИВАНИЕ)!И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ В ДИСКРЕТНОМ ВРЕМЕНИ

§ 1. Описание системы

§2. Система уравнений равновесия

§ 3. Алгоритм решения системы уравнений равновесия

§ 4. Стационарные вероятности потери заявок

§ 5. Численный анализ

ВЫВОДЫ

ГЛАВА 3. ДВУХФАЗНАЯ СИСТЕМА КОНЕЧНОЙ 72 ЕМКОСТИ С МАРКОВСКИМ ПОТОКОМ И МАРКОВСКИМ ОБСЛУЖИВАНИЕМ В ДИСКРЕТНОМ ВРЕМЕНИ

§ 1. Описание системы

§2. Система уравнений равновесия

§ 3. Алгоритм решения системы уравнений равновесия

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

§5. Стационарные вероятности потери заявок

§ б. Численный анализ

ВЫВОДЫ

• ГЛАВА 4. МАРКОВСКАЯ ДВУХФАЗНАЯ СИСТЕМА

КОНЕЧНОЙ ЕМКОСТИ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ В ДИСКРЕТНОМ ВРЕМЕНИ

§ 1. Описание системы

§2. Система уравнений равновесия

§ 3. Алгоритм решения системы уравнений равновесия

§ 4. Стационарные вероятности потери заявок

ВЫВОДЫ

Введение диссертации (часть автореферата) на тему «Анализ систем массового обслуживания с марковским потоком и марковским обслуживанием в дискретном времени»

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

Проектирование, управление и расчет этой тончайшей инфокоммуникационной системы представляют собой интереснейшие задачи для математиков, инженеров и экономистов всего мира. Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории массового обслуживания (ТМО). Возможности применения систем массового обслуживания (СМО) в качестве моделей сетевых систем и их компонентов отражены, например, в [1, 4-6, 22, 24, 26, 27, 30, 34-36]. В связи с этим большое внимание в литературе уделяется собственно анализу СМО (см., например, [1, 7, 16, 23, 28, 29]).

В качестве стандартных моделей в ТМО принято рассматривать системы, функционирующие в непрерывном времени [16, 23, 29]. Тем не менее, дискретные модели также находят широкое применение, примерами здесь служат хорошо известные методы исследования непрерывных СМ О с помощью построения дискретных цепей Маркова по моментам поступления или ухода заявок из системы [10, 44, 70, 71], а также методы аппроксимации непрерывных систем дискретными посредством квантизации времени [2, 3, 12, 71].

Кроме указанных классических примеров использования дискретных моделей существуют и другие приложения аппарата дискретных СМО для анализа производительности реальных систем. В качестве примера, можно привести хорошо известны вычислительные системы с разделением времени (time-sharing), обладающие врожденной дискретной природой — временем, разделенным на слоты. Появление и развитие таких систем относится к середине 60-х годов, в это время и появляются первые исследования в области СМО с дискретным временем, см., например, работы [72, 73]. В этих работах шаг дискретизации временной шкалы соответствует размеру временного слота, который выделен для осуществления процессором определенного количества работы — алгоритм кругового обслуживания (round-robin algorithm). Следует отметить, что, несмотря на то, что технических сложностей, возникающих при работе с дискретными СМО, значительно больше, чем при работе со СМО в непрерывным временем, сам математический аппарат является более элементарным по сравнению с непрерывным временем. Под техническими трудностями понимаются комбинаторные сложности, возникающие при выводе системы уравнений равновесия, что связано с возможностью осуществления большого количества событий за один временной слот, в отличие от непрерывного времени, когда за такт может произойти всего одно событие, приводящее к изменению состояния рассматриваемой СМО.

Впервые эти особенности были рассмотрены в работах Клейнрока [72, 73]. Из-за сложностей работы с дискретным временем для оценки характеристик производительности систем, обладающих дискретной природой, были разработаны методы приближенного анализа с помощью непрерывных СМО, например, системы с разделением времени можно аппроксимировать моделями с разделением процессора (processor sharing), как это было впервые предложено в работе [93] и расширено в работе [71, гл. 4].

Из-за сложности работы с системами в дискретном времени публикаций в этой области значительно меньше по сравнению с их количеством в области непрерывных СМО. Однако, начиная с середины 60-х годов, теория дискретных систем массового обслуживания постепенно развивалась, в 1983 году вышло несколько монографий Хюнтера [67, 68], в которых рассматривались в основном однолинейные СМО неограниченной емкости. Также следует отметить появление в это время базового курса лекций по дискретным СМО у Кобаяши [74], в котором рассматривались их приложения к анализу систем временного мультиплексирования. Постепенно развивалась теория для дискретных многофазных СМО и сетей массового обслуживания (СеМО) с дискретными узлами неограниченной емкости, однако к концу 80-х годов количество работ в этой области очень незначительно [60 ,66, 84, 94, 100].

Новый всплеск исследований в области дискретных СМО связан с развитием сетей на базе технологии асинхронного режима передачи (Asynchronous Transfer Mode, ATM) и приходится на середину 90-х годов [см., например, 53, 69, 87, 88, 92, 101]. Характерной особенностью сетей ATM является фиксированный размер ячейки, в которой передается информация различного типа. Например, коммутаторы ATM, как правило, моделируются с помощью дискретных СМО, поскольку их синхронизация осуществляется посредством мельчайших временных квантов. В 90-е годы выходят несколько монографий [53, 95, 99] и большое число статей, посвященных исключительно моделям в дискретном времени, наиболее известные среди которых публикации [51, 52, 58, 59, 62-65, 77, 83, 89]. В работах [53, 95, 99] сделан исчерпывающий обзор литературы по моделям в дискретном времени, детально рассмотрены всевозможные дискретные СМО неограниченной емкости с потоками и обслуживанием различных типов (детерминированный, геометрический, фазовый и др.).

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

Впервые понятие марковского потока было введено Ныотсом в 1979 году [79], а затем во время нового всплеска исследований, связанных с потоками фазового типа, уточнено Лукантони [75, 76]. С тех пор в литературе по теории очередей большое внимание уделяется собственно анализу СМО с марковским потоком [8, 9, 16, 37, 47, 57]. Как известно, марковский поток заявок устроен более сложно, чем поток фазового типа, и в определенном смысле является его обобщением [15, 57]. Поток фазового типа в свою очередь характеризуется некоторым РН-распределением, включающем в себя, как частные случаи, экспоненциальное, эрланговское, гиперэкспоненциальное и другие распределения. Имеются два основных фактора, объединяющих поток фазового типа и марковский поток: первый — это свойство марковости процессов, управляющих генерацией заявок; второй — оба потока являются фазового типа, т.е. и марковский поток устроен так, что процесс генерации заявок представляется как случайное блуждание по конечному множеству фаз, длительность прохождения которых имеет экспоненциальное распределение. Однако между этими потоками есть существенное различие: марковский поток не является рекуррентным. Именно последнее свойство марковского потока объясняет его широкое использование для моделирования реальных телекоммуникационных систем с очередями [40, 41, 42, 53, 54, 69, 85, 87, 88, 92, 101].

Для получения стационарного распределения очереди для СМО с марковским входящим потоком, а также для СМО с распределением времени обслуживания фазового типа в работах Бочарова и Печинкина [15, 17, 18] было предложено использовать алгоритмический метод, основанный на использованном в [16, 31] методе последовательного исключения состояний вложенной цепи Маркова. Впервые алгоритмические методы анализа СМО были разработаны Ныотсом [80-82] и использовались для анализа системы G/РН/ 1/оо. Развитию алгоритмических методов анализа СМО посвящены также публикации [46, 55, 56, 78, 86, 98].

Появление понятия дискретного марковского потока в начале 90-х было обусловлено необходимостью решения ряда конкретных практических задач. Впервые системы с дискретным марковским потоком исследуются в работах Блоидия [42, 43], в которых DMAP применяется для моделирования ATM трафика, а с помощью системы конечной емкости с групповым марковским потоком и рекуррентным обслуживанием в дискретном времени анализируются характеристики производительности сетевых коммутационных устройств. В [92] дискретный марковский поток применяется для анализа производительности процесса мультиплексирования на уровне адаптации ATM. Дальнейшим развитием исследований систем с входящим марковским потоком заявок стало изучение СМО с различными распределениями времени обслуживания и дисциплинами обслуживания, а также с учетом повторных заявок. Этой тематике был посвящен ряд работ [19, 38, 39, 61, 87, 96, 97]. В работах [90, 91] с помощью методов имитационного моделирования исследуется устойчивость параметрических оценок марковского потока.

Цикл работ [11-14, 20, 21, 32, 33, 45, 48, 49], опубликованных в последние годы, связан с исследованием систем не только с марковским потоком, но и с марковским обслуживанием.

По аналогии с марковским потоком естественно рассмотреть модель обслуживания заявок в виде некоторого марковского процесса, допускающего разбиение обслуживания . на фазы с экспоненциальным распределением, при этом длительности обслуживания заявок могут быть зависимы между собой. Впервые марковское обслуживание было формально определено в работе [10], а понятие марковского обслуживания в дискретном времени введено в работе [12].

Достаточно полный обзор публикаций по системам с марковским потоком заявок в дискретном времени содержит обзор [57], там же рассмотрены новые направления в их развитии.

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

IP (Internet Protocol) поверх WDM (Wavelength Division Multiplexing)).

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

Появление понятия дискретного марковского потока в начале 90-х было обусловлено необходимостью решения ряда конкретных практических задач. С помощью дискретного марковского потока и его частных случаев (поток Бернулли; поток Бернулли, управляемый цепью Маркова; дискретный поток фазового типа) достаточно хорошо моделируются процессы поступления единиц информации фиксированной длины в системах и сетях связи, по отношению к которым применяются различные механизмы мультиплексирования, как например в сетях ATM.

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

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

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

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

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

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

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

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

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

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

Апробация работы. Материалы диссертации докладывались на международных конференциях: "Современные математические методы анализа и оптимизации телекоммуникационных сетей" (Беларусь, Минск, 2005 г.); Fifth Workshop on Simulation (Russia, St. Petersburg, 2005 г.); 17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation (France, Paris, 2005 г.); XXIV International Seminar on Stability Problems for Stochastic Models (Latvia, Jurmala, 2004 г.); на XL и XLI Всероссийских научных конференциях по проблемам математики, информатики, физики и химии (Москва, РУДН, 2004, 2005 гг.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН.

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

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

Заключение диссертации по теме «Теоретические основы информатики», Вискова, Елена Валерьевна

Выводы

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

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

2. Разработан матричный алгоритм решения СУР.

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

4. Найдены выражения для вероятности потери из-за переполнения буферного накопителя, а также вероятности потери в результате поступления отрицательных заявок.

ЗАКЛЮЧЕНИЕ

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

1. Формализовано понятие дискретного марковского потока и введено понятие дискретного марковского обслуживания.

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

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

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

5. Разработан программный комплекс для расчета стационарных характеристик на основе алгоритмов, полученных для вышеуказанных СМО; проведен численный анализ полученных характеристик производительности.

Список литературы диссертационного исследования кандидат физико-математических наук Вискова, Елена Валерьевна, 2005 год

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

2. Башарип Г.П., Ефимушкин В.А. Исследование однолинейной системы с заявками нескольких типов в дискретном времени // Пробл. передачи информ. 1984. Т. XX. Вып. 1. С. 95-104.

3. Башарип Г.П., Куренков Б.Е. Исследование одной СМО с дискретным временем // Изв. АН СССР. Техническая кибернетика, 1983. Ш. С.26-30.

4. Башарип Г.П., Самуйлов К.Е. Современный этап в развитии теории телетрафика // Вычислительная математика. 2001. Т. 1. № 1.

5. Башарин Г.П., Харкевич А.ДЧ-■ Шпепс ' М.А. Массовое обслуживание в телефонии. М.: Наука, 1968.

6. Боровков А.А. Вероятностные процессы в теории массового обслуживания. М.: Наука, 1972.

7. Бочаров П.П. Анализ системы массового обслуживания MAP/G/1/r конечной емкости // Вестник. РУДН. Сер. "Прикладная математика и информатика". 1995. № 1. С. 52-67.

8. Бочаров П. П. Анализ конечной очереди с марковским входящим потоком, зависящим от состояния системы, ипроизвольным обслуживанием. // Автоматика и телемеханика. 1995. № 12. С. 60-70.

9. Бочаров П.П. Стационарное распределение конечной очереди с рекуррентным потоком и марковским обслуживанием // Автоматика и телемеханика. 1996. № 9. С. 66-78.

10. Бочаров П.П., Вискова Е.В. Система массового обслуживания DMAP/DMSP/1/R в дискретном времени // Тезисы докладов XL Всероссийской научной конф. по проблемам математики, информатики, физики и химии, 19-23 апреля 2004 г. М.: Изд-во РУДН, 2004. С. 57-58.

11. Бочаров П.П., Вискова Е.В. Однолинейная система массового обслуживания конечной емкости с марковскими потоком и обслуживанием в дискретном времени // Автоматика и телемеханика. 2005. № 2. С. 73-91.

12. Бочаров П.П., Вискова Е.Б., Надаев Э.А. Марковская система конечной емкости с отрицательными заявками в дискретном времени // Вестник РУДН, сер. "Прикл. мат. и информатика". 2005. № 1. С. 61-75.

13. Бочаров П.П., Литвин В.Г. Методы анализа при расчетах систем массового обслуживания с распределениями фазового типа // Автоматика и телемеханика. 1986. № 5. С. 5-23.

14. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: Изд-во РУДН, 1995.

15. Бочаров П.П., Печинкин А.В., Д'Апиче Ч., Фонг Н.Х. Однолинейная система массового обслуживания конечной емкости с групповым марковским потоком pi полумарковским обслуживанием // Вестник РУДН, сер. "Прикл. мат. и информатика". 2001. № 1. С. 64-79.

16. Бочаров П.П., Печинкин А.В., ДАпиче Ч., Салерно С. Стационарные характеристики системы массового обслуживания G/MSP/1/r // Автоматика и телемеханика. 2003. № 2. С. 127-142.

17. Бочаров П.П., Шлумпер Л.О. Однолинейная система массового обслуживания с фоновыми заявками // Автоматика и телемеханика. 2005. № 6. С. 74-88.

18. Вискова Е.В. Двухфазная система массового обслуживания с марковскими потоком и обслуживанием в дискретном времени // Информационные процессы. 2005. Т. 5. № 3. С. 247-257.

19. Вискова Е.В., Матюшенко С.П., Двухфазная марковская . система-с потерями в дискретном времени /•/ Тезисы докладов

20. XLI Всероссийской научной конф. по проблемам математики, информатики, физики и химии, 19-22 апреля 2005 г. М.: Изд-во РУДН, 2005. С. 91-92.

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

22. Гнеденко Б.В., Коваленко И.П. Введение в теорию массового обслуживания. М.: Наука, ГРФМЛ, 2 изд., 1987.

23. Ершов В.А., Кузнецов Н.А. Теоретические основы построенияцифровой сети с интеграцией служб (ISDN). М.: Институт проблем передачи информации РАН, 1995.

24. Ефимуштн В.А. Анализ системы конечной емкости с обслуживанием общего вида и неоднородными заявками в дискретном времени //В кн.: Модели информационных сетей М.: Наука, 1984. С. 76-83.

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

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

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

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

29. Лагутин B.C., Степанов С.Н. Телетрафик в мультисервисных сетей связи. М.: Радио и связь, 2000.

30. Печинкии А.В. Стационарные вероятности состояний системы с входящим потоком марковского типа, относительным приоритетом и раздельными очередями // Автоматика и телемеханика. 1998. № 1. С. 107-119.

31. Печинкии А.В., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. № 9. С. 85-100.

32. Печинкин А.В., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания G/MSP/n/r // Вестник РУДН, сер. "Прикл. мат. и информатика". 2003. С. 119-143.

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

34. Шварц М. Сети ЭВМ. Анализ и проектирование. М.: Радио и связь, 1981.

35. Шпепс-Шнеппе М.А. Системы распределения информации. Методы расчета. М.: Связь, 1979.

36. Alfa A.S., Dolhun K.L., Chakravarthy S. A discrete queue with Markovian arrival process and phase type group services // Journal of Applied Mathemetics and Stochastic Analysis. 1995. № 8. P. 151-176.

37. Alfa A.S., Frigui I. Discrete NT-policy single server queue with Markovian arrival process and phase type service // European Journal of Operational Research. 1996. № 88. P. 599 613.

38. Andersen А.Т., Jensen A., Nielsen B.F. Modelling and performance study of packet-traffic with self-similar characteristics over several lime-scales with Markovian arrival processes // VTT Sim-posium. 1995. P. 256-269.

39. Andersen А. Т., Nielsen B.F. Application of superpositions of two state Markovian sources to modelling of self-similar behaviour // Proc. of IEEE INFOCOM, 1. 1997. P. 196-204.

40. Blondia C. Performance evaluation of an M/l-stage in an ATM switching element // Performance evaluation. 1992. V. 15. P. 1-20.

41. Blondia С. A discrete-time batch Markovian arrival process as B-ISDN traffic model // Belgian J. of Oper. Res., Statist. Comput. Sc. 1993. V. 32 (3,4). P. 3-23.

42. Bocharov P.P., D'Apice C, Pechinkin A.V., Salerno S. Queueing theory. Ultrecht Boston: VSP, 2004.

43. Bocharov P.P., Naumov V.A. Matrix-geometric stationary distribution for the PH/PH/l/r queue // Elektron. Informationsverarb. Kyb. 1986. V.22.-№4. P.179-186.

44. Bocharov P.P., Viskova E.V. The DMAP/DMSP/l/r queueing system in discrete time // Trans, of XXIV Int. Seminar on Stability Problems for Stochastic Models. Jurmala. Latvia. 2004. P. 103-108.

45. Bocharov P.P., Viskova E.V., Lyubin D.Yu. The two-stage queueing system with negative arrivals in discrete time // Proc. of 5th St. Petersburg Workshop on Simulation. St. Petersburg, Russia. 2005. P. 155-161.

46. Boxma O.J., Resing J.A.C. Tandem queues with determenistic service times // Operations Research. 1994. № 49. P. 221 239.

47. Briem U., Theimer Т.Н., Kroner H. A General Discrete-Time Queueing Model: Analysis and Applications // Proc. of 13th Int. Teletraffic Congress, Copenhagen, 1991. P. 13-19.

48. Bruneel H. Performance of Discrete Time Queueing Systems // Computers and Operations Research. 1993. V. 20. P. 303 320.

49. Bruneel H., Kim G. Discrete-Time Models for Communication System including ATM. Kluwer Academic Publications, Boston, 1993.

50. Bruneel H., Steyaert B. Cell delay and queue length haracteristics in ATM buffers with multiple output lines //Proc. of IEEE ATM Workshop. 1997. P. 611-620.

51. Chakravarthy S.R., Alfa A.S. Matrix-analytic Methods in Stochastic Models. Marcel Dekker, 1996.

52. Chakravarthy S.R., Alfa A.S. Advances in Matrix-analytic Methods in Stochastic Models. Notable Publications, 1998.

53. Chakravarthy S.R. The batch Markovian arrival process: A review and future work // Advances in Probability Theory and Stochastic Processes. Eds., A. Krisnamoorthy et al., Notable Publications Inc., 2000. P. 21-39.

54. Daduna H. The cycle time distribution in a cycle of Bernoulli servers in discrete time // Mathematical Methods in Operations Research. 1996. № 44, P. 295-332.

55. Daduna H. Discrete Time Queueing Networks: Recent Development // Tutorial Lecture Notes in Performance'96. Lausanne. 1996. P. 163-204.

56. Daduna H., Schassberger. R. Networks of queues in discrete time // Zeitschrift fuer Operation Research. 1983. № 27. P. 159-175.

57. Frigui I., Alfa A.S., Xu X.I. Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1 // Naval Research Logistics. 1997. № 44. P. 559-576.

58. Gravey A., Hebuterne C. Simultaneity in discrete-time single server queues with Bernoulli inpets // Performance Evaluation. 1992. № 14. P. 123-131.

59. Harnpanichpun NPujolle G. Product-form discrete-time queues in series with batch transition: late arrival case // Performance Evaluation. 1995. № 21. P. 261-269.

60. Henderson W., Pearce C.E.M., Taylor P.G., Dijk N.M. Insensi-tivity in discrete-time generalized semi-Markov processes allowing multiple events and probabilistic service scheduling // Annals of Applied Probability. 1995. № 5. P. 71-88.

61. Henderson W., Taylor P. G. Discrete-time queueing networks with geometric release probabilities // Advances of Applied Probability. 1992. № 24. P. 229-233.

62. Hsu J., Burke P.J. Behaviour of tandem buffers with geometric input and markovian output. IEEE Transaction on Communications. 1976. № 24. P. 358-361.

63. Hunter J.J. Mathematical Techniques of Applied Probability, volume I: Discrete Time Models: Basic Theory. Academic Press, New York, 1983.

64. Hunter J.J. Mathematical Techniques of Applied Probability, volume II: Discrete Time Models: Thechniques and Applications. Academic Press, New York, 1983.

65. Rang K., Kim C. Performance analysis of statistical multiplexing of heterogenous discrete-time Markovian arrival processes. Computer Communication. 1997. № 20. P. 970-978.

66. Kleinrock. L. Queueing Theory, volume I. John Wiley and Sons, New York, 1975.

67. Kleinrock. L. Queueing Theory, volume II. John Wiley and Sons, New York, 1976.

68. Kleinrock. L. Analysis of time-shared processor // Naval Research Logistics Quarterly. 1964. V. 2. № 10. P. 59-73.

69. Kleinrock. L. Time-shared processor. A theoretical treatment // Journal of Association of Computing Machinery. 1967. V. 2. № 14. P. 242-261,

70. Kobayashi H. Stochastic modelling: Queueing Networks //In G.Louchard and G. Latouche, editors, Probability Theory and Computer Science, International Lecture Series in Computer Science, Part II. Academic Press, London, Orlando, 1983. P. 53-121.

71. Lucantoni D. New results for the single server queue with a batch Markovian arrival process // Stochastic Models. 1991. V. 7. P. 1-46.

72. Lucantoni D.M., Meier-Hellstern K.S., Neuts M.F. A single server queue with server vacations and a class of non-renewal processes // Adv. Appl. Probab. 1990. V. 23. № 2. P. 676-705.

73. Miyazawa M., Takagi H. Advances in discrete time queues (Special issue) // Queueing System and Their Applications. 1994. № 18.

74. Neuts M.F. A versatile Markovian arrival process // Journal of Appl. Prob. 1979. V. 16. P. 764-779.

75. Neuts M.F. Matrix-geometric solutions in stochastic models. An algorithmic approach. Baltimore and London: The Johns Hopkins Univ. Press, 1981.

76. Neuts M.F. Matrix-analytic Methods in queueing theory // European Journal Oper. Res. 1984. K°- 15. P. 2-12.

77. Neuts M.F. Structured Stochastic Matrices of M/G/l type and their applications. Marcel Dekker, 1989.

78. Pestien V., Ramakrishnan S. Futures of some discrete-time cycle queueing models // Annals of Applied Probability. 1994. № 4. P. 591-606.

79. Pujolle G., Claude G.P., Seret D. A discrete queueing system with a product form solution // Proceedings of IFIP WG 7.3 International Seminar on Computer Networking and Performance Evaluation. Amsterdam. 1986. P. 139-147.

80. Rananand N. Approximating a variable bit rate source by Markov processes. IEEE Global telecommunication Conference. 1994. № 2. P. 1107-1112.

81. Ramaswami V. Matrix analytic methods: A tutorial overview with some extensions and new results //In Matrix-analytic Methods in Stochastic Models, Eds., S.R. Chakravarthy and A.S. Alfa. Marcel Dekker, 1996. P. 261-296.

82. Ramaswami V., Wang J.L. Discrete time queueing analysis of ATM systems with phase-type distributed talk spurts traffic sources // IEEE Global Telecommun. Conf. 1996. № 1. P. 623-628.

83. Ramaswami V., Wang J.L. Discrete time queueing analysis of ATM systems with heterogenous traffic sources. IEEE Global Telecommun. Conf. 1996. № 2. P. 1093-1098.

84. Rubin I., Tsai Z.-H. Message delay analysis of multiclass priority TDM A, FDMA, and discrete-time queueing systems // IEEE Trans. Inform. Theory. 1989. V. 35. P. 637-647.

85. Rykov V., Dimitrov B. On parameter estimation of MAP via simulation method / / Proc. of Fifth Workshop on Simulation. St. Petersburg, St. Petersburg University, 2005. P. 583-590.

86. Rykov V., Efrosinin D. On stability of parameters estimation of MAP // Proc. of XXV International Seminar on Stability Problems for Stochastic Models. Salerno, Italy, September 20-24, 2005. P. 242-249.

87. Saito H. Performance Evaluation and dimensioning for AAL2 GLAD // Proc. of IEEE INFOCOM. 1999. № 1. P. 153-160.

88. Sakata M., Noguchi S.; Oizumi J. An analysis of the M/G/l queue under rounde-robin scheduling. Operation Research. 1971. № 19. P. 371-375.

89. Schassberger R., Daduna H. A discrete-time technique for solving closed queueing network models of computer systems // Messung, Modellierung and Bewertung von Rechensystemen, Berlin 1983. P. 122-134,

90. Takagi H. Queueing Analasis: A Foundation of Performance Analysis, volum 3. Discrete-Time Systems. North-Holland, New York, 1993.

91. Van Houdt В., Blondia C. The delay distribution of a type к customer in a first come first served DMAPK./PH[K]/1 queue // Journal of Appl. Probab. 2002. V. 1. № 39. P. 213-222.

92. Van Houdt В., Lenin R.B., Blondia C. Delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue withage dependent service times // Queueing systems. 2003. № 45. P. 59-73.

93. Walraevens J., Fiems D., Bruneel H. Transient Analysis of A Discrete-Time Priority Queue // Proc. of the 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications. Riga, Latvia. 2005. P. 05-18.

94. Woodward M.E. Communication and Computer Networks: Modelling with Discrete-Time Queues. IEEE Computer Society Press, Loc Alamitos, CA, 1994.

95. Walrand J. A discrete-time queueing network // Journal of Applied Probability. 1983. № 20. P. 903-909.

96. Wang S.S., Silvester J.A. Discrete-time performance model for integrated service ATM multiplexers // Proc. of IEEE Global Telecommunications Conference. 1993. V. 2. P. 757-761.