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

. ■ - <■■' «'. Томский государственный университет

имени В.В.Куйбышева

• На правах рукописи Дудин Александр Николаевич

УДК 519. 872

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

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

исследованиях •

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Томск - 1992.

Работа выполнена в Белорусском государственном университете

им. В.И.Ленина

Официальные оппоненты: Анисимов В.В. - д.ф.-м.н., профессор

Рыков В.В. - д.ф.-м.н., профессор Терпугов А.Ф. - д.ф.-м.н., профессдр

Ведущая организация: Институт проблем управления АН СССР (г.Москва)

Защита состоится '42 " марта 199.2г. в часов на заседании специализированного Совета Д 063.63.03 при Томском государственном университете (634050, г. Томск, проспект Ленина, 36).

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

Автореферат разослан " 199«#.

Ученый сещзетарь специализированного совета ,

у—л /

канд. физ.-мат. наук, доцент 1 , Б.Е.Тривоженко

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

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

A.М.Горцев, Э.А.Даниелян, И.И.Ежов, А.М.Захарин, В.А.Нвницкип,

B.В.Калашников, Г.А.Медведев, Г.К.Мишкой, А.А.Назаров, А.В.Печинкин, В.В.Рыков, А.Ф.Терпугов, Г.И.Фалин. С.Ф.Яиков и др.

Классические модели систем массового обслуживания являются уже довольно хорошо изученными. Состояние теории С?.!0 к концу 70-х годов отражено в фундаментальном справочника, созданном большим коллективом авторов под редакцией Б.В.Гнеденко и Д.Кени-га.

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

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

Задача оптимального .распределения системных ресурсов между потоками запросов различных пользователей к настоящему времени решена только для наиболее простых дисциплин разделения ресурсов, таких как статические относительные и абсолютные приоритеты и различные их комбинации, а также различные циклические дисциплины. Решение задачи при более сложных дисциплинах разделения ресурсов наталкивается на непреодолимые аналитические трудности. В такой ситуации разумным выходом является декомпозиция модели функционирования системы в целом на подмодели, описывающие процессы обслуживания запросов различных потоков, анализ характеристик этих подмоделей и, затем, агрегирование характеристик подмоделей в характеристики' модели в целом. При этом, естественно, на этапе агрегирования возникают существенные проблемы взаимной стыковки параметров подмоделей (интенсивносте? потоков, распределений различных времен, стоимостных коэффициентов и т.д.), но в принципе с помощью итерационных процедур, реализуемых на ЭВМ, эти сложности (по крайней мере на прикладном уровне) вполне преодолимы. Известным примером применения такого подхода является исследование систем с циклически опросом с помощью декомпозиции модели системы на подмодел! систем массового обслуживания с отключающимся прибором (с удаляющимся на отдых прибором, с прогулками и т.д.). Эта иде? является довольно прозрачной, а систематически применил ее ь исследованию систем с циклическим опросом Х.Такаги. Пр1 применении такого подхода и декомпозиции моделей систем, обслуживаших разнородные потоки запросов различных приоритетов, возникают более сложные модели СМО, чем модели СМО с отключающимся прибором. А именно, модели СМО с управляемы» режимом функционирования (СМО УР) и модели СМО, функционируют в случайной среде. Системы, функционирующие в случайной среде, I •литературе иногда называют СМО ИР (СМО с изменяемым режимо! функционирования). Будем называть их так же, хотя, на наш взгля, термин СМО ИР можно было бы употребить и к системам < управляемым режимом функционирования, и к системам функционирующим в. случайной среде. В обоих видах систем имев' место изменение режима функционирования СМО. Разница заключаете; в том, что СМО.УР сама управляет своим режимом функционирования выбирая его динамически в зависимости, например, от числ;

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

Системы массового обслуживания с изменяемым режимом функционирования обоих видов, и СМО УР, и СМО ИР, находятся в юле зрения специалистов в области теории массового обслуживания /же более двадцати лет. Обзоры работ в области СМО УР опубликованы В.В.Рыковым; М. и Е. Фаянбергами; Т.Крейблом, I.Гроссом, М.Мэгэзином; Дж.Тегхэмом. Вышеупомянутые СМО с отклю-1акшимся прибором являются по существу частным случаем СМО УР с хвумя возможными режимами функционирования, в котором при работе :истемы в одном из режимов обслуживания запросов не производит-;я. Всплеск интереса к этим СМО, наблюдающийся в последние годы, )бъясняется, в первую очередь, возможностью использования их, :ак было отмечено выше, для исследования систем с циклическим тросом очередей, особенно, локальных вычислительных сетей СЛЕС) : протоколами доступа типа TOKEN PASSING RING и TOKEN PASSING !US (стандарты IEEE 802.5 и 802.4). Представление о состоянии 1ел в исследовании СМО с отключающимся прибором можно составить 13 обзоров Б.Доши и Дас.Тегхэма. Отметим, что развивается и клас-:ификация таких моделей СМО. К известному разделению по способу ¡ключения прибора (N-, Т- и D - стратегии) добавилось разделение ю способу выключения прибора (системы с исчерпывающим, ентильным, ограниченным и полуисчерпываюшим обслуживанием), [асть результатов данной работы также относится к исследованию МО с отключающимся прибором.

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

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

Довольно полная библиография по СМО ИР содержится в монографии . По-видимому первые результаты исследования СМО ИР содержатся в известной монографии Б.В.Гнеденко, И.Н.Коваленко*""". Соответствующая СМО рассматривается в ней как некоторое обобщение ненадежной СМО типа M|G|I и называется системой с частичным выходом прибора из строя. Залетим, что ненадежные СМО являются по отношению к СМО ИР примерно таким же частным случаем, как СМО с отключаодимся прибором по отношению к СМО УР. Их в этом плане объединяет то, что при работе системы в некоторых режимах обслуживание запросов не производится вообще, что существенно облегчает решение задачи. В монографии ***) намечен путь' решения задачи нахождения стационарного распределения суммарной длины запросов в системе типа M|G|I, функционирующей в марковской случайной среде. Для системы с двумя возможными состояниями среды эта задача практически решена. Дальнейшего развития тематика СМО ИР в работах Б.В.Гнеденко, И.Н.Коваленко и их учеников не получила. С начала 70-х годов эта тематика привлекла внимание зарубежных ученых.

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

процессы, характеризующие состояния СМО и среды являются зависи-» >

Mayer К. H. Wortesysteme mit, variabler bearbeitungsrate У У Lecture nottes in economics and mathematical systems. Operations research, computer, social science.- Berlin, „„. Heidalberg. New-York.- 1971.- v.<Sl.- 312 p.

Сояресич Д.H., Скляревич Ф.К. Вероятностные модели объек-» tod с возможными изменениями - рига: Зинатне.-1989.- 366 с. ртденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания, 'м.: Наука.- 19бё.- 432 с.

мыми, применение такого усреднения вместо усреднения по совместному распределению процессов является незаконным. Известен пример, когда использование классических моделей СМО для анализа процесса передачи данных в цифровой сети интегрального обслуживания (ЦСИО) с гибридной коммутацией, более адекватной моделью которого является процесс обслуживания запросов в СМО ИР, привело к'тому, что полученное значение задержки пакета в сети в 500 раз отличалось от истинного.

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

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

Сформулированная цель предопределяет следующие задачи исследований : • 1

-изучение класса моделей СМО типд. M|G|I и М|М|®, функционирующих в полумарковской случайной среде и среде типа процесс гибели и размножения;

- исследование моделей СМО типа M|G|I с управляемым режимом функционирования, свойств оптимальных стратегий управления ими и зависимостей параметров оптимальных стратегий •• от основных параметров СМО;

- исследование моделей многолинейных марковских СМО, системы с повторными вызовами и СМО типа GI|M|I с управляемым режимом функционирования;

- создание комплекса программных средств для расчета характеристик вышеперечисленных моделей СМО и синтеза оптимальны* стратегий управления ими.

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

ции.

Научная новизна. Впервые:

- найдены характеристики СМО, функционирующих в полумарковскоп случайной среде;

- проведено обстоятельное исследование математической модели передачи данных в ЦСИО в режиме гибридной коммутации с плавающим порогом или адаптивной коммутации;

-исследованы немарковские модели СМО, функционирующих -в синхронной случайной среде;

- проведено систематическое комплексное исследование систем массового обслуживания типа М|0|1 и М|М|п с управляемым режимом функционирования при учете наличия различных видов штрафов, немгновенности и инерционности переключения, надежности, отсутствия информации о состоянии системы и т.д.;

- рассмотрены модели управляемых СМО с рекуррентным входным потоком и с повторными вызовами.

Практическая значимость работы и внедрение результатов

исследований.

Содержание данной работы во многом определилось потребностью адекватного описания процессов обработки информации в ЦЛЮ,' ЦСИО - по общему признанию (см., например, тематический выпуск журнала "Автоматика и вычислительная техника" 1691, И) -магистральный путь развития средств электросвязи в мире в ближайшие десятилетия. Развитие ЦСИО обусловлено, во-первых, ростом объемов дискретной информации, передаваемой по сетям связи; во-вторых, преимуществами цифровых методов передачи и коммутации; в-третьих, достижениями в областях техники цифровой многоканальной связи, микроэлектроники и вычислительной техники. ЦОИО предназначается длй передачи посредством единых технических средств • массивов самых разных видов информации - речи, интерактивных данных, файлов ЭВМ, больших массивов данных, телефакса, факсимиле и т.д. Различные виды информации имеют различные требования к характеристикам процесса их передачи. Обилие видов передаваемой информации, разнобой и противоречивость в требованиях к характеристикам делают задачу проектирования такий сетей и управления их работой чрезвычайно сложной. Сложность возникает и на этапе разработки концепции сети и критериев оценки эффективности, и на этапе топологического проектирования, и на этапе организации управления потоками в сети, и на этапе анализа и синтеза

алгоритмов коммутации. При решении задач двух последних этапов активно используются модели СМО. Классические модели СЫО довольно неплохо опнсызают процессы передачи информации в традиционных (неинтегральных) сетях связи, а также в ЦСИО при использовании традиционных режимов коммутации - коммутации пакетов и коммутации каналов - и режима гибридной коммутации с фиксированным порогом. При исследовании процессов передачи информации в ЦСИО с использованием перспективных режимов -гибридной коммутации (см.., например, книгу С.И.Самойленко*'), потребность адекватного описания процессов передачи математической моделью неизбежно приводит к необходимости исследования СМО УР и СМО ИР. Соответствующие модели возникают при описании функционирования сети и на канальном, и на сетевом, и на транспортных уровнях эталонной модели взаимодействия открытых систем. Вопрос о выборе оптимального режима коммутации в ЦСИО в настоящее время остается открытым. Решение его зависит во многом от решения технических проблем (например, создания эффективного гибридного узла коммутации, обеспечения синхронизации и т.д.), но в первую очередь - от результатов анализа экономичности функционирования различных вариантов ЦСИО. Такой анализ неделим без построения и строгого анализа характеристик процессов передачи информации в ЦСИО, что, в свою очередь, диктует необходимость исследования СМО УР и СМО ИР. Такая работа проводилась в частности в ОНИЛ МОКС с ПУ Белгосуниверситета по заказам научно-исследовательского института электротехнических устройств ЛНПО "Красная Заря" (г.Ленинград) и результаты данной диссертационной работы лежат в русле этих исследований. Основные модели, описывающие процессы передачи информации в ЦСКО, это - система M|G|I, функционирующая в случайной среде, система М|М|», функционирующая в случайной среде, системы M|G|I, GI|M|I и М|Н|п с управляемым режимом работы. Такие модели и исследуются в данной работе.

Другим важным реальным объектом, при исследовании которого возникают модели СМО УР и СМО ИР, являются системы множественного доступа с предоставлением, ресурсов по требованию. Такие системы являются в некотором смысле гибридными между системами множественного доступа с полным распределением ресурсов и системами со случайным множественным доступом (см.,

Самойленко С.И. Сети ЭВМ,- М.: Наука,- 1986,- 160 с.

*

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

Практическая значимость результатов работы заключается в

следующем.

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

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

3. Разработанная методика исследования систем, функционирующих в синхронной случайной среде, позволяет повысить качество расчетов характеристик протоколов различных уровней информационно-вычислительных .сетей, использующих механизм скользящего окна. В частности, она использована при оценке производительности, максимальной пропускной способности и настройке протокольных параметров станции ЛВС "'Квант-С",

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

5. Намеченный подход к исследованию систем типа |М 11 с управляемым режимом функционирования позволит сушественнс

Башарин Г.П., ЕФимушкин В.А. Методы анализа локальных информационно-вычислительных сетей // Итоги науки и тежники.-Оэр.

Связь,- м.: ВИНИТИ,- 1888,- г.г.- с.60 - 109.

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

7. Созданная методика расчета характеристик систем с этключаюшимся прибором позволяет точно рассчитывать <арактеристики баз данных в вычислительных .сетях (что ранее делалось только приближенно) и улучшить экономические показатели IX функционирования.

3. Разработанное на основе полученных в данной работе результатов программное обеспечение для ЕС ЭВМ и ПЭВМ класса'IBM 3С может найти широкое применение при исследовании и оптимизации нирокого спектра реальных систем и процессов, допускающих интерпретацию в терминах СМО УР и СМО №.

Результаты работы использовались при выполнении -осбюджетной НИР I? гос. per. 79015086, работы в рамках сомплексной программы в области вычислительной техники АН ОССР. ¿В и ССО СССР, регламентированной постановлением № 1473 / 146 от 29.12.1980 / 31.12.1980, а также при выполнении ряда (оздоговорных НИР, в том числе с номерами гос. регистрации 31036329; 0185001I154; 0I8700I5088; 01900009052; 01900013855. Результаты нашли применение в разработках предприятий т/я A-II29, и/я М-5308 (г. Санкт-Петербург), ОКБ '"Квант" Сг.Минск), внедрены в учебный процесс в Белорусском университете \ в Военном инженерно-космическом институте им. А.Ф.Можайского Сг. Санкт-Петербург).

Апробация результатов работы. Результаты диссертации представлялись и докладывались на V Советско-японском симпозиуме по теории вероятностей (Тбилиси, 1982), V Международной вильнюсской конференции по теории вероятностей и. математической ;татистике (Вильнюс, 1989), VIII Всесоюзном совещании по проблемам управления (Таллин, 1980), II Всесоюзном совещании -семинаре "Оптимизация динамических систем" (Минск, 1980), V всесоюзном совещании по статистическим методам в процессах травления (Алма-Ата, 1981), II, III, IV Всесоюзных совещаниях по распределенным автоматизированным системам массового

обслуживания (Кишинев, 1986, Винница, 1990, Душанбе, 1991), V и VI Всесоюзных' конференциях "Вычислительные сети коммутации пакетов" (Рига, 1987, 1989), V Всесоюзной школе-семинаре по распределенным автоматизированным системам массового обслуживания (Рига, 1988), XIII - XV Всесоюзных школах-семинарах по вычислительным сетям (Алма-Ата, 1988, Минск, 1989, Ленинград, 1990), I Всесоюзной конференции по информационным системам множественного доступа (Минск, 1989), I - VII Белорусских зимних школах по - теории массового обслуживания (Гродно, 1985, 1987 - 1989, 1991, Гомель, 1986, Витебск, 1990), школе-семинаре "Современные вероятностные методы исследования информационно -вычислительных систем и сетей" (Петрозаводск, 1987), республиканском научно-техническом школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" (Одесса, 1990), V Республиканской конференции математиков Белоруссии (Гродно, 1980), семинаре "Проблемы автоматизации управления процессами массового обслуживания" (Киев, 1988), семинаре "Статистический анализ и оценивание характеристик стохастических моделей" (Киев, 1988), семинаре "Математические методы оптимизации процессов" функционирования вычислительных сетей" (Киев, 1989), Всесоюзной научно-технической конференции "Распределенные микропроцессорные управляющие системы и локальные вычислительные сети" (Томск, 1991) и др.

Публикации. Ito теме диссертации опубликовано более 5С работ. Основные результаты диссертации отражены в 39 работах.

Структура и объем работы. Диссертация состоит из 5 глав, списка литературы из 220 наименований. Объем работы 354 страниц, из них основной текст занимает 288 страниц, содержит 39 рисункое и 16 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава I посвяшена исследованию математических моделей СМ( типа M|G|I и М|М|ю, функционирующих в случайной среде.

Шд случайной средой будем понимать полумарковский случайный процесс. v>t с пространством состояний < 0,1.....п > и полу марковским стохастическим ядром Q(t) = ||Qtj (ОЦ, i, j = 0,n

Обозначим через Р = | 11м=г^- матрицу переходных вероятностей вложенной по моментам скачков процесса и1 цепи Маркова (Р =

= о (со)), через в(0 = | |6.((ъ)| |, .—— будем обозначать мат-

1 '' ' О.. (О

рицу времен пребывания среды в своих состояниях (С..(ъ)= ——).

1) Ри

Системой типа М|в|1, функционирующей в случайной среде будем называть однолинейную СМО с ожиданием, поведение которой зависит от состояния процесса и1 следующим образом. Во время нахождения среды в состоянии 1 в СЬЮ поступает поток запросов, имеющий показательное распределение интервалов между запросами с параметром Поступающие запросы характеризуются длиной, имеющей функцию распределения.В^ (ъ). Обслуживание'запросов производится со скоростью единиц длины в единицу времени. При изменении состояния среды параметры л., 5. и распределение Вс(0 мгновенно изменяют свои значения или вид, 1 = 0,п.

Наиболее простым процессом, характеризующим поведение СМО является процесс - суммарная длина запросов в системе в момент ъ. Процесс С! = и1- где ~ сопровождающая

компонента полумарковского процесса

Введем обозначения:

со

р^) = / е^йВ^О, Ре э > О,

О

со

ь[и = X Лв^О. х =Т. I -ТЗ^Г.

О

00 % = / ^/у),

О

Л1 = - \«>1 •

/ » *

Г(1,х,у) = ^^ 'Р < 1->1 = 1, < >£, €1 < у >, , (I)

1 X > О, У > 0.

Необходимым и достаточным условием существования пределов (I) является выполнения неравенства

Т = Ё РД > 0, (2)

__V — О

где 1 = 0,п , -"стационарная вероятность нахождения процесса

Для преобразований Лалласа-Стилтьеса 00

Ф(1,и) = X е^^ГО.х.сп), I = 0,п ,

в состоянии 1.

получено представление в виде:

~ —аз <»>у

«"Ci,

» II 1 1 IT 1«1]Г

s)= - а (s)' { 6lF(i,+0,eo)+ E Er Je r dF(r,+0,y)*

О

(3)

х [у,/*) - 1Ео р1Л V (5) ] } , 1 где а^з) = (в^-б^, а У1>г(з) - функции, вид которые

может бьггь получен алгоритмически.

Для двух важных классов случайных сред, а именно: среды бе: памяти, у которой = ^(Ор; , т.е. время пребывали?

среды в состоянии I зависит только от номера этого состояния, г вероятность перехода в состояние j зависит только от номерг этого состояния, а также циклической среды, у которой переход и; состояния и осуществляется в состояние и+, где

р+1, и = 0,п X ,

.0, и = п.

вид функций Yi>r(s) получен явно. Константы F(r,+0,cc) i

со

-uy

преобразование Лапласа-Стилтьеса J е dF(r,+0,y) удаетс$

о

исключить, ограничив "класс распределений GLj(y) множество) гиперобобшенноэрланговских распределении, являющимся плотным вс множестве всех распределений, или для любых других распределена фазового типа с ограничением на число переходов заявки в сети время пребывания в которой интерпретирует случайную величину < распределением фазового типа.

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

«¿vi - с 4i, n'r v " ,

Ro v > - min < «е^ь. h = I,Hi r, г =XkT >,

окончательный результат следующий:

ф) {«Ч

—И.(«>у

<Xi.S) «= - -yfo -I 6, J(I-e 1 )dF(i,+0,y) +

о

I-Ci(g(S)) I- П CU(»U(S))

l=o

l -1 ™ —m <a>y 1-1

E6mJe " dF(m,+0,y) П ei(»,(s))^

tnsO l = m+ l

О

п — 33 <э>у 1-4 п

Е бт / е т чГСт,+0,у)П е^Ся» П е^С-»

1 = "0,п , где

00 -в <«.у к1

/ в с!р(1, +0,у) = Е

"1.Г

г — 1 Ь = 1

4=1

I , г , Ь

П"

(6)

1,г,1

1 =

где

I

= I - * а-Р1св)).

Ч.г.Ь Н,г,Ь

а вероятности ^.г.ь^.+О) 'находятся из системы линейных алгебраических уравнений:

к. Н т

I 1.г 1,г,Ь.

Е Е Ра.г.ь.л.+О) = т,

Е Бь Е

I = О Г=1

Ч1.Г

(7)

I, г I, г

И б1 Е

1 = о г = 1

Е Е г ЬЦ))

Ь = 1 ¿=1 '

I , г

п О-ч.^Ч»

I . г,1

= о,

и

1 = I.

Е Е

I =0 Г =1

I.

Е т,

ь -1

где величина Т задана соотношением (2), в котором величина Р1

имеет вид:

н.

I . г

1.Г.Н,

Р^Ея, Е ^

Г — 4 Ь = 1 Х1,Г.

/ Е

Е

Ь = 1

I»' т,

г.г.ь

I = О г=1 "" Ь = 1 ^Ь.г.Ь

а величины являются корнями уравнения к.

" и

I - п Еч1гп" С^ьС*»"

I =о г = 1 ' Ь = 1 ' '

= О

1=а^Г, (8)

(9)

в соответствушей заданной области я е э.

Важной с точки зрения практики является модель системы типа М11, функционирующей в случайной среде, задаваемой числом запросов в некоторой системе массового обслуживания типа М|М|п|0. Т.е. времена пребывания среды в своих состояниях имеют экспоненциальное распределение с параметрами = 1=0,г>-1, ч;,, = п>1т, а переходные вероятности вложенной цепи имеют вид:

л 1=0^1

■Ут . т

т

,ir

л +ij«l

I. i=n

Pl.ui - ' Pi..i-i

0, l=n

Важность этой модели СМО M|G|I, функционирующей в случайной среде типа процесса гибели и размножения, определяется тем, что она адекватно описывает процесс передачи данных в ЦСИО в режимах гибридной коммутации с плавающим порогом и адаптивной коммутации. Исследование этой модели проводилось также Г.И.Фалиным и' С.Халфиным, а также в большом количестве зарубежных работ, выполненных на инженерном уровне. В данной работе ' для такой модели СМО получено преобразование Лапласа-Стилтьеса распределения процесса {К*,^}, а также выражения для условных средних длин L. распределения суммарной длины -запросов в системе. В случае, когда распределения В. (О длин пакетов, поступающих в систему при нахождении среды в состоянии 1, являются экспоненциальными (схема обобщения на случай РН-распределений проста), получены распределения суммарной длины запросов в системе, выражения для преобразования Лапласа g(s) распределения G(x) виртуального времени ожидания запросов в системе,- а также для двойных преобразований Лапласа распределений G^x.y) = < х | ut = i, *t_0 = у>,

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

Предложена схема нахождения распределения вероятностей числа запросов в СМО-типа M|G|I, функционирующей в случайной среде.

Изучены две модели системы типа М|в|1, функционирующей в синхронной случайной среде. Т.е. в среде, которая изменяет свои состояния независимо от состояний СМО. но только в моменты изменений состояний СМО (здесь - в моменты окончания обслуживания запросов в системе). В первой из этих моделей среда изменяет свои состояния циклически, распределение числа запросов,' обслуженных за время пребывания среды в фиксированном состоянии, геометрическое. Вторая из моделей является адекватной моделью процесса передачи информации в каналах информационно-вычислительных сетей с использованием механизма скользящего окна. Время обслуживания запроса состоит из двух зталов, первый из которых выполняется всегда, а второй - только при наличии свободного окна (из V/ имеющихся) для передачи. Запрос, обслуживание которого на втором этапе не производится из-за занятости окон, покидает.систему. Запрос, получивший ■ два этапа обслуживания, занимает окно, которое остается занятым в течении времени, имеющего экспоненциальное распределение с параметром к. Рассмотрен двумерный процесс {ц ,С1 >, где ^ -

п п п

число запросов в системе в п-й момент окончания обслуживания запроса, - число занятых окон в момент ьп+0, ^ О,

г» п

= ТЖ. Получена система линейных алгебраических уравнений

п

для частичных производящих функций распределения процесса ,С1->. В случае • старт-стопного протокола Ш = I) решение

п п

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

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

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

Главы 2 и 3 диссертации посвяшены рассмотрению системы типа М|01 с управляемым режимом функционирования. Предполагается, что однолинейная система массового обслуживания с ожиданием может работать в в, в >2, режимах. При работе системы в г-м режиме интервалы между моментами поступления запросов в систему имеют показательное распределение с параметром а время, обслуживания запроса имеет функцию распределения Вг(ъ). г = 1,в. Изменение режима работы системы возможно в моменты окончания обслуживания запросов в 'зависимости от. числа запросов, находящихся в системе. Имеется экономический критерий функционирования системы. Требуется выработать оптимальную стратегию выбора режимов обслуживания запросов. В главе 2 изучено несколько таких моделей СМО. В первой, базовой, модели, предполагается, что отсутствует штраф за переключения с режима на режим. Для такой модели из литературы известно, что при естественном упорядочении режимов работы в порядке убывания коэффициентов загрузки (и возрастания платы за использование соответствующего режима) оптимальная стратегия является монотонной - многопороговой, задаваемой следующим образом. Фиксируется натуральные числа называемые порогами,

• 'Если число 1 запросов в системе в

данный .момент ' окончания обслуживания запроса удовлетворяет неравенству то следующий запрос обслуживаеися в 1-ом

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

процедур нахождения" оптимальных значений порогов ^.....В

нашей работе мы априорно ишем оптимальную стратегию в классе многопороговых стратегий.• При фиксированном наборе порогов методами теории массового обслуживания ищется распределение вероятностей состояний системы массового обслуживания и явная

зависимость значения критерия качества от порогов (^.....

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

Рассмотрена ситуация, когда в функционале качества работы системы присутствует аддитивный штраф за переключение режимов работы. В этой ситуации оптимальная стратегия является гистерезисной, т. е. стратегией следующего вида. Зафиксированы натуральные числа j и к, называемые порогами. Если число 1 запросов в системе в некоторый момент окончания обслуживания запроса не больше, чем .1, следующий запрос будет обслуживаться в первом режиме, если 1>к, то во втором. Если же выполняется неравенство система сохраняет прежний режим

функционирования. Путем анализа поведения процесса ^ ,и1 V,'

п г»

где ^ ■ - число запросов в системе в момент окончания

г»

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

п

использовался перед моментом (после момента ъп). получено стационарное распределение числа запросов в системе и явная зависимость значения функционала качества от порогов j и к, что позволяет легко найти оптимальные значения порогов J и к.

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

вероятностей состояний системы. Приведем соответствующий результат.

Теорема. Стационарное распределение АО, вероятностей состояний рассматриваемой системы задается следующим образом :

, IV*) = Е * г*о .Е « Е ^ д^ .

I и = о т = о

/» (\CI-z)) - z

= П>> Л а (X (!-.)) -

(10)

(«(aO-D^CACI-z)) + *2(z)p?(\(I-z)> где

«0 = (1-р2){ф-(1) + (pt-p2) »т -ЕЕ t^J 1 , (II) I L i=im=o JJ

вероятности «е^ m>I, задаются производящей функцией

S(Z) = [Z(I-5(^i))+5(A1)(q(^(I-z))-q(A1))]/(I-6(A1)q(X )) (12)

- Е ф2(=) = Е *(z) = Е ^z™. <£>>=

m = 1 m= j+i m= 1

функции /3tcs>, <5<s>, qfsj есть преобразования Лапласа-Сгилтьеса распределений соответственно времени обслуживания запроса при работе системы в i-ом режиме, времени до выхода прибора из строя в свободном состоянии, времени восстановления прибора, pv= \ь|1). 1 - Гг. а величины Дт имеют вид:

П. Т If (1-г)р<(Л П-г))-1 I

Д„ = Е 4п 1 „ И - (13)

^ [ «-*»-* | 2 = 0 Получена явная зависимость значения критерия качества от

порога. Результат легко обобщается и на случай, когда прибор

может выходить из строя и в занятом состоянии. Рассмотрена.также

система, являющаяся гибридом системы с управляемым режимом

обслуживания и системы с отключающимся прибором. Приведены

результаты исследования таких систем на ЭВМ.

Рассмотрен и решен вопрос переноса результатов исследования

СМО со стационарным ординарным пуассоновским потоком на системы

с потоком - групп запросов с известным распределением числа

запросрв в группе.

Рассмотрена ситуация, когда имеется возможность изменения

режима функционирования СМО, но информации о числе запросов в

системе не имеется. Предложены рандомизированные и рандомизиро-

ванно-пороговые стратегии управления такими системами. Получена

зависимость значения критерия качества функционирования системы

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

В. главе 3 рассмотрены ситуации, когда, в отличие от задач главы 2, переключение режимов работы производится с некоторой задержкой. В первой модели предполагается, что при переключении режима работы системы с г-го на и-я система прекращает обслуживания запросов на время, имеющее функцию распределения Gr<t>, г = i,2. Поток запросов в это время не прекращается. Оптимальная стратегия ищется в классе гистерезисных стратегий, обеспечивающих меньшее число переключений по сравнению с пороговыми стратегиями. Получена зависимость значения критерия качества от порогов стратегии управления, реализована на ЭВМ процедура нахождения оптимальной гистерезисной стратегии.

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

случайный процесс Ct = jit , rt , }• , где it - число

n l» n n n * n

запросов в системе в момент окончания обслуживания n-го запроса, - номер режима, используемого перед моментом tn, ut = о,

п п

если после момента tn система не будет находиться в состоянии ожидания реализации принятого решения о переключении, и ut - и,

п

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

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

Рассмотрена и более сложная модель, отличающаяся от предыдущей тем, что после принятия решения о переключении на более быстрый режим обслуживания и истечения времени обслуживания h запросов с вероятностью q, о < q < 1, осуществляется переключение, а с дополнительной вероятностью в переключении режима системе отказано. Такая модель учитывает специфику функционирования сетей с предоставлением каналов по требованию, в которых возможный ситуации, когда весь резервный ресурс распределен между пользователями сети. Формально при 4=i из этой модели получается предыдущая модель СМО, но по существу это очень разные модели, и из характеристик более общей из них формально при q=i характеристики другой получить крайне затруднительно, если возможно вообще. Для этой более обшей модели также получено распределение вероятностей состояний системы. Приведем соответствующий результат.

ПУСТЬ • rt<P4i) = ¿In Р < i. = i, i\ =1, и, = и >,

-Г» -+00 t't't *

Г1 n n

eW>(i) = P-Ci =ir = 2 V = U >

41' Г» 00 x Xt -1» rt *t *'

n n n

noC2) = E *'°4i)z\ П Cz) = E *<p,(i)z\

V SSO i = j -

KDCZ) = E =<0>(i)z\ K4iz) = E -'"(i)*1.

isj + i i — j -h+1

K(z) = E ■a"(i)xl. v = h+1 , |z| <1.

Теорема Стационарное распределение вероятностей состояний рассматриваемой системы определяется следующим образом

= а^ЧО),' i = 0, j-2h+I ,

*,0,Cj-2h+i) = - lE GmA,m)«<O1(0), i =

m= i h

n-'Cj-h.!) = - E GmAUM -

- V УЛ „ О )Т1,01(0), 1=~27ь,

I—т—1 гл ' '

т= 1

П.Сг) =

^ +по(г) ^ 1 7 • .К,7 ]

Г Р (1-2)) .Ь I - (1-я) -]

г р. (Л (1-г)) .

■V*5 = -) П.Сг). V»

(14)

к„(*) =

рл\ (1-*))-

Г рл\(1-я)) -.и-« __

= -] к»Ся!}' р = 1.Н+1

а"0-Ь+г) = 6Ч'°'(0), г =ТЛГ,

Г *

где коэффициенты в являются решением системы ' ь линейных

г

алгебраических уравнений, коэффициенты которой в свою очередь

являются решением системы ь2+ь линейных алгебраических уравнений, коэффициенты которых зависят от значении корней

уравнения I - (1-ч)(р1(Л1(1-г)) / 2)ь = 0 в единичном круге комплексной плоскости,

А, = Е С V V*, = Ди„ 1 > 0.

1=1 4

где величины л1 заданы формулой (13),

С Е П . г =ТТ2".

(I , - . . , I >Е I. 1=1 I 1 Ь I

00 (л от

г'г' = Г -Ч- «* Г йВ (О. т > О,

о

К = { с«,.....1-Х5Г. £4=1},

вероятность *<о1(0) имеет вид:

Е с/'1' - Е С 6

где

2 Ь-т Ь-т-1

£ = Е А . + £ \/1 - —, т = ТТТГ

1=1 1=о 1 ч

(15)

< 1 )

I

_

I

а-^я^а-г))

Я1СЛ1С1-2:))-2 J 2 . о

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

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

I

аУ + сЛ + сгР2

Ю)

1

(16)

с +

где V - среднее время пребывания запроса в системе.

- штраф за

единицу времени пребывания запроса в системе, Р1 - средняя доля времени работы системы в 1-м режиме, ^ - стоимость единицы времени использования 1-го .режима, 1 = 1,2, * - интенсивность входного потока, р1 - загрузка системы при работе в первом режиме, и, V, V, с - некоторые константы. В случае, когда р4<I, вид констант и и с известен точно. Константы V и V в задачах,где данная соотношение не удается получить, предлагается искать

I. =о

с помощью статистического моделирования поведения системы при каком-либо одном Фиксированном значении порога Задача оптимизации значения порога затем реизется с использованием аналитической зависимости (16).

Глава 4 посвящена исследованию многолинейных марковских систем- с управляемым режимом Функционирования. Как и ранее, предполагается, что;изменение рехммов работы системы возможно только в моменты окончания обслуживания запросов, что обусловливает применение метода вложенных цзпеи Маркова. Получено распределение вероятностей состояний системы, управляемой с помощью многопороговой стратегии управления, явная зависимость значения функционала качества от порогов, которая, также как и для однолинейных систем, в случае наличия двух возможных режимов имеет вид (16). Результаты численных экспериментов подтвердили вывод, сделанный в главе 2, об эффективности использования изменения режима функционирования СМО и о малой целесообразности использования более двух режимов. В случае наличия двух возможных режимов получено трансцендентное уравнение для оптимального, значения порога при при р±=I

это оптимальное значение получено в явном виде.

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

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

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

Впервые в литературе исследована модель многолинейной СМО с

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

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

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

ше в •>, где авторы исследовали систему с помоцью метода шффузионной аппроксимации. Данная СМО отличается от слассической системы типа М|в|I поведением в свободном юстоянии. В момент, когда система становится пустой, с вероятностью р начинается отдых (период реорганизаций). Отдых ;остоит из медленного цикла, длина которого имеет распределение -КО, и, возможно, некоторого; числа быстрых циклов, длительность которых имеет показательное распределение. Стратегия включения прибора задается порогами п и к, к>п>1. Прибор системы вклкчается в работу после окончания медленного цикла, если во время его число запросов в системе достигло уровня п. или после быстрого цикла, во время которого число запросов в системе достигло уровня к. Очевидно, тачая стратегия включения прибора является довольно общей, известные М- Т- стратегии включения прибора получаются из нее как частные случаи. Данная модель поддается точному аналитическому расчету с помощью аппарата вложенных цепей Маркова, полученные результаты пропе, чем приближенные, полученные диффузионной аппроксимацией. Для однолинейной системы с ординарным и групповым потоком, а также для многолинейной систеш с таксп дисциплиной организации отдыха приборов получены основные характеристики систеш в довольно простом виде. Например, для однолинейной системы с групповым входным потоком (поток групп простейший с параметром л, группа с. вероятностью е1, 1>1, состоит из х запросов) производящая функция «(ж) числа запросов в системе в моменты окончания обслуживания запросов имеет вид :

«(==) = л

pWI-ec*?))-* р

р(*(1-0С:гЪ)

р(Л(1-Ч?С2>))-

оо £

. .02='

(17)

где вероятность *t того, что система пуста, имеет вид

«о » (I-Р)

I+p(Q(pz+k)-I + Е rnSm)

ffls П

(18)

где p(s) - преобразование Лапласа-Стилтьеса распределения

времени обслуживания, s(z) - производящая функция числа запросов

в группе, Чт - вероятность поступления m запросов в систему за

*> К°гая Я.Л.. Литвин В.Г., Лысяков П.К. Приближенный анализ оперативных методов реорганизации баз данных в вычислительных сетях //Автоматика и вычислительная техника.-1987.-Л5 3.-с.55-59.

К 2

время медленного цикла, С!=ЕЧт, т2 - средняя длительность

ш= О

быстрого цикла, Рг="А-с2' р=ль1( где ь1 - первый момент распределения времени обслуживания.

Среднее время завершения полной реорганизации базы данных Треорг имеет Бид

Т = V /

реорг

I+Q+ ЕЧт Е Е

т== О а = О 2 v = О

(19)

где V - число циклов, необходимых для проведения реорганизации базы данных, еа> - среднее число запросов в группе,

<i>

<1.....1 >£ГГ

1 . i т

где - множество, задаваемое следующим образом :

i^'-iCi,.....1,) : i>I. j=U, Е 1 =га К

i-i

Решена задача нахождения оптимального набора параметров (р,n,k) в задаче минимизации задержки запроса в системе при ограничении на минимальное число циклов реорганизации, необходимых для поддержания системы в рабочем состоянии'.

Рассмотрена базовая модель системы типа GI|M|I с управляемым- режимом функционирования. Предполагается, что система может работать в двух режимах. При работе системы в г-ом режиме интервалы между моментами поступления запросов в систему имеют функцию распределения Аг(ъ), время обслуживания запросов имеет экспоненциальное распределение с параметром *-=1,2. Изменение режима функционирования СМО возможно в моменты поступления запросов в систему. Решена задача нахождения оптимальной пороговой стратегии управления режимами функционирования СМО: Данная модель СМО имеет важное значение при решении таких актуальных задач теории сетей передачи информации, как' задача управления потоками в сети и задача ограничения нагрузки.

Систеш массового обслуживания с повторными вызовами являются довольно адекватными моделями функционирования канального уровня локальных вычислительных . сетей при использовании протоколов типа CSMA/CD (стандарт IEEE 802.3). В ряде работ отмечается важность разработки вариантов протокола с динамическим управлением его параметрами, в частности с

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

Развитие исследований двух последних задач (система GI|M|I с управляемым входным потоком и система М|М|1 с повторными вызовами), для которых №1 исследовали только базовые модели, получило в работах В.И.Клименок (наличие более двух режимов, более широкие классы стратегий).

Разработанные в • диссертации алгоритмы нахождения характеристик СМО с изменяемым функционирования и параметров оптимальных стратегий управления СМО программно реализованы в виде комплекса программ для ЭВМ. Часть программ реализована на языках PL/1 и ФОРТРАН под управлением ОС ЕС ЭВМ, другая часть -на языке PASCAL для ПЭВМ типа IBM PC AT. Проводится адаптация программ, рассчитанных на реализацию на ЕС ЭВМ, на IBM-совместимые ПЭВМ.

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

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

Решена задача исследования системы типа M|G|I, функционирующей в полумарковской случайной среде, а также в марковской среде типа процесс гибели и размножения. Исследованы системы типа М|М|<п, функционирующие в марковской и полумарковской случайной среде.

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

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

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

Исследованы базовые модели УСМО типа 61|М|1 и М|М|1 с повторными вызовами, на основе которых в дальнейшем былс проведено комплексное исследование систем такого вида.

Проведено исследование моделей СМО типа М(в|I. Мх|в|1 I М|М|п с отключающимся прибором и дисциплиной включения адекватно описывающей процесс динамической реорганизации ба: данных в вычислительных сетях.

Для всех исследованных в работе моделей результаты доведен! до простого компактного вида, что позволяет зффективне рассчитывать характеристики систем и параметры оптимально стратегий управления ими. На базе этих результатов созда] комплекс программ для ЭВМ ряда ЕС и ПЭВМ, программно совместимы: с 1ВМ РС, для нахождения оптимальных стратегий управлени; рассматриваемых СМО. С его использованием проведено исследован» зависимости вида оптимальных стратегий от различных параметро! изученных СМО'.

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

Полученные ¡д диссертационной работе теоретические и практи ческие результаты внедрены на предприятиях п/я А-П29, п/ М-5308 (г. Санкт-Петербург), ОКБ "Квант", в Белгосуниверситет .(г. Минск) и в ВИКИ им. А.Ф.Можайского (г. Санкт-Петербург).

Результаты диссертации опубликованы в 52 научных работах Основными из них являются :

[. Дудин А.II. Об оптимальном управлении многолинейной двухскоростной системой массового обслуживания с потерями на переключение скоростей // Второе Всесоюзное совещание-семинар "Оптимизация динамических систем".- Тезисы докладов.- !.!ннск: БЕИ.- 1980.- с.43 - 45.

2. Дудин А.II. Об оптимальном управлении скоростью обслуживания требований в многолинейны;.- система:? массового обслуживания// Теория оптимальных решений: Вильнюс: Ин-т математики и кибернетики,- 1980,- Вып.6,- с.125 - 139.

3. Дудин А.Н. О задаче оптимального управления шогоасоростнол системой массового сбслуживания//Автоматика и телемеханика.-IS80.- №9.- с.43 - 51.

4. Дудин А.Н. Об оптимальном назначении скорости обслуживания требований в многолинейной системе массового обслуживания // Доклады АН БССР,- 1980.- т.24,- с.780 - 783.

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

' кибернетика,- 1981,- }?2,- с.109 - 115.

6. Дудин А.Н. Оптимальное назначение скорости обслуживания требований в многолинейной двухскоростной система массового обслуживания // Автоматика и телемеханика.- 1931,- !Ш,-с.74 - 82.

7. Дудин А.Н. Оптимальное управление двухскоростной многолинея- . ной системой массового обслуживания со штрафом за переключения // Ред. журн. "Вестник ЕГУ. Сер.I".- Минск.- 1981,- S5 е.- Деп. в ВИНИТИ 01.07.81,- JP3228-8I.

8. Дудин А.Н. О синхронном и асинхронном переключении скоростей работы каналов двухскоростной системы массового обслуживания // Ред. журн. "Вестник БГУ. Сер.1",- Минск,- 1981.- 59 е.- . Деп. в ВИНИТИ 01.07.81. №3229-81.

9. Дудин А.Н. Оптимальное управление многолинейными системами с изменяемой интенсивностью обслуживания // V Всесоюзное совещание по статистическим методам в процессах управления. М.: ВИНИТИ.- 1981.- с.167 - 169.

[0. Дудин А.Н. Об одной системе массового обслуживания, функционирующей в случайной среде // Ред. журн. "1Ьвестия АН СССР. Техническая кибернетика",- М.: 1985.- 14 е.- Деп. в ВИНИТИ ' 10,01.1985.-•№294-85:

П. Дудин А.Н: Об одной системе с повторными вызовами и изменяемым режимом работы // Ред. журн. "Известия АН СССР. Техниче-

екая киберенетика"- М.: 1985.- О е.- Деп. в ВИНИТИ 10.01.1985.- 10293-85.

12. Дудин А.Н. Об одной ненадежной системе массового обслуживания с изменяемой скоростью входявзго потока // Вестник БГУ. Сер.I- 1985. 1?2.- с.65 - 67.

13. Дудин А.Н. Об обслуживающей системе с переменным режимом работы // Автоматика и вычислительная техника,- 1985,- £2. -с.27 - 29.

14. Дудин А.Н. Оптимальное управление ненадежной двухскоростнои системой массового обслуживания //Автоматика и телемеханика. - 1985,- К=9.- с.56 - 62.

15. Дудин А.Н. Модель процесса передачи данных в интегральны?: сетях связи с адаптивной коммутацией // V Всесоюзная конференция "Вычислительные сети коммутации пакетов"- Тезисы докладов. Рига: ИЭВТ,- 1987,- т.I,- с.121 -124.

16. Дудин А.Н. Анализ характеристик процесса передачи данных в канале цифровой сети интегрального обслуживания // Автоматика и вычислительная техника,- 1987,- №6.- с.44 - 52.

17. Дудин А.Н., Пирогов К.И. Анализ и оптимизация систем передачи данных с предоставлением каналов rio требованию // II Всесоюзное совещание "Распределенные автоматизированные системы массового обслуживания" - Тезисы докладов. Кишинев - 1986.

18. Дудин А.Н. Оптимальное управление двухскоростнои системой массового обслуживания с инерционным переключением // Автоматика и телемеханика,- 1988,- №5.- с.90 - 98.

19. Дудин А.Н., Халаф Э. Нахождение оптимальной гистерезисной стратегии управления двухскоростнои системой массового обслуживания // Вестник БГУ. Сер.I.- 1989.- №3.- с.35 - 38.

20. Дудин А.Н.. Ихсан X. Оптимальное управление текущим порогом КП/ККН при адаптивной коммутации // XIII Всесоюзная школа -семинар по вычислительным сетям.- Тезисы докладов.- М.: ВИНИТИ,- 19881- Ч.2.- с.82 - 86.

21. Дудин А.Н. Оптимальное управление многолинейной системой массового обслуживания с выключающимся обслуживающим устрой-ствЬм // V Всесоюзная школа-семинар по автоматизированным системам массового обслуживания,- Тезисы докладов.- Рига: ЦНИИ АСУ ТА.- 1988.- с.299 - 300.

22. Дудин А.Н., Клименок В.И. Об одной управляемой системе с повторными вызовами // V Всесоюзная школа-семинар по автома-

тизированным система».! массового обслуживания.- Тезисы докладов,- Pifra: ЦНИИАСУ ГЛ.- I9C3.- с.301 - 302.

23. Дудин Л.Н. Простепиая система массового обслуживания, функционирующая в случайной срэдз // Еероятностное моделирование систем и сетей обслуживания, Межвузовский сборник.- Петрозаводск: РИОПГУ,- 1988,- с.14 - 20.

24. Дудин Л.Н. Обобщение аналитической модели системы телефонной сигнализации с общим канатом, учитывающей помехи в перэдаю-щэй среде // Техника средств связи. Сер.СС,- 1989.- Вып.4,-с.49 - 53.

25. Дудин А.Н., Бенедиктова Л.И. Численный расчет процесса передачи данных в цифровой сети интегрального обслуживания.// Ред. журн. "Автоматика и вычислительная техника"*.- Рига: 1989,- 56 е.- Деп. в ВИНИТИ 13.01.1989,- ,¥322-В89.

26. Дудин А.Н. Анализ модели оперативной ' реорганизации баз данных в вычислительных сетях // Автоматика и вычислительная техника,- 1989,- 1РЗ.- с.70 - 75.

27. Дудин А.Н., Халаф Э. Оптимизация предоставления каналов по требованию в спутниковой сети множественного доступа с временным разделением // Первая всесоюзная конференция по информационным системам множественного доступа.-. Тезисы докладов.- Москва - Минск,- 1989,- с.67 - 71.

28. Дудин А.Н. Анализ вероятностных характеристик системы M|G|I,-. функционирующей в марковской случайной среде//У Международная 'Конференция по теории вероятностей,- Тезисы докладов.-

. Вильнюс,- 1989,- т.З,- с.204 - 205.

29. Дудин A.H.V 0 системе M|G|I в синхронной циклической случайной среде // XIV Всесоюзная школа-семинар по вычислительным сетям,- Тезисы докладов,- Москва - Минск,- 1989.- ч.З,-с.44 - 48.

30. Дудин А.Н., Марков А.В. Анализ системы массового обслуживания, функционирующей в эрланговской случайной среде без памяти // Всесоюзная конференция "К0МПАК-89"- Тезисы - докладов,- Рига,- 1989,- с.158 - 161.

31. Дудин А.Н. Расчет характеристик системы M|G|I, функционирующей в полумарковской случайной среде без памяти // Техника средств связи. Сер.СС,- 1990,- №7.- с.30 - 38.

32. Дудин А.Н., Марков А.В. Расчет характеристик системы массового обслуживания, функционирующей в полумарковской циклической случайной среде // XV Всесоюзная школа-семинар по

вычислительным сетям,- Тезисы докладов.-. Москва - Ленинград. - 1990,- ч.2.- с.241 - 246.

33. Дудин А.Н., Марков А.В. 0 системе М|М|ш. функционирующей и случайной среде // III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания.- Тезисы докладов.- М,- 1990,- с.177 - 179.

"34. Дудин А.Н., Климзнок В.И. Модель приемника транспорт но;: станции ЛВС как СМО M|G|I|N с выключающимся прибором // III Всесоюзное совещание по распределенным автоматизировании:, системам массового обслуживания.- Тезисы докладов,- М,-1990,- с.81 - 83.

35. Дудин А.Н., Клименок В.И. Оптимизация динамического управления входной нагрузкой в узле информационно-вычислительног сети // Автоматика и вычислительная техника,- 1991,- )Р2.-с.25 - 31.

36. Дудин А.Н., Клименок В.И; Оптимизация управления мультиреш-мной системой типа GIJM|I // Математическое моделирование народно-хозяйственных процессов.- Петрозаводск,- 1990.-с.14 - 21. ,

37: Дудин А.Н.. Халаф Э. Оптимальное гистерезисное управление двухскоростной системой массового обслуживания с инерционны; переклкчением//Анализ и синтез систем массового обслуживали! и сетей ЭВМ.- Тезисы докладов,- ч.1,- Одесса.- 1990.-с.54 - 60.

38. Дудин А.Н. Динамическая реорганизация баз данных в вычислительных сетях при групповом поступлении запросов // Анализ i синтез систем массового обслуживания и сетей ЭВМ,- Тезис: докладов,- Ч.1.- Одесса.- 1990,- с.50-53.

39. Дудин А.Н.', Бенедиктова Л.И. О численной реализации алгорит . ма' нахождения оптимальной стратегии выбора режимов обслужи

вания // IV Всесоюзное совещание по распределенным вычисли тельным системам массового обслуживания.- Тезисы докладов.

И,- I99L- с.221 - 223.