Введение к работе
Актуальность темы. Разработка математических методов, предсказывающих значения стационарных характеристик узлов сети при выбранных допустимых нагрузках, является актуальной темой в современной теории случайных процессов, описывающих поведение телекоммуникационных сетей. Одной из основных проблем является, также, и само нахождение условий существования стабильного режима работы открытых сетей, или, что то же самое, условий эргодичности марковских процессов, описывающих функционирование таких сетей, поскольку при создании и эксплуатации телекоммуникационных сетей необходимо гарантировать их стабильную работу.
Математическая теория, описывающая функционирование телекоммуникационных сетей, является динамично развивающейся областью теории случайных процессов. Она стала развиваться лишь во второй половине 20-го века. Первоначально, развитие теории осуществлялось (когда это было возможно) методами, имеющимися в более старой и развитой области - классической теории массового обслуживания. Так, Р.М.Лойнес, доказав фундаментальную теорему об эргодичности случайного процесса, описывающую поведение общей модели очереди G G |l |со при нагрузке меньшей единице, немедленно
обобщил этот результат на случай простейшей коммуникационной сети - линейной последовательности серверов.
Другим направлением исследований первоначально было нахождение и изучение точно решаемых моделей - таких сетей, для которых их инвариантные меры явно выражаются через инвариантные меры отдельных изолированных серверов - узлов, составляющих сеть. Это направление началось с обнаружения сетей Джексона. Инвариантная мера состояния для сетей Джексона является произведением инвариантных мер отдельных изолированных узлов сети. В дальнейшем были найдены различные примеры сетей, для которых инвариантная мера находилась явно и, как правило, строилась в виде меры - произведения инвариантных мер отдельных изолированных узлов сети (product form networks).
Объяснение появления таких примеров сделал Ф.Келли. Он создал теорию квазиобратимых марковских процессов и предъявил достаточные условия, которым должны удовлетворять переходные вероятности марковских процессов, задающих работу сети, для того, чтобы инвариантные меры являлись мерой - произведением инвариантных мер изолированных узлов сети. Оказалось, что условия квазиобратимости чрезвычайно жесткие, - при малом изменении параметров (малом изменении распределений интервалов между поступлениями требований, малом изменении распределений времен обслуживания и малом изменении дисциплин обслуживания в узлах сети), свойства квазиобратимости исчезают. Исчезает и надежда на получение явных аналитических выражений для инвариантных мер для сетей общего положения. Тем не менее, и до настоящего времени иногда обнаруживаются новые нетривиальные точно решаемые модели - примеры таких сетей.
В связи с невозможностью использования явных аналитических методов стали развиваться качественные математические методы анализа случайных процессов, описывающих поведение сложных коммуникационных сетей. Это направление было основано в работах Р.Лойнеса, В.А.Малышева, Р.Л.Добрушина, А.А.Боровкова, П.Р.Кумара, В.Анатхарама, А.Столяра, Ф.Келли, Р.Ш.Липцера, Д.Харрисона, Д.Штояна, Р.Ясногородского, Р.Шассбергера, В.Калашникова, А.Мандельбаума, Ф.И.Карпелевича, и в настоящее время продолжает свое развитие в работах М.Брэмсона, Д.Дая, М.В.Меньшикова, С.Г.Фосса, Д.А.Коршунова, Ю.Барышникова, С.Б.Шлосмана, А.Ю.Веретенникова, А.А.Владимирова, Ш.Мейна, А.А.Пухальского, А.Д.Маниты, Р.Уильяме, Н.О'Конелла, Н.Д.Введенской, Л.Г.Афанасьевой, Е.А.Печерского, А.А.Замятина, Г.Файоля, Ф.Бачелли, Ж.Маресса, Т.Константопулоса, Ю.М.Сухова и в
работах многих других специалистов. Следует отметить особый инженерный подход и вклад в создание коммуникационных сетей, осуществленный Л.Клейнроком в его книгах. Автору особенно близка идея, неоднократно высказанная Р.Л.Добрушиным, заключающаяся в том, что идеология и многие методы статистической механики, как более старой и развитой области науки, могут продуктивно использоваться при анализе свойств больших телекоммуникационных сетей.
Первым вопросом математической теории открытых сетей со многими классами требований представляется проблема нахождения условий существования и единственности стабильного режима (эргодичности) таких сетей. Долгое время считалось несомненным фактом, лишь требовавшим строгого математического доказательства следующее утверждение, сформулированное Р.Л.Добрушиным, являющееся естественным обобщением теоремы Лойнеса об эргодичности классической системы массового обслуживания, состоящей из единственной очереди к одному серверу.
Определим номинальную нагрузку рт на произвольный узел т сети, как среднее
значение за единицу времени суммарных длин тех требований, которым предстоит обслуживаться в узле т. Гипотеза, дающая условия эргодичности открытых сетей, заключалась в утверждении, что если для каждого узла т сети номинальная нагрузка рт<\, то случайный процесс, описывающий работу сети, эргодичен и среднее число
требований, циркулирующих в сети в растущие моменты времени, не стремится к бесконечности.
В [ІЗ] эта гипотеза была опровергнута, - было доказано, что уже для простой сети,
состоящей из 2-х узлов, в которой циркулируют 2 класса требований, при некоторой приоритетной дисциплине даже при экспоненциально распределенных независимых временах обслуживания и при пуассоновских входных потоках требований, утверждение гипотезы не верно. Чтобы исследовать поведение соответствующего однородного марковского процесса со счетным числом состояний был построен жидкостный предел, возникающий в Эйлеровском скейлинге. Похожая идея для изучения эргодичности случайных блужданий в положительных октантах ранее использовалась В.А.Малышевым и его учениками . Однако, в силу имеющихся дополнительных инвариантов, связанных с условием консервативности дисциплин обслуживания в узлах, анализ поведения траекторий жидкостного предела для сетей допускает «явное» описание. Векторное поле «детерминированной» жидкостной динамики явно строится как в конечномерном случае (приоритетные дисциплины), так даже и в бесконечномерном случае (дисциплины FIFO, LIFO), и это дает возможность рассматривать произвольно распределенные (а не только экспоненциально распределенные) времена обслуживания требований и общие входные потоки.
Метод жидкостного предела, разработанный в [13], стал важным инструментом
исследования условий стабильности различных сетей массового обслуживания. Естественно возникают следующие проблемы:
-
доказательство сходимости к жидкостному пределу в Эйлеровском скейлинге для достаточно широкого и общего класса сетей массового обслуживания;
-
доказательство того факта, что если все траектории жидкостного предела, начинающиеся из непустых жидкостных состояний, попадают за конечное время (зависящее от начального состояния) в пустое состояние, то первоначальный случайный процесс, описывающий поведение сети, эргодичен;
-
доказательство свойств отсутствия эргодичности или невозвратности случайного процесса при условии, что все жидкостные траектории, стартующие из малой окрестности некоторого непустого начального состояния, ведут себя достаточно регулярно и при этом растут к бесконечности.
1 Malyshev A.V. Networks and dynamical systems. Adv. Appl. Prob. 1993, V. 25, P. 140-175
Первые два утверждения были доказаны независимо в работах А.Столяра и Д.Дая. Третье утверждение было доказано в [19]. Доказательство основано на использовании
методов теории больших уклонений.
Другим предельным переходом, важным для анализа стохастических процессов, моделирующих большие сети массового обслуживания, является термодинамический предельный переход, при котором число узлов в сети стремится к бесконечности. По аналогии с идеями статистической механики, естественно ожидать, что многие свойства бесконечной сети, возникающей в термодинамическом пределе, окажутся доступнее для математического анализа, чем аналогичные свойства больших конечных сетей.
Еще в 70-х годах Л.Клейнрок предложил следующую инженерную концепцию, -гипотезу для приближенного вычисления стационарных распределений больших сложных сетей, названную пуассоновской гипотезой. Пусть имеется огромная сеть, состоящая из очень большого числа узлов, причем маршруты требований таковы, что на каждый узел поступает большое число малых потоков требований, идущих из различных узлов сети. Пусть также известно, что случайный процесс, моделирующий работу такой сети, стации-онарен и эргодичен. Для приближенного вычисления инвариантной меры этого процесса предлагается следующий простой метод. Потоки требований, поступающие на каждый фиксированный узел, заменяются на пуассоновские потоки постоянной интенсивности. При этом предполагается, что потоки, поступающие на различные узлы сети, независимы. В этих предположениях возможно явное нахождение инвариантной меры, поскольку работа сети распадается на работу независимых систем массового обслуживания, для нахождения стационарных характеристик которых обычно имеются явные аналитические формулы. Ясно, что строгий смысл этой гипотезе можно придать лишь в термодинамическом пределе для последовательностей таких сетей с растущим числом узлов, для которых интенсивности потоков, поступающих из узла А в узел В, стремятся к нулю для произвольных пар А и В. А.А.Боровков уточнил и упростил задачу, предложив для начала доказать пуассоновскую гипотезу в простейшем нетривиальном случае: для термодинамического предела замкнутых симметричных сетей на полном графе с фиксированным отношением числа требований к числу узлов и с произвольно одинаково распределенными, независимыми в совокупности последовательностями времен обслуживания требований в узлах. Р.Л.Добрушин подчеркивал связь этой проблематики с исследованием свойств термодинамического предела для моделей среднего поля в статистической физике, что оказалось очень важно для доказательства пуассоновской гипотезы.
Цель работы.
-
Нахождение условий стабильности открытых телекоммуникационных сетей.
-
Исследование свойств жидкостных траекторий, возникающих в Эйлеровском пределе для телекоммуникационных сетей.
-
Исследование условий асимптотической независимости для симметричных сетей большого объема.
-
Исследование свойств нелинейных марковских процессов, возникающих в термодинамическом предельном переходе для симметричных сетей.
Методы исследования. В наших исследованиях использованы методы теории вероятностей и теории случайных процессов, в частности теории больших уклонений, теории нелинейных марковских процессов; методы функционального анализа, в частности теории марковских полугрупп; методы теории нелинейных динамических систем.
Научная новизна. Для широкого класса марковских процессов, описывающих работу телекоммуникационных сетей, разработан новый метод исследования, - метод жидкостного предела. Построенные жидкостные пределы для открытых телекоммуникационных сетей позволили находить условия эргодичности марковских процессов, исследуя свойства их жидкостных траекторий.
Впервые исследован предельный случайный процесс, возникающий в результате термодинамического предельного перехода, для замкнутых симметричных сетей на полном графе. Эргодические свойства указанного предельного нелинейного марковского процесса позволяют проверять справедливость пуассоновской гипотезы для симметричных замкнутых сетей массового обслуживания.
Разработан новый метод исследования нелинейных марковских процессов, возникающих в термодинамическом пределе для общих симметричных сетей. Этот метод, - метод исследования предельной нелинейной жидкостной динамической системы, возникающей в Эйлеровском пределе, позволил обнаружить новое явление спонтанной синхронизации и опровергнуть пуассоновскую гипотезу для таких сетей при больших нагрузках.
Теоретическая и практическая ценность. Работа носит теоретический характер. В диссертации разработаны новые методы исследования, которые позволили получить новые результаты и доказать утверждения, существовавшие ранее в виде гипотез. В частности, опровергнута гипотеза об условиях эргодичности открытых коммуникационных сетей. Построенный пример, опровергающий эту гипотезу, известен теперь как пример Рыбко - Столяра. Для анализа свойств данного примера и для нахождения условий эргодичности сложных открытых сетей со многими классами требований разработан новый метод исследования, - метод жидкостного предела для таких сетей. Используя этот метод, получены новые общие критерии неэргодичности и невозвратности открытых сетей, - доказаны общие теоремы о неэргодичности и невозвратности открытых сетей при условии, что все жидкостные траектории, стартующие из малой окрестности некоторого непустого начального состояния, ведут себя достаточно регулярно и при этом растут к бесконечности.
Доказана справедливость пуассоновской гипотезы для симметричной замкнутой сети на полном графе. Доказательство основано на обнаружении специального свойства самоусреднения для неоднородных процессов M(V)|G|l и на доказательстве сходимости
нелинейного марковского процесса, возникающего в термодинамическом пределе к глобальному аттрактору, - неподвижной точке в пространстве мер, соответствующей утверждению пуассоновской гипотезы.
Найдены контрпримеры к пуассоновской гипотезе для замкнутых симметричных сетей с несколькими типами узлов и несколькими классами требований в условиях большой нагрузки. Эти контрпримеры основаны на обнаружении нового явления спонтанного резонанса при большой нагрузке для таких сетей.
Доказана справедливость пуассоновской гипотезы для марковских замкнутых сетей с несколькими классами требований и несколькими типами узлов при малой нагрузке.
Результаты и методы работы могут быть использованы в теории вероятностей и теории случайных процессов и, кроме того, могут иметь приложения для прикладных исследований и проектирования больших коммуникационных сетей. Так, во многих современных исследованиях стохастических сетей, жидкостные модели занимают центральное место, например, в вопросе выбора параметров узлов сетей для обеспечения их стабильной работы и в вопросе оптимального управления потоками в таких сетях.
Апробация результатов и публикации. Результаты работы неоднократно докладывались на научных семинарах под руководством Р.Л.Добрушина, Р.А.Минлоса и М.С.Пинскера в ИППИ им.А.А.Харкевича РАН (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 наименования.
