Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Рыбко Александр Николаевич
Асимптотические свойства стационарных распределений телекоммуникационных сетей
05.13.17 - Теоретические основы информатики
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
Москва 2009
Работа выполнена в Институте проблем передачи информации им.А.А.Харкевича Российской академии наук
Официальные оппоненты: академик РАН, доктор физико-математических наук, профессор А.А.Боровков доктор физико-математических наук, профессор M.И.Вишик доктор физико-математических наук, профессор В.И.Оселедец
Ведущая организация: Механико-математический факультет МГУ им.М.В.Ломоносова
Защита состоится л__ _________ 2009 г. в 11 часов на заседании Диссертационного совета Д.002.077.01 при Институте проблем передачи информации им.А.А.Харкевича РАН по адресу: 127994, Москва, ГСП-4, Б. Каретный пер., 19, стр1.
С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации им.А.А.Харкевича РАН Автореферат разослан л__ __________2009 г.
Ученый секретарь Диссертационного совета Д.002.077.доктор физико-математических наук И.И.Цитович а
Общая характеристика работы
Актуальность темы. Разработка математических методов, предсказывающих значения стационарных характеристик узлов сети при выбранных допустимых нагрузках, является актуальной темой в современной теории случайных процессов, описывающих поведение телекоммуникационных сетей. Одной из основных проблем является, также, и само нахождение условий существования стабильного режима работы открытых сетей, или, что то же самое, условий эргодичности марковских процессов, описывающих функционирование таких сетей, поскольку при создании и эксплуатации телекоммуникационных сетей необходимо гарантировать их стабильную работу.
Математическая теория, описывающая функционирование телекоммуникационных сетей, является динамично развивающейся областью теории случайных процессов. Она стала развиваться лишь во второй половине 20-го века. Первоначально, развитие теории осуществлялось (когда это было возможно) методами, имеющимися в более старой и развитой области - классической теории массового обслуживания. Так, Р.М.Лойнес, доказав фундаментальную теорему об эргодичности случайного процесса, описывающую поведение общей модели очереди GG 1| при нагрузке меньшей единице, немедленно обобщил этот результат на случай простейшей коммуникационной сети - линейной последовательности серверов.
Другим направлением исследований первоначально было нахождение и изучение точно решаемых моделей - таких сетей, для которых их инвариантные меры явно выражаются через инвариантные меры отдельных изолированных серверов - узлов, составляющих сеть. Это направление началось с обнаружения сетей Джексона.
Инвариантная мера состояния для сетей Джексона является произведением инвариантных мер отдельных изолированных узлов сети. В дальнейшем были найдены различные примеры сетей, для которых инвариантная мера находилась явно и, как правило, строилась в виде меры - произведения инвариантных мер отдельных изолированных узлов сети (product form networks).
Объяснение появления таких примеров сделал Ф.Келли. Он создал теорию квазиобратимых марковских процессов и предъявил достаточные условия, которым должны удовлетворять переходные вероятности марковских процессов, задающих работу сети, для того, чтобы инвариантные меры являлись мерой - произведением инвариантных мер изолированных узлов сети. Оказалось, что условия квазиобратимости чрезвычайно жесткие, - при малом изменении параметров (малом изменении распределений интервалов между поступлениями требований, малом изменении распределений времен обслуживания и малом изменении дисциплин обслуживания в узлах сети), свойства квазиобратимости исчезают. Исчезает и надежда на получение явных аналитических выражений для инвариантных мер для сетей общего положения. Тем не менее, и до настоящего времени иногда обнаруживаются новые нетривиальные точно решаемые модели - примеры таких сетей.
В связи с невозможностью использования явных аналитических методов стали развиваться качественные математические методы анализа случайных процессов, описывающих поведение сложных коммуникационных сетей. Это направление было основано в работах Р.Лойнеса, В.А.Малышева, Р.Л.Добрушина, А.А.Боровкова, П.Р.Кумара, В.Анатхарама, А.Столяра, Ф.Келли, Р.Ш.Липцера, Д.Харрисона, Д.Штояна, Р.Ясногородского, Р.Шассбергера, В.Калашинкова, А.Мандельбаума, Ф.И.Карпелевича, и в настоящее время продолжает свое развитие в работах М.Брэмсона, Д.Дая, М.В.Меньшикова, С.Г.Фосса, Д.А.Коршунова, Ю.Барышникова, С.Б.Шлосмана, А.Ю.Веретенникова, А.А.Владимирова, Ш.Мейна, А.A.Пухальского, А.Д.Маниты, Р.Уильямс, Н.ОТКонелла, Н.Д.Введенской, Л.Г.Афанасьевой, Е.А.Печерского, A.А.Замятина, Г.Файоля, Ф.Бачелли, Ж.Маресса, Т.Константопулоса, Ю.М.Сухова и в аработах многих других специалистов. Следует отметить особый инженерный подход и вклад в создание коммуникационных сетей, осуществленный Л.Клейнроком в его книгах.
Автору особенно близка идея, неоднократно высказанная Р.Л.Добрушиным, заключающаяся в том, что идеология и многие методы статистической механики, как более старой и развитой области науки, могут продуктивно использоваться при анализе свойств больших телекоммуникационных сетей.
Первым вопросом математической теории открытых сетей со многими классами требований представляется проблема нахождения условий существования и единственности стабильного режима (эргодичности) таких сетей. Долгое время считалось несомненным фактом, лишь требовавшим строгого математического доказательства следующее утверждение, сформулированное Р.Л.Добрушиным, являющееся естественным обобщением теоремы Лойнеса об эргодичности классической системы массового обслуживания, состоящей из единственной очереди к одному серверу.
Определим номинальную нагрузку m на произвольный узел m сети, как среднее значение за единицу времени суммарных длин тех требований, которым предстоит обслуживаться в узле m. Гипотеза, дающая условия эргодичности открытых сетей, заключалась в утверждении, что если для каждого узла m сети номинальная нагрузка m <1, то случайный процесс, описывающий работу сети, эргодичен и среднее число требований, циркулирующих в сети в растущие моменты времени, не стремится к бесконечности.
В 13 эта гипотеза была опровергнута, - было доказано, что уже для простой сети, [ ] состоящей из 2-х узлов, в которой циркулируют 2 класса требований, при некоторой приоритетной дисциплине даже при экспоненциально распределенных независимых временах обслуживания и при пуассоновских входных потоках требований, утверждение гипотезы не верно. Чтобы исследовать поведение соответствующего однородного марковского процесса со счетным числом состояний был построен жидкостный предел, возникающий в Эйлеровском скейлинге. Похожая идея для изучения эргодичности случайных блужданий в положительных октантах ранее использовалась В.А.Малышевым и его учениками1. Однако, в силу имеющихся дополнительных инвариантов, связанных с условием консервативности дисциплин обслуживания в узлах, анализ поведения траекторий жидкостного предела для сетей допускает лявное описание. Векторное поле детерминированной жидкостной динамики явно строится как в конечномерном случае (приоритетные дисциплины), так даже и в бесконечномерном случае (дисциплины FIFO, LIFO), и это дает возможность рассматривать произвольно распределенные (а не только экспоненциально распределенные) времена обслуживания требований и общие входные потоки.
Метод жидкостного предела, разработанный в 13, стал важным инструментом [ ] исследования условий стабильности различных сетей массового обслуживания.
Естественно возникают следующие проблемы:
1) доказательство сходимости к жидкостному пределу в Эйлеровском скейлинге для достаточно широкого и общего класса сетей массового обслуживания;
2) доказательство того факта, что если все траектории жидкостного предела, начинающиеся из непустых жидкостных состояний, попадают за конечное время (зависящее от начального состояния) в пустое состояние, то первоначальный случайный процесс, описывающий поведение сети, эргодичен;
3) доказательство свойств отсутствия эргодичности или невозвратности случайного процесса при условии, что все жидкостные траектории, стартующие из малой окрестности некоторого непустого начального состояния, ведут себя достаточно регулярно и при этом растут к бесконечности.
Malyshev A.V. Networks and dynamical systems. Adv. Appl. Prob. 1993, V. 25, P. 140-1аПервые два утверждения были доказаны независимо в работах А.Столяра и Д.Дая.
Третье утверждение было доказано в 19. Доказательство основано на использовании [ ] методов теории больших уклонений.
Другим предельным переходом, важным для анализа стохастических процессов, моделирующих большие сети массового обслуживания, является термодинамический предельный переход, при котором число узлов в сети стремится к бесконечности. По аналогии с идеями статистической механики, естественно ожидать, что многие свойства бесконечной сети, возникающей в термодинамическом пределе, окажутся доступнее для математического анализа, чем аналогичные свойства больших конечных сетей.
Еще в 70-х годах Л.Клейнрок предложил следующую инженерную концепцию, - гипотезу для приближенного вычисления стационарных распределений больших сложных сетей, названную пуассоновской гипотезой. Пусть имеется огромная сеть, состоящая из очень большого числа узлов, причем маршруты требований таковы, что на каждый узел поступает большое число малых потоков требований, идущих из различных узлов сети.
Пусть также известно, что случайный процесс, моделирующий работу такой сети, стациионарен и эргодичен. Для приближенного вычисления инвариантной меры этого процесса предлагается следующий простой метод. Потоки требований, поступающие на каждый фиксированный узел, заменяются на пуассоновские потоки постоянной интенсивности.
При этом предполагается, что потоки, поступающие на различные узлы сети, независимы.
В этих предположениях возможно явное нахождение инвариантной меры, поскольку работа сети распадается на работу независимых систем массового обслуживания, для нахождения стационарных характеристик которых обычно имеются явные аналитические формулы. Ясно, что строгий смысл этой гипотезе можно придать лишь в термодинамическом пределе для последовательностей таких сетей с растущим числом узлов, для которых интенсивности потоков, поступающих из узла A в узел B, стремятся к нулю для произвольных пар A и B. А.А.Боровков уточнил и упростил задачу, предложив для начала доказать пуассоновскую гипотезу в простейшем нетривиальном случае: для термодинамического предела замкнутых симметричных сетей на полном графе с фиксированным отношением числа требований к числу узлов и с произвольно одинаково распределенными, независимыми в совокупности последовательностями времен обслуживания требований в узлах. Р.Л.Добрушин подчеркивал связь этой проблематики с исследованием свойств термодинамического предела для моделей среднего поля в статистической физике, что оказалось очень важно для доказательства пуассоновской гипотезы.
Цель работы.
1) Нахождение условий стабильности открытых телекоммуникационных сетей.
2) Исследование свойств жидкостных траекторий, возникающих в Эйлеровском пределе для телекоммуникационных сетей.
3) Исследование условий асимптотической независимости для симметричных сетей большого объема.
4) Исследование свойств нелинейных марковских процессов, возникающих в термодинамическом предельном переходе для симметричных сетей.
Методы исследования. В наших исследованиях использованы методы теории вероятностей и теории случайных процессов, в частности теории больших уклонений, теории нелинейных марковских процессов; методы функционального анализа, в частности теории марковских полугрупп; методы теории нелинейных динамических систем.
Научная новизна. Для широкого класса марковских процессов, описывающих работу телекоммуникационных сетей, разработан новый метод исследования, - метод жидкостного предела. Построенные жидкостные пределы для открытых телекоммуникационных сетей позволили находить условия эргодичности марковских процессов, исследуя свойства их жидкостных траекторий.
аВпервые исследован предельный случайный процесс, возникающий в результате термодинамического предельного перехода, для замкнутых симметричных сетей на полном графе. Эргодические свойства указанного предельного нелинейного марковского процесса позволяют проверять справедливость пуассоновской гипотезы для симметричных замкнутых сетей массового обслуживания.
Разработан новый метод исследования нелинейных марковских процессов, возникающих в термодинамическом пределе для общих симметричных сетей. Этот метод, - метод исследования предельной нелинейной жидкостной динамической системы, возникающей в Эйлеровском пределе, позволил обнаружить новое явление спонтанной синхронизации и опровергнуть пуассоновскую гипотезу для таких сетей при больших нагрузках.
Теоретическая и практическая ценность. Работа носит теоретический характер.
В диссертации разработаны новые методы исследования, которые позволили получить новые результаты и доказать утверждения, существовавшие ранее в виде гипотез. В частности, опровергнута гипотеза об условиях эргодичности открытых коммуникационных сетей. Построенный пример, опровергающий эту гипотезу, известен теперь как пример Рыбко - Столяра. Для анализа свойств данного примера и для нахождения условий эргодичности сложных открытых сетей со многими классами требований разработан новый метод исследования, - метод жидкостного предела для таких сетей. Используя этот метод, получены новые общие критерии неэргодичности и невозвратности открытых сетей, - доказаны общие теоремы о неэргодичности и невозвратности открытых сетей при условии, что все жидкостные траектории, стартующие из малой окрестности некоторого непустого начального состояния, ведут себя достаточно регулярно и при этом растут к бесконечности.
Доказана справедливость пуассоновской гипотезы для симметричной замкнутой сети на полном графе. Доказательство основано на обнаружении специального свойства самоусреднения для неоднородных процессов M t G 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, [ ] являющейся однородным марковским процессом с непрерывным временем и счетным числом состояний. Сеть состоит из J узлов. Имеется I классов требований. Входной поток требований класса i,i 1,..., I, есть пуассоновский поток с интенсивностью i (эти { } потоки взаимно независимы для разных классов требований). Каждому классу требований соответствует свой маршрут (i,1),..., (i,k),..., (i, K()), j(i,k) J, k = 1,..., K (i), т.е. последовательность узлов сети в которых должны обслуживаться требования данного класса прежде, чем покинуть сеть. Здесь K (i) - длина маршрута для требований класса i, а (i,k) J(k =1,..., K(i)) - номер узла сети, в который попадают на обслуживание требования класса i на k -м шаге своего маршрута.
В каждом узле имеется единственный обслуживающий прибор и очередь с неограниченным числом мест для ожидания. Времена обслуживания всех требований во всех узлах предполагаются взаимно независимыми случайными величинами. Через ik, i I, k = 1,..., K(i) обозначим среднее время обслуживания требования класса i на k -м { } шаге маршрута (т.е. в узле (i,k)). Положим для простоты, что все времена обслуживания экспоненциально распределены. В каждом узле j J действует некоторая консервативная дисциплина обслуживания. Это означает, что обслуживающий прибор всегда работает с интенсивностью единица, если очередь не пуста.
Нетрудно определить однородный марковский процесс s(t) со счетным фазовым пространством, описывающий работу рассматриваемой сети.
аОбозначим через суммарную номинальную нагрузку узла j :
j = ik j i (i,k ): (i,k )= j В 1 доказана следующая простая теорема.
[ ] Предложение 1: Если s(t) - эргодический марковский процесс, то для всех j J j <1.
Добрушиным была выдвинута следующая естественная гипотеза.
Гипотеза 1: Если для всех j J j <1 (1) то s(t) есть эргодический марковский процесс.
Наш подход основан на изучении свойств некоторого предельного детерминированного жидкостного процесса. Этот детерминированный процесс может рассматриваться как предел последовательности процессов, получающихся с помощью Эйлеровского скейлинга - нормировки и одновременного изменения масштаба времени на последовательности исходных процессов с неограниченно возрастающим начальным состоянием.
Приведем наглядную интерпретацию этого предельного детерминированного жидкостного процесса. Имеется J сосудов и I сортов жидкости. В начальный момент времени суммарное количество жидкостей во всех сосудах равно единице. Жидкость сорта i I вливается в первый сосуд (i,1) своего маршрута с постоянной скоростью i, перетекает через последовательность сосудов (i,1),..., (i,k),..., (i, K(i)) и затем покидает сеть. Единица i -й жидкости в сосуде j = (i,k) имеет вязкость ik. Каждый сосуд j J имеет два отверстия - верхнее, через которое жидкости втекают в сосуд (величина этого отверстия неограниченна), и нижнее, через которое жидкости вытекают из сосуда.
Величина нижнего отверстия равна единице. Таким образом, если данный сосуд не пуст, то общая вязкость жидкости, вытекающей из данного сосуда за единицу времени равна единице. Жидкость вытекает через отверстие в данном сосуде согласно той же дисциплине, что и дисциплина обслуживания для соответствующего узла сети обслуживания. Например, для дисциплины FIFO жидкости вытекают из сосуда в том же порядке, в котором они втекают в данный сосуд. Свойство эргодичности рассматриваемого марковского процесса s(t) соответствует тому факту, что система сосудов опустошится за конечное время при любом начальном состоянии с суммарным количеством жидкостей, равным единице. Похожие детерминированные процессы дискретного типа исследовались в теории расписаний для производственных систем (см.
работы Перкинса и Кумара, Кумара и Сейдмана).
Пример нестабильного детермини- рованного жидкостного процесса в Tеореме помогает доказательству невозвратности соответствующего марковского процесса (Теорема 6).
В этом параграфе мы рассматриваем простейшую нетривиальную сеть, исследование которой не поддается методам, развитым ранее. Эта сеть состоит из двух узлов, в которых обслуживаются два класса требований. Требования движутся через сеть в противоположных направлениях, а именно: требование первого класса поступая в сеть проходит обслуживание в начале в первом узле, а затем во втором. Наоборот, требования второго класса обслуживаются сначала во втором узле, а потом в первом. При этом требования обоих классов стоят в общих очередях в каждом из узлов. Первый рассмотренный в этом параграфе случай, это сеть соответствующая дисциплине FIFO в обоих узлах. В этом случае доказана Гипотеза 1 (Теорема 1).
аВторой случай, рассматриваемый в п. 1.1.4. - это специальное приоритетное обслуживание в каждом из узлов: в первом узле требования второго класса имеют абсолютный приоритет, а во втором узле наоборот, требования первого класса имеют абсолютный приоритет. Показано (Теорема 6), что в этом случае Гипотеза 1 не верна: для некоторой области параметров, удовлетворяющих условию <1, j J j соответствующий марковский процесс невозвратен.
1.1.2. Сеть с дисциплиной обслуживания FIFO. Итак, пусть задана дисциплина FIFO в каждом узле. Состояние сети s S зададим следующим образом:
s = sjl,l = 1 Qj ), j J.Здесь Qj - общее число требований в узле j J, } { sjl Gj (i, k) : (i, k) = j - класс требования, стоящего на l -м месте в очереди в узле j.
{ } Очевидно, что s(t) есть неприводимая счетная цепь Маркова в непрерывном времени t.
Теорема 1. При выполнении условия (1) марковский процесс s(t) является эргодическим.
Нам удобно ввести в рассмотрение процесс, описывающий поведение рассматриваемой сети более детально.
(, Положим Qt) = Qik (t),(i,k)Gt 0, где G (i,k) : i I,k =1,2,Qik (t) - общее { } { } число требований (i, k) потока, находящихся в узле j = (i,k) в момент t 0. Ясно, что Q(t) есть проекция s(t) (т.е. функция от состояния s(t) ). Определим норму состояния s(t) как s(t) Qt) Qik (t).
( (i,k )G Условимся, что все величины, относящиеся к процессу s(t), будут в дальнейшем снабжены верхним индексом n, если s(0) = n 1.
n Обозначим через Fik (t),t 0, суммарное число требований (i, k) -потока, поступивших в узел j = (i,k) до момента времени t, включая требования (i, k) -потока, n находящиеся в узле j в начальный момент t = 0. Для определенности положим Fik (t) - неотрицательные кусочно-постоянные неубывающие функции непрерывными справа.
- Определим отрицательную константу T0 : T0 =- min,i I,ik,(i, k) G.
i n Продолжим функции Fik (t) на отрезок nT0,0 следующим образом. Условимся, [ ] что требования, находящиеся в сети в момент t = 0, поступали в сеть в отрицательные моменты nT0,(n -1)T0,...,T0 (по одному требованию в каждый момент). Причем последовательность поступления требований различных классов соответствует их порядку расположения в очередях в момент 0.
n Обозначим через Fik (t) суммарное число требований (i, k) -потока, покинувших узел j = (i,k) до момента t. Ясно, что для всякого n nn n Fik (nT0) = 0, Fik (0) = 0,(i, k)G, Fik (0) = Qn(0) n (i,k )G Если начальное состояние сети имеет норму n 1, то рассмотрим процесс n;(t ) n n F ( ), nT0,t, Fik ( '), ' 0,t,(i, k) G,t 0.
[ ] [ ] } {F ik n;(t) Зададим следующее отображение семейства процессов F с различными } { n;(0) значениями n и начальными состояниями F в семейство нормированных процессов } { n;(t) f. Пусть } { аnn n;(t ) n n f fik ( ), T0,t, fik ( '), ' 0,t,(i, k) G,t 0, где fik (t) Fik (nt),t T0, [ ] [ ] { } n 1 nn nn n fik (t) Fik (nt),t 0. Положим qik (t) Qik (nt), qn (t) qik (t),(i, k)G. Ясно, что для } { n n n;(0) n n любого n 1 и любого f fik (T0) = 0,(i,k)G, qn(0) = fik (0) =1.
, (i,k )G В 13 доказан следующий результат, из которого следует Теорема 1.
[ ] Теорема 2. Существует такая константа T>0, что для любого t T и для любой n;(0) n;(t) последовательности начальных состояний f процессов f выполнено равенство lim E qn (t) = 0.
n 1.1.3. Предельный детерминированный жидкостный процесс и его свойства.
Зафиксируем произвольную пару (i, k) G. Рассмотрим последовательность функций n n;(0) fik (t),t T0,0, n 1, входящих в соответствующие начальные состояния f, n 1, [ ] { } фигурирующие в условии теоремы 3. Нетрудно видеть, что эта последовательность имеет предельные точки в смысле равномерной метрики g - g ' sup g(t) - g '(t), причем [ ] t T0,[ ] каждая предельная точка fik (t),t T0,0, есть неубывающая непрерывная функция, [ ] -удовлетворяющая условиям Липшица с константой L T0 и условию fik (T0) = 0.
n;(0) Таким образом, последовательность начальных состояний f,n 1, содержит nl ;(0) подпоследовательность f,l 0, которая сходится к множеству функций f = fik (t),t T0,0, fik (0) 0,(i, k) G. Каждая из функций fik (t),t T0,0,(i,k)G, [ ] [ ] } { удовлетворяет условиям, приведенным ранее, причем fik (0) = 1.
(i,k )G Естественно предположить, что для любого фиксированного t nl ;(t) последовательность наборов случайных функций f (или, что эквивалентно, nl ;( ) последовательность случайных процессов f, 0,t ) сходится по вероятности к [ ] (t ) некоторому множеству детерминированных функций f (или к детерминированному ( ) жидкостному процессу f, 0,t ).
[ ] В 13 мы не доказываем результат о сходимости процессов. Вместо этого в [ ] данном разделе мы дадим формальное определение предельного детерминированного (t ) жидкостного процесса f, соответствующего предельному начальному состоянию (0) f и исследуем его свойства. В следующем пункте эти свойства детерминированного жидкостного процесса будут в некотором смысле перенесены на последовательность n;(i) случайных процессов f,n . Это позволяет доказать Теорему 2.
Рассмотрим множество функций f = fik (t),t T0, fik (t '),t ' 0,(i, k) G, } { которое удовлетворяет следующим условиям.
1. Для любого (i, k) G, fik (t) и fik (t) являются неубывающими, непрерывными, -функциями, удовлетворяющими условию Липшица с константой L = T0, и n fik (t),t T0,0, n 1, [ ] { } 2. fik (0) = 1. Обозначим wi (t) fik (t)ik,t 0, j J, wi (t) wi (t) -t, (i,k )G (i,k )Gj i (t) t + min0,min w( ),t 0, j J, (t) max t : j ( ) = wj (t),t 0, j J.
[ ] j 0 t Потребуем, чтобы множество функций f удовлетворяло также следующему условию:
fik (t) = fik ( (t)),t 0,(i, k) G, fik (t) = fik (0) + it, k =1,t 0,i I, (i,k ) 3.
fik (t) = fik (0) + fik -1(t),t 0,k >1,i I.
Определение. Если множество функций f удовлетворяет условиям 1-3, то назовем (t ) f = fik ( ), T0,t, fik ( '), ' 0,t,(i, k) G,t 0, [ ] [ ] } { детермированным жидкостным процессом с дисциплиной FIFO, (0) f = fik ( ), T0,t, fik (0) = 0,(i, k) G.
[ ] } { соответствующим начальному состоянию (0) Теорема 3. Для любого начального состояния f (т.е. набора функций fik (t),t T0,0,(i,k)G, удовлетворяющего условиям 1) - 3) существует по крайней [ ] { } (t ) мере один соответствующий ему детерминированный жидкостный процесс f,t 0.
Доказательство этой теоремы легко получить, например, из теоремы Брауэра о неподвижной точке непрерывного отображения выпуклого компакта в себя. Если (t ) некоторый детерминированный процесс f,t 0, фиксирован, то естественно ввести следующие определения:
q(t) qik (t),(i,k)G, где qik (t) = fik (t) - fik (t), q(t) qik (t).
{ } (i,k )G В 7 доказана следующая теорема, относящаяся к детерминированному [ ] (t ) жидкостному процессу f и являющаяся аналогом Теоремы 2.
Теорема 4. Существует такая константа T > 0, что для любого (t ) детерминированного жидкостного процесса f, соответствующего произвольному (0) начальному состоянию f, выполняется следующее свойство:
q(t) = 0,t T.
1.1.4. Сеть со специальной приоритетной дисциплиной обслуживания.
Контрпример к Гипотезе 1. Рассмотрим следующую дисциплину обслуживания в узлах рассматриваемой сети. В узле 1 требования класса 2 (т.е. требования (2,2)-потока) имеют абсолютный приоритет и, наоборот, в узле 2 абсолютный приоритет имеют требования класса 1 (т.е. требования (1,2)-потока).
Нетрудно видеть, что для такой дисциплины обслуживания поведение сети описывается более простой марковской цепью Q(t) со счетным пространством ( состояний: Qt) = Qik (t),(i,k)G,t 0. Заметим, что состояние Q для которых { } > 0, Q1,Q > 0, 2, являются несущественными, и они a priori могут быть исключены из фазового пространства, после чего марковский процесс Q(t) становится неприводимым.
Мы покажем, что марковский процесс Q(t) является невозвратным для широкой области параметров i,i =1, 2,ik,(i,k)G, удовлетворяющих условиям <1, j =1,2.
j оставим все определения предыдущих пунктов без изменений, за исключением специально оговариваемых случаев. Мы также начнем с рассмотрения предельного детерминированного жидкостного процесса.
, Детерминированный жидкостный процесс q(t) = qik (t),(i,k)Gt 0, { } соответствующий фиксированному начальному состоянию q(0), q(0) = 1, задается (аналогично тому, как это сделано выше) как проекция детерминированного процесса (t ) f,t 0, qik (t) = fik (t) - fik (t),(i,k)G,t 0, (0) с произвольным начальным состоянием f, удовлетворяющим условию fik (0) = qik (0),(i,k)G.
(t ) Детерминированный жидкостный процесс f,t 0 определяется аналогично тому, как это было сделано для дисциплины FIFO, необходимо лишь заменить условие 3 на следующее условие 3*:
3*. fik (t) = fik (ik (t)),t 0,(i, k) G, fi1(t) = fi1(0) + it,t 0,i I, fik (t) = fik (0) + fik -1(t),i I,k = 2, где ik (t) max t : wik (t) = ik (t),(i,k)G, wik (t) fik (t)ik (t),(i,k)G, [ ] ik (t) t + min0,min wik ( ),(i, k) = (1,2),(2,2), wik (t) = wik (t) - t,(i, k) G, 0 t 11(t) = 1(t) - 22(t), 21(t) = 2(t) - 12(t) (функции j (t), j J, определены выше).
Замечание 1. В рассматриваемом в данном разделе случае процесс q(t) может быть d также определен как решение дифференциального уравнения вида q(t) = A(q(t)),t dt с разрывной функцией A().
Замечание 2. Нетрудно видеть, что существуют такие начальные состояния q(0), что соответствующий им процесс q(t) не единственен. Например, по крайней мере два различный процесса q(t) соответствуют такому начальному состоянию, что q11(0) > 0, q21(0) > 0, q12(0) = q22(0) = 0.
Рассмотрим нашу сеть со следующими параметрами:
1 = 2 =1,12 =22 =2 > 1/ 2,11 =21 =1, причем выполняется условие (1), которое принимает вид 1 +2 <1. Следовательно, выполняется неравенство 0 1 1-2.
Теорема 5. Пусть фиксировано следующее начальное состояние процесса q(t) :
q11(0) = 1, q12(0) = q21(0) = q22(0) = 0.
Пусть T =2 / (1-2) > 1, T1 =1 / (1-1). Тогда детерминированный жидкостный процесс q(t) на отрезке 0,T определяется единственным образом и имеет вид [ ] 0 t T1, 1- ((1)-1 -1)t, q11(t) = T1 t T, -1 - (1 -2 )t,0 t T1, q12(t) = -1 --1)(1-1)-12 - (2 -1)t,T1 t T, ( q21(t) = t,0 t T, q22(t) = 0 t T.
Таким образом, в момент времени Т, q21(T ) = T > 1, q11(T ) = q12(T ) = q22(T ) = (Доказательство следует непосредственно из определения q(t).) Мы видим, что в момент времени Т состояние процесса q(t) подобно с точностью до симметрии состоянию в момент времени t = 0 и q(T ) = T > q(0) =1. Следовательно, процесс q(t), с начальным состоянием, рассматриваемым в Теореме 5, обладает свойствами q(t) 0,t 0, q(t) ,t .
( Вернемся теперь к рассмотрению марковского процесса Qt) = Qik (t),(i,k)G.
{ } Теорема 6. Если параметры сети таковы, что 1 = 2 = 1,12 =22 >1/ 2,11 =12 =1 > 0,1 +2 < 1, то марковский процесс Q(t) невозвратен.
1.2. Неэргодичность телекоммуционных сетей при нестабильности их жидкостных моделей, общий случай.
1.2.1. Описание модели. Мы рассматриваем открытую сеть, состоящую из M узлов, в которой циркулируют требования L классов. Имеется L ' L внешних потоков требований, при этом каждый внешний поток содержит требования лишь одного класса.
Класс требований однозначно определяет номер узла, в котором она обслуживается, так что L M. Требования, поступившие в данный узел, образуют единую очередь в порядке моментов их поступления, а обслуживание происходит в соответствии с дисциплиной обслуживания, принятой в этом узле. Относительно последней предполагается, что она определяется только классами требований и местами, которые они занимают в очереди;
внутри классов требования обслуживаются в порядке поступления. После окончания обслуживания в узле требование либо меняет класс и поступает на обслуживание в соответствующий узел, либо покидает сеть обслуживания.
Сопоставив сети ее жидкостную модель, мы покажем, что при выполнении некоторых технических условий верно следующее: если существует такое начальное состояние жидкостной модели, для которого равномерно по всем "жидкостным траекториям" с "близкими" начальными состояниями (заметим, что в общей ситуации траектории жидкостной модели не единственны) "общее количество жидкости" стремится к бесконечности не медленнее, чем линейно, то случайный процесс, описывающий поведение сети обслуживания, неэргодичен. Этот результат дополняет результаты Столяра и Дая и, по-видимому, охватывает все имеющиеся в настоящее время примеры неэргодических сетей обслуживания.
Пусть U - метрическое пространство с борелевской -алгеброй B (U ). Скажем, что последовательность Pn, n 1 (или последовательность Xn, n 1 случайных { } { } элементов с распределениями Pn ) является экспоненциально плотной с показателем an, 1/an если для любого > 0 существует компакт K U такой, что limPn (U / K) .
n Известный результат Пухальского2 заключается в том, что если последовательность Pn, n 1 экспоненциально плотна с показателем an, то существует { } подпоследовательность n' такая, что последовательность Pn', n' 1 удовлетворяет { } принципу больших уклонений для нормирующей последовательности an' с некоторым функционалом действия I '. Назовем любой такой функционал действия I ' предельной точкой последовательности Pn, n 1 в смысле принципа больших уклонений для { } нормирующей последовательности an.
аPuhalskii A. On functional principle of large diviations. New Trends in Probability and Statistics. Utrecht;
VSP/MoksТlas, 1991, V.1, P.198-218а Также скажем, что последовательность Pn,n 1 является U0 -экспоненциально { } плотной с показателем an, где U0 U, если Pn,n 1 является экспоненциально плотной { } с показателем an, и любая ее предельная точка I ' в смысле принципа больших уклонений для нормирующей последовательности an обладает тем свойством, что I '(z) = для всех z U \U0.
Определим теперь некоторые топологические объекты, которые нам понадобятся в дальнейшем. Пусть S - полное сепарабельное метрическое пространство. Обозначим чеpез D( 0,, S) пространство Скорохода непрерывных справа и имеющих пределы [ ) слева функций, заданных на 0, и принимающих значения в S с метрикой Скорохода[ ) Прохорова-Линдвалла, превращающей это пространство в полное сепарабельное метрическое пространство.
Обозначим через Vb+ пространство неубывающих, ограниченных и непрерывных справа функций на 0, со значениями в +, равных 0 в точке 0. Следующая [ ) конструкция превращает Vb+ в полное сепарабельное метрическое пространство. Пусть D( 0,1, ) - пространство Скорохода действительнозначных, непрерывных справа, [ ] + имеющих пределы слева функций на 0,1, и пусть D0 ( 0,1, ) - подпространство [ ] [ ] D( 0,1, ), состоящее из неубывающих, равных 0 в точке 0, непрерывных слева в точке [ ] + функций. Установим взаимнооднозначное соответствие между Vb+ и D0 ( 0,1, ), [ ] сопоставляя функции f Vb+ функцию f = ( f(t),t 0,1 ), определяемую соотношениями [ ] f(t) = f (-log(1-t)),0 t <1 и f(1) = lim f (t). Обозначая чеpез d0 (полную) метрику t Скорохода-Прохорова D( 0,1, ), положим по определению ( f, g) = d0( f, ) [ ] для f, g Vb+. Очевидно, что Vb+ с метрикой является метрическим пространством, гомеоморфно вкладывающимся как замкнутое множество в D( 0,1, ), в частности, оно [ ] является полным сепарабельным метрическим пространством. Для J f = ( f, j =1,..., J )(Vb+ )J примем обозначение f = lim f (x). Обозначим через j j x j=D+( 0,, d ) подпространство D( 0,, d ) покомпонентно неубывающих и равных 0 в [ ) [ ) точке 0 функций; через C( 0,, S) (соответственно, C+ ( 0,, d ) ) - подпространство [ ) [ ) непрерывных функций, лежащих в D( 0,, S) соответственно, D+ ( 0,, d ) через Vc+ - [ ) [ ),подпространство D( 0,, ) неубывающих непрерывных липшицевых функций с [ ) константой Липшица, не превосходящей 1, равных 0 в точке 0; через Vb+ -,c,подпространствоVb+, определенное какVb+ = Vb+ Vc+. Все подпространства снабжены,c,1,индуцированными топологиями. Произведения пространств снабжены топологиями произведения.
1.2.2. Жидкостная модель, основной результат. Мы рассматриваем сеть массового обслуживания, описанную в п.1.2.1. Через s(l) обозначим узел, в котором обслуживаются требования класса l, где l = 1, 2,..., L. Через c(m), m = 1,..., M, обозначим множество классов требований, которые обслуживаются в узле m: c(m) = l 1,2,..., L : s(l) = m. Сопоставим состоянию сети в момент времени t { } } { вектор N(t) = (Nl (k,t),l =1, 2,..., L, k = 1, 2,...), где Nl (k,t) обозначает количество требований класса l среди первых k заявок в очереди к прибору s(l) в момент t (напомним, что требования в узле стоят в очереди в порядке их поступления). Для l = 1,..., L обозначим через El (t) количество требований класса l, поступивших извне за время t. Обозначим через Sl (t) количество требований класса l, обслуженных прибором s(l) за время обслуживания заявок этого класса, равное t. Для l,l ' = 1, 2,..., L обозначим через ll '(i) количество требований класса l среди первых i требований класса l, обслуженных прибором s(l), которые после обслуживания превратились в требования класса l '. Все рассматриваемые нами случайные объекты предполагаются заданными на одном вероятностном пространстве (, F, P).
Определим теперь жидкостную модель, соответствующую данной сети обслуживания. Для этого рассмотрим последовательность сетей обслуживания, занумерованных индексом n и отличающихся от исходной только начальными состояниями (т.е. с теми же процессами поступления, обслуживания и изменения классов требований, задающимися случайными величинами El (t), Sl (t) и ll '(i) соответственно).
Состояние n -й сети в момент времени t будем обозначать через Nn(t) = (Nln(k,t),l =1,..., L,k =1,2,...). Введем соответствующие нормированные процессы, полагая Eln (t) = El (nt), En (t) = (Eln (t),l = 1,..., L), En = (En (t),t 0), n n Sln (t) = Sl (nt), Sn (t) = (Sln (t),l = 1,..., L), S = (Sn (t),t 0), n n n ll '(t) = ll '(nt),n (t) = (ll '(t),l = 1,..., L),n = (n (t),t 0), (2) n Fln (xt) = Nln (nx, nt), Fl n (t) = (Fln (x,t), x 0), n Fn(t) = (Fln(t),l =1,..., L), Fn = (Fn(t),t 0).
n Процессы En, S и n рассматриваются как случайные элементы пространств D+( 0,, L), D+( 0,, L) и D+( 0,, LL), соответственно. Мы рассматриваем [ ) [ ) [ ) n F (t) как случайный элемент пространства (Vb+)L, и Fn - как случайный элемент пространства Скорохода D( 0,,(Vb+)L). Заметим, что общее число требований класса l, [ ) стоящих в очереди в узле s(l) в момент t, равно Qln(t) = Nln(,t).
Зададим также процессы Bn = (Bn(t),t 0) как Bn(t) = (Bln(t),l =1,..., L), Bln(t) = Bln(nt) / n, где Bln(t) обозначает время, затраченное узлом s(l) на обслуживание требований класса l за время t для n -й сети. Поскольку приращения Bln (t) - Bln (s), m = 1,..., M для t s не превосходят t - s, то процессы Bn lc(m) lc(m) pассматpиваются как случайные элементы Vc+ - подпространства C+( 0,, L) функций [ ),1,L f = ( f1,..., fL ) таких, что fl ,Vc+, m = 1,..., M снабженного индуцированной ,lc(m) топологией.
n,t0 n,t0 Для t0 0 определим сдвиги F = (F (t),t 0), Bn,t = (Bn,t (t),t 0), 0 0 0 0 0 En,t = (En,t (t),t 0), Sn,t = (Sn,t (t),t 0) и n,t = (n,t (t),t 0), полагая 0 0 Fn,t (t) = Fn(t + t0), Bn,t (t) = Bn(t + t0) - Bn(t0), En,t (t) = En(t + t0) - En(t0), Sln,t (t) = Sln(t + Bln(t0)) - Sln(Bln((t0)),l =1,2,..., L, n,t0 n n l (t) = ll '(t + Sln(Bln(t0))) - ll '(Sln(Bln(t0))), l,l ' = 1, 2,..., L Предположим, что имеют место законы больших чисел:
P P n Etn(t) Stn(t) ll '(t) P pll 't, l,l ' = 1, 2,..., L (3) lt, lt, P где обозначает сходимость по вероятности. Введем функции:
= ((lt,l =1,..., L),t 0), = ((lt,l =1,..., L),t 0), p = (( pll 't,l,l ' = 1,..., L),t 0).
Обозначим через Vb+ подпространство пространства (Vb+ )L функций,c,1,L,c,f = ( f1,..., fL ) таких, что fl (x) = x пpи x fl, m = 1,..., M. (4) lc(m) lc(m) Заметим, что Vb+ замкнуто в (Vb+)L.
,c,1,L Пусть G = (Gl ( f,b,e,s,)), где t 0, f D( 0,,(Vb+ )L), bVc+, [ ),1,L e D+ ( 0,, L), s D+ ( 0,, L) и D+( 0,, LL) - функция со значениями в [ ) [ ) [ ) конечномерном векторном пространстве, являющаяся C( 0,,Vb+ )Vc+ C+( 0,, L)C+( 0,, L)C+ ( 0,, LL) -непрерывной и [ ) [ ) [ ) [ ),c,1,L,1,L борелевской по f, b, e, s и при каждом значенииt. Предположим также, что G обладает следующим свойством автомодельности:
Gkt f,b,, , p = Gt ( f *k,b*k,, , p),t 0, k = 1, 2,..., (5) () k где по определению f *k = (k-1 f (kx, kt), x 0,t 0) и b*k = (k-1b(kt),t 0).
Будем говорить, что функция G задает жидкостную модель, если для n всех n = 1, 2,...,, начальных состояний N (0) и t 0 имеет место pавенство 0 0 0 0 Gt (Fn,t, Bn,t, En,t, Sn,t,n,t ) = 0,t 0 (6) Пусть Lip ( 0,,Vb+ ), где > 0, обозначает подмножество C( 0,,Vb+ ) [ ) [ ),c,1,L,c,1,L функций f = ( f1,..., fL ) таких, что sup fl (x,t) - fl (x, s) (t - s), 0 s t,l = 1,..., L. (7) xДля f0 Vb+ определим M( f0) как множество функций f Lip ( 0,,Vb+ ), [ ),c,1,L,c,1,L L где = (l + 2l ), с начальным значением f (0) = f0, для которых существуют такие l=функцииbVc+, что Gt ( f,b,, , p) = 0,t ,1,L Мы также обозначим через Mt ( f0) множество f (t) : f M( f0). Назовем { } семейство M = M ( f0) : f0 Vb+ семейством жидкостных решений (траекторий), { },c,1,L соответствующим функции G. Заметим, что M замкнуто в C( 0,,Vb+ ).
[ ),c,1,L Для > 0 и g (Vb+)L обозначим чеpез g функцию, для котоpой g (x) = g( x), x 0; соответственно, для множества функций положим = g : g .
{ } Принимая во внимание свойства непрерывности и автомодельности функцииG, а также тот факт, что множество функций f Lip ( 0,,Vb+ ) таких, что f (0) [ ),c,1,L принадлежит компактному множеству, является компактом в C( 0,,Vb+ ), мы видим, [ ),c,1,L что семейство M обладает следующими свойствами: (автомодельность) для k = 1, 2,... и f0 Vb+ ),c,1,L M(k-1 f0 k) = f *k, f M( f0), в частности, Mt ( f0 k) = Mkt ( f0) k,t 0;
{ } kk (компактность) для каждого > 0 множество M( f0) является компактом в f0Vb+ : f0 ,c,1,L C( 0,,Vb+ ). Эти условия естественны для жидкостной модели. Наложим следующие [ ),c,1,L ограничения на процессы E, S и .
(А) Последовательности распределений процессов En,n 1, Sn, n 1 и } } { { n,n 1 являются, соответственно, C+ ( 0,, L) -, C+ ( 0,, L) - и C+( 0,, LL) [ ) [ ) [ ) } { экспоненциально плотными с показателем n. Если функционалы действия IE, IS и I являются соответствующими точками накопления в смысле больших уклонений для En,n 1, Sn, n 1 и n, n 1 для нормирующей последовательности n, то они равны } } } { { { нулю только на функциях , и p соответственно.
Условие (А), в частности, выполнено в обычной ситуации, когда для каждого класса требований входные управляющие последовательности интервалов времени между поступлениями требований и времен обслуживания являются н.о.p., и процессы изменения классов требований после окончания обслуживания являются процессами Бернулли. Заметим, что условие (А) влечет за собой (3). Следующая теорема является основным результатом пункта 1.2.
Теорема 7. Пусть функция f0 Vb+ такова, что,c,1,L f(t) C := lim inf > 0.
t fM( f0 ) t Пусть существует Vb+ Vb+ -непрерывная функция R :(Vb+ )L Vb+ +,c,1,L,c,1,L,c,1,L такая, что R( f, g) g - f и R( f, g) = R( f, g) для f (Vb+ )L, g Vb+, > 0, и,c,1,L существуют натуральное число k0 и числа (0,C), (0,C / -1) и > 0, для которых выполнены следующие свойства:
1) Если функция f0 Vb+ удовлетворяет условию R :( f0, f0) , то,c,1,L 0 0 sup inf R(g 2k, g 2k ) 2k ;
gM ( f0 ) gM ( f0 ) 2k0 2k2) Если функция f0 Vb+ такова, что для некоторого k k0, k0 +1,..., { },c,1,L inf( R( f0 2k, g 2k ) 2k; то sup inf R(g 2k +1, g 2k +1) 2k +1.
gM2k f0 ) gM2k+1 ( f0 ) gM2k ( f0 ) Пусть, кpоме того, esssup R(Fn(0), f0) 0 пpи n . Тогда n F (2k ) lim P(lim > C - (1+) =1.
n k 2k Следствие 1. При выполнении условий теоремы 1 для всех достаточно больших n справедливо n n lim limP( N (t) a) > 0, и, следовательно, процесс N (t),t 0, неэргодичен.
t 1.2.3. Обсуждение. В этом параграфе мы обсуждаем условия Теоремы 7, формулируем различные ее варианты и следствия. Мы также pассматpиваем некоторые свойства жидкостных моделей.
Прокомментируем сначала условия 1 и 2 Теоремы 7. Условие 1 выполняется, если жидкостные траектории на конечных интервалах времени непрерывно зависят от начального состояния. Условие 2 означает, что конус траекторий, близких к траекториям, выходящим из f0, "расширяется" не быстрее, чем линейно: если в момент времени 2k жидкостная траектория находится в "окрестности" размера 2k (1+) вокруг траекторий, выходящих из точки f0, то в момент времени 2k +1 она будет находиться в "окрестности" размера 2k +1. Роль расстояния играет здесь функция R, типичными примерами ее выбора являются R( f, g) = g - f и R( f, g) = sup g(x) - f (x).
xТеорема 7 дает условия, при которых случайный процесс N (t) неэргодичен. Если мы несколько усилим условия теоремы, потребовав, чтобы, начиная с некоторого k0, траектории, близкие в момент 2k к траекториям, выходящим из f0, были близки к ним на k всем интервале, 2k +1, а не только в момент 2k +1, то можно утверждать невозвратность траекторий N (t) в ноль. Именно, имеют место следующие утверждения, доказательства которых аналогичны доказательствам Теоремы 7 и Следствия 1.
Теорема 8. Пусть в Теореме 7 условие 2 заменено следующим условием:
+ 2Т. если функция f0 b,c,1,L такова, что inf R( f0 2k, g 2k ) (1+) 2k gM ( f0 ) 2k для некоторого k k0,k0 +1,..., то { } sup sup inf (1+ t)-1R g(2k t) 2k (1+ t), g 2k (1+ t) 2k (1+ t) 2k.
( ) ( ) ( ) ( ) gM( f0 ) 0t1gM2k ( f0 ) n F (t) Тогда lim P lim > C - (1+) =1.
n t t Следствие 2. При выполнении условий теоремы 2 для всех достаточно больших n n n P lim N (t) = > 0 т.е. процесс N (t),t 0 невозвратен.
t Замечание. Теоремы 7 и 8 налагают ограничения на расстояния между жидкостными траекториями в моменты 2k,k = k0,k0 +1,... Такой выбор моментов времени не является, однако, единственно возможным: утверждение теоремы остается в силе, если заменить указанную последовательность моментов времени на произвольную возрастающую последовательность tk, k = k0, k0 +1,..., такую, что lim tk +1 / tk < и k lim tk +1 / tk >1. Доказательства отличаются лишь обозначениями.
k Глава 2. Термодинамический предел для телекоммуникационных сетей В этой главе рассматриваются бесконечные сети и сети с растущим к бесконечности числом узлов. Изучаются инвариантные меры таких сетей. Общий случай Пуассоновской гипотезы Боровкова-Клейнрока для замкнутой симметричной сети на полнлсвязном графе был доказан в 21,31- 33,35. Он потребовал исследования предельного нелинейного [ ] марковского процесса - нелинейной динамической системы в пространстве вероятностных мер на специальном многообразии, и доказательства того факта, что указанная динамическая система имеет глобальный аттрактор - точку в пространстве вероятностных мер, являющуюся произведением стационарных мер систем MGI 1 отдельных узлов сети.
2.1. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе. Пуассоновская гипотеза.
2.1.1. Формулировка задачи. Рассмотрим следующую телекоммуникационную сеть: имеется N обслуживающих устройств (очередей) и M требований. Эти требования находятся в указанных очередях и обслуживаются согласно дисциплине FIFO в каждом узле, причем во всех очередях времена обслуживания образуют последовательность одинаково распределенных независимых случайных величин с (фиксированной) функцией распределения F (x),0 x <. Обозначим через a среднее значение времени обслуживания:
a = xdF(x) < . (8) Потребуем также для простоты, чтобы у распределения F () имелась плотность F '(x). Специальным обстоятельством, выделяющим рассматриваемый класс сетей, является следующее естественное правило маршрутизации: мы будем считать, что всякое требование, заканчивая обслуживание в любом узле, независимо от прошлого поступает в конец любой очереди к соответствующему прибору n = 1,..., N с одинаковой -вероятностью Pn N.
Мы будем рассматривать данный случайный процесс как марковский. Простейшим (но не лучшим) образом (см. далее) состояния этого процесса Y(M,N )(t), лежащие в соответствующем фазовом пространстве A(M, N) N N, задаются как набор + очередей (k1,..., kn,..., kN ) в узлах 1,..., N и набор x1,..., xn,..., xN времен, уже затраченных { } на обслуживание требований, находящихся на обслуживании в соответствующих непустых очередях. Ясно, что процесс Y(M,N )(t) эргодичен при минимальных ограничениях на распределение F (). Действительно, ясно, что с вероятностью единица через конечное время все N требований окажутся в одной очереди, например, на первом приборе. Затем момент времени, когда очередное требование заканчивает обслуживание (в первом приборе) является моментом восстановления. Поскольку среднее время между наступлением двух соседних таких моментов конечно, то процесс Y(M,N )(t) эргодичен. Нас будут интересовать свойства семейства инвариантных мер M,N () процессов Y(M,N )(t).
Нереально надеяться на явное аналитическое нахождение инвариантной меры M,N () для общего распределения F () времени обслуживания одного требования и для произвольных значений параметров M, N +. Известны два случая, когда удается явно найти инвариантную меру M,N : во-первых, когда времена обслуживания требований распределены экспоненциально, и во-вторых, когда все времена обслуживания равны фиксированной константе. В этом (втором) случае возникает конечная цепь Маркова с числом состояний, быстро растущим с ростом M и N, однако, по крайней мере при малых M и N возможно явно вычислить соответствующую инвариантную меру.
А.А.Боровков в 1995 г. предложил простую и естественную гипотезу о свойствах M,N () при N , M , lim M / N = > 0, заключающуюся в следующем.
N Естественно думать, что в указанном термодинамическом пределе потоки требований, поступающие в любое конечное множество очередей, будут пуассоновскими и независимыми между собой, поскольку они являются объединением бесконечного числа бесконечно малых потоков требований, поступающих из других различных очередей.
Коль скоро это верно, то нетрудно из соображений баланса вычислить предельное значение для интенсивности пуассоновского потока, поступающего в любой фиксированный узел. Предельная проекция инвариантной меры на данный узел оказывается стационарной мерой классической системы массового обслуживания M GI 1 , - очереди, с дисциплиной обслуживания FIFO на которую поступает постоянный пуассоновский поток требований интенсивности , а длины всех требований взаимно независимы и одинаково распределены с функцией распределения F (). При этом находится из соотношения: среднее число требований в стационарном режиме системы M GI 1 совпадает с = lim M / N. Прежде всего заметим, что эта гипотеза N была ранее доказана для случая постоянного времени обслуживания в работе А.Столяра3.
Отметим также, что факт об асимптотической независимости отдельных узлов при термодинамическом предельном переходе в такого рода задачах принято называть термином УPropagation of ChaosФ.
Доказательство гипотезы базируется на том факте, что на фазовом пространстве действует группа G симметрий, относительно которой рассматриваемый марковский процесс инвариантен. Это означает, что для любой пары x A(M, N ) и y A(M, N ) элементов x, y фазового пространства A(M, N) процесса y(M,N )(t) и любого элемента группы g G q(x, y) = q(g(x), g( y)), (9) где q(,) - соответствующие инфинитизимальные переходные вероятности. В нашем случае группой G является группа перестановок N -го порядка, возникающая при различных перенумирациях N обслуживающих приборов (очередей). Теперь естественно N перейти к фактор-процессу () - марковскому процессу, возникающему благодаря (9) на пространстве орбит группы G. Эти орбиты удобно наглядно интерпретировать как специальные вероятностные меры на соответствующем фазовом пространстве. В нашем случае орбиты задаются как наборы долей (плотности долей) очередей (из всего множества N очередей), имеющих фиксированную структуру (длину очереди k и обслуженное время ). Таким образом, этот естественный фактор-процесс описывается как случайная эволюция вероятностных мер на специальном пространстве U.
2.1.2. Основная конструкция и результаты. Приведем более детальное описание N фактор-процесса () в нашем случае. Пусть - множество натуральных чисел.
N Положим U = 0 ( + ). Фазовым пространством процесса () являются { } специальные атомарные вероятностные меры на U. Меру x мы называем рациональной со знаменателем N, если значение x - меры любого измеримого по ней множества является рациональным числом со знаменателем N. Множество таких вероятностных мер на пространстве U мы обозначаем через PN. Всякая мера x PN образована N атомами, расположенными в пространстве U, каждый из которых имеет меру 1/ N. Допускается, чтобы некоторые их этих атомов сливались. Атомарная мера x PN имеет следующую интерпретацию: мера атомов, расположенных в точке 0 U интерпретируется как доля { } N пустых очередей (из N очередей) для состояния процесса (). Атом массы 1/ N, находящийся на n -м луче + и имеющий координату на этом луче означает, что у Столяр А.Л. Асимптотика стационарного распределения для одной замкнутой системы обслуживания// Пробл. Передачи информ. 1989. T.25. №4. C. 80-92.
состояния x PN имеется очередь, содержащая ровно n требований, причем требование, находящееся на обслуживании, уже обслуживается ровно время .
Опишем наглядно случайную эволюцию атомарных мер x PN соответствующую N марковскому процессу () :
1) у всех атомов типа (n, ), n 1, лежащих на лучах (n, + ),n 1 со скоростью единица растет координата , - это соответствует продолжению обслуживания требований, обслуживающихся в непустых очередях;
2) атомы с координатами (n, ), n 1 совершают прыжки в точки (n -1,0) с F '( ) интенсивностями ( ) = - эти события означают, что требование, находящееся на 1- F( ) обслуживании в течение времени в очереди длины n, закончило обслуживание.
3) в момент прыжка, описанного в п.2) происходит следующее событие: с вероятностью 1/ N выбирается произвольный атом из конфигурации, пусть, например, его координаты (n ', ') U, (если выбранный атом находился в 0 U, то для него координата ' 0 ) и { } выбранный атом прыгает из точки (n ', ') U в точку (n '+1, ') U. Это событие соответствует переходу требования, закончившего обслуживание в узле с очередью (n, ) в очередь (n ', ').
Мы напомним основные факты, касающиеся нелинейных марковских процессов Мы ограничимся простейшим случаем марковских цепей с дискретным временем, живущих на конечном множестве S, S = k. Случай, достаточной для наших нужд общности, описан в 20,21, разделы 2 и 3. В дискретном случае множество состояний [ ] нашей марковской цепи - это симплекс k всех вероятностных мер на S, k = = ( p1,..., pk ) : pi 0, p1 +...+ pk =1, а эволюция марковского процесса определяет { } отображение P : k k. В случае обычной марковской цепи отображение P аффинно, и поэтому мы будем называть такую цепь линейной. Матрица переходных вероятностей совпадает с P. Нелинейная марковская цепь определяется семейством матриц переходных вероятностей P, k, где элемент P (i, j) есть вероятность перехода от i к j за один шаг, начиная из состояния . Нелинейное отображение P теперь определяется как P = P.
Эргодические свойства линейных марковских цепей определяются теоремой Фробениуса-Перрона. В частности, если линейное отображение P таково, что образ P(k ) содержится во внутренности Int(k ) множества k, то существует в точности одна точка Int(k ), такая что P() = и для любого k имеется сходимость P ( ) при n .
Если отображение P нелинейно, то мы имеем дело с более или менее произвольной динамической системой на k, и в общем случае нельзя ответить на вопрос о стационарных состояниях цепи или о мерах на множестве k, инвариантных относительно P.
Замечательным обстоятельством является то, что имеется предельная при N , M детерминированная динамическая система y x(t, y), y P, x(t, y) P,t 0, аMcKean, H., P.,Jr. A>
Sci. USA., 56, 1966, 1907-1911.
McKean, H., P.,Jr. An exponential formula for solving BoltzmannТs equation for a Maxwellian gas. J.
Combinatorial Theory, 2, 1967, 358-382.а описывающая предельную детерминированную эволюцию вероятностных мер на том же фазовом пространстве U. Эта динамическая система задается бесконечной нелинейной системой интегро-дифференциальных уравнений в соответствующем банаховом пространстве, и следующим необходимым шагом является доказательство существования и единственности решения этой системы уравнений. Здесь (и далее) помогает вероятностная интерпретация решения системы y x(t, y), y P, x(t, y) P,t 0 как эволюция вероятностной меры, задающей соответствующий нелинейный марковский процесс. В нашем случае этот нелинейный марковский процесс наглядно устроен следующим образом: пусть имеется неоднородный марковский процесс (t), описывающий эволюцию очереди M (t) GI 1 на которую поступает переменный пуассоновский поток интенсивности (t). Точкам фазового пространства процесса (t) сопоставим точки U полагая, что точка (n, ) соответствует следующему событию - длина очереди процесса (t) равна n, а обслуживаемое требование обслуживалось время . Обозначим через y = x(0) начальное состояние процесса (t) - вероятностную меру на U = 0 ( + ). Обозначим через x(t, y) P вероятностную меру на U для { } процесса M (t) GI 1 в момент времени t. Наложим на (t) дополнительное условие, связав (t) с самой мерой x(t, y) на очередях нашего процесса M (t) GI 1 в момент t :
именно, положим (t) равной средней по мере x(t, y) интенсивности выхода требований из очереди.
(t) = Ex(t, y) ( ) = ( ) y)(n, ) (10) ( ) (x(t, )d n= Обозначим через (t) нелинейный марковский процесс, соответствующий эволюции мер y x(t, y) процесса (t) для входа которого выполняется дополнительное равенство (10).
Теорема 9. Пусть функция (r), r + принадлежит банахову пространству C1( + ). Тогда для любой начальной вероятностной меры y P нелинейный марковский процесс, отвечающий динамической системе y x(t, y), y P,t 0 существует и единственен.
Доказательство это теоремы основано на использовании принципа сжатых отображений.
Следующим шагом является доказательство сходимости при N N , M , lim M / N = > 0 марковских процессов () к предельной N динамической системе - нелинейному марковскому процессу (t). При любом t определим линейный оператор T (t) : T (t)F ( y) = F (x(t, y)),действующий в множестве функций на P.
Обозначим через BN банахово пространство ограниченных числовых функций на PN, с нормой F = sup F (x),F BN.
N N Марковскому процессу () с пространством состояний PN отвечает полугруппа T () линейных операторов, действующих в пространстве BN. Именно, если F BN, то N N (TN (t)F )(x) = E(F ( (t)) (0) = x), x PN.
Теорема 10. Для любого t 0 и любой функции F и P, непрерывной в слабой топологии, выполняется равенство lim sup TN (t)F (y) -F (x(t, y)) = 0 (11) N yPN Сходимость в (11) равномерна на каждом отрезке изменения t.
Доказательство этой теоремы основано на использовании теоремы ТроттераКуртца о сходимости марковских полугрупп.
Теорема 11. Для нелинейного марковского процесса (t), определяющего специальную эволюцию очереди M (t) GI 1 при любой начальной мере y, функция (t) при t сходится к константе = (y), где находится из соотношения: средняя длина очереди по стационарной мере для системы MGI 1 с входным пуассоновским потоком постоянной интенсивности равна средней длине очереди по мере y.
Таким образом, из Теорем 9-11 следует справедливость пуассоновской гипотезы N для рассматриваемой модели - последовательности процессов (), поскольку из общих теорем о сходимости марковских полугрупп следует, что множество инвариантных мер нелинейной динамической системы y x(t, y), y P,t 0 содержит все предельные точки множества M,N и поскольку, согласно Теореме 11, процесс (t) при фиксированной начальной средней длине очереди сходится к единственной инвариантной мере. Сложное по существу и громоздкое доказательство Теоремы 11 основано на следующем нетривиальном свойстве самоусреднения.
2.1.3. Свойства самоусреднения систем массового обслуживания.
Рассмотрим неоднородный по времени случайный процесс - систему массового обслуживания M (t) G 1 , на которую поступает пуассоновский поток переменной интенсивности (t), а времена обслуживания образуют стационарную эргодическую последовательность со средним временем обслуживания равным единице. Наложим на функцию (t) условие неперегруженности:
l limsup (x)dx <1 (12) T T -T Наложим также на функцию (t) следующее условие: (t) является непрерывной положительной функцией и следующие интегралы расходятся 0 (x)dx =, (13) (x)dx =.
- Теорема 12. Обозначим через b(t) интенсивность окончания обслуживания требований в момент времени t для указанной системы M (t) G 1 . Тогда функция b(t) удовлетворяет уравнению:
+ b(t) = (t - x)q,t (x)dx, - < t < , (14) - где ядра q,t зависят от функции только через ограничение . Более того, эти (-,t ] ядра стохастические, т.е. для каждого t выполнено (15) ,t q (x)dx = 1, где q,t (x) = 0 при x < 0.
В работах 31- 33 Теорема 12 была доказана для системы M (t) GI 1 .
[ ] Доказательство было основано на новых нетривиальных комбинаторных конструкциях.
Общий результат - Теорема 12 для системы M (t) G 1 доказан в 35.
[ ] Глава 3. Пуассоновская гипотеза для симметричных сетей с несколькими типами требований и несколькими типами узлов Содержание этой главы основано на работах 39, 41. Техника, развитая в [ ] 21, 22,31- 33,35 позволила изучать термодинамический предел инвариантных мер [ ] марковских процессов, описывающих симметричные сети более сложной природы, чем замкнутые сети на полном графе с одним типом требований. Модели реальных телекоммуникационных сетей (напр. Internet) требуют изучения сетей со многими классами требований и со многими типами узлов с различными параметрами.
Неожиданно оказалось, что Пуассоновская гипотеза Клейнрока для симметричных замкнутых сетей с несколькими типами узлов и несколькими классами требований, вообще говоря, неверна при достаточно большой нагрузке (отношению числа требований к числу узлов). Доказательство этого факта в 41 основано как на изучении свойств [ ] жидкостного предела, так и на изучении термодинамического предельного перехода для симметричных замкнутых сетей общего вида. Оказалось также, что пуассоновская гипотеза для таких сетей справедлива при малой нагрузке 39.
[ ] 3.1. Спонтанные резонансы и когерентные состояния в сетях с очередями.
3.1.1. Инфрмационные сети и их коллективное поведение. Пуассоновская гипотеза является инструментом, позволяющим предсказывать поведение больших систем с очередями. Она впервые была сформулирована Л.Клейнроком и касается следующей ситуации. Рассмотрим большую сеть, состоящую из серверов, по которым циркулирует большое число требований. Требования обслуживаются в различных узлах сети. Если узел занят, то требование становится в очередь. Требования поступают в сеть извне через некоторые из узлов, и эти внешние потоки требований - пуассоновские, с постоянными интенсивностями. Время обслуживания на каждом узле случайное, зависящее как от узла, так и от требования. Пуассоновская гипотеза предсказывает следующее поведение сети в большом масштабе пространства и времени:
Х Рассмотрим полный входящий поток F требований на данный узел N. Тогда F приближенно равен пуассоновскому потоку P с зависящей от времени функцией интенсивности N (T ).
Х Выходящий поток из узла N - не пуассоновский в общем случае! - имеет интенсивность N (T ), которая, как функция времени, является более гладкой, чем N (T ) (из-за усреднения, имеющего место в узле N ).
Х В результате интенсивности потоков N (T ) на разных узлах N сходятся к T постоянным пределам N N (t)dt при T . Потоки, приходящие на T различные узлы, почти независимы.
Х Скорость сходимости равномерна относительно размеров системы.
Отметим, что распределения времен обслуживания в узлах сети могут быть произвольными, поэтому пуассоновская гипотеза применима в достаточно общей ситуации. ПГ предполагается справедливой для класса сетей, в которых внутренний поток на каждый узел N есть объединение потоков из многих других узлов, и каждый из этих потоков составляет лишь малую долю общего потока на узел N. Если пуассоновская гипотеза справедлива, то она дает возможность легко вычислять важные характеристики проектируемых сетей.
Основания для такого предположения естественны: поскольку входной поток есть сумма многих малых потоков, он близок к пуассоновскому. И благодаря случайной природе времен обслуживания выходящий поток из каждого узла должен быть более гладким чем полный входящий поток. Понятно, что пуассоновская гипотеза может быть верна лишь в термодинамическом пределе, когда число узлов стремится к бесконечности.
Она была доказана для симметричных замкнутых сетей на полносвязных графах в 21,31- 33 при довольно общих предположениях. В частности, вариация выходящего [ ] потока оказалась меньше, чем входящего, так что все потоки должны со временем сойтись к соответствующим постоянным значениям.
Нашей целью здесь является построение сети, удовлетворяющей всем перечисленным предположениям (что поток на любой узел есть бесконечная сумма малых потоков с других узлов), и обладающей, тем не менее, когерентными состояниями. Это означает, что состояния серверов эволюционируют синхронно и фаза данного сервера ведет себя (в термодинамическом пределе) как периодическая неслучайная функция, одна и та же для различных серверов.
Подчеркнем, что наша сеть демонстрирует эти когерентные состояния только если среднее число N требований на сервер (называемое в дальнейшем нагрузкой) велико. Для малых нагрузок имеет место сходимость к единственному состоянию равновесия. Этот аналог высокотемпературного поведения будет описан далее в 3.2.
Сеть строится из бесконечного числа экземпляров элементарной треугольной сети (описанной ниже). Единичная треугольная сеть =1 с N требованиями представляет собой эргодический марковский процесс скачков с непрерывным временем и конечным множеством состояний. Когда N растет, этот процесс сходится (в эйлеровском пределе) к 5-мерной жидкостной динамической системе , имеющей периодическую траекторию C, которая оказывается устойчивым (локальным) аттрактором. Составная система соответствует в некотором смысле склеенному семейству динамических систем . Мы докажем свойство синхронизации этого склеенного семейства , и это позволит нам строить когерентные состояния сети .
Сети M, составленные из M треугольных сетей , являются эргодическими. Их эволюция задается неприводимыми марковскими процессами на конечном числе состояний в непрерывном времени. Пусть M - инвариантная мера процесса M. При M последовательность марковских процессов M слабо сходится на конечных интервалах времени к некоторому предельному (нелинейному марковскому) процессу . Тогда, по известной теореме принадлежащей Р.З.Хасьминскому6 - любая точка накопления последовательности M является стационарной мерой процесса .
Специальная мера , описывающая поведение, предписанное пуассоновской гипотезой, тоже является стационарной мерой процесса . Если - глобальный аттрактор для , то, конечно, пуассоновская гипотеза справедлива. Доказательство пуассоновской гипотезы в работах 31,32 основано на этих рассуждениях. Существование точки [ ] накопления последовательности M, отличной от , было бы самым сильным контрпримером к пуассоновской гипотезе. Здесь мы доказываем более слабое утверждение о том, что не является глобальным аттрактором для процесса .
3.1.2. Основная сеть. Рассмотрим следующий пятимерный марковский процесс N. Он описывает замкнутую сеть с N требованиями. Эта сеть является замкнутым аналогом открытой сети, изученной в 13, в которой требования, покидая сеть, попадают [ ] в дополнительный узел O, из которого они возвращаются назад. Сеть состоит из трех узлов: O, A и B обслуживающих требования. Все времена обслуживания аTheorem 1,2,14 в Liggett, Thomas M. Interacting particle systems. Grundlehren der Mathematischen Wissenschlaften, 276. Springer-Verlag, New-York, 1985.
экспоненциальны, поэтому нам достаточно указать интенсивности обслуживания, правила эволюции классов требований и приоритеты. В узле O все требования имеют класс O.
Узел O обслуживает требования по принципу FIFO, с интенсивностью 0 = 3. После обслуживания требование переходит на узел A или B выбирая один из них с вероятностью. Если оно переходит на A, оно становится требованием класса A, в противном случае - класса B. Требование класса A обслуживается с интенсивностью =10, а затем переходит на узел B, получая класс AB. Там оно обслуживается с A интенсивностью = 2 и возвращается в узел O, получая класс O. Симметрично, AB требование класса B в узле B обслуживается с интенсивностью =10 и затем попадает B в узел A, где оно становится требованием класса BA,и обслуживается с интенсивностью = 2 в узле A,. после чего оно вновь возвращается в узел O, получая класс O.
BA Требования класса BA имеют в узле A абсолютный приоритет, аналогично, требования класса AB имеют в узле B абсолютный приоритет: если требование класса AB поступает на узел B в момент, когда на этом узле обслуживается требование класса B, обслуживание последнего прекращается и возобновляется лишь когда обслуживание всех требований класса AB будет закончено. Аналогично, требования класса BA прерывают обслуживание требований класса A в узле A. Такой выбор интенсивностей обслуживания очень важен, поскольку для него жидкостная модель этой сети имеет аттракторы - периодические жидкостные траектории.
N 3.1.3. М связанных процессов. Пусть M - марковский процесс, построенный из M копий сетиN, связанных по схеме среднего поля. Полное число требований в сети будет взято равным NM. В дальнейшем мы будем иногда опускать индекс N Среднеполевая сеть определяется следующим образом. Каждый узел Oi, i = 1,..., M, соединяется со всеми узлами Aj, Bj, j = 1,..., M, и каждое требование, покидающее узел Oi, поступает на один из 2M узлов Aj, Bj с одинаковой вероятностью. Интенсивность обслуживания на узле Oi такая же, как и выше, т.е. равна 0 = 3.
2M Аналогично, требования класса A на каждом из узлов Ai обслуживаются с интенсивностью =10, а затем выбирают один из узлов Bj с вероятностью и так AB M далее. Приоритеты в сети сохраняются: если узел Ai например, находится в состоянии, когда требования обоих классов - A и BA - присутствуют, то требования класса BA обслуживаются первыми, без задержки.
Конфигурация процесса определяется числом требований каждого класса на каждом из 3M узлов, то есть целочисленной точкой в пространстве ( 5M )+. В силу среднеполевой симметрии, множество конфигураций может быть факторизовано по произведению групп перестановок SM SM SM, и по-прежнему оставаться марковским процессом. Орбита симметрической группы соответствует семейству M целочисленных точек xi ( 5)+, некоторые из которых могут совпадать.
Нам будет удобно представлять эти конфигурации как атомарные меры M xi (16) { } xi M i=N Нам удобно считать эти рациональные атомарные меры принадлежащими + 1 + множеству M = M 5 всех вероятностных мер на 5 . Заметим, что каждая N N такая мера разлагается в произведение (O, A, B ) O A B O A B вероятностных мер на 1 = xO, [ ] [ ] [ ] { } соответственно 2 = xA, xBA и 2 = xB, xAB. Здесь через * мы обозначили различные { } { } 1 M проекции. Получаем O = x для некоторых (не обязательно различных) xi 1, i=1 i M 1 M 1 M i = 1,..., M, а также A = x ', B = x '', xi ', xi '' 2. Обозначим множество i=1 i i=1 i M M N всех таких мер через M. Состояние M нашего марковского процесса теперь можно M интерпретировать как элемент множества M M, т.е. как вероятностную меру на ( ) M N измеримом пространстве MM. Среди этих мер есть конфигурации процесса M, а именно, -меры m при mM, поэтому можно определить вложение M M M.
( ) M MM N N Тем не менее, даже если начальное состояние 0 процесса M оказывается такой ( ) M N мерой m, т.е. 0 M, то при любом положительном t мы можем лишь утверждать, ( ) M M N N что M (t)M M, тогда как M t M.
( ) ( ) M M N Пусть дана последовательность M 0 M (M ) начальных состояний ( ) M N N марковского процессаM, удовлетворяющая условию M 0 = m, при mM M, и ( ) M M пусть слабый предел = limM mM существует. Тогда слабые пределы (t) = limM M (t) существуют при любом t, и, кроме того, при любом t выполнено N (t) M. Это нелинейный марковский процесс, НМП, обозначаемый через . Процесс называется нелинейным, так как механизм эволюции из данной конфигурации зависит не только от этой конфигурации, но и от всей меры, из которой эта конфигурация была выбрана. Построенные ниже предельные НМП зависят от параметра N - количества клиентов в расчете на одну базовую сеть. Нашей целью является изучение зависимости от N, поэтому мы введем индекс N явным образом в наши обозначения. Таким образом, N N через (t) мы обозначаем состояния процесса .
Предельный НМП будет подробно описан в следующем разделе. Сформулируем теперь предварительную версию нашего основного результата.
N Теорема 13. Рассмотрим нелинейный марковский процесс , стартующий из N меры , являющейся атомарной мерой с атомом на векторе X (A, N) 5, у которого координата xA = N а все остальные координаты нулевые. Тогда мера (t) не стремится ни к какому пределу при t , если N достаточно велико.
Точнее, существует такая последовательность моментов времени t 'k , что N (t 'k ) X (A, N) >1-N, где N 0 при N . Здесь UN X A, N окрестность ( ) () ( ) UN точки X A, N радиуса N N, где N N 0 при N . В то же время, существует ( ) ( ) ( ) N другая последовательность t ''k , для которой (t ''k ) X (B, N) >1-N.
() UN N Другими словами, мера (t) колеблется во времени.
N Соответственно, состояния конечных сетей M (t) долгое время осциллируют прежде чем сойтись к своим пределам. Этот колебательный режим продолжается в течение интервала времени, длина которого расходится вместе с M. Различные N компоненты вектора M (t) осциллируют почти синхронно для больших M.
N 3.1.4. Нелинейный марковский процесс . Дадим кратко наглядную N интерпретацию нелинейного марковского процесса () аналогично тому, как мы описали нелинейный марковский процесс () в главе 2.
Сначала рассмотрим тройку независимых неоднородных по времени марковских процессов O (t), A (t) и B (t). Неоднородный процесс O (t) описывает эволюцию открытой системы (t) M 1 , в которую поступает переменный по времени пуассоновский поток требований типа O. Пусть A (t) - это неоднородный по времени процесс, описывающий эволюцию открытой системы (t) M 1 , в которую поступает пара пуассоновских потоков переменной интенсивности A(t),BA(t) требований типа A { } и BA соответственно. Как и ранее, требования типа BA имеют в узле A абсолютный приоритет. Аналогично, пусть B (t) - неоднородный во времени процесс, описывающий эволюцию открытой системы (t) M 1 , в которую поступает пара пуассоновских потоков переменной интенсивности B(t),AB (t) требований типа B и AB { } соответственно, причем требования типа AB абсолютный приоритет в узле B.
Зафиксируем случайные начальные состояния O (0) = O, A (0) = A и B (0) = B с суммарным средним числом требований равным 3 N. Обозначим через O (t), A (t), B (t) тройку вероятностных мер для неоднородных независимых { } марковских процессов O (t),A (t),B (t) в момент t. Обозначим через bA(t) среднюю по { } мере A(t) интенсивность окончания обслуживания требований класса A в узле A в момент t. Обозначим через bBA(t) среднюю по мере A(t) интенсивность окончания обслуживания требований класса BA в узле A в момент t. Аналогично, обозначим через bB (t) среднюю интенсивность по мере B (t) окончания обслуживания требований класса B в узле B в момент t. Обозначим через bAB (t) среднюю интенсивность по мере B (t) окончания обслуживания требований класса AB в узле B в момент t. Наконец, обозначим через bO (t) среднюю по мере O(t) интенсивность окончания обслуживания требований класса O в узле O в момент t. Наложим на интенсивности поступления требований в узлы O, A и B следующее дополнительное соотношение:
(t) = B (t) = bO (t) A (t) = bA(t) (17) AB BA(t) = bB (t) O (t) = bAB (t) + bBA(t) Эта система уравнений является одновременно неявной системой уравнений на N меры O (t), A (t), B (t). Обозначим через (t) = O(t) (t) (t) M где тройка { } { } A B O(t) = O(t), (t) = A(t), B (t) = B (t) и O (t), A (t), B (t) удовлетворяет { } A дополнительному соотношению (17). Имеет место следующая теорема, аналог Теоремы 9.
N N N N Теорема 14. Отображение: (t) (0) = задает динамическую ( ) N систему в пространстве M, причем среднее число требований для (t) не меняется по t и равно N.
Тем самым решение системы уравнений (17) существует и единственно и N определяет нелинейный марковский процесс . Эта теорема также доказывается при помощи принципа сжатых отображений. Следующий результат аналогичен Теореме 10.
N Он заключается в доказательстве сходимости при M марковских процессов M к N предельной динамической системе - нелинейному марковскому процессу . При любом t 0 определим линейный оператор T (t) : T t F = F t 0 = действующий на ( ) ( ) ( ) ( ) ( ) множестве функций от M. Обозначим через BM банахово пространство ограниченных N числовых функций на MM с нормой F = sup F (x),F BM.
N N Марковскому процессу M () с пространством состояний MM отвечает марковская N полугруппа TM (t) линейных операторов, действующих в пространстве BM. Именно, если F BM, то NN N N TM (t)F (x) = E M (t) M (0) = x x MM.
() ( ) (F ), N Теорема15. Для любого t 0 и любой функции F на M, непрерывной в слабой топологии, выполняется равенство N lim sup TM (t)F (vN ) - F vN (t) vN (0) = vN = 0. (18) ( ) M N N MM Сходимость здесь равномерна на каждом отрезке изменения t.
Доказательство этой теоремы также основано на использовании Теоремы ТроттераКуртца о сходимости марковских полугрупп.
Однако, в отличие от нелинейного марковского процесса (t) из 2.1, процесс N N (t) отнюдь не сходится к - неподвижной точке при больших значениях N. У N процесса (t) при больших N имеется нетривиальное инвариантное множество, окрестность в топологии Канторовича-Рубинштейна некоторого специального цикла C.
Доказательство этого утверждения весьма сложно и громоздко и составляет основное содержание 41. Опишем кратко конструкцию этого цикла. Рассмотрим t - [ ] ( ) жидкостную эволюцию единственного экземпляра треугольной сети 1(t) при M =1.
Сначала доказывается, что для этой жидкостной динамики имеется нетривиальный аттрактор - цикл C(t) 5.
+ Затем рассматривается жидкостная динамика M t для процесса M (t) при ( ) произвольном M. У этой жидкостной динамики имеется следующее замечательное свойство синхронизации: интенсивности входных потоков жидкостей одинаковых классов в одноименные узлы совпадают между собой в любой момент времени. Это свойство следует из самой конструкции жидкостного предела и из того факта, что каждое требование фиксированного класса после окончания обслуживания выбирает последующий узел из множества узлов соответствующего типа равновероятно. Отсюда следует, что начиная с некоторого момента жидкостные траектории процесса M t ( ) синхронизируются: количества одноименных жидкостей во всех одноименных узлах M с некоторого момента T = T (M ) совпадают, после чего жидкостная эволюция для процесса M t становится неотличима от жидкостной эволюции t Следовательно, ( ) ( ).
жидкостная эволюция для процесса M t также имеет аттрактор - цикл C(t), лежащий ( ) на 5-мерной диагонали пространства 5M.
+ Построив нелинейную жидкостную динамику t для нелинейного марковского ( ) N процесса (t) удается доказать существование аттрактора - предельного цикла и для этой жидкостной динамики. Доказав сходимость в эйлеровском скейлинге при N N процесса (t) к жидкостной динамике t получим, что при больших значениях N ( ) N N траектория (t) процесса (t) никогда не выходит из малой окрестности цикла C(t), что и составляет утверждение Теоремы 13.
3.2. Справедливость пуассоновской гипотезы. Замкнутые сети при малой нагрузке.
3.2.1. Постановка задачи. Долгое время предполагалось, что справедливость Пуассоновской гипотезы является общим свойством всех больших сильно связных сетей.
Она была доказана для замкнутой симметричной сети - полносвязного графа в 21,31- 33,35. Однако были найдены и контрпримеры (см. 38, где рассматривались [ ] [ ] специфические распределения времени обслуживания, и особенно 41, где была [ ] построена сеть с экспоненциальными временами обслуживания, для которой Пуассоновская гипотеза перестает выполняться при высоких нагрузках). Мы предполагаем, что ситуация здесь аналогична ситуации в статистической механике, где все модели ведут себя сходно при высоких температурах, тогда как при низких температурах некоторые из них демонстрируют фазовые переходы. В симметричных сетях массового обслуживания аналогом (обратной) температуры является средняя нагрузка на сервер - , и пример, приведенный в 41, есть пример такого фазового [ ] перехода (первого рода), когда соответствующая бесконечная система имеет множественные состояния равновесия. Здесь мы развиваем эту аналогию, демонстрируя, что при весьма общих предположениях Пуассоновская гипотеза выполняется для замкнутых симметричных сетей общего вида в средне-полевом приближении, если нагрузка на каждый узел мала.
Пусть G = (V, E) - конечный граф. Мы интерпретируем граф G как сеть, состоящую из серверов, обслуживающих требования. Таким образом, мы предполагаем, что граф G наделен некоторыми дополнительными структурами. Во-первых, на каждый сервер V могут приходить требования различной природы: с каждым сервером мы cC(). Таким образом мы ассоциируем (конечное) множество классов - или цветов -{ } определяем непересекающееся объединение V = V C() всех возможных классов требований. Мы соединяем пару (1,c1) с парой (2,c2), где ci C(i ), с помощью направленнго ребра, e E, если (1,2) является ребром в E, и если, кроме того, требование класса c1 обслуживается сервером 1 и в результате попадает на сервер 2 как требование класса c2.
Пока что мы просто определили новый (больший и направленный) граф G = (V, E).
Далее мы должны задать времена обслуживания. Мы будем предполагать их экспоненциально распределенными с интенсивностями (,c) > 0.
Последняя информация, которая понадобится для определения системы, касается переходной матрицы вероятностей P = 1,c1, 2,c2 на G. Величина ( ) ( ) {P } P (1,c1),(2,c2) - это вероятность того, что требование класса c1 на узле 1 попадет [ ] затем на узел 2 как требование класса c2.
Мы хотим также наложить на нашу элементарную сеть (G, ) условие связности:
Условие 1. Эргодичность матрицы P. Рассмотрим Марковский процесс G с непрерывным временем, отвечающий Случаю Единственнго Требования. Это означает, что в нашей сети находится лишь одно требование. Изначально он находится на некотором сервере и имеет цвет c C(). С течением времени требование меняет свое местоположение и цвет случайным образом с интенсивностями, задаваемыми функциями (,), и переходными вероятностями P. Мы хотим, чтобы этот Марковский процесс (с непрерывным временем, на конечном числе состояний) был эргодическим. Это эквивалентно эргодичности Марковской цепи, определяемой матрицей P.
В тех сетях, которые мы здесь рассматриваем, будет циркулировать большое число требований, поэтому мы должны объяснить, что происходит, когда несколько требований приходят на обслуживание в тот же самый узел. Здесь мы опишем достаточно общую ситуацию. Предположим, что на сервере в момент времени t имеется очередь x = c1,c2,...,ck требований ci C(). Это означает, что эти требования пришли на узел { } до момента t, и по-прежнему находятся там в момент t, ожидая обслуживания. Они записаны в очередь в порядке их поступления. Величина k = k(x ) называется длиной очереди (на сервере в момент t ). Дисциплина R() - это правило i (*) для сервера , которое сопоставляет каждой непустой очереди x индекс 1 i (x ) k т.е. индекс требования в очереди x, обслуживание которого происходит в момент t. Как только обслуживание этого требования завершается и оно покидает сервер, очередь x превращается в очередь x i (x ),ci ( x ) c1,c2,...,ci ( x )-1,ci ( x )+1,...,ck, (19) { } { } так что k x i (x ),ci (x ) = k(x ) -.
{ } () Например, сервер может обслуживать требования просто в порядке их поступления, то есть i (x ) 1. Эта дисциплина FIFO Мы будем изучать достаточно общий класс дисциплин, с двумя ограничениями.
Первое из них состоит в том, что сервер не может простаивать, если на нем есть требования, ожидающие обслуживания. Такие дисциплины называются консервативными.
Вторым ограничением является следующее свойство монотонности. Пусть t1 t2 tk c1,c2,...,ck,... - последовательность прихода требований на узел , где ti - момент прихода i -го требования. Пусть нам известно время, необходимое для обслуживания каждого требования. Тогда дисциплина R() позволяет определить функцию N (t), значением которой является длина очереди в момент t 0. Рассмотрим теперь другую последовательность поступлений, отличающуюся от предыдущей на одно дополнительное t1 t2 i i+1 tk требование c : c1,c2,...,cit,ctcit,...ck,... где ti < t < ti+1. При этом Nc(t) - длина очереди +c изменится. Мы хотим, чтобы N (t) N(t) для всех t > 0. Этим свойством обладает большинство естественных дисциплин обслуживания.
Отметим, что допускается ситуация, когда обслуживание требования c прерывается, когда поступает требование с более высоким приоритетом. Обслуживание требования c затем возобновляется в соответствии с правилом приоритетов R().
3.2.2 Графы типа среднего поля. Сопоставим теперь графу G = (V, E) последовательность G(G) = G G(G) ... G (G) ... графов, конструируемых 12 M следующим образом. Для любого M рассмотрим сначала непересекающееся объединение i M экземпляров Gi = (V, Ei ) графа G, i = 1,..., M. Полученный граф G = Vi,Ei имеет ( ) M i множество вершин VM = M V, т.е. всех вершин этих M экземпляров графа G.
i=Определим теперь множество ребер графа EM с множеством вершин VM. Мы будем i i i j считать пару (1,2j ) VM ребром графа EM 1 V,2j V,i, j =1,..., M, если и только если две вершины 1,2 V соединены ребром e E. Таким образом, каждое ребро графа G порождает ровно M ребер графа EM. Других ребер в графе EM нет.
Например, если граф G состоит из единственной вершины , соединенной с самой собой посредством петли, то граф G (G) - полный граф с M вершинами и M дополнительной петлей у каждой вершины.
Теперь мы определим средне-полевые графы G (G) точно таким же образом, как M выше. Конечно, у этих графов есть естественная ориентация, унаследованная от графа G.
Все функции интенсивности сохраняются, а переходная матрица PM определяется как i PM 1,c1, 2j,c2 = P (1,c1),(2,c2).
[] ( ) ( ) M Всюду в дальнейшем мы фиксируем элементарную сеть (G, ), и изучаем соответствующие модели среднего поля G (G), населенные N = требованиями.
M M Параметр мы назовем нагрузкой. Таким образом, для каждого M мы строим эргодический марковский процесс на сети G (G) с N требованиями. Обозначим этот M процесс M, а через M обозначим его инвариантную меру. Нас будут интересовать асимптотические свойства этих стационарных состояний M при M , а также свойство сходимости состояний M (t) процесса M в момент t к пределуM при t .
Говоря неформально, пуассоновская гипотеза для средне-полевых сетей G (G) M утверждает о поведении мер M (t) при больших M следующее: если начальное состояние M (0) выбрано подходящим образом, что означает, что длины начальных очередей в каждом узле не превосходят некоторой константы K, то через некоторое время T (K ), не зависящее от M.
Х Все M V серверов нашей сети становятся почти независимыми, т.е. мера M (t) близка к мере-произведению на множестве VM ;
Х На каждом узле VM процесс M (t) выглядит так, как будто бы входные потоки всех возможных классов требований на являются независимыми пуассоновскими потоками Pc,c C() с постоянными интенсивностями c (зависящими только от , графа G и функции, но не от M или t ). Эти требования затем образуют очередь на и обслуживаются согласно правилу R(), а затем покидают сервер.
c Обозначим стационарное состояние такого узла через {,cC()}. Эквивалентно, c {,cC()} есть предельное состояние следующего марковского процесса с C( непрерывным временем на = + ) :
C( Этот процесс начинается из пустого состояния + ), требования класса c C() поступают в моменты времени образующие пуассоновский поток интенсивности c, последовательность их обслуживания задается правилом R, времена обслуживания имеют экспоненциальное распределение с интенсивностями (,c) > 0, после обслуживания требования покидают сервер.
В этом случае мы очевидным образом получаем соотношения c ' = (20) [ ] cP (,c),( ',c '), V cC( ) где c 'C( '). Они определяют множество = c,c V интенсивностей пуассоновских { } входящих потоков с точностью до общего множителя .
Отметим, что ожидаемое число требований, N = N( ), имеющихся в сети G в c состоянии {,cC( )}, как функция , т.e. N( ) непрерывно и строго возрастает по V , если 0.
Поэтому, в силу эргодичности матрицы P, интенсивности однозначно определены соотношениями (20), дополненными уравнением N( ) = . Обозначим стационарное распределение очередей, соответствующее упомянутым пуассоновским входным потокам , через :
c,cC( ) = (21) { }.
V Для упрощения обозначений мы ограничимся в дальнейшем случаем дисциплины FIFO с приоритетами. Для ее описания мы снабдим каждое множество цветов C( ) отношением приоритета являющееся линейным упорядочением, и скажем, что требование класса c1 имеет более высокий приоритет, чем требование c2, если и только если c2 c1. В каждый момент времени, когда на сервере есть несколько требований, ожидающих обслуживания, обслуживается требование с самым высоким приоритетом.
Если имеется несколько таких требований, то они обслуживаются в порядке их поступления на сервер. Приоритеты соблюдаются в такой степени, что даже если требование с более высоким приоритетом поступает в момент, когда требование с низким приоритетом находится на обслуживании, то обслуживание последнего приостанавливается и возобновляется только когда вновь пришедшее требование покидает узел. Преимуществом такой дисциплины является то обстоятельство, что C( очередь на сервере полностью описывается вектором из = + ). В противном случае наши доказательства могут быть проведены аналогичным образом, однако здесь мы этого не будем делать.
Марковские процессы M (t) и стационарные меры M определенные выше, являются мерами на пространстве конфигураций нашей системы, т.е. на M, где = = V. Пусть (x1,..., xM )M - случайная конфигурация нашего процесса.
+ V 1 M Рассмотрим случайную меру x M (). В силу симметрии нашей сети i i=M относительно группы перестановок SM, описанные процессы на мерах по-прежнему марковские. Это позволяет нам интерпретировать все меры M (t) и M как меры на одном и том же пространстве M (). Они совпадают с частотами данного состояния на данном сервере в сети G (G). Поэтому меры M (t) и M становятся элементами M пространства M M (). Тем не менее, предельная мера (t)M M () оказывается ( ) ( ) атомарной мерой и, таким образом, может быть записана как (t) = при M ().
Нарушая немного строгость обозначений, мы будем отождествлять меру (t)M M () с этой мерой M (), и скажем, что (t)M (). Процесс (t) - ( ) это Нелинейный Марковский Процесс (НМП, см. 21,31- 33.) [ ] В принятых обозначениях предыдущие утверждения означают, что сходимость M (t) M равномерна по M, и что M при M . Меру мы будем называть динамикой Пуассоновской гипотезы.
3.2.3. Основной результат. Рассмотрим элементарную сеть (G, ), связную в смысле условия 1. Мы предположим, что на каждом сервере V задана консервативная дисциплина обслуживания R(), определяющая порядок, в котором обслуживаются требования из очереди. Рассмотрим теперь последовательность M марковских процессов на сетях G (G), M =1,2,..., населенных N = требованиями. Пусть M - M M инвариантная мера процесса M.
Теорема 16. Сходимость. Существует значение = (G,, P) > 0, такое, что для любого < (G,, P) слабый предел limM M существует и равен мере .
В нашем следующем утверждении речь идет о сходимости к стационарным состояниям M. Тут мы должны указать класс начальных состояний наших марковских процессов.
Теорема 17. Экспоненциальная скорость сходимости. Пусть марковский процесс M стартует из состояния M (0), обладающего тем свойством, что в каждом узле $ VM длина очереди k = k(,t = 0) удовлетворяет уравнению (22) exp{k }dM (0) K, где > 0, K - некоторые константы, также зависящие от G,, P. Пусть < (G, ).
( ) Тогда, для любой локальной функции f, получаем fdM (t) - fdM f exp, где константа = (, K) не зависит от M.
{-t } В главе 3 мы называем функцию локальной, если она зависит лишь от состояний конечного числа серверов. Здесь мы приводим доказательства лишь для одной сети специального вида, построенной в 41. Основное утверждение работы 41 заключается в [ ] [ ] том, что для этой сети утверждение Теоремы 17 не выполняется при высоких значениях нагрузки , так что здесь мы действительно наблюдаем эффект фазового перехода. Как это обычно бывает в задачах статистической механики, все системы при высокой температуре (при малых ) ведут себя схожим образом, и все могут изучаться одним и тем же способом. Для сетей ситуация та же самая, и наши результаты легко могут быть обобщены на системы общего вида, описанные выше. Напротив, системы при низких температурах (при больших ) должны рассматриваться индивидуально, и их поведение может быть весьма разнообразным.
Основные результаты.
1. Разработан метод нахождения условий эргодичности открытых коммуникационных сетей - метод жидкостного предела.
2. Опровергнута гипотеза о существовании стабильного режима при номинальных нагрузках меньших единицы для открытых коммуникационных сетей.
3. Разработан метод термодинамического предельного перехода для симметричных замкнутых телекоммуникационных сетей. С его помощью доказана пуассоновская гипотеза Клейнрока-Боровкова для открытых симметричных сетей на полных графах.
4. Опровергнута пуассоновская гипотеза Клейнрока для общих симметричных коммуникационных сетей со многими типами требований и многими типами узлов.
5. Доказана пуассоновская гипотеза Клейнрока для симметричных коммуникационных сетей со многими классами требований и многими типами узлов при малых нагрузках.
Список литературы.
1. Рыбко А.Н., Пропускная способность сетей связи и эргодичность марковских процессов со счетным числом состояний// Proceedings of the Third Czechoslovak - Soviet - Hungarian Seminar of Information Theory, Liblice. 1980. C. 71-80.
2. Рыбко А.Н.. Стационарные распределения марковских процессов, описывающих работу коммуникационных сетей// Пробл. передачи информации. 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. Рыбко А.Н.. Условия существования стационарного режима для двух классов коммуникационных сетей// Пробл. передачи информации. 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. 94100.
6. Рыбко А.Н., Михайлов В.А.. Область пропускной способности сетей с коммутацией каналов и очередями// Пробл. передачи информации. 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>
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. Bacelli F., Karpelevich F.I., KelТbert M.Y., Puhalskii A.A., Rybko A.N., Suhov Y.M. A mean field limit for a>
13. Рыбко А.Н., Столяр А.Л. Эргодичность случайных процессов, описывающая работу открытых сетей массового обслуживания// Пробл. передачи информации. 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 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.
19. Пухальский А.А., Рыбко А.Н. Неэргодичность сетей массового обслуживания при нестабильности их жидкостных моделей// Пробл. передачи информации. 2000. Т. 36, № 1. С. 26-46.
20. 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.
21. Карпелевич Ф.И., Рыбко А.Н. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе// Пробл. передачи информации. 2000. Т. 36, № 2. С. 69-95.
22. 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.
23. 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.
24. 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.
25. 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.
26. Rybko A., Shlosman S. Poisson hypothesis for large information networks: the study of non-linear Markov processes//Abs. of Intern. Conf. УKolmogorov and Contemprorary MathematicsФ, Moscow. June 2003. М:, Изд. ЦПИ, 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 A., Shlosman S. Poisson hypothesis for information networks (A study in non-linear Markov processes) I Domain of Validity// /pdf/04/04066.110v1.pdf. 2004. P. 1-77.
30. Rybko A., Shlosman S. Poisson hypothesis for information networks II.Cases of violation and phase transitions//
2004. P.1-27.
31. 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.
32. Rybko A., Shlosman S. Poisson hypothesis for information networks (a study in non-linear Markov processes). PartII// Moscow mathematical journal. 2005. V. 5, N. 4, P. 927-959.
33. Рыбко А.Н., Шлосман С.Б. Пуассоновская гипотеза: комбинаторный аспект// Пробл.
передачи информации. 2005. Т. 41, № 3. С. 51-57.
34. Rybko A., Shlosman S., Vladimirov A. Self-averaging property of queuing systems// 2005. P. 1-18.
35. Владимиров А.А., Рыбко А.Н., Шлосман С.Б. Свойства самоусреднения систем массового обслуживания// Пробл. передачи информации. 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// 2007. 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.1, P.159-180.
39. Rybko A., Shlosman S., Vladimirov A. Absence of breakdown of the Poisson hypothesis. I Closed networks at low load // 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-Rocquencourt. April 2008. P. 13.
41. 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.
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.
ИППИ РАН, С. 149-156.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям