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

004601049

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

Рыбко Александр Николаевич

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

05.13.17 - Теоретические основы информатики

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

Москва 2009

004601049

Работа выполнена в Институте проблем передачи информации им.А.А.Харкевича Российской академии наук

Официальные оппоненты: академик РАН, доктор физико-математических наук,

профессор А.А.Боровков

доктор физико-математических паук, профессор М.И.Вишик доктор физико-математических наук, профессор В.И.Оселедец

Ведущая организация: Механико-математический факультет МГУ им.М.ВЛомоносова

Защита состоится « г т 2009 г. в 11 часов па заседании Диссертационного совета Д.002.077.01 при Институте проблем передачи информации им.А.А.Харкевича РАН по адресу: 127994, Москва, ГСП-4, Б. Каретный пер., 19, стр1.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации им.А.А.Харкевича РАН

Л 10

Автореферат разослан У » I 2009 г.

Ученый секретарь Диссертационного совета Д.002.077.01

доктор физико-математических наук уу И.И.Цитович

Общая характеристика работы

Актуальность темы. Разработка математических методов, предсказывающих значения стационарных характеристик узлов сети при выбранных допустимых нагрузках, является актуальной темой в современной теории случайных процессов, описывающих поведение телекоммуникационных сетей. Одной из основных проблем является, также, и само нахождение условий существования стабильного режима работы 0TKpi.iTi.ix сетей, или, что то же самое, условий эргодичности марковских процессов, описывающих функционирование таких сетей, поскольку при создании и эксплуатации телекоммуникационных сетей необходимо гарантировать их стабильную работу.

Математическая теория, описывающая функционирование телекоммуникационных сетей, является динамично развивающейся областью теории случайных процессов. Она стала развиваться лишь во второй половине 20-го века. Первоначально, развитие теории осуществлялось (когда это было возможно) методами, имеющимися в более старой и развитой области - классической теории массового обслуживания. Так, Р.М.Лойнес, доказав фундаментальную теорему об эргодичности случайного процесса, описывающую поведение общей модели очереди g|g|I|°o при нагрузке меньшей единице, немедленно

обобщил этот результат на случай простейшей коммуникационной сети - линейной последовательности серверов.

Другим направлением исследований первоначально было нахождение и изучение точно решаемых моделей - таких сетей, для которых их инвариантные меры явно выражаются через инвариантные меры отдельных изолированных серверов - узлов, составляющих сеть. Это направление началось с обнаружения сетей Джексона. Инвариантная мера состояния для сетей Джексона является произведением инвариантных мер отдельных изолированных узлов сети. В дальнейшем были найдены различные примеры сетей, для которых инвариантная мера находилась явно и, как правило, строилась в виде меры - произведения инвариантных мер отдельных изолированных узлов сети (product form networks).

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

В связи с невозможностью использования явных аналитических методов стали развиваться качественные математические методы анализа случайных процессов, описывающих поведение сложных коммуникационных сетей. Это направление было основано в работах РЛойнсса, В.Л.Малышева, РЛ.Добрушина, А.А.Боровкова, П.Р.Кумара, В.Анатхарама, А.Столяра, Ф.Келли, Р.ШЛипцсра, Д.Харрисона, Д.Штояна, Р.Ясногородского, Р.Шассбсргсра, В.Калашиикова, Л.Мандсльбаума, Ф.И.Карпелсвича, и в настоящее время продолжает свое развитие в работах М.Брэмсона, Д.Дая, М.В.Меньшикова, С.Г.Фосса, Д.А.Коршунова, Ю.Барышпикова, С.Б.Шлосмапа, А.Ю.Всретснникова, Л.А.Владимирова, Ш.Мейна, А.Л.Пухальского, А.Д.Маниты, Р.Уильямс, Н.О'Конелла, Н.Д.Введспской, Л.Г.Афапасьевой, Е.А.Псчсрского, А.А.Замятипа, Г.Файоля, Ф.Бачслли, Ж.Маресса, Т.Константопулоса, Ю.М.Сухова и в

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

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

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

В [13] эта гипотеза была опровергнута, - было доказано, что уже для простой сети,

состоящей из 2-х узлов, в которой циркулируют 2 класса требований, при некоторой приоритетной дисциплине даже при экспоненциально распределенных независимых временах обслуживания и при пуассоновских входных потоках требований, утверждение гипотезы не верно. Чтобы исследовать поведение соответствующего однородного марковского процесса со счетным числом состояний был построен жидкостный предел, возникающий в Эйлеровском скейлинге. Похожая идея для изучения эргодичности случайных блужданий в положительных октантах ранее использовалась В.А.Малышевым и его учениками1. Однако, в силу имеющихся дополнительных инвариантов, связанных с условием консервативности дисциплин обслуживания в узлах, анализ поведения траекторий жидкостного предела для сетей допускает «явное» описание. Векторное поле «детерминированной» жидкостной динамики явно строится как в конечномерном случае (приоритетные дисциплины), так даже и в бесконечномерном случае (дисциплины FIFO, LIFO), и это дает возможность рассматривать произвольно распределенные (а не только экспоненциально распределенные) времена обслуживания требований и общие входные потоки.

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

1) доказательство сходимости к жидкостному пределу в Эйлеровском скейлинге для достаточно широкого и общего класса сетей массового обслуживания;

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

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

' Malyshcv A.V. Networks and dynamical systems. Adv. Appl. Prob. 1993, V. 25, P. 140-175 3

Первые два утверждения были доказаны независимо в работах Л.Столяра и Д.Дая. Третье утверждение было доказано в [19]. Доказательство основано па использовании

методов теории больших уклонений.

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

Еще в 70-х годах Л.Клсйпрок предложил следующую инженерную концепцию, — гипотезу для приближенного вычисления стационарных распределений больших сложных сетей, названную пуассоповской гипотезой. Пусть имеется огромная сеть, состоящая из очень большого числа узлов, причем маршруты требований таковы, что па каждый узел поступает большое число малых потоков требований, идущих из различных узлов сети. Пусть также известно, что случайный процесс, моделирующий работу такой сети, стации-онарен и эргодичен. Для приближенного вычисления инвариантной меры этого процесса предлагается следующий простой метод. Потоки требований, поступающие на каждый фиксированный узел, заменяются па пуассоиовские потоки постоянной интенсивности. При этом предполагается, что потоки, поступающие на различные узлы сети, независимы. В этих предположениях возможно явное нахождение инвариантной меры, поскольку работа сети распадается на работу независимых систем массового обслуживания, для нахождения стационарных характеристик которых обычно имеются явные аналитические формулы. Ясно, что строгий смысл этой гипотезе можно придать лишь в термодинамическом пределе для последовательностей таких сетей с растущим числом узлов, для которых интенсивности потоков, поступающих из узла А в узел В, стремятся к пулю для произвольных пар А и В. А.А.Боровков уточнил и упростил задачу, предложив для начала доказать пуассоновскую гипотезу в простейшем нетривиальном случае: для термодинамического предела замкнутых симметричных сетей па полном графе с фиксированным отношением числа требований к числу узлов и с произвольно одинаково распределенными, независимыми в совокупности последовательностями времен обслуживания требований в узлах. РЛ.Добрушин подчеркивал связь этой проблематики с исследованием свойств термодинамического предела для моделей среднего поля в статистической физике, что оказалось очень важно для доказательства пуассоповской г ипотезы.

Цель работы.

1) Нахождение условий стабильности открытых телекоммуникационных сетей.

2) Исследование свойств жидкостных траекторий, возникающих в Эйлсровском пределе для телекоммуникационных сетей.

3) Исследование условий асимптотической независимости для симметричных сетей большого объема.

4) Исследование свойств нелинейных марковских процессов, возникающих в термодинамическом предельном переходе для симметричных сетей.

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

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

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

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

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

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

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

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

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

Апробации результатов и публикации. Результаты работы неоднократно докладывались на научных семинарах под руководством Р.Л.Добрушипа, Р.А.Минлоса и М.С.Пинскера в ИППИ им.А.А.Харкевича РАН (1980-2009), па научных семинарах под руководством Р.Л.Добрушипа, Я.Г.Синая, В.А.Малышева и Р.А.Минлоса в МГУ им.М.В.Ломоносова (1980-1990), на летнем научном семинаре под руководством Я.Г.Синая в МГУ им.М.В.Ломоносова и в ИППИ им.А.А.Харкевича РАН (2005-2009), на научном семинаре под руководством А.М.Вершика в математическом институте им.В.А.Стеклова РАН в Санкт-Петербурге (2004), на научном семинаре под руководством А.А.Боровкова в Институте Математики им.С.Л.Соболева (1989), а также на

многочисленных международных семинарах и конференциях, в частности, на 1-ом Конгрессе Бсрнулли, (Ташкент 1986), Международной Конференции но Теории Вероятностей и се нриложеням (Париж 1993), 16-ой Европейской Конференции но Исследованию Операций (Брюссель 1998), Международной Конференции «Л.Н.Колмогоров и Современная Математика» (Москва 2003), 4-ой Международной Конференции «Предельные Теоремы в Теории Вероятностей и их Приложения» (Новосибирск 2006), Международной Конференции Памяти РЛ.Добрушина (Москва 2009) и др. (см. [ 1,3,5,7,10,15,18,26,36,40,43]).

Основные материалы диссертации изложены в 43 работах.

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

Содержание работы.

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

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

В первой главе описана конструкция жидкостного предела для сетей массового обслуживания и изложены результаты об эргодичности для открытых сетей массового обслуживания, полученных автором на основе этой конструкции. Основой для первой главы диссертации служат работы [13,19,23].

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

1.1.1. Постановка задачи. Опишем функционирование сети, рассмотренной в [13], являющейся однородным марковским процессом с непрерывным временем и счетным числом состояний. Сеть состоит из ./ узлов. Имеется / классов требований. Входной поток требований класса /,/е{1,...,/}, есть пуассоновский поток с интенсивностью Д, (эти

потоки взаимно независимы для разных классов требований). Каждому классу требований соответствует свой маршрут

)0Л-,Л',к),...,Мт), ли)е./, к = 1.....ЛГ(1),

т.е. последовательность узлов сети в которых должны обслуживаться требования данного класса прежде, чем покинуть сеть. Здесь АГ(/) - длина маршрута для требований

класса /, а Л',к) а ./(к = 1,..., А"(/)) - помер узла сети, в который попадают па обслуживание требования класса / па к -м шаге своего маршрута.

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

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

Нетрудно определить однородный марковский процесс s(l) со счетным фазовым пространством, описывающий работу рассматриваемой сети.

Обозначим через р] суммарную номинальную нагрузку узла j: Pi = £ Va

(/,1 ):jV,k)=j

В [l] доказана следующая простая теорема.

Предложение 1: Если s(t) - эргодический марковский процесс, то для всех j g J

Л<1-

Добрушиным была выдвинута следующая естественная гипотеза.

Гипотеза 1: Если для всех j в J

Pi<1 (О

то s(t) есть эргодический марковский процесс.

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

Приведем наглядную интерпретацию этого предельного детерминированного жидкостного процесса. Имеется J сосудов и I сортов жидкости. В начальный момент времени суммарное количество жидкостей во всех сосудах равно единице. Жидкость сорта i е / вливается в первый сосуд у(/, I) своего маршрута с постоянной скоростью Я , перетекает через последовательность сосудов j(J,\),...,j(i,k),...,j(i,K(J)) и затем покидает сеть. Единица /-й жидкости в сосуде j = j(i,k) имеет вязкость vlt. Каждый сосуд j с J имеет два отверстия - верхнее, через которое жидкости втекают в сосуд (величина этого отверстия неограниченна), и нижнее, через которое жидкости вытекают из сосуда. Величина нижнего отверстия равна единице. Таким образом, если данный сосуд не пуст, то общая вязкость жидкости, вытекающей из данного сосуда за единицу времени равна единице. Жидкость вытекает через отверстие в данном сосуде согласно той же дисциплине, что и дисциплина обслуживания для соответствующего узла сети обслуживания. Например, для дисциплины FIFO жидкости вытекают из сосуда «в том же порядке», в котором они втекают в данный сосуд. Свойство эргодичности рассматриваемого марковского процесса л(/) соответствует тому факту, что система сосудов опустошится за конечное время при любом начальном состоянии с суммарным количеством жидкостей, равным единице. Похожие детерминированные процессы дискретного типа исследовались в теории расписаний для производственных систем (см. работы Перкипса и Кумара, Кумара и Сейдмана).

Пример нестабильного детермипи- рованного жидкостного процесса в Теореме 5 помогает доказательству невозвратности соответствующего марковского процесса (Теорема 6).

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

Второй случай, рассматриваемый в п. 1.1.4— это специальное приоритетное обслуживание в каждом из узлов: в нервом узле требования второго класса имеют абсолютный приоритет, а во втором узле наоборот, требования первого класса имеют абсолютный приоритет. Показано (Теорема 6), что в этом случае Гипотеза 1 не верпа: для некоторой области параметров, удовлетворяющих условию /з>. < 1, jeJ соответствующий марковский процесс невозвратен.

1.1.2. Сеть с дисциплиной обслуживания FIFO. Итак, пусть задана дисцинлипа FIFO в каждом узле. Состояние сети s cS зададим следующим образом:

j = = 1-г Qj),J е ./} .Здесь QJ - общее число требований в узле j е J ,

Sj, б Gj = {(/,£): j(i,k) = yj - класс требования, стоящего па 1-м месте в очереди в

узле j. Очевидно, что s(t) есть неприводимая счетная цепь Маркова в непрерывном времени t.

Теорема 1. При выполнении условия (I) марковский процесс s(t) является эргодическим.

Нам удобно ввести в рассмотрение процесс, описывающий поведение рассматриваемой сети более детально.

Положим 0(O = {04(O,('.*)eG,/>O}, где G = {(i,k):iе f,k = \,2\,QJt) - общее

число требований (;,4) потока, находящихся в узле j = j(i,k) в момент />0. Ясно, что Q(t) есть проекция л(/) (т.е. функция от состояния s(t)). Определим норму состояния л(/)

как |Ио|=||е(о||' Z & (')■

<i,»)cG

Условимся, что все величины, относящиеся к процессу .v(<), будут в дальнейшем снабжены верхним индексом п, если ||.5(0)|| = п > 1.

Обозначим через F^(i),t> 0, суммарное число требований (i, i) -потока, поступивших в узел j = j(i,k) до момента времени /, включая требования (¿Д)-потока, находящиеся в узле j в начальный момент 1 = 0. Для определенности положим F"t(t) -неотрицательные кусочно-постоянные неубывающие функции непрерывными справа. Определим отрицательную константу : Г0 = -шт[Яг' ,i е ¡,v.t,{i,k) е Gj .

Продолжим функции F"k(t) на отрезок [лГ^О] следующим образом. Условимся, что требования, находящиеся в сети в момент 1 = 0, поступали в сеть в отрицательные моменты пТ0,(п-\)Т0,...,Т0 (по одному требованию в каждый момент). Причем последовательность поступления требований различных классов соответствует их порядку расположения в очередях в момент 0.

Обозначим через I) суммарное число требований (/,4)-нотока, покинувших узел j = j(i,k) до момента /. Ясно, что для всякого п > 1

У-;(»Г0) = 0,4"(0) = 0,(/Д)е0, X

Если начальное состояние сети имеет норму п > 1, то рассмотрим процесс

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

значениями п и начальными состояниями |f";(0)J в семейство нормированных процессов {/";<"}. Пусть

гт ± е [r0,/],iЖМ'е [о,/],(/,*) Ê g} ,i > 0, где Л"(<) = * Та,

= Положим <?,", (О = -££("')> q"(t)±Uk(t)Ai,k)tG}. Ясно, что для

п п 1

любого л>1 и любого /"-<0) /¿(Гц) = 0,V(/,fc) е G, ||<7"(0)| = £ /Л°) = 1В [13] доказан следующий результат, из которого следует Теорема 1. Теорема 2. Существует такая константа Т>0, что для любого t>T и для любой последовательности начальных состояний f"'m процессов f"M выполнено равенство ПтЯ||«Л0| = 0.

1.1.3. Предельный детерминированный жидкостный процесс и его свойства.

Зафиксируем произвольную пару (/',A)eG. Рассмотрим последовательность функций

[/ЛО,'е[Г0,0]),«>1, входящих в соответствующие начальные состояния f""'\n > 1, фигурирующие в условии теоремы 3. Нетрудно видеть, что эта последовательность имеет предельные точки в смысле равномерной метрики ||g-g'||= sup [&'(0-g'C)]> причем

"ft-®]

каждая предельная точка /i(i),/e[7,0,0], есть неубывающая непрерывная функция, удовлетворяющая условиям Липшица с константой ' и условию fik(T0) = 0.

Таким образом, последовательность начальных состояний /";(0),«> 1, содержит подпоследовательность /""<0,,/> 0, которая сходится к множеству функций /0={Л(0,'е[Го,0Цд0)^0,(/,*)еС}. Каждая из функций f:l(t),l c-\TJ)},Q,k)^G,

удовлетворяет условиям, приведенным ранее, причем ^ ^(0) = 1.

(мм;

Естественно предположить, что для любого фиксированного t > 0 последовательность наборов случайных функций (или, что эквивалентно,

последовательность случайных процессов /"';<i),£e[0,/]) сходится по вероятности к некоторому множеству детерминированных функций /(,) (или к детерминированному жидкостному процессу /'^,^€[0,/]).

В [13] мы не доказываем результат о сходимости процессов. Вместо этого в данном разделе мы дадим формальное определение «предельного» детерминированного жидкостного процесса /''', соответствующего «предельному» начальному состоянию /(0) и исследуем его свойства. В следующем пункте эти свойства детерминированного жидкостного процесса будут в некотором смысле перенесены на последовательность случайных процессов f"M,n —> °о. Это позволяет доказать Теорему 2.

Рассмотрим множество функций / = J J]t (t),t>T0, 7,t (< '), ' ' ^ 0, (/, 4 ) с Gj, которое удовлетворяет следующим условиям.

1. Для любого (/,4)eG, ftt(t) и (I) являются неубывающими, непрерывными, функциями, удовлетворяющими условию Липшица с константой ¿ = |7,0|', и {/Г(0.'е[Г0,0]},л>1,

2- Z /4(0) = 1. Обозначим w,(l)= JeJ, w(t)=",«)-<,

(М)ю' (f ,t)cal

w,(t) = / + min j^O, mm [ J, / > 0, j e J, v1(/) = max [r <t: w. (r) = Wj (<)],' S 0, j e J. Потребуем, чтобы множество функций/удовлетворяло также следующему условию: з. Л(0 = /»( W»-' * 0,(/,*) с G, /.(/) = /а(0) + Л'Д = 1,/ * о,« ЕI, Л(0 = Л(о)+Л-|(0.^о.*>1,/б/.

Определение. Если множество функций f удовлетворяет условиям 1-3, то назовем /'" = {/а(£),£ е [Г0,/],(£'),'£ [0,/],(/,*) е с},/> 0,

детермироваииым жидкостным процессом с дисциплиной FIFO, соответствующим начальному состоянию /"" = МШ = 0,(/,*) е с}.

Теорема 3. Для любого начального состояния /(0' (т.е. набора функций (/),/ е [7J,,0],(/,Ä:) s Gj, удовлетворяющего условиям 1) - 3) существует по крайней

мере один соответствующий ему детерминированный жидкостный процесс /{1),1 > 0.

Доказательство этой теоремы легко получить, например, из теоремы Брауэра о неподвижной точке непрерывного отображения выпуклого компакта в себя. Если некоторый детерминированный процесс /''',/> 0, фиксирован, то естественно ввести следующие определения:

9(0 = {i*(0,(U)eG}, где (/) = /.(/)-/,('). ||<?(')||= £ <7а0).

В [7] доказана следующая теорема, относящаяся к детерминированному жидкостному процессу /'" и являющаяся аналогом Теоремы 2.

Теорема 4. Существует такая константа Т>0, что для любого детерминированного жидкостного npoijecca /''', соответствующего произвольному начальному состоянию /<0>, выполняется следующее свойство: ||</(/)| = 0,V/>r.

1.1.4. Сеть со специальной приоритетной дисциплиной обслуживания. Контрпример к Гипотезе 1. Рассмотрим следующую дисциплину обслуживания в узлах рассматриваемой сети. В узле 1 требования класса 2 (т.е. требования (2,2)-потока) имеют абсолютный приоритет и, наоборот, в узле 2 абсолютный приоритет имеют требования класса 1 (т.е. требования (1,2)-потока).

Нетрудно видеть, что для такой дисциплины обслуживания поведение сети описывается более простой марковской цепью Q(t) со счетным пространством состояний: 0(0 = {йД'М'Д) сС},(>(). Заметим, что состояние Q для которых Jßu>0,

[Qz, 2>0,

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

Мы покажем, что марковский процесс Q(t) является невозвратным для широкой области параметров A,,; = l,2,v.t,(/,£)eG, удовлетворяющих условиям pt < 1,7 = 1,2. оставим все определения предыдущих пунктов без изменений, за исключением специально оговариваемых случаев. Мы также начнем с рассмотрения «предельного» детерминированного жидкостного процесса.

Детерминированный жидкостный процесс q(l) = {<7l((/),(/,к) е G,t > 0}, соответствующий фиксированному начальному состоянию <7(0), ||?(0)|| = 1, задается (аналогично тому, как это сделано выше) как проекция детерминированного процесса f'\t> О,

с произвольным начальным состоянием /(0), удовлетворяющим условию

Л(0) = <7,Д0),(/Д)еС.

Детерминированный жидкостный процесс /''',/>0 определяется аналогично тому, как это было сделано для дисциплины FIFO, необходимо лишь заменить условие 3 на следующее условие 3«:

3' - Л (0 = fit (')),'£(>,('> к) Е G, (/) = (0) + A,t, t > О,/ е /, Л(0 = Л(0) + Л_, (/),/ е = 2,

где

Ч (0 = max [г < /: vv, (/) = w:t СО], (', *) е= G, wlt (f) = /Л (fK (/), (/, Л) е G,

wlt (t) = t + min

0,min йл,(£)

0<£<i

,(/,*) = (1,2),(2,2), *„(/) = wjl)-l,d,k) e G,

н<,(/) = IV,(Г) — уг'22{/), Л2|(0 = и"2(0-й>12(0 (функции Л(0,уе./, определены

выше).

Замечание 1. В рассматриваемом в данном разделе случае процесс q(t) может быть

также определен как решение дифференциального уравнения вида —?(/) = Л(<у(/)),/ > 0

Л

с разрывной функцией А(-).

Замечание 2. Нетрудно видеть, что существуют такие начальные состояния <?(0), что соответствующий им процесс (¡(1) не единственен. Например, по крайней мере два различный процесса </(/) соответствуют такому начальному состоянию, что ?11(0)>0,911(0)> 0,9,2(0) = 9И(0) = 0. Рассмотрим нашу сеть со следующими параметрами: 4 = ^ = 1^,2 = ^22 = > 1 /2,|/м = У21 = v,,

причем выполняется условие (1), которое принимает вид у,+у2 <1. Следовательно, выполняется неравенство 0< V, <\-У2.

Теорема 5. Пусть фиксировано следующее начальное состояние процесса : ?и(0) = 1, <г„(0) = 921(0) = 9и(0) = 0.

Пусть Т = У2/(1-У2)>1, = У, /(1-у,). Тогда детерминированный жидкостный процесс на отрезке [О, Г] определяется единственным образом и гшеет вид

Г1 — (С^,)"' —1>/, О < Г <

<7н(')= ,

0 T.<t<T,

„ (/)4 (V—2-')ло</<т;,

12 !(»',-»', )(1 - V, )■' VI' - К11 -1)/, Т, < I < Т, Чи(1) = 1,0<1<Т, <722(/) = 0 <1<Т.

Таким образом, в момент времени Т, <у21(Г) = Г > 1, Ци(Т) - Цп(Т) = ц22(Т) = 0 (Доказательство следует непосредственно из определения q(t).) Мы видим, что в момент времени ^состояние процесса q(l) подобно с точностью до симметрии состоянию в момент времени 1 = 0 и ||<7(7")|| -Т> ||</(0)|| = 1. Следовательно, процесс ?(/), с начальным состоянием, рассматриваемым в Теореме 5, обладает свойствами ||<у(0|| * 0,1 > 0, ||9(')|| °°>'

Вернемся теперь к рассмотрению марковского процесса ¿)(1) = {й4(')>('Д) е С}. Теорема 6. Если параметры сети таковы, что Л, = = \,у12 = у12 > 112,Уи = у12 = у, > 0,у, + У2 < 1, то марковский процесс 0(/) невозвратен.

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

1.2.1. Описание модели. Мы рассматриваем открытую сеть, состоящую из М узлов, в которой циркулируют требования /, классов. Имеется ¿'<£ внешних потоков требований, при этом каждый внешний поток содержит требования лишь одного класса. Класс требований однозначно определяет помер узла, в котором она обслуживается, так что Ь > М . Требования, поступившие в данный узел, образуют единую очередь в порядке моментов их поступления, а обслуживание происходит в соответствии с дисциплиной обслуживания, принятой в этом узле. Относительно последней предполагается, что она определяется только классами требований и местами, которые они занимают в очереди; внутри классов требования обслуживаются в порядке поступления. После окончания обслуживания в узле требование либо меняет класс и поступает па обслуживание в соответствующий узел, либо покидает есть обслуживания.

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

Пусть и - метрическое пространство с борелевской с-алгеброй В (и). Скажем, что последовательность {Рп,л>1} (или последовательность |ХП,я > 1} случайных элементов с распределениями Рп) является экспоненциально плотной с показателем ап, если для любого Е > О существует компакт К си такой, что ПтР"а-(уIК)<с. Известный результат Пухапьского2 заключается в том, что если последовательность {Рп,п> 1} экспоненциально плотна с показателем ап, то существует подпоследовательность п' такая, что последовательность > 1} удовлетворяет принципу больших уклонений

2 Puhalskii A. On functional principle of large divialions. New Trends in Probability and Statistics. Utrecht; VSP/Moks'las, 1991, V. 1, P. 198-218

для нормирующей последовательности ап. с некоторым функционалом действия /'. Назовем любой такой функционал действия /' предельной точкой последовательности {/>„,л >1} в смысле принципа больших уклонений для нормирующей последовательности ап.

Также скажем, что последовательность {/^,л>1} является £/0-экспоненциально плотной с показателем ап, где ио с: и, если {Р„, л > 1} является экспоненциально плотной с показателем ап, и любая ее предельная точка /' в смысле принципа больших уклонений для нормирующей последовательности а„ обладает тем свойством, что /'(г) = со для всех 2 е С/ \ ¡70.

Определим теперь некоторые топологические объекты, которые нам понадобятся в дальнейшем. Пусть 5 - полное сепарабелыюе метрическое пространство. Обозначим через £)([0,°о),пространство Скорохода непрерывных справа и имеющих пределы

слева функций, заданных на [0,°о) и принимающих значения в 5 с метрикой Скорохода-

Прохорова-Линдвалла, превращающей это пространство в полное сепарабелыюе метрическое пространство.

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

конструкция превращает У/в полное сепарабелыюе метрическое пространство. Пусть 0([0,1],К) - пространство Скорохода действительнозначных, непрерывных справа, имеющих пределы слева функций на [0,1], и пусть £>„'([(), 1],Е) - подпространство £)([0,1],М), состоящее из неубывающих, равных 0 в точке 0, непрерывных слева в точке 1 функций. Установим взаимнооднозначное соответствие между Ук* и £>¿([0,1],К), сопоставляя функции /еУ^ функцию / = (/(/),7е[0,1]), определяемую соотношениями /(0 = /(-1о§(1-/)),0</<1 и /(1) = йт/(/). Обозначая через с!а (полную) метрику

1—гч

Скорохода-Прохорова £>([0,1],1$), положим по определению р(/,я) = для/, £ е Ук'. Очевидно, что У/с метрикой р является метрическим пространством, гомеоморфно вкладывающимся как замкнутое множество в Д([0,1],М), в частности, оно является полным сепарабельным метрическим пространством. Для

/ = (/я7 = 1 ,...,./) е (К/)7 примем обозначение ||/|| = Кт^/Д.*). Обозначим через

^([О.оо),^) подпространство £)([0,со),К'') покомпонентно неубывающих и равных 0 в

точке 0 функций; через С([(),ю),Л') (соответственно, С+([0,со),М'')) - подпространство

непрерывных функций, лежащих в 0([0,оо),5) соответственно,£>+([0,сю),К*1) через Ус\ -

подпространство £)([(),со),К) неубывающих непрерывных липшицевых функций с

константой Липшица, не превосходящей 1, равных 0 в точке 0; через У/е1 -

подпространство У^, определенное какУ^с1 =У6* пУс+г Все подпространства снабжены

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

1.2.2. Жидкостная модель, основной результат. Мы рассматриваем сеть массового обслуживания, описанную в п. 1.2.1. Через .?(/) обозначим узел, в котором обслуживаются требования класса /, где/= 1,2,..., £. Через с(т),ш = I,...,М , обозначим множество

классов требований, которые обслуживаются в узле т:с(т) = |/е{1,2,...,/,} :.$(/) = /и}.

Сопоставим состоянию сети в момент времени <

векторЛг(/) = (./V,(&,/),/ = \,2,...,Ь,к = 1,2,...), где Ы,(к,1) обозначает количество требований класса / среди первых к заявок в очереди к прибору л(/) в момент / (напомним, что требования в узле стоят в очереди в порядке их поступления). Для / = 1,...,/. обозначим через /*.',(/) количество требований класса /, поступивших извне за время I. Обозначим через >У((/) количество требований класса /, обслуженных прибором .?(/) за время обслуживания заявок этого класса, равное I. Для /,/'= 1,2,...,/, обозначим через Ф(/.(/') количество требований класса / среди первых / требований класса /, обслуженных прибором .?(/), которые после обслуживания превратились в требования класса /'. Всс рассматриваемые нами случайные объекты предполагаются заданными па одном вероятностном пространстве (О,/7,/3).

Определим теперь жидкостную модель, соответствующую данной сети обслуживания. Для этого рассмотрим последовательность сетей обслуживания, занумерованных индексом п и отличающихся от исходной только начальными состояниями (т.е. с теми же процессами поступления, обслуживания и изменения классов требований, задающимися случайными величинами /Г,(г), и Ф„.(/) соответственно). Состояние п-й сети в момент времени I будем обозначать через N"(1) = (Ы"(к,1),1 = I,..., А = 1,2,...). Введем соответствующие нормированные процессы, полагая

я; (/)=-£,(«/), £■(/)=№"('),/ = = (£"(<), '2:0),

п

5,"(0 = -л>/),л"ч0 = (л7(/),/ = 1,...,/.), = ($•(/),/ > 0), п

ф;.(0=-ф,,(«/), Ф"(о=(ф;,,(0,/ = = (ф"(0.' а 0), (2)

п

''(хо={г-7(х,п,х> 0),

^"(0=стчо./=Д ^=(,),!> 0).

Процессы Е", и Ф" рассматриваются как случайные элементы пространств -ОЧ[0,°о)Д''), £>Ч[",°°)Д'') иД+([0,оо)Д'х'), соответственно. Мы рассматриваем Р"(1) как случайный элемент пространства (Г/)'', и - как случайный элемент пространства Скорохода ¿)([0,оо),(^+)'). Заметим, что общее число требований класса /, стоящих в очереди в узле ¡(1) в момент I, равно (],"(!) = /У" (=»,/).

Зададим также процессы В" = (В" (/),/> 0) как В"(/) = (В" (/),/ = 1,...,/,), В;(0 = В;(л/)/и, где в;(/) обозначает время, затраченное узлом .?(/) на обслуживание требований класса / за время I для и-й сети. Поскольку приращения ^ Я,"(/)- ^ В"(!),т = 1,...,М для / > л не превосходят / — л-, то процессы В"

/с <■(„,) /ес(ш)

рассматриваются как случайные элементы У*и - подпространства С"([0,°о),1К'') функций

/ = (/,...,/,) таких, что ^ е,У*„т = ],...,М снабженного индуцированной

/сс(™)

топологией.

Для 1„ > 0 определим сдвиги = (/•'" '"(/),/> 0), В" '1 = (В"Л(/),/ > 0),

=(£"'" >0), Г '' иФ"'° = (ф" '° (/),< > 0), полагая

Р*(0 = /•'"(/ +О, В"'"(0 = й"0 + /„)-/Г(/и), £"•'»(/) = Г (/+/„)-£"(/0),

Предположим, что имеют место законы больших чисел:

л;(о—ф^о-^дл /,/'=1,2,..„г, (з)

где ——> обозначает сходимость по вероятности. Введем функции:

Я = ((Я/,/ = 1 >0), р = ((//,?,/ = 1,...,!),/ >0), р = ((р,^,/,/' = 1,...,£),/ >0).

Обозначим через ,, подпространство пространства ,)' функций

/ = (/,—,/,.) таких, что

X /(*) = * при *< X ||у;||,'п = 1,...,м. (4)

Заметим, что ,, замкнутое .

Пусть С = (С,(/,Ь,с,з>(*)), где />0, /ёО([0,оо),(к;)'), се£>+([0,°о)Д'), 8е0+([0,оо),к') и ф е £>+([0,оо),М''*'-) - функция со значениями в конечномерном векторном пространстве, являющаяся

С([0,оо),К^, ^хГД, хС+([0,оо),М1)хС+([0,«>),К')хС+([0,сю),К'''')-непрерывной и борелевской по /, Ь, е, в и ф при каждом значении^. Предположим также, что О обладает следующим свойством автомоделыюсти:

~С1и(/,Ь,Я,р,р) = С,(/*к,Ь*к,Я,р,р),1>0,к = \,2,-, (5)

где по определению /*к = (к~'/(кх,Ш),х > 0,? > 0) и Ь*к = (к [Ь(к1),1>0).

Будем говорить, что функция й задает жидкостную модель, если для всех и = 1,2,...,, начальных состояний N"(0) и / > 0 имеет место равенство

С1 , В"'1', Г-'", Г, Ф"'") = 0,1 > 0 (6)

Пусть Ырр([0,оо),Уьс1,), где /У>0, обозначает подмножество С'([(),ю),^.,,) функций / = (/|,...,/, ) таких, что

0< ж </,/ = 1.....(7)

х>()

Для /оеКД^ определим ОТ(/0) как множество функций/е!//^^,«)),^,, и), где/? = ^'^(Л( + 2//(), с начальным значением /(0) = /0, для которых существуют такие функцииЬ е Ус\,, что 0,(/,Ь,Л,//,р) = 0,/>0

Мы также обозначим через ОТ,(/0) множество {/(/):/ е 9?1(Уо)} • Назовем семейство ОТ = :/0 еКД,семейством жидкостных решений (траекторий),

соответствующим функции й. Заметим, что ОТ замкнуто в С([0,со),КД|;).

Для а> 0 и g е (Ук')' обозначим через j«« функцию, для которой g о «(х) - ^(«х), х > 0; соответственно, для множества функций Г положим r°a = {g°a:£er}.

Принимая во внимание свойства непрерывности и автомодельное™ функции G, а также тот факт, что множество функций /еЫрр([0,со),К4*с,, ) таких, что ||/(0)|| принадлежит компактному множеству, является компактом в C([0,°o),Ft+e,,.), мы видим, что семейство 9Л обладает следующими свойствами: (автомодсльпость) для £ = 1,2,... и

Щк-'Л » к) = {/•* к, / е ОТ(/0)}, в частности, ОТ, (1/0 о к) = 1 «Dl» (/„) ° t > 0;

(компактность) для каждого а> 0 множество |J Ш(/0) является компактом

Wbuitit*

в С([0,со),КД,,) . Эти условия сстсствспны для жидкостной модели. Наложим следующие ограничения па процессы Е, S иФ.

(А) Последовательности распределений процессов j£",n>l}, js"1,«^} и |ф",и>1} являются, соответственно, C+([0,oo),R')-, C+([0,°o),IR')- и С+([0,со),К'"')-экспонепциалыю плотными с показателем и. Если функционалы действия/5 и /ф являются соответствующими точками накопления в смысле больших уклонений для Е",п> l}, {Г,л>1} и {ф",и>1} для нормирующей последовательности и,то они равны нулю только па функциях Я, р и р соответственно.

Условие (А), в частности, выполнено в обычной ситуации, когда для каждого класса требований входные управляющие последовательности интервалов времени между поступлениями требований и времен обслуживания являются п.о.р., и процессы изменения классов требований после окончания обслуживания являются процессами Бсрнулли. Заметим, что условие (А) влечет за собой (3). Следующая теорема является основным результатом пункта 1.2.

Теорема 7. Пусть функция /„ с Vh\,, такова, что

INI

С:= lim inr J!-ü>0.

1-+=о/е9Л(/0) I

Пусть существует Vkc,, х V*c,, -непрерывная фунщия R: (У/)1 х Уь*с,; —> 1К+ такая, что Л(/,г)ф|-|/|| и R(af,ag) = aR(f,g) для f e(y;)L, а> 0, и

существуют натуральное число ка и числа £ е (0,С), ц ё (0,С/с-1) и 8 > 0, для которых выполнены следующие свойства:

1) Если функция /(¡еУ^сцудовлетворяет условию R:(f0,f0)< б, то sup inf . R(g°2K,go2K)<s2K\

2) Еслифункция f„eV^clL такова, что для некоторого ke{k0,k0 +1,...}, inf Д(/0 ° 2*, g ° 2*) <с2к; то sup inf R(go2k*\go2k*')<€2k*\

geW^i/o) СеМ^шДеМ,,,!«)

Пусть, кроме того, esssup/?(F"(0),yj,)—>0 при п—><ю. Тогда

meii

limPdim--г—!!>C-(l + ^)t = l.

■-»« 2

Следствие 1. При выполнении условий теоремы 1 для всех достаточно больших псправедливо

l¡ml¡mP( ЛГ"(0 >я)>0, и, следовательно, процесс №(t),t> 0, неэргодичен.

и >'-» I >'j II II

1.2.3. Обсуждение. В этом параграфе мы обсуждаем условия Теоремы 7, формулируем различные ее варианты и следствия. Мы также рассматриваем некоторые свойства жидкостных моделей.

Прокомментируем сначала условия 1 и 2 Теоремы 7. Условие 1 выполняется, если жидкостные траектории на конечных интервалах времени непрерывно зависят от начального состояния. Условие 2 означает, что конус траекторий, близких к траекториям, выходящим изf0, "расширяется" не быстрее, чем линейно: если в момент времени 2* жидкостная траектория находится в "окрестности" размера 2l(\ + r¡)c вокруг траекторий, выходящих из точки /0, то в момент времени 2t+l она будет находиться в "окрестности" размера 2мс. Роль расстояния играет здесь функция R, типичными примерами ее

выбора являются «(/,£) = |ИНИ1| и ^(/•¿') = suP|g(j:)-/W|-

i>0

Теорема 7 дает условия, при которых случайный процесс N(í) неэргодичен. Если мы несколько усилим условия теоремы, потребовав, чтобы, начиная с некоторого ка, траектории, близкие в момент 2* к траекториям, выходящим из /0, были близки к ним на всем интервале [2*,2*11 J, а не только в момент 2Ь1, то можно утверждать невозвратность траекторий N(t) в ноль. Именно, имеют место следующие утверждения, доказательства которых аналогичны доказательствам Теоремы 7 и Следствия 1.

Теорема 8. Пусть в Теореме 7 условие 2 заменено следующим условием:

2'. если функция /„е/ ,, такова, что inf /?(/„ ° 2*, ¿ о 2*) < (1 + r¡)e2k

для некоторого ¿e{£0,£0 +1,...}, то sup sup inf (1+0"'л(^(24/)о(2'(1 + /)),й(2'(1+/))о(2*(1 + 0))^^2'.

gEmi/josKis^,«/») v v / \ / \ П

Тогда l¡m Р

Цщ1!-1>c-(\+t¡)E

f->rО t

Следствие 2. При выполнении условий теоремы 2 для всех достаточно больших п

Р(НК(0| = <*>)> 0 т.е. процесс 0 невозвратен.

Замечание. Теоремы 7 и 8 налагают ограничения на расстояния между жидкостными траекториями в моменты 2к,к = к0,к0 + ],... Такой выбор моментов времени не является, однако, единственно возможным: утверждение теоремы остается в силе, если заменить указанную последовательность моментов времени на произвольную возрастающую последовательность ¡к,к = к0,к0 + 1,..., такую, что Нт/4+1 //4 < °о и Нт?<м / ^ >1.

Доказательства отличаются лишь обозначениями.

Глава 2. Термодинамический предел для телекоммуникационных сетей

В этой главе рассматриваются бесконечные сети и сети с растущим к бесконечности числом узлов. Изучаются инвариантные меры таких сетей. Общий случай Пуассоновской 17

гипотезы Боровкова-Клсйпрока для замкнутой симметричной сети на полплсвязном 1рафс был доказан в [21,31-33,35]. Он потребовал исследования предельного нелинейного марковского процесса - нелинейной динамической системы в пространстве вероятностных мер на специальном многообразии, и доказательства того факта, что указанная динамическая система имеет глобальный аттрактор - точку в пространстве вероятностных мер, являющуюся произведением стационарных мер систем M|G/|l|co отдельных узлов сети.

2.1. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе. Пуассоновская гипотеза.

2.1.1. Формулировка задачи. Рассмотрим следующую телекоммуникационную сеть: имеется N обслуживающих устройств (очередей) и М требований. Эти требования находятся в указанных очередях и обслуживаются согласно дисциплине FIFO в каждом узле, причем во всех очередях времена обслуживания образуют последовательность одинаково распределенных независимых случайных величин с (фиксированной) функцией распределения F(x),0 < х < оо. Обозначим через а среднее значение времени обслуживания:

Потребуем также для простоты, чтобы у распределения /*"(■) имелась плотность Р\х). Специальным обстоятельством, выделяющим рассматриваемый класс сетей, является следующее естественное правило маршрутизации: мы будем считать, что всякое требование, заканчивая обслуживание в любом узле, независимо от прошлого поступает в конец любой очереди к соответствующему прибору п = I,..., N с одинаковой

вероятностью Рп = Лг_|.

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

соответствующем фазовом пространстве А(М,Щ св"х2", задаются как набор очередей (к1,...,кп,...,кк) в узлах и набор ^х],...,хп,...,хК} времен, уже затраченных

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

ограничениях на распределение /*'() ■ Действительно, ясно, что с вероятностью единица через конечное время все N требований окажутся в одной очереди, например, па нервом приборе. Затем момент времени, когда очередное требование заканчивает обслуживание (в первом приборе) является моментом восстановления. Поскольку среднее время между наступлением двух соседних таких моментов конечно, то процесс ¥{и д;|(/) эргодичен. Нас будут интересовать свойства семейства инвариантных мер л^О процессов

Нереально надеяться па явное аналитическое нахождение инвариантной меры жмн (') Для общего распределения Р(-) времени обслуживания одного требования и для

произвольных значений параметров Л/,АгеЖ+. Известны два случая, когда удастся явно найти инвариантную меру ли ы: во-первых, когда времена обслуживания требований распределены экспоненциально, и во-вторых, когда все времена обслуживания равны фиксированной константе. В этом (втором) случае возникает конечная цепь Маркова с числом состояний, быстро растущим с ростом М и N, однако, по крайней мерс при малых М и N возможно явно вычислить соответствующую инвариантную меру.

(8)

О

A.A.Боровков в 1995 г. предложил простую и естественную гипотезу о свойствах nMN(:) при N со,M 00, lim MIN = а > 0, заключающуюся в следующем.

Естественно думать, что в указанном термодинамическом пределе потоки требований, поступающие в любое конечное множество очередей, будут пуассоновскими и независимыми между собой, поскольку они являются объединением «бесконечного числа бесконечно малых» потоков требований, поступающих из других различных очередей. Коль скоро это верно, то нетрудно из соображений баланса вычислить предельное значение для интенсивности Я пуассоновского потока, поступающего в любой фиксированный узел. Предельная проекция инвариантной меры на данный узел оказывается стационарной мерой классической системы массового обслуживания Л/ |Сг/ jl |оо, - очереди, с дисциплиной обслуживания FIFO на которую поступает

постоянный пуассоновский поток требований интенсивности X, а длины всех требований взаимно независимы и одинаково распределены с функцией распределения F(-). При этом Л находится из соотношения: среднее число требований в стационарном режиме системы Л/|с/|]|оо совпадает с а = \\т M / N . Прежде всего заметим, что эта гипотеза

была ранее доказана для случая постоянного времени обслуживания в работе А.Столяра3. Отметим также, что факт об асимптотической независимости отдельных узлов при термодинамическом предельном переходе в такого рода задачах принято называть термином "Propagation of Chaos".

Доказательство гипотезы базируется на том факте, что на фазовом пространстве действует группа G симметрий, относительно которой рассматриваемый марковский процесс инвариантен. Это означает, что для любой пары х е A(M,N) и у с Л(М, N) элементов х,у фазового пространства A(M,N) процесса у(м „,(/) и любого элемента группы g е G

Ф,У)---Ч(Я(Х),Х(У)), (9)

где </(■,■) - соответствующие ипфинитизимальные переходные вероятности. В нашем случае группой G является группа перестановок N-го порядка, возникающая при различных перенумирациях N обслуживающих приборов (очередей). Теперь естественно перейти к фактор-процессу £"(■) марковскому процессу, возникающему благодаря (9) на пространстве орбит группы G. Эти орбиты удобно наглядно интерпретировать как специальные вероятностные меры на соответствующем фазовом пространстве. В нашем случае орбиты задаются как наборы долей (плотности долей) очередей (из всего множества N очередей), имеющих фиксированную структуру (длину очереди к и обслуженное время г). Таким образом, этот естественный фактор-процесс описывается как случайная эволюция вероятностных мер на специальном пространстве U.

2.1.2. Основная конструкция и результаты. Приведем более детальное описание фактор-процесса £,"(■) в нашем случае. Пусть N - множество натуральных чисел. Положим t/= {0}u(NxRt). Фазовым пространством процесса ) являются специальные атомарные вероятностные меры lia U. Меру х мы называем рациональной со знаменателем N, если значение х - меры любого измеримого по ней множества является рациональным числом со знаменателем N. Множество таких вероятностных мер на пространстве U мы обозначаем через PN. Всякая мера х cPN образована N атомами, расположенными в пространстве U, каждый из которых имеет меру 1 /N. Допускается, чтобы некоторые их этих атомов сливались. Атомарная мера х gРд, имеет следующую

3 Столяр Л.Л. Асимптотика стационарного распределения для одной замкнутой системы обслуживания// Пробл. 11срсдачи информ. 1989. Т.25. №4. С. 80-92. 19

интерпретацию: мера атомов, расположенных в точке [0] с и интерпретируется как доля пустых очередей (из N очередей) для состояния процесса £"(•)• Атом массы МЫ, находящийся на и-м луче и имеющий координату г на этом луче означает, что у состояния хеР„ имеется очередь, содержащая ровно п требований, причем требование, находящееся на обслуживании, уже обслуживается ровно время г.

Опишем наглядно случайную эволюцию атомарных мер х соответствующую марковскому процессу £"(•):

1) у всех атомов типа (я,г),«>1, лежащих на лучах (я,М4),я>1 со скоростью единица растет координата т, - это соответствует продолжению обслуживания требований, обслуживающихся в непустых очередях;

2) атомы с координатами (л,г),я>1 совершают прыжки в точки (я-1,0) с

/.' '(г)

иптепсивпостями /?(г) = -—- эти события означают, что требование, находящееся па

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

3) в момент прыжка, описанного в н.2) происходит следующее событие: с вероятностью 1 /N выбирается произвольный атом из конфигурации, пусть, например, его координаты (л',г')еС/, (если выбранный атом находился в {0}еС, то для пего координата г'= 0) и выбранный атом прыгает из точки (п',т')еС/ в точку (п'+1,т')е11. Это событие соответствует переходу требования, закончившего обслуживание в узле с очередью (л, г) в очередь (л ',!"')•

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

общности, описан в [20,21], разделы 2 и 3. В дискретном случае множество состояний нашей марковской цепи - это симплекс Ак всех вероятностных мер на 51,

А4 ={// = (/•.....,Рк)'Р1 ^0,/7, + ...+ рк = 1}, а эволюция марковского процесса определяет

отображение Р:А, —>Д4. В случае обычной марковской цепи отображение Р аффинно, и поэтому мы будем называть такую цепь линейной. Матрица переходных вероятностей совпадает с Р. Нелинейная марковская цепь определяется семейством матриц переходных вероятностей еД4, где элемент /}((/, /) есть вероятность перехода от / к 7 за один шаг, начиная из состояния ц. Нелинейное отображение Р теперь определяется как Р^=мР/1.

Эргодичсские свойства линейных марковских цепей определяются теоремой Фробениуса-Перрона. В частности, если линейное отображение Р таково, что образ Р(Д4) содержится во внутренности /я/(Д4) множества Д4, то существует в точности одна точкаме/л<(Д4), такая что Р(//) = // и для любого УеА, имеется сходимость Р"(у) —» ц при л °о.

Если отображение Р нелинейно, то мы имеем дело с более или менее произвольной динамической системой на Д4, и в общем случае нельзя ответить на вопрос о

4 McKcan, II., P.,Jr. A class ofMarkov processes associated with non-linear parabolic equations. 1'roc. Nat. Acad. Sci. USA., 56, 1966, 1907-1911.

5 McKcan, II., P.,Jr. An exponential formula for solving Boltzmann's equation for a Maxwcllian gas. J. Combinatorial Theory, 2, 1967, 358-382.

стационарных состояниях цени или о мерах на множестве Л,, инвариантных относительно Р.

Замечательным обстоятельством является то, что имеется предельная при N—> оо, М-» со детерминированная динамическая систсма у -> х(1,у),у<вР ,х(1,у) сР ,/ > О, описывающая предельную детерминированную эволюцию вероятностных мер па том же фазовом пространстве (У, Эта динамическая система задается бесконечной нелинейной системой интегро-дифферепциальиых уравнений в соответствующем банаховом пространстве, и следующим необходимым шагом является доказательство существования и единственности решения этой системы уравнений. Здесь (и далее) помогает вероятностная интерпретация решения системы у х(/,у),у еР ,х(1,у)еР ,/> 0 как эволюция вероятностной меры, задающей соответствующий нелинейный марковский процесс. В нашем случае этот нелинейный марковский процесс наглядно устроен следующим образом: пусть имеется неоднородный марковский процесс ¿¡™(1), описывающий эволюцию очереди А/(<)|С/|1|°о на которую поступает переменный пуассоновский поток интенсивности Я(/). Точкам фазового пространства процесса £ "(1) сопоставим точки и полагая, что точка (и, г) соответствует следующему событию -длина очереди процесса !;" (/) равна и, а обслуживаемое требование обслуживалось время г . Обозначим через у = х(0) начальное состояние процесса £"(/) - вероятностную меру на С/ = {()} и (NхРч). Обозначим через х(1,у) еР вероятностную меру па II для процесса А/(/)|(7/|1|со в момент времени /. Наложим на Я(/) дополнительное условие, связав Л(1) с самой мерой д:(1,у) на очередях нашего процесса Л/(7)|С/| ||'» в момент I: именно, положим 1(1) равной средней по мере х(1,у) интенсивности выхода требований из очереди.

Обозначим через £,"(1) нелинейный марковский процесс, соответствующий эволюции мер у—*x(t,y) процесса £"(0 для входа которого выполняется дополнительное равенство (10).

Теорема 9. Пусть функция ß(r),r еМ+ принадлежит банахову пространству C|(Rt). Тогда для любой начальной вероятностной мерыу^Р нелинейный марковский процесс, отвечающий динамической системе y^x(t,y),yeP,l> 0 существует и единственен.

Доказательство это теоремы основано па использовании принципа сжатых отображений.

Следующим шагом является доказательство сходимости при N -» да, М -> со, lim М / N = а > 0 марковских процессов £"(•) к предельной

VV->oo

динамической системе - нелинейному марковскому процессу При любом 1> 0

определим линейный оператор T(l): T(t)F (у) = F (jc(i,>>)),действующий в множестве функций на Р .

Обозначим через BN банахово пространство ограниченных числовых функций на PN, с нормой ||F I =sup|F (x)\,F s BN.

Марковскому процессу £"(■) с пространством состояний Pv отвечает полугруппа Тя(-) линейных операторов, действующих в пространстве Вч. Именно, если F с BN, то 21

(10)

(TN(t)F )(x) = E(F (0)|v(0) = x),xeP„.

Теорема 10. Для любого t> 0 и любой функции F и Р , непрерывной в слабой топологии, выполняется равенство

lim siip |7-„(/)Я (y)-F (x(t,y))| = 0

"-»"Vif,

(11)

Сходимость в (II) равномерна на каждом отрезке изменения I.

Доказательство этой теоремы основано на использовании теоремы Тротгера-Куртца о сходимости марковских полугрупп.

Теорема 11. Для нелинейного марковского процесса определяющего

специальную эволюцию очереди M(/)|G/|l|°o при любой начальной мере у, функция Л(1) при /—>оо сходится к константе Л = Л(у), где X находится из соотношения: средняя длина очереди по стационарной мере для системы оо с входным пуассоновским

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

Таким образом, из Теорем 9-11 следует справедливость пуассопопской гипотезы для рассматриваемой модели — последовательности процессов £"(•), поскольку из общих теорем о сходимости марковских полу|-рупп следует, что множество инвариантных мер нелинейной динамической системы >>-> x(i,_y),y еР ,(> 0 содержит все предельные точки множества яиы и поскольку, согласно Теореме 11, процесс £,'(') "Ри фиксированной начальной средней длине очереди сходится к единственной инвариантной мере. Сложное но существу и ¡ромоздкое доказательство Теоремы 11 основано на следующем нетривиальном свойстве самоусрсднепия.

2.1.3. Свойства самоусрсдпснии систем массового обслуживании.

Рассмотрим неоднородный по времени случайный процесс - систему массового обслуживания A/(/)|G|l|°o, на которую поступает пуассоповский поток переменной интенсивности Л(/), а времена обслуживания образуют стационарную эргодическую последовательность со средним временем обслуживания равным единице. Наложим па функцию Л(1) условие пеперегруженности: 1 0

/ = limsup— \Л(х)йх<\

7--ко Т _т

(12)

Наложим также на функцию Л(1) следующее условие: Л(t) является непрерывной положительной функцией и следующие интегралы расходятся

Ü со

¡Л(х)dx = <x>, |Л(*)Л = оо. (13)

—о

Теорема 12. Обозначим через b(t) интенсивность окончания обслуживания требований в момент времени t для указанной системы M(<)|G|l|«>. Тогда функция b(t) удовлетворяет уравнению:

b(t) = A(t-x)qiJ(x)dx, -оо <1 <аа, (14)

где ядра ql t зависят от функции Л только через ограничение Более того,

эти ядра стохастические, т.е. для каждого t выполнено

]qxj(x)dx = \, (15)

О

где qi ,(jc) = 0 при х < О.

В работах [31-33] Теорема 12 была доказана для системы M(i)|G/|l|oo. Доказательство было основано на новых нетривиальных комбинаторных конструкциях. Общий результат - Теорема 12 для системы M(/)|(7|l|co доказан в [35].

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

Содержание этой главы основано на работах [39,41]. Техника, развитая в [21,22,31-33,35] позволила изучать термодинамический предел инвариантных мер марковских процессов, описывающих симметричные сети более сложной природы, чем замкнутые сети на полном графе с одним типом требований. Модели реальных телекоммуникационных сетей (напр. Internet) требуют изучения сетей со многими классами требований и со многими типами узлов с различными параметрами. Неожиданно оказалось, что Пуассоновская гипотеза Клсйнрока для симметричных замкнутых сетей с несколькими типами узлов и несколькими классами требований, вообще говоря, неверна при достаточно большой нагрузке (отношению числа требований к числу узлов). Доказательство этого факта в [41] основано как на изучении свойств жидкостного

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

3.1. Спонтапныс резопанем и когерентные состояния в сетях с очередями.

3.1.1. Инфрмациопные сети и их коллективное поведение. Пуассоновская гипотеза является инструментом, позволяющим предсказывать поведение больших систем с очередями. Она впервые была сформулирована Л.Клейнроком и касается следующей ситуации. Рассмотрим большую сеть, состоящую из серверов, по которым циркулирует большое число требований. Требования обслуживаются в различных узлах сети. Если узел занят, то требование становится в очередь. Требования поступают в сеть извне через некоторые из узлов, и эти внешние потоки требований - пуассоновские, с постоянными интснсивпосгями. Время обслуживания на каждом узле случайное, зависящее как от узла, так и от требования. Пуассоновская гипотеза предсказывает следующее поведение сети в большом масштабе пространства и времени:

• Рассмотрим полный входящий поток F требований на данный узел N . Тогда F приближенно равен пуассоповскому потоку Р с зависящей от времени функцией интенсивности (Т).

• Выходящий поток из узла N - не пуассоповский в общем случае! - имеет интенсивность yN (Г), которая, как функция времени, япляется более гладкой, чем (Г) (из-за усреднения, имеющего место в узле N ).

• В результате интенсивности потоков AN (Т) на разных узлах N сходятся к

_ 1 г

постоянным пределам Лд, и— £ AN (t)dt при Т —>со. Потоки, приходящие на различные

узлы, почти независимы.

• Скорость сходимости равномерна относительно размеров системы.

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

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

Основания для такого предположения естественны: поскольку входной поток сеть сумма многих малых потоков, он близок к пуассоповскому. И благодаря случайной природе времен обслуживания выходящий поток из каждого узла должен быть «более гладким» чем полный входящий поток. Понятно, что пуассоповская г ипотеза может быть верпа лишь в термодинамическом пределе, когда число узлон стремится к бесконечности. Она была доказана для симметричных замкнутых сстсй па полпосвязпых графах в [21,31-33] при довольно общих предположениях. В частности, вариация выходящего потока оказалась меньше, чем входящего, так что все потоки должны со временем сойтись к соответствующим постоянным значениям.

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

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

Сеть V^ строится из бесконечного числа экземпляров элементарной треугольной сети V (описанной ниже). Единичная треугольная сеть V = V, с N требованиями представляет собой эргодический марковский процесс скачков с непрерывным временем и конечным множеством состояний. Когда N растет, этот процесс сходится (в эйлеровском пределе) к 5-мсрной жидкостной «динамической системе» А, имеющей периодическую траекторию С , которая оказывается устойчивым (локальным) аттрактором. Составная система соответствует в некотором смысле склеенному семейству Ди динамических систем Д. Мы докажем свойство синхронизации этого склеенного семейства А^, и это позволит нам строить когерентные состояния сети Vx.

Сети Ум, составленные из M треугольных сетей V, являются эргодическими. Их эволюция задастся неприводимыми марковскими процессами па конечном числе состояггий в непрерывном времени. Пусть пи - инвариантная мера процесса V,,. При М—>оо последовательность марковских процессов Vw слабо сходится на конечных интервалах времени к ггекоторому предельному (нелинейному марковскому) процессу . Тогда, по известной теореме принадлежащей Р.З.Хасьмипскому6 - любая точка накопления последовательности яи является стационарной мерой процесса V„. Специальная мера описывающая поведение, предписанное пуассоповской гипотезой, тоже является стационарной мерой процесса . Если - глобальный аттрактор для V„, то, конечно, пуассоповская гипотеза справедлива. Доказательство пуассоповской гипотезы в работах [31,32] основано на этих рассуждениях. Существование точки накопления последовательности nu, отличной от > было бы самым сильным контрпримером к пуассоповской гипотезе. Здесь мы доказываем более слабое утверждение о том, что ^ не является глобальным аттрактором для процесса .

6 Theorem 1,2,14 в Liggett, Thomas M. Interacting particle systems. Grundlchrcn der Mathematischen Wissenschaften, 276. Springer-Verlag, New-York, 1985.

3.1.2. Основная сеть. Рассмотрим следующий пятимерный марковский процесс V". Он описывает замкнутую сеть с N требованиями. Эта сеть является замкнутым аналогом открытой сети, изученной в [13], в которой требования, покидая сеть, попадают в дополнительный узел О, из которого они возвращаются назад. Сеть состоит из трех узлов: О, Л и В обслуживающих требования. Все времена обслуживания экспоненциальны, поэтому нам достаточно указать интенсивности обслуживания, правила эволюции классов требований и приоритеты. В узле О все требования имеют класс О. Узел О обслуживает требования по принципу FIFO, с интенсивностью /0 = 3. После обслуживания требование переходит на узел А или В выбирая один из них с вероятностью ^. Если оно переходит па А, оно становится требованием класса А, в

противном случае - класса В. Требование класса А обслуживается с интенсивностью 7^=10, а затем переходит на узел В, получая класс АВ. Там оно обслуживается с интенсивностью уАВ = 2 и возвращается в узел О, получая класс О. Симметрично, требование класса В в узле В обслуживается с интенсивностью уя = 10 и затем попадает в узел А, где оно становится требованием класса ВА ,и обслуживается с интенсивностью уйл = 2 в узле A после чего оно вновь возвращается в узел О, получая класс О.

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

3.1.3. М связанных процессов. Пусть VNM - марковский процесс, построенный из

М копий сстиУ", связанных по схеме среднего поля. Полное число требований в сети будет взято равным NM. В дальнейшем мы будем иногда опускать индекс N

Срсдпеполевая сеть определяется следующим образом. Каждый узел Oi, i = \,...,M, соединяется со всеми узлами AJt Bj, j = 1,..., М, и каждое требование, покидающее узел

О., поступает на один из 2М узлов Aj, Ву с одинаковой вероятностью .

Интенсивность обслуживания на узле Oi такая же, как и выше, т.е. равна у„= 3. Аналогично, требования класса А на каждом из узлов Д обслуживаются с

интенсивностьюуАЙ =10, а затем выбирают один из узлов В. с вероятностью — и так

М

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

Конфигурация процесса определяется числом требований каждого класса на каждом из ЪМ узлов, то есть целочисленной точкой в пространстве (R5")'. В силу срсдпсполевой симметрии, множество конфигураций может быть факторизовано по произведению групп перестановок Su х Su х Su, и по-прежнему оставаться марковским

M = M

всех вероятностных мер на | —г£ | . Заметим, что каждая такая мера

процессом. Орбита симметрической группы соответствует семейству Л/5 целочисленных точек х. б(Е5)*, некоторые из которых могу т совпадать.

Мам будет удобно представлять эти конфигурации как атомарные меры

о6)

Нам удобно считать эти рациональные атомарные меры принадлежащими множеству

разлагается в произведение = рах рй = Пб[/фПг[/*]хПд[//]

вероятностных мер на К'={дг0}, соответственно R2 = {д^.дг^} и К2 = {х„,хА11}. Здесь

через П. мы обозначили различные проекции. Получаем р(> = ~ " àx для некоторых

(не обязательно различных)^ eZ1, i = I,...,M, а также. /'g = Sx.,

x/,xt"e 1?. Обозначим множество всех таких мер через М„. Состояние v^ нашего марковского процесса теперь можно интерпретировать как элемент множества M (М„), т.е. как вероятностную меру на измеримом пространстве М„. Среди этих мер есть конфигурации процесса Vj, а именно, i-меры 5т при твМи, поэтому можно определить вложение М„сИ (М„). Тем не менее, даже если начальное состояние v£(0) процесса VNU оказывается такой мерой 5т, т.е. (0) е M и, то при любом положительном t мы можем лишь утверждать, что (Ми), тогда как

Пусть дана последовательность v^(0)eM(MM) начальных состояний марковского процессаV^, удовлетворяющая условию ^(0) = ^ , при ш„еМ„, и пусть слабый предел >' = 1'тм-,„тм существует. Тогда слабые пределы v(l) = vu (/) существуют при любом /, и, кроме того, при любом t выполнено

v(/)eM . Это нелинейный марковский процесс, 11МП, обозначаемый через V". Процесс называется нелинейным, так как механизм эволюции из данной конфигурации зависит не только от этой конфигурации, но и от всей меры, из которой эта конфигурация была выбрана. Построенные ниже предельные НМП зависят от параметра N - количества клиентов в расчете на одну базовую сеть. Нашей целью является изучение зависимости от N, поэтому мы введем индекс N явным образом в наши обозначения. Таким образом, через v"(t) мы обозначаем состояния процесса V*.

Предельный НМП будет подробно описан в следующем разделе. Сформулируем теперь предварительную версию нашего основного результата.

Теорема 13. Рассмотрим нелинейный марковский процесс V", стартующий из меры у", являющейся атомарной мерой с атомом на векторе X(A,N)b7J, у которого координата хЛ=Ы а все остальные координаты нулевые. Тогда мера vit) не стремится ни к какому пределу при / —> оо, если N достаточно велико.

Точнее, существует такая последовательность моментов времени —>ао, что > , где сн ->0 при N -> °о. Здесь окрестность

точки Х(Л,Л') радиуса (Л^), где кы(ЛГ) -»0 п/и/ N —><х>. В то .же время, существует другая последовательность —>со, для которой > 1 — £ы-

Другими словами, мера колеблется во времени.

Соответственно, состояния конечных сетей долгое время осциллируют

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

3.1.4. Нелинейный марковский процесс V*. Дадим кратко наглядную интерпретацию нелинейного марковского процесса аналогично тому, как мы

описали нелинейный марковский процесс £"(■) в главе 2.

Сначала рассмотрим тройку независимых неоднородных по времени марковских процессов <5(0 и Е,"п (I). Неоднородный процесс описывает эволюцию

открытой системы Л(0|М|1|°о, в которую поступает переменный по времени пуассоновский поток требований типа О. Пусть ¿¡¿(1) - это неоднородный по времени процесс, описывающий эволюцию открытой системы Я(/)|л/|1|оо, в которую поступает пара пуассоповских потоков переменной интенсивности {ЛА(1),Л1И(1)} требований типа А и ВА соответственно. Как и ранее, требования типа ВА имеют в узле А абсолютный приоритет. Аналогично, пусть ¿¡¡'¡(/) - неоднородный во времени процесс, описывающий эволюцию открытой системы л(/)|л?|1|а>, в которую поступает пара пуассоповских потоков переменной интенсивности {ЛДОДлдМ} требований типа В и АВ соответственно, причем требования типа АВ абсолютный приоритет в узле В.

Зафиксируем случайные начальные состояния £д(0) = ¿^'(0) = и (0) = с суммарным средним числом требований равным 3 N. Обозначим через {|'о(0>//^(0>/'в(0} тройку вероятностных мер для неоднородных независимых марковских процессов (0>£Г (0>£г (')} в момент /. Обозначим через ЬА(1) среднюю по мерс //^(0 интенсивность окончания обслуживания требований класса А в узле А в момент 1. Обозначим через ЬВА{() среднюю по мере (/) интенсивность окончания обслуживания требований класса В А в узле А в момент I. Аналогично, обозначим через ЬЙ(1) среднюю интенсивность но мере /'„(') окончания обслуживания требований класса В в узле В в момент /. Обозначим через Ьлп{1) среднюю интенсивность по мерс (1) окончания обслуживания требований класса АВ в узле В в момент /. Наконец, обозначим через Ьа(1) среднюю по мере р(1(1) интенсивность окончания обслуживания требований класса О в узле О в момент /. Наложим па интенсивности поступления требований в узлы О, А и В следующее дополнительное соотношение:

<*„(') = ¿.(0 = ^,(0

•Ллв(') = Ьл(>) (17)

Л, (О = М0 Л(') = МО+МО

Эта система уравнений является одновременно неявной системой уравнений на меры ■ Обозначим через И(/) = {^(0x1^(0x^(0} еМ где тройка

Уй(.1) = /'о( 0. ^(0 = ^(0. ^¡¡(0 = /'й(0 и {^й(0,^-(0./'в(0} удовлетворяет дополнительному соотношению (17). Имеет место следующая теорема, аналог Теоремы 9.

Теорема 14. Отображение: у" —> у"((0|у"(0) = V") задает динамическую систему в пространстве М , причем среднее число требований для у"(1) не меняется по I и равно

N.

Тем самым решение системы уравнений (17) существует и единственно и определяет нелинейный марковский процесс V". Эта теорема также доказывается при помощи принципа сжатых отображений. Следующий результат аналогичен Теореме 10. Он заключается в доказательстве сходимости при А/—>сю марковских процессов У^ к предельной динамической системе - нелинейному марковскому процессу V". При любом />0 определим линейный оператор 7X0: ^(О^М = ^ОЧ')!^")= Действующий на множестве функций от уе М . Обозначим через Ви банахово пространство ограниченных числовых функций на М^ с нормой

||Р|| = 8ир|Р(4РеВи.

Марковскому процессу V^(•) с пространством состояний М^ отвечает марковская полугруппа 7^(/) линейных операторов, действующих в пространстве Ви. Именно, если Р еВи,то

Тсорема15. Для любого /> 0 и любой функции Р на М", непрерывной в слабой топологии, выполняется равенство

Гш 8ир|гмя(/)Р(И)-Р(И(/)(И(0) = у")| = 0. (18)

Сходимость здесь равномерна па каждом отрезке изменения I.

Доказательство этой теоремы также основано на использовании Теоремы Троттера-Куртца о сходимости марковских полугрупп.

Однако, в отличие от нелинейного марковского процесса I) из 2.1, процесс V* (0 отнюдь не сходится к ^-неподвижной точке при больших значениях N. У процесса У*(0 при больших N имеется нетривиальное инвариантное множество, окрестность в топологии Канторовича-Рубинштейна некоторого специального цикла С.

Доказательство этого утверждения весьма сложно и фомоздко и составляет основное содержание [41]. Опишем кратко конструкцию этого цикла. Рассмотрим А(/) -жидкостную эволюцию единственного экземпляра треугольной сети У,(0 ПРИ М=\.

Сначала доказывается, что для этой жидкостной динамики имеется нетривиальный аттрактор - цикл С(/) е М*.

Затем рассматривается жидкостная динамика Аи(') Для процесса Vм(^) при

произвольном М. У этой жидкостной динамики имеется следующее замечательное свойство синхронизации: интенсивности входных потоков жидкостей одинаковых классов в одноименные узлы совпадают между собой в любой момент времени. Это свойство следует из самой конструкции жидкостного предела и из того факта, что каждое требование фиксированного класса после окончания обслуживания выбирает последующий узел из множества узлов соответствующего тина равновероятно. Отсюда следует, что начиная с некоторого момента жидкостные траектории процесса Л„ (/) синхронизируются: количества одноименных жидкостей во всех одноименных узлах М с некоторого момента Т = Т(М) совпадают, после чего жидкостная эволюция для процесса Дм(/) становится неотличима от жидкостной эволюции Л(') Следовательно,

жидкостная эволюция для процесса ЛА, (/) также имеет аттрактор - цикл С(/), лежащий на 5-мсрной диагонали пространства

Построив нелинейную жидкостную динамику Л, (/) для нелинейного марковского процесса удается доказать существование аттрактора - предельного

цикла и для этой жидкостной динамики. Доказав сходимость в эйлеровском сксйлинге при Ы—>оо процесса I) к жидкостной динамике Д., (V) получим, что при больших

значениях N траектория и'"" (/) процесса никогда не выходит из малой окрестности

цикла ОД, что и составляет утверждение Теоремы 13.

3.2. Справедливость пуассоповской гипотезы. Замкнутые сети при малой нагрузке.

3.2.1. Постановка задачи. Долгое время предполагалось, что справедливость Пуассоповской гипотезы является общим свойством всех больших сильно связных сетей. Она была доказана для замкнутой симметричной сети - полпосвязного графа в [21,31-33,35]. Однако были найдены и контрпримеры (см. [38], где рассматривались специфические распределения времени обслуживания, и особенно [41], где была построена сеть с экспоненциальными временами обслуживания, для которой Пуассоновская гипотеза перестает выполняться при высоких нагрузках). Мы предполагаем, что ситуация здесь аналогична ситуации в статистической механике, где все модели ведут себя сходно при высоких температурах, тогда как при низких температурах некоторые из них демонстрируют фазовые переходы. В симметричных сетях массового обслуживания аналогом (обратной) температуры является средняя нагрузка на сервер - р, и пример, приведенный в [41], есть пример такого фазового

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

Пусть О ~(у,Е) - конечный граф. Мы интерпретируем граф С как сеть, состоящую из серверов, обслуживающих требования. Таким образом, мы предполагаем, что граф б наделен некоторыми дополнительными структурами. Во-первых, на каждый сервер иеУ могут приходить требования различной природы: с каждым сервером и мы ассоциируем (конечное) множество классов - или цветов -{сеС(и)]. Таким образом мы определяем

пеперссскающссся объединение V = 1)|ж(,С(о) всех возможных классов требований. Мы соединяем пару (ц,с,) с парой (и2,с2), где с, еС(ц), с помощью направленнго ребра, се£, ссли (ц,о2) является ребром в Е, и если, кроме того, требование класса с, обслуживается сервером и, и в результате попадает на сервер и2 как требование класса сг.

Пока что мы просто определили новый (больший и направленный) граф 0 = (У,Е). Далее мы должны задать времена обслуживания. Мы будем предполагать их экспоненциально распределенными с интснсивпостями у(р,с)> 0.

Последняя информация, которая понадобится для определения системы, касается переходной матрицы вероятностей /> = |/,^ц,с, ),(и2,с2)Л на О. Величина />[(у|,с|),(и2,с2)] - это вероятность того, что требование класса с, на узле у, попадет затем на узел о2 как требование класса с2.

Мы хотим также наложить на нашу элементарную сеть (О,у) условие связности:

Условие 1. Эргодичность матрицы Р. Рассмотрим Марковский процесс С с непрерывным временем, отвечающий Случаю Единственнго Требования. Это означает, что в нашей сети находится лишь одно требование. Изначально он находится на некотором сервере и и имеет цвет с е С (и). С течением времени требование меняет свое местоположение и цвет случайным образом с интенсивностями, задаваемыми функциями /(■, •), и переходными вероятностями Р. Мы хотим, чтобы этот Марковский процесс (с непрерывным временем, на конечном числе состояний) был эргодическим. Это эквивачентно эргодичности Марковской цепи, определяемой матрицей Р.

В тех сетях, которые мы здесь рассматриваем, будет циркулировать большое число требований, поэтому мы должны объяснить, что происходит, когда несколько требований приходят на обслуживание в тот же самый узел. Здесь мы опишем достаточно общую ситуацию. Предположим, что на сервере и в момент времени I имеется очередь хи = {с,,с2,...,с4} требований с. бС(м). Это означает, что эти требования пришли па узел и до момента I, и по-прежнему находятся там в момент ожидая обслуживания. Они записаны в очередь в порядке их поступления. Величина к = к(хи) называется длиной очереди (на сервере и в момент /). Дисциплина У?(и) - это правило /ц(*) для сервера и, которое сопоставляет каждой непустой очереди хи индекс 1 </„(*„)<£ т.е. индекс требования в очереди ха, обслуживание которого происходит в момент 1. Как только обслуживание этого требования завершается и оно покидает сервер, очередь ха превращается в очередь

Например, сервер может обслуживать требования просто в порядке их поступления, то есть i„(x„) = 1. Эта дисциплина FIFO Мы будем изучать достаточно общий класс дисциплин, с двумя ограничениями.

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

Вторым ограничением является следующее свойство монотонности. Пусть cf'.cj2,...,^',... - последовательность прихода требований на узел и, где /( - момент

(19)

прихода /-го требования. Пусть нам известно время, необходимое для обслуживания каждого требования. Тогда дисциплина Н(и) позволяет определить функцию N(1), значением которой является длина очереди в момент / > 0. Рассмотрим теперь другую последовательность поступлений, отличающуюся от предыдущей на одно дополнительное требование с: с\',... где /, <1 </,,,. При этом N'(1) - длина очереди изменится. Мы хотим, чтобы ЛГе(/) >для всех />0. Этим свойством обладает большинство естественных дисциплин обслуживания.

Отмстим, что допускается ситуация, когда обслуживание требования с прерывается, когда поступает требование с более высоким приоритетом. Обслуживание требования с затем возобновляется в соответствии с правилом приоритетов Я ('•>).

3.2.2 Графы типа среднего поля. Сопоставим теперь графу О = (V, Е) последовательность (^>((7) = С с с... с: О,(О) с:... графов, конструируемых следующим образом. Для любого М рассмотрим сначала непересекающееся объединение М экземпляров О' = (V,/■'') графа С, / = I,...,М. Полученный граф <2|,=(\/',Е') имеет

множество вершин Ум = Ц" V, т.е. всех вершин этих М экземпляров графа С. Определим теперь множество ребер графа с множеством вершин Уи. Мы будем считать пару (и[,о'г)с:Ум ребром графа Е^ ц' еУ,и{ еК7,/,/ = 1,...,Л/, если и только если две вершины и,, и2 с- V соединены ребром ее/;. Таким образом, каждое ребро графа О порождает ровно Мг ребер графа Е^. Других ребер в графе Е^ нет.

Например, если граф О состоит из единственной вершины и, соединенной с самой собой посредством петли, то граф О, (С) - полный граф с М вершинами и дополнительной истлей у каждой вершины.

Теперь мы определим средпе-полсвые графы (О') точно таким же образом, как выше. Конечно, у этих графов есть естественная ориентация, унаследованная от графа О. Все функции интенсивности сохраняются, а переходная матрица Ри определяется как

Всюду в дальнейшем мы фиксируем элементарную сеть (С,/), и изучаем соответствующие модели среднего поля О,((!), населенные N-\_рМ \ требованиями. Параметр р мы назовем нагрузкой. Таким образом, для каждого М мы строим эргодический марковский процесс на сети С^, (С) с N требованиями. Обозначим этот процесс , а через л''м обозначим его инвариантную меру. Нас будут интересовать асимптотические свойства этих стационарных состояний лрх1 при А/-»со, а также свойство сходимости состояний процесса Ум в момент I к пределу яри при >оо.

Говоря неформально, пуассоповская гипотеза для средне-полевых сетей ОДСг) утверждает о поведении мер у£,(0 при больших М следующее: если начальное состояние выбрано подходящим образом, что означает, что длины начальных

очередей в каждом узле не превосходят некоторой константы К, то через некоторое время Т(К), не зависящее от М.

• Все М\У\ серверов нашей сети становятся почти независимыми, т.е. мера близка к мере-произведению па множестве Ум;

• Па каждом узле процесс v«(/) выглядит так, как будто бы входные

потоки всех возможных классов требований на и являются независимыми пуассоновскими потоками Рс,сеС(и) с постоянными интснсивностями Лс (зависящими только от р, графа G и функции/, но не от М или /). Эти требования затем образуют очередь на v и обслуживаются согласно правилу R(p), а затем покидают сервер. Обозначим стационарное состояние такого узла через Эквивалентно,

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

Эгот процесс начинается из пустого состояния 0 е , требования класса с еС(и) поступают в моменты времени образующие пуассоповский поток интенсивности Лс, последовательность их обслуживания задается правилом Л„, времена обслуживания имеют экспоненциальное распределение с интснсивностями ^(о,с)>0, после обслуживания требования покидают сервер.

В этом случае мы очевидным образом получаем соотношения

V = E Z \A(v,c\(u\c% (20)

и< V и С(р)

где с'еС(и'). Они определяют множество ипгснсивностсй

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

Отметим, что ожидаемое число требований, N = Л'(А), имеющихся в сети G в состоянии к Дг'"**lC<"" > как Функция а, т.е. N(aX) непрерывно и строго возрастает но а, если Л ^ 0.

Поэтому, в силу эргодичности матрицы Р, интенсивности Я'' однозначно определены соотношениями (20), дополненными уравнением N(A) = p. Обозначим стационарное распределение очередей, соответствующее упомянутым пуассоновским входным потокам Xе, через хР'-

ис-У

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

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

Марковские процессы v«(0 и стационарные меры определенные выше,

являются мерами на пространстве конфигураций пашей системы, т.е. па С2М,

гдсП = ■ Пусть (х1 ,...,хи) с Q" - случайная конфигурация нашего процесса.

Рассмотрим случайную меру eM(i2). В силу симметрии нашей сети

относительно группы перестановок Su, описанные процессы на мерах по-прежнему марковские. Это позволяет нам интерпретировать все меры v'^(t) и крм как меры па одном и том же пространстве М (П). Они совпадают с частотами данного состояния на данном сервере в сети Cjf(G). Поэтому меры vpM{t~) и л''м стагговятся элементами пространства М (М(Q)). Тем не менее, предельная мера vf(i)eM(M(ü)) оказывается атомарной мерой и, таким образом, может быть записагга как vp(t) = 8K при к е М (П). Нарушая немного строгость обозначений, мы будем отождествлять меру rf(()eM(M(Ci)) с этой мерой /ceM(Q), и скажем, что vp(t)еМ(П). Процесс vp(t) -это Нелинейный Марковский Процесс (НМП, см. [21,31-33].)

В принятых обозначениях предыдущие утверждеггия означают, что сходимость vm (0 71 м равномерна по М, и что при —> %р при М —> оо. Меру %р мы будем называть «динамикой Пуассоновской гипотезы».

3.2.3. Основной результат. Рассмотрим элементарную есть (G,y), связную в смысле условия 1. Мы предположим, что па каждом сервере veV задана консервативная дисциплина обслуживания R(u), определяющая ггорядок, в котором обслуживаются требования из очереди. Рассмотрим теперь последовательность Vu марковских процессов на сетях Gj,(G"), М = 1,2,..., населенных N = \_pM\ требованиями. Пусть лрм -инвариантная мера процесса VM .

Теорема 16. Сходимость. Существует значение р = p(G,y,Р)> О, такое, что для любого р < p(Gy у, Р) слабый предел üm,,^ лрм существует и равен мере %Р ■

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

Теорема 17. Экспоненциальная скорость сходимости. Пусть марковский процесс Vpu стартует из состояния Г'м(О), обладающего тем свойством, что в каждом узле $L>€ Vu длина очереди ки = k(v,t = 0) удовлетворяет уравнению

|ехр{и^}^(0)<^, (22)

где х>0, К - некоторые константы, также зависящие от (G,y,Pj. Пусть р < p(G,y). Тогда, для любой локальной функции /, получаем

|JßvM (0 _ |ß71» | -1|/|| СХР {~т1} • константа т = г(и, К) не зависит от М.

В главе 3 мы называем функцию локальной, если она зависит лишь от состояний конечного числа серверов. Здесь мы приводим доказательства лишь для одной сети специального вида, построенной в [41]. Основное утверждеггие работы [41] заключается в том, что для этой сети утверждение Теоремы 17 не выполняется при высоких значениях нагрузки р, так что здесь мы действительно наблюдаем эффект фазового перехода. Как это обычно бывает в задачах статистической механики, все системы при высокой температуре (при малых р ) ведут себя схожим образом, и все могут изучаться одним и тем же способом. Для сетей ситуация та же самая, и ггаши результаты легко могут быть 33

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

Основные результаты.

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

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

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

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

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

Список литературы.

1. Рыбко А.Н., Пропускная способность сетей связи и эргодичность марковских процессов со счетным числом состояний// Proceedings of the Third Czechoslovak - Soviet -Hungarian Seminar of Information Theory, Liblicc. 1980. C. 71-80.

2. Рыбко A.H.. Стационарные распределения марковских процессов, описывающих работу коммуникационных сетей// Пробл. передачи информации. 1981. Т. 17, № 1. С. 7189.

3. Mikhaylov V.A., Rybko A.N., The sufficient conditions for existence of stationary mode in channel switching networks with queues// Abs. of Intern. Coll. On Information Theory, Budapest. 1981. P. 58.

4. Рыбко A.H.. Условия существования стационарного режима для двух классов коммуникационных сетей// Пробл. передачи информации. 1982. Т. 18, № 1. С. 94-103. +

5. Dobrushin R.L., Rybko A.N., Capacity region of communication networks// Fundamentals of teletraffic theory. Proc. of 3-Int. Sem. On Teletrafic Theory, Moscow. June 1984. P. 94-100.

6. Рыбко A.H., Михайлов B.A.. Область пропускной способности сетей с г коммутацией каналов и очередями// Пробл. передачи информации. 1986. Т. 22, № 1. С. 6584.

7. Kel'bert M.Y., Kontsevich M.L., Rybko A.N., Ergodicity of infinite Jackson networks// Proc. of the 1-st Bcrnoully Congress, Tashkent. 1986. V. 2. P. 548.

8. Добрушип Р.Л., Кельберт М.Я., Рыбко A.H.,Сухов Ю.М. Качественные методы теории сетей с очередями//Преприпт ИП11И АН СССР. М.: ВИНИТИ, 1986. С. 1-54.

9. Кельберт М.Я., Концевич М.Л., Рыбко А.II. Бесконечные сети Джексона// Теория Лр вероятностей и ее применения. 1988. Т. 33. С. 379-382.

10. Karpelevich F.I., Rybko A.N., On one new class of Markov processes with interaction modeling adsorbtion// Proc. of the Fifth International Vilnius Conference on Probability Theory and Mathematical Statistics. June 1989. V. 3. P. 277.

11. Dobrushin R.L., Kel'bert M.Y., Rybko A.N., Suhov Y.M. Qualitative methods in the theory of queuing networks// Stochastic Cellular Systems, Ergodicity, Memory and Morphogenesis, Ed. Dobrushin R.L., Kryukov V.I., Toom A.L.,Manchester: Manchester Univ. Press, 1990. P. 183-224.

12. Bacclli F., Karpelcvich F.I., Kel'bert M.Y., Puhalskii А.Л., Rybko A.N., Suhov Y.M. A mean field limit for a class of queuing networks// Journal of statistical Physics. 1992. V 6, N. 3/4. P.803-825.

13.Рыбко A.H., Столяр A.JI. Эргодичность случайных процессов, описывающая работу открытых сетей массового обслуживания// Пробл. передачи информации. 1992. Т. 28, № 3. С. 3-26.

14. Рыбко Л.Н., Третьяков Л.Н. Гидродинамический предел и существование стационарной меры для открытых сетей массового обслуживания с несколькими типами требований// Современные методы исследования телекоммуникационных систем. РАН, ИППИ, М: 1992. С. 90-120.

15. Rybko A.N., Stolyar A.L., On the Ergodicity of Markov processes corresponding to the open message switching networks// Proc. of Int. Conf. on Applied Probability in Engineering Computer and Communication Sciences, Paris. 1993. P. 142-143.

16. Karpelevich F.I., Malyshev V.A., Rybko A.N. Stochastic evolution of neural networks// Markov processes and related fields. 1995, V. 1, N. 1, P. 141-161.

17. Foss S.G., Rybko A.N. Stability of multiclass Jackson-type networks// Markov processes and related fields. 1996. V. 2,N. 3, P. 461-486.

18. Rybko A.N., The unstable behavior of fluidc models and transicntncss of corresponding stochastic processes modeling open queuing networks// Abs. of 16th European Conference on Operational Research, Brussels. July 1998. P. 87.

19. Пухальский A.A., Рыбко A.H. Неэргодичность сетей массового обслуживания при нестабильности их жидкостных моделей// Пробл. передачи информации. 2000. Т. 36, № 1. С. 26-46.

20. Karpclevich F.I., Rybko A.N. Thcrmodynamical limit for symmetrical closed qucueing networks// On Dobrushin's way. From probability to statistical mechanics, Ed R.Munlos, S.Shlosman, Yu.Suhov. Providence: AMS. 2000. P. 133-155.

21. Карпелевич Ф.И., Рыбко A.H. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе// Пробл. передачи информации. 2000. Т. 36, № 2. С. 69-95.

22. Karpelevich F.I., Rybko A.N. Thermodynamical limit for the mean field model of simple symmetrical closed queucing network// Markov processes and related fields. 2000. V. 6, N. 1,P. 89-105.

23. Khanin K., Khmelcv D., Rybko A., Vladimirov A. Steady solutions of fluid dynamics for FIFO networks//Moscow mathematical journal. 2001. V. 1, N. 3, P. 407-419.

24. Rybko A.N., Stolyar A.L., Suhov Yu.M. Stability of global LIFO networks// Memory book of F.l.Karpclevich, Providencc: AMS. 2002. Ser. 2, V. 207. P. 177-184.

25. Karpclevich F.I., Malyshev V.A., Petrov A.A., Pirogov S.A., Rybko A.N. Context free evolution of words// Memory book of F.I.Karpelcvich, Providencc: AMS. 2002. Ser.2, V. 207. P. 91-114.

26. Rybko A., Shlosman S. Poisson hypothesis for large information networks: the study of non-linear Markov processcs//Abs. of Intern. Conf. "Kolmogorov and Contemprorary Mathematics", Moscow. June 2003. M:, Изд. ЦП И, Part 2. P. 956-957.

27. Malyshev V.A., Pirogov S.A., Rybko A.N. Random walks and chemical networks// Moscow mathematical journal. 2004. V. 4, N. 2, P. 441 -453.

28. Dinaburg E., Maes C., Pirogov S., Redig F., Rybko A. The Potts model built on sand// Journal of statistical physics. 2004. V. 117, N. 1/2, P. 179-198.

29. Rybko Л., Shlosman S. Poisson hypothesis for information networks (A study in nonlinear Markov processes) I Domain of Validity// lntn://arxiv.oru/l'S cachc/math/arxiv /pdf/0406 /04066.110vl.pdf. 2004. P. 1-77.

30. Rybko Д., Shlosman S. Poisson hypothesis for information networks H.Cases of violation and phase transitions// http://arxiv.org/PS_cache/arxiv/math-ph/pdf/0410/0410.053v. 1 pdf. 2004. P.l-27.

31. Rybko Л., Shlosman S. Poisson hypothesis for information networks (a study in nonlinear Markov processes). Parti// Moscow mathematical journal. 2005. V. 5, N. 3, P. 679-704.

32. Rybko Л., Shlosman S. Poisson hypothesis for information networks (a study in nonlinear Markov processes). Partll// Moscow mathematical journal. 2005. V. 5, N. 4, P. 927-959.

33. Рыбко Л.Н., Шлосмап С.Б. Пуассоповская гипотеза: комбинаторный аспект// Пробл. передачи информации. 2005. Т. 41, № 3. С. 51-57.

34. Rybko Л., Shlosman S., Vladimirov Л. Self-averaging property of queuing systems// http://arxiv.org/PS_cache/arxiv/math/pdr/0510/0510.046v.2pdf. 2005. P. 1-18.

35. Владимиров А.Л., Рыбко A.H., Шлосмап С.Б. Свойства самоусредпения систем массового обслуживания// Пробл. передачи информации. 2006. Т. 42, № 4, С. 91-103.

36. Rybko A.N. Poisson hypothesis for information networks (a study in non-linear Markov processes// Abs. of IV Intern. Conf. "Limit Theorems in Probability and their Applications", Novosibirsk. August, 2006. P. 28.

37. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks// http://arxiv.org/PS_cache/arxiv/math/pdf/0708/0708.3073v2.pdf2007. P. 1-53.

38. Rybko A., Shlosman S. Poisson hypothesis for information networks. 2. Cases of violations and phase transitions//Moscow mathematical journal. 2008. V.8, N.l, P.159-180.

39. Rybko A., Shlosman S., Vladimirov A. Absence of breakdown of the Poisson hypothesis. I Closed networks at low load // htlp://arxiv.ora/PS cache/arxiv/math/pdf/0811/0811.3577 v.lpdf. 2008. P. 1-18.

40. Rybko A.,Shlosman S.,Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks//Abs. of Symphosium on Perspectives in Modeling and Performance of Computer Systems "Model35", INRIA, Paris-Rocqucncourt. April 2008. P. 13.

41. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the qucueing networks// Journal of statistical physics. 2009. V. 134, N. 1, P. 67-104.

42. Рыбко Л.Н. Пуассоповская гипотеза для больших симметричных коммуникационных сетей// Глобус, общематематичсский семинар. Вып.4. Под ред. М.Л.Цфасмана и В.В.Прасолова. М,: МЦ НМО. 2009. С. 105-126.

43. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks// Proc. of Dobrushin International Conference, Moscow. July 2009. ИППИРАН, C. 149-156.

Подписано и печать 26.10.2009 г. Печать лазерная цифровая Тираж 100 экз.

Типография Лец1к-1)пп1 115230, Москва, Варшавское шоссе, д. 42 Тел.: 543-50-32 www.autoref.ac-print.ru

Введение б

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

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

1.1.1 Введение.

1.1.2 Формальное описание модели.

1.1.3 Сеть с дисциплиной обслуживания ЕСРЭ.

1.1.4 Предельный детерминированный процесс и его свойства

1.1.5 Доказательство теоремы 1.4.

1.1.6 Сеть со специальной приоритетной дисциплиной обслуживания. Контрпример к гипотезе 1.1.

1.2.2 Некоторые факты и обозначения.56

1.2.3 Жидкостная модель. Основной результат.61

1.2.4 Доказательство теоремы 1.9.66

1.2.5 Обсуждение. Примеры.76

2 Термодинамический предел для телекоммуникационных сетей 85

2.1 Сети Джексона на счетных графах.85

2.1.1 Введение.85

2.1.2 Условие единственности мультипликативной фазы . . 87

2.1.3 Условия единственности инвариантной меры.88

2.2 Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе . 92

2.2.1 Введение.92

2.2.2 Пространство и.96

2.2.3 Компактификация и пространства II.104

2.2.4 Свойства некоторой системы уравнений в пространстве 1Т.114

2.2.5 Дифференциальные свойства динамической системы у —х(£, у) .121

2.2.6 Полугруппы и их генераторы.126

2.2.7 Сходимость полугрупп.131

2.3 Пуассоновская гипотеза в информационных сетях.134

2.3.1 Введение.134

2.3.2 Обозначения .145

2.3.3 Некоторые результаты работы [21].151

2.3.4 Основной результат .153

2.3.5 Соотношение самоусреднения .156

2.3.6 Комбинаторика размещения стержней .164

2.3.7 10 (десять) технических результатов .172

2.3.8 Свойства регулярности нелинейного марковского процесса .173

2.3.9 Оценки на ядра усреднения.184

2.3.10 Соотношение самоусреднения: общий случай.189

2.3.11 Самоусреднение =Ф- релаксация: предварительные соображения .195

2.3.12 Самоусреднение ==Ф- релаксация: вероятностное доказательство? .196

2.3.13 Самоусреднение релаксация: случай конечного носителя .200

2.3.14 Самоусреднение ==Ф- релаксация: случай бесконечного носителя .204

2.3.15 Приближение к стационарной точке.205

2.3.16 Притяжение к стационарной точке .208

2.3.17 Самоусреднение релаксация: зашумленный случай .211

2.3.18 Склейка.212

2.3.19 Сходимость средних.214

2.3.20 Окончание доказательства релаксации в зашумленном случае.217

2.3.21 Заключение .220

2.4 Свойство самоусреднения систем массового обслуживания . 221

2.4.1 Введение.221

2.4.2 Основной результат .223

2.4.3 Теорема об усреднении.227

2.4.4 Доказательство теоремы.228

2.4.5 Самоусреднение может не иметь места.237

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

3.1 Спонтанные резонансы и когерентные состояния в сетях с очередями.239

3.1.1 Введение.239

3.1.2 Модель среднего поля и ее предел.245

3.1.3 Сходимость У;^ —> : применение теоремы Троттера-Курца.250

3.1.4 Жидкостные сети .260

3.1.5 Эйлеровский предел нелинейного марковского процесса282

3.1.6 Основной результат.289

3.1.7 Заключение.296

3.2 Справедливость пуассоновской гипотезы. Замкнутые сети при малой нагрузке.297

3.2.1 Введение.297

3.2.2 Основной результат.306

3.2.3 Доказательство.307

Литература 321

Введение

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

Математическая теория, описывающая функционирование телекоммуникационных сетей, является динамично развивающейся областью теории случайных процессов. Она стала развиваться лишь во второй половине 20-го века. Первоначально, развитие теории осуществлялось (когда это было возможно) методами, имеющимися в более старой и развитой области -классической теории массового обслуживания. Так, Р.М.Лойнес, доказав фундаментальную теорему об эргодичности случайного процесса, описывающую поведение общей модели очереди (7|6?|1|оо при нагрузке меньшей единицы [164], немедленно обобщил этот результат на случай простейшей коммуникационной сети - линейной последовательности серверов [165].

Другим направлением исследований первоначально было нахождение и изучение точно решаемых моделей - таких сетей, для которых их инвариантные меры явно выражаются через инвариантные меры отдельных изолированных серверов - узлов, составляющих сеть. Это направление началось с обнаружения сетей Джексона. Инвариантная мера состояния для сетей Джексона является произведением инвариантных мер отдельных изолированных узлов сети. В дальнейшем были найдены различные примеры сетей, для которых инвариантная мера находилась явно и, как правило, строилась в виде меры - произведения инвариантных мер отдельных изолированных узлов сети (product form networks).

Объяснение появления таких примеров сделал Ф.Келли. Он создал теорию квазиобратимых марковских процессов и предъявил достаточные условия, которым должны удовлетворять переходные вероятности марковских процессов, задающих работу сети, для того, чтобы инвариантные меры являлись мерой - произведением инвариантных мер изолированных узлов сети [147-149]. Оказалось, что условия квазиобратимости чрезвычайно жесткие, - при малом изменении параметров (малом изменении распределений интервалов между поступлениями требований, малом изменении распределений времен обслуживания и малом изменении дисциплин обслуживания в узлах сети), свойства квазиобратимости исчезают. Исчезает и надежда на получение явных аналитических выражений для инвариантных мер для сетей общего положения. Тем не менее, и до настоящего времени иногда обнаруживаются новые нетривиальные точно решаемые модели, - примеры таких сетей.

В связи с невозможностью использования явных аналитических методов стали развиваться качественные математические методы анализа случайных процессов, описывающих поведение сложных коммуникационных сетей. Это направление было основано в работах Р.Лойнеса, В.А.Малышева, Р.Л.Добрушина, А.А.Боровкова, П.Р.Кумара, В.Анатхарама, А.Столяра, Ф.Келли, Р.Ш.Липцера, Д.Харрисона, Д.Штояна, Р.Ясногородского, Р.Шассбергера, В.Калашникова, А.Мандельбаума, Ф.И.Карпелевича, и в настоящее время продолжает свое развитие в работах М.Брэмсона, Д.Дая, М.В.Меньшикова, С.Г.Фосса, Д.А.Коршунова, Ю.Барышникова, С.Б.Шлос-мана, А.Ю.Веретенникова, А.А.Владимирова, Ш.Мейна, А.А.Пухальского, А.Д.Маниты, Р.Уильямс, Н.О'Конелла, Н.Д.Введенской, Л.Г.Афанасьевой, Е.А.Печерского, А.А.Замятина, Г.Файоля, Ф.Бачелли, Ж.Маресса,

Т.Константопулоса, Ю.М.Сухова и в работах многих других специалистов.

Следует отметить особый инженерный подход и вклад в создание коммуникационных сетей, осуществленный Л.Клейнроком в его книгах [151-153].

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

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

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

Чтобы исследовать поведение соответствующего однородного марковского процесса со счетным числом состояний в [13] был построен жидкостный предел, возникающий в Эйлеровском скейлинге. Похожая идея для изучения эргодичности случайных блужданий в положительных октантах ранее использовалась В.А.Малышевым и его учениками [66,122,140,167]. Исследование эргодических свойств случайных блужданий в этих работах основывается на концепции индуцированных эргодических марковских цепей на соответствующих эргодических гранях октанта. Для построения векторного поля дететерминированной динамической системы, возникающей в эйлеровском пределе в этой ситуации, необходимо явно найти стационарные вероятности указанных индуцированных цепей, что не поддается существующим аналитическим методам для размерностей больше, чем два. Удивительным результатом, полученным в [140], является тот факт, что для случайных блужданий в положительных октантах размерности больше трех, область значений параметров, задающих случайные блуждания, для которых соответствующие блуждания являются нулевыми возвратными, является областью полной размерности в пространстве параметров. Это обстоятельство также затрудняет построение и изучение предельной динамической системы для блужданий в октантах больших размерностей.

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

Метод жидкостного предела, разработанный в [13], стал важным инструментом исследования условий стабильности различных сетей массового обслуживания. Так, следует отметить замечательные работы Брэмсо-на, [94,95], в которых при помощи анализа поведения жидкостного предела, обнаружены примеры невозвратных сетей с дисциплиной FIFO и номинальной нагрузкой меньшей единицы во всех узлах. Естественно возникают следующие проблемы: 1) доказательство сходимости к жидкостному пределу в Эйлеровском скейлинге для достаточно широкого и общего класса сетей массового обслуживания; 2) доказательство того факта, что если все траектории жидкостного предела, начинающиеся из непустых жидкостных состояний, попадают за конечное время (зависящее от начального состояния) в пустое состояние, то первоначальный случайный процесс, описывающий поведение сети, эргодичен; 3) доказательство свойств отсутствия эргодичности или невозвратности случайного процесса при условии, что все жидкостные траектории, стартующие из малой окрестности некоторого непустого начального состояния, ведут себя достаточно регулярно и при этом растут к бесконечности. Первые два утверждения были доказаны независимо в работах А.Столяра [192] и Д.Дая [104]. Третье утверждение было доказано в [19].

В этой работе мы рассматриваем общую открытую конечную сеть массового обслуживания, состоящую из М узлов, в которой циркулируют требования L классов. Имеется U < L внешних потоков требований, при этом каждый внешний поток содержит требования лишь одного класса. Класс требований однозначно определяет номер узла, в котором оно обслуживается, так что L > М. Требования, поступившие в данный узел, образуют единую очередь в порядке моментов их поступления, а обслуживание происходит в соответствии с дисциплиной обслуживания, принятой в этом узле. Относительно последней предполагается, что она определяется только классами требований и местами, которые они занимают в очереди; внутри классов требования обслуживаются в порядке поступления. После окончания обслуживания в узле требование либо меняет класс и поступает на обслуживание в соответствующий узел, либо покидает сеть обслуживания.

Сопоставив сети ее жидкостную модель, мы покажем, что при выполнении некоторых технических условий верно следующее: если существует такое начальное состояние жидкостной модели, для которого равномерно по всем «жидкостным траекториям» с «близкими» начальными состояниями (заметим, что в общей ситуации траектории жидкостной модели не единственны) «общее количество жидкости» стремится к бесконечности не медленнее, чем линейно, то случайный процесс, описывающий поведение сети обслуживания, иеэргодичен. Этот результат дополняет результаты [104,192] и, по-видимому, охватывает все основные имеющиеся в настоящее время нетривиальные примеры неэргодических сетей обслуживания. Он также представляется существенно более полным, чем результат Мей-на [182], который, рассматривая марковский случай, доказал, что если все «жидкостные траектории», принадлежащие «жидкостному пределу», стремятся к бесконечности, то исходный случайный процесс невозвратен.

Доказательство основной теоремы в [19] основано на использовании аппарата теории больших уклонений [52,197,187], что дает возможность получать оценки скорости сходимости в законах больших чисел, использующихся в конструкции жидкостного предела. Этот подход позволяет провести доказательство при довольно общих предположениях относительно процессов поступления, обслуживания и маршрутизации требований; в частности, мы не требуем, чтобы соответствующие случайные величины являлись н. о. р.

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

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

Еще в 70-х годах Л.Клейнрок предложил следующую инженерную концепцию - гипотезу для приближенного вычисления стационарных вычислений больших сложных сетей массового обслуживание, названную пуас-соновской гипотезой. Пусть имеется огромная сеть, состоящая из очень большого числа узлов, причем маршруты требований таковы, что на каждый узел поступает большое число малых потоков требований, идущих из различных узлов сети. Пусть также известно, что случайный процесс, моделирующий работу такой сети, стационарен и эргодичен. Для приближенного вычисления инвариантной меры этого процесса предлагается следующий простой метод. Потоки требований, поступающих на каждый фиксированный узел, заменяются на пуассоновские потоки постоянной интенсивности. При этом предполагается, что потоки, поступающие на различные узлы сети, независимы. В этих предположениях возможно явное нахождение инвариантной меры, поскольку функционирование сети распадается на работу независимых систем массового обслуживания, для нахождения стационарных характеристик которых обычно имеются явные аналитические формулы. Ясно, что строгий смысл этой гипотезе можно придать лишь в термодинамическом пределе для последовательностей таких сетей с растущим числом узлов, для которых интенсивности потоков, поступающих из узла А узел В, стремятся к нулю для произвольных пар А и В. А. А.Боровков уточнил и упростил задачу, предложив для начала доказать пуассоновскую гипотезу в простейшем нетривиальном случае: для термодинамического предела замкнутых симметричных сетей на полном графе с фиксированным отношением числа требований к числу узлов и с произвольно одинаково распределенными независимыми в совокупности последовательностями времен обслуживания требований в узлах. Р.Л.Добрушин подчеркивал связь этой проблематики с исследованием свойств термодинамического предела для моделей среднего поля в статистической физике, что оказалось очень важно для доказательства пуассоновской гипотезы. А.Столяр в [72], еще до того как A.A.Боровков сформулировал задачу для симметричной замкнутой сети, сумел ее решить в простейшем нетривиальном случае, - когда времена обслуживания всех требований во всех узлах равны фиксированной константе. Другой простой случай гипотезы Боровкова-Клейнрока, а именно случай одинаково экспоненциально распределенных времен обслуживания всех требований, был решен независимо в [22] и в работе Д.Хмелева и В.И.Оселедца [69].

Общий случай гипотезы Боровкова-Клейнрока был доказан в [31,32]. Он потребовал исследования предельного нелинейного марковского процесса -нелинейной динамической системы в пространстве вероятностных мер на специальном многообразии, и доказательства того факта, что указанная динамическая система имеет глобальный аттрактор - точку в пространстве вероятностных мер, являющуюся произведением стационарных мер систем M\GI\l\oo для отдельных узлов сети. Важным элементом доказательства является специальное свойство самоусреднения [33,35] для систем М(t)\GI\l\oo и M(i)|G|l|oo, доказанное в [33,35] соответственно.

Техника, развитая в [21,31,32,35], позволила изучать термодинамический предел инвариантных мер марковских процессов, описывающих симметричные сети более сложной природы, чем замкнутые сети на полном графе с одним типом требований. Неожиданно оказалось, что пуассонов-ская гипотеза для симметричных замкнутых сетей с несколькими типами узлов и несколькими типами требований, вообще говоря, неверна при достаточно большой нагрузке (отношению числа требований к числу узлов). Доказательство этого факта в [41] основано как на новой конструкции и изучении свойств жидкостного предела для нелинейных марковских процессов, описывающих поведение больших симметричных сетей, так и на изучении термодинамического предельного перехода для симметричных замкнутых сетей общего вида. Оказалось также, что пуассоновская гипотеза для таких сетей справедлива при малой нагрузке [39].

Первая глава диссертации основана на работах [13,19] и посвящена конструкции и исследованию жидкостного предела для открытых сетей с многими классами требований.

Вторая глава основана на работах [9,20-22,31-33,35,38,42] и в основном посвящена доказательству пуассоновской гипотезы для замкнутой симметричной сети на полносвязном графе.

Третья глава основана на работах [39,41] и посвящена анализу ассимп-тотических свойств больших симметричных сетей более общей природы.

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

Заключение

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

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

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

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

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

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

1. Рыбко А.Н., Пропускная способность сетей связи и эргодичность марковских процессов со счетным числом состояний// Proceedings of the Third Czechoslovak - Soviet - Hungarian Seminar of 1.formation Theory, Liblice. 1980. C. 71-80.

2. Рыбко A.H. Стационарные распределения марковских процессов, описывающих работу коммуникационных сетей// Пробл. передачи информации. 1981. Т. 17, № 1. С. 71-89.

3. Mikhaylov V.A., Rybko A.N., The sufficient conditions for existence of stationary mode in channel switching networks with queues// Abs. of Intern. Coll. On Information Theory, Budapest. 1981. P. 58.

4. Рыбко A.H. Условия существования стационарного режима для двух классов коммуникационных сетей// Пробл. передачи информации. 1982. Т. 18, № 1. С. 94-103.

5. Dobrushin R.L., Rybko A.N., Capacity region of communication networks// Fundamentals of teletraffie theory. Proc. of 3-Int. Sem. On Tele-trafic Theory, Moscow. June 1984. P. 94-100.

6. Рыбко A.H., Михайлов В.А. Область пропускной способности сетей с коммутацией каналов и очередями// Пробл. передачи информации. 1986. Т. 22, № 1. С. 65-84.

7. Kel'bert M.Y., Kontsevich M.L., Rybko A.N., Ergodicity of infinite Jackson networks// Proc. of the 1-st Bernoully Congress, Tashkent. 1986. V. 2. P. 548.

8. Добрушин Р.Л., Кельберт М.Я., Рыбко А.Н.,Сухов Ю.М. Качественные методы теории сетей с очередями//Препринт ИППИ АН СССР. М.: ВИНИТИ, 1986. С. 1-54.

9. Кельберт М.Я., Концевич М.Л., Рыбко А.Н. Бесконечные сети Джексона/ / Теория вероятностей и ее применения. 1988. Т. 33. С. 379-382.

10. Karpelevich F.I., Rybko A.N., On one new class of Markov processes with interaction modeling adsorbtion// Proc. of the Fifth International Vilnius Conference on Probability Theory and Mathematical Statistics. June 1989. V. 3. P. 277.

11. Bacelli F., Karpelevich F.I., Kel'bert M.Y., Puhalskii A.A., Rybko A.N., Suhov Y.M. A mean field limit for a class of queuing networks// Journal of statistical Physics. 1992. V 6, N. 3/4. P.803-825.

12. Рыбко A.H., Столяр А.Л. Эргодичность случайных процессов, описывающая работу открытых сетей массового обслуживания// Пробл. передачи информации. 1992. Т. 28, № 3. С. 3-26.

13. Rybko A.N., Stolyar A.L., On the Ergodicity of Markov processes corresponding to the open message switching networks// Proc. of Int. Conf. on Applied Probability in Engineering Computer and Communication Sciences, Paris. 1993. P. 142-143.

14. Karpelevich F.I., Malyshev V.A., Rybko A.N. Stochastic evolution of neural networks// Markov processes and related fields. 1995, V. 1, N. 1, P. 141-161.

15. Foss S.G., Rybko A.N. Stability of multiclass Jackson-type networks// Markov processes and related fields. 1996. V. 2, N. 3, P. 461-486.

16. Rybko A.N., The unstable behavior of fluide models and transientness of corresponding stochastic processes modeling open queuing networks// Abs. of 16th European Conference on Operational Research, Brussels. July 1998. P. 87.

17. Пухальский А.А., Рыбко A.H. Неэргодичность сетей массового обслуживания при нестабильности их жидкостных моделей// Пробл. передачи информации. 2000. Т. 36, № 1. С. 26-46.

18. Karpelevich F.I., Rybko A.N. Thermodynamical limit for symmetrical closed queueing networks// On Dobrushin's way. From probability to statistical mechanics, Ed R.Munlos, S.Shlosman, Yu.Suhov. Providence: AMS. 2000. P. 133-155.

19. Карпелевич Ф.И., Рыбко A.H. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе// Пробл. передачи информации. 2000. Т. 36, № 2. С. 69-95.

20. Karpelevich F.I., Rybko A.N. Thermodynamical limit for the mean field model of simple symmetrical closed queueing network// Markov processes and related fields. 2000. V. 6, N. 1, P. 89-105.

21. Khanin K., Khmelev D., Rybko A., Vladimirov A. Steady solutions of fluid dynamics for FIFO networks//Moscow mathematical journal. 2001. V. 1, N. 3, P. 407-419.

22. Rybko A.N., Stolyar A.L., Suhov Yu.M. Stability of global LIFO networks// Memory book of F.I.Karpelevich, Providence: AMS. 2002. Ser. 2, V. 207. P. 177-184.

23. Karpelevich F.I., Malyshev V.A., Petrov A.A., Pirogov S.A., Rybko A.N. Context free evolution of words// Memory book of F.I.Karpelevich, Providence: AMS. 2002. Ser.2, V. 207. P. 91-114.

24. Rybko A., Shlosman S. Poisson hypothesis for large information networks: the study of non-linear Markov processes//Abs. of Intern. Conf. "Kol-mogorov and Contemprorary Mathematics Moscow. June 2003. M:, Изд. ЦПИ, Part 2. P. 956-957.

25. Malyshev V.A., Pirogov S.A., Rybko A.N. Random walks and chemical networks// Moscow mathematical journal. 2004. V. 4, N. 2, P. 441-453.

26. Dinaburg E., Maes C., Pirogov S., Redig F., Rybko A. The Potts model built on sand// Journal of statistical physics. 2004. V. 117, N. 1/2, P. 179-198.

27. Rybko A., Shlosman S. Poisson hypothesis for information networks (A study in non-linear Markov processes) I Domain of Validity// http://arxiv.org/PS-cache/math/arxiv /pdf/0406 /04066.110vl.pdf. 2004. P. 1-77.

28. Rybko A., Shlosman S. Poisson hypothesis for information networks II.Cases of violation and phase transitions// http://arxiv.org/PS-cache/arxiv/math-ph/pdf/0410/0410.053v.lpdf. 2004. P.l-27.

29. Rybko A., Shlosman S. Poisson hypothesis for information networks (a study in non-linear Markov processes). Parti// Moscow mathematical journal. 2005. V. 5, N. 3, P. 679-704.

30. Rybko A., Shlosman S. Poisson hypothesis for information networks (a study in non-linear Markov processes). Partll// Moscow mathematical journal. 2005. V. 5, N. 4, P. 927-959.

31. Рыбко A.H., Шлосман С.Б. Пуассоновская гипотеза: комбинаторный аспект// Пробл. передачи информации. 2005. Т. 41, № 3. С. 51-57.

32. Rybko A., Shlosman S., Vladimirov A. Self-averaging property of queuing systems// http://arxiv.org/PS-cache/arxiv/math/pdf/0510/0510.046v.2pdf. 2005. P. 1-18.

33. Владимиров A.A., Рыбко A.H., Шлосман С.Б. Свойства самоусредне-иия систем массового обслуживания// Пробл. передачи информации. 2006. Т. 42, № 4, С. 91-103.

34. Rybko A.N. Poisson hypothesis for information networks (a study in nonlinear Markov processes// Abs. of IV Intern. Conf. "Limit Theorems in Probability and their Applications Novosibirsk. August, 2006. P. 28.

35. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks// http://arxiv.org/PS-cache/arxiv/math/pdf/0708/0708.3073v2.pdf 2007. P. 1-53.

36. Rybko A., Shlosman S. Poisson hypothesis for information networks. 2. Cases of violations and phase transitions// Moscow mathematical journal.2008. V.8, N.l, P.159-180.

37. Rybko A., Shlosman S., Vladimirov A. Absence of breakdown of the Poisson hypothesis. I Closed networks at low load // http://arxiv.org/PS-cache/arxiv/math/pdf/0811/0811.3577 v.lpdf. 2008. P. 1-18.

38. Rybko A.,Shlosman S.,Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks//Abs. of Symphosium on Perspectives in Modeling and Performance of Computer Systems "Model35IN-RIA, Paris-Rocquencourt. April 2008. P. 13.

39. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the queueing networks// Journal of statistical physics.2009. V. 134, N. 1, P. 67-104.

40. Рыбко A.H. Пуассоновская гипотеза для больших симметричных коммуникационных сетей// Глобус, общематематический семинар. Вып.4.

41. Под ред. М.А.Цфасмана и В.В.Прасолова. М,: МЦ НМО. 2009. С. 105126.

42. Rybko A., Shlosman S., Vladimirov A. Spontaneous resonances and the coherent states of the queuing networks// Proc. of Dobrushin International Conference, Moscow. July 2009. ИППИ PAH, C. 149-156.

43. Афанасьева JI.Г., Хмелев Д.В., Большие транспортные сети с конечномерным пространством состояний// Теория вероятностей и ее применения. 1999 Т. 44, № 1, С. 157-158.

44. Башарин Г.П., Толмачев A.JL Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных сетей// В сб.: Итоги науки и техники (сер. теория вероятн., матем. статист., теор. киберн.). М.: ВИНИТИ, 1983. Т. 21. С. 3-119.

45. Биллингели П. Сходимость вероятностных мер.// М.: Наука, 1979. 352 с.

46. Боровков A.A. Асимптотические методы в теории массового обслужи-вания//М.: Физматгиз, 1980, 381 С.

47. Боровков A.A., Могульский A.A., Саханенко А.И., Предельные теоремы для случайниых процессов// М.: ВИНИТИ. Итоги науки и техники. Фундаментальные проблемы математики, 1995, Т. 82, 200 С.

48. Боровков A.A., Фосс С.Г. Оценки для эксцесса случайного блуждания через произвольную границу и их применения// Теория вероятностей и ее применения, 1999, Т. 44, № 2, С. 1-24.

49. Боровков К. А. Распространение хаоса в сетях обслуживания// Теория вероятностей и ее применения. 1997. Т. 42,№ 3. С. 449-460.

50. Введенская Н. Д., Добрушин Р. Л., Карпелевич Ф. И. Система обслуживания с выбором наименьшей из двух очередей асимптотический подход// Пробл. передачи информации. 1996. Т. 32,№ 1. С. 20-34.

51. Венцель А. Д., Фрейдлин М. И. Флуктуации в динамических системах под действием малых случайных возмущений.// М.: Наука, 1979. 424с.

52. Добрушин P.JT. Центральная предельная теорема для неоднородных цепей Маркова// Теория вероятностей и ее применения, I, II. 1956, Т. 1, С. 72-89, Т. 1, С. 365-425.

53. Добрушин P.JL, Сухов Ю.М., Асимптотическое поведение звездообразной сети коммутации сообщений с большим числом радиальных лучей// Пробл. передачи информации. 1976, Т. 12, С. 49-65.

54. Добрушин Р.Л., Печерский Е.А. Большие уклонения для случайных процессов с независимыми приращениями на бесконечном интервале// Пробл. передачи информации. 1998. Т. 34, № 4, С. 76-108.

55. Замятин A.A., Малышев В.А., Манита А.Д. Явление гомеостаза в сетях химических реакций// Теория вероятностей и ее применения. 2006, Т. 51, С. 793-802.

56. Калашников В.В. Качественный анализ поведения сложных систем методом пробных функций// М.: Наука. 1978, 247 с.

57. Кемени Дж., Снелл Дж., Кнепп А. Счетные цепи Маркова.// М.: Наука, 1987. 414 с.

58. Климов Г. П., Ляху А. К., Матвеев В. Ф. Математические модели систем с разделением времени.// Кишинев: Штиинца, 1983. 109 с.

59. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа.// М.: Наука, 1968. 496 с.

60. Корнфельд И.П., Синай Я.Г., Фомин C.B., Эргодическая теория.// М.: Наука, 1980. 382 с.

61. Коршунов Д.А., Предельные теоремы для общих цепей Маркова// Сиб. матем. журнал. 2001, Т. 42, № 2, С. 354-371.

62. Лиггет Т. Марковские процессы с локальным взаимодействием.// М.: Мир, 1989. 550 с.

63. Липцер Р. Ш., Ширяев А. Н. Теория мартингалов.// М.: Наука, 1986. 512 с.

64. Малышев В.А. Случайные блуждания. Уравнения Винера-Хопфа в четверти плоскости. Автоморфизмы Галуа// М.: Изд. МГУ, 1970, 201 с.

65. Малышев В. А., Меньшиков М. В. Эргодичность, непрерывность и аналитичность счетных цепей Маркова// Тр. Московского математического общества. М.: Изд-во МГУ, 1979, Т. 39, С. 3-48.

66. Малышев В.А., Пирогов С.А. Обратимость и необратимость в стохастической химической кинетике// Успехи матем. наук. 2008, Т. 63, № 1, С. 3-36.

67. Малышев В.А., Минлос P.A. Гиббсовские случайные поля// М.: Наука. 1985, 288 с.

68. Оселедец В.И., Хмелев Д.В., Глобальная устойчивость бесконечных систем нелинейных дифференциальных уравнений и неоднородные счетные цепи Маркова// Пробл. передачи информации. 2000, Т. 36, № 1, С. 60-76

69. Петров В.В. Суммы независимых случайных величин// М.: Наука. 1972. 415 с.

70. Скороход А. В. Предельные теоремы для случайных процессов// Теория вероятностей и ее применения. 1956. Т. 1, № 2. С. 261-292.

71. Столяр А. Л. Асимптотика стационарного распределения для одной замкнутой системы обслуживания// Пробл. передачи информации. 1989. Т. 25,№ 4. С. 80-92.

72. Флеминг У., Ришар Р. Оптимальное управление детерминированными и стохастическими процессами.// М.: Мир, 1978.

73. Феллер В. Введение в теорию вероятностей и ее приложения, Т. 2// М.: Мир, 1984, 752 с.

74. Фосс С.Г., Денисов Д.Е. Об условиях невозвратности для цепей Маркова// Сиб. Матем. журнал. 2001, Т. 46, № 4, С. 640-657.

75. Фосс С.Г., Чернова Н.И., Об оптимальности дисциплины FCFS в многоканальных системах и сетях обслуживания// Сиб. матем. журнал. 2001, Т. 42, № 2, С. 434-450.

76. Afanassieva L.G., Delcoigne F., Fayolle G. On polling Systems where servers wait for customers// Markov Processes and Related Fields. 1997, V. 3, N. 4, P. 527-546.

77. Anantharam V. The stability region of the finite-user, slotted ALOHA system// IEEE Trans. Inf. Theory. 1991, V. 37, P. 535-540.

78. Anantharam V. On the rod placement theorem of Rybko and Shlosman// Queueing Systems. 2006, V. 52, N. 3, P. 185-188.

79. Andjel E. D. Invariant measures for the zero range process// Ann. Probab. 1982. V. 10, N. 3. P. 525-547.

80. Baccelli F., Foss S.G., Ergodicity of Jackson-type queueing networks I. Queueing Systems. 1994, V. 17, P. 5-72.

81. Baccelli F., Bonnard T. Window flow control in FIFO networks with cross traffic// Queueing Systems. 1999, V. 32, P. 195-231.

82. Baccelli F., Borovkov A., Mairesse J. Asymptotic results on infinite tandem queueing networks// Probability Theory and Related Fields, 2000, V. 118, N. 3, P. 406-426.

83. Baccelli F., Foss S. Moments and tails in monotone-separate stochastic networks// The Annals of Applied Probability, 2004, V. 14, P. 612-650.

84. Baryshnikov Yu.M. Supporting-point processes and some of their applications// Probab. Theory Related Fields. 2000, V. 117, N. 2, P. 163-182.

85. Baryshnikov Yu.M. GUEs and queues// Probab. Theory Related Fields. 2001, V. 119, N. 2, P. 256-274.

86. Baryshnikov Yu.M., Ghrist R. On target enumeration in sensor networks via integration with respect to Euler characteristics// SIAM J. Appl. Math. 2009, V. 70, N. 3, P. 925-844.

87. Benjamini I., Haggstrom O., Peres Yu., Steif J., Which properties of a random sequence are dynamically sensitive?// Ann. Probab. 2003, V. 31, N. 1, P. 1-34.

88. Blank M. Variational principles in the analisis of traffic flows (why it is worth to go against the flow)// Markov Processes and Related Fields. 2000, V. 6, N. 3, P. 287-304.

89. Borovkov A.A. Stochastic processes in queueing theory.// New York: Springer-Verlag, 1976, 280 p.

90. Borovkov A.A. An asymptotic exit problem for multidimensional Markov chains// Markov Processes and Related Fields. 1997, V. 3, N. 4, P. 547564.

91. Borovkov A.A., Ergodicity and stability of stochastic processes// N.Y.: Wiley and Sons, 1998, 580 P.

92. Borovkov A.A., Korshunov D.A., Schassberger R. Ergodicity of a polling network with an infinite number of stations// Queueing Systems, 1999, V. 1-3, P. 169-193.

93. Bramson M. Instability of FIFO queueing networks// Ann. Appl. Probability. 1994. V. 4. P. 414-431.

94. Bramson M. Instability of FIFO Queueing networks with quick service times// Ann. Appl. Probability. 1994. V. 4. P. 693-718.

95. Bramson M. Convergence to equilibria for fluid models of FIFO queueing netwirks// Queueing Systems. 1996, V. 22, P. 5-45.

96. Bramson M. State space collapse with application to heavy traffic limits for multiclass queueing networks// Queueing Systems. 1998, V. 30, P. 89-148.

97. Bramson M. A stable queueing network with unstable fluid model// Ann. Appl. Probability. 1999, V. 9, P. 818-849.

98. Bramson M., Dai J.G. Heavy traffic limits for some queueing networks// Ann. Appl Probability. 2001, V. 11, P. 49-90.

99. Bramson M. Stability of queueing networks// N.Y.: Springer. 2008, VIII. V. 1950, 190 p.

100. Chen H., Mandelbaum A. Discrete flow networks: bottlneck analisis and fluid approximations// Math. Oper. Res. 1991, V. 16, P. 408-446.

101. Chen H. Fluid approximations and stability of multyclass queueing networks: work-conservativing disciplines// Ann. Appl. Probability. 1995, V. 5, P. 637-655.

102. Chen H., Ye H. Existence condition for the diffusion approximations of multiclass priority queueing networks// Queueing Systems. 2001, V. 38, P. 435-470.

103. Dai J.G. On Positive Harris recurrence of multiclass queueing networks: a unified approach via fluid models// Ann. Appl. Probability. 1995. V. 5. P. 49-77.

104. Dai J.G., Meyn S.P. Stability and convergence of moments for multiclass queueing networks via fluid limit models// IEEE Trans.Automat. Control. 1995, V. 40, P. 1889-1904.

105. Dai J.G. A fluid limit model criterion for instability of multiclass queueing networks// Ann. Appl. Probability. 1996, V. 6, P. 751-757.

106. Dai J.G., Weiss G. Stability and instability of fluid models for re-entrant lines// Math. Oper. Res. 1996, V. 21, R 115-134.

107. Dai J.G., Hassenbein J.J., Vande Vate J.H. Stability of a three-station fluid network// Queueing Systems. 1999, V. 33, R 293-325.

108. Dai J.G., Vande Vate J.H. The stability of two-station multitype fluid networks// Operations Research. 2000, V. 48, P. 721-744.

109. Dai J.G., Hassenbein J.J., Vande Vate J.H. Stability and instability of a two-station queueing network// Ann. Appl. Probability. 2004, V. 14, P. 326-377.

110. Delcoigne F., Fayolle G. Thermodynamical limit and propagation of chaos in polling systems// Markov Processes and Related Fields. 1999. V. 5, N 1. P. 89-124.

111. Dembo A., Vershik A., Zeitouni O. Large deviations for integer partitions// Markov Processes and Related Fields. 2000, V. 6, N. 2, P. 147-179.

112. Deuschel J. D., Stroock D. W. Large deviations.// New York: Academic Press, 2001. 283 p.

113. Duffield N.G., O'Connell N. Large deviations and overflow probabilities for the general single-server queue, with applications// Math. Proc. Camb. Phil. Soc. 1995, V. 118, N. 2, P. 363-374.

114. Dumas V. A multiclass network with non-linear, non-convex, nonmonotonic stability conditions// Queueing Systems. 1997, V. 25, P. 1-43.

115. Dumas V. Essential fases and stability conditions of multiclass networks with priorities// Markov Processes and Related Fields, 2001, V. 7, N. 4, P. 541-559.

116. Dupius P., Ellis R. S., Weiss A. Large deviations for Markov processes with discontinuous statistics. I: general upper bounds// AT&T-BL Technical Memorandum, Work Project N. 311404-3199. File Case 20878. 1989.

117. Ether S. N., Kurtz T. G. Markov processes:characterization and convergence.// N. Y.: J. Wiley and Sons,1989. 534 p.

118. Fayolle G., Ignatyuk I.A., Malyshev V.A., Mensliikov M.V. Random walks in two dimentional complexes// Queueing Systems. 1991, V. 9, P. 269-300.

119. Fayolle G., Malyshev V.A., Mensliikov M.V. Random walks in quarter plane with zero drift. I: ergodicity and nullrecurrence// Annales d'Institut Henry Poincare, 1992, V. 28, N. 2, P. 179-194.

120. Fayolle G., Iasnogorodski R., Malyshev V.A. Random walks in quarter plane// N.Y.: Springer, 1999. 158 p.

121. Fayolle G., Malyshev V.A., Menshikov M.V. Topics in constructive theory of Markov chains. Part 1.// Cambridge: Cambridge University Press, 1995. 169 p.

122. Foss S., Tweedy R.L. Perfect simulation and backward coupling// Stochastic Models, 1998, V. 14, N. 1-2, P. 187-204.

123. Foss S., Chernova N. On stability of partially acessible multi-station queue with state-dependent routing// Queueing Systems, 1998, V. 29, N.l, P. 55-73.

124. Foss S., Last G. Stability of polling systems with general service policies and with stage depending routing// Probability in the Engineering and Inf. Sciences, 1998, V. 12, N. 1, P. 49-68

125. Foss S., Kovalevskii A., Stability criterion via fluid limits and its application to a polling model// Queueing Systems, 1999, V. 32, N. 1-3, P. 131-168

126. Foss S., Konstantopoulos T. Extended renovation theoty and limit theorems for stochastic ordered graphs// Markov Processes and Related Fields, 2003, V. 9, N. 3, P. 413-468.

127. Gajrat A.S., Iasnogorodski R., Malyshev V.A. Null recurrent string// Markov Processes and Related Fields. 1996, V. 2, N. 3, P. 427-460.

128. Gamarnik D., Hasenbein J.J. Instability in stochastic and fluid queueing networks// Ann. Appl. Probability. 2005, V. 15, P. 1652-1690.

129. Ganesh A., O'Connell N., Wishik D. Big queues// B.: Springer-Verlag. Lecture Notes in Mathematics, 2004, V. 1838. 260 p.

130. Gibbens R.G., Kelly F.P. Dynamic routing in fully connected networks// IMA J. Math. Cont. Inf. 1990, V. 7, P. 77-111.

131. Goodman J.B., Massey W.A. The non-ergodic Jackson networks// J. Appl. Probab. 1984. V. 21, N. 4. P. 860-869.

132. Graham C., Meleard S. A large deviation principle for a large star-shaped loss network with lines of capacity one// Markov Processes and Related Fields. 1997, V. 3, N. 4, P. 475-492.

133. Harrison J.M., Reiman M.I. Reflected Brownian motion on an ortant// Ann. Probability. 1981, V. 9, P. 302-308.

134. Harrison J.M. Brownian models of queueing networks with heterogeneous customer populations// N.Y.: Springer. Stochastic Differential Systems, Stochastic Control Theory and their Applications. IMA Math. Appl. 1988, V. 10, P. 147-186.

135. Harrison J.M. Balanced fluid models of multyclass queueing networks: a heavy traffic conjecture// N.Y.: Springer. Stochastic Networks. IMA Math. Appl. 1995, V. 71, P. 1-20.

136. Harrisom J.M., Williams R.J. A multiclass closed queueing network with unconventional heavy traffic behavior// Ann. Appl. Probability. 1996, V. 6, P. 1-47.

137. Hassenbein J.J. Necessary conditions for global stability of multiclass queueing networks// Oper. Res. Lett. 1997, V. 21, P. 87-94.

138. Hutson V.C.L., Pym J. S. Applications of functional analysis and Operators theory.// London: Academic Press, 1980. 426 p.

139. Ignatyuk I.A., Malyshev V.A., Classification of random walks in Z\.// Selecta Mathematica, 1993, V. 12, N. 2, P. 129-194.

140. Jackson R.R.P. Queueing systems with phase-type service// Operat. Res. Quart. 1954, V. 5, P. 109-120.

141. Jackson R.R.P. Jobshop-like queueing systems// Mgmt. Sci. 1963, V. 10, P. 131-142.

142. Jackson J.R. Networks of waiting lines// Operat. Res. 1959. V. 5, N 5. P. 518-521.

143. Kantor M. Lower bound for the probability of the overload in certain queueing networks// J. Appl. Probab. 1984. V. 22, N. 2. P. 429-436.

144. Kaspi H., Mandelbaum A. On Harris recurrence in continuous time// Math. Oper. Res. 1994, V. 19, P. 211-222.

145. Kaspi H., Mandelbaum A. Regenerative closed queueing networks// Stoch. Stoch. Rep. 1992, V. 39, N. 4, P. 239-258.

146. Kelly F.P. Networks of queues with customers of different types// J. Appl. Probability. 1975, V. 12, P. 542-554.

147. Kelly F.P. Networks of queues// Adv. Appl. Probability. 1976, V. 8, N.2, P. 416-432.

148. Kelly F. P. Reversibility and stochastic networks.// N. Y.: Wiley Sons, 1979. 222 p.

149. Khas'minskii R.Z. Stochastic stability of differential equations// Ned.: Si-jthoff Nordhoff. 1980. 344 p.

150. Kleinrock L. Communication Nets, Stochastic Message Flow and Delay// N. Y.: McGraw-Hill Book Company, 1964. 209 p.

151. Kleinrock L. Queueing Systems, V.l Theory// N. Y.: Wiley Sons, 1975, 432 p.

152. Kleinrock L. Queueing Systems, V. 2 Computer Applications// N. Y.: Wiley Sons, 1975, 549 p.

153. Kolokoltsov V.N. Kinetic equations for the pure jump models of k-nary interacting particle systems// Markov Processes and Related Fields. 2006, N. 1, P. 95-138.

154. Kumar P.R., Seidman T. Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems// IEEE Trans. Automat. Control. 1990. V. 35, N 3. P. 289-290.

155. Kumar P.R. Re-entrant lines// Queueing Systems. 1993, V. 13, P. 87-110.

156. Kumar S., Kumar P.R. Performance bounds for queueing networks and scheduling policies// IEEE Trans. Autom. Control. August 1994, V. AC-39, P. 1600-1611.

157. Kumar S., Kumar P.R. Closed queueing networks in heavy traffic: fluid limits and efficiency// N.Y.: Springer-Verlag. Lecture Notes in Statistics. Stochasic networks: stability and rare events. Ed. P.Glasserman, K.Sigman, D.Yao. 1996, V. 117, P. 41-64.

158. Kumar S., Kumar P.R. Fluctuation smoothing policies are stable for stochastic reentrant lines// Discrete Event Din. Syst. Theory Appl. 1996, V. 6, N. 4, P. 361-370.

159. Kurkova I., Malyshev V.A. Martin boundary and elliptic curves// Markov Processes and Related Fields, 1998, V. 4, N. 2, P. 203-272.

160. LeBoudec J.Y., Thiran P. Network calculus a theory of deterministic queuing systems.// Lecture Notes in Computer Science, N. 2050, Springer, 2001. 300 p.

161. Lindvall T. Weak convergence of probability measures and random functions in the function space D0, oo) // J. of Appl. Probability. 1973. V. 10. P. 109-121.

162. Liptser R., Spokoiny V., Veretennikov A.Yu. Freidlin-Wentzell type large deviations for smooth processes// Markov Processes and Related Fields. 2002, V. 8, N. 4, P. 611-636.

163. Loynes R.M. The stability of a queue with nonindependent interarrival and service times// Proc. Camb. Phil. Soc. 1962, V. 58, P. 497-520.

164. Loynes R.M., On the waiting time distribution for queues in series// J. Roy. Stat. Soe., 1965, V. 27, P. 491-496.

165. Lu S.H., Kumar P.R. Distributed scheduling based on due dates and buffer priorities// IEEE Trans. Automat. Control. 1991, V. 36, P. 1406-1416.

166. Malyshev V.A. Networks and Dynamical Systems// Adv. Appl. Probability. 1993. V. 25. P. 140-175.

167. Malyshev V.A., Spieksma F. Intrinsic convergence rates of countable Markov chains// Markov Processes and Related Fields. 1995, V. 1, N. 2, P. 203-266.

168. Malyshev V., Turova T. Gibbs measures on attractors in biological neural networks// Markov Processes and Related Fields. 1997, V. 3, N. 4, P. 443464.

169. Malyshev V.A. Fixed points for stochastic open" chemical systems// Markov Processes and Related Fields. 2005, V. 11, N. 2, P. 337-354.

170. Mandelbaum A, Stolyar A.L. Scheduling flexible servers with convex delay costs: heavy traffic optimality// Oper. Res. 2004, V. 52, N. 6, P. 836-855.

171. Manita A., Shcherbakov V. Asymptotic analisis of a particle system with mean-fiels interaction// Markov Processes and Related Fields. 2005, V. 11, N. 3, P. 489-518.

172. Massey B. Open Networks of Queues// Adv. Appl. Probability. 1984. V. 16, N.l. P. 176-201.

173. McKean H.P., Jr. A class of Markov processes associated with nonlinear parabolic equations.// Proc. Nat. Acad. Sci. U.S.A., 56, 1966, 1907-1911.

174. McKean H.P., Jr. An exponential formula for solving Boltzmann's equation for a Maxwellian gas.// J. Combinatorial Theory, 2, 1967, 358-382.

175. Meyn S.P., Tweedie R.L. Generalized resolvents and Harris recurrence of Markov processes// Contemporary Mathematics. 1993, V. 149, P.227-250.

176. Mein S.P., Tweedie R.L. Stability of Markov processes II: continuous-time processes and sample chains// Adv. Appl. Probability. 1993, V. 25, P. 487517.

177. Meyn S.P., Tweedie R.L. Stability of Markov processes III: Foster-Lyapunov criteria for continuous-time processes// Adv. Appl. Probability. 1993, V. 25, P. 518-548.

178. Meyn S.P., Tweedie R.L. Markov chains and stochastic stability// N.Y.: Springer. 1993. 568 p.

179. Meyn S.P., Tweedie R.L. State dependent criteria for convergence of Markoc chains// Ann. Appl. Probability. 1994, V. 4, P. 149-168.

180. Meyn S.P., Down D. Stability of generalized Jackson networks// Ann. Appl. Probability. 1994, V. 4, P. 124-148.

181. Meyn S.P. Transience of multiclass queueing networks and their fluid models// Ann. Appl. Probability. 1995. V. 5. P. 946-957.

182. Milstein G.N., Veretennikov A.Yu. On deterministic and stochastic sliding modes via small diffusion approximation// Markov Processes and Related Fields. 2000, V. 6, N. 3, P. 371-396.

183. Moustafa M.D. Input-output Markov processes// Proc. Konjukijke Netherlands Aqad. Netenschappen. 1957, V. 60, P. 112-118.

184. Perkins J.R., Kumar P.R. Stable, distributed, real-time scheduling of flexible manufacturing / assembly / disassembly systems// IEEE Trans. Automatic Control. 1989, V. 34, N. 2, P. 139-147.

185. O'Connell N. Prom laws of large numbers to large deviation principles// Markov Processes and Related Fields. 1997, V. 3, N. 4, P. 589-596.

186. Puhalskii A. On functional principle of large deviations//New Trends in Probability and Statistics. Utrecht: VSPMoks'las, 1991. V. 1. P. 198-218.

187. Puhalskii A. Large deviation analysis of the single server queue// Queue-ing Systems. 1995. V. 21. P. 5-66; erratum: 1996. V. 23. P. 33

188. Puhalskii A., Whitt W. Functional large deviation principles for firstpassage-time processes// Ann. Appl. Probability. 1997. V. 7, N 2. P. 362381.

189. Reiman M.I., Williams R.J. A boundary property of semimartingale reflecting Brownian motions// Probab. Theory Related Fields. 1988, V. 77, P. 87-97.

190. Seidman T.I. "First come, first served"can be unstable// IEEE Trans. Automat. Control. 1994, V. 39, P. 2166-2170.

191. Stolyar A. On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes// Markov Proc. Rel. Fields. 1995. V. 1, N. 4. P. 491-512.

192. Stolyar A.L., Ramakrishnan K.K. The stability of a flow merge point with non-interleaving cut-through scheduling disciplines// Proceedings of IFO-COM 1999.

193. Stolyar A.L. Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic// Adv. Appl. Probability. 2004, V. 14, N. 2, P. 1-53.

194. Stoyan D., Daley D. Comparison methods for queues and other stochastic models.// Chichester New York: Wiley, 1983. 217 p.

195. Taylor L.M., Williams R.J. Existence and uniqueness of semimartingale reflecting Brownian motions in an ortant// Probab. Theory Related Fields. 1993, V. 96, P. 283-317.

196. Varadhan S. H. S. Large deviations and applications.// Philadelphia: SIAM, 1984. 75 p.

197. Varakin A.B., Veretennikov A.Yu. On parameter estimation for "poli-nomial ergodic"Markov chains with polinomial growth loss functions// Markov Processes and Related Fields. 2002, V. 8, N. 1, P. 127-144.

198. Whitt W. Large fluctuations in a deterministic multiclass network of queues// Managm. Sci. 1993, V. 39, P. 1020-1028.

199. Whitt W. Stochastic-process limits: an introduction to stochastic process limits and their application to queues// N.Y.: Springer. 2002. 529 p.

200. Williams R.J. An invariant principle for semimartingale reflecting Brownian motion in ortant// Queueing Systems. 1998, V. 30, P. 5-25

201. Williams R.J. Diffusion approximation for open multiclass queueing networks: sufficient conditions involving state space collapse// Queueing Systems. 1998, V. 30, P. 27-88.

202. Yambartsev A.A., Zamyatin A.A. Dynamics of two interacting queues// Markov Processes and Related Fields. 2001, V. 7, N. 2, P. 301-324.