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

АКАДЕлШ НАУК СССР ИНСТИТУТ ПРО ЕЛЕ!" ИНФОРМАТИКИ

На правах рукописи БОЧАРОВ Павел Петрович

УДК 681.32:519.2

РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ АНАЛИЗА ОЧЕРЭДЕЙ В СЕТЕВЫХ СИСТШХ С УЧЕТОМ ОтНИЧЕНЮСТИ БУФЕРНЫХ НАКОПИТЕЛЕЙ

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

(Специальность 05.25.01, - Теоретические основы информатики)

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

Москва 1988

Работа выполнена в Ордена Друкбн народов Университете друябк народов имени Патриса Лут.1угл<5ы

Официальные оппоненты: доктор технических наук, профессор

' САДОЙЛЕНКО С.И.,

доктор технических наук, профессор ШЕДАКИН Ю.И.,

доктор технических Еаук, профессор ЩБАКСВ Б.С.

Ведущее предприятие: Ордена Ленина Институт проблем управления (автоматики и телемеханики) Минприбора и AIT СССР

Защита диссертации состоится "_"__ 1988 г.

__час. _мин. на заседании специализированного'

совета Д 003.56.01 при Институте проблем информатики по адресу: Москва, ул.Вавилова, д.30/6.

С диссертацией ыояно ознакомиться в библиотеке Института проблем информатики.

Автореферат разослан "_"__ 1938 г.

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

старший научный сотрудник "То С.Н.1ШШЕНК0

, i " !

ОВЦАЯ ХАРАКТВЙЮТШ РАБОТЫ

¿^{¿"'ЖМгуальность теми диссертации. Развитие систем сбора, хра- -нения, обработки и распределения информации на базе ЭВМ, а такие частичное или полное интегрирование таких систем привели к появлению и быстрому развита» информационно-вычислительных систем и сетей (ИБС). Процесс взаимного проникновения вычислительной техники и средств связи привел к создании ново)' отрасли науки 2 техники - индустрии информатики, являлцойся в настоящее время важнейшей отраслью народного хозяйства.

Становлению и развитию теоретических осноз информатики в значительной мере способствовали ведущие представители отечественной науки: Авен О .И., Александров A.1L, Башарин Г.П., Велихов Е.П., Глушков B.ivl., Гнеденко Б.В., Дородницын A.A., Ершов А.П., Захаров-Г.П., Калашников В.З., Коваленко Z.H., Лазарев В.Г., Липаев В.В., Ыарчук Г.Н., Мельников В.А., 1.'1изин И.А., Михалевич B.C., Наумов Б.Н., Новиков Г.И., Пашкеев С .Д., Поспелов Г.С., Прангишвили И.З., Пугачев B.C., Рыжиков Ю.И., Сашрс-кий A.A., Самойленко С.И., Соловьев А.Д., Семешшга B.C., Ушаков И.А., Харкевич А.Д., Цыбаков B.C., Шемакин Ю.И., Шнепс М.А., Якубайтис Э.А.

Опыт создания и эксплуатации ИБС, квазиэлектронных и электронных Af-fTC я других систем коммутации, широко испльзунцих'микропроцессорную технику, гибких производственных систем и т.п. привел к необходимости прогноза их производительности путем оценки характеристик использования ресурсов, длин очередей и задержек в них. Естественным аппаратом для аналитического моделирования этих систем, позволяющим получить оценки их производительности, служит теория систем и сетей массового обслуживания.

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

- анализ ограниченных очередей в однофазных структурно-сло.т-

ных моделях при общих предполо;хею:ях относительно нагрузки и разработка точных методов oii¿h;.j: показа то лей производительности систем,

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

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

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

Диссертационная работа выполнена в соответствии с планом НИР Университета дружбы на'родов (УДН) по Постановлению Минвуза СССР и АН СССР "О совместных НИР в области Вычислительной техники на I981-1985 гг." Я 1473/146 от 29.12.80/31.12.80 (пп. 4.2.4, 4.2.5, 5,.2 и 10.I), по Координационному плану НИР АН СССР на I98I-I985 гг. от 24.10.81 по комплексной проблема "Кибернетика" (пп. I.13.4.1 и I.I3.4.2), по Координационному плану фундаментальных е цршишдаых исследований АН СССР на 1986-1990 гг. от 5.12.85 по проблема "Ивфорыадаокно-вычколитольше сети" (шифр I.I3.8, пл. I.13.8.2), ва основании которых проводились исследования со гообадсетпш! теаам кафедры ватадЕтальпой штештекн:

"Теория систем и сетей .массового обслуживания и ее приложения к расчету информационно-вычислительных сетей и их компонент" гос.регистрации 01316000893) и "Разработка методов и алгоритмов анализа информационно-вычислительных сетей и их компонентов" (Л гос.регистрации 01860013672), а также по хоздоговорным темам: "Разработка и исследование моделей организации эксплуатации автоматических линий (АЛ) на основе теории массового обслуживания и теории расписаний" (.'5 гсс.регистрации 73051958), выполненной по заказу ЭНИЫС Минстанкопрсма СССР, и "Разработка и анализ датема-тических моделей сети ОКС" (> гос.регистрации 80010704), выполненной по заказу ЦНИИ связи Минсвязи СССР.

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

ъ

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

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

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

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

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

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

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

Научная новизна работы. 3 диссертации осуществлено теоретическое обобщение и решение проблемы, имещей важное народнохозяйственное значение, - проблем разработки комплекса новых методов и средств анализа очередей в сетевых системах с учетом ограниченности К!; исследование осуществлено, исходя из разработанных автором точных численных методов, рекурсивных подходов и методов приближенноЛ декомпозиции, составлящих основу для разработки

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

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

разработаны теоретические основы расчета показателей производительности однофазных моделей с ограниченным общим БН, с исходными распределениями фазового типа, что позволяет унифицировать расчетные алгоритмы и учитывать при практических расчетах вторые моменты исходной нагрузки; возможности разработанной теории показаны при решении задачи расчета необходимого объема Ш концентратора;

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

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

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

оперативной реорганизацией БД, оценка времени переупорядочивания пакетов в узле обработки ИБС, эффективности сквозных протоколов при решении задачи управления потоками в сетях, а такие задачи •оценки вероятностных характеристик функционирования электронных АКТГС с активной периферией и оценки производительности и ритмичности АЛ.

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

Реализация результатов работы состоит

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

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

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

на численные методы теории массового обслуживания и оценки производительности вычислительных систем, а такке при выполнении учебно-исследовательских работ в УДН на базе учебных пособий автора "Однолинейные системы массового обслуживания", УДН, 1985 г. и "Таблицы стационарных характеристик однолинейной системы обслуживания конечной емкости", УДН, 1986 г., и разработанного комплекса подпрограмм для аналитического моделирования сетевых систем с ограниченными БН.

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

Апробация работы. Основные результаты работы были доложены на У1 Международном конгреое по теории телетрафика (ФРГ, Мюнхен, 1970), П,Ш,1У Всесоюзных научно-технических совещаниях

у

С>

по информационным сетям и автоматической коммутации (Москва и 1973; Поста, 1975; Москва, 1981), Всесоюзном научно-техническом совещания по совершенствованию средств автоматической коммутация в 15АСС (Таллин, 1982) г УШГ IX,, X и XI Всесоюзншс школах-семинарах по вычислительным сетя?.". (Звенигород, 1983; Пущино, 1984; Тбилиси» 1985; Рига, 1986), Научно-технических совещаниях по применению математических методов и вычислительной техники при решении народнохозяйственных задач (Гомель, 1986; Гродно, 1987), а такжа ва научных семинарах кафедры вычислительной математики УДН и научных конференциях факультета физико-математических и естественных наук УДК.

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

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

Объем диссертации; 286» стр. текста, 73 рисунка и таблицы, список литературы, включающий 259 работ отечественных и зарубежных авторов, приложения к главам 3 и 4 на 14 стр. и приложение к диссертации, содержащее описание модулей комплекса подпрограмм для аналитического моделирования сетевых систем с ограниченными БН, и таблицы показателей производительности однолинейной системы с ограниченным БН, а также материалы по внедрению результатов диссертации.

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

В юегве являющейся вводной для диссертации, ставятся кон-Яфвтные задает гтатазэ сетевых систем; исследование эффективности

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

алгоритмов диспетчеризация управляющих ЭВМ; расчет необходимого объема Ш концентратора ИВС при заданной вероятности блокировки Ш; оценка производительности АИС с оперативной реорганизацией £Д; оцека времени переупорядочивания пакетов в центре обработки ЙВ'С, когда для дальнейшей передачи пакетов требуется сохранить порядок, принятый в узле отправителе; оценка производительности стартстслного сквозного протокола с СП-повтором и ГВМ-позтором, необходимая при решении задачи управления потоками в сетях; оценка характеристик функционирования электронной АЫ1С с активными периферийными устройствами упразления (ПУУ) и оценка производительности и ритмичности гибкой АЛ. Выделяются классы типовых моделей однофазных и многофазных систем массового обслуживания и открытых сетей очередей, описывакгрюс функционирование широкого спектра реальных сетевых систем с ограниченными БН. Вводятся основные показатели, позволяющие оценить производительность сетевых систем на базе моделей от:ередей.

Предположение ограниченности БН для указанных выше типовых моделей очередей выдвигает на первый план проблему "размерности". В этом случае мало пригодны традиционные метода теории очередей, Позволяющие при бесконечных БН получить ряд результатов, не решая систем уравнений, описывающих процессы очередей. И, следовательно, возникает необходимость в получении решений этих систем уравнений, имевдих, как правило, большой порядок и, вследствие этого, трудно решаемые даже с использованием 53М. Последнее обстоятель-. ство стимулировало разработку численно-алгоритмических методов (рокуррентшх, матрично-рекуррентных и др.) оценки показателей производительности сетевых систем. Подход, направленный на развитие расчетных алгоритмов и сокращение размерности решаемых задач, является определяющим в диссертации.

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

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

При атои рассыатркваютсл как условия бесприоритетного обслужива-вхя, хедвхтвркэушого дисщгплизами обслуживания РСР Б - в по-

*

рядке поступления, ¿СРБ - в обратном порядке я £АЛ/£>ОМ -в случайном порядке, образующими множество дисциплин , так и возможность введения при к. =2 приоритетов четырех типов, составляющих множество дисциплин { . I = 1.2; „/ = 0,2 , где I = I ( I = 2) означает относительный (абсолютный) приоритет при выборе из накопителя, у =0(^=2) означает, что при переполнении накопителя теряется любая заявка (вытесняется неприори- ■ теткая заявка).

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

связывающие эти распределения:

к

Здесь: р(Х/11^7) - стационарная плотность вероятнос-

ти состояния системы, когда на приборе находится -¿-заявка, ее обслуживание длится уже время сс , а очередь характеризуется вектором .. (числом О.), где ^ . - количество -

заявок в очереди, 4-=1,к (<?- —^Г • - общая длина очереди);

Ду - интенсивность потока у -заявок, , а А=21 .

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

заявок В> (6) ■= ¿^Г£>.< С'Ь) . Такой анализ был выполнен и ре-■1-1 -Л

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

Средние значения общей длины очереди и ожидающих -с -

заявок связаны следующим соотношением: % = ^ £ >

Полученные вывода, обобщающие результаты Г.П.Башарина для

экспоненциальных О? Л £ (г ) , -1-1, к , позволяют существенно снизить размерность решаемой задачи анализа беснриоритетных очередей.

На баге рекуррентных формул для распределения общей очереди рассчитываются основные показатели производительности системы, выражения для которых выводятся в главе 2. В частности, выведены соотношения типа форлулы Литтла, позволяющие на основе фоктори-альных моментов • порядка /п. длины очереди () вычислить начальные моменты иТ/г1 порядка /п. времени ожидания . при дисциплине РС Р £ ^

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

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

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

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

Экспериментальный данные для реальных сетевых систем доказывают, что часто исходные потоки ые являются пуассоновскнми, а длительности обслуживания экспоненциально распределенными, т.е.1 хоэЗфщнэнты вариации (КВ) соответствующих распределений могут значительно отличаться от единицы. Однако ыетодов расчета ио-дохаЯ очере.'о8, учктыващих два коиеята распределений, харак-

терпзукщих поток и время обслуживания, до последних лет не существовало..

В у;о 3 разработана вполне законченная теория стационарной очереди к однс;.г/ обслуотвапцему устройству с ограниченным накопителем емкости в достаточно общих предположении, когда ОР интервалов v.v-щ поступлениями заявок А С?'- ) и длительностей их обслуживания являются распределениями фазового типа,

А(х) = i~<ТтеЛХГ, су)

ô (х) - 1- fTeHx Г-, х * о, ß"T= Cs)

допускающими неприводимые РН - представления ( <=>( ,7\) и (ß, M ) порядков -- и /я- соответственно. Здесь О , ¿--7~¿Г , (ßj ? О , j-Tr^ ) определяют фиктивную фазу, с которой начинается процесс поступления (обслуживания) заявки; .Д ( M ) -матрица интенсивноетей переходов гдрковского процесса поступления (обслуживания) заявок по фиктивным фазам; 1 - вектор-столбец из единиц, соответствующей контексту размерности. ФР вида (4) и (5) охватывают класс распределений с КВ как меньшими единицы, так и большими.

Множество возможных дисциплин обслуживания охватывает дис- . циплины {FCF £> , LCF$, &AMJDOM}.

В § 2 этой главы рассмотрен более общий случай, когда процессы поступления и обслуживания зависят от числа заявок, находящихся з системе. При этом соответствующие р/-/ -представления задаются наборам пар (с*Г, ), к — о, Л , и ( fC , M¿ ), k-J¡H » где параметр к отражает число заявок в системе, а ß= 1 . При этом простым преобразованием матриц _Д ^ и M к возможен учет обратной связи как на входе, так и на выхо- • де системы.

Фазовая структура распределений позволяет ыарковизовать ' процесс длины очереди. Пусть p¿0 - стационарная вероятность свободного состояния системы, когда процесс генерации заявки находится на фазе ¿ , i = ití. , и P-tkJ. - стационарная вероятность наличия в системе к заявок, когда процесс генерации (обслуживания) заявки находится на фазе i , í— /, t , (фазе J , j = l,m. ). Определим векторы p¡¡T~(p •••jp¿0)

а

и ihku •'•> Pikm)''')РВт ) ■ ■ • > Plan ) -

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

Ак = (Гы -1) & М,, -Ак б>7 > к = 7/i ,

где через А & обозначено тензорное произведение матриц А и ft . Далее поломил

W0=-(A0o'fr)M~\ WL=7ik 3 к -=

V* - - Хк = -Ак Г;

z •■= qz (wz мх ) сiа г;j 1.

Теорома I. Стационарное распределение { , < - ¿у/? j-представляется в виде

гкт= КтПщ, у • <*>

п - о

где - единстзешюе решение системы уравнений

n:Tz - о7, дг^/. С?)

Такое представление стационарного распределения дает простой и элективный алгоритм расчета характеристик очереди для произвольных моментов времени, в результате которого решение уравнений равновесия (СУР) порядка ¿{MR-*-1) сводится к решению системы линейных алгебраических уравнений (СЛАУ) порядка £. Распределение {р^ } к= O^k} является базовым для получения ряда других показателей производительности системы. В частности , на его основе вычисляются характеристики очереди в моменты поступланая заявок влн охончання их обслуживания.

' f

Пусть ^'(лг,., № - стационарная вероятность того,

что в. момент- ¿'±0- поступления (окончания обслуживания) заявки з системе находится. к заявок и процесс обслуживания (генерации) заявки находится на фазе ^ (фазе.), и - стационарная

вероятность - свободного состояния:системы в момент -¿ — О поступления заявки..

Теорема. 2.. Стационарное, распределение определяется, следующими. выражениями::

= ~к Г"г ?■

= т Ри ГСТ^1У, к - (ф

где Л —интенсивность.потока», а «Я ——Л 1 ;

В'частности,, из теоремы-2 вытекает выражение для вероятное^ ет у! потери заявки,.

5Г= -1— Г) . С9))

Тёореыа 3. Стационарное распределение находится на.

основе соотношений

где -М 1.

Доказательство теорем 2 и 3 основано на использовании- конечных цепей Шркова с полуыарковским управлением и предусматривает возможность обобщения указанных результатов на случай, когда для ФР А(х) вида (4) (или ФР Ь[х) вида (5)) опущено условие о{ I % О , ¿ — £ ,(или /-!^ ъ О , 7^7г> ).

Аналогичные результаты получены для распределений и ЭР^ . Также выведена соотношения, отражающие связь биномиальных моментов длины очереди, наблюдаемой в различные моменты времени. Нужно- заметить» что показатели производительности системе,. определяемые в- различные моменты времени, могут значительно- отличаться друг- от друга- Так* например, когда ФР (4) и (5} являются экспоненциальными,. при вычислении средней длины очереди в произвольный момент времени с помощью той же характеристики,, наблюдаемой в момент £ + 0 поступления заявок,

Г*

для относительной ошибки Л ^ выполняется следующая оценка:

>/-/>, (п)

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

Соотношения (8) и (10) дают возможность также получить выражения для характеристик системы, связанных с ожиданием заявки и выходящим потоком.

Пусть ^(з) - преобразование Лапласа-Стилтьеса (ПЛС) ФР В(х) ,

^а) т(з 1-м) 'г;

а ¿ОМ - ПЛС ФР времени ожидания заявки, принятой в систему. Теорема 4. При дисциплине обслуживания 1-С Р £

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

■Л (1-Я) иг, = ¿¡^ ,

= 2 ¿-г , . (11)

где ( у ) _ начальный (биномиальный) момент порядка V

времени ожидания (длины очереди), а компонент ^ вектора

^ - средняя длина очереди с учетом фазы J обелукивания заявка. +

Далее, пусть ^'^о 1 2 <УСз) - ПЛС ФР

интервалов между выходами обслуженных заявок. Теорема 5. Для рассматриваемой системы

Из соотношения (15) следует, что интенсивность выхода Л р и дисперсия интервалов между выходами находятся из сле-

дующих вышжений:

= л (1- ю,

я* = + х~, т

где 5*^" - дисперсия времени обслуживания.

В главе 3 также получены выражения для ПЛС совместного распределения и ковариации смежных интервалов между уходами обслуженных заявок.

Необходимо отметить, что влияние ограниченности БН на характеристики выходящего потока весьма существенно и может привести к значительным ошибкам, если это не учитывать в расчетах. Так, например, в методе диффузионной аппроксимации считают, что в условиях большой загрузки = сГ& . Однако на примере очереди, когда ФР (4) и (5) - экспоненциальные, в главе 3 показано, что относительная ошибка при таком приближении может быть при малой емкости БН достаточно большой. В частности, при емкости БН Т= I, относительная ошибка составляет 505?.

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

В главе 4 разрабатываются методы и расчетные алгоритмы, составляющие основу для анализа двух очередей к одному прибору с общим ограниченным БН. Предполагается, что поток ± -заявок является рекуррентным с ФР А| ) фазового типа,

1-Цтел-1ССГ, *>о 3 ^Т-= О?)

допускающим неприводимое РИ -представление С , 7*1 ^ ) порядка ¿1 , -¿= 1,2. ФР длительностей обслуживания г. -заявок

также является распределением фазового типа,

с неприводимым РН -представлением {р^ , М^ ) порядка /п. ^ ,

г = 1.2.

Для случая, когда 1 -заявки пользуются -Абсолют н.ым приоритетом с повторением обслуживания для прерванных 2-заявок, раз-

работай матрично-рекуррентпый метод анализа очередей, являхцаЕся комбинацией катрично-алгоритмического подхода, разутого для анализа приоритетных систем в глазе 2, с подходом, предложенным в главе 3, и использующим также метод блочного Hi, -разложения матриц. Полученный расчетный алгоритм дает эффективное решение проблемы "размерности" для данной модели: СУР порядка if [f t- Jim, f f<{z<\?)rn, />] яа основе этого алгоритма сводится к CJIA7 порад-

Для системы с одним прибором и относительным приоритетом, в ^'которой неприоритетные заявки поступают пз бункера (где всегда ■есть заявки, готовые к поступлению) на основе подхода, развитого в главе 3, решешю для стационарного распределения ее состояний получено в обобщенной матрично-мультипликативной форме. Определяемый этим представлением алгоритм такке достаточно прост и эффективен при расчетах. Основным его преимуществом является тот факт, что вместо СУР порядка ^ лог ) на завершающей

стадии алгоритма решается СЛАУ порядка -t i т. .

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

Результаты для модели с бункером и относительным'Приоритетом позволяют выполнить анализ вероятностно-временных характеристик ЛИС с оперативной реорганизацией БД. Здесь приоритетным является поток запросов пользователей, а заявки из бункера моделируют работу по реорганизации БД. Такая система обслуживания может служить также моделью фрагмента сети передачи данных, в.узлах'которой .при отсутствии информационных сообщений осуществляется передача"син-хронизирухцих сообщений.

В данной главе также решается задача на хождения■оценки < времени пороупорядочивания пакетов в узле обработки вычислительной сетя (например, в сетях с архитектурой £/\'А ) на базе модели очереди к двум приборам различной производительности:о общий>ограниченным ЕН емкости i . При этом считается, что входящий;по-

•/.ток-заявок является рекуррентным с ФР вида (4), а длительности..ах .обслуживания.на приборе -L характеризуются ОР вида (18), i= 1,2. ;Обслуживание•заявок производится в соответствии с дисциплиной FCFS.

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

'Генерации заявки и обслуживания (здесь 'к .- число заявок в системе, /L = Д, если на приборе с большей интенсивностью обслужива- • ■ ния находится заявка с номером ¿. , а на другом приборе - заявка с номером J л i <J ,з противном случае П- = 2)'

Пусть Т/П ■■-. мскент выхода заявки »г и

Тогда случайная величина (с.в.) определяет задержку песеупорядочивания заявки, связанную с ожиданием заявки m~i . Для ФР с.з. Л^^ в стационарном режиме, когда т.-*- оо .получены выражения для ПJ1C и начальных моментов. В частности, среднее время переупорядочквания вычисляется на основе - следующего соотношения:

- г tl-^O'ofq ©д£ Ш

Л о

• где Лр - суммарная интенсивность выхода, а /¿¿* •= - А/г 1,

t = 1,2. На основе этих результатов можно произвести расчет оцен-: ки задержки переупорядочивания пакетов в двухканальном: ;цецтре, VQÖ-

• работки вычислительной сети, когда для дальнейшей; передачи-:пакетов требуется сохранить порядок, принятый в.узле-отправителе.

Результаты глав 3 и 4 для однофазных системно, РН-~растра- ' делениями дают возможность учитывать при оценках, показатедей^рро-изводительности два момента исходной статистики -соо.тв&тртвутацих сетевых систем и, следовательно, позволяют повысить--дичестзо.-:их проектирования и эффективность использование.

В главе 5 разработан комплекс методов и,алгоритмрв,¡^основании которых рассчитываются показатели производнтельноеуи многофазных систем. Вначале рассматриваются двухфазные.систеед*о ограниченным промежуточным накопителем емкости Z. с потеряют ила блокировками для трех случаев: с неограниченной очередью на ; входе, с ограниченным входным накопителем и с бункером на входе. . Для первого из этих случаев при экспоненциальной нагрузке и с

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

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

реполнешш промежуточного накопителя с повторением обслуживания на приборе I (дисциплина В 5 ) определяет следующая теорема.

Теорема 6. Максимальная интенсивность выхода для экспоненциальной двухфазной системы с обратной связью и дисциплиной В 5 имеет вид

) о г***/**,

л* =<

° ) /-/а (1-е ) 1)1 ^ , Гг 0)

где % = /¿л/) а /^¿-интенсивность

обслуживания на приборе -¡_ , ^ = 1,2.

Этот результат можно использовать для оценки пропускной способности концентратора вычислительной сети, когда учитывается этап ввода сообщений в Ш.

Заметим, что выражение дом величины Д.'^, в случае блокировки фазы I при переполнении промежуточного накопителя с отключением обслуживания прибора I (дисциплина Ь ) определяется на основе формулы (20), в которой параметр % заменен на -ьь^.

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

Анализ системы с бункером на входе выполнен в предположениях, когда времена обслуживания имеют ФР фазового типа. На ос-

нове матрично-мультипликативного подхода, предложенного в главе 3, разработан алгоритм расчета среднего значения и асимптотического разложения дисперсии числа заявок обслуженных за время t в стационарном режиме функционирования системы. Эти теоретические выводы дают возможность решить поставленную в главе I задачу оценки производительности и ритмичности двухучастковой гибкой АЛ.

Для класса Ш- фазных систем без промежуточных накопителей с потерями или блокировками предложен рекуррентный подход, позволяющий произвести вычисления показателей производительности систем без решения СУР, что существенно сокращает заfрати памяти и машинного времени. Расчетные рекуррентные соотношения обладают хорошей вычислительной устойчивостью и дают корректные результаты для моделей большой размерности. Проиллюстрируем этот подход на случае пи-фазной экспоненциальной системы без накопителей с блокировками и повторением обслуживания. Пусть Л. - интенсивность входного пуассоновского потока, а интенсивности обслуживания на всех приборах одинаковы и равны ц. . Обозначим через Pmttm, .. ¿1) , ij = ОД, j ~ijrri , стационарные вероятности состояний соответствующего марковского процесса и положим У*к ~'k)iРт(Ьт) • гДе символ L £ означает серию £ ,...,{ дайны i , а символом " • " обозначено суммирование по всем значениям аргумента. Имеет место следующая теорема.

Теорема 7. Величины ffmk определяются рекуррентными соотношениями

. rn>,Z } к = 7,/г> ,

= i

гдеß — , а i>t-(Jt) - единичная функция Хевисайда.

На основе этих соотношений вычисляются характеристики системы. В частности, вероятность простоя системы f>m (о т) равна

Рт(0т) = ,

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

На основе теорема Таюг.е-1лсш1б рассчитывать показатели производительности аналогичной системы с неограниченным БН на входе в условиях насыщения, т.е. при критической загрузкеопре--делящей границу значения интенсивности входящего потока,, при .'.которой существует стационарный режим. В этом случае максимальная* интенсивность выхода (гп ) имеет вид

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

^ = (>У1г 1) /—. (2.5))

Для /п -фазной системы без наййййТёйей'й. сР потерями при входном потоке, описываемым распределением Кокса,. & экспоненциально распределенными длительностями обслуживания решена-задача' оптимального размещения приборов минимизирующего 'среднее 'Число' заявок в система. Этот результат сформулирован-'в> следующей теореме.

Теорема 7. Пусть С/г^. ,..., в .(/Л» )' --век-

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

множество всех перестановок множества {■/, „ т} Тогда!

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

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

№

накопителей, так и для различных механизмов блокировок.

Исследуемая сетевая модель содержит М однолинейных узлов с БН конечной емкости II , г-/,/-/ . Предполагается, что поступающий на узел ¿ внешний поток заявок задается его интенсивностью ,Хр х. - КЗ СА (0/1) интервалов между их поступлениями, г ~= /,А/ . Аналогичным образом обслуживание на узле I характеризуется интенсивностью и КВ С& (г ) его длительности, ■¿«/7/? . После оконча1Шя обслуживания на узле ± заявка независимо от состояния сети и ее предыстории направляется на узел,/' (г у ) с вероятностью^^' , -¿^ ^ - у^м , ( 0) либо

с вероятностью 0,- ; погадает сеть. Алгоритм по-

V

ведения заявки при переполнении БН узла ^ описывается одной из дисциплин сопряжения узлов, определенных выше для многофазных систем (дисциплины & , В 5 и I, - потеря заявки).

Основные положения приближенных подходов, основанных т идее декомпозиции и учитывающие два момента распределений для сетей с неограниченными БН были сформулированы М.Райзером и Х.Кобаяши, Е.Геленбе и Г.Пхиолем (диффузионная аппроксимация) и П.Кюном (итерационный подход). Однако развитие этой теории для сетей с ограниченными БН сдерживалось из-за отсутствия необходимых расчетных формул для показателей производительности отдельных узлов сети, позволяющих учесть два момента, описывающих эти узлы распределений. Анализ, выполненный в главе 3, предоставил необходимый для этих целей аппарат.

Для сети с внутренними потерями показатели производительности определяются с помощью разработанной автором итерационной процедуры. Пусть ( //) ) - интенсивность входящего на

узел у (выходящего из узла у ) потока и С^(^) ( ) -

КВ интервалов мезду поступлениями (выходами) заявок на узел J (из узла ^ ), = /, Л/ . Тогда в предположении независимости потоков, циркулирующих в сети, величины Лу и С а ) , , определяется из соотношений

А'/

= +Лс! ,

<7 л— 1 °

где % = Я (с -/).

В диссертации даются также выражения, позволяющие по заданным интенсивности Л и КВ Сд (г ) построить двухпаргмзтрическую ФР фазового типа. Эти.выражения в сочетании с соотношениями (26) и расчетными алгоритмами главы 3 составляют основу итерационной процедуры, по окончании которой на базе вычисленных значений .'Ху и } » , рассчитываются показатели производительно-'

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

Для сети с блокировками и отключением обслуживания разработана итерационная процедура .расчета двух моментов ФР времени пребывания заявки в узле сети с учетом возможных его бл.чнровок. Это позволяет, выполнив дополнительную корректировку параметров входящих на узлы потоков заявок, использовать для расчета характеристик данной сети итерационный алгоритм, предложенный для сети с потеряли. Аналогичный подход используется.для сети с блокировками и повторением обслуживания. В частнооти, в этом случае ПЛС ^¿(Ъ) времени блокировки заявки в узле ъ определяется следующим выражением:

где Уи - вероятность потери заявки на узле ^ (в сети с потерями), £ ¿(з) - ПЛС ФР времени обслуживания заявки на узле -С , а величина ^¿у - вероятность потери заявки рекуррентного потока с ФР (■%) , поступающего на узел ^ с дополнительным потоком заявок от остальных узлов сети.

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

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

<ш

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

В главе 7. в первой части описываются возможности и структу- ■ ра комплекса подпрограмм для аналитического моделирования сетевых систем с ограниченными БН, разработанного на основе результатов диссертации для рассматри..\омых в ней типовых моделей очередей. Комплекс подпрограмм, ориентированный на ЕС ЭВМ и насчитывающий 33 основных модулей на языке С0РТРАН-1У, предназначен для анализа сетевых систем как для предварительных.оценок на этапе проектирования, так и з процессе их эксплуатации и модернизации, а также для иейользования в учебном процессе - при проведении учебно-ис-следоватсльских работ.

Вторая часть главы содержит численные результаты для конкретных задач анализа сетевых систем, выполненные на основе указанного выше ко.-.ишекса подпрограмм на ЭВМ ЕС-1055. Эти результата условно делятся на две группы. В первой из них представлены результаты достаточно обширных численных экспериментов, позволяющие сделать определенные вывода и рекомендации для задач исследования эффективности алгоритмов диспетчеризации управляющих ЭВМ, расчета Щ концентратора ИВС и оценки вероятностных характеристик электронной АМТС с актив ним ПУУ. В частности, для второй из этих за-, дач при исследовании влияния вторых моментов статистики сообщений на вероятность блокировки Ш концентратора показано, что при изменении КВ от I до 4 вероятность блокировки возрастает на несколько порядков. Ко второй группе относятся результаты, носящие иллюстративный характер и демонстрирующие возможность применения раз-' работанннх методов для поставленных в главе I задач анализа сетевых сисгем.

ВЫВ0,!1Н. ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

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

1) однофазных моделей; описывающих функционирование компонентов ИБС и применяемых при оценке эффективности алгоритмов диспетчеризации в управляющих ЭВМ, при проектировании ЕЛ концентратора, при оценке производительности АИС с оперативной реорганизацией БД, при оценке времени переупорядочивания сообщений в узле обработки ИЗС и т.д.,

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

3) открытых сетевых моделей с ограниченными БН, применяемых для оценки показателей производительности как отдельных компонентов ИВС, так и сетевых показателей - длин очередей, времен задержек и др., при оценке вероятностно-временных характеристик электронной АМГС с активной периферией и т.д.

Комплекс разработанных методов и средств направлен на существенное снижение трудоемкости и повышение качества решения проблем проектирования и эффективности использования сетевых систем за счет I) построения на основе экспериментальных исследований более содержательных моделей их функционирования,/2) теоретического анализа алгоритмов распределения их ресурсов' в широком диапазоне изменения структурных и нагрузочных параметров моделей, 3) существенного упрощения расчетов показателей их производительности по сравнению с имитационным моделированием или непосредственным решением систем уравнений, описывающих модель.

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

I. Разработаны теоретические основы анализа очередей в однофазных системах с ограниченными БН, в том числе:

4-У

I) Для нескольких пуассонозских потоков заявок к одному ©б~ служивапцему устройству при произвольной длительности их обслуживания получено свойство инвариантности характеристик очередей относительно бесприоритетных дисциплин обслуживания, что позволило существенно уменьшить размерность решаемой задачи, сведя ее к анализу одной очереди; для расчета показателей производительности системы разработаны рекуррентные формулы и вычислительные алгоритмы, учитывающие возможность введения приоритетов«

2} Построена законченная теория для анализа очереди о исходными распределения:® фазового типа, включающая расче£нне алгоритмы я форьулы для основных показателей производительности системы в условиях стационарного режима.

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

П. Разработан комплекс методов и расчетных формул и алгоритмов для многофазных систем, в том числе:

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

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

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

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

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

1) При расчетах технических характеристик управляющих устройств серийно выпускаемых Н10 Веб квазиэлектронных А1ЛТС и разрабатываемых в ЦНЖС Минсвязи СССР совместно с И10 ВЭ£> цифровых систем коммутации.

2) На этапах проектирования и настройки автоматизированной подсистемы оперативного' обеспечения Госкомгидромета и Гидрометцентра СССР информацией по гидрометеорология и контролю природной среды (СИША-ОКА) во Всесоюзном НИИ Гидрометинформации Мирового центра данных, г.Обнинск.

3) При исследовании функционирования гибких АЛ на1 стадии проектирования и в процессе эксплуатации для установления характеристик производительности, ритмичности и оптимальных межоперационных накопителей вд бснове методики, внедренной в Э1ШСе и других организациях ¡Шсмажсирома1 СССР',

V. Теоретические резужла1® исследований, отраженные в учебных пособиям адаора? (14, 2,4 ], & -гаюке комшгеяге подпрограмм используются в умбйш прбцёй^ й> шщхх и лабораторных работах по курсам, ориентированный" да ййяодо теории массового обслуживания, а также при выполнений учеб'й'б^йе^л'ёжш^ёл^ских работ в Университете дружбы народов.

Внедрение результатов подтверждено документальное

Основное содержание диссертации отраяено в следующих опубликованных работах.

1. Бочаров П.П., Громов А.И. О пуассоновской двухфазной система ограниченной емкости // Метода теории телетрафика в системах распределения информации. - М.: Наука, 1975. - С.15-28.

2. Бочаров П.П., Наумов В.А. Анализ гиперэкспоненциальной двухфазной системы с ограниченным промежуточным накопителем // Информационный сети и их структура. - М.: Наука, 1976. -

С Д68-181.

3. Бочаров П.П., Наумов В.А. О некоторых сиотемах массового обслуживания конечной емкости // Проблемы передачи информации. -1977. - Т.ХШ, вып.4. - С.96-104.

4. Бочаров П.П. Анализ системы M2/G2/i/r с относительными и абсолютными приоритетами // Численные методы решения задач математической физики и теории систем. - 1.1. УДН, 1979. - С.32-43.

5. Бочаров П.П. О пуассоновской многофазной системе конечной емкости с блокировками и переобслуживанием // Теория телетрафика и сети с управляемыми элементами. - М.: Наука, i960, - 0.130-137..

6. Бочаров П.П., Альборес Ф.Х. О двухфазной экспоненциальной системе обслуживания с внутренними потерями или'блокировками // Проблемы управления и теории информации. - i960. - 1.9,,

Я 5. - С.365-379.

7. Бочаров П.П., Рохас Х.П. О многофазной экспоненциальной системе обслуживания с блокировками // Проблемы управления да теории информации. - 1980. - Т.9, 3 6. - С.441-455.

8. Бочаров П.П. Об одной модели обмена информацией меяду буферной памятью ЭЗМ с внешним накопителем // Известия АН ССОР.. Техническая кибернетика. - 1981. - № I. - С.160-166,

9. Bocharov P.P., Alboreo P.J. On two-node exponential queueing network with internal loesea or blocklng // Probiens оt Control and Information Theory. - 19Ö3. - V. 12, H° 4. -

P. 243-254.

10. Башарин Г.П., Бочаров П.П., Спесивов С.С. Об алгоритмическом и программном обеспечении методов аналитического моделирования информационно-вычислительных систем и юс компонентов // Препринт Научного совета по комплексной проблеме "Кибернетика" АН СССР. - М.: ВИНИТИ, 1983.

/'h

II. Бочаров И .П. О некоторых приближенных формулах для системы m/gi/1/г // Модели информационных сетей. - М.: Наука, 1984. - С.83-91.

■12. Бочаров П.П. 0 многофазной системе с потерями // Автоматика и телзмеханика. - 1984. - М 10. - С.60-65.

13. Бочаров П.П. Приближенный метод расчета разомкнутых и неэкспоненциальных сетей ограниченной емкости с потерями // IX • Всесога. школа-семинар по вычислительным сетям // Тезисы докладов. - М.: ВИНИТИ, 1984.-- 4.2. - С.88-94.

14. Бочаров П.П. Однолинейные системы обслуживания конечной емкости. - И.: Изд-во УДН, 1985.

15. Бочаров П.П. О системе массового обслуживания ограниченной емкости с распределениями фазового типа, зависящими от состояния очереди // Автоматика и телемеханика. - 1985. -

№ 10. - С.31-38.

16. Бочаров П.П. Анализ однолинейной системы обслуживания конечной емкости с заявками нескольких видов и дисциплиной

FIFO // Методы теории телетрафика в системах связи и вычислительной технике. - М.: Наука, 1985. - С.51-61.

17. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей ограниченной емкости с блокировками // X Всесоюз. школа-семинар по вычислительным сетям // Тезисы докладов. - М.: ВИНИТИ, 1985. - 4.2. - С.175-180.

18. Бочаров П.П., Литвин В.Г. Методы анализа и расчета систем массового обслуживания с распределениями фазового типа // Автоматика и телемеханика. - 1986. - Jt 5. - С.5-23.

19. Бочаров П.П. О времени ожидания и выходящем потоке в системе рн/рн/1/г // Применение математических методов и вычислительной техники при решении народнохозяйственных задач // Научно-техническое совещание, г.Гомель, 1986 // Тезисы докладов. - Изд-во Б1У, 1986. - С.16-17.

20. Бочаров П.П. О стационарных вероятностях оистемы рн/рн/1/г // Методы теории телетрафика в децентрализованных системах управления. - М.: Наука, 1986. - C.II-23.

21. Bocharov p.P., Speelvov S.S. On multistage queueing system with losses and arriving flow of phase type // Problems

xJj 1

of Control and Information Theory, - 19(36, - V. 15, 11° 6. -Г. 465-474.

22. Бочаров П.П. Анализ выходящего потока в однолинейной системе обслуживания конечной емкости с распределениями фазового типа // XI Всесоюз. семинар по вычислительным оетям // Тезисы докладов. - М.: ВИНИТИ, 1986, - Ч.З. - С.55-57.

23. Бочаров П.II., Спесивов С.С. О моделях очередей о блокировками в вычислительных сетях // XI Всесоюз. семинар по вычислительным оетям // Тезисы докладов. - М.: ВИНИТИ, 1966. - Ч.З. -С.20-24.

24. Бочаров ПЛ., Спесивов С.С. Таблицы стационарных характеристик однолинейной системы обслуживания конечной емкости. -М.: Изд-во УДН, 1986.

25. Бочаров 11.11. Приближенный метод расчета разомкнутых неэкспоненциальных сетей массового обслуживания конечной емкости о потерями или блокировками // Автоматика и телемеханика. - 1987. -» I. - С.55-65.

26. Бочаров П.П. О выходящем потоке системы PU/Pli/1/т: // Модели систем информатики. - М.: Наука. 1967. - С.97-107.

27. Bochnrov I'.r. The nnnlynio of queue length and output flow in flln^le server with finite waiting room and phnne type dintr'butloro// Problenn of Control nnd Information Theory. -

19'-7. - V. 1С, I!0 3. - P. 211-223.

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

В работах [1,6] автору принадлежит постановка задачи и метод решения; в [ 2 J автором разработан рекуррентный алгоритм для расчета показателей производительности двухфазной системы о блокировкам; в [ 3]автору принадлежит постановка задачи и доказательство результатов для двухфазной системы с блокировкам; в [7,9,21J - постановка задачи, метод решения п доказательство

основных результатов; в [Ю ] - описание методов аналитического моделирования информационно-вычислительных систем и юс компонентов; в [18] - вероятностная интерпретация распределений фазового типа к описание алгоритмов для систем о ограниченными Ш; в [ 23 ] - описание основных типов блокировок, применяемых в оатях очередей п адоя приближенного расчета распределения вре-кош оболуяЕвашш заявка в узле сети о учетом блокировок; в [ 24 ] - алгоритм расчета характерготяг. в описание таблиц.