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

у

российский университет дружбы шротов'

На правах рукописи цатшенко Сергей Иванович

УДК 519.2:621.39

анализ шюгоканальшх систбм массового обслуживания

конечной емкости с переупорядочивашем заявок ( 05.13.17 -теоретические основы информатики)

Автореферат

диссертации на соискание ученое степени кандгчата фгаико-математическпг наук

Москва - 1992

\

Работа выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов

Научный руководитель -доктор технически наук, профессор П.П. Бочаров

Официальные оппоненты: доктор физико-математических наук, профессор A.B. Печинкин кандидат физико-математических наук, доцент Е.В. Чепурин

Ведущая организация - Институт проблем передачи информации Российской Академия наук

Защита диссертации состоится "/¿г7" с$ и Св^иР 1993 г. в 15 час. 00 мин. не заседании специализированного совета К 053.22.28 в Российском университете друкби народог.

Адрес: 117923, Москва, ул. Орджоникидзе, 3, факультет физико-математических и естественных наук, ауд.

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

Автореферат розаслаи " ^ " ¿¿иХи/л 1992 г.

/1

Ученый секретарь

специализированного совета ^ В.А. Ефимушкин

кандидат физико-математических нау

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

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

Исследовшше систем с пере упорядочиванием заявок начато сравнительно недавно. Розультати этого исследования пока но дали ответов на ряд существенных вопросов. В частности, до сих пор не получена аналитические розультати, пригодные для расчетов стационарных характеристик систем с пере упорядочиванием заявок, кмещих произвольное количество приборов различной производительности.' Кроме этого, во всех исследованных ранее системах с переупорядочиванием заявок под емкостью накопителя системы понималось максимально допустимое количество заявок в очереди, а одно место в накопителе ставилось в соответствие объему памяти узла коммутации, требуемому для размещения пакета с максимально допустимой длиной. Ясно, что подобный способ модели! Л5ания памяти не учитывает различий мезду длинами пакетов и, следовательно,. не вполне адекватно отражает реальные ситуации, происходящие в узлах сети.

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

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

Целью диссертационной работы является:

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

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

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

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

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

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

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

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

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

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

заявок, ожидающих обслуживания;

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

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

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

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

Реализация результатов работы. Результаты диссертации нашли свое применение при аналитическом моделировании центров коммутации сообщений р рамках хоздоговорной НИР УДН "Разработка методов для оценок показателей производительности центров коммутации сообщений и пакетов сетей коммутации сообщений общего пользования" (государственный регистрационный номер 0188.0021080), выполненной в соответствии с Координационным планом АН СССР фундаментальных и прикладных исследований по проблеме "Информационно-вычислительные сети" (шифр I.13.8) на I986-1990 гг. совместно с Институтом проблем управления.

Апробация работы. Материалы диссертационной работы докладывались на XV. Всесоюзном семинаре по вычислительным сетям (Ленинград, 1990), XXV, XXVI и XXVII на; 'ных конференциях факультета физико-ма-матических и естественных наук Российского университета д1ужби народов (Москва 1990,1991,1992), VIII Белорусской зимней школе-семинаре по теории массового обслуживания (Брест, 1992), а также на научном семинаре кафедры теории вероятностей и математической стат!. тики

Российского университета дружбы народов.

Публикация. По материалам диссертационной работы опубликовано а раооТ,"~йз" них 2 - в центральной печати.

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

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

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

В порной главе исследуется m-канальная экспоненциальная СМО, 2«п«», с оСаиш накопителем ограниченной емкости и переупорядочивани-ом заявок. Описание системы дается в § I главы. Предполагается, что на систему поступает пувссоновский поток заявок с параметром Л. Заявки имеют случайную длину, а длины заявок независимы в совокупности н {^определены по экспоненциальному закону. Бремена обслуживания на приборе j независимы мекду собой, а также не зависят от времени об-слумшашя на других приборах и от длин обслуживаемы* заявок и распределены по экспоненциальному закону с параметром , j «t, m.

Йлкость накопителя система характеризуется двумя параметрами: максимальным числом ъ мест для окидания, г <■00 , и числом U", U>0, ограничивавдим суммарный объем заявок в очереди. Заявка, поступающая на систему, когда в ней находится т+t заявок, или же, когда суммарный объем ожидающие в очереди заявок и данной заявки превышает 1Г, теряется и в дальнейшем не влияет на функционирование системы.

Далее, примем, что p^V.. ^f^rn • а что заявка, имеющая возможность выбора прибора, выбирает из всех свободных приборов тот, который имеет наименьший порядаоаый номер. Заявки выбираются из очереди на обслуживание » порядке их прибытия в систему, т.е. согласно дисциплине FCFS.

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

В дальнейшем рассматриваемая СМО кодируется как M/M/m/(r.v)/rea где буквы гез (сокращение от английского resequence - переупорядочи-

вание) указывают на то, что данная СМО является системой с пореупо-рядочивашшм, а остальные символы кода даются в соотьетствии с обозначениями Кендалла.

(г ,ц- )

н

буфер переупорядочивания

Рис.1, т-канальная экспоненциальная СМО конечной емкости с буфером пероупорядочившшя

В § 2 строится математическая модель рассматриваемой СМО.

Пусть - вероятность того, что поступающая на систему заявка присоединится к очереди при условии, что в момент ее прихода в системе имеется ровно к заявок, к = 0, т*-г. Вероятности определяются через исходило параметры СМО. Далее, вводя величины = , мы сводам анализ очередей в рассматриваемой СМО к анализу очередей в СМО без ограничения на суммарный объем заявок, но на которую поступает пуассоновскиЯ поток с интенсивностью Ак , к=0, т + ч,. в дальнейшем такая СМО кодируется как М(к)/М/т/г/геэ.

Функционирование СМО !1(к)/и/т/г/геа описывается однородным мар— ковским процессом (МП) ХИ), 1*0 , над пространством состояний

хт - и X

_ т

^ = .....'Ч-оГн.

_4

при этом.

-СЛИ ^ 0 , то

х" = {(к,11.....1т-), ь^О.т, ^&=1,т}, К*т,т+г,

где и(X) - функция Хевисайда.

Здесь для некоторого момента времени I: X (к,11,...,1т) , если в системе находится К заявок, к = о, ЦрО означает, что

прибор ^ пуст, в противном случае ¡^ есть номер заявки, обслуживаемой прибором ^ , ^ = 1,т . В дальнейшем подмножество Х^ множества Х*" называется к-ой грутп..^ состояний, К^О, т+1.

Размерность пространства Хт является факториальной л с ростом т быстро возрастает. Кроме этого, определенную сложность представляет введение порядка между элементами Xм. Указанные проблемы модно разрешить, алгоритмизоваз процесс построения пространства -£т,

что позволит использовать ЭВМ как для построения самого пространства состояний, так и для построения матрицы интенсивностей переходов МП Х(1) , в в последствии и для вывода и решения системы уравнений равновесия (СУР). Для этого введем следующие определения.

Пусть - множество различных последовательностей длины из неотрицательных целых чисел.

определение' I. Оператор называется оператором ^ -вставки,

определенным на множестве ^ , если для (ЛоЛ!.---.1-*)' .....

Далее пусть "У - подмножество множества У& мощности ^, ,

.....¿1. "в ^«и;.....

Определение 2. Оператор С. называется оператором вставки, определенным на множестве различ!шх конечных подмножеств множества *У5 , если для ^^у с

......

Определение 3. к-ой степенью Ьк оператора Ь называется оператор, действие которого состоит в к последовательных применениях оператора . к = 1,2,... . Под нулевой степенью оператора L будем по1га-мать токдоственный оператор.

Определение 4. Оператор называется оп«патог м ¿-удаления,

¿ = 1,3, определенным на множестве если дг. • ^»-с,и 1,---Л?)4-

.....

Определим подмножество 'У», множества такое, что для

С-оЛц-среди чисел есть хотя бы одно, неряр-

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

Определение 5. Оператор М называется оператором выделения максимума, определенным на множестве если для (¡.0,14,...,1ь)е у^ М^оЛь—• где £ такое, что ' .

Далее доказываются следущие леммы.

Лемма 1.1. Для любого фиксированного т, т*2,

ГьКС0,0т-к), к-о.т-1, где О^и^О) ;

^•к'Т.т-А. --в раз

(к-щ+ч ,1), Кат, тч-х.

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

Леша 1.2. Порядковый номер п состояния (к,11,...,1П)) в пространстве состояний Хт определяется выражением

ти(к-1.т-1]

и- (туи(к-т)т!>]^ т1_. ♦ 1,

где fHK.li.....О,

(I)

= М(4... к, 14.....¿-.г, п«1г»1т-1,ку.

Здесь и далее (6)^.- число размещений из I по .

В дальнейшем нам потребуется не только формула для вычисления порядкового номера состояния, но и алгоритм обратного А^йствиг -восстановления состояния по его порядковому номеру.

Обозначим через - состояние системы, порядковый номер которого в пространстве ЗСт равен и, и введем последовательность чисел О. 5=0; _

гЧ-1 + '(>лЧ-1 . (2)

Тогда состояние систем можно определить по его порядковому номеру с помощью следуодих двух лемм.

-1

Лемма 1.3. Пусть «€(п„

ц]. где 5 = к+1 , определя-

ются ТПсоотвётствии с (2). Тогда хи£'Хк.

Лемма 1.4. Пусть х„е ОС™ , и пусть определена последовательность-чисел .....5т1п(к т-11 следущими рекуррентными соотношениями:

т-

1 где п„ вычисляется в соответствии с (2);

К1 0 ' к

а*2-"ад

п- п

Тогда хй = (кДь...11т) . где

... С. (О.От*к), к=о, т-1;

4.....1 _

(3)

После алгоритмизации пр. десса построения пространства ССт разрабатывается алгоритм построения матрицы интенсивностей переходов А = л/=|0Ст|. Эта задача решается в 5 3 главы I. Суть

решения состоит в следующем. Сначала строится алгоритм, который для каждого состояния системы определяет условия перехода и состияние

системы, из которого можно перейти в даннное за счет поступления заявки (обозначим этот алгоритм через Е0). Далее строится алгоритм, который для каждого состояния системы определяет условия перехода и состояние системы, в которое можно перейти из данного за счет обслу-кивания на приборе j (обозначим соответствующий алгоритм через Е^), После того, как алгоритмы Ej, о, m , получены, остается для всех номеров состояний системы n, n=I,N, выполнить следующие действия.

1) С помощью Формул (2)-(3) по порядковому номеру и восстановить соответствующее состояние системы .

2) С помощью алгоритма Е0 (алгоритмов Е^, j = i, m ) определить условия перехода , а в случае их выполнения - соответствующее состояние (к4, . <jfc3(K,i.t.....Im)' иэ которого (в которое) можно

попасть в данное (из данного). Здесь через 0ö03Ha4eH0

множество номеров алгоритмов Ej, j = o, m, в которых проверка выполнения условий соответствующего перехода для состояния (K,L1,...,lm) дала г-локительный результат.

3) С помощью формулы (I) определить порядковые номера nj состояний ,i-4m), j £3(k,lt)...,Lml и выполнить следующие операции присваивания: 'mecJD1 ! ann^'-=Pj • 0сли

Ясно, что реализация указанных выше действий позволяет для каждого состояния системы определять соответствующие данному состоянию ненулевые элементы матрицы А . При этом заметим, что алгоритм построения пространства ЗСт таков, что состояния каждой из групп X™ следуют друг за другом, а сами группы упорядочены по возрастанию к, к= о, m+t. Кроме того, переходы МП x("о возможны лишь между состояниями соседних групп (либо за счет поступления заявки, либо за счет обслуживания на одном из приборов). Следовательно, матрица А интен-сивностей переходов МП Х(0 будет иметь блочный трехдиагональный вид.

Далее, все состояния процесса X, 1) сообщатся и Л/ < 00. Следовательно, существует _

lim Р1ВД = *п1грг>,

при этом вероятности рп отличны от нуля и совпадают со стационарными.

Стационарное распределение вероятностей {р^, п = 1,л/} является единственным решением СУР

рт А = от.

ртТ = i ,

(4)

где р -Ср1,...,ры) . а 1- вектор из единиц. \

Решение (4) подучено в § 4 главы I. Для решения использован принцип последовательного вложения марковских цепей1'. Для этого рассматриваются моменты , 5» о, скачков ЮТ ХШ и строится цепь Маркова (ИМ) 1Х£, Ь>0}, вложенная в Х(0 по моментам

Пусть Хм- множество состояний ИМ а в^НуН^М -

матрица переходных вероятностей этой цепи. Очевидно, что £ы совпадает с Хт , а элементы мзтрицы определяются из следующих соотношений :

1о. ы, I

а.

а- ч* .

Далее строится последовательность цепей Маркова -»о) ,

.... {30$, $*о} , вложенных в цепь {Х£( 5*0} путем поочередного исключения элементов множества Х^, начиная с последнего по порядку элемента. Другими словами, множество состояний Хп ЦМ {Х£, 0} определяется по- следующему правилу:

Яг»вЯ»«Л1хп+Л. .....1.

Обозначим через матрицу переходных вероятностей

Ш &*(>} , Элементы матрицы 0И определяются через

эле!ленты матрицы 0.ы, следующими рекуррентными соотношениями1':

П+1 + !

п _ -ЛИ

(6)

И,^ наконец, рассматривается стационарное распределение

ВД (^9, ь«о1 и доказывается следующая _

Теорема 1.1. Стационарное распределение определя-

ется соотношениями

где

Л

«и.

а. »=1-;

(7)

' 1ч

а I = 1, ь , вычисляются в соответствии с (6).

Пранявичюс Г.И. Модели и методы исследования вычислительных систем.- Вильнюс: Моклас, 1982.

Итак, формулы (7) позволяют рассчитать стационарноо распределение да Ь*о1, вложенной в МП XII) по моментам скачков этого процесса. Теперь для получения решения СУР (4) достаточно использовать известные соотношения между стационарными вероятностями состояний МП и состояний ЦМ. влохеннсй в этот процесс по моментам его

скачков. В итоге приходим к следующему результату. _

.еорема 1.2. Стационарное распределение определя-

ется соотношениями

Рп = " ^п ,

где вычисляются по формулам (7).

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

Теорема 1.3. Для любого фиксированного п»1,г,...,л/ матрица 0„ имеет елочный трехдиагональяый вид и все ее элемента, за исключением линь может элементов, стоящих на пересечении двух последних блочных строк и двух последних блочных столбцов, совпадают с соответствующими элементами матрицы Ом .

Теорема 1.3 фактически утверждает, что для вычисления элементов матрицы О м будут использоваться элементы не более чем четырех блоков матрицы , Элементы асе остальных блоков мат-

рицы совпадают с соответствующими элементами матрицы и на

данном этапе вычислений не используются. В свою очередь, элемента матрицы 0М определяются в соответствии с (5) через элементы матрицы А . Таким образом, избранный здесь метод решения СУР (4) позволяет производить генерацию блоков матрицы А поэтапно, по мдре их использования в вычислениях. Другими словами, существует возможность построения алгоритма одновременной генерации матрицы А и расчета стационарного распределения МП Х(4) , что позволяет использовать память ЭВМ оптимальным образом. Данный алгоритм был разработан автором и лег в основу комплекса подпрограмм для расчета стационарных характеристик многоканальных экспоненциальных систем обслуживания с переупорядочиванием заявок.

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

В этой связи в § 5 сила доказана следующая

Теорема 1.4. Стационарная Функция распределения задержки

переупорядочивать в СМО М(к)/М/т/г/геэ определяется выражением

т .

Я^Ш^ > ри,1......

¿&Х-Г1......^^Пи..-^»

4 ^»Ч^'-гт'»!

где

<И-ГП' .....

в - интенсивность выходящего из системы потока, вычисляем« УЛ0 т .

^гй^.х-г'1-г1-

, т.

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

В $ 7 проводится численное исследование показателей производительности конкретных систем. В ходе числешюго исследования, в частности, установлено, что средняя величина и дисперсия задержи переупорядочивания с ростом загрузки р=Л/р » ("^¿♦...♦рт. сначала растут, а затем при достаточно большом р их значения стабилизируются. Кроме этого выявлено, что средняя ^ .держа переупорядочиваю«! в системах с одинаковой суммарной интенсивностью р при равных значениях £ тем выше, чем больше различие мэаду ^, ¿'¿.ю. Эти и другие результаты численного исследования отражены в приводимых в главе графиках и таблицах.

Во второй главе рассматривается двухканальная СМО с накопителем ограниченной емкости, на которую поступят рекуррентный поток заявок с ФР фазового типа А(х),

А(Х)=1-*те 1, Х*0, = с неприводимым РК-предетавлением (2,Л) порядка £ .

Предполагается, что каждая заявка имеет случайную длину, причем длины заявок являются независимыми в совокупности случайными величинами с общей ФР ЭСх). Времена обслуживания заявок на приборе ^ независимы между собой, а также не зависят от длин заявок и имеют общую ФР фазового типа

1-р7ем^1Т, х*0, р;Т- 1,

с неприводимым РН-представлением (^,М^ ) порядка' т^, ¿=1,2.

Как и в предыдущей главе, рассматривается СМО с потерями заявок на входе. При этом емкость накопителя, по-прежнему, характеризуется двумя параметрами: числом * мест для ожидания, и числом и, ограничивающим суммарный объем заявок в очереди.

Далее, без ограничения общности полагается, что интенсивность обслуживания на приборе 2 не превосходит интенсивности обслуживания на приборе I. Заявка, поступающая в свободную СМО, направляется на первый прибор. При наличии очереди действует дисциплина РСРБ.

Также предполагается, что всем заявкам при поступлешш в систему присваивается порядковый номер и требуется сохранение порядка между заявками на выходе из СМО, установленного при входе в нее. Заявки, завершившие обслуживание и паругипщио установленный порядок, накапливаются в Ш.

В соответствии с принятыми ранее обозначениями рассматриваемая СМО кодируется как РН/РН/2/(г,у)/гез.

Второй параграф главы 2 начинается с исследования поступающего на систему потока. Как и в предыдущей главе, определяются вероятности |к , с которыми заявки принимаются в систему при условии, что в момент их поступления в системе имеется ровно к заявок, и рассматриваются интервалы времени между поступлениями заявок в систему, за-верпапдиеся их присоединением к очереди. Известно2', что распределение данных интервалов времени^допускает неприводимое РН-представ-ление (л.А^, где Дк = Д+ А ХТ(А-?К), А = -ЛТ . Данный факт позволяет свести анализ исследуемой СМО к анализу системы без ограничения на суммарный объем заявок, но в которой имеется зависимость процесса поступления от числа заявок в системе. Такая система кодируется как РН(Ю/РН/2/г/гез.

Далее вводится понятие упорядоченности СМО РН(к)/РН/2/г/гез. Считается, что системе, находит'- э в упорядоченном состоянии (упорядочена), если на приборах I и 2 обслуживаются заявки с номерами л/4 и Л/4. н А/4<л/а, в противном случае, т.е. при Ы1>Ыг, система неупо-рядочена. Система также упорядочена (неугорядочена) при наличии в ней одной заявки на приборе I (приборе 2).

Функционирование СЫО РН(Ю/РН/2/г/геа с учетом введенного поня-/ ____£_

^ Бапарин Г.П., Бочаров П.П., Коган Я.А. Анализ очеродей в выделите дал сетях. -М.: Наука, 1989.

тия упорядоченности, а также с учетом вероятностной интерпретации FH-распределения2) описывается однородным Ш над пространством состояний

x-x0+litz:ccKLn.

Здесь подмножество Х0 включает в себя состояния, когда система простаивает, а подмножество ХК-1Л включает в себя состояния, означающие, что в системе находится к заявок, к=1, т.+2, в БП содержится h заявок, и»0 , и система упорядочена, если 1=1, либо неупсрядо-чена, если 1=2. Обозначим

р = Lim PUCUbx}, хеХ, Гж t-t»

и введем векторы

S = L=i'2' П>'°-

где индексы s, , определяют фиктивные фазы генерации и обслуживания заявок на приборах I и 2 соответственно. Далее положим

Лк = -Лк1, к = о, 1*Z, р^-М-1, ¿=1,2;

Координаты вектора р являются стационарными вероятностями состояний системы, не учитывающих содержимое БП. Эти вероятности являются решением СУР

?ТА=Т,

с условием нормировки ' -

рТ Т = 1, (9)

где матрица А* является блочной трехдиагональной с

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

Для решения СУР (8) используется метод блочного иЬ-разложения, что приводит к следующему результату.

Теорема 2.1. Решение СУР (8) представимо в виде

где невырожденные матрицы V* задаются соотношениями

Ам1,к , к=г+г, о,

вектор ро является единственным с точностью до постоянного множителя решением СУР

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

В § 3 главы 2 исследуется задержка переупорядочивания заявок в стационарном режиме работы системы. В частности, доказана следующая Теорема 2.2. Преобразование Лапласа-Стильтьеса (Ш1С) ^Сй)стаци-онарной фр задержки переупорядочивания в СМО РН(к)/РН/2/г/геа определяется выражением

г х*г

? = ^ [ 72 (II р^(и(г^)(Г®©Т) + и(.¿-1МТ® 1 ер,)) + + 71 ^..(ииф^»^«^^-!)^^

где - интенсивность выходящего из системы потока, определяемая по формуле

т

Здесь и далее и®У - тензорное произведение матриц II и V . В 5 4 разрабатыв ;тся рек,гррентный матричный алгоритм для расчета факториальных моментов числа заявок в БП. Для этого вводятся производящие функцни (ПФ)

1=1,г, геС, 12141,

и векторы ^и), аналогичные по структуре векторам р^. рк1.

Далее вводятся обозначения

.....СлЛ

= + х+г, 1=1,2, <>»0,1,1,... .

Заметим, что и"к-ь0 = . к=1, г + 2, и = 2 , а является факториальным моментом порядка >) числа заявок в БП, ^=1,2,... ,

Для определения ^ выводится СУР, в которой учитывается содержимое БП. Затем, переходя обычным образом от СУР к системе уравнений для ПФ и дифференцируя последние ^ раз по Н при Н = 1 и фик-с1фованном 1=1,2 , получаем систему

= «IV . (10) где ^ - " блочная трехди8гональная матрица о абсолютным диагональным преобладанием и блоками, определяемыми явным образом через исходные параметры системы, а = «

0\ К=Ч + 2, 1=1,2,

З'ки'

Для решения системы (10) используется метод блочного Ш>-разло-кекия, что в итоге позволяет получить рекуррентный по ^ алгоритм для расчета >)=1,2,... .

В заключение $ 4 доказана следующая

Теорема 2.3. Средняя величина задержки переупорядочивать бА и среднее число заявок 1Г4 в БП СМО РН(к)/РН/2/г/гез связшш соотношением

Заметил, что соотношение (II) является аналогом известной формулы Литтла.

В 5 б получены выражения для определения вероятности потерь заявок и вычисления начальных моментов числа заявок в системе и в очереди, а также выведен ряд соотношений мваду макрохарзктеристикеми системы, полезных дл контроля вычислений. Кроме этого исследована величина суммарного объема заявок в накопителе ОТО РН/РН/2/(г,у)/гез и доказана следующая

Теорема 2.4. Стационарная ФР Рш суммарного объема заявок в

"РН/Р11/2/(г,у)/гез определяется выражением

"О, х*1Г; г г+2

= + ¿-рТб, Ч1Г), 0<х4о";

к=о Г* к=з Гк к-а к-г »

х>^, ц-

где вх(х)«6<х>, (^(х^С^г-х^С^х), ь=г7г.

о

Завершается вторая глава численными расчетами стационарных показателей производительности СМО РН/РН/2/(г,у)/гез, выполненными с помощью комплекса подпрограмм, разработанного на основе получошшх аналитических результатов.

В третьей главе рассматривается двухканальная ОТО с общим накопителем емкости 1 и с переупорядочиванием заявок в случае, когда на систему поступает в независимых потоков заявок с интенсивностями В - 1, &. Предполагается, что длительности обслуживания заявок различных типов на приборе ^ являются независимыми в совокупности случайными величинами с ФР фазового типа (■(.) ,

с неприводимым РН-представлением (, М^ ) порядка м|, £=1,5 , ^ =1,2.

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

Рассматриваемая система кодируется как Ы&/РН&/2/г/гез.

Функционирование "МО опис"вается однородным МП ХСи , 4.»О , над пространством состояний г %+г

где

Х.ио^гГПСЯ!:

Ч'Л ■ИТ^н».'«-). и*,г, к-2.1^.

Здесь для некоторого момента времени -1 : Х(О=^0) , если в момент Ь система пуста; Х(1) = , I) , если в системе имеется единственная заявка типа , обслуживаемая на приборе I , и при этом процесс обслуживания находится на фазе ХШ = , ¿4)0, если в системе имеется К заявок, при этом в очереди ожидают в порядке их прибытия заявки с номерами потоков Ц,..., С.к , на ^-ом приборе оба-'г;.'ивается заявка типа и обслуживание происходит на фазе ^ , ^=1,2, а индекс ¡- характеризует состояние упорядоченности системы: система упорядочена, если 1=1 и не упорядочена, если 1=2.

В предположении, что интенсивности потоков и обслуживания заявок положительны и конечны, финальные вероятности

рсх) = е«пРти=х}, х^х,

существуют, строго положительны, не зависят от начального распределения, совпадают со стационарными вероятностями и являются решением соответствующей СУР. Вывод СУР осуществлен в § 2 главы 3.

Далее, определим макросостояния системы (К, 61э,1"), 1= 1,2., ¿у=1,1Г)уУ, V = 1,2, К= 2, 1+2, где К означает число заявок в

системе, а индексы имеют прежний смысл. Кроме этого,

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

и введем векторы

р • < р1е4,1 .И.....Р^, т'1, и»;

рТ(к,е1,ег>1)=ср(к,г1,ег,1,1,1),...>р(к,е1,Е1,^, I».

В § 3 главы 3 доказана следующая

Теорема 3.1. Стационарное распределение вероятностей

{рСм.О.....х-.ГГк,

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

к

о = рт<*ЛА,'о П се ,

| I

а координаты вектора р(к, являются репением СУР для СМО с

одномерным пуассоновским потоком интенсивности Л и функцией распределения длительности обслуживания на приборе ] фазового типа с неприводимым га-представлением (р^, Ир порядка т^ , ¿=1,2.

В вероятностном смысле теорема 3.1 представляет собой теорему умножения вероятностей. Данная теорема позволяет выражать решение СУР для исходной СМО через решение СУР для системы, которую в соответствии с принятыми обозначениями следует кодировать как М/Р11/2/г/гез. В свою очередь СМО М/ТН/2/г/гез является частным случаем системы РН(к)/РН/2/г/гез, рассмотренной в предыдущей главе. Поэтому, для расчета стационарных вероятностей состояний СМО М/РН/2/г/гез можно воспользоваться теоремой 2.1, предварительно полагая ЛК = (-Л), к = о,г+г,

На основе стационарного распределения исследуемой СМО в 5 4 получен ряд показателей ее производительности. В частности, доказана следующая

Теорема 3.2. ПЛС г) стационарной ФР задержки пере упорядочивания Е-заявок определяется выражением

. г ь

Орт(ефк--И III [исг-^кГск.ел.о-

с ¿=1 1 ' 14 к=г 1

где интенсивность выходящего из системы потока ¿-заявок, вы-

числяемая по формуле

Кроме этого, в 5 4 получен рекуррентный матричный алгоритм для определения факториалышх моментов числа заявок в БП, а тагам выведены формулы для расчета вероятностей потерь и начальных моментов числа заявок определенного типа в системе и в очереди.

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

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

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

1. Разработаны алгоритмы для расчета' стационарных распределений длин очередей в рассматриваемых СМО.

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

3. Для двухканалышх С).!0 конечной емкости с распределениями фазового типа и переупорядочиванием заявок выведены выражения для ПЯС стационарной ФР и начальных моментов задержки переупорядочивашя, разработан рекуррентный матричный алгоритм для расчета факториальных моментов числа заявок в БЛ, получено соотношение типа формулы Лит-тла, связывающее среднюю задержу переупорядочивашя и среднее число заявок в БП, а также выведено выражение для стационарной функции распределения суммарного объема заявок в очереди.

4. Для двухканальных систем обслуживания конечной емкости с пе-рэупорядочиванием заявок в случае (яюгомерпого пуассоновского потока найдены выражения для ;!ЛС* стационарной ФР и начальных моментов задержки переупорядочивашя заявок определенного типа, получен алгоритм для расчета факториальных моме' 'ов числа заявок в БП.

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

Основные результаты диссертации отражены а следуюсос опубликованных работах:

1. Бочаров П.П., Матвиенко С.И. Анализ'двухкенальпоЯ гкспонотиаль-ной системы обслуживания кокачнсЯ емкости с учетом пэрзупорядочивания заявок // Модели п катода информационных сетей.- М.: Наука, 1990.- С.3-9. "

2. Бочаров П.П., Матюяенко С.И. Анал'.з процесса переупорядочиваю« пакетов в узлах коммутации вычислительных сетей // Тезисы докладов 15-ой Всесоюзной скалы-семинара по вычислительным сетям. Ч.З.- М.: ВИНИТИ, 1990.- С.10-14.

3. Бочаров П.П., Матшенко С.И. 0 трехканалъной экспоненциальной системе обслуживания с конечным накопителем и переупорядочива-ниом заявок // Анализ систем информатики.- М.: Наука, 1991.-С.17-27.

4. Бочаров П.П., Матшенко С.И. Переупорядочивание заявок в многоканальной системе обслуипзания // Тезисы докладов 8-ой Белорусской зимней школы-семинара по теории массового обслуживания.-Кинск: БГ/, 1992.- С.14.

5. Бочаров П.П., Матшенко С.И., Хорхе Булгашш. О даухк анальной1 експонепциальной система кассового обслугзшашш с переупорядочиванием заявок нескольких типов // Тезисы докладов ХШ научной конфоренщш факультета физико-математических и естественных наук.- М.: Издательство УДН, 1991. -С.92.

6. Матюшенко С.И. О многоканальной экспоненциальной системе обслуживания с переупорядочиванием заявок // Тезисы докладов ХШ1 научной конференции факультета физико-математических и естественных наук.- М.: Издательство УДН, 1991.- С.137.

7. Ыатпаенко С.И. Анализ очередей в двухканальной система обслухо:-вания конечной емкости с р а спро де ло ниямн фазового типа и переупорядочившие« заявок // Тезисы докладов ЕСЛИ Научной конференции факультета физико-математических н естественных наук. Часть 2,- и.: Издательство УДН, 1992.- С.81.

8. Наткшенко С.И., Ктгаркмана Дизере, Спеснвов С.С.. О двухканальной экспоненциальной системе обслуживания конечной емкости с ограниченным буфером шреупорядочивания // Тезисы докладов ХХУ111 Научной конференции факультета физико-математических и естест-вензшх наук. Часть 2. - М.: Издательство УДН, 1992.- С.82.

§ /// 1}2"> Подписано к печати. Объем 1.0 п. л. Тир. 100, зак.

ТИПОГРАФИЯ РОССИЙСКОГО УНИВЕРСИТЕТА ДРУЖБЫ НАРОДОВ