Введение к работе
Актуальность темы диссертации.
Интенсивное развитие теории СеМО стимулируется расширением области применения данного раздела теории массового обслуживания. Стремительное развитие информатики и вычислительной техники требует разработки теоретических основ для исследования таких объектов, как сети ЭВМ, сети передачи данных, коммуникационные сети, локальные сети и т.д. Теория сетей массового обслуживания (СеМО) предоставляет удобный язык для адекватного описания функционирования больших систем, поскольку в терминах этой теории можно формализовать достаточно сложные модели.
Существенный вклад в развитие теории СеМО внесли В.В.Аниси-мов, Г.П.Башарин, А.А.Боровков, П.П.Бочаров, Е.Геленбе, Дж.Джек-сон, В.А.Ивницкий, Ф.П.Келли, М.Я.Кельберт, Д.Кениг, Л.Клейнрок, Ю.В.Малинковский, Г.А.Медведев, Б.Меламед, Р.Мюнтц, Ю.М.Сухов, П.Тейлор, А.Л.Толмачев, Д.Тоусли, Дж.Уолренд, Г.И.Фалин, Дж.Ховард, К.Ченди, Р.Шасбергер, С.Ф.Яшков и др.
При исследовании СеМО наибольший интерес представляет изучение стационарного функционирования сетей, поскольку большую часть времени изучаемый объект проводит в установившемся режиме. Большинство работ по данному вопросу связано с возможностью представления стационарного распределения сети в виде произведения множителей, характеризующих стационарное распределение узлов сети, поскольку в настоящее время в противном случае сети не поддаются аналитическому исследованию. Классическими в этом смысле считаются результаты, полученные Джексоном, Гордоном и Ньюэллом. Дальнейшим обобщением таких моделей явились сети Келли, ВСМР-ест. Келли было установлено, что узлы, из которых состоит мультипликативная сеть, обладают свойством, которое он назвал квазиобратимостью, основанное на возможности представления процессов поступления и ухода функционалами от траекторий марковской цепи, описывающей состояние узла. В том или ином виде это понятие появлялось в работах многих авторов. Наиболее полно в своих работах понятие квазиобратимости использовал и оценил его значимость Уолренд. Нетрадиционный подход, позволяющий марковской цепи переходы из состояния в это же самое состояние, позволил перенести понятие квазиобратимости на модели, которые не являются
"заявко-сохраняющими".
Во многих практических ситуациях в отдельных узлах сети могут возникать проблемы, связанные с перегрузками. В связи с этим возникает необходимость уменьшать нагрузки на такие узлы. Одним из способов решения этой проблемы является введение обходов узлов заявками. Ю.В.Малинковским были рассмотрены модифицированные сети Джексона, в которых вероятность обхода узла зависела от его состояния, описанного числом заявок в узле. Для таких сетей были получены условия мультипликативности стационарного распределения, исследованы выходящие из сети потоки заявок.
При изучении стационарного распределения большой интерес представляет инвариантность (или нечувствительность) стационарного распределения по отношению к функциональной форме распределений длительностей обслуживания в узлах. Это связано с тем, что в реальных сетях распределения продолжительностей обслуживания часто отличаются от показательного. Доказательство инвариантности стационарного распределения позволяет при проектировании реальных сетей предполагать, что обслуживание в узлах имеет показательное распределение, наиболее удобное для моделирования.
В связи с этим весьма актуальным представляется исследование стационарного распределения более общей модели сети с обходами, в которой изолированный от сети узел описывается цепью Маркова с непрерывным временем, на предмет мультипликативности стационарного распределения и его инвариантности по отношению к распределениям продолжительностей обслуживания в узлах сети.
Связь работы с крупными научными программами, темами.
Полученные в работе результаты использовались при работе над госбюджетной НИР ГБЦМ 95-13 "Стационарное функционирование сетей массового обслуживания", № госрегистрации 1996756, выполненной по плану Министерства образования РБ в 1995-1997 гг. и госбюджетной НИР ГБЦМ 98-01 "Теоретические и прикладные вопросы теории меры и теории вероятностей", № госрегистрации 1998648, выполненной по плану Министерства образования и науки РБ в 1998-1999 гг.
Цель и задачи исследования.
Основной целью работы является разработка методов исследования стационарного распределения сетей массового обслуживания с обходами узлов заявками, установление условий представимости стацис-
нарного распределения а виде произведения, определение условий инвариантности стационарных вероятностей исследуемых сетей относительно распределений длительностей обслуживания в узлах, а также характера выходящих из открытой сети потоков заявок.
Для достижения поставленной цели решаются следующие задачи:
а) рассматриваются открытые и замкнутые сети массового обслу
живания с обходами узлов заявками с экспоненциальным обслужива
нием в узлах, в случае открытой сети входной поток — простейший,
изолированный от сети узел описывается регулярной эргодической це
пью Маркова с непрерывным временем, а вероятность обхода заявкой
узла зависит от его состояния;
б) для построенных моделей находятся достаточные условия муль
типликативности стационарного распределения, для открытой сети с
обходами доказывается пуассоновость потоков заявок, выходящих из
сети;
в) доказывается инвариантность стационарного распределения от
крытых и замкнутых сетей массового обслуживания с обходами узлов
заявками относительно распределений длительностей обслуживания в
узлах с инверсионной дисциплиной обслуживания и абсолютным при
оритетом для поступающей в узел заявки;
г) устанавливается критерий мультипликативности стационарно
го распределения открытой сети массового обслуживания с обходами
узлов заявками и открытой сети массового обслуживания с обходами
и ограниченным временем ожидания в очередях.
Объект и предмет исследования.
Исследуются открытые и замкнутые сети массового обслуживания с обходами узлов заявками. Изучается стационарный режим работы таких сетей.
Гипотеза.
Стационарное распределение марковских сетей массового обслуживания с обходами узлов заявками имеет форму произведения в предположении, что узлы квазиобратимы, и инвариантно по отношению к распределению длительностей обслуживания в узлах в случае, когда поступающая в узел начинает обслуживаться немедленно, вытесняя заявку, находящуюся на приборе, в очередь.
Методология и методы проведенного исследования.
В работе использовались методы теории вероятностей, теории случайных (марковских) процессов, теории массового обслуживания. В исследованиях мультипликативности стационарного распределения
применялся метод локального баланса, при анализе выходящих потоков использовался метод обращения времени, для установления критерия мультипликативности использован нетрадиционный подход описания сети, позволяющий переходы из некоторого состояния в это же самое состояние с некоторой положительной интенсивностью.
Научная новизна и значимость полученных результатов.
-
Для открытых и замкнутых сетей массового обслуживания с обходами узлов заявками, в которых изолированый узел описывается марковским процессом, определены условия, при которых стационарное распределение такой сети имеет форму произведения.
-
Для открытой сети с обходами узлов заявками доказана пуас-соновость выходящих из сети потоков заявок.
-
Доказана инвариантность стационарного распределения сети с обходами относительно распределений длительностей обслуживания в узлах с инверсионной дисциплиной обслуживания и абсолютным приоритетом для поступающей в узел заявки.
-
Установлен критерий мультипликативности стационарного распределения открытой сети массового обслуживания с обходами узлов заявками и открытой сети с обходами и ограниченным временем ожидания в очереди.
Все результаты работы новые и являются развитием и обобщением имеющихся результатов по сетям массового обслуживания, в частности, по сетям с обходами узлов заявками на случай, когда состояние изолированного от сети узла описывается марковским процессом.
Результаты диссертации развивают научные представления о сетях массового обслуживания, работающих в стационарном режиме.
Практическая значимость полученных результатов.
Работа имеет теоретический характер. Практическая значимость полученных результатов определяется возможностью применять их к достаточно широкому классу задач при проектировании и эксплуатации реальных объектов таких, как сети ЭВМ, сети передачи данных, коммуникационные сети, локальные сети и т.д.
Основные положения диссертации, выносимые на защиту.
1. Стационарное распределение открытой и замкнутой сети массового с обходами узлов заявками, в которой изолированный узел описывается марковским процессом, имеет мультипликативную форму при условии квазиобратимости узлов сети. В случае открытой сети выходящие из нее потоки заявок являются пуассоновскими.
-
Для открытой и замкнутой сети массового обслуживания с инверсионной дисциплиной обслуживания и абсолютным приоритетом для поступающей в узел заявки стационарное распределение инвариантно по отношению к функциональному виду распределений длительностей обслуживания при фиксированных первых моментах.
-
Устанавливается критерий мультипликативности стационарного распределения открытых марковских сетей массового обслуживания с обходами узлов заявками и открытых марковских сетей с обходами и ограниченным временем ожидания в очереди.
Личный вклад соискателя.
Все результаты, приведенные в диссертации, получены автором самостоятельно. В совместных работах постановка задач и обсуждение результатов принадлежат научному руководителю. В работе [4] автору принадлежит раздел 5. В работе [1] автору принадлежат результаты, относящиеся к классу 2.
Апробация результатов диссертации.
Материалы диссертации докладывались на 12-й Белорусской зимней школе-семинаре по теории массового обслуживания "Исследование систем и сетей массового обслуживания" (Гродно, 1996), на VII Белорусской Математической конференции (Минск, 1996), на 13-й Белорусской зимней школе-семинаре по теории массового обслуживания "Математические методы исследования телекоммуникационных сетей" (международная научная конференция BWWQT -97, Минск, 1997), на 14-й Белорусской зимней школе-семинаре по теории массового обслуживания "Математические методы исследования систем и сетей массового обслуживания" (международная научная конференция BWWQT-98, Минск, 1998), на Республиканской научно-технической конференции для студентов и аспирантов "Новые компьютерные технологии в науке, технике, производстве и индустрии развлечений" (Гомель, 1998),на II Республиканской научно-технической конференции для студентов и аспирантов "Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях" (Гомель, 1999), на 15-й Белорусской школе-семинаре по теории массового обслуживания "Современные математические методы исследования телекоммуникационных сетей" (международная научная конференция BWWQT -99, Минск, 1999).
Опубликованность результатов.
Результаты диссертации отражены в 10 работах, из них 2 статьи в научных журналах, б статей в сборниках материалов научных конфе-
ренций, 2 тезисов научных конференций. Общее количество страниц опубликованных материалов — 42.
Структура и объем диссертации.
Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения, списка используемых источников. Общий объем диссертации составляет 95 страниц. Общий объем 2 иллюстраций — 1 страница. Общее количество использованных источников равно 93.
Похожие диссертации на Стационарное распределение вероятностей состояний сетей обслуживания с обходами
