Введение к работе
Современные инфотелекоммуникационные и вычислительные системы становятся все более сложными, что обусловлено необходимостью повышения надежности передачи и обработки информации. Построение и исследование математических моделей для оценки качества их функционирования является важной задачей. Применение для этой цели классических моделей теории массового обслуживания не всегда дает адекватные результаты, поскольку необходимо, чтобы модели учитывали как характерные особенности систем, так и возможное влияние различных дестабилизирующих факторов, как, например, внезапные сбои, попадание вируса, потеря передаваемых или обрабатываемых данных, существенное увеличение времени обработки информации вследствие всплеска нагрузки на узел.
Для учета подобных факторов Е. Геленбе, П. Глинн, К. Сигман в своей статье1 предложили концепцию отрицательных заявок, и связанных с ними сетей и систем массового обслуживания, которые получили название соответственно G-сети и G-системы. Классический принцип действия отрицательных заявок заключается в следующем. Отрицательная заявка при поступлении в СМО или в некоторый узел СеМО "убивает" (разрушает) одну обычную заявку, ожидающую в очереди, после чего обе заявки мгновенно покидают систему. С тех пор было исследовано большое число различного вида систем и сетей обслуживания с отрицательными заявками: рассматривались случаи, когда отрицательные заявки могли удалять группу ожидающих в очереди заявок или полностью опустошать очередь (катастрофы); были также введены понятия триггера, выталкивающего заявку из одного узла сети в другой, и сигнала, который с заданной вероятностью может быть либо отрицательной заявкой, либо триггером. Подробное исследование публикаций в области исследования G-систем и G-сетей до 2003 года, включая известные обобщения, приводится, например, в обзорах Бочарова П.П. и Вишневского В.М.2 , и Artalejo J.R.3. В теоретических работах после 2003 года внимание уделялось исследованию различных модификаций G-систем, например, с марковским входящим потоком, марковским обслуживанием, специальными дисциплинами обслуживания и "убийства" заявок. Из недавних прикладных работ в этой области стоит отметить исследования по применению G-систем в телефонии для моделирования работы call-центров, при анализе систем инвентаризации и анализу механизмов балансировки нагрузки в телекоммуникационных сетях4'5.
Значительное внимание уделяется и изучению систем с отрицательными заявками в
1 Gelenbe Е., Glynn P., Sigman К. Queues with negative arrivals // Journal of Applied Proba
bility. 1991. V. 28. P. 245-250.
2 Бочаров П.П., Вишневский В.М. G-сети: развитие теории мультипликативных сетей //
Автоматика и телемеханика. 2003. № 5.
3 Artalejo J.R. G-networks: A versatile approach for work removal in queueing networks. Eur.
J. Oper. Res., 2000, vol. 126, pp. 233-249.
4 Yang Woo S. Multi-server retrial queue with negative customers and disasters // Queueing
Syst. 2007. № 55. P. 223-237.
5 Manuel Paul, Sivakumar В., and Arivarignan G. Perishable Inventory System with Postponed
Demands and Negative Customers // Journal of Applied Mathematics and Decision Sciences. 2007.
дискретном времени ' . Это объясняется тем, что они играют важную роль в оценке производительности систем и сетей связи, поскольку позволяют учитывать дискретный характер передаваемой информации и дискретность функционирования реальных систем.
Предметом исследования являются стационарные вероятностно-временные характеристики функционирующих как в непрерывном, так и в дискретном времени систем обслуживания с отрицательными заявками, которые не "убивают", а вытесняют заявки, поступившие в систему, в другую очередь (бункер) из которой те обслуживаются с относительным приоритетом.
Классическая отрицательная заявка предполагает "удаление" работы из системы или сети. Однако на практике встречаются системы, в которых уже поступившая в систему работа не "удаляется" безвозвратно вследствие внутренних или внешних факторов, а откладывается на некоторое случайное время. Примером могут служить системы распределенных вычислений, где необходима синхронизация выполненных заданий, а вычислительное оборудование вышло из строя; системы распределенных баз данных, где, в случае сбоев программного обеспечения, происходят откаты (но не удаление) транзакций в рамках механизма двухфазной фиксации. Поэтому исследование систем с отрицательными заявками, позволяющих исследовать качество функционирования реальных систем с учетом подобных аспектов, является актуальной задачей.
Цель работы. Целью диссертационной работы является разработка математических методов расчета стационарных характеристик марковских систем массового обслуживания с отрицательными заявками и бункером для вытесненных заявок с различными ограничениями на емкости накопителя, бункера и на число приборов, функционирующих как в непрерывном, так и в дискретном времени.
Научная новизна. В диссертации получены следующие новые научные результаты:
Введена новая модель системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок.
Разработан математический метод расчета основных стационарных характеристик одноканальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок, с очередями в накопителе и бункере неограниченной емкости.
Предложены аналитические методы и алгоритмы расчета совместного стационарного распределения в одноканальных системах массового обслуживания с отрицательными заявками и бункером для вытесненных заявок, с различными ограничениями на длины очередей в накопителе и бункере, разработанные, в том числе, с помощью теории многочленов Чебышева и Гегенбауэра. Показано как полученные результаты, касающиеся стационарных характеристик рассмотренных одноканальных систем, можно перенести на случай, когда в системах не один, а п приборов.
6 Li Ma A Class of Geom/Geom/1 Discrete-time Queueing System with Negative Customers.
Int.J.NonlinearSci., V. 5, No. 3, 2008. P.275-280.
7 Hyun Min Parka, Won Seok Yangb, Kyung Chul Chaea The Geo/G/1 Queue with Negative
Customers and Disasters. Stochastic Models. V. 25 Issue 4. 2009.
4. Предложен аналитический метод расчета стационарных характеристик для функционирующей в дискретном времени одноканальной марковской системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок с очередями в накопителе и бункере неограниченной емкости.
Научная и практическая ценность. Результаты диссертации могут быть использованы в качестве теоретической основы для будущих исследований более сложных систем массового обслуживания с отрицательными заявками и бункером для вытесненных заявок.
Разработанные в диссертации математические методы и вычислительные алгоритмы могут применяться для анализа характеристик телекоммуникационных систем, систем распределенных вычислений и систем распределенных баз данных.
Исследования проводились в рамках грантов Российского фонда фундаментальных исследований (РФФИ) № 06-07-89056-а "Математические модели, методы, алгоритмы и программное обеспечение, основанное на веб-технологиях, для проведения фундаментальных исследований в области анализа производительности сетевых систем" и № 09-07-12032-офи_м "Разработка математические методов, вычислительных алгоритмов и программных средств для решения задач моделирования информационно- вычислительных и телекоммуникационных систем".
Методы исследования. В работе используются методы теории вероятностей, теории случайных процессов, теории массового обслуживания и теории специальных функций.
Личное участие автора. Научному руководителю диссертации Печинкину А.В. принадлежат постановки задач и помощь в выборе методов исследования. Автору диссертации принадлежат аналитические преобразования и выводы, доказательства теорем, проведение численных расчетов и имитационного моделирования. В работе [4], опубликованной в соавторстве с Р. Мандзо и И. Касконе, соавторам принадлежит участие в постановке задачи и обсуждение методов исследования.
Реализация результатов работы. Результаты исследований вошли в программу "WEB-ориентированный программный комплекс удаленного расчёта стационарных характеристик систем массового обслуживания"8. На основе теоретических результатов написаны программные модули расчета моделей
одноканальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок полностью конечной емкости и
одноканальной системы массового обслуживания с отрицательными заявками и бункером для вытесненных заявок полностью неограниченной емкости,
которые зарегистрированы в Реестре программ для ЭВМ Российского агентства по патентам и товарным знакам9.
8 Дата регистрации РОСПАТЕНТом 11.01.2010г., номер свидетельства о регистрации
№ 2010610026.
9 Свидетельство № 2011610585 и № 2011610589 соответственно.
Результаты диссертации использовались в научно-исследовательских работах, проводимых Институтом проблем информатики Российской академии наук:
Разработка общих базовых математических методов расчёта систем массового обслуживания, функционирующих в дискретном времени10.
Исследование систем и сетей массового обслуживания специального вида и информационно-управляющих систем с новыми видами обратной связи11.
Исследование систем и сетей массового обслуживания специального вида с ненадёжными приборами и отрицательными заявками.
Достоверность и обоснованность.
Все сформулированные в диссертации теоремы доказаны. Достоверность результатов также подтверждена данными сравнений с результатами имитационного моделирования, которые показали хорошую точность.
Апробация работы. Результаты работы были представлены на следующих научных конференциях и международных семинарах:
XLII-XLVI Всероссийские конференции по проблемам математики, информатики, физики и химии. Москва, Российский университет дружбы народов (РУДИ), 2006-2010;
международная конференция "International Conference on Ultra Modern Telecommunications" - ICUMT 2010 (18-20 October 2010, Moscow, Russia);
международный семинар "Распределенные компьютерные и телекоммуникационные сети" - DCCN 2010 (26-28 Октября 2010, Москва, Россия);
V отраслевая научная конференция "Технологии Информационного общества", посвященная 90-летию МТУСИ (9-10 Февраля 2011, Москва, Россия);
Кроме того, результаты работы докладывались на заседаниях следующих научно-исследовательских семинаров:
научный семинар ФГУП ЦНИИС и секции "Моделирование сетей связи, информационных систем и процессов" МНТОРЭС им. А.С. Попова, декабрь 2010;
научный семинар кафедры исследования операций Московского государственного института электроники и математики (технический университет), 2011;
научные семинары по теории массового обслуживания в институте проблем информатики Российской академии наук (ИПИ РАН), 2008-2011.
Публикации. Результаты диссертации опубликованы в 11 работах соискателя, перечень которых приведен в конце автореферата. Научные работы [4, 6, 11] опубликованы в журналах, входящих в утвержденный ВАК перечень ведущих рецензируемых научных изданий, в которых должны быть размещены основные научные результаты диссертации на соискание ученой степени кандидата наук.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 137 страниц текста, в
10 Свидетельство № 01200903883.
11 Свидетельство № 01200807411.
том числе 8 рисунков и 18 таблиц. Список литературы включает в себя 71 наименование, в том числе и публикации соискателя по теме исследования. Каждая глава разбита на параграфы, параграфы, в свою очередь, разбиты на пункты, имеющие порядковую нумерацию. Формулы внутри каждого пункта имеют двойную нумерацию с указанием главы и порядкового номера формулы в данной главе.
