Введение к работе
Актуальность темы диссертации. Научно-технический прогресс в ведущих отраслях народного хозяйства сегодня немыслим без широкого использования возможностей современных высокопроизводительных ЭВМ и математического моделирования. Широкое применение при исследовании процессов в различных технических, физических, экономических, экологических и т. д. системах находят математические модели систем массового обслуживания (СЮ). Крупный вклад в развитие теории массового обслуживания внесли В.В.Анисимоз, Г.П.Башарин, А.А.Боровков, Б.В.Гнеденко,. И.Н.Коваленко, В.С.Королюк, Г.П.Климов, Ю.В.Прохоров, Д.С.Сильвестров, А.Д.Соловьев, А.Ф.Турбин и др. Широко известны также своими работами в области исследования СЬЮ Т.И.Алиев, Л.Г.Афанасьева, A.M.Андронов, П.П.Бочаров, О.М.Брехов, В.М.Вишневский. A.M.Горцев, Э.А.Даниелян, П.И.Ежов, А.М.Захарин, В.А.Нвницкип, В.В.Калашников, Г.А.Медведев, Г.К.Мишкой, А.А.Назаров, А.В.Печинкин, В.В.Рыков, А.Ф.Терпугов, Г.И.Фалин. С.Ф.Япков и др.
Классические модели систем массового обслуживания являются уже довольно хорошо изученными. Состояние теории СЮ к концу 70-х годов отражено в фундаментальном справочнике, созданном большим коллективом авторов под редакцией Б.В.Гнеденко и Д.Кени-га.
Однако в связи с интенсивным развитием многих отраслей экономики и совершенствованием техники актуальным становится исследование все новых систем и процессов, математические модели которых уже не укладываются в рамки классических моделей теории СЮ. Особенно много таких математических моделей возникает при формализации задач проектирования, синтеза w оптимизации функционирования ЭВМ, их узлов и элементов, информащюннот вычислительных сетей (в том числе локальных информационно-вычислительных сетей), современных и перспективных сетей связи. Как правило, элементы таких систем и сетей являются весьма дорогостоящими, - а требования к экономическим показателям их функционирования являются жесткими. Вследствии этого . задача оптимального выбора топологии таких систем (номенклатуры элементов и способа организации их взаимодействия) и оптимального динамического распределения системных ресурсов
между различными потоками запросов пользователей является очень актуальной.
Задача оптимального .распределения системных ресурсов между потоками запросов различных пользователей к настоящему времени решена только для наиболее простых дисциплин разделения ресурсов, таких как статические относительные и абсолютные приоритеты и различные их комбинации, а также различные циклические дисциплины. Решение задачи при более сложных дисциплинах разделения ресурсов наталкивается на непреодолимые аналитические трудности. В такой ситуации разумным выходом является декомпозиция модели функционирования системы в целом на подмодели, описывающие процессы обслуживания запросов различных потоков, анализ характеристик этих подмоделей и, затем, агрегирование характеристик подмоделей в характеристики' модели в целом. При этом, естественно, на этапе агрегирования возникают существенные проблемы взаимной стыковки параметров подмоделей (интенсивносте? потоков, распределений различных времен, стоимостных коэффициентов и т.д.), но в принципе с помощью итерационных процедур, реализуемых на ЭВМ, эти сложности (по крайней мере на прикладном уровне) вполне преодолимы. Известным примером применения такого подхода является исследование систем с циклическик опросом с помощью декомпозиции модели системы на подмоделк систем массового обслуживания с отключающимся прибором (с удаляющимся на отдых прибором, с прогулками и т.д.). Эта иде? является довольно прозрачной, а систематически применил ее t исследованию систем с циклическим опросом Х.Такаги. Ира применении такого подхода и декомпозиции моделей систем, обслуживащих разнородные потоки запросов различных приоритетов, возникают более сложные модели СМО, чем модели СМО с отключавшимся прибором. А именно, модели СМО с управляемы» режимом функционирования (СМО УР) и модели СМО, функционирующие в случайной среде. Системы, функционирующие в случайной среде, і литературе иногда называют СМО ИР (СМО с изменяемым режимої функционирования). Будем называть их так же, хотя, на наш взгля, термин СМО ИР можно было бы употребить и к системам < управляемым режимом функционирования, и к системам функционирующим в. случайной среде. В обоих видах систем имее-место изменение режима функционирования СМО. Разница заключаете; в том, что СМО.УР сама управляет своим режимом функционирования выбирая его динамически в зависимости, например, от числ;
запросов в система, с целью улучшения экономических показателей своего функционирования. В системах, которые далее будем называть СМО ИР, изменение резгннов функционирования происходит в зилу воздействия внешних причин (случайной среды функционирования) и не поддав гея управлению со стороны СМО. Легко видеть, что іри декомпозиции некоторой модели системы с разделением ресурсов '.юдель СМО УР описывает процесс обслуживания приоритетных тотоков запросов, а СМО ИР - потоков запросов, не имэгаих триоритета.
Системы массового обслуживания с изменяемым режимом функционирования обоих видов, и СМО УР, и СМО ИР, находятся в толэ зрения специалистов в области теории массового обслуживания /же более двадцати лет. Обзоры работ в области СМО УР опубликованы В.В.Рыковым; М. и Е. Фаянбергами; Т.Крейблом, \.Гроссом, М.Мэгэзином; Дж.Тегхэмом. Вышеупомянутые СМО с отклю-іаюшимся прибором являются по существу частііьа.і случаем СМО УР с івумя возможными режимами функционирования, в котором при работе :истемы в одном из режимов обслуживания запросов не производит-;я. Всплеск интереса к этим СМО, наблюдающийся в последние годы, )бъясняется, в первую очередь, возможностью использования их, :ак было отмечено выше, для исследования систем с циклическим тросом очередей, особенно, локальных вычислительных сетей СЛЕС) : протоколами доступа типа TOKEN PASSING RING и TOKEN PASSING SUS (стандарты IEEE 802.5 и 802.4). Представление о состоянии іел в исследовании СМО с отключающимся прибором можно составить із обзоров Б.Доши и Дх.Тегхэма. Отметим, что развивается и клас-:ификация таких моделей СМО. К известному разделению по способу іключєния прибора (N-, Т- и D - стратегии) добавилось разделение ю способу выключения прибора (системы с исчерпывающим, ентильным, ограниченным и полуисчерпызаюшш обслуживанием), [асть результатов данной работы также относится к исследованию МО с отключающимся прибором.
Меньше в настоящее время появляется работ по СМО УР более бщего вида, чем СМО с отключающимся прибором. В первую очередь то объясняется большей сложностью их исследования, а также тем, то попытки решения задачи с общих позиций, например, в рамках атематической теории оптимального управления (с использованием ринципа максимума Понтрягина, динамического программирования и . д.), в рамках теории управляемых марковских и полумарковских роцессов, не привели 1С каким-либо существенным результат ам.
Имеющиеся работы, посвященные исследованию СМО УР, носят разрозненный характер и. если не считать монографии К.-Х.Майера*\ посвященной исследованию несколько отличной от нашей и более простой модели СМО УР, в данной работе впервые систематически изучаются модели систем с управляемым режимом функционирования.
Довольно полная библиография по СМО ИР содержится в монографии **'. По-видимому первые результаты исследования СМО ИР содержатся в известной монографии Б.В.Гнеденко, И.Н.Коваленко***'. Соответствующая СМО рассматривается в ней как некоторое обобщение ненадехной СМО типа M|G|I и называется системой с частичным выходом прибора из строя. Заметим, что ненадежные СМО являются по отношению к СМО ИР примерно таким же частным случаем, как СМО с отключающимся прибором по отношению к СМО УР. Их в этом плане объединяет то, что при работе системы в некоторых режимах обслуживание запросов не производится вообще, что существенно облегчает решение задачи. В монографии ***) намечен путь' решения задачи нахождения стационарного распределения суммарной длины запросов в системе типа M|G|I, функционирующей в марковской случайной среде. Для системы с двумя возможными состояниями среды эта задача практически решена. Дальнейшего развития тематика СМО ИР в работах Б.В.Гнеденко, И.Н.Коваленко и их учеников не получила. С начала 70-х годов эта тематика привлекла внимание зарубежных ученых.
Исследование моделей СМО ИР является чрезвычайно актуальным. В первую очередь это объясняется тем, что использование классических, моделей СМО для расчета многих реальных систем, в которых, входной поток и (или) интенсивность обслуживания запросов претерпевают большие флуктуации, может приводить к большим ошибкам. Причиной этих ошибок является то, что при применении классических моделей СМО производится последовательное усреднение по маргинальным распределениям вероятностей состояний . СМО и состояний случайной среды, управляющей Флуктуацией параметров входного потока и обслуживания. Поскольку процессы, характеризующие состояния СМО и среды являются зависи-
»>
Mayer К.Н. Wartesysteme mit variabler bearbeitungsrate /V Lecture notes in economics and systems. Operations research, computer, social science.- Berlin, Be. Heidalbere. New-York.- 1971.- v.ol.- 312 p.
Склярешіч A.H., Скляреаич Ф.К. Вероятностные модели объек-» топ с возможными изменениями - рига; Зинатне.-і989.- 366 с. ріеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания, 'м.: Наука.- 1966.- 432 с.
мыми, применение такого усреднения вместо усреднения по совместному распределению процессов является незаконным. Известен пример, когда использование классических моделей СМО для анализа процесса передачи данных в цифровой сети интегрального обслуживания (ЦСИО) с гибридной коммутацией, более адекватной моделью которого является процесс обслуживания запросов в СМО ИР, привело к'тому, что полученное значение задержки пакета в сети в 500 раз отличалось от истинного.
Примеры реальных систем. функционирование которых описывается в терминах СМО УР и СМО ИР, будут, приведены ниже. Практическая важность исследования этих систем делает изучение СМО ИР и СМО УР очень актуальнім.
Цель работы и задачи исследований. Основная цель работы состоит в создании комплекса математических моделей СМО УР и СМО ИР, предназначенного для использования при системном проектировании, анализе и оптимизации управления большим классом реальных и перспективных систем, в частности, перспективных информационно-вычислительных сетей; в разработке и совершенствовании методов и алгоритмов исследования их вероятностно-времэн-ных характеристик и оптимизации их функционирования по заданным экономическим критериям, а также в создании комплекса программных средств, реализующих разработанные алгоритмы.
Сформулированная цель предопределяет следующие задачи исследований : v
-изучение класса моделей СМО типа M|G|I и М|М|со, функционирующих в полумсфковской случайной среде и среде типа процесс гибели и размножения;
исследование моделей СМО типа M|G|I с управляемым режимом функционирования, свойств оптимальных стратегий управления ими и зависимостей параметров оптимальных стратегий от основных параметров СМО;
исследование моделей многолинейных марковских СМО, системы с повторными вызовами и СМО типа GI|M|I с управляемым рекимом функционирования;
создание комплекса программных средств для расчета характеристик вышеперечисленных моделей СМО и синтеза оптимальных стратегий управления ими.
Методы исследования базируются на аппарате теории вероятностей, теории массового обслуживания', дифференциальных уравнений, теории функций комплексного переменного, методов оптимиза-
шли.
Научная новизна. Впервые:
найдены характеристики СМО, функционирующих в полумарковскоп случайной среде;
проведено обстоятельное исследование математической модели передачи данных в ЦСИО в режиме гибридной коммутации с плавающим порогом или а&аптивноп коммутации;
-исследованы немарковские модели СМО, функционирующих -в синхронной случайной среде;
проведено систематическое комплексное исследование систем массового обслуживания типа M|G|I и М|М|п с управляемым режимом функционирования при учете наличия различных видов штрафов, немгновенности и инерционности переключения, надежности, отсутствия информации о состоянии системы и т.д.;
рассмотрены модели управляемых СМО с рекуррентным входным потоком и с повторными вызовами.
Практическая значимость работы и внедрение результатов
исследований.
Содержание данной работы во многом определилось потребностью адекватного описания процессов обработки информации в ЦСИО,' ЦСИО - по общему признанию (см., например, тематический выпуск журнала "Автоматика и вычислительная техника" 1991, Н) -магистральный путь развития средств электросвязи в мире в ближайшие десятилетия. Развитие ЦСИО обусловлено, во-первых, ростом объемов дискретной информации, передаваемой по сетям связи; во-вторых, преимуществами цифровых методов передачи и коммутации; в-третьих, достижениями в областях техники цифровой многоканальной связи, микроэлектроники и вычислительной техники. ЦСИО предназначается для передачи посредством единых технических средств массивов самых разных видов информации - речи, интерактивных данных, файлов ЭВМ, больших массивов данных, телефакса, факсимиле и т.д. Различные виды информации имеют различные требования к характеристикам процесса их передачи. Обилие видов передаваемой информации, разнобой и противоречивость в требованиях к характеристикам делают задачу проектирования таких сетей и управления их работой чрезвычайно сложной. Сложность возникает и на этапе разработки концепции сети и критериев оценки эффективности, и на этапе топологического проектирования, и на этапе организации управления потоками в сети, и на этапе анализа и синтеза
алгоритмов коммутации. При решении задач двух последних этапов активно используются модели СМО. Классические модели СМО довольно неплохо опнсьвают процессы передачи информации в традиционных (неинтегральных) сетях связи, а также в ЦСИО при использовании традиционных режимов коммутации - коммутации пакетов и коммутации каналов - и режима гибридной коммутации с Фиксированным порогом. При исследовании процессов передачи информации в ЦСИО с использованием перспективных режимов -гибридной коммутации (см.., например, книгу С.И.Самойленко*'), потребность адекватного описания процессов передачи математической моделью неизбежно приводит к необходимости исследования СМО УР и СМО ИР. Соответствующие модели возникают при описании функционирования сети и на канальном, и на сетевом, и на транспортных уровнях эталонной модели взаимодействия открытых систем. Вопрос о выборе оптимального режима коммутации в ЦСИО в настоящее время остается открытым. Решение его зависит во многом от решения технических проблем (например, создания эффективного гибридного узла коммутации, обеспечения синхронизации и т.д.), но в первую очередь - от результатов анализа экономичности функционирования различных вариантов ЦСИО. Такой анализ неделим без построения и строгого анализа характеристик процессов передачи информации в ЦСИО, что, в свою очередь, диктует необходимость исследования СМО УР и СМО ИР. Такая работа проводилась в частности в ОНИЛ МОКС с ПУ Белгосуниверситета по заказам научно-исследовательского института электротехнических устройств ЛНПО "Красная, Заря" (г.Ленинград) и результаты данной диссертационной работы лежат в русле этих исследований. Основные модели, описывающие процессы передачи информации в ЦСКО, это - система M|G|I, функционирующая в случайной среде, система MjM|co, функционирующая в случайной среде, системы M|G|I, GI|M|I и М|Н|п с управляемым режимом работы. Такие модели и исследуются в данной работе.
Другим важным реальнім объектом, при исследовании которого возникают модели СМО УР и СМО ИР, являются системы множественного доступа с предоставлением, ресурсов по требованию. Такие системы являются в некотором скисле гибридными между системами множественного доступа с полным распределением ресурсов и системами со случайным множественным доступом (см.,
Самойленко СИ. Сети ЭВМ.- М.: Наука.- 1986.- 160 с.
например, *) ). По сравнению с полным распределением ресурсов системы с предоставлением ресурсов по требованию обеспечивают гораздо большую эффективность использования ресурса. Преимущество же перед методом случайного множественного доступа состоит в обеспечении гарантированного максимального уровня задержки. Решение задачи оптимального распределения ресурсов сети между пользователями в зависимости от текущего состояния сети возможно лишь в терминах СМО УР.
Практическая значимость результатов работы заключается в следующем.
1. Развитый в работе подход к исследованию систем,
функционирующих в полумарковской среде, позволяет строить и
исследовать гораздо более адекватные математические модели
процессов в реальных системах со значительной флуктуацией
параметров и распределения под влиянием внешних воздействии.
-
Полученная совокупность точных аналитических результатов для расчета характеристик системы типа M|G|I в случайной среде типа процесс гибели и размножения и системы типа М|М|» в случайной среде позволяет точно рассчитывать структурно-функциональные характеристики перспективных сетей связи, а также мокет служить эталоном при валидации и сертификации многочисленных численных методов исследования таких сетей.
-
Разработанная методика исследования систем, функционирующих в синхронной случайной среде, позволяет повысить качество расчетов характеристик протоколов различных уровней информационно-вычислительных .сетей, использующих механизм скользящего окна. В частности, она использована при оценке производительности, максимальной пропускной способности и настройке протокольных параметров станции ЛВС *"Квант-С".
-
Развитая в работе теория систем типа M|G|I и М|М|п с управляемым режимом функционирования открывает широкие возможности для улучшения технико-экономических показателей многих реальных систем, в частности, цифровых сетей интегрального обслуживания, спутниковых сетей связи с предоставлением каналов по требованию и т.д.
-
Намеченный подход к исследованию систем типа GI|M|I с управляемым режимом функционирования позволит существеннс
"' Башарин Г.П., ЕФимушкин В.А. Методы анализа локальных информационно-вычислительных сетей // Итоги науки и тежники. -Сер. Связь,- м.: ВИНИТИ.- 1S88.- г.г.- с.єо - 109.
продвинуться в решении важной задачи динамического управления потоками и ограничения нагрузки в сетях связи. 3. Заложенные в работе основы исследования управляемых систем с повторными вызовами позволили получить совокупность результатов, соторые будут иметь важное значение при решении задачи эптимизации . параметров протоколов управления передачей информации в ЛВС с возможностью динамического реагирования на гекушее значение трафика в сети.
?. Созданная методика расчета характеристик систем с этключаюшимся прибором позволяет точно рассчитывать <арактеристики баз данных в вычислительньк .сетях (что ранее делалось только приближенно) и улучшить экономические показатели їх функционирования.
3. Разработанное на основе полученных в данной работе результатов программное обеспечение для ЕС ЭВМ и ПЭВМ класса'IBM С может найти широкое применение при исследовании и оптимизации пирокого спектра реальных систем и процессов, допускающих интерпретацию в терминах СМО УР и СМО ИР.
Результаты работы использовались при выполнении -осбюджетной НИР )? гос. per. 79015086, работы в рамках гамплексноя программы в области вычислительной техники АН СССР, № и ССО СССР, регламентированной постановлением № 1473 / 146 от 29.12.1980 / 31.12.1980, а также при выполнении ряда (оздоговорных НИР, в том числе с номерами гос. регистрации 31036329; 0I8500III54; 0I8700I5088; 01900009052; 0І9000І3855. Результаты нашли применение в разработках предприятий п/я 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) и др.
Публикации. По теме диссертации опубликовано более 5С работ. Основные результаты диссертации отражены в 39 работах.
Структура и объем работы. Диссертация состоит из 5 глав, списка литературы из 220 наименований. Объем работы 354 страниц, из них основной текст занимает 288 страниц, содержит 39 рисункое и 16 таблиц.
