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

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

Головко Николай Иванович

ИССЛЕДОВАНИЕ МОДЕЛЕЙ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ В ИНФОРМАЦИОННЫХ

СЕТЯХ

05 13 18- математическое моделирование, численные методы и комплексы программ

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

Владивосток 2007

ООЗ160253

003160253

Работа выполнена в Тихоокеанском государственном экономическом университете на кафедре математики и моделирования

Научный консультант

Официальные оппоненты

Ведущая организация

доктор физико-математических наук, профессор

КАТРАХОВ Валерий Вячеславович

доктор технических наук, профессор ДЕВЯТИСИЛЬНЫЙ Александр Сергеевич

доктор технических наук, профессор ЗАМЯТИН Николай Владимирович

доктор технических наук, профессор ПЛУТЕНКО Андрей Долиевич

Томский государственный университет

Защита состоится 8 ноября 2007 г в Ю00 часов на заседании диссертационного совета Д 005 007 01 в Институте автоматики и процессов управления Дальневосточного отделения РАН по адресу 690041, г Владивосток, ул Радио, 5

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

Автореферат разослан

/

£ 2007

г.

Отзывы на автореферат (2 экз ), заверенные печатью, высылать по адресу 690041, г Владивосток, ул Радио, 5, ученому секретарю диссертационного совета Д 005 007.01

Ученый секретарь

диссертационного совета Д 005 007 01

А В Лебедев

Общая характеристика работы

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

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

В качестве аналитических моделей сети в целом и отдельных ее элементов использовали сети и системы массового обслуживания (СМО) О И Авен, Я А Коган, Ф А Скляревич', Е.А Лебедев, J Sztrik и другие авторы

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

Однако для реальных моделей (элементов сетей ЭВМ, вычислительных комплексов, сетей связи) это предположение не всегда выполняется. Параметры потоков сообщений в таких системах претерпевают с течением времени случайные или детерминированные изменения по ряду причин Нестационарность входных потоков сети изучали А И Ляхов, С Baiocchi, Р.А W Lewis, A Svoronos, R A Upton. Возникновение и исчезновение потоков сообщений в узлах информационных сетей в силу изменения маршрутов сообщений или выхода из строя отдельных элементов сети исследовали Л Б Богуславский, Л А. Растригин, Ф А Скляревич, А К Agrawala Функционирование узлов локальных, а также глобальных информационных сетей типа Интернет (про-

вайдерских узлов связи, proxy и web серверов, передающих станций и тд), описываемых СМО с параметрами, изменяющимися в случайные моменты времени, рассмотрено Г.П Башариным, В А. Кокотушки-ным, В.А Наумовым, Д К. Снайдером В таких СМО на вход поступает дважды стохастический пуассоновский поток заявок со случайной интенсивностью, длительность обслуживания распределена по экспоненциальному закону, накопитель имеет конечный или бесконечный объем

Достаточно хорошо исследованы СМО с входным дважды стохастическим пуассоновским потоком заявок со скачкообразной интенсивностью, имеющей дискретное пространство состояний, в работах А.М Горцева, А Н. Дудина, М.Ю Китаева, В И Клименок, А А. Назарова, M Т Саксонова, JIИ Самочерновой, А.Ф Терпугова, А М. Чеботарева, А А. Юшкевич, J Abate, I Iscoe, J Keilson, Nam Su, T Rolski, L D. Servi Дважды стохастические потоки, интенсивность которых является процессом с независимыми приращениями или гауссовским процессом, рассмотрены в работах С Cheng-Shang, Chao Xiu Li, Pinedo Michael.

Нестационарное распределение числа заявок в СМО с пуассоновским входным потоком заявок, экспоненциальным обслуживанием, постоянными интенсивностями входного потока и обслуживания, бесконечным накопителем получил А Б Кларк Впоследствии аналогичное решение несколько другим методом получено А. Гешевым В дальнейшем появилось множество работ, посвященных анализу и расчету нестационарных вероятностных характеристик СМО с постоянными интенсивностями входного потока и обслуживания с бесконечным или конечным накопителем в работах А И Ляхова, Г.П Климова, Б В Три-воженко, Я Стрик, H. Greenberg, E.L Leese, Р Leguesdron, M F. Neuts, R R Read, R A Sack, K. Stange, R Syski

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

потоком и экспоненциальным обслуживанием с постоянными интен-сивностями

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

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

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

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

— разработка новых методов и средств мониторинга информационных потоков в ИС,

— построение моделей систем массового обслуживания, описывающих функционирование серверов,

— разработка математических моделей СМО в ИС,

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

—- разработка рекомендаций по использованию характеристик показателей эффективности функционирования СМО в ИС с целью прогноза состояния ИС.

Основные научные результаты.

1. Разработаны новые методы мониторинга информационных потоков в информационных сетях с использованием протоколов функционирования серверов

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

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

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

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

7 Предложены новые методы

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

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

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

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

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

10 Выработаны научно-технические рекомендации для применения моделей систем массового обслуживания в ИС

11. На основе мониторинга ИС и результатов исследования моделей СМО ИС даны рекомендации к модернизации программного обеспечения и оборудования ИС в Тихоокеанском государственном экономичес-

ком университете (ТГЭУ)

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

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

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

3 Разработаны новые численные методы расчета характеристик СМО в информационных сетях

4 Выработаны научно-технические рекомендации для применения моделей СМО в информационных сетях На основе мониторинга ИС и результатов исследования моделей СМО ИС даны рекомендации к модернизации программного обеспечения и оборудования ИС в ТГЭУ

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

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

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

ных вычислительных сетей типа Интернет провайдерских узлов связи, web-серверов, передающих станций и т д

Составлены на языке FORTRAN Visual Workbench v 1 00 комплексы программ и методических рекомендаций для мониторинга и статистического анализа информационных потоков, а также для расчета характеристик потоков сообщений в узлах информационных сетей распределения, среднего числа сообщений в узлах информационных сетей, времени ожидания сообщением начала обслуживания

Реализация результатов работы. Теоретические результаты данной работы, составленные комплексы программ и методических рекомендаций для мониторинга и статистического анализа информационных потоков, а также для расчета характеристик потоков сообщений в узлах информационных сетей использованы в ряде организаций для расчета вероятностных характеристик информационных сетей данных организаций, о чем получены акты о внедрении, в том числе в Тихоокеанском государственном экономическом университете, департаменте связи и информатизации администрации Приморского края, ОАО "ВМТП", ООО " Дальрефтранс"

Публикации. По материалам диссертации опубликовано 60 работ, из них 2 монографии, 24 статьи и препринта, в том числе 6 работ в рецензируемых изданиях, 4 публикации в журналах из списка ВАК Объем и структура работы. Диссертация изложена на 349 страницах компьютерного текста (набранного в системе ВД^дХ) и состоит из введения, 15 глав, заключения и списка литературы, включающего 358 наименований К ней дано также 3 приложения, изложенных на 50 страницах Работа содержит 227 рисунков

Апробация результатов. Результаты реферируемой работы докладывались на V Всесоюзной конференции КОМПАК-87 Вычислительные сети коммутации пакетов (Рига, 1987), Всесоюзной конференции "Совершенствование методов исследования потоков событий и систем массового обслуживания" (Томск, 1989), шести Всероссийских межвузовских научно-технических конференциях ТОВВМУ (Владивосток,1993-1998), II Международной конференции по математическому моделированию (Якутск, 1997), четырех Дальневосточных конференциях студентов и аспирантов по математическому моделированию (Владивосток, 1997-2000), 4-м Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 2000), трех Воронежских международных научно-технических конференциях "Математическое моделирование в естественных и гуманитарных науках" (Воронеж, 2000-2002), четырех Воронежских международных научно-технических конференциях "Современные проблемы прикладной математики и математического моделирования" (Воронеж, 2003-2006), двух

международных Белорусских школах-семинарах по теории массового обслуживания (Гомель, 2003,2004), научном семинаре под рук акад В.А Ильина и акад. Е И Моисеева на факультете ВМК МГУ (Москва, 2004), научном семинаре под рук проф А И Кожанова в Институте математики СО РАН (Новосибирск, 2004), объединенном научном семинаре Института прикладной математики ДВО РАН (Владивосток, 2005, 2006), научных семинарах кафедры математики и моделирования Тихоокеанского государственного экономического университета (Владивосток, 2003,2006), восьми Дальневосточных школах-семинарах им акад Е В Золотова (Владивосток, 1998-2005)

Личный вклад автора состоит в разработке концепции и постановке задач исследования Автором лично развиты математические модели и методы математического моделирования систем массового обслуживания в информационных сетях Предложение об использовании моделей систем массового обслуживания с дважды стохастическим входным пуассоновским потоком для исследования информационных сетей появилось в результате обсуждений проблемы с профессором А Ф Терпуговым и И А Коротаевым [3,4, 5,9-11], а окончательные формулировки и итоговые теоретические и численные экспериментальные результаты получены автором самостоятельно Неоценимый вклад в настоящую работу внес научный консультант профессор В В. Катра-хов, он участвовал в исследовании вопросов существования стационарного режима и эргодичности систем массового обслуживания с дважды стохастическим входным пуассоновским потоком [1, 2, 7, 8, 14-26] Научно-исследовательские работы по изучению моделей систем массового обслуживания в информационных сетях проводились совместно с аспирантами Тихоокеанского государственного экономического университета ТА Жук (Писаренко) [7, 16, 17], Н А Кучер (Филинова) [6, 13-15, 18-20], Е А Свителик [22, 23], В Е. Таниным, В О Каретником и Владивостокского государственного университета экономики и сервиса ДЕ Рыжковым [26], научным руководителем которых являлся автор

Содержание работы

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

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

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

Рис 1 Схема информационной сети ТГЭУ

Первая часть содержит 5 глав В 1-й главе дается тематический обзор по проектированию сетей передачи данных Приводятся общие сведения о сетях передачи данных Рассматривается классификация сетей передачи данных Подробно исследуются технологии реализации локальных сетей передачи данных, в частности, технологии Ethernet, Token Ring, FDDI, Fast Ethernet, Gigabit Ethernet, DSL, ADSL, R-ADSL, IDSL, HDSL, SDSL, VDSL Bo 2-й главе выполнен тематический обзор по администрированию сетей и сервисов Интернет Исследованы вопросы- проблемы администрирования сетей TCP/IP, организация сети

TCP/IP, подключение локальной сети к Интернет, маршрутизация в сетях TCP/IP, организация системы доменных имен, обмен электронной почтой, информационные технологии Интернет, проблемы безопасности сетей TCP/IP, основы межсетевого обмена в сетях TCP/IP, структура стека протоколов TCP/IP, основные протоколы стека TCP/IP, стандарты "Семиуровневой модели сетевого обмена" или в английском варианте "Open System Interconnection Reference Model" (OSI Ref.Model) В 3-й главе на основе исследования общих закономерностей информационных сетей в структуре, составе, программном обеспечении, протоколах взаимодействия в типовых информационных сетях с количеством рабочих станций более 600 получены следующие результаты

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

Например, как это показано на рис 1 пользователи информационной локальной сети (JIC) Тихоокеанского государственного экономического университета через коммутаторы этажей и корпусов, затем через корневой коммутатор подключаются к специализированным серверам, таким как сервер локальных ресурсов, библиотечный сервер, сервер баз данных, ргоху-сервер, web-сервер, сервер мониторинга В частности, работу Proxy-сервера описывает следующая типичная модель СМО Proxy-сервер получает заявки от пользователей JIC на доступ к Интернет ресурсам, выполняет запрос доступности данных ресурсов и получив положительный ответ, реализует заявки

Информационный обмен между ргоху-сервером и Интернет ресурсами реализуется с помощью пакетной коммутации, при которой информация передается пакетами с использованием установленных протоколов связи в течении определенных сеансов При этом каждая заявка порождает совокупность дополнительных сеансов, которые называют порожденными сеансами Если пользователь JIC обратился, например, к сайту, то каждый дополнительный сеанс служит обычно для передачи в виде отдельных файлов объектов, размещенных на сайте (картинок, отдельных фреймов, банеров и т д )

Совокупность порожденных сеансов одного пользователя JIC является одной общей (интегральной) заявкой Закон распределения интер-

валов времени между моментами поступления интегральных заявок характеризует тип входного потока интегральных заявок

Закон распределения интервалов времени т\<г между моментами поступления заявок характеризует тип входного потока заявок Обслуживание каждой заявки заключается в передаче файла определенного объема Уг со скоростью К, равной максимальной пропускной способности сервера Совокупность случайных величин г)г = Уг/К образует совокупность длительностей обслуживания, закон распределения которых характеризует тип обслуживания

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

Предложены новые средства мониторинга информационных потоков в информационных сетях, представляющих собой совокупность программных модулей, использующих протоколы функционирования серверов Согласно стандартам " Семиуровневой модели сетевого обмена" (OSI Ref Model) на 7-м — прикладном уровне работа каждого сервера регистрируется специальными протоколами, в которых, как правило, отмечается для каждого сеанса внутренний адрес заявки JIC (в виде IP адреса и/или JIC идентификатора), дата и время заявки, web-адрес запрашиваемых ресурсов, код результата запроса выполнения заявки, объем передаваемой информации (в байтах) — длина пакета Предложенные средства мониторинга представляют собой совокупность разработанных программных модулей, которые автоматически считывают в результате синтаксического анализа из протоколов функционирования серверов информацию о входном потоке заявок и обслуживании, в частности — информацию об интервалах времени т>г между моментами поступления заявок и совокупности длительностей обслуживания 7)г = Уг/К

С применением статистических методов исследованы прикладные модели СМО и классифицированы типы возможных входных потоков, законы распределения обслуживания, в результате чего в информационных сетях обнаружены новые, ранее не исследованные типы СМО Установлено, что обслуживание экспоненциальное с постоянным параметром fjb, на вход данных СМО поступает пуассоновский поток заявок со случайной — диффузионной или скачкообразной — интенсивностью A(i) входного потока с непрерывным пространством состояний, емкость накопителя является конечной или бесконечной Наблюдалась диффузионная интенсивность с упругими границами и постоянными коэффи-

циентами сноса и диффузии

Для статистического анализа распределения времени обслуживания в контрольные моменты наблюдались выборки длин пакетов Уь , Уп, объема п = 450 На основе данной выборки строился вариационный ряд

V. И v2 vk

пг П1 П2 . Пк

объема п = пх + + пк, Уу <У'г< <14, с выборочными частотами п1;

, п/с Выборка (1) использовалась для построения выборки времен обслуживания т]г — Уг/ь

% m m m

nt Пг n2 Пк

На основе выборки (2) строилась эмпирическая функция распределения Fe (t) согласно определению по формуле

(з)

z—' п п

г T)><t

где суммирование проводится по всем значениям индекса г, для которых выполняется условие г)г < t На рис 2 показан график эмпирической функции распределения Fe (t) в контрольный момент времени Ю00 Аналогичный вид имеют графики эмпирической функции распределения в остальных контрольных точках наблюдения. По графику Fe(t) виден экспоненциальный характер распределения времен обслуживания Поэтому в качестве теоретического уравнения регрессии принята функция экспоненциального распределения Ft(t)

Ft(t) = 1-е-"',

где ц — параметр экспоненциального распределения Для краткости функция Ft(t) называется теоретической функцией экспоненциального распределения На рис 2 график эмпирической функции показан слева и справа, тогда как график теоретической функции распределения показан только слева Такое построение графиков выполнено в силу достаточной близости данных функций, из-за которой графики функций сливаются

03 06 0912 15 ¿(сек) 0 03 060912 15 ¿(сек)

Рис 2 Распределение времени обслуживания

Параметр /л находился двумя различными методами, по методу наименьших квадратов (для экспоненциальной регрессии) и с применением основного свойства экспоненциального распределения

Рассматривалась относительная погрешность отклонения эмпирической -Ре(<0 от теоретической Ft(i) функции распределения по норме пространства Ь\ интегрируемых функций

(4)

где

г г

У 1^.(4)11^1(4)11^= / (5)

о о

значение г задавалось из условия поточечного отклонения (4)

не более чем на малое значение е —10_6 для ¿>г Для рис 2 значения г равны максимальным значениям абсцисс По сути, относительная погрешность — это относительное отклонение площадей под функциями распределениями на интервале (0,г) Расчеты показали меньшую погрешность отклонения эмпирического и теоретического распределений е/,, для значений д, найденных по формуле ц = 1/7?

Статистический анализ показал невысокую погрешность отклонения €ьг эмпирической и теоретической функции распределения в среднем на 0 14%

Во всех контрольных точках проверялась гипотеза об экспоненциальном законе распределения времени обслуживания с применением критерия Пирсона при уровне значимости у = 0 05 В процедуре использования критерия Пирсона задавалось число интервалов з = 50 и области группирования строились равномерным разбиением интервала выборочных значений на в подинтервалов Количество степеней свободы критерия бралось равным к = в — 2 В частности, согласно расчетам для рис 2 наблюдаемое значение критерия "хи-квадрат" Х^адл равно 133, критическая точка критерия "хи-квадрат" при заданном уровне значимости х|р равна 173 Расчеты показали во всех контрольных точках наблюдаемое значение критерия меньше критической точки Это означает, что результаты проверки гипотезы не противоречат гипотезе об экспоненциальном характере распределения времени обслуживания

Аналогичным образом с помощью эмпирической и теоретической функции распределения показано экспоненциальное распределение интервалов времени между моментами поступления заявок порожденных сеансов, а также во всех точках проверялась гипотеза об экспоненциальном распределении Параметр данного экспоненциального распределения Л находился с применением основного свойства экспоненциального распределения А = 1/т

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

При количественном описании потока временной интервал наблюдения (40, ,£„) разбивался на детерминированные малые единичные интервалы г\, ,гп, в которых наблюдались средние значения числа заявок Мг/х, ,Ы\vn Вычисление величин ЬЛи\, , ЬАрп производилось усреднением количества появившихся заявок на подинтервалах интервалов г\, , гп

Статистический анализ показал диффузионный характер изменения интенсивности А(£) входного дважды стохастического пуассоновского потока для серверов с большим режимом загрузки и скачкообразный характер А(£) с непрерывным пространством состояний для серверов с невысоким режимом загрузки Большой режим загрузки наблюдался для ргоху-сервера и \veb-cepBepa, невысокий режим загрузки — для сервера баз данных и библиотечных серверов Диффузионная интенсивность наблюдалась в основном с упругими границами, в единичных случаях — с поглощающими Примеры диффузионной и скач-

кообразной интенсивности приведены на рис 3

09 30

10 8 6 4 2 0

т

11-00

О 0.6 121824 3 ¿(мин) о 03060912 15 *(мин) а) диффузионная б) скачкообразная

Рис 3 Интенсивность А(£)

Поскольку, согласно определению, диффузионным процессом А(£) называется марковский случайный процесс 2-го порядка с независимыми приращениями, диффузионные моменты 1-го и 2-го порядка которого равны коэффициенту сноса а(£,ат) и коэффициенту диффузии Ь(£,ж), соответственно, то проверялась гипотеза о независимости малых приращений А(<)

Статистический анализ входного потока заявок порожденных сеансов на ргоху-сервере показал наличие диффузионной интенсивности входного потока с постоянными коэффициентами сноса и диффузии Статистический анализ потока входных заявок показал также наличие диффузионной интенсивности входного потока на других серверах, как правило на таких, где заявки во входном потоке появляются достаточно часто, например, на \уеЬ-сервере

Статистический анализ скачкообразной интенсивности А(£) с применением проверки соответствующих гипотез показал, что интервалы постоянства Т интенсивности распределены экспоненциально с постоянным параметром а = Т, а значения А(£) в точках разрыва — независимы

В 4-й главе строятся математические модели исследуемых СМО с экспоненциальным обслуживанием интенсивности ц, одним обслуживающим прибором емкости N0 Максимальное число заявок в СМО равно N = N0 + 1 На вход СМО поступает ДС пуассоновский поток заявок с диффузионной интенсивностью входного потока А(£) с упругими границами [а,/3], коэффициентом сноса а и коэффициентом диффузии

Ь. Приводится вывод уравнений относительно нестационарных и стационарных характеристик числа заявок в указанных СМО Здесь и в дальнейшем для краткости характеристиками числа заявок называется совместное нестационарное распределение Qk(t,x) = P{v{t) = к,х< X(t)<x+dx}/dx,0^k^N, числа заявок u(t) и интенсивности A(i) входного потока (нестационарные характеристики числа заявок) и совместное стационарное распределение qk(x) = Р{и = к,х<\<x + dx}/dx,0^ k^N, числа заявок v и интенсивности Л входного потока в стационарном режиме (стационарные характеристики числа заявок) В дальнейшем в работе для краткости СМО с ДС пуассоновским потоком заявок называются дважды стохастическими СМО (ДС СМО) Кроме того, в работе для краткости используется система обозначений Кендала СМО с пуассоновским дважды стохастическим входным потоком с интенсивностью A(i) обозначаются как СМО типа M/M/1/Nq с диффузионной или скачкообразной интенсивностью A(t) Обозначим через f(t,x) = Р{ж < А(£) < x+dx}/dx — нестационарную плотность интенсивности входного ДС потока A(i); через f(x) = P{x<\<x+dx}/dx — стационарную плотность A (t), где и — процесс u(t) в стационарном режиме, А — процесс A (t) в стационарном режиме

Характеристики СМО рассматриваются в пространстве дважды непрерывно дифференцируемых по х функций Введем дифференциальный оператор Ф, одинаково действующий на нестационарные и стационарные характеристики-

ФЯкЦ,х) = -ад-^,фдк(х) = -а<{к (х)

Относительно нестационарных характеристик Qk(t,x),0^k^N, получена начально-краевая задача со следующими уравнениями 1° Во внутренних точках х€(а,/3) для Qk = Qk(t,x)

k=0 —xQo + fiQi + <PQo = ) (6) l^k^N-1 œQfc-i-(® + Ai)Çfc + /iQ*+i + «PQfc = ^, (7)

k = N xQ^-târf+Wrt^ÇQZ- (8) 2° В граничных точках x = a,x = /3

\ 9QdxT^ ~ aQk^ = 0,0^k^N,n=a,r2=p (9)

3° Начальные условия с начальными плотностями (ж)

Qk(0,x) = 7rk(x),wk(x)^0,0^k^N (10)

4° Условие нормировки N

= 0,®е[а,/3] (11)

к=о

Относительно стационарных характеристик получе-

на краевая задача со следующими уравнениями

1°. Во внутренних точках х £ (а,(3)

к = 0 -xqo{x)+|J,q1(x) + Фqo(x) = 0, (12)

1 < к ^ N -1 хцк„х (ж) - (ж + 1м)як (х) + ¡Щк+1 (х) + (х) = 0, (13) к = Ы xqN-1(x)-fJ,qN(x) + ФqN(x) = 0 (14)

2° В граничных точках

^ (г,) - аЯк (г,) = 0,0 ^ к < ЛГ, п = а, г2 = р (15)

3° Условие нормировки

N

£>(*)=/(®) (16)

к=0

Полученные начально-краевая задача (6)-(11) и краевая задача (12)-(1б) для краткости в работе называются 1-й моделью нестационарных и стационарных ДС СМО Первая модель содержит однородную систему уравнений, но неоднородное условие нормировки Для удобства анализа ДС СМО с конечным и бесконечным накопителем в работе выполняется переход ко 2-й модели нестационарных и стационарных ДС СМО с неоднородной системой уравнений Этот переход осуществляется в последующих главах суммированием уравнений (6)-(9) и (12)-(15) по к, где п^к^М, и использованием замены переменных Замена переменных может осуществляться различными способами. Например, в 6-й главе для стационарного режима используется замена переменных рп (х) — 0 цк (х), 0 ^ п ^ N0 Тогда 2-я модель для стационарных характеристик рп (х), 0 ^ п ^ N0, N0 = N — 1, представляет собой следующую краевую задачу

1° Во внутренних точках х£(а,13)

п = 0 -{х + ц)ро(х) + №1(х) + Фро(х)=0, (17)

1<п<Л/о-1 жРп-1 (х) — (х + /и,)рп(х) +/хрп+1(х) + Фрп(х)=0, (18) п = N0 ц/(х)+хрм0~1(х)-(х + 1л)рн0(х) + Фрп0(х) = 0 (19)

2° В граничных точках

(г.) - арп(г.) = 0,0 < п < ЛГ0, п = а, г2 = /3 (20)

В 12-й главе для нестационарного и стационарного режима используется замена переменных — (для новых переменных здесь используется прямой шрифт), гп(х) = '%2к=пЧк(х),0^

Например, вторая модель для стационарных характеристик дк(х),0^ к^N0,^0 = N-1, представляет собой следующую краевую задачу

1° Во внутренних точках х £ (а,(3):

к = 0 х/(х)-(х + (1)до(х)+цд1(х) + Фдо(х)=0, (21)

хдк-1(х)-(х + (1)дк(х) + цдк+1(х)+Фдк(х) = 0, (22)

& = ЛГ0- хдно-1(х)-(х + ц)дМо(х) + Фдрг0(х)=0 (23)

2° В граничных точках

\д'к (г г) ~ адк (г,) = О, О < к < N0, п = а, г2 - /3 (24)

Вторая модель для стационарных характеристик явно не содержит условия нормировки, но оно выполняется, так как использовалось при замене переменных- го(х) = Вторая модель для неста-

ционарных характеристик имеет аналогичный вид и содержит в правых частях (21)-(24) производные по t

Следует заметить, что для СМО с бесконечным накопителем параметры ЛГ0,]У равны оо

В 4-й главе приводится также вывод и решение в явном виде уравнений с заданными начальными и граничными условиями (упругое отражение от границ) для плотностей /(£,х) и /(х) диффузионного процесса А(£) Уравнение относительно /(¿,ж) представляет собой уравнение Фоккера-Планка с упругими границами

1° Во внутренних точках хЕ(а,/3)

2° В граничных точках х = а,х — 0

ьд/м ьдцт 2 Ъх--= --

3° Начальное условие с начальной плотностью /о (х)

ГР

/(0,я) =/о(ж), / /0(х)сЬс-

J а

4°. Условие нормировки. /а ¡{Ь,х)<1х — 1

В 5-й главе приводится вывод уравнений для характеристик числа заявок СМО с ДС пуассоновским входным потоком заявок со скачкообразной интенсивностью входного потока \(1) Рассматриваются СМО с одним обслуживающим прибором, конечной или бесконечной емкостью накопителя Щ, экспоненциальным обслуживанием интенсивности /1 На вход СМО поступает дважды стохастический пуассоновский поток, интенсивность которого А(4) представляет собой следующий скачкообразный процесс Интервалы Т постоянства А(£) распределены по экспоненциальному закону с параметром а Интенсивность А(£) изменяется на промежутке [а, 6] и имеет в точках разрыва £о справа условную плотность распределения <р(х\у) = Р{аг < А(4о + 0) < х + в,х\А(£о — 0) = у}/с1х, значения процесса А(£) в точках разрыва слева и справа независимы, ¡р(х\у)=(р(х)

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

фдк(«,х) = <р{х)$ЬаЯк{*,у)<1у, Ф®(ж) = <р(х)/й6дк(у)йу

Нестационарные характеристики (¿к(Ь,х) числа заявок удовлетворяют следующей начально-интегральной задаче

1° Система интегро-дифференциальных уравнений для С}к = х)

к = 0 -(ж + а)до + М<91+аФ'9о = ^'9о, (25)

1 ^ к ^ N -1 ~{х + ^ + а)Як+ + аФ<2* = (26)

к = И ж<5Лг_1-(/х + а)дЛГ + аФд^ = —^лг (27)

2° Начальные условия с начальными плотностями тгк(х)

Ок(0,х)=тгк(х),пк(х)^0,0 ^к^Ы (28)

3° Условие нормировки

N

«) = /(*.®)>*>0>аб[а»Ч (29)

к=О

Стационарные характеристики дк(х) числа заявок СМО удовлетворяют следующей системе интегральных уравнений 1° Система интегральных уравнений

к — 0 ~(х + а^о{х)+ дда(а;) + аФдо(ж) = 0, (30)

1 < к < N -1 хдк-1 {х) - (х 4- /л + а)дк(х) + тк+г (ж) + аФдк(х) = 0, (31)

к = Ы хдм-г{х) — (/¿ + а)длг(ж) + аФдм(х) =0

(32)

2° Условие нормировки N

(33)

Полученные начально-интегральная задача (25)-(29) и система интегральных уравнений (ЗО)-(ЗЗ) для краткости в работе называются 1-й моделью нестационарных и стационарных ДС СМО Первая модель содержит однородную систему уравнений, но неоднородное условие нормировки. Для удобства анализа ДС СМО с конечным и бесконечным накопителем в работе выполняется переход ко 2-й модели нестационарных и стационарных ДС СМО с неоднородной системой уравнений. Этот переход осуществляется в последующих главах суммированием уравнений (25)-(28) и (30)-(32) по к, где и использовани-

ем замены переменных — Еьт!^^'1)' О^п^Д^ (для новых

переменных здесь используется прямой шрифт), гп(х)

Например, вторая модель для стационарных характеристик (ж), 0 ^ к ^ Л?о, представляет собой следующую систему интегральных уравнений

& = 0 х/(х)-(х + ц + а)до(х)+[1,д1(х) + аФдо(х)=0, (34) 1 ^ к ^ АГ0 -1 хдк-1 (я) - (х + м + а)дк(х) + мвк+1 (х) + аФдк (ж) = 0, (35) к = И0 хдМо^1(х)-{х + /л + а)дко{х)+аФдт(х) = 0 (36)

Вторая модель для стационарных характеристик явно не содержит условия нормировки, но оно выполняется, так как использовалось при замене переменных го{х) — ^2к=оЯк(х)—/(х) Вторая модель для нестационарных характеристик имеет аналогичный вид и содержит в правых частях (34)-(36) производные по t

Следует заметить, что для СМО с бесконечным накопителем параметры N0, N равны оо

В 5-й главе приводится также вывод и решение интегро-дифферен-циального и интегрального уравнений Колмогорова-Феллера относительно плотностей f(t,x) и /(ж) скачкообразного процесса А(£) Уравнение —а/(г,ж)+аФ/(£,а:) = //(г,а;) с начальным условием при начальной плотности /(ж) /(0,а;) = /(ж) и условием нормировки [а = 1 имеет решение f(t,x)=(p(x) + [f(0,x) — ^p(x)]e~at Уравнение —а/(х) + аФ/(а;) —0 имеет очевидное решение /(ж) = ^р(х)

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

Вторая часть содержит 3 главы 6-я глава содержит анализ СМО типа М/М/1/0 с отказами с диффузионной интенсивностью входного потока Нестационарные характеристики (¿к{Ь,х),к=0,1, для ДС СМО с отказами при ТУо = О, N = 1 удовлетворяют начально-краевой задаче (6), (8), (9)-(11), стационарные характеристики %(х), £ = 0,1, удовлетворяют краевой задаче (12), (14) - (16) Для случая с нулевым и "ненулевым коэффициентом сноса в работе доказано существование и единственность решения краевой задачи относительно стационарных характеристик числа заявок, которые найдены в явном виде с помощью степенных рядов Найденные степенные ряды выражаются через функции Бесселя

В 7-й главе с использованием матричного метода анализа находятся выражения для стационарных характеристик числа заявок в дважды стохастических СМО типа М/М/ 1/Щ, ОсЛ^Соо, с диффузионной интенсивностью входного потока Нестационарные характеристики удовлетворяют начально-краевой задаче (6)-(11), стационарные характеристики qf. (х), 0 ^ к ^ Л/', удовлетворяют краевой задаче (12)-(16).

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

В 8-й главе рассматривается ДС СМО типа М/М/ с конечной емкостью накопителя А/о, экспоненциальным обслуживанием ин-

тенсивности ц на одном обслуживающем приборе На вход ДС СМО поступает дважды стохастический пуассоновский поток заявок со скачкообразной интенсивностью А(£), описанной в 7-й главе. В работе с применением матричного метода находится решение системы интегральных уравнений (ЗО)-(ЗЗ) относительно стационарных характеристик % (х), = числа заявок в СМО Решение получено в виде

сходящегося матричного ряда Неймана Для нахождения дь (х) рассматривается также метод интегрированных характеристик СМО, который заключается в решении векторного уравнения Фредгольма 2-го рода с вырожденным ядром С применением матричного метода находится также решение системы интегро-дифференциальных уравнений (25)-(29) для нестационарных характеристик Приводится до-

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

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

Третья часть содержит 3 главы В 9-й главе рассматриваются нестационарные классические СМО с нестационарным пуассоновским потоком с интенсивностью А(£), нестационарным экспоненциальным обслуживанием на одном приборе с интенсивностью уи(£), с конечным ^0<оо или бесконечным N0 = оо накопителем Обозначим переменные детерминированные интенсивности А(£), р(£) для краткости через А, ¡л Вероятности распределения числа заявок Рк (£) удовлетворяют известной системе дифференциальных уравнений Колмогорова-Чепмена

к = 0 + = (37)

АР*_1(«)-(А + А1)Рк(0+мР*+1(«)=^(*), (38) ¿ = А Р„^)-цРмЦ)=Р'мЦ) (39)

с начальными условиями

^(0)=тгьО^А;^ЛГ!ЛГ = ДГо + 1 (40)

Для нахождения нестационарных вероятностей Рк (£) предлагается метод производящих функций с вариацией правой части Данный метод имеет достаточно широкую общность применения для марковских нестационарных классических СМО произвольной структуры, например СМО с резервными приборами, и демонстрируется на примере СМО М(£)/М(г)/1 с бесконечным и СМО М(£)/М(£)/1/7У0 с конечным накопителями Особенность предложенного метода производящих функций заключается в расширении задачи Коши (37)-(40) для значений к^Ъ и применимости его к решению задачи Коши (37)-(40) с переменными интенсивностями А(£), /х(4)

В 10-й главе исследуются марковские СМО с простейшим пуассо-новским входным потоком заявок интенсивности Л и одним прибором с экспоненциальным обслуживанием интенсивности ¡л Рассматриваются СМО с детерминированными интенсивностями входного потока и обслуживания, с бесконечным и конечным накопителями Вначале исследуются модели классической СМО М/М/1 с бесконечным накопителем Рассматриваются первая, затем вторая модели СМО Модели представляют собой задачи Коши для бесконечных систем уравнений Колмогорова-Чепмена относительно нестационарного распределения числа заявок Системы уравнений рассматриваются в соответствующих банаховых пространствах Рассматривается сначала преобразование 1-й модели во 2-ю, а затем стационарная СМО

Введем обозначения Р (£) = [Р0 (¿), Р\ (£), Рг (£), ]т _ вектор распределения числа заявок Здесь и далее значок 1 обозначает транспонирование Для формулировки результатов используются следующие банаховы пространства стандартные пространства последовательностей I,- и пространство сходящихся к нулю последовательностей £°.

Исходная (1-я) математическая модель СМО М/М/1 представляет собой задачу Коши для бесконечной (для бесконечного накопителя) системы дифференциальных уравнений Колмогорова-Чепмена относительно вектора распределения числа заявок Р[Ь) и имеет вид

^ = Р(0) = Р°, (41)

где Р° — [Р°,Р°]т - начальное распределение вероятностей количества заявок в системе, а А - бесконечная трехдиагональная матрица, у которой элементы подциагонали равны А, элементы надциагонали равны ц, элементы диагонали начиная со второй строки равны —А —р, а в первой строке элемент диагонали равен —А Остальные коэффициенты матрицы А равны О

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

функциями распределения Поэтому осуществляется переход ко второй модели Введем обозначения W = (1,0,0, )т, Р = [РъРг, ]т, P¿(í) = & = 1,2, координаты начального вектора Р(0)=Р° определяются формулой Р£ = Yl°¡Lk > к = 1,2, Введем также матричный оператор А — ~{\ + ц)Е + nD~l +XD+1, где Е — единичная матрица, а однодиагональные матричные операторы сдвига D~x,D+l устроены следующим образом у первого из них единицы стоят на первой над-диагонали, у второго - на первой поддиагонали, а остальные элементы нулевые.

Вторая модель СМО представляет собой задачу Коши dP

-у-= АР + AW, P(0) = P° (42)

at

Для стационарных решений р и р, 1-й и 2-й модели, соответственно, получены следующие результаты Первая модель стационарной СМО сводится к уравнению и условию нормировки

Ар-0, v(jp) = l, peii, а вторая модель - к уравнению

Ар = —Агу, р€Л w = W Эти две задачи, рассматриваемые в соответствующих пространствах, эквивалентны друг другу. В работе показано, что в стационарной СМО стационарное решение р в обычном смысле существует только в случае отсутствия перегрузок, приводятся стационарные решения р и р Следует отметить разный шрифт для обозначения матриц А и А, а также решений р и р для 1-й и 2-й моделей, соответственно

Для динамической СМО показано, что задачи Коши (41) и (42) имеет единственные решения Исследуются операторные экспоненты, спектр и резольвента операторных экспонент, находится решение задачи Коши в соответствующих банаховых пространствах, находится динамическое распределение числа заявок, выраженное через функции Бесселя Изучаются стабилизация нестационарного решения задачи Коши и эргодичность динамической модели СМО, приводятся результаты по асимптотике стабилизации динамического распределения Рассматриваются случаи СМО с перегрузками в критическом (А = дг) и некритическом случае (A >fi), СМО без перегрузок (А < ц) В работе показано, что чем ближе начальное распределение к финитному, чем легче у него хвост, тем с большей скоростью динамическое распределение сходится к финальному В работе рассматриваются случаи, когда хвост начального распределения имеет различный тип

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

В 11-й главе исследуется нестационарное и стационарное распределение незавершенной работы в классической СМО М/М/1 с бесконечным накопителем, простейшим пуассоновским входным потоком заявок с интенсивностью Л, экспоненциальным обслуживанием с постоянным параметром ¡л

Незавершенная работа £/(*) представляет собой время, необходимое для освобождения системы от всех заявок, находящихся в ней в момент t В момент прихода очередной заявки незавершенная работа равна времени ожидания заявкой начала обслуживания

Стационарная функция распределения Ь(ш) удовлетворяет стационарному интегро-дифференциальному уравнению Такача

-АЬН + А

о

с односторонним краевым условием Ь(0) = ро, где ро - стационарная вероятность отсутствия заявок в СМО

Нестационарная функция распределения Нудовлетворяет нестационарному интегро-дифференциальному уравнению Такача

^ .У, чвН(«,«). , 8Н(ш,г) —= + Л / В(ш-и)—+—

о

с односторонним краевым условием по и/ Н(0,£) = РоМ и начальным условием Р{{7(0)=о>о} = 1

Для решения интегро-дифференциального уравнения Такача в стационарном и нестационарном режимах используется известный метод преобразований Лапласа и Стилтьеса Новыми являются следующие результаты для СМО М/М/1 в стационарном режиме найдены функция и плотность распределения, моменты незавершенной работы, доказано существование и единственность стационарного режима по незавершенной работе, показана эргодичность нестационарного решения интегро-дифференциального уравнения Такача Глубокое и полное исследование незавершенной работы в классической СМО необходимо для последующего анализа незавершенной работы в ДС СМО

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

Четвертая часть содержит 4 главы В 12-й главе исследуется стационарное распределение числа заявок в СМО с бесконечным накопителем и ДС пуассоновским входным потоком с диффузионной интен-

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

(43)

Стационарные характеристики числа заявок в системе дк(х), к^О, удовлетворяют краевой задаче (12), (13), (15), (16), которая для краткости в работе называется 1-й моделью рассматриваемой ДС СМО Для удобства анализа в 12-й главе выполняется переход ко 2-й модели, краевой задаче (21), (22), (24) с неоднородными уравнениями (21), (22) Для решения данной краевой задачи предлагается метод производящих функций с вариацией правой части Вводится расширение краевой задачи (21), (22), (24) при к<0 и производящая функция в виде ряда Лорана Р(х,г): 00

Р(х,г) = £ 9к{х)гк, *€С, (44)

к=—оо

где дк(х), к^—1, дополнительные неизвестные функции

В работе показано существование и единственность решения полученной краевой задачи для Р(х,х) в области 0,1,хг и найдено это решение, разрешенное относительно неизвестной функции Т(х) 00

*•(*,*)= дк(Г(х))гк, ге{с\0} (45)

к=—оо

Из подстановки до(х), д\ (х) в уравнение (21) следует интегральное уравнение Фредгольма 1-го рода относительно неизвестной функции Т(ж) При условии выполнения условия отсутствия перегрузок (43) в работе показано с применением разработанных методов и численного анализа существование и единственность решения уравнения относительно Т(х), нестационарных и стационарных характеристик, эргодичность СМО

В 13-й главе исследуется стационарное распределение числа заявок в СМО с бесконечным накопителем и ДС пуассоновским входным потоком заявок со скачкообразной интенсивностью такого же типа, как в 5-й и 8-й главах Предполагается выполнение условия отсутствия перегрузок в стационарном режиме (43). Стационарные характеристики числа заявок дй(а;), к^О, удовлетворяют бесконечной системе разностно-интегральных уравнений (30), (31), (33), которая для краткости в работе называется 1-й моделью рассматриваемой ДС СМО. Для удобства анализа в 13-й главе выполняется переход ко 2-й модели, к системе разностно-интегральных уравнений (34), (35) Для решения системы (34), (35) вводятся производящие функции Р(х,г) и д(г):

РМ = Е„>02пА«(®). З(г) = ¡^(у^ёу.

Производящая функция Р(х,г) удовлетворяет интегральному уравнению Фредгольма 2-го рода с вырожденным ядром

Е{х,г)[хг2 — (х + ц + а)г+ц\ + агФР(х,г) = цдо(х) — xzf{x) (46) В работе показано существование, единственность, аналитичность и рациональность решения интегрального уравнения (46) в области Пг.жг и найдено это решение Коэффициенты степенного ряда дп{х) выражены через неизвестную функцию до(х) Из подстановки до(х), дг{х) в уравнение (34) следует интегральное уравнение Фредгольма 2-го рода относительно неизвестной функции до(х) ь

А(х)д0(х) = 1 К(х,у)до(у)*у + У(х) (47)

а

Показано, что в условиях отсутствия перегрузок в СМО (43) для интервала значений 0 < /) < (Ь) интегральное уравнение (47) обращается в тождество; для интервала значений (а) интегральное уравнение (47) не имеет решений; для интервала значений г\(а) <р<1 в работе показано с применением разработанных методов и численного анализа существование и единственность решения интегрального уравнения (47) относительно до{х), нестационарных и стационарных характеристик, эргодичность СМО

В 14-й главе исследуется стационарное распределение незавершенной работы и (¿) в ДС СМО с бесконечным накопителем и ДС пуассо-новским входным потоком заявок со скачкообразной интенсивностью такого же типа, как в главах 5,8,13 Рассматриваются ДС СМО с одним прибором типа М/М/1 с экспоненциальным обслуживанием интенсивности /х, а также ДС СМО типа М/С/1 с произвольным законом обслуживания В (х) Приводится вывод интегро-дифференциальных уравнений типа Такача относительно незавершенной работы в нестационарном и стационарном режимах Нестационарная функция распределения Н(ц>,£,а;) удовлетворяет интегро-дифференциальному уравнению типа Такача следующего вида

ли

-(а + г)Н(и;,г,а;) + а; / В(со-з)Н'3(8,г,х)(18 + 'Н.'ш(ш,Ъх)+ Jo

+аФЩш^,х)-~Н.'г(ш,Ь,х),ш>0, (48)

с односторонним краевым условием по и Н(0,£,х) — (¿о^,!) и начальным условием Р{И7(0)=а>о} = 1 Стационарная функция распределения Ь(сс1,ж) удовлетворяет интегро-дифференциальному уравнению типа Такача следующего вида

ГШ

—(а + х)Ъ{и),х)+х / В(ш — я)Ь'8(5,х)с?5 + Ь^(а;,а;)-|-3 о

+аФЬ(о;,а;) = О, о; > О, (49)

с односторонним краевым условием по и Ъ.(0,х)=до(х)

В работе найдено решение интегро-дифференциального уравнения типа Такача с применением преобразований Лапласа и Стилтьеса я получены моменты незавершенной работы в стационарном режиме, доказано существование и единственность стационарного режима по незавершенной работе

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

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

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

— апробации численных методов и верификации полученных результатов путем сравнения полученных характеристик различными численными методами и определения точности полученных результатов,

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

Расчеты проводились для каждой главы согласно разработанным методам, приведенным в каждой главе По результатам расчетов

оформлено 218 рисунков графиков функций и приведено подробное описание численного анализа для глав 3, 7, 8, 12-14 Составлены программы на языке FORTRAN Visual Workbench v 1.00 для расчета вероятностных характеристик СМО и автоматического вывода результатов расчетов на графики функций в системе ЖЦцХ

В численном анализе исследовались моменты числа заявок M(t),D(t) — среднее значение и дисперсия числа заявок в СМО в момент времени t, Mi/, Dv — среднее и дисперсия числа заявок v в стационарном режиме СМО, M(a;) = ^n^0ng„(x)/da;, = Mv)2qn{x)/dx —

плотность распределения среднего и дисперсии числа заявок по интенсивности Л в стационарном режиме

Рис 4 Плотности распределения числа заявок

При проведении численного анализа исследуемых СМО ставились задачи 1) разработка численных методов расчета распределений числа заявок- Pk(t), Qk(t,x), qk(x), моментов числа заявок в СМО M(t), D(í), М(ж), D(a;), Mi/, Di/, моментов незавершенной работы ME/,DÍ/, 2) наблюдение в исследуемых СМО при различных входных данных указанных вероятностных характеристик СМО и процесса стабилизации, а также точности стабилизации нестационарных характеристик к стационарным, 3) наблюдение за неотрицательностью вероятностных характеристик СМО (наблюдался минимум вероятностных характеристик СМО — mm), 4) сравнение характеристик рассматриваемой СМО и аналогичной классической СМО с усредненной интенсивностью входного потока А = J^(x/¡j,)f(x)dx, имеющей моменты числа заявок Мси и Oev

Численный анализ показал неотрицательность вероятностных характеристик. Пример графиков плотностей qk{x) для ДС СМО с беско-

нечным накопителем, диффузионной интенсивностью входного потока с нулевым коэффициентом сноса а — 0 приведен на рис 4

Рис 5 Стационарные моменты числа заявок

Для описания численных экспериментов в работе введены понятия, которые для краткости названы опорным планом и сечением опорного плана, проводились численные расчеты, и результаты отражались на графиках зависимостей характеристик СМО от входных данных В работе под опорным планом понимается фиксированный набор входных данных, при котором существуют и неотрицательны характеристики числа заявок Например, для СМО типа M/M/1/Nq со скачкообразной интенсивностью входного потока A(i) рассматривался опорный план Ц — В, а = 0 5, 6=1 5, а = 1, N = 4, е = 10~6 и равномерное распределение <р(х), где е — точность вычисления интегралов Сечение по параметру £ — это наборы входных параметров, отличающиеся друг от друга только параметром остальные параметры неизменны и взяты из опорного плана Для сравнения моментов числа заявок рассматриваемой СМО Mi/ и Df с моментами классической СМО Мcv и Dci/ наблюдались относительные отклонения среднего числа заявок е0(Мг/) = |(Mi/ — Mcz/)/Mt/| 100% и дисперсии числа заявок e0(Di/) = j(Df — Dcv)/Qu\ 100% Для опорного плана строились графики функций, зависящих от переменных (t), (t,x) В сечениях для числа заявок строились графики следующих величин: mm, Mv, Dz/, e0(Mi/), £0(Dz/), для незавершенной работы строились графики Mi/, DU

В работе дана интерпретация изменений вероятностных характеристик СМО в зависимости от от параметров СМО

Например, на рис 5 показаны изменения среднего и дисперсии числа заявок Mv, Du в ДС СМО с конечным накопителем, диффузион-

ной интенсивностью входного потока с нулевым коэффициентом сноса а = 0 в зависимости от интенсивности обслуживания /х На рис 5 мат ожидание и дисперсия числа заявок уменьшаются с увеличением (л, Действительно, при увеличении интенсивности обслуживания ¡х заявки быстрее обслуживаются и покидают СМО, поэтому среднее число заявок, как и дисперсия, уменьшается

е0(%)

£о(0г/) ер(М1/)

0.0 03060912 15 а

0 3 6 9 12 15

а

Рис 6 Относительные отклонения моментов

На рис 6 приведены изменения относительных отклонений е0(Ми) и еа{0^) для ДС СМО с конечным накопителем, скачкообразной интенсивностью входного потока в зависимости от а,а При стягивании отрезка [о, 6] (левый рисунок) в точку, характеристики СМО приближаются к характеристикам СМО с постоянной интенсивностью входного потока А — а = Ь, при увеличении а Н> оо (правый рисунок) характеристики СМО стабилизируются, что соответствует предельным результатам

Для ДС СМО с бесконечным накопителем численный расчет нестационарного распределения числа заявок проводился с применением метода Эйлера для решения задачи Коши относительно производящей функции. Например, для ДС СМО типа М/М/1 с бесконечным накопителем с диффузионной интенсивностью входного потока производящая функция = удовлетворят уравнению

хг2 — (х + ц) + [1

+ &1%х(Ьх,г) = гЩЬх,2) + (1 •

и соответствующим начальным и краевым условиям Указанная задача Коши решалась с применением метода Эйлера относительно производящей функции Я(Ь,х,г) На каждом шаге по £ плотности находились по формуле обратного преобразования Лорана

1 2жг

1«1=Р

Предложенный метод для краткости в работе называется методом Эйлера-Лорана Для всех исследуемых СМО с применением метода Эйлера-Лорана показана стабилизация нестационарного решения к стационарному и независимость стационарного решения от начальных условий На рис 7 приведен пример стабилизации нестационарных вероятностей Рк (¿) к стационарным вероятностям рк для ДС СМО с бесконечным накопителем, скачкообразной интенсивностью

1 08 06 0.4 02 0 -

Рп{Ь)

РоЮ

0.2 0 16 0.12 0.08 0 04 -- 0 -

т) ЙЙ

0 3 6 9 12 15

0 3 6 9 12 15

Рис 7 Стабилизация нестационарных вероятностей Рк(Ь)

В заключении диссертационной работы приводятся основные результаты исследований, научно-технические рекомендации для применения моделей систем массового обслуживания в ИС, а также рекомендации к модернизации программного и аппаратного обеспечения ИС ТГЭУ

В работе показывается метод прогнозирования состояния ИС на примере администрирования предоставлением пользователям ресурсов Интернет. Запросы внешних пользователей из Интернет к ресурсам ИС серверов- библиотечного сервера, ргоху-сервера, \уеЬ-сервера, а также запросы внутренних пользователей к ресурсам Интернет создают общую нагрузку на выделенный канал связи в Интернет, который обладает заданной пропускной способностью К Кбит/с Пропускная способность К представляет собой максимальное количество килобит в секунду, которое может пропустить выделенный канал, и определяется по договору администрации ИС с провайдером, обеспечивающим доступ в Интернет Ежемесячная оплата 8пеЬ администрации ИС услуг

провайдера зависит от объема трафика информации Уш/, проходящей через выделенный канал связи в Интернет и стоимости единицы трафика С (К), которая является функцией от пропускной способности К

где — объем в байтах г-го сообщения на ^-м сервере, у3 — число сообщений, проходящих через ]-й сервер, таег — количество серверов Величины Уг<} наблюдаются в результате мониторинга ИС, функциональная зависимость С (К) определяется провайдером сети, методы и примеры вычисления среднего числа сообщений Мг^ приводятся в данной работе

Если заказана высокая пропускная способность К, а сеть простаивает, те велика вероятность простоя сети р0, то администрация ИС несет неоправданно высокие затраты и, следовательно, затраты на ресурсы ИС необходимо понижать Если заказана невысокая пропускная способность К, а сеть перегружена, время ожидания пользователями начала обслуживания 17 велико (обслуживание пользователей тормозится), то пользователи ИС несут неоправданно высокие потери при низких затратах на ресурсы ИС Зпе1, и, следовательно, затраты на ресурсы ИС необходимо повышать

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

На основе мониторинга ИС и результатов исследования моделей СМО ИС в работе даны конкретные рекомендации к модернизации программного обеспечения и оборудования ИС в ТГЭУ

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

Рекомендации к модернизации оборудования ИС Анализ информа-

(50)

ционных потоков ИС с применением моделей СМО показал необходимость модернизации ИС по следующим направлениям- а) выделение службы DNS и программного обеспечения ДОТ на отдельных серверах; Ъ) замена концентратора внешней сети маршрутизатором Аналогичный анализ показал перспективные направления модернизации ИС а) построение дополнительных выделенных каналов ADSL, а также создание оптоволоконного или спутникового выделенного канала связи; Ъ) повышение производительности серверов и коммутаторов путем замены на более производительное оборудование, с) подключение новых Интернет-сервисов ТГЭУ к отдельным выделенным каналам связи

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

Список основных публикаций по теме диссертации

1 Головко Н И, Катрахов В В Анализ систем массового обслуживания, функционирующих в случайной среде — Владивосток. Изд-во ДВГАЭУ, 2000 - 144 с

2 Катрахов В В , Головко Н И, Рыжков Д Е Введение в теорию марковских дважды стохастических систем массового обслуживания - Владивосток. Изд-во ДВГУ, 2005. - 212 с

3 Головко И И, Коротаев И А Время задержки сообщения в узле сети при переменной интенсивности входящего потока // Автоматика и вычислительная техника - 1989 - №2 - С 36-39

4. Головко Н.И, Коротаев И А. Системы массового обслуживания со случайно изменяющейся интенсивностью входящего потока // Автоматика и телемеханика - 1990 - №7. - С 80-85

5 Головко Н Н, Коротаев И А Расчет характеристик нестационарных систем массового обслуживания // Автоматика и телемеханика - 1991. - №2 - С 97-102

6 Головко НИ., Филинова НА Матричный анализ систем массового обслуживания с конечным накопителем при скачкообразной интенсивности входного потока // Автоматика и телемеханика - 2000 -№9 - С 73-83

7 Головко Н И, Катрахов В В , Писаренко Т А Краевые задачи в стационарных системах массового обслуживания с диффузионной интенсивностью входного потока // Дифференциальные уравнения -2002 - №3 - С 305-312

8. Головко Н И, Катрахов В В Нестационарное распределение числа заявок в марковских системах обслуживания // Дальневост мат. журн.-2004 -№2 - С 211-217

9 Головко Н.И Расчет характеристик многолинейной СМО в диффузионном приближении при медленно флуктуирующем входном потоке // Поиск сигнала в многоканальных системах. - Томск Изд-во ТГУ, 1985 - №1. - С 5-13

10 Головко Н И Распределения числа заявок в марковской нестационарной СМО // Управляемые системы массового обслуживания -Томск Изд-во ТГУ, 1986 - №4 - С. 22-27

11 Головко НИ, Коротаев И А Анализ некоторых систем массового обслуживания с переменной интенсивностью входящего потока // Поиск сигнала в многоканальных системах - Томск Изд-во ТГУ, 1987 - №2 - С 65-76.

12 Головко Н И. Матричный анализ систем массового обслуживания с конечным накопителем при скачкообразной интенсивности входного потока [текст] - Деп. ВИНИТИ №2296-В93 - Владивосток, 1993. -16 с

13 Головко НИ, Катрахов В.В, Филинова Н.А Марковские системы обслуживания с конечным накопителем при скачкообразной интенсивности входного потока // Вестник ДВГАЭУ - Владивосток* Изд-во ДВГАЭУ. 1999, - №11 - 6 с

14 Головко Н.И, Катрахов В.В, Филинова Н А Марковские системы обслуживания с бесконечным накопителем при скачкообразной интенсивности входного потока // Вестник ДВГАЭУ Владивосток Изд-во ДВГАЭУ, - 2000, - №1 - 6 с

15. Головко Н И, Катрахов В.В, Филинова Н А Незавершенная работа в системах обслуживания с бесконечным накопителем при скачкообразной интенсивности входного потока // Вестник ДВГАЭУ - Владивосток: Изд-во ДВГАЭУ, 2000 - №2. - 6 с

16 Головко Н.И, Катрахов ВВ., Писаренко Т.А. Стационарные системы массового обслуживания с диффузионной интенсивностью входного потока. Препр / ИПМ ДВО РАН - Владивосток Дальна-ука, 1999 - №11 - 25 с

17 Головко НИ, Катрахов В В, Писаренко ТА. Стационарные системы массового обслуживания с диффузионной интенсивностью входного потока с ненулевым коэффициентом сноса. Препр / ИПМ ДВО РАН - Владивосток Дальнаука, 1999 - №12 - 18 с.

18 Головко Н И, Катрахов В В , Кучер Н А Стационарные системы массового обслуживания с конечным накопителем при скачкообразной интенсивности входного потока Препр / ИПМ ДВО РАН -Владивосток Дальнаука, 1999 - №19. - 20 с.

19 Головко Н.И, Катрахов В В, Кучер НА Стационарные системы массового обслуживания с бесконечным накопителем при скачкообразной интенсивности входного потока Препр / ИПМ ДВО РАН -Владивосток Дальнаука, 1999 - №20 - 20 с

20 Головко НИ, Катрахов В.В, Кучер Н.А Матричный метод анализа стационарной модели системы массового обслуживания при скачкообразной интенсивности входного потока Препр / ИПМ ДВО-РАН - Владивосток Дальнаука, 2001 - №5. - 20 с.

21 Головко Н.И, Катрахов В В О нестационарных марковских системах обслуживания. Препр / ИПМ ДВО РАН. - Владивосток. Дальнаука, 2004. - №20. - 15 с.

22 Головко Н.И., Катрахов В.В, Свителик Е А Стационарное распределение числа заявок в системах обслуживания с бесконечным накопителем при диффузионной интенсивности входного потока Препр / ИПМ ДВО РАН - Владивосток Дальнаука, 2004. - №21 - 28 с

23 Головко НИ, Катрахов В В, Свителик Е А. О времени ожидания в системах обслуживания с бесконечным накопителем при диффузионной интенсивности входного потока Препр / ИПМ ДВО РАН - Владивосток Дальнаука, 2004 - №22 - 23 с

24. Головко Н И, Катрахов В В Стационарное распределение числа заявок в системах обслуживания с бесконечным накопителем при скачкообразной интенсивности вход-ного потока Препр. / ИПМ ДВО РАН. - Владивосток Дальнаука, 2004 - №23 - 18 с

25 Головко НИ., Катрахов В В О времени ожидания в системах обслуживания с бесконечным накопителем при скачкообразной интенсивности входного потока Препр / ИПМ ДВО РАН - Владивосток Дальнаука, 2004. - №24 - 16 с

26 Катрахов В В, Головко Н И, Рыжков ДЕ О системе обслуживания с конечным накопителем при скачкообразной интенсивности входного потока Препр / ИПМ ДВО РАН - Владивосток Дальнаука, 2005 - №9. - 27 с

Головко Николай Иванович

ИССЛЕДОВАНИЕ МОДЕЛЕЙ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ В ИНФОРМАЦИОННЫХ СЕТЯХ

Автореферат

Подписано в печать 16 07 07 Формат 60x84/16 Уел п л 2,09 Уч -изд л 2,5 Тираж 120 экз Заказ 127

Издательство Тихоокеанского государственного экономического университета Участок оперативной полиграфии 690091, Океанский пр-т, 19.

71 08-5/130

ТИХООКЕАНСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ

УНИВЕРСИТЕТ

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

ГОЛОВКО НИКОЛАИ ИВАНОВИЧ

ИССЛЕДОВАНИЕ МОДЕЛЕЙ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ В ИНФОРМАЦИОННЫХ СЕТЯХ

Специальность 05.13.18 - математическое моделирование, численные

методы и комплексы программ

Диссертация на соискание ученой степзш; доктора технических наук

Научный консультант:

доктор физико-математических наук,

профессор Катрахов В.В.

Владивосток 2007

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

ПК — персональный компьютер;

СПД — сеть передачи данных;

JIC (LAN) — локальная сеть (Local Area Networks);

WAN — глобальная сеть (Wide Area Networks);

MAN — городская сеть (или сеть мегаполисов) (Area Networks) ;

ОС — операционная система;

Интернет — всемирная компьютерная сеть;

ИС — информационная компьютерная сеть (классификацию ИС см. в главе 1);

ISO (International Standard Organization) — Международная организация по стандартизации;

OSI (Open System Interconnection) Ref.Model — стандарты процедур межсетевого взаимодействия, разработанные организацией International Standard Organization (ISO). Эти стандарты получили название "Семиуровневой модели сетевого обмена"или в английском варианте "Open System Interconnection Reference Model";

TCP/IP — стандарты передачи данных в Интернет (Transmission Control Protocol/ Internet Protocol) (описание стандартов приведено в главе 2);

WWW —- служба размещения ресурсов в Интернет (World Wide Web - Всемирная паутина);

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

web-адрес — уникальное доменное имя из нескольких слов (сочетаний символов), разделенных точками, например: www.bigcorp.com;

URL-адрес — путь на сервере к каталогу или файлу, например: /info/abi/spec.html или /info/abi/;

ргоху-сервер — сервер, обеспечивающий связь пользователей JIC с Интернет;

web сервер — сервер, предоставляющий информационные ресурсы в Интернет;

ADSL — асимметричная цифровая абонентская линия (Asymmetric Digital Subscriber Line);

провайдер — фирма, предоставляющая услуги подключения JIC к Интернет;

ЭВМ — электронная вычислительная машина;

СМО — система массового обслуживания;

М/М/1, M/M/m/No — обозначения Кендалла для СМО с пуассоновским входным потоком заявок и экспоненциальным обслуживанием, постоянными интенсивностями входного потока и обслуживания, на m приборах с бесконечным и конечным накопителем емкости Nq, соответственно;

¡j, — интенсивность экспоненциального обслуживания;

¡j,(t) — интенсивность нестационарного экспоненциального обслуживания;

A (t) — интенсивность входного пуассоновского потока в момент времени Ц

M(t)/M(t)/1, M(t)/M(t)/l/No — обозначения Кендалла для СМО с нестационарным пуассоновским входным потоком заявок с детерминированной интенсивностью A (t) и нестационарным экспоненциальным обслуживанием с интенсивностью ¡i(t) с бесконечным и конечным накопителем емкости No, соответственно;

ДС — дважды стохастический(ая) ;

ДС ПП — дважды стохастический пуассоновский поток заявок; ДС СМО — дважды стохастическая система массового обслуживания; [a, b] — интервал значений скачкообразной интенсивности входного ДС пуассоновского потока A(i) (в гл. 5,8,13,14);

Т — интервал постоянства скачкообразной интенсивности Л [t)\

а — параметр экспоненциального распределения интервала постоянства скачкообразной интенсивности A(t) (в гл. 5,8,13,14);

(р(х\у) — условная плотность распределения скачкообразной интенсивности A (t) в точках разрыва;

[а, ß] — интервал значений диффузионной интенсивности A (t) входного ДС пуассоновского потока (в гл. 4,6,7,12);

а — коэффициент сноса диффузионной интенсивности A (t) входного ДС пуассоновского потока (в гл. 4,6,7,12);

b — коэффициент диффузии диффузионной интенсивности A (t) входного ДС пуассоновского потока (в гл. 4,6,7,12);

No — емкость накопителя СМО; N = iVo+1 — максимальное число заявок в СМО; v{t) - число заявок в СМО в момент времени i;

Pk{t) = РЩ^) == к, 0 ^ к ^ N} — нестационарное распределение числа заявок в СМО в момент времени t\

V — процесс u(t) в стационарном режиме;

Рк = P{v = к, 0 к ^ N} — стационарное распределение числа заявок в СМО; M(t),D(t) — среднее значение и дисперсия числа заявок в СМО в момент времени i; f(t,x) = Р{х < A(i) < x+dx}/dx — нестационарная плотность интенсивности входного ДС потока A(i);

Л — процесс A(і) в стационарном режиме;

f(x) = Р{ж < Л < x+dx}/dx — стационарная плотность A(i);

Qk(t,x) = P{v(t) = к, X < A [t) < x+dx} j dx, 0 ^ к ^ N, — совместное нестационарное распределение числа заявок v(t) и интенсивности A (t) входного потока (нестационарные характеристики числа заявок) ;

и — число заявок в стационарном режиме;

1к{х) = — X < X < x + dx}/dx, 0 ^k^N, — совместное стационарное распределение

числа заявок и и интенсивности А входного потока в стационарном режиме (стационарные

характеристики числа заявок);

Mv = Y^ крк — стационарное среднее числа заявок v в СМО в стационарном режиме; к^ 1

DV = ^ (/с — Mv)2pk — стационарная дисперсия числа заявок и в СМО; fcjïi

M (ж) = = n,dx < X < х + dx}/dx = ^ nqn(x) — плотность распределения

О п^О

среднего числа заявок по интенсивности А в стационарном режиме;

= {n — Mu)2P{v = n, dx < X < х + dx}/dx = (п ~ Mz/)2çn(a;) — плотность

распределения дисперсии числа заявок по интенсивности А в стационарном режиме; U(t) — незавершенная работа СМО в момент времени і;

H(w,i) = P{U(t) ^ w} — нестационарная функция распределения незавершенной работы; h(w) = P{U ^ ш} стационарная функция распределения незавершенной работы U в стационарном режиме;

5(ш) — дельта-функция Дирака.

4

Для краткости функции Qk{t, х), 0 ^ к ^ N, в дальнейшем будем называть нестационарными характеристиками числа заявок, а функции qk{x), 0 ^ к ^ N, стационарными характеристиками числа заявок. Согласно определению стационарного режима, в стационарном режиме СМО характеристики СМО не меняются с течением времени, то есть х) = 0, 0 ^ к ^ N.

В стационарный режим СМО может перейти различными способами. В частности, если в качестве начального распределения числа заявок в СМО задано стационарное распределение числа заявок <2^(0,х) — дь(х), 0 ^ к ^ N, то Vi ^ 0 будет выполняться Qk{t,x) = Як(х)-> 0 ^ к ^ N. В другом случае, при произвольном начальном распределении числа заявок СМО может перейти в стационарный режим при t —> сю. В этом случае в качестве qk{x) можно рассматривать пределы qk{x) = lim Qk(t,x), 0 ^ к ^ N, существование и единственность

t—>оо

которых для рассматриваемых СМО показано в работе. Если указанные пределы для qk(x), 0 ^ к < N, существуют, единственны и не зависят от начального распределения числа заявок, то случайные процессы: число заявок v{t) в СМО и интенсивность входного потока А(t) являются эргодичными, а СМО с таким свойством - эргодичной. В работе показана эргодичность

ь

рассматриваемых СМО. Заметим, что интегралы f q^ (х) dx = р^, 0 ^ к ^ N, представля-

0,

ют собой стационарное распределение числа заявок, удовлетворяющее условию нормировки N ь

pk = 1, а интегралы / Qk{t,x) dx = -Pfc(i), 0 ^ к ^ N, представляют собой нестационарное к=О а

распределение числа заявок, удовлетворяющее условию нормировки ~

ВВЕДЕНИЕ

Актуальность проблемы. Новейшие достижения в области микроэлектроники привели к новым концепциям в организации информационных служб. Благодаря высокопроизводительным и экономичным микропроцессорам информационно-вычислительные ресурсы приближаются к рабочим местам менеджеров, бухгалтеров, плановиков, администраторов, инженеров и других категорий работников. Совершенствуются персональные системы обработки данных, автоматизированные рабочие места на базе персональных компьютеров (ПК). На этой основе с 80-х годов наметилась тенденция развития вычислительной техники — создание локальных сетей (ЛС) различного назначения. Наличие в учреждении и офисах ЛС создает для ее пользователей новые возможности интегрального характера, благодаря прикладным программам и другому документообороту. Образуется автоматизированный документооборот, создаются различные массивы управленческой, коммерческой и другой информации общего назначения. Вместе с тем, параллельно наблюдалось создание общедоступных сетей передачи данных, например, А11РАКЕТ,БИЗЛИНК, ГЕОНЕТ, ГЛАСНЕТ, ИАСНЕТ, ИНФОКОМ, ИНФОРМСЕТЬ, ИНТЕРЛИНК, ИСТОК-К, МЭБ,МФДи МИБ, МИР, РЕЛКОМ, ЭОУАМ ТЕЬЕРОШГ, спринт-сеть и т.д. [70, 92]. В дальнейшем наметилась тенденция к объединению всех сетей в единую мировую сеть, которая получила название Интернет. Наличие рабочих мест, подключенных не только к локальным ресурсам, но и к мировой базе данных, создало новую ситуацию для администраторов ЛС. Появилась необходимость мобильно реагировать на изменяющиеся запросы пользователей и соответствующим образом "подстраивать"ресурсы ЛС: увеличивать или уменьшать производительности серверных станций, возможно изменять топологию ЛС, создавать дополнительные ресурсы Л С в виде новых маршрутизаторов и т.д.

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

В настоящее время возможности оценки поведения локальной сети в целом достаточно ограничены. Информационная сеть с точки зрения информационных потоков представляет собой непрерывно жужжащий улей, в котором достаточно сложно разобраться и определить внешние характеристики системы в целом: успешно или нет функционирует построенная топология и аппаратная часть сети или она нуждается в некоторой реорганизации. На вход узлов поступают потоки сообщений, в узлах они накапливаются, обрабатываются, затем передаются дальше. Возникает картина некоторой мельницы: на вход что-то поступает, перерабатывается, затем идет дальше. У администраторов сети возникает вопрос хорошо или плохо работает "мельница"? Отдельные фрагментальные показатели, которые дает операционная система, к сожалению, дают только косвенную картину. Для оценки поведения ЛС необходимо иметь модель ЛС в целом. Такую проблему возможно решить при помощи моделирования.

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

вания серверов.

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

При рассмотрении СМО задается ее структура, то есть входной поток, обслуживание, комплекс обслуживающих приборов, емкость накопителя, и дисциплина обслуживания. Входной поток описывается совместной функцией распределения интервалов времени между соседними моментами появлениями заявок г ^ 1, а для ординарных рекуррентных потоков, когда интервалы независимы и одинаково распределены, — функцией распределения А(т) = Р{тг < т, г ^ 1}. Чтобы указать о какой именно СМО идет речь, надо задать функцию распределения интервалов между соседними моментами появлениями заявок, функцию распределения длительности обслуживания, количество обслуживающих приборов и емкость накопителя. В теории массового обслуживания приняты следующие обозначения для классификации СМО:

А/В/тп/Ы,

где А, В обозначают типы функций распределения для входного потока и обслуживания, тп — количество обслуживающих приборов, N — емкость накопителя. Параметры А, В принимают значения из набора {М, О, Нц и др. }, где М — экспоненциальное распределение, б — распределение общего вида, Нц — гиперпоказательное распределение порядка Л.

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

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

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

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

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

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

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

Задачи исследования. Поставленная цель достигается путем решения ряда взаимосвязанных задач диссертационной работы, состоящих в следующем:

— разработка новых методов и средств мониторинга информационных потоков в ИС;

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

— разработка математических моделей СМО в ИС;

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

— разработка рекомендаций по использованию характеристик показателей эффективности функционирования СМО в ИС с целью прогноза состояния ИС.

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