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

ГОСУДАРСТВЕННЫЙ ДОШТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ШСШШ- ОБРАЗОВАНИЮ

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

На правах рукописи УДК ¿19.Ш2

СПИВАК ЛЕВ РОМАНОШЧ СИСТШШ МАССОВОГО ОБСгаИВАНЩ В РЕДКО ИЗМЕНЯЮТСЯ СЛУЧАЙНОЙ СЩЕ

1

Спэциальиость 05.13.01 -Управление в технических системах

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

кандидата технических наук

Томск - 1994

Работа выполнена в Томском государственном университете и Сибирском физико-техническом институте.

Научные руководители: доктор технических наук И.А.Коротаев.

доктор физико-математических иаук А.Терпугов. Официальные оппоненты: доктор технических наук

A.А.Назаров,

кандидат технических наук

B.Д.Теуцеков.

Ведущая организация: Белорусский государственный университет (г.Минск).

Защита состоится " // " 1994 г. к ^ —- часов

на заседании специализированного Совета Д.063.53.03 Томского государственного университета имени В.Б.Куй-бшева (634050, г.Томск, пр.Ленина, 36).

С диссертацией можно ознакомиться в научной библиотеке Томского государственного университета.

Автореферат разослан 19Э4г.

Ученый секретарь снециализ"рованногр Совета, кандидат физике-математических наук, доцент . Б.Е.Трквоженко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Разработка ин$ормационно-вычислителъ-шх сетей, т.е. сетей ЭШ и сетей передачи информации пред-¡тавляет собой в настоящее время одно из основных направлений муки и техники. Математическими моделями сети в целом и её отдельных элементов являются, соответственно, сети и системы мас-ювого обслуживания.

Как правило, в качестве математических моделей узлов сети гагут использоваться стандартные ¿20 типа М/Ы/1/оо , М/М/1//У , 1/5-/1/00 , либо более сложные СМО, учитывающие специфику ре-1льных сетей.

Большинство авторов работ по анализу элементов информаци-шно-вычислительных сетей считают, что рассматриваемые потоки •рафика описываются пуассоновекими процессами.' Это подтверждайся измерениями на реальных сетях и позволяет получить акали-? ■ичес кие результаты в замкнутой форме.

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

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

использование адаптивной маршрутизации, в результате которой ¡а узлах появляются и исче ают потоки сообщений; подключение либо отключение источников информации к сети.

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

Цель работы. При выполнении работы ставилась задача разработать методы анализа СМО со случайно изменяющимися параметрами, а именно:

а) ОЛО, функционирующих в случайной марковской среде;

б) СМО, функционирующих в случайной полумарковской среде.

Методика исследования. Для решения поставленных задач использовались методы теории массового'обслуживания, теории слу- . чайных процессов, теории вероятностейметод асимптотических разложений. Для получения количественных результатов проводились расчёты на ЭШ.

Научная не тона.

I. Предложен метод расчёта характеристик широкого класса .. СМО, функционирующих в случайной среде. Основная идея метода ¿включается г предположении, что состояние среды изменяется ^щгаточно редко, справедливом для реальных систем, рассматри-^^НЕ в качестве элементов и фрагментог: икформационно-Бычис- .

лительных сетей. Это предположение позволяет применить для нахождения ряда характеристик исследуемых СТО метод малого параметра. Искомые характеристики ищутся в виде раэлложения в ряд по малому параметру. Для коэффициентов разложения получены рекуррентные формулы.

2. Вышеописанный метод использован для исследования следующих СМО, функционирующих в случайной марковской среде: М/М/Х/У, М/М/1/ео, М/М////<х> , СМО с параметрами, зависящими от состояния системы, СЮ с интенсивностя&... изменения среды различных порядков малости и М/£/1/<*э . Для СМО с экспоненциальным обслуживанием получены рекуррентные формулы для вычисления коэффициентов разложения в ряд по ма-ому параметру распределения числа заявок в системе, а для М/£у/1/<*> - коэффициентов разложения Лапласа-Стилгьеса от функции распределения виртуального времени ожидания.

3. Рассмотрены (Ж), функционирующие в случайной полумарковской среде: М/М/1Л» , М/М/1/Л'', ОЮ с параметрами, зависящими от состояния системы, и Ы/б- ДЛ*5 . Для СМО с экспоненциальным обслуживанием найдены рекуррентные формулы для вычисления коэффициентов разложения в ряд распределения числа'заявок в системе, а;для СМО типа М/&/1 /со - коэффициентов разложения преобразования Лапласа от функции распределения суммарного объёма заявок в системе.

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

ристик разрабатываемых заказчиками систем обработки информации и систем передачи данных. В рамках хоздоговорной темы "Диагноз-ПТ", выполненной в 19Ю-90Р.г. Томским госуниверситетом для НИИ ССУ (г.Москва), СШ НИИ ССУ (г.Пятигорск), заказчикам были переданы математические модели и методы расчёта, а также комплексы программ, реализующие соответствующие методы. Данные комплексы используптся для расчёта и оптимизации разрабатываемых систем. Акт о внедрении результатов диссертации приведён в приложении.

Публикации. Основные результаты проведённых исследований опубликованы в I печатных работах. Материалы диссертации были также изложены в отчётах по хоздоговорной теме "Диагноз-ПТ".

Апробация работы . Основные положения диссертации и отдельные её результаты докладывались и обсуждались на

- ежегодных зимних Белорусских школах-семинарах по теории массового обслуживания и её приложениям (г.¡Витебск, 1990г., г.Гро; но, 1991г., г.Брест, 1992г.),

- республиканской конференции "Совершенствование метЬдов исследования потоков событий и систем массового обслуживания" (г.Киев, 1989г.), .

- семинаре "Математические методы оптимизации процессов функционирования вычислительных сетей (г.Киев, 1969г.),

- республиканской научно-технической школе-ссминаре "Анализ и синтез систем массового обслуживания и сетей ЭЕМ" (г.Одесса, 1990?.),

- Всесоюзной научно-технической конференции "Распределенные микропроцессорные управляющие системы и локальные вычислительные сети" (г.Томск, 1991г.).

' - 7 -

Структура и объём работы. Диссертация состоит из введения, трёх глав, заключения, списка литературы, содержащего 96 наименований, приложения. Содержание диссертации изложено на 122 страницах машинописного текста.

(ЗДЕШНИЕ РАБОТЫ

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

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

В §1.1 рассматривается система типа М/М/1/оо . Входящий поток в системе является пуассоновским с интенсивностью Х(1) причём есть кусочно-постоянный марковский процесс с. •

конечным числом состояний [ А/, .. . Ал] . X (X.) сохраняет постоянное значение А[ в течение некоторого промежутка времени Т[ »после чего скачкообразно изменяет своё значение. ка А^ с вероятностью ^ ¿у , причём

77 есть случайная величина, распределённая по экспоненциальному закону с параметром о1* ..

Такой поток в литературе чаще всего именуется пуассоновским потоком на цепи Маркова или пуассоновским потоком в случайной марковской среде.

Время обслуживания распределено по экспоненциально^ закона с параметром ^ . -

Обозначим Р(_ (J) стационарную вероятность того, что в системе J заявок и значение интенсивности входящего потока равно A¿ . Вероятности Рс отвечают системе

уравнений:

' А, Я (¡-о - Ч*; +/* Ш+

<

¿> Та

и условию нормировки:

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

Малый параметр £ вводим следующим образом:

о1 г. .= <¿1 £, I» Будем искать ) в виде

Ш-гР/Ж-

Подставляя это разложение в исходную систему и приравни-!ая коэффициенты при одинаковых степенях С , получаем системы однородных (при Л =0) и неоднородных (при Л > 0) разносных уравнений, решения которых «меют вид

п Н), , -Л; / « * /

* / / // '

це - ^с/у* - загрузка системы,

^ , £ = 7 - стационарные вероятности того, что качение интенсивности входящего потока равно Д , ко-эрые удовлетворяют системе

£ Ь - 1

(и _ Л1«;

Для коэффициентов С и найдены ра-

рхс.нтше по \ формулы.

- 10 -

Кроме того, определены условия применимости дак^ого метода. Для этого необходимо выполнение неравенства

. (¿1 ■ пых Т~, < / Ц-г)/ 14,п -Р1

в некоторой окрестности точки 1 « 0.

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

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

б(х) - Р['1 <х] • : :

где ^ - длительность обслуживания.

Рассматриваем виртуальное время ожидания ) • т,е-

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

Обозначим

-и -

I. функцию распределения виртуального времени ожидания

I м'О-^с ■

Задача решена с точностью до преобразований Лапласа-[лтьеса от (-х,, t) . которые ищутся также в

1е разложения в ряд П" малому параметру. Для коэффициентов ¡ложения получены рекуррентные формулы.

Кроме того, найдены среднее и дисперсия виртуального вреда ожидания.

Вторая глава посвящена системам массового обслуживания, [кционирующим в полумарковской случайной средз. Как известно-, ювиым отличием полумарковского процесса от марковского яв- ->тся то, что распределение времени пребывания последнего в -ом -остоянии может быть произвольны;.!. Это приводит к пробам значительно более общего вида, т.е. класс, полумаркоз-IX процессов включает в себя, класс марковских процессов.

Как и ранее, предполагается, что состояние среды измеия-:я редко, т.'е. средние длительности пребывания процесса в Ф,см состоянии имзют порядок I/С , где £. - малый' параметр.

В § 2.1 рассматривается система МД1/1/оо в полумарков-)й случайной среде. Пусть ■- полумарковский слу-

}ный процесс с множеством состояний /1,2,... л], ¿("£) ~ тело заявок в системе в момент £ и ^ (СJ ~ время момента £ до следующего изменения состояний процесса ^ Обозначим (j,x¡ () вероятность того,, что

Пусть

ПО-'}

ищется в виде разложения в ряд по ма-

лому параметру и для коэффициентов разложения получены рекуррентные формулы.

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

В четвёртом параграфе рассматривается система типа М/6-/1Д» Пусть ^ (?) ~ управляющий полумаркоъокий проце-с. Если в момент t (Ь) ~ I то входящий поток - пуассо-

новский с параметром А; , заявки обслуживаются с постоянной скоростью . Обозначим ^(Ь) суммарную длину заявок, находящихся в системе в момент - время от момен-

та до следующего скачка процесса ^•• Отметим, что при постоянной скорости обслуживания суммарная длина заявок совпадает с виртуальным временем ожидания системы

Пусть р- (х,^, Ь) - функция ра^лределения для

суммарной длины заявок, т.е.

которое ищется также в виде разложения в ряд по малому параметру.. Для коэффициентов разложения найдены рекуррентные формулы.

Третья "глава посвящена применению методов, изложенных в диссертации, к решению конкретных технических задач.

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

в (хф с) - РПШч,ум<р> т;<х/

Рассматривается преобразование Лапласа от

ток информации типа голос/данные. Достаточно адекватной моделью потока такого типа является пуасоновскэй поток со случайно изменяющейся интенсивностью.

Отдельно рассматривался случай, когд» у ОТО в случайной среде изменяется лить интенсивность входящего потока, а параметры обслуживания остаются неизменными. Расчётные формулы были реализованы в виде программы на языке Си для ЭШ типа 1Ш РС. Программа производит расчёт следующих характеристик Ш):

- первые Ш значений распределения числа заявок в системе {т задается в программе);

- средняя длина очереди;

- среднее время ожидания -

для систем типа МД1/1/« , М/й/1/У , МД1/Л /со и Ц/а/п/// , функционирующих в случайной марковской среде.

"рограмма работает в диалоговом режиме. Полученные данные выводятся на экран дисплея и на печать.

Вышеописанные программы использовались для расчёта характеристик системы обработки•информации, так называемой "аппаратной управления" в рамках хоздоговорной темы "Разработка математических методов расчёта характеристик элементов и фрагментов АСУС в нестационарных условиях" (шифр "Диагяоз-ПТ"). Использование программ позволило избежать трудоёмкого имитационного моделирования. ...

Во втором параграфе третьей главы проводится анализ полученных результатов, на примере которых прослеживается'ряд закономерностей и зависимостей псведения системы от исходных параметров (иктенсивностей входящего потека и обслуживания, а тах*е изменения случайной среды). Численные примеры приведены в виде, таблиц.

- 14 -

В Заключении формулируются основные результаты и шкоды работы.

В Приложение включён акт о внедрении результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. С помощью метода малого параметра были исследованы еле дущие СМО, функционирующие ¿случайной марковской среде: . ЫД!/1/оо , М/М/1//^ \&/И/А//оо , СМО с параметрами, зависящими, от состояния системы, СМ- с иятенсивностями изменения среда различных порядков малости и Ш/С/1/оа . Получены рекуррентные формулы для вычисления коэффициентов разложения в ряд по малом параметру распределения числа заявок в системе для СМО с экспо кекциальным обслуживанием и коэффициентов разложения преобразо вания Лапласа-Стилтьеса от функции распределения виртуального времени ожидания для СМО типа М/£/1/оо.

3. Из систем, функционирующих в случайной полумарковской среде, были проанализированы следующие:

ШП/оо , М/М/1/И/, СМО с параметрами, зависящими от состояна ' системы, и М/&/1/оа ; Для систем с экспоненциальны}.) обслужива тем были получены рекуррентные формулы для нахождения коэффи-

цйентов разложения функции распределения числа заявок, а для системы M/G-/I/oo - преобразования Лапласе от функции распределения суммарного объёма заявок в системе.

4. Рассмотрено применение метода расчёта характеристик СМО в случайной среде, описанного в первых главах. На основе расчётных формул были написаны программы для ЗШ. Проводится анализ численных результатов, на примере которых прослеживается ряд закономерностей и зависимостей поведения системы от исходных параметров (интенсивностей входящего потока и обслуживания, а Tt.jfte изменения случайной среду).

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНО В СВЕДУЩИХ РАБОТАХ:

1. Коротаев И.А., Сиивак Л.Р. Расчёт характеристик СМО с входящим потоком переменной интенсивности // Техника средств связи, серия СС, 1989. Вып.7, C.I9-25.

2.Коротаев И.Д., Сиивак Л.Р. 'Расчёт характеристик системы массового обслуживания с входящим MC-потоком // Совершенствование методов исследования потоков событий и систем массового обслуживания. (тезисы докладов). Томск: Изд-вс Т1У, 1939. С.НО.

3.Коротаев И.А., Сливак Л.Р. Системы"массового обслуживания типа U/&/1 и входящим MC-потоком: время ожидания // Математические методы исследования сетей связи и сетей ЗШ (тезисы докладов). Минск. 1990. С. 54-55.

4.Коротаев И.А., Спивак Л.Р. Система обслуживания с редко меняющимся режимом работы /'/ Автоматика и вычислительная техника. 1990. JT6. С.18-19.

5.Коротаев И.А., Спквак Л.Р. Система ¡¿/£/1 в редко изменяющейся полумарковсиой среде // Сети связи и сети ЭШ как модели массового обслуживания (тезисы докладов). Минск, 1991. С.74-75.

— 16 -

6. Коротав в И.Д., Спивак Л.Р. Анализ ШО с переменной интенсивностью входящего потока методом малого параметра )/ Радиотехнике. 1991. т. G.6-II.

7.Корота«в И.А., Спивак Л.Р. Системы массового обслуживания в полумарковской случайной среде (препринт). Томск: *Изд-во ТГУ,

1991. 1бс.

8.Коротаег И.А., Спивак Л.Р. Система массового обслуживания M/M/1/oo в полумарковской случайной среде // Анализ и синтез систем массового обслуживания к сетей ЭШ (тезисы докладов).. Одесса, 1990.

9.Коротаев И.А., Слива« Л.Р. Система U/U/l/ео со случ^Лно изм каащяииея параметрами // Сети связи и сети ЗШ. Анализ и прим ненке (тезисы докладов). Минск, 1992. С.76-77. Ю.Коротаев H.A., Спивак Л.Р. Системы массового обслуживания полумарковской случайной среде // Автоматика и телемеханика.

1992. К7. C.Ö6-92. •

II. Спивак Л.Р. Процесс гибели и размножения в редко изменяют ся случайной сред« // Математические методы исследования сете связи и сетей ЭШ (тезисы докладов). Минск. 1990. C.I29-I30.