Моделирование сетей обслуживания методом слабой регенерации

Цель работы — разработка методов моделирования сетей обслуживания на основе слабой регенерации.

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

Система массового обслуживания (узел) характеризуется потоком заявок (клиентов), нуждающихся в обслуживании и числом каналов (приборов) обслуживания. Сеть обслуживания представляет собой объединение взаимодействующих систем массового обслуживания. Для исследования стационарных характеристик систем (сетей) массового обслуживания, главной целью которого является выбор наиболее разумной конфигурации системы (сети), обычно изучаются математические модели систем (сетей) массового обслуживания. Изучением таких моделей занимается теория массового обслуживания [4, 8, 12]. В дальнейшем, для краткости, под системой (сетью) массового обслуживания мы будем понимать их математические модели, как это принято в теории массового обслуживания.

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

В данной работе рассматриваются в основном процессы с дискретным временем.

Актуальность тематики обусловлена интенсивным развитием коммуникационных сетей. Несмотря на быстрое развитие теории массового обслуживания, широко изучены только так называемые Марковские сети, обладающие свойством мультипликативности [4, 8, 12]. Это свойство заключено в теореме Джексона и ее обобщениях, которые содержат достаточные условия мультипликативности предельного распределения векторного процесса очереди в узлах сети. Другими словами, при этих условиях существует предельное распределение процесса, равное произведению маргинальных распределений, относящихся к отдельным узлам. Такие сети, допускающие мультипликативность, называются сетями Джексона. Достаточным условием мультипликативности является обратимость во времени марковского процесса, которая выражается в форме уравнений детального баланса, связывающих вероятности перехода и предельное распределение данного процесса. При этом предельное распределение числа заявок в каждом узле можно выписать в явном виде.

Однако, поведение многих реальных систем нельзя описать марковскими процессами (входной поток не является пуассоновским, а время обслуживания имеет закон распределения, отличный от экспоненциального), кроме того, если сеть и можно описать марковским процессом, то он может быть очень сложным (большой размерности), что приводит к невозможности использования хорошо разработанных методов классической статистики [9]. Для анализа поведения таких сетей можно использовать регенеративный подход [68]. При определенных (весьма слабых) условиях существует предельное распределение регенерирующего процесса, при этом значения процесса делятся на циклы регенерации, которые между собой независимы. Моменты начала нового цикла, называются моментами регенерации [6, 7]. Эти моменты образуют вложенный процесс восстановления. Такая регенерация называется сильной или регенерацией по Смиту [7, 68]. Класс сильно регенерирующих процессов является хорошо изученным. Примерами таких процессов являются процессы, описывающие поведение многоканальных систем типа GI/GI/m [51].

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

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

Метод слабой регенерации базируется на методе обновляющих событий Боровкова [3]. Кроме того, он использует метод расщепления (при анализе цепей Маркова, возвратных по Харрису). Класс слабо регенерирующих процессов гораздо шире и до настоящего времени исследован недостаточно подробно. В применении к процессам обслуживания известны результаты только для многоканальных систем типа GI/GI/m и тандемов [10, 49]. Вышеуказанные системы и сети являются частными случаями ациклических сетей типа Джексона. Сеть типа Джексона представляет из себя несколько узлов обслуживания с входным потоком восстановления, каждый узел имеет несколько каналов обслуживания, заявки в узел поступают из других узлов и внешнего входного потока [24]. В данной работе выявлен класс событий, которые являются обновляющими для тандемной сети GI/GI/ш •/GI/mN и ациклической сети типа Джексона, что позволяют строить моменты слабой регенерации.

Параллельно с теоретическими исследованиями регенеративный метод был успешно применен к статистическому анализу сетей обслуживания. Здесь надо отметить работы [5, 9, 38, 63, 6], где для исследования многоканальных систем типа GI/GI/m и тандемов используется подход, основанный лишь на сильной регенерации. В этой связи методом имитационного моделирования было исследовано поведение тан-демных сетей GI/GI/m •/GI/tun, на основе и сильной, и слабой регенерации.

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

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

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

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

Для того, чтобы выяснить как влияют изменения вероятности сильной регенерации и числа узлов сети при выполнении условия эффективности слабой регнерации на время доверительного оценивания с заданной точностью были проведены имитационные эксперименты по моделированию тандемных сетей GI/GI/m —>•.—"> 'jGljm^. Кроме того, для того, чтобы оценить как изменяется длина доверительного интервала в результате применения методов одинаковых и противоположных случайных чисел на основе слабой регенерации были проведены имитационные эксперименты и получены доверительные интервалы для оценки среднего времени ожидания.

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

На защиту выносятся получены следующие основные результаты:

1. Для сетей типа Джексона выявлен класс событий, являющихся обновляющими;

2. Доказано, что доверительные интервалы, построенные по моментам сильной регенерации и по моментам слабой регенерации асимптотически эквивалентны;

3. Показано, что с увеличением числа узлов в сети типа Джексона вероятность сильной регенерации уменьшается;

4. Доказана теорема о знаке ковариации для монотонных случайных функций с разным числом аргументов;

5. Установлена линейная зависимость между временем доверительного оценивания с заданной точностью по моментам сильной регенерации и числом узлов сети при имитационном моделировании тандемных сетей;

Апробация работы. Основные результаты диссертации докладывались на международных конференциях и семинарах: Developments in Distributed Systems and Data Communications, Петрозаводск, май 1998 г.- The 3th St. Petersburg Workshop on Simulation, июнь-июль 1998 г.- Developments in Distributed Systems and Data Communications, Петрозаводск, май 1999 г.- Probabilistic Analysis of Rare Events: Theory and Problems of Safety, Insurance and Ruin, Рига, июль 1999 г.- Second International Conference on Stochastic Analysis, Осло, август 1999 г.- Finnish school on Theory of Probability, Лахти, июнь 2000 г.- The 4th St. Petersburg Workshop on Simulation, июнь-июль 2001 г.- Developments in Distributed Systems and Data Communications, Петрозаводск, май 2002 г. -Finnish school on Theory of Probability, Лахти, июнь 2002 г.- Applied stochastic models and information processes, Петрозаводск, сентябрь 2002 г.

Работа частично поддержана грантом РФФИ № 01−07−90 259.

Публикации работ. По теме диссертации опубликовано 6 работ [11, 14, 25, 53, 54, 55].

Структура работы. Работа содержит введение, 4 главы, заключение и приложение. Краткое содержание состоит в следующем.

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

Во второй главе рассматриваются основные свойства регенеративной структуры некоторых систем и сетей обслуживания (многоканальной системы типа GI/GI/m и тандема).

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

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

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

В главе 4 приведены численные результаты имитационного моделирования тандемной сети GI/GI/m —У. -> -/GI/rriN' процессорное время (в секундах), необходимое для построения доверительных интервалов с заданной точностью по моментам сильной и слабой регенерациидлины доверительных интервалов, построенных методами слабой регенерации, одинаковых случайных чисел и противоположных случайных чисел. Процессорное время, необходимое для построения доверительного интервала включает время, затраченное на генерацию с.ч., необходимых для вычисления всех характеристик, описывающих рассматриваемый процесс (например, для вычисления времен обслуживания, входного потока, вычисления незавершенного времени обслуживания и времени ожидания заявки в сети). Установлены линейная зависимость между временем доверительного оценивания по моментам сильной регенерации и числом узлов сети.

Заключение

.

В данной диссертационной работе были получены следующие результаты:

1. Для сетей типа Джексона определен класс событий, являющихся обновляющими;

2. Доказано, что доверительные интервалы, построенные по моментам сильной регенерации и по моментам слабой регенерации асимптотически одинаковы;

3. Показано, что с увеличением числа узлов в сети типа Джексона вероятность 5 уменьшается;

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

5. Установлена линейная зависимость между временем доверительного оценивания с заданной точностью по моментам сильной регенерации и числом узлов сети при имитационном моделировании тандемных сетей;

В дальнейшем следует продолжить исследование в следующих направлениях:

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

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

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