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

Р Г Б ОД

1 8 Ш 13%

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

На правах рукописи

МОРОЗОВ Евсей Викторович

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

Специальность 05.13.01:- Управление в технических системах

АВТОРЕФЕРАТ

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

Москва - 1996

Работа выполнена на кафедре прикладной математики и кибернетики Петрозаводского государственного университета.

Официальные оппоненты:

доктор физ.-мат. наук, проф. В.В.Калашников,

Институт системного анализа РАН,

доктор физ.-мат. наук, проф. В.В.Рыков,

Академия нефти и газа им. И.М.Губкина,

доктор техн. наук, проф. В.М.Вишневский, ИПУ РАН.

Ведущее предприятие:

Факультет вычислительной математики и кибернетики МГУ им. Ы.В.Ломоносова.

Защита состоится

» /'/' - С^и^Л 1996г. в часов

на заседании диссертационного совета Института проблем управления по адресу:

117806, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ.

Автореферат разослан " // " .

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

С.А.Власов

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

Актуальность тематики.

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

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

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

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

числом узлов (А.А.Боровков, Р.Л.Добрушин, М.Я.Кельберт, Ю.М.Сухов) и т.п. Более детальный анализ удается провести лишь для сетей достаточно простой структуры (например, имеющих два последовательных узла), однако и в этом случае известно немного точных результатов.

Первым и часто основным вопросом при исследовании сетей и особенно в задачах их синтеза является поиск условий эргодичности, выполнение которых обеспечивает работоспособность данной сети, а с практической точки зрения исключает неприемлемо большие перегрузки (или задержки при передаче сообщений по сети). Естественно, что при- переходе к анализу неэкспоненциальных сетей в первую очередь были предприняты усилия, чтобы распространить условия эргодичности (А) на этот более общий случай. Действительно, в 1981 г. Е.ЯиттеНп доказал эти условия для тандемной сети обслуживания, применив разработанный им метод . построения моментов так называемой слабой регенерации (более общей, зем классическая сильная регенерация по Смиту ) для соотбетствующей цепи Маркова.

В 1986 г. А.А.Боровков предложил конструкцию моментов сильной регенерации для общих сетей обслуживания (открытых и замкнутых) с марковской маршрутизацией, входным потоком восстановления и с одноканальными узлами. В работах А.А.Боровкова и С.Г.Фосса было доказано, что условия эргодичности (А) верны для открытой сети и в этом случае. По-существу, аналитическое исследование неэкспоненциальных сетей обслуживания и ограничивается лишь таким (глобальным) эргодическим анализом.

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

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

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

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

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

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

Поиск условий эргодичности (работоспособности) сложных неоднородных сетей остается сложной и чрезвычайно важной проблемой. На это, в частности, указывают результаты, которые недавно получил М.Вгатэоп (1994), правда, для- неоднородных сетей Келли (где маршрут заявки выбирается заранее, а не по ходу ее движения по сети). Оказывается, что ожидаемое условие эргодичности (А), справедливое в однородном случае, здесь таковым не является и не исключает неограниченного, роста очереди в сети.

Вторая основная проблема, которой уделено Енк:.:чние в

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

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

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

Цель данной работы.

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

Методы исследования.

Методы исследования, используемые в диссертационной работе, опираются как на классические результаты теории восстановления, так и на их обобщения, для слабо регенерирующих и однозависимых процессов, доказанные автором работы. Кроме того, используются свойства марковских.цепей, -в т.ч. цепей, возвратных по Харрису,-"метод обновлений", разработанный А.А.Боровковым, различные процедуры стохастического сравнения, геометрические свойства БкСорочнкх траекторий регенерирующих процессов на одном -цикле

Научная новизна.

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

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

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

Значительная часть важных аналитических результатов теории массового обслуживания, таких как формулы Литтла, формула Поллачека-Хинчина, "закон сохранения работы" Клейнрока и др., перенесена на неоднородный регенерирующий узел в эргодической сети.

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

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

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

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

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

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

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

геометрические свойства траекторий регенерирующих процессов на одном цикле регенерации.

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

Практическая ценность.

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

Апробация работы.

Основные результаты работы Неоднократно докладывались на конференциях и научных семинарах в Московском, Белорусском, Петрозаводском, Киевском. и Донецком университетах; в университетах Гетеборга (Швеция), Ольборга (Дания) и Дебрецена (Венгрия), на 10 школах-семинарах по теории массового обслуживания в Белоруссии, на шести семинарах по проблемам устойчивости стохастических моделей, организованных Математическим институтом и Институтом системного анализа РАН (в том числе, трех международных), на двух конференциях по дискретной вероятности (Петрозаводск, 1988, 1992), на международных конференциях по теории вероятностей и математической статистике (Вильнюс, 1985, 1989), на международных конференциях "Coupling and Regeneration" (Петрозаводск, 1992) и "Mathematical Methods and Tools in Computer Science" (Санкт- Петербург, 1994). .

Структур? работы. *

Диссертация состоит из введения, четырех глав, заключения и 1'пискп литературы, содержащего 174 названия. Изложена на »•трянкаах машинописного текста. • *

Далее будем предполагать, что каждая сеть обслуживания

содержит N узлоз (1<Н<«>), а узел 1 включает ш( параллельных

обслуживающих каналов. Времена обслуживания (Я в к_м канале узла 1 являются и.о.р.с.в., причем

ЕЭ' 1 *=Ь =1/д е (О,»), к=1.....т (1)

1 к 1 к 1 к 1

(здесь и далее 1=1..... N, если не оговорено иначе).

Заявки перемещаются по сети в соответствии с маршрутной

матрицей ^Цр^Ц- гДе есть вероятность (мгновенного)

перехода заявки в узел ,) после завершения обслуживания в узле

1 (это и означает марковскую маршрутизацию). Если сеть

замкнута, то в ней циркулирует постоянное число М заявок, а

матрица Р является стохастической. В случае открытой сети

задается кроме того, входной поток в сеть г=[т -Ч- где

п п +1 п 1

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

{Р , . . . , Рон распределения заявок входного потока по узлам

сети (источник входного потока трактуется как узел О).

Вероятность ухода заявки из сети после обслуживания в узле 1*0

равна Р =1~у Р . Матрица Г, дополненная вектор-строкой Р и 1 о I } о

вектор-столбцом [Р ,...,Р ), оказывается стохастической и в

* 10' ' n0

случае открытой сети.

Для описания динамики сети вводятся основные (непрерывные справа) случайные процессы

{ииЬЬ^и), . . . .у^Ш)^, {зиы31(0....,8н(ъ))}1, .

причем

*1и)={1,1ги)_____1>1т (^)|.

И1(Ь)=|и11(Ь).....я1ж (Ъ)|,

где ™ (Ь) есть время ожидания в очереди к к-му каналу узла 1 в момент Ъ, э (Ъ) - незавершенное время обслуживания в момент г,

(в к-м канале узла 1), а _ число заявок, обслуживаемых

к-м каналом из тех, что находятся в узле 1 в момент Ъ.

Величина ^^Х^цс является суммарной интенсивностью к

обслуживания в узле 1. Если каналы узла 1 идентичны (тогда '"'и,2^), то Узел * называемся однородным. Сеть называется однородной, если все ее узлы однородны.

Определение 1. Процесс Х={Х(Ъ))1 называется слабо регенерирующим, если существует вложенный . процесс восстановления .

Т=и +. . ,+а , ]

п О п-1 пЫ

такой, что для каждого пь2 процесс

fx(t), tsT , (Т -Т ) „ 1

^ n n+k n k^lj

не зависит от

•íx(t), t<r , , (Т.....Т )},

1 Т1-1 1 и I

и его распределение не зависит от nal.

Определение 2. Процесс Т называется однозависимым процессом восстановления, если с.в. [а ) неотрицательны, одинаково

П ПС 1

распределены и для любого п

{а ,...,а V и Ja ,a ,...I

О n-lj ^ n + l Ti-f 2 j

независимы, а а и а , вообще говоря, нет.

п п +1

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

В § 1.1 некоторые основные элементы регенеративного подхода к эргодическому анализу иллюстрируются на примере простейшей открытой сети Джексона, когда т =1, а интервалы (т ) и (б'1')

1 и п

имеют показательное распределение с параметрами Ао и ц соответственно, причем,

р^А^^а, (2)

где (А ]" есть решение системы уравнений

Заметим, что {а =Т -Т ) есть н.о.р.с.в., независящие от а .

nn+lnl о

Пусть

(6)

J-0

В' условиях (2) имеет место сходимость по распределению

v(b)*v при t—х» (4)

и мультипликативное представление распределения вектора v (теорема Джексона).

Вложенный процесс Т={Т ] моментов сильной регенерации марковского процесса у(•) определяется так

Т =0, Т =inf(t : t >Т , 1>(О-0), пгО. (5)

О л + 1 к к п к

-Т J"0 есть н.о.р.с.в., i

♦ 1 п 1 г

r(t)=min |тп-Ъ: Tn-t£o|.

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

Еа <», Т <о> п.н. , (7)

I i '

то процесс у( •) с.о. Если же Еа^оо, то

у(t)=фсо при t—*». (8)

Условие (4) влечет с.о. r('), а значит и (7). Это, в частности,

позволяет доказать существование предельного распределения

немарксвского (но сильно регенерирующего) процесса И(-) (§1.1).

В работах A.A.Борозкова и С.Г.Фосса доказано, что условия

эргодичности (2) верны для произвольной открытой сети, где х

есть процесс восстановления, а m н1. Если предположить, что

кроме условия (2) в такой сети выполнено гарантирующее

существование процесса Т условие регенерации

п

P(V £ S'nj>0, (9)

причем, маршрут I=(1,...,R) пересекает сеть, т.е.

Р •••Р >0, (10)

Ol RO

то удается доказать также и (7) (§1.2). Доказательство построено на многократном применении условия (9), что приводит

к оценке

1Р(Т 5 с1|1>(0)=Х)г:Е (11)

хеВ 1

для любого ограниченного множества В и некоторых (зависящих от В) чисел (3<оо и с>0.

Кроме того, в §1.2 приведено новое доказательство соотношений

р =А п Ь /л е\ <1 , (12)

г1. о 1 1 о о 1 ' '

где {п() есть финальные вероятности цепи Маркова, управляемой

матрицей Р, а величина с! ■ имеет смысл средней (потенциальной)

нагрузки для 1-го узла, приносимой поступающей в сеть одной

заявкой. Показано также, что в условиях (2) с вероятностью 1

А =Пт Ь1(Ъ)/Ъ=Ит а (Ъ)/Ъ, (13)

где а((0 есть число обращений заявок в узел 1 в интервале [0,Ъ], а Ь (О - число обращений заявок в узел 1, порожденных заявками, поступившими в сеть в интервале [0,Ъ]. Отметим, что при нарушении (2), второе равенство в (13), вообще говоря, не верно.

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

Теорема 3.1. Если выполнены условия (1) и 5(0)<«о п.н., то процесс 3(•) с.о.

Заметим, что с.о. а( •) непосредственно не следует из теории восстановления из-за наличия в процессе обслуживания "дырок" случайной длины, вызванных простоями обслуживающих каналов. Обозначим

у/ = У V- Ш, V - У V (О, Б = У Б (О.

I /. 1 к Ь и 11с X. I. 1к

* 1 , к 1 , к 1 , к

С. о. процесса Б( • ) (а значит и (Б^) позволяет доказать, что

оба процесса {иг } и С V» ^} (а значит и №(•), уСО) являются с.о.

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

к ы т!

п=1 1=1 р=1

и поэтому с. о. 1>( ■ ) влечет с. о. процесса Ш(-).

Пусть (w , . . . ,w ) есть вектор Кифера-Вольфовица времени

n 1 n m

ожидания n-й заявки в очереди m-каналыюго узла и

Д =max(w -W )=w -w ,' nal. (15)

n ^ ^ ni n J nra n1

Имеет место

Теорема 3.2. В условиях fl) и wlm<0> п.н. последовательность [Л ) является с.о.

п

Теорема 3.2 обобщает "ключевую" лемму из работы Кифера и Вольфовица (1955) на случай неидентичных каналов и любого значения w . Независимость утверждения теоремы 3.2 от характера входного потока дейает ее полезной в анализе сетей.

Данный результат переносится и • на случай непрерывного времени. Пусть (S } =S(k' - времена обслуживания в к-м

nk ncl

канале, к=1.....ш,

n(t)=min Ik: t >t).

k

Теорема 3.3. Если процессы п(-) и [S(k'}m независимы, то

k= 1

процесс {Д ) с.о.

nit) t

Пусть wt(t)- время ожидания в очереди i-ro канала в момент t, Д =тах |и (t)-w (t)|, r(t)=t -t.

t^^'l J* rvtt)

, Теорема 3.4. Если в условиях теоремы 3.3 процесс т(-) с.о., то процесс {At} также с.о.

Заметим, что всо упомянутые результаты из §1.3 верны и для неэргодического узла, т.е. при нарушении условия (7).

В параграфах 1.4, 1.5 показано, что условия (2) являются необходимыми для эргодичности общей неоднородной открытой сети обслуживания. В §1.4 рассматривается случай сильной неэргодичности

max pí>1, (16)

i

когда с вероятностью 1

lim inf v /t>0, lim inf r /t>0. (17)

t-*»

В §1.5 предполагается, что

max (1

и выполнено условие регенерации

R

p(v I sik )

<р>ч

>0, (19)

где к есть некоторый канал узла ре1, р=1,...,Е1. Условие (19) р

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

Теорема 5.1. Если процесс восстановления Т не имеет задержки

(т.е. т1=«1 по распределению), выполнены.условия (18), (19), то

г(Ь)-»1» при t—> ». (20) В условиях теоремы 5.1 -также

ПрИ Ъ-» со,

и поэтому случай (18) называется слабой неэргодичностью.

В §1.5 рассмотрен пример 2-узловой тандемной сети, где нарушены условия эргодичности, т.е.

-7ГГ>-777" "И, (21)

° ЕБ'2' ЕБ'1' 1 1 1

(узел 2 имеет га идеКтичных каналов). Однако показано, что процесс времени ожидания в узле 2 с.о. Таким образом, условие неэргодичности (1&) (и (16)) не позволяет, вообще говоря, точно локализовать те узлы, в которых текущая нагрузка действительно нарастает (в данном примере узел 1 играет роль фильтра, снижая реально поступающую в узел 2 нагрузку до уровня ниже критического).

В §1.6 рассмотрена замкнутая неоднородная сеть с М заявками и условием сильной регенерации

р(з;1'> £ Б * ]>0 (22)

в предположении, что ш =1 и

Р12.--РК1>0. (23)

Условия (22), (23) означают, что любая заявка, выходящая из (одноканального) узла 1, может вернуться в узел 1 по свободным каналам к ,...,кн маршрута 10=(2.....Ю быстрее, чем в узле 1

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

В качестве основного процесса рассматривается марковский процесс Х=(у(Ъ) ,3(0] , моменты сильной регенерации которого задаются так:

Т =0, Т =ш1п/Ъ .г >Т ,Х(2~)={М,0]), П£0, (24)

Оп+1 I к к п к I

где {7а ]- моменты перехода заявок в сети (такую конструкцию

сильной регенерации замкнутой сети с одноканальными узлами рассматривали независимо А.А.Боровков и G Shedler в

предположении min Р >0).

1

Теорема 6-.1. В условиях (22), (23) и Х(0)<» п.н. процесс Т-{Т ] является положительно возвратным.

Доказательство теоремы 6.1 опирается на процедуру разгрузки, состоящую в многократном использовании условия (22) и позволяющую вначале собрать все М заявок в узлах {1)1)1о, а затем — в узле 1, что влечет'

*(t)*-»oo при t—> ■». (25)

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

Pij>Pji>'=0 для всех k-r'i-j (||pjj'|| есть к-я степень матрицы F) , потребовала выделения его в отдельную главу 2. Основная проблема здесь состоит.в том, что известные мажоранты опираются на идентичность обслуживающих каналов узла, и это позвсляет связать время обслуживания как с заявкой, так и с обслуживающим каналом. При неидентичных каналах это невозможно, что потребовало построения новой процедуры стохастического сравнения.

Рассматривается сеть с положительно возвратным регенерирующим входным потоком т°=[т ]и и вложенным ппоцессом восстановления

п О

ß=lß его моментов регенерации, т.е. в обозначении

п 1

Y -х +■••+% , naO, ß =0

П в 0 -1 *о

п п + 1

предполагаются выполненными условия

ßl<a>, Yo<» п.н. , (26)

Е ß <а>, Е У <», (27)

o*i ' о о V

где обозначение Eq (а далее и Р ) относится к случаю отсутствия, задержки у процесса ß.

В §2.1 рассматривается неоднородный m-канальный узел, где (S(k>) есть н.о.р. интервалы обслуживания в к-м канале, а

п п

входной поток г удовлетворяет условию регенерации

min Р (т >S(l), ß -1)>0. (28)

^ О О 1 '1

В качестве основного рассматривается процесс

Х=|х(Ъ)={1>(Ъ) ,и(Ъ) , а также вложенный по моментам прихода

[г ) процесс х=|х вХ(01 .

п ^ п п ] п

Моменты

p(1,=minWn: k=/3 для некоторого pal ,Х =ol, п*0

л* 1 ^ n р k \

(29)

являются моментами сильной регенерации процесса X, а {Т шь„и>)

п п

- моментами сильной регенерации процесса X. Обозначим Х=ЕоЭ1/ЕоУо (интенсивность входного потока),

т

,С 1 )

дГ1/ез;",' m-Xiv

В §2.1 доказано, что если Х(0)=0 и процесс <3 не имеет задержки ("нулевое" начальное условие), то при

л<(1 (30)

процессы восстановления /3е 111) и Т=(Т ] положительно

п п

возвратны.

В §2.2 предшествующий результат перенесен на случай произвольных начальных условий. Вначале рассматривается модифицированный узел обслуживания, получаемый из исходного узла с помощью "независимого" назначения заявок в каналы (с вероятностью и^/Ц в канал к). Доказано, что в модифицированном узле процессы времени ожидания во всех каналах имеют положительно возвратные вложенные процессы моментов регенерации. Отсюда следует

Теорема 2.2. Если Х(0)<ш п.н. и выполнено условие (30), то с вероятностью 1

lim inf 1/t

t-»co

о

I <m}dx >0' (31)

причем сходимость в (31) имеет место и в среднем означает

индикатор события .{•]).

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

некоторый канал модифицированного узла.

Теорема 2.4. В условиях теоремы 2.2 процессы р'1' и Т положительно возвратны.

В §2.3 э^годический анализ распространен на однослойную сеть, характеризуемую условием

РО1>0, Для любого 1.

Прежде всего доказано, что в условиях

X ал Р <ц , (31)

1 0 011' 1

Р (т >3' 3 ' , |3 =1] >0 о[ О 1к *1 J

(32)

для некоторого процессы Xе 1' и X1", описывающие узел 1 в непрерывном и дискретном времени соответственно (это "проекции" X и X на узел 1), являются положительно возвратными регенерирующими процессами (т.е. положительно возвратны соответствующие вложенные процессы восстановления). Затем этот результат перенесен на основные процессы X, X, описывающие всю сеть.

Теорема 3.2. Если Х(0)<>» п.н. и выполнены условия (31), (32), то регенерирующие процессы X и X положительно возвратны.

В §2.4 предыдущий, анализ перенесен на произвольную ациклическую сеть, предварительно разбитую на непересекающиеся слои Ь ,...,ЬП> определяемые следующим образом: Ьо={0),

Ь .Нх: Р >0 для некоторого ¿еЬ , Р =0 для и...иЬ нЬ I,

п +1 ^ .11 п.п "О п п I

П=0, . . . ,11-1.

Т.о.. слой I. образуют такие узлы, куда обязательно поступают заявки из "предшествующего" слоя и могут поступать заявки ' лишь из подсети I/. Затем проводится послойный эргодический анализ с использованием следующего условия регенерации:

Р0Г'Л0>0- (33)

причем вероятность поступления заявки в свободный канал 1 каждого узла р=1,...,И не меньше некоторого Д>0 независимо от состояния узла.

Пусть теперь процесс Х1п) (Х(п)) есть проекция процесса X (X) на подсеть Ъ .

п

Теорема 4.1. Пусть Х<п>(0)<ю п.н., выполнены условия (33), (34) и .

где IX } есть решение системы уравнений I - V X Р .. Тогда

.) j р р j

„ п-1

процессы ХСп>, ХСп> являются положительно возвратными регенерирующими процессами.

Заметим, что при п-й теорема 4.1 содержит условия эргодичности всей сети, и что вложенные процессы моментов регенерации определяются по аналогии с (29).

В §2.5 вводится понятие границы стационарности в ациклической сети. Пусть

л'1'"!,]: Р^'>о для некоторого к|.

Тогда

: Для всех кеН'-"!.

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

В §2.6 доказана теорема устойчивости выходного потока из однородного т-канального узла А, на вход которого поступает N потоков заявок и {-Ь*1 *} - моменты прихода для 1-го потока,

п

1=1,...,Л.

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

п

где с .в. д'1 1 ¡=0, а

^ п»к п \ к (кап

независимы при любом п. Положим

A(t)=£ I п

С 1 ) к

Пусть J^ (J ) есть момент начала n-го по счету обслуживания, а К (К ) - момент его окончания в узле А (А) .

П 11

Теорема 6.1. Для каждого nil

J a J з J +Д ,

n n n n

К з К s К +Д

n n П n+W-1

Пусть b(t) (b(t)> число обслуженных заявок в узле А (А) в интервале [0,t],

Теорема 6.2 (устойчивости). Если 1/(0)<о> п.н. и при t —* а> EA(t)=o(t) (A(t)=o(t) п.н.),

тогда при t —х»

E(b(t)-b(t))=-4t) |b(t)-b(t)=o(t) n.H.j.

В §2.7 теорема 6.2 применяется к эргодическому анализу пост-граничной зоны (лежащей "ниже" G) в тандемной однородной сети. В случае G=[i .Л >« ) этот анализ удается

распространить вплоть до первого после

"перегруженного"

узла, а при G=(i :Л

-Д, )

О

до узла i^+1. При этом величины

{д^ трактуются как интервалы простоя 1-го канала узла 1 . Кроме того, в §2.7 дано независимое доказательство свойства монотонности открытой однородной сети на основе теоремы 6.1.

Глава 3 посвящена эргодическому анализу неоднородных сетей, в которых условия сильной регенерации типа (9), (19), (22), (28), (32), (34) заменяются более слабыми условиями

(36)

для замкнутой сети, и

min IP is11' >S( 1 ') >0, iel ={2, . . . ,F lk о

1

ети, и

s< i )

It > - p =l)>0, iel=[ 1.....R)

°l ° n, 1 J

IP_ |t_ > - ** ■. Pi=l|>0, iel=[ 1.....R) (37)

для открытой ациклической сети с однородным маршрутом I и

п

-го-

ре генерирующим входным потоком т, причем целое rij , lsnjsmi таково, что в (37) Р (•)=0 при замене п на n -1.

О 11

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

В §3.1 замкнутая сеть описывается с помощью возвратной по

Харрису цепи Маркова Х=(Х ), полученной из основного процесса

п

{е(t),S(t)} вложением по моментам перехода заявок в сети.

Теорема 1.2. Если XQ<«> п.н. и выполнено условие (36), то цепь X является положительно возвратной.

Указаны также условия эргодичности цепи X. Отметим, что в рассматриваемой сети сбор всех И заявок в одном узле 1, вообще говоря, невозможен, - и на множестве регенерации й заявки распределены некоторым образом по узлам маршрута I При

этом явно вычислена длина периода обновления X, на которЪм процесс X переходит во множество А с "полным обновлением", -а 'также вероятность такого перехода. Отметим, что из-за зависимости входного потока и процессов обслуживания в замкнутой сети с.о. процесса X доказывается иначе, чем прежде. Именно, используется тот факт, что в любом интервале

дискретного времени [п,п+2М], по крайней мере ' одна и та це заявка начнет и завершит обслуживание. Доказано также, что любое ограниченное множество В состояний X имеет конечную стационарную меру, т.е.

. С„{ I ^[X 6В)}

v п=0 п >

где /З^1'- первый момент регенерации цепи X , . а tp ~ мера регенерации X, сосредоточенная на множестве Д.

В §3.2 описана регенеративная структура слабо регенерирующего

процесса X=ji>(t), W(t), S(t), 5(t)|t в ациклической сети, где

Компонента 5(■) относится ко входному потоку т. При этом, в момент регенерации процесса X, вложенного по моментам входного потока {t ), в узле isl находится п или n -1 заявок. В §3.3

п 11

найдены условия положительной возвратности однородной сети, а в §3.4 они распространены на произвольную ациклическую сеть, предварительно разбитую на слои (L^}. Следует отметить, что обновляющие события (порождающие моменты ffl^1') регенерации основного процесса), обеспечивают поступление в сеть заявок (их число равно длине периода обновления), каждая из которых начинает очередной цикл регенерации т и обслуживается в узлах I "максимально быстро". Это приводит к появлению "обновляющей" заявки, скажем, п-й, которая пересекает сеть по узлам I без ожидания в очереди. Кроме того, все "предшествующие" заявки уходят из сети за время движения n-й заявки по маршруту X, "не соприкасаясь" с заявками с номерами кгп. Это приводит к появлению очередного момента регенерации процесса X за конечное время с некоторой положительной вероятностью, отделенной от нуля равномерно по любому ограниченному множеству состояний X в момент начала описанной процедуры разгрузки сети. Как и ранее это Елечет (25), а затем и (7). В доказательстве нижеследующей теоремы существенно используется конструкция В.В.Калашникова и С.Г.Фосса (1991) вложенного процесса восстановления Т=-(Т )

п

моментов слабой регенерации для первоначально однозависимого

»

основного процесса X в непрерывном времени.

Теорема 4.1. Пусть Х(0)<» п.н., выполнено условие (37) и

• . V*v

Тогда процессы X и X являются положительно возвратными слабо регенерирующими процессами (относительно вложенных процессов восстановления Т и /3( 1 ' = ((3*1' ]) .

п

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

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

Глава 4 посвящена, в основном, локальному анализу неоднородного узла, включенного в положительно возвратную регенерирующую сеть. В §4.1 показано, что каждый "локальный" процесс Х(1> (описывающий узел i) также . является регенерирующим, моменты слабой регенерации (Т<1>) которого

п п

построены в явном виде и, вообще говоря, не связаны с событиями в узле i. В то же время процесс Х11> является однозависимым относительно некоторого вложенного

"естественного" процесса JT(l>"t,*> 1 sTtl>, где {t"') есть

^ n gtI))п п п

п

моменты прихода заявок в узел i, a Z( 1 ' =• iZ' ' ' J^ являются моментами слабой регенерации процесса х"' (вложенного в Х<1) по моментам {t^1 '} ) • Установлено, что все три вложенных процесса являются положительно возвратными одновременно, причем имеет место соотношение

А Е Т("=Е Z(1).

10 1 0 1

Существование процесса (Т^1') позволяет дать неформальную трактовку стационарных распределений как предельных для регенерирующего процесса Х(1>. В то же время доказательство различных соотношений, связывающих предельные распределения характеристик узла i (§4.3), опирается на естественные и прозрачные геометрические связи траекторий процессов Х(1) и X(tl на одном и том же цикле процессов Тс1' и z'1' соответственно.

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

Обозначим

N(t)=min[k: T fct) , A «=t—Т , В =Т -t.

к ' t H ( t ) - 1 t M(t)

Теорема 2.1. Если Т={J - однозависимый процесс восстановления и Tj<m п.н., то с вероятностью 1

lim N(t)/t»l/E Т (=0, если Е Т =м). (38)

Ol Ol

Следствие 2.1. Если однозависимый процесс восстановления Т положительно возвратный, то при t—мо

t), Bt=o(t) п.н., tAt=o(t). (39)

Теорема 2.2. Если Т - однозависимый процесс восстановления, ТО ДЛЯ ЛЮбЫХ р>0, Ь<е>

E|Np(t)| < ». (40)

Теорема 2.3. Пусть X есть некоторый функционал от регенерирующего процесса с , положительно возвратным однозависимим вложенным процессом Т моментов регенерации и, кроме того,

шах |Х( t) | <<о п.н., Е |max|X(t) | |=Д<<».

KT >-t<T '

i i

Тогда с вероятностью 1

lim X(t)/t=A/E Т . (41)

о 1

Процесс X в теореме 2.3 называется однозависимим процессом накопления.

Теорема 2.4. Если Т - однозависимый процесс восстановления, Т <» п.н. и Е0(Т")<о> для некоторого п>0, тогда при t—*» с вероятностью 1

Bt=o(t1/n), At=o(t1/n). (42)

Найдены также условия сходимости в среднем в (38) и (41).

В §4.3 ряд соотношений типа законов сохранения и оценок для моментов, известных ранее при различных условиях для изолированного стационарного (однородного) узла, перенесен на неоднородный ш-канальный узел в сети с регенерирующим входным потоком с интенсивностью Л.

Пусть w4(t) (S (t)) есть время ожидания в очеред!? (незавершенное время обслуживания) в i-м канала в момент t , .4 (Sll>) - время обслуживания п-й заявки (в канале i), а w - ее время ожидания в очереди, и пусть , S^ S, w означают

соответственно слабые пределы и (1;), Б (1) ( при t—>ю) , Б и

11 п

и (при п—»») . Показано, в частности, что для любого к>0

м ■

(43)

(44)

Из (44) при ш=к=1 следует обобщенная формула Поллачека-Хинчима

Еи'^Е^иБ+З2/^. (45)

Доказано также, что для любого хгО

£ (Р(VI*>х) =Х1Е|(У(+3-Х)+-(»1-Х)+|НЬк , (46)

1

£ Р(Б*>х) =ЛЕ|(5-Х)+|. (47)

1

В случае идентичных каналов (с распределением В времени обслуживания) из (46), (47) следует

Р(п">х)вЬ /т, Р(3*>х)вА Г (1-В(у))с1у. (48)

1 X 1 Ш .)

у^х

Положим

йо=Р(1'/=0), Р1=Р(и*=0), 1=1,...,ш.

1

Доказано, что

^Р^^д-А, (50)

1

1Р0=а~р^ог(м~Я)тах ЕЗ^1*. (51)

• _ 1

Кроме того, для рассматриваемого узла доказаны известные формулы Лпттла и "закон сохранения" незавершенной работы К"1->;':нрока (в случае заявок нескольких типов с относительными

1

К)к} - -¿г^Г1^*-}.

приоритетами), а также ряд других результатов.

В §4.4 построена общая конструкция слабой регенерации, реализующая идею разделения "новых" и "старых" заявок на периоде обновления основного процесса в сети. На этом периоде (случайной длины) "старые" заявки покидают сеть без "соприкосновения" с "новыми" заявками, а разделяющий их движущийся "фронт" может проходить как между узлами, так и внутри узлов. Данная конструкция (частный случай которой, использован в главе 3) существенно расширяет класс регенерирующих сетей обслуживания. Общая конструкция . демонстрируется на примере 2-узловой тандемной сети.

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

Заключение и выводы.

В результате проведенного исследования можно сделать следующие основные выводы.

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

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

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

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

5. Доказано, что известные в однородном случае необходимые и достаточные условия эргодичности (А) . справедливы и ■ для неоднородной ациклической сети с регенерирующим входным пото: - Кроме того, доказана необходимость этих условий для

эргодичности общей неоднородной открытой сети.

6. Показано, что значительная часть результатов, известных для изолированного узла (включая формулы Литтла, Поллачека-Хинчина, "закон сохранения" Клейнрока и ряд других конструктивных соотношений и оценок), распространяются и на узлы, функционирующие в неоднородной регенерирующей сети.

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

Публикации.

По результатам диссертации опубликовано 43 научных работы, среди которых 18 статей, 3 научных отчета и 21 тезисы докладов, представленных на 20 научных конференциях и семинарах. Основными публикациями по теме диссертации являются следующие:

1. Е.В.Морозов. Некоторые результаты для процессов с непрерывным временем в системе 01/01/1 с потерями из очереди.I. Весц1 АН БССР, сер. фаз.-мат. навук, 1983, N0 2,. 51-55

2. Е.В.Морозов. Некоторые результаты для процессов с непрерывным временем в системе 01/01/1 с потерями из очереди.II. Весц1 АН БССР, сер. ф1з.-мат. навук, 1983, N0 4, 41-44.

3. Е.В.Морозов. Условия стационарности многоканальной очереди с зависимостью между входным потоком, временем обслуживания и временем ожидания. Докл. АН БССР, 1984, т.28, N0 3, 205-207.

4. Е.В.Морозов. Система массового обслуживания й1/01/т с потерями из очереди и неидентичными каналами. Изв. АН СССР. Техническая кибернетика, 1985, N0 2, 84-90.

5. Е.В.Морозов. Регенерация и критерий стационарности одного класса сетей обслуживания. Тезисы докл. 4-й междунар. конф. по теории вероятностей и математической . статистике, т.2, Вильнюс, 1985. 216-217.

6. Е.В.Морозов. Предельные соотношения для многоканальных гогенерпрующпх очередей с несколькими видами заявок. Докл. АН БССР, 1966. т.30, N0 1. 13-16.

7. £.В.Морозов. Регенерация и критерий стационарности

многоканальных очеоедей, связанных в тандем. Изв. АН СССР. Техническая кибернетика, 1986, No 3, 119-123.

8. Е.В.Морозов. Обновляемость многоканальных очередей. Докл. АН БССР, 1987, т.31, No 2, 120-123.

9. Е.В.Морозов. Одна теорема об устойчивости обслуженного потока. В сб. Проблемы устойчивости стохастических моделей, труды X Всесоюзн. семинара, Куйбышев, КГУ, 1987, 59-64.

10. Е.В.Морозов. Сохранение регенерирующего потока в ациклической сети. В сб. Проблемы устойчивости стохастических моделей, Труды семинара, М., ВНИИСИ, 1988, 115-120.

11. Е.В.Морозов. Критерий стационарности одного класса непуассоновских сетей обслуживания. Изв. АН СССР. Техническая кибернетика," 1988, No 1, 129-133.

12. Е.В.Морозов. О регенеративной декомпозиции ациклических немарковских сетей обслуживания. Тезисы докл. 2-й Всесоюзн. конф. "Вероятностные методы в дискретной математике", Петрозаводск, 1988, с.72.

13. Е.В.Морозов. Обслуживание регенерирующего потока. В сб. Сетеметрия, анализ и моделирование информационно-вычислит. сетей, Куйбышев, КГУ, 1988, 88-94.

14. Е V.Morozov. The ergodicity of closed non-Markov queuaing networks. Internat. Conf. on Stochastic Processes and Their Appl., Abstracts, Hungary, Debrecen, 1988, p.45.

15. Е.В.Морозов. Регенерация по Харрису в сетях обслуживания. Тезисы докл. 5-й Междунар. конф. по теории вероятностей и математической статистике, Вильнюс, 1989, 65-66.

. 16. Е.В.Морозрв. Регенерация замкнутой сети обслуживания. В сб. . Проблемы устойчивости стохастических моделей. Труды семинара, М., ВНИИСИ, 1990, 61-69.

17. E.V.Morozov. A comparison theorem for queueing system with non-identical channels. Lect. 'Notes in Math"., Stability Problems for Stochastic Models, Springei—Verlag, New York, 1993, No 1546, 130-133. '••''.

18. Е.В.Морозов. Регенеративный подход к анализу' пуас.соновских сетей.'Труды 'ПГУ. Прикл. математ. и информатика, вып. 2, Петрозаводск, ПГУ, 1994, 40-53.

19. Е. V. Morozov. Wide sense regenerative processes with'

applications to multi-channel queues and networks. Acta Appll. Math., 1994, 34, 189-212.

20. E.V.Morozov. Regenarative structure of queueing network processes and simulation. Abstract of Internat. Workshop on Math. Methods and Tools in Computer Simulation, Saint-Petersburg State Univ., 1994, 101-102.

21. -E.V.Morozov. Unstability conditions of open non-homogeneous Jackson queueing networks. Abstracts of XYI Internat. Seminar on Stability Problems of Stochastic Models, Hungary, Eger,

1994, p.50.

22. E.V.Morozov. An extended ' regenerative structure and queueing network simulation." Sei.Report, No 1995-08/ISSN 0347-2609, Dept. of Math., Chalmers Univ., Gothenburg, Sweden,

1995.

23. E.V.Morozov. The stability of non-homogeneous queueing system with regenerative input. Sei. Report, No R-95-2021/ISSN 0908-1216, Dept. Math. and Computer Sei., Aalborg Univ., Aalborg, Denmark, 1995.

24. E.V.Morozov. Stochastic boundness of .some queueing processes. Sei. Report, No R-95-2022/ISSN 0908-1216, Dept. Math, and Computer Sei., Aalborg Univ., Aalborg, Denmark, 1995.