Случайные процессы в структурно-сложных системах обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Московский ордена Ленина, ордена Октябрьской Революции ордена Трудового Красного Знамени Государственный университет имени М.В.Ломоносова

Факультет вычислительной математики и кибернетики

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

ФАЛИН ГЕННАДИЙ ИВАНОВИЧ

УДК 519.2:621.39

СЛУЧАЙНЫЕ ПРОЦЕССЫ В СТРУШРНО-СЛОЖНЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ

01.01.05 - теория вероятностей и математическая статистика 05.12.14 - сети, узлы связи и распределение информации

АВТОРЕФЕРАТ

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

Москва 1988

Работа выполнена на кафедре теории вероятностей механико-ш-тематического факультета Московского Государственного университета имени Ы.В.Ломоносова

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

академик АН УССР, профессор В.С.Королю;:

доктор технических наук, профессор Г.П.Башарин

доктор физико-иате^гатичоских наук, профессор В.Ы.Круглов

Ведущая организация - Институт математики Сибирского отделения АН СССР.

Мщ&М /Г

Зенита диссертации состойся в 1 / час. на заседании

специализированного Совета Д.053.05.38 при Московском Государственном университете имени М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, факультет вычислительной теаатики и кибернетики, аудитория .

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

Автореферат разослан » п" МЧА ни г.

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

Совета, доцент ^Ц,---7 Н.П.Трифонов

Актуальность проблемы

Основным объектом-исследования в классической теории массово- • го обслугавания являются изолированные системы относительно простой структуры, в то время как в современных приложениях (к расчету вероятностно-временных характеристик компьютерных и коммуникационных систем и сетей) приходится иметь дело с группами взаимодействующих систем, т.о. с сетями обслуживания или, как мы предпочитаем говорить (поскольку термин "сеть" в приложениях употребляется в более узкой смысле) со структурно-сложными системами. Обычно в инженерной практике, где уже давно отказались от рассмотрения изолированных систем, изучение сетей всякого рода проводится так называемая! * приближенными" методами (вроде метода эквивалентных замен Вилкинсона и Бретинойдера; метода декомпозиции Клейнрока и т.д.), которые не имеют строгого обоснования. Для расчета современных систем пепйпяии и обработ:::: :п:фор;»аЦиИ, киторые чрезвычайно сложны в твхнтксаом отношении и требуют громадных расходов на проектирование, создание и эксплуатацию, это совершенно неприемлемое положение. Развитие теории массового обслуживания в направлении исследования структурно-сложных систем интересно не только с прикладной, но и с чисто теоретической точки зрения, т.к. требует выяснения границ применимости классических методов, их обобщения, разработки новых методов, привлечения идей других математических теорий.

Нала работа состоит из двух частей:

1. Процессы обслуживания в структурно-сложных системах с потерями;

2. Случайные блувдания по кногомернш» целочисленным решеткам.

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

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

их состояния недостаточно указать общее число занятых каналов, а требуется включение некоторых дополнительных параметров. Это приводит х тому, что фазовое пространство процессов, описывающих их функционирование, становится необозримо слоеным; даже численный расчет затруднен (если только система не обладает большой симметрией). Для марковских моделей основы математической теории таких процессов заложили в 60-е годы В.Бенеш чи Г.П.Башаринг; важные результаты получены Ы.А.Шнепсом (асимптотический анализ неполнодоступных схем) и др. В последние годы появилось несколько работ ( В&ътсм

Мъ. Ар1>1. ргс1сх&., 1986, ) по сетям типа на

древовидных графах. К анализу систем типа Л /§-1 с обходными путями и тем более систем типа <?/£ никахих подходов не было вовсе (на самом деле и для марковских систем известно не очень много). Наш подход базируется на следущей идее (восходящей к Бенещу) - фазовое пространство б сложной системы имеет определенную -структуру. Чаще всего мы используем то, что Б является частично упорядоченным множеством, при доказательстве теорем эргодичности важно наличие структуры моноида и т.д.

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

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

I/

'В.Беиеа. Математические основа теории телефонных сообщений. Ы.: Связь, 1968.

^Г.П.Башарин, А.Д.Харкевич, Ы.А.Шнепс. Массовое обслуиившие в телефонии. М.: Связь, 1968.

а

тической физике в связи с изучением газа Лоренца (Я.Г,Синай), как модель теплопроводности (Крзыли и др.) и т.д. Блуздания такого рода впервые рассмотрел В.А.Малышев, который дал необходимые и достаточные условия эргодичности и указал метод расчета стационарного распределения. Частные виды процессов такого рода изучали В.С.Королюк, Хал^ин, Сегал и др. Алгоритмические методы расчета стационерного распределения разрабатывал Ныэтс и его группа. Однако целый ряд принципиальных вопросов не был изучен (достаточно сказать, что не была проведена классификация состояний в неэр-годическом случае).

Нестандартные блуздания в полуполосе w} возникают

при исследовании систем с повторными вызовами. Первые модели повторных вызовов были описаны в 50-е годы ( Wilkinson., Coh-ei-ъ ); соответствуйте результаты в краткой фодае вопити в нззест:=;с -о-;;огра4«и Саати и Гнордана по теории массового обслуживания. Начиная с 60-х годов они интенсивно изучается инженерами (Ионин^Г.Л,, ШнепЛ.А. и его ученики - Степанов5С.Н., Школьный Е.И.; Корнышев D.H., Le QaLl и др.), В 70-60-е годы появился ряд работ математического характера (B-Qieeniei^ 6, CJ-. Redout7 и др.), однако, несмотря на очевидные успехи теории повторных вызовов целый ряд принципиальных задач не был решен, например, не было никаких подходов к анализу асимптотического поведения систем при большой интенсивности повторения (наиболее валзшй предельный переход).

Отношения порядка для мер на Z+ в последние годы интенсивно используются при, исследовании конкретных процессов в сетях Двексона, системах с повторили вызовами, сетях ALOHA , теории перколяцни и др. Однако имеющаяся обцая теория монотонности сто-

^Ионкн Г.Л., Седол Я.Я. Таблицы вероятностных характеристик пол-ноцоступшго пучка при повторных вызовах.М.: Наука, 1970. ^yÜHenc U.A. Снстеггы распределения информации. Ы.: Связь, 1979. 'Степанов С.Н. Численные методы расчета систем с повторными смзовгп!. II.: Наука, 1933.

' Ъ. Q-itM-icuj ■ QuiutU^ systm* with, itiuzniny (adomtis and ikt otcUz o[- t<vncU*n, ouuas. Pft,.T>. Vta.sU. Uni/eviitu ot- Catikvtia, ВггкСгд, /536.

fLedcid. A study ojr i&tiial ^xmiUß fystevu witi ■

AI. Tkesis, liniveisity of. To-wntb, /904.

хаотических моделей (Д.Штойян) для многомерных процессов результатов почти не содержит. Кроне того, при решении многих важных конкретных задач теории сетей (например, в эргодичности сетей МОЙЬ ) не принимались в расчет свойства монотонности, что приводило к весьма громоздким и неэффективным решениям.

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

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

"пуассоновской гипотезы" для больших звездообразных сетей типа и т.д.);

- стационарных распределений блувданий в полосе ¿?+*гЧ

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

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

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

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

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

Приложения. Значительная часть результатов и методов диссертации использовалась при выполнении научно-исследовательских работ "Иатематкческий анализ функционирования программно-управляемых АНТС", "Исследование телефонных систем с приоритетами и повторными вызовают в условиях внедрения програгжно-управляекых AiflC", "Стохастические модели для оценки перспективных систем связи" и др., которые вались на механико-математическом факультете ИГУ и внедрены в соответствующих организациях.

Результаты диссертации составили основу рада специальных курсов по теории случайных процессов, теории массового обслуживания и их прилокеникм, прочитанных в 1982-1988гг. на механико-ка-теиатическом факультете ИГУ.

Результаты и методы диссертации, выдвинутые в ней идеи использовались в Dane работ по топши м»с?е;огс выполненных у нас в стране и за рубежом.

Апробация. Результаты диссертации докладывались на I Всемирном конгрессе общества математической статистики и теории вероятностей ки.Бернулли (Топкент, 1986), 1У Международной Вильнюсской конференции по теории вероятностей и математической статистике (Вильнюс, 1965), Ш и 1У Меедународных семинарах по теории телотрафика (Москва, 1984, София, 1988), Ломоносовских чтениях в 1981-1988гг., ряде других конференций, на семинарах механико-математического факультета МГУ, факультета вычислительной математики и кибернетики МГУ, ЛОНИ АН СССР, институтов математики СО АН СССР, АН ЛитССР, АН УССР, Болгарской АН, Киевского Госуниверситета, ИППИ АН СССР и др.

Публикации. Основные результаты диссертации опубликованы в 34 работах, список которых приводится в конце автореферата.

Структура диссертации. Диссертация состоит из двух глав, содержит 299 страниц текста, библиографии из 20В наименований на 21 страницах.

Глава I разделена на 7, а глава 2 - на 8 параграфов. Нумерация формул и теорем в каядсм параграфе своя. При . ссылках на

другие параграф* одной гз&вы добавляется номер параграфа (например, теорема 3.1 означает теореиу I §3), & при ссыхках на другую главу еще и номер главы (например, теорема 1.3.I означает теорему I §3 гл.1).

Содержание диссертации. В первой глава изучаются процессы обслуживания в структурно-сложных системах с потерями. Нал подход базируется на следующей идее (восходящей в Бенещу (1966))-фазовое пространство \S' сложной системы имеет определенную структуру. Чаще всего мы используем то, что S является частично упорядоченным множеством; при доказательстве теорем эргодичности важно наличие структуры моноида и т.д.

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

Определение I. Структурно-сложная система с потерями задана, если заданы:

1. непустое конечное множество С -множество обслуживавших устройств;

2. непустое монотонно убывахцве подмножество S в множестве всех подмножеств С -множество возможных комбинаций занятых каналов;

3. натуральное число Д/ - число типов вызовов, обслуживаемых системой;

4. отображение S: •G U {&} такое, что

0, S(x,i)ux e S (здесь С' - множество одноэлементных подмножеств С ), S(x,i) определяет, какой канал должен занять поступивший вызов L -го типа ( I -вызов), если в момент его прибытия была занята группа каналов ¿с € S . Если S(x,i)=d, то в состоянии я. I-вызов теряется; если жэ $(x,i}= (a-i для некоторого а« С , то в состоянии х i-вызов принимается на обслуживание и направляется в канал о. , так что : новое состояние есть у = х и (а.) .

Многие результаты гл.1 устанавливаются или иллюстрируется для важного класса структурно-сложных систем - неполнодоступнах

схем (НС) ,

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

подмножеств С , на каэдом из которых задан линейный порядок

НС предназначена для обслуживания /V типов вызовов. Если занята группа каналов л с С , то ¿ -вызов получает отказ или принимается на обслуживание в соответствии с тем,

или нет. В последнем случае вызов занимает наименьший в смысле порядка <• канал из х .

Входящие потоки в рассматриваемые системы описываются последовательностями вида (т*, Т^ , 1Л) , где Т^ - интервал между прибытием п. -го и (н.+0-го вызовов, т? - вреия обслуживания И -го (осли ом будет принят на обслуживание), Ск -тип п -го вызова. Величины Т^, ¿л - являются случайными величинами, заданными на некотором основном вероятностном пространстве (-П-, Р) . Большая часть результатов гл.1 доказана для случая, когда величины Т^, ¿^ независимы в совокупности, Т^ - экспоненциально распределены с параметром <5, Т^- одинаково распределены по закону тдеэт распределение ,..,, (системы типа А1./§1 ).

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

Основное определение I позволяет написать для процесса (пополненного обычным образом остаточными длинами об-слугивания процесса ) рекуррентное соотношение щца

и ^=УС ¿д-Д

где + обозначает объединение (непересекЕщнхся) ынояеетв. 1(А) - индикатор утверждения А ■ произведения иножества Xе С на натуральное число к - это кратныз элемента X в ноновде всех подкнопеств С с операцией объединения.

Хотя употребление в этой равенстве символов + , • в отличном от привычного смысле требует некоторого внимания при

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

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

Теорема I.I.I. Предположим, что последовательность является стационарной в узком смысле, а последовательность (Т^, т^), кроме того, метрически транзитивной. Если Я/ Л к {ы: *' • •+ "Sk-/}i >0 • то распределение последова-

тельности процессов / при

сходится к распределению стационарного по к процесса i^o , - оа<k<-i-°aj такого, что Р( (£)= 0)У О.

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

§ 2 гл.1 посвящен изучению слабозагрувенных систеы типа А% когда суымарная нагрузка Л стремится к нулю. Пусть (-х,у) = 0 , если уф х U ¿а} для некоторого «.= S(x,¿) и » если S(.r,¿)=/a$ , ух и{а) ;

- условная вероятность того, что в состоянии гс. вызов принимается на обслуживание и переводит схецу в состояние у , oífx) = SIZoC(x,tj) , I ос I - число занятых каналов в состоянии х . Основной результат (теорема I.2.I) с помощью метода моно-

тонных траекторий А.Д.Соловьева устанавливает возможность разложения стационарных вероятностей у^х) - Р -г ^ Ь', в виде <Х(х) определяется рекуррентным соотнесением: а(0)-/, а/х) - > \ Му)" (величина а до кяеет смысл вероятности перехода из 0 в х по монотонным траекториям). Эта теорема показывает, что хотя для структурно-сложных систем типа свойство нечувствительности не имеет места, для таких важных классов систем как НС , произвольные системы коммутации со случайным алгоритмом занятия свободных путей и т.д. имеет асимптотическая нечувствительность вероятности блокировки к виду функции распределения времени занятия В(ж) при фиксированном среднем

. Полученное

нами асимптотическое' разложение для вероятности блокировки

, .ч . , -I»

и- ——- ^_^-«м^уачх) + позволяет получить

Г а; |х|=с1

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

В § 3 гл.1 рассматриваются сети типа /М /м с обходными путями. Гра<|ы интенснвностей переходов связанных с ними марковских процессов не имеют сколько-нибудь простой структур! и поэтому дане для простейзкх конфигураций получение-точных аналитических формул - непростая задача.

В связи с этим по аналогии с классическим результатом для неполнодоступных схем кы ставим задачу получения асимптотического разложения средней вероятности блокировки при большой загрузке. Трудность этой задачи в случае сетей связана с тем, что пространство 2 имеет много максимальных состояний, калдоо из которых вносит вклад в соответствующие члены асимптотического разложения, в то время, как в случае неполнодоступных схем Л содержит только одно максимальное состояние. Основной результат 9 3- это следующая

Теорема 1.3.1. При оо средняя вероятность блокировки

Здесь N - общее число каналов сети, Р^ - множество путей, состоящих из I звеньев, для р е Р^ , - прямые каналы,

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

на направление р .

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

чрезвычайно мало.

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

Теорема 1.4.1. Для стационарной вероятности потерь в произвольной марковской структурно-сложной системе справедлива следующая двусторонняя оценка:

где У" - средние стационарные положения точки в процессах рождения и гибели 1С параметрами X' = с£(х), /ц!=п,

Л! -Л.^ахы^сс), «''=*• *

1x1^ И- *

Оценка, даваемая теоремой 1.4.1 является асимптотически точной при большой загрузке для равномерных схем (которые, как известно, являются асимптотически оптимальными). Кроме того, мы проводим численное сравнение точности этих оценок с рекомендуемым существующей теорией расчета равномерных схем методом Е1Р. Из него следует, что метод Е1 обеспечивает меньщую погрешность, Однако вадное обстоятельство заключается в том, что при использовании идеально симметричной схемы мы не иокем контролировать погрешность, в то время, как наша теорема дает гарантированные оценки.

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

Теорема 1.4.2. Пусть задана НС с множеством каналов С » структурой доступности С ? ^» интенсивностями входящих потоко^ Л- , 1?; N , функцией распределения времени обслуживания В(х) , которая принадлежит к типу ЬРИ . Рассмот-

ркя наряду с ней обобщенную НС с параметрами Ь'(^) ~ Ь(*эс), Л, ос'бх,^) . Если системы начинают функционирование в момент t = 0 из пустого начального состояния и при всех 6 £ ЛоС^-) ч) (или № ¿«Сх,у) ), то

(соответственно с^(-Ь)).

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

Несмотря на очевидную пользу асимптотических разложений, оценок и т.п. качественных результатов, ясно, что точные численные данные ногут быть получены только численным решением уравнений статистического равновесия. Однако непосредственное решение этих уравнений невозможно даже для простейших структур ия-*я трономического числа возможных состояний. Тем не менее, во многих случаях прогресс может быть достигнут за счет укрупнения состояний процесса ^(Ь) . Как правило, возможность укрупнения связана с симметрией процесса ^(Ь) . Классический результат в этом направлении выгладит следупцим образом. Назовем автоморфизмом процесса перестановку ф: 5 Б его фазового пространства, сохранявшую интенсивности перехода: а.(Ф(х),<р(у))= а(х,у). Введем отноаение эквивалентности на 5 , считая, что , если существует автоморфизм Я0 такой, что д= сР(х) ; классами эквивалентности х пра этом будут орбиты группы (р автоморфизмов . Тогда процесс снова будет марковским с интен-сивностяыи перехода а(х,1р = 2И л(х,г) . Здесь возможность укрупнения состояний процесса описывается в терминах характеристик самого процесса, в то время как естественнее и удобнее для приложений делать это через симметрию реальной системы, функционирование которой этот процесс описывает. В § 5 эта идея реализуется на примере неполнодоступных схем.

Определение. Биекция у : С -» С - автоморфизм НС , если для каждого с найдется | = ^ (О такое, что и сужениэ

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

Возникающие в связи с эти» группы автоморфизмов включают такие классические группы как четвертая группа Клейна, группа

диэдра и т.д.

Пусть vf : С С - автоморфизм H С . Тогда ^ поточечно передвигает и подмножества С , т.е. естественно задает отображение îf'. S-* S фазового пространства процесса .

Теорема 1.5.1. Если <f. С->С -автоморфизм НС такой, что соответствующая перестановка ^ множества типов вызовов сохраняет интенсивности входящих потоков, то if : автоморфизм процесса ij (V) .

Эта теорема позволяет укрупнить состояния процесса y i классами эквивалентности будут орбиты группы Ç = /у } . Аналогичные утверждения доказаны для НС. со случайным исканием и с повторными вызовами.

В § 6 рассматриваются сети типа M/çi без обходных путей (в частности, если конфигурационный граф сети - дерево).

Отдельно изучаются два случая - сети с централизованным управлением (все каналы на маршруте мецду вызывающей и вызываемой вершинами занимаются мгновенно) и сети с децентрализованным управлением (вызов последовательно занимает каналы на своем маршруте и получает отказ при блокировке одной из промежуточных линий только при появлении на ее выходе). В первом случае основной результат (теорема 1.6.2) утверэдает, что в стационарном режиЫе распределение числа вызадов разных типов в сети p(ïï)~pfnt,.. -, имеет вид: f(E)~ i) у«•! р (о) . Особо подчеркнем, что в этой теореме не "накладывается никаких ограничений на функцию распределения времени занятия (вроде существования непре-

рывной плотности). Во втором случае аналогичный результат (теорема 1.6.3) утверждает, что в стационарном режиме распределение числа вызовов разных типов, находящихся на различных фазах обслуживания, р(н) = f>(hLp , имеет ввд: р(п)" 0 П(йс2д)пУД,1 p(ô), где - среднее время обслуживания вызова ти^а i на j -м ребре его маршрута. Здесь, в отличие от теоремы 1.6.2, ш предполагаем наличие непрерывной плотности у времени занятия (отметим, что теоремы непрерывности позволяют распространить результат и на общий случай).

Следует отметить, что полученные в теоремах 1.6.2 и 1.6.3 "явные" форцулы для р (к) принципиально отличаются от формул Эр-ланга тем,' что статистическая сумма в случае сетей имеет необозри-

ко слсашй вид. Однгэо дхл большее сетей (где эта слошость чувствуется особенно скльно), юутредико потоки является сушами больсого числа редких потоков и происходит упрощение ситуации. На интуитивно« уровне это обстоятельство хоропо понятно и км сироко пользуется в ингакерноЯ практике. Строгое доказательство, однако, требует значительных усилий, В § 7 гл.1 кы даем резенке этой проблема для звеэдообраз1шх сетей тепа М ¡Q-I о стеционарноц реакке фгнкциониро вения.

Теорема 1.7,1. Если число узлов в сети К неограниченно возрастает, то: а) состояния различных линий асимптотически независима; б) вероятность блокировки лиши есть (4f) ( jo - нагрузка, производимая одним узлом); в) число передаваемых сообщений асимптотически норюлый со средккм н дисперсией К(С<+ 4f)/H+Sf- 0/(

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

Во второй главе кзучаатся сети с кокмутецаэй сообщений, пакетов, гибридной коммутацией» Как правило, мы рассматривает! кх ' в более общем контексте как блуддання по кногоиергзг* цолочислен-icra резвткш.

В § I гл.2 iü рассматриваем неправодккые непериодические цепи Ilapsoва ¿¿-(¿¿-¿г¡j-i) с дискретшм временем, фазовое пространство которых является произведением Z+ и некоторого конечного ккогества. Относительно вероятностей перехода

= í 1, и-) ) предполагается ограниченность скачков О,

если |L-jÍ>L п ограниченная однородность по первой коордша-те oi~l крока, быть когет, конечного числа состояний).

IMm щи ¿- i

Пра этом, не нарувая .общности, когко считать, что f%m , «ели L > I , a = ° , если | i. -j | > { . Чтобы с формулировать основные результаты, н=я понадобятся некоторкз дополнительные обозначения. Цусть Р\ h=-1,o, j - матрица рззыерои N*N , образованная вороятностсп перехода pj^ ; Р"^ ozis L » - мзтркца

размером /Vх А/ , образованная вероятностями р^т • Матрица Р является стохастической и ее можно рассматривать

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

ционарное распределение индуцированной цепи,/МЛ= Сд^ - — р средний снос ос^ из точки (С, л), ь ^ У , А -матрица, размером (/V-/)* С Ы-1) , образованная N-1 первыми строками и столбцами матрицы Р-Е , [о.п11<кы - вектор

Теорема 2.1.1. Цепь зргодична, возвратная нулевая

или невозвратная в соответствии с тем, величина ¿И отрицательна, равна нулю или положительна.

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

Теорема 2,1.1. Пусть ^ = (а^, у^) - "двумерная" цепь с фазовым пространством * {•),,..,л} такая, что

1. существуют »/>„*, ;

2. Существует неотрицательная функция ё- и величины М^ такие, что ^ ^п. (кроме, бить может, конечного чийла состояний).

Если <ЕГ /Ч^ <о , то цепь - эргодична.

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

IГЬ £

лышевым, расчет сводится к вычисления нулей Т>(х) =

= c¿et (х1'Р+,-+з:(р0-е)-г Р'1) в единичном круге

и при выполнении условия эргодичности Т>{х) юеавт простой нуль в точке а: и N-1 нулей внутри этого круга. В более частных предположениях, которые тем не менее часто выполнены на практике, можно локализировать нули гораздо эффехтшное.Имея в виду подобные прикладные задачи, мы изучаем алгебраическими методами вопрос о действительных корнях уравнения Тз О) = о . Именно, рассматривается случай, когда из внутренних (по первой коор-

дкиате) точех полуполосы Z+y {l,..., А/} переходы возможны только в близайуп окрестность, т.е. » если )н-м/>1.

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

Теорема. Если >0 , а произведения

frL'frU и Рпп.Г frlt*. » • достаточно ва-

лы, то D¿x) имеет 2<v простых нулей, /и-/ из которых лежит на интервале (о,/) , /V - на интервале , .и один находится в точхв х = •( .

И, наконец, мы исследуем асимптотику инвариантной меры при приблизении к порогу эргодичности. С этой целы) вводится в рассмотрение семейство блртданий в полосе Z+x {i, .. с переходными вероятностями ( схема серий). Допустим, что все они эргодичкы, т.е. -£.'*'■=-SZxJ1 М1*<С. Что иовно сказать в этом случае о поведении стационарных распределений л-^' ОлузданиИ '

Дяя определенности мы предположим,, .что при сс-»<*>

стремятся к переходила вероятностям Д^* некоторого блуцдания

так, что индуцированная цепь не меняется. Для "предельного" блуддания, очевидно, О . Таким образом, если П(1<',

П* - матрицы переходных вероятностей блузданий со-

ответственно, то уравнения х Сп1°°-Е)-0 имеют и притом единственное решение в классе вероятностных мер на решетке

N} , в 70 время как предельное уравнение ос (п*-е)»0 з этом класса решения не имеет. Изучаемая задача, следовательно, относится к классу некорректно поставленных. Идейную основу для ее анализа делт обцае теории Гихонова-Арсенкна, КоролЕка-Турбина, Однако, специфика задачи тахоед, что ее решение не удается извлечь нз обцих результатов относительно некорректно поставленных задач. Поэтому ш развиваем самостоятельную технику. .

Основной результат дает следус^ая

Теорама 2.1.3. если

f-Wf.-'M M-t) <*>1 +

2. При об—со i Lfm. -¿T-J-P*. j +

+ Г21 Xм IV^- f^oiw 1 л-»i w SL

то в стационарном реаиме Hojrápoванная первая координата а вторая координата асггятотичаскн независимы, причем имеет асимптотически экспоненциальное распределение со средним

Здесь запись вида С^пЛ^«.«*/-/ обозначает вектор (а.,,).

Методы, разработанные джя блуждания описанного выше вида могут быть применены и джя исследования более общих процессов-блужданий в полосе Я¿1} с непрерывной первой координатой, некоторых блуаданий в 2+ и т.д. № демонстрируем это в

§ 2 гл.2 на примере модели системы гибридной коммутации с плавающим порогом с ожиданием блокированных телефонных вызовов (в математическом плане дело сводится к изучение некоторой цепи Маркова с фазовым пространством * ¿+) . Как и в & I гл.2 дан метод точного численного решения задачи (он сводится к расчету нудой некоторого определителя; основной результат утверждает, что все они действительные и положительные) и показано, что в стационарном режиме при большой загрузке нормированная задолженность системы асимптотически экспоненциальна и не зависит от загрузки приоритетными телефонными вызовами.

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

«мш»-

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

Появление показательного распределения в 55 1,2 в качестве предельного пря приближении к порогу эргодичности совсем не удивительно, т.к. в теории массового обслуживания это обычное предельное распределение при большой загрузке. Его появление имеет обычно более глубокие корни и связано со сходимостью соответствующим образом* нормированного процесса к диффузионно^ процессу с отражением в нуле. Мы не обсуждаем эту проблему в § I в общем случав, однако в § 2 доказываем соответствующую функциональную предельную теорецу.

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

фузионноы приближении сильно загруженных периодических систем.

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

х {■!,..,, , отличающиеся от изученных в §§ 1,2 отсутствием однородности по первой координате. Рассмотрим, например, следующую основную модель. Имеется полнодоступная группа из с каналов, на которую поступает пуассоновский поток вызовов интенсивности Л ; времена занятий экспоненциально распределены со средним . Вызов, в момент поступления которого пучох блокирован,

покидает зону обслуживания и через экспоненциально распределенное со средним </¿4 время повторяет попытку доступа в канал.Процесс (н(&), С.Ц)} . где Са) - число занятых каналов, Ы(Ь) -длина очереди ранее блокированных вызовов, будет марковским с фазовым пространством 2 + х{о, 1,...,с} . Интенсивности перехода из /•. • - -тичди ^ ,(.; . атип аил^иилииы и^гдут лппвипи аивиивтв ит ^ .

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

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

Теореиа 2.3.1. При стационарная вероятность бло-

кировки £> и стационарная средняя дясна очереди А/ в основной иодели есть

&ы -йгЛ^ё тт ^я1 •"

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

¿и. € (о,+ <л) . Мы сводим эту проблецу к сингулярно возмущенным дифференциальным уравнениям, что, например, для основной модели дает следующий результат.

Теорема 2.3.4. Дусть сс = сс{с,-2) - корень уравнения

с"1 (З^+хУ1 \ 1

сг У \.л-ьХ> - Д -—-- на (о,+®) (при Л< с. этот корень „

& с! ' ' а1 с ^ Ы

суцествует и единственен), '^¿-"^(¿г йТУ-

Тогда в стационарном режиме при

и (Л см«} - ~»> (В условиях большой загрузки изучаемые системы демонстрируют интересное переходное явление.

Теорема 2.3.5. При асимптотическое разложение ста-

ционарной вероятности блокировки в двухнанальной основной модели имеет вцд (ниже £ = -/-Д/й ):

+ . если /<</,

* * —*

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

Терема 2.4.2. Дусть -два N -мерных миграцион-

ных процесса с пространства»« состояний А^Ааин$мнитези-мальными характеристиками цЧ1<\ /?,, и Л^ ,

и\ л соответственно. Для любых двух векторов л./яеН таких, что и-^ии обозначим через множество а

• , г „ -,(0 -.И) 1И (11

для ie L обозначим через J. и J.- ~ J.

ственно. Если

2. при всех Ai, тёД^таких, что П-§ж и всех ^ справедливы неравенства • ...

множест-j соответ

a:

„1-^, ^- ¿,'(0 luv <r- Ljia.)

д -2- yl /) Ui.

, 1П «Л

то существует "двумерный" марковский процесс (^ « ) такой,что

I. также являются марко!

дапцими с^ ^ , по распределению;

1. ^ , j также являются марковскими процессами, соспами с по распределению;

2. ll^fa) при всех исходах w и всех

Метод доказательства этой теоремы интересен тем, что дает явную конструкцию процесса ) , реализующего потраектор-

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

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

В § 5 изучаются свойства монотонности блужданий по частично упорядоченным множествам (L) < ) относительно обобщенной стохастической упорядоченности Ч (если п - два случайных элемеи-та, то Р(^-х)^ РС^ »ж) при всех х eL ). Для

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

Теорема 2.5.2. Оператор перехода цепи Маркова с переходными

вероятностями рХ1, монотонен относительно порздка -< , если для всех . Здесь /Р^-Д^/хг»

('^с, г) - функция Мебиуса частично упорядоченного множества

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

Теорема 2.5,3. Если (Ь,^) - дистрибутивная решетка, то необходимым и достаточным условием монотонности оператора перехода Т цели Маркова на Ь с переходными вероятностями является справедливость неравенства

йе/^"7л<|при всех 2,^еА. •а *, (хел .4 ; ,

одесь А? = у ее б Л | ас < 2 и не существует таких, что

х<ас'<г} , Лх=1п£ А - пересечение в решетке (I,

1А|=Са^А. хеА

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

Теорема 2.5.4. Пусть ¿^ , ~ Две последовательности

случайных элементов из / . Тогда для справедливости неравенства -< при всех е достаточно, чтобы:

1. ^ £'1 ,

2. существовало семейство матриц Р(£)= (» Удовлетворяющих условиям теоремы 2.4.2 и таких, что

< = все* а^б/..

В заключительной части § 5 мы рассматриваем применение этих результатов для оценки характеристик сетей Дкексона.

Теорема 2.5.5. Пусть , ,.,, ^ ) - объединенный

процесс длин очередей в сети Джексона из N однолинейных узлов с интенсивностями обслуживания ^и- , интенсивностями внешних потоков Л- , емкостями буферов с- (включая и место для обслуживаемого требования; требование внешнего или внутреннего потока, в момент поступления которого буфер заполнен - теряется) ; / ^;« л/ ; матрицей маршрутизации Р = Срм ) ; при этом, не нарушая общности, можно считать, что = о , а

/{) - аналогичная характеристика сети из N независимых систем Al/м//¡С- с темя же интенсивностями обслуживания ju.' , но с интенсивностями входящих потоков а,- * is is N . Тогда неравенства а• > J. + м- РЦ

' ¿ч J'» v t' • i-H +

необходимы и достаточны для того, чтобы <5,- < <, при всех tto

L. / ^ £. Н it

если только «¿у -< £

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

В § 6 гл.2 изучается монотонность и сравнимость процессов, связанных с сетями ALOHA . В начале ны рассматриваем сеть с конечным числом /И w»!«™^ пет с." 2 "стсруг сп y.z'jlzz.

ется последовательностью CL(t) = (a.iCt),...f aM(D) , где CL^L)-число новых пакетов, порожденных L -й станцией в окне (t, t ti) . Управление доступом мы задаем последовательностью -мерных векторов ЬШ^С^Ш, 4М (Ь)), где = / или О в

соответствии с тем, разрешено ли ¿-й станции передавать информацию в окне (i, t+i) или же она обязана пропустить это окно. В качестве основного процесса изучается объединенный процесс длин очередей на станциях (¿J - (^¡(i), который пред-

ставляет собой некоторое блуждание по Z^ .

Теорема 2.6.1. Предположим, что а■ (i) и & (i) являются с^чайнымн величинами на некотором основном вероятностном пространства Р) , причем последовательность (CL(t), стационарна в узком смысле и метрически транзитивна. Если а МасШ < П (1-&, (*))] при всех , то пра t->oo функция распределения монотонно сходится к некоторой собственной функции распределения.

Условие эргодичности, фигурнругцее в теореме 2.6.1, в определенном смысле является и необходимым. Из него следует, что сеть ALOHA с бесконечным числом станций не может быть устойчивой, сколь мала не была бы поступающая нагрузка А . В математическою! плане дело сводится к утверядению о неэргодичности некоторой специальной цепи Нархова £ ( имеет смысл суммарной очереди

в сети в момент t ). Оказывается, с неустойчивостью сети

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

Теорема 2.6.2. Цепь , описывающая длину очереди в сети

ALOHA с бесконечным числом станций - невозвратна. Более того, существует конечная почти наверное случайная величина У , удовлетворяющая условию Крамера, такая, что начиная с момента V в канале будут одни конфликты.

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

Теорема 2.6.3. Пропускная способность любого алгоритма управления доступом, не зависящего от индивидуальной истории пакетов, не может быть больше 1/е .

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

В § 7 гл.2 мы проводим новый взгляд на точно решаемые многомерные задачи массового обслуживания как на моментно замкнутые (по терминологии С.А.Ыолчанова и В.А.Малышева)блуждания по . Он не только позволяет понять общие причины появления сходных результатов для различных конкретных протоколов, но и позволяет решить задачи, которые при непосредственном подходе решить не удалось. Пусть 4г (Ь) ~ (ilj стационарное марковское случайное блуждание в дискретном времени по , (/iffa), jj^fn))-(М ,M{^О+О-^фО^л^векгор среднего сноса из

точки ег^ ,(<А(м, адн=е#шЯ^Ы.кШь-Д)

вектор средних квадратических сносов, С£>)= M{(€iit+i)~£| №>)' • (fc11)--Sj(t))j^(,-fc)=h.} - "ковариация" сносовш координатам. Ыы предполагаем, что все эти величины сохраняют постоянные значения в пределах внутренности 55 = {(«/, € Z^ I W , {} квадранта Я* , на гранях ЩW'f-

Значение величины Цк.) при к^Ъ мы обозначаем через ¡¡г ,

при л&Ъ' - через А' , при леЪ - через V , М1?-

/ с "

через у- .

Теорема 2.7.1. Если определитель

ь-

то

%ъ % Фо,

V4

и Mb*Л11 гА

V

Здесь И = - линейно независимые вектора

стпп« гтпопКпозлрв«!*^ I? *** Т^рО'^ЗННСГС У---С"--1"С^'

явно описанную матрицу

С А' А ? ^/»^»с).

Теорема 2.742. Если блугедание симметрично и определители

Д-

О

A VM

I»«1 .J. ji I

С

i II

0 ■

I о о ,

I J1 С-

i'rcl-id ^Vj.'i-^jut Д.

Ы-li y'+f-lfi t+t-ib

совпадают, то

Ml, W =

Из этих утверадений следуют известные результаты для средних длин очередей в системе типа /(j^ /<** с относительным приоритетом, симметричной сети ALOHA с. двумя станциями и Т.д.

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

Теорема 2.7.3. Средние длины очередей разных типов в системе типа А* / ^ j\ /<** с групповым поступлением и повторны* .. ¿i(P+C:-0 . Л; С,-

ми вызовами представимы в виде: N- ~

■ + ■

-хс»

\ А a-/) i где величины могут быть найдены как решение систеггы ли-

нейных уравнений ^

Аналогичная система может быть выписана и для вторых моментов (теорема 2.7.4.).

Приведенные выше результаты показывают, что точные и детальные модели современных систем случайного множественного доступа с очень большим трудом поддаются аналитическому исследованию. В связи с этим ь последние годы в качестве моделей сетей пакетной коммутации, локальных вычислительных сетей, компьютерных систем реального времени используют однолинейные системы обслуживания с повторными вызовами. Сравнение с результатами моделирования и статистических измерений на сетях показывает хорошую точность этих моделей. С другой стороны, они допускают детальное аналитическое исследование характеристик, которые более интересны, чем длина очереди (например, время реакции системы). В § 8 гл.2 мы разрабатываем методы исследования различных процессов, связанных с системами такого рода; изложение ведется на примере основной модели типа /Ч /<гА • Ниже: 3 - интенсивность потока первичных вызовов, ^ч - интенсивность повторения ранее блокированных вызовов, 3/х) - функция распределения времени обслуживания , - ее преобразование Лапласа-Стилгьеса, &

Лр, , =75 (А-Аъ).

Первый вопрос, который мы рассматриваем - это существование стационарного режима. Как обычно, при _р< / система эргодична, при ^ / - неэргодична, причем при >/>/ - невозвратна. Интересно отметить, что в зависимости от ^ при / = / может быть как невозвратность, так и нулевая возвратность.

Стационарное распределение Р^ длины очереди (РА ~

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

Теорема 2.8.1. Если система находится в стационарном режиме функционирования, то

а) при /*/&) асимптотически нормально со средним

и дисперсией (Л^+ЛЦ-Ыр^/Сл О'р)^),

б)-при ^ Рл - Р^(^) сходится к стационарноцу рас-

пределению длины очереди Рп в соответствующей системе с

ояццанием; более того, справедлива следующая оценка:!

2(1-0

Теорема 2.8.2. Если bfe) имеет вид НАС С , то стационарное распределение числа^ебований в системе меньше в смысле W » чем отрицательное биномиальное распределение

Теоре'аа 2.8.3 дает явную формулу для совместного преобразования Лапласа длины А -периода занятому, L , и числа требований, обслуженных за этот промежуток, ^ , а также явные формулы для моментов М L^ \ М1°. Однако в эти форцулы входит преобразование Лапласа , что -.затрудняет их использование.

Тссрс-с. 2.С.4. ДасГ пвчуаСгоителепне оценки fii ■

Теорема 2,8.4. Для любой системы с повторными вызовами

_ J Л f' 1-е;tpC-Pd-u» ,1

а если В ix.) принадлежит к типу НЛСС, то

miw* о-1

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

- CfVs+ifM/0-f)-

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

Теорема 2.8.6. Если ~Ь фиксировано, то независимо от загрузки системы виртуальное время ожидания W(i) конечно почти наверное. Однако, ЛШ/t) < °о тогда и только тогда, когда j><.JL . Такка образом, при росте нагрузки возникает своеобразный фазовый переход, причем его точха не совпадает с точкой j>=i перехода эргодичность/неэргодичность для процесса W(i) .

Теорема 2.8.7. Если Тк - время ожидания требования, которое начало ожидание в момент окончания обслуживания некоторого вызова при наличии vt-i других вызовов, то при н-»<» распределе

нив случайной величины 7^/(п^) слабо сходится к распределению с плотностью р /а~р) ,

И-О-ГИТ

» если /-У

срч) *есл» />л

Кроме того, в теореме 2.8.8 мы находим явное выражение дня М ехр ) в стационарном режиме (функционирования.

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

квазивходящего потока, а также рассматриваем его ковариационные свойства. Интересным следствием этих результатов является естественный пример потока с экспоненциальными интервалами между событиями, который тем не менее не является пуассоновским - это квазивходящий поток в систему /М/5-///°° с Функцией распределения времени обслуживания вида где .

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

1. Фалин Г.И. Асимптотический анализ одного класса сетей с коммутацией каналов. - Проблемы передачи информации, 1981, 17, №1, с.

■ 96-101.

2. Фалин Г.И. Асимптотическая инвариантность вероятностных характеристик структурно-сложных систем коммутации с потерями. - Проблемы передачи информации, 1981, 17, JS2, с.79-85.

3. Фалин Г.И. Укрупнение состояний симметричных неполнодоступных схем. - Проблемы управления и теории информации, 1982, с.3-12.

4. Фалин Г.И. Процессы обслуживания в сетях с коммутацией каналов. В кн.: Первый Всемирный конгресс общества математической статистики и теории вероятностей им.Бернулли. Тезисы. М.: Наука, 1966, Т.П.

5. Фалин Г.И. Об ППГОПИЧНОСТИ одной unnftnu тлтврчвоиипго доступа в широковещательный канал. - Известия АН СССР. Техническая кибернетика, 1981, № 4, с.126-130.

6. Фалин Г.И. Оценка эффективности одного класса алгоритмов случайного множественного доступа в радиоканал. - Проблема передачи информации, 1962, 18, i?3, с.85-90.

7. Фалин Г.И. Свдйства монотонности и устойчивости одного класса случайных блуяда лий. ДАН УССР, 1986, MI, с.12-15.

8. Фалин Г.И. Оценки погрешности при аппроксимации счетных цепей Паркова, связанных с моделями повторных вызовов..- Вестник Московского университета. Сер.1, Математика и механика, 1987, Ш, с.12-15.

9. Фалин Г.И. О неустойчивости системы синхронная ALOHA . В сб.: Вероятностное моделирование систем и сетей обслуживания, Петрозаводск, IS88. с.84-91.

10. Фалин Г.И. О точности одного численного метода расчета характеристик систем с повторными вызовами. - Электросвязь,: 1983, Ш, с.35-36.

11. Фалин Г.И. Влияние неоднородности состава абонентов на функционирование телефонных систем с повторными вызовами. - Известия АН СССР, Техническая кибернетика, 1983, №6, с.21-25.

12. Фалин Г.И. Асимптотические свойства распределения числа тре-&ваний в системе типа W/^/z/co с повторными вызовами. - Известия АН СССР. Техническая кибернетика, 1984, ЯЗ, с.168.

13. Фалин Г.И. Об эргодичности многолинейных систем массового об-

служивания с повторными вызовами. - Известия АН СССР. Техническая кибернетика. 1966, №4, с.63-68.

14. Фалин Г.И. Предельные теоремы для систем обслудивания с повторными вызовами. - В кн.: Четвертая международная Вильнюсская конференция по теории вероятностей и математической статистике. Тезисы докладов. Вильнюс, 1985, 1985, т.Ш, с.235-237.

15. Фалин Г.И. Асимптотическое исследование полнодоступных коммутационных систем при большой интенсивности повторения блокированных вызовов. - Вестник Московского университета. Математика и механика, 1984, #6, с.49-53.

16. Фалин Г.И. Инвариантность вероятностных характеристик одного класса сетей с коммутацией каналов. - Вестник Московского университета. Вычислительная математика и кибернетика, 1987, № 3, с. 5357.

17. Фалин Г.И, 0 сходимости процессов обслуживания в структурно-сложных системах с потерями к стационарным. - Теория вероятностей и ее приложения, 1987, »3, с.577-580.

18. Фалин Г.И. Эргодичность, устойчивость и нечувствительность для одного класса сетей с коммутацией каналов, - Проблемы передачи информации, 1988, Т.ХХ1У, вып.1, с.74-88.

19. Фалин Г.И. Монотонность случайных блужданий по многомерным целочисленным решеткам, ДАН УССР, -серия "А", 1987,Ш,с. 17-20.

20. Фалин Г.И. Сравнимость миграционных процессов. - Теория вероятностей и ее применения, 1988, № 2.

21. Фалин Г.И. Об эргодичности некоторых комцуникационных систем.-Сибирский математический журнал, 1988, №2, с.210-211.

22. Фалин Г.И. Монотонность случайных блувдсний по частично упорядоченным множествам. Успехи математических чч/к« с. 155-156.

23. Фалин Г.И, 0 квазивходящем потоке для системы Украинский математический дурная, 1988, т.40, с.291-294.

24. Фалин Г»И. Об однолинейной системе со случайно меняхцейся скоростью обслуживания. Изв.АН СССР. Техническая кибернетика, 1988, М, с. 134-137.

25. Фалин Г.И. Об эргодичности блужданий в полуполосе. Математические заметки, 1988, №2, с„225-230.

26. Фалин Г.И. Расчет системы гибридной коммутации с плавающим порогом при наличии комплектов ожидания, 1988,' №3, с.102-108.

27. Фалин Г.И. Двухканальная система с повторными вызовами. Изв. АН СССР. Техническая кибернетика, 1985, М, с. 162-163.

28. Fatiiь if. I. On. sufficient atnditions for erqcdia-ty cf mutiCcAanneZ <рием.е.Сл£ system wiik repeated calls. Advances Uu Applied Probability, 1984, л02,

29. Fa.iC/v Q. I. Quasi-input process in ike t4/Q-/l/°° fyueue. Advances in Applied Proiakfrty, /384,^3, 69S-696.

30. Fa&it (jr. L. On. waiting tc/не process ui single-line yueae with repeated talis. Journal of Applied Probability, /Э86, л t, 1в:Щ)92. ф

31. /-aA'/t Q-.i. Sinqii- lirLQ. repeated orders cjueueing systems. Math. Operatio/isforscJtanp and •Statist¿k. Optimiiation, /386, м'Г, 649-66?.

32. Fa-Cin. Q-. I. AlitliitfuuxneJL queueing system with repeated ealh under hiqk intensity of' 'repetition. Journal of-Infoimxtion, Processing and Cybernetics,/9&'t, ,3f-47.

33. Fa6.4 Q-.I. On a -m и I tic ¿ass iattk arrived retrial queue. Advances in. Applied Proiaiitiiy, /Э8Ь,М, 48b~48t.

34. Фалин Г.И.. Блуадания в полуполосе и системы гибридной кям-мутации с плаващим порогом. "International Seminar crt. TeEetraffic, Tkeoru anuL Computer , Sofia., Bu^aria, Marck 1988. Proce&dinqs", Sofia, V988, pp.lS-li 0.