Введение к работе
Актуальность проблемы. Разработка информационно-вычислитель-шх сетей, т.е. сетей ЭШ и сетей передачи информации пред-їтавляет собой в настоящее время одно из основных направлений іауки и техники. Математическими моделями сети в целом и её отдельных элементов являются, соответственно, сети и системы мас-ювого обслуживания.
Как правило, в качестве математических моделей узлов сети гагут использоваться стандартные \2Ю типа M/iJ/I/oo , M/M/I//V , l/fr/l/oo , либо более сложные СМО, учитывающие специфику ре-ільних сетей.
Большинство авторов работ по анализу элементов информаци-iHHO-вычислительных сетей считают, что рассматриваемые потоки рафика описываются пуассоновекими процессами.' Это подтверждайся измерениями на реальных сетях и позволяет получить акали-? ичес кие результаты в замкнутой форме.
Однако во многих случаях в силу специфики потоков трафика очно смоделировать их бывает невозможно. В реальных сетях ин-'енсивность потока на отдельный узел может изменяться либо де-ерминированным образом из-за неоднородности обращений'к узлам :ети и нестационарности потоков, входящих на сеть извне, либо яучайкым образом по следующим причинам:
блокировка или временный выход из стро- узлов сети, что при-юдит к их обходу и, следовательно, появлению новых-потоков на ругйх узлах;
использование адаптивной маршрутизации, в результате которой в узлах появляются и печі ают потоки сообщений; подключение либо отключение источников информации к сети.
- 4 -Анализ СЗЛО с изменяющимися во времени параметра!... является сложной математической задачей, решению которой были посвящены, в частности, работы Л.Клейнрока, Г.П.Бааарина, А.К.Ду-дина, А.А.Назарова к других авторов. Почти всегда характеристика ОЮ можно определить лишь приближённо или численно. Б настоящее зремя разработан ряд методов расчёта характеристик СМО конкретных конфигураций с переменными параметрами. Однако, достаточно универсальных методов {как приближённых, так и численных), применимых к расчёту характеристик целого класса ШО пока не существует, поэтому есть необходимость в разработке таких методов хотя бы для определённых классов систем.
Цель работы. При выполнении работы ставилась задача разработать методы анализа ШО со случайно изменяющимися параметрами, а именно:
а) ОЛО, функционирующих в случайной марковской среде;
б) CMG, функционирующих в случайной полумарковской среде.
Методика исследования. Для решения поставленных задач использовались методы теории массового'обслуживания, теории слу- . чайных процессов, теории вероятностейі метод асимптотических разложений. Для получения количественных результатов проводилась расчёты на ЭШ.
Научная нг изна.
I. Предложен метод расчёта характеристик широкого класса.. СМО, функционирующих в случайной среде. Основная идея метода
їєтся т предположении, что состояние среды изменяется зчно редко, справедливом для реальных систем, рассматри-в качестве элементов и фрагментоЕ икфсрмационнс-Еычис- .
. --5-
лительных сетей. Это предположение позволяет применить для нахождения ряда характеристик исследуемых СМО метод малого пара-
метра. Искомые характеристики шцутся в виде раэлложения в ряд по малому параметру. Для коэффициентов разложения получены рекуррентные формулы.
-
Вышеописанный метод использован для исследования следующих СМО, функционирующих в случайной марковской среде: M/W/I//V, М/М/1/ео, MA!//V/e« , СМО с параметрами, зависящими от состояния системы, ШО с ИНТЄНСИВНОСТЯ&... изменения среды различных порядков малости и U/G /I/' . Для СМО с экспоненциальным обслуживанием получены рекуррентные формулы для вычисления коэффициентов разложения в ряд по ма-ому параметру распределения числа заявок в системе, а для М//1/<х> - коэффициентов разложения Лапласа-Стилгьеса от функции распределения виртуального времени ожидания.
-
Рассмотрены СМО, функционирующие в случайной полумарковской среде: М/М/ІЛ» , M/M/I//V, ОЮ с параметрами, зависящими от состояния системы, и М/^/іА** . Для СМО с экспоненциальным обслуживанием найдены рекуррентные формулы для вычисления коэффициентов разложения в ряд распределения числа'заявок в системе, а (для СМО типа И/&/1/оо - коэффициентов разложения преобразования Лапласа от функции распределения суммарного объёма заявок в системе.
Практическая ценность и реализация результатов работы. Предложенные модели и методы могут использоваться при проектировании и эксплуатации информационно-вычислительных сетей для расчёта характеристик отдельных узлов сети. Предложенные в дис-сер' ции модели и методы были использованы при расчёте характе-
ристик разрабатываемых заказчиками систем обработки информации и систем передачи данных. В рамках хоздоговорной темы "Диагноз-ПТ", выполненной в І9Ш-90Р.г. Томским госуниверситетом для НИИ ССУ (г.Москва), СІ НИЙ ССУ (г.Пятигорск), заказчикам были переданы математические недели и методы расчёта, а также комплексы программ, реализующие соответствующие метода. Данные комплексы используются для расчёта и оптимизации разрабатываемых систем. Акт о внедрении результатов диссертации приведён в приложении.
Публикации. Основные результаты проведённых исследований опубликованы в I печатных работах. Материалы диссертации были также изложвкы в отчётах по хоздоговорной теме "Диагноз-ПТ"-.
Апробация работы . Основные положения диссертации и отдельные её результаты докладывались и обсуждались на
ежегодных зимних Белорусских школах-семинарах по теории массового обслуживания и её приложениям (г.Витебск, 1990г., г.Гро; но, 1991г., г.Брест, 1992г.),
республиканской конференции "Совершеьетаование методов исследования потоков событий и систем массового обслуживания" (г.Киев, 1989г.),
семинаре "Математические методи оптимизации процессов функционирования вычислительных сетей (г.Киев, 19Й9г.),
республиканской научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭЕМ" (г.Одесса, 1990г.),
Всесоюзной научно-технической конференции "Распределенные микропроцессорные управляющие системы и локальные вычислительные сети" (г.Томск, 1991г.).
' - 7 -
Структура и объём ргботы. Диссертация состоит из введения, трёх глав, заключения, списка литературы, содержащего 96 наименований, приложения. Содержание диссертации изложено на 122 страницах машинописного текста.
СОДЕЕШМЕ РАБОта
Во введении дана общая характеристика работы, обоснована её актуальность, формулируется цель исследования, даётся краткий обзор работ по теме диссертации и формулируются основные полученные результаты.
Первая глава состоит из пести параграфов и посвящена системам массового обслуживания, функционирующим в случайной марковской среде.
В 1.1 рассматривается система твпа М/М/1/оо . Входящий поток в системе является пуассоновским с интенсивностью X(t) причём Д( t) есть кусочно-постоянный марковский процесс с. конечным числом состояний f Я/, .. . Л л J . A ft) сохраняет постоянное значение Л і в течение некоторого промежутка времени 7( » после чего скачкообразно изменяет своё значение. ка Л; с вероятностью <2 / , причём
7~ есть случайная величина, распределённая по экспоненциальному закону с параметром ot* ..
Такой поток в литературе чаще всего именуется пуассоновским потоком на цепи Маркова или пуассоновским потоком в случайной марковской среде.
Время обслуживания рь.определено по экспоненциально^ закот? с параметром А* . -
- 8 -Обозначим Ні [J/ стационарную вероятность того, что в системе / заявок и значение интенсивности входящего потока равно Xi . Вероятности Рі (і) отвечают системе уравнений:
а, к (j-o - (xits «я Pdj)+/< Ш+
«'условии нормировки:
Основным допущением, позволявпуш решить эту систему, является предположение о редких изменениях интенсивности -входного потока, что соответствует тому, что с/,, <<Г і t С' = Туї . Для реальных потоков это допущение справедливо, т.к. события, приводящие к изменению интенсивности входящего на элемент сети потока (например,отказ одного из элементов, изменение маршрутизации, подключение дополнительных источников к сети), происходят достаточко редко по сравнению с остальными событиями в системе Это допущение позволяет нам применить к решенив исходной системы метод мал.го гшрамгтра.
Малый параметр вводим следующим образом:
ОІ і- = oli І , і* ЦІЇ Будем искать Г{ (У/ в виде
Подставляя это разложение в исходную систему и приравни-!ая коэффициенты при одинаковых степенях , получаем систе-ш однородных (при Л- =0) и неоднородных (при Л > 0) разносных уравнений, решения которых «іМЄОТ ВИД
Р/У-ъ «-/>)/
де Pс " Л і/ J* - загрузка систеш*,
Ті у І = /, '? - стационарные вероятности того, что
качение интенсивности входящего потока равно Д; , ко-эрые удовлетворяют системе
І ti - і
1С/
Ш гл<к)
Для коэффициентов С , и <) , найдены ра-
рхснтные по /\ формулы.
- 10 -Kpowe того, определены условия применимости даного методе. Для этого необходимо выполнение неравенства
_=JL_ . /no* oli ^^ Т7Г-, с 1
в некоторой окрестности ТОЧКИ ZoO.
В параграфах со второго по пятый рассматриваются соответ
ственно системы с конечным„накопителем, с несколькими обслужи
вающими приборами, с параметрами, 'зависящими от состояния сис
темы, и с интенсивностдаи изменения среды различных порядков
малости. Бее эти системы функционируют в случайной марковской
среде. Для каргой получены рекуррентные формулы для коэффици
ентов разложения в ряд по малому параметру распределения чис
ла заявок в системе. ;
Б шестом параграфе рассматривается система с произвольным обслуживанием, с одним обслуживаюіцям прибором и бесконечным числом мест для ожидания, также функционирующая в случайной марковской среде. Функция распределения времени обслуживания
где П - длительность обслуживания.
Рассматриваем виртуальное время ожидания Т'ftJ . т>е. время, которое -тяжко пройти от момента t до полного освобождения прибора от обслуживания требований, поступивших в систему до момента Г . При рассматриваемой дисциплине "первый пришёл - первый обслужен" виртуальное ьремя ожидания совпадает с обычным временем гжиданик начала обслуживания заявкой, пришедшей в момент L Обозначим
-.11 -
](oc,t) = P'[Mt)±k,r(t)
;. функцию распределения виртуального времени ожидания
« Mt)-Xi.
Задача решена с точностью до преобразований Лапласа-
глтьеса от г t- (тс, t) которые ищутся также в
іе разложения в ряд П" малому параметру. Для коэффициентов їложения получены рекуррентные формулы.
Кроме того, найдены среднее и дисперсия виртуального вре-ш ожидания.
Вторая глава посвящена системам массового обслуживания, ікционирующим в полумарковской случайной средз. Как известно', ювкым отличием полумарковского процесса от марковского яв- -ітся то, что распределение времени пребывания последнего в -ом -остоянии может быть произвольным. Это приводит к про-!сам значительно более общего вида, т.е. класс, полумаркоз-!х процессов включает в себя, класс марковских процессов.
Как и ранее, предполагается, что состояние среды измеия-:я редко, т.'е. средние длительности пребывания процесса в Ф,см состоянии имзют порядок I/O. , где . - малый' параметр.
В 2.1 рассматривается система МДї/I/oo в пслумарксв-)й случайной среде. Пусть ~%(t) - полумарковекий слу-їньгй процесс с множеством состояний /1,2,... /і]', /(f/~ шсло заявок в системе в момент t и ft ftJ - время момента "С ДО следующего изменения состояний процесса J(tJ Обозначим г і (i,x, t) вероятность того,, что
Пусть .
e t~>oo
ищется в виде разложения в ряд по малому параметру и для коэффициентов разложения получены рекуррентные формулы.
. Во втором и третьем параграфах рассматриваются системы с конечным накопителем и с параметрами, зависящими от состояния, функционирующие в полумарковской случайной среде.
В четвёртом параграфе рассматривается система типа М/6-/ІД»
Пусть $ (t) - управляющий полумаркоьский проце-с. Если
в момент Г ^/С ш І- т0 ходячий поток - пуассо-
иовский с параметром А; , заявки обслуживаются с постоянной скоростью &i . Обозначим ft J суммарную длину заявок, находящихся в системе в момент t » ]> (tj - время от момента до следующего скачка процесса J(t) Отметим, что при постоянной скорости обслуживания суммарная длина заявок *?(t). совпадает с виртуальным временем ожидания системы
Пусть fifX'^j^/ - функция распределения для
суммарной длины заявок, т.е.
/у (x.y,t)- P!Vt)4. ?.№ W
Рассматривается преобразование Лапласа от Fi(3C,4, t/, которое ищется также в виде разложения в ряд по малому параметру.. Для коэффициентов разложения найдены рекуррентные формулы.
Третья "глава посвящена применению методов, изложенных в диссертации, к решения конкретных технических задач.
Кяк известно, систем массового обслуживания і случайной .среде являются общепринятыми моделями узлов цифровых сетей интегрального обслуживания. Предположим, что на узел поступает по-
- ІЗ -ток информации типа голос/данные. Достаточно адекватной моделью потока такого типа является пуасоновскэй поток со случайно изменяющейся интенсивностью.
Отдельно рассматривался случай, когда у СІЮ в случайной среде изменяется лить интенсивность входящего потока, а параметры обслуживания остаются неизменными. Расчётные формулы были реализованы в виде програгмы на языке Си для ЭШ типа 1Ш PC. Программа производит расчёт следующих характеристик СМО:
первые Пі значений распределения числа заявок в система {т задается в программе);
средняя длина очереди;
среднее время ожидания -
для систем типа МД1/1/« , Уі/Л/1/М , М/М/Л/оо и U/a/n/АҐ , функционирующих в случайной марковской среде.
Программа работает в диалоговом режиме. Полученные данные выводятся на экран дисплея и на печать.
Вышеописанные программы использовались для расчёта характеристик системы обработки информации, так называемой "аппаратной управления" в рамках хоздоговорной темы "Разработка математических методов расчёта характеристик элементов и фрагментов АСУС в нестационарных условиях" <шифр "Диагяоз-ПТ"). Использование программ позволило избежать трудоёмкого имитационного моделирования. ...
Во втором параграфе третьей главы проводится анализ полученных результатов, на примере которых прослеживается'ряд закономерностей и зависимостей псведения системы от исходных параметров (иктенсивностеЯ входящего потека и обслуживания, а также изменения случайней среды). Численные примеры приведены в виде. таблиц.
- 14 -В Заключении формулируются основные результаты и шкоды работы.
В Приложение включён акт о внедрении результатов работы.