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

Лукашенко Олег Викторович

Асимптотический анализ и оценивание

качества обслуживания систем с гауссовским

входным потоком

05.13.18 – Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ

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

Петрозаводск – 2012 2

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте прикладных математических исследований Карельского научного центра Российской академии наук

Научный руководитель: доктор физико-математических наук, профессор, Морозов Евсей Викторович Лифшиц Михаил Анатольевич,

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

доктор физико-математических наук, профессор, профессор кафедры теории ве­ роятностей и математической статисти­ ки математико-механического факультета ФГБОУ ВПО «Санкт-Петербургский госу­ дарственный университет»

Шевцова Ирина Геннадьевна, кандидат физико-математических наук, ассистент кафедры математической стати­ стики факультета вычислительной матема­ тики и кибернетики ФГБОУ ВПО «Мос­ ковский государственный университет име­ ни М. В. Ломоносова»

Ведущая организация: ФГБОУ ВПО «Российский университет дружбы народов»

Защита состоится 20 декабря 2012 г. в 17:00 часов на заседании диссерта­ Д 212.190.03 госу­ ционного совета на базе ФГБОУ ВПО «Петрозаводский дарственный университет», расположенного по адресу: 185910, г. Петроза­ водск, пр. Ленина, 33.

Петрозаводского

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

Автореферат разослан « » ноября 2012 г.

Ученый секретарь диссертационного совета Р. В. Воронов

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

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

д. Последние два десятилетия ознаменовались существенными достижениями в исследовании сетевого трафика. Было, в частности, установлено, что про­ цессы, протекающие в сетях передачи данных, могут обладать фрактальными свойствами (эффект самоподобия) и долговременной зависимостью (долгой памятью). Эти свойства сетевого трафика были обнаружены и изучены в ра­ ботах У. Леланда, У. Вилинджера, Д. Уилсона, М. Такку, А. Эррамилли, М.

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

Столь существенное отличие в свойствах сетевого трафика потребовало разработки новых моделей и методов их анализа. В частности, наличие дол­ говременной зависимости между данными сетевого трафика сделало весьма популярными модели, основанные на гауссовских процессах. Самым извест­ ным и изученным самоподобным гауссовским процессом с долговременной за­ висимостью является дробное броуновское движение (ДБД). Так, например, данный процесс, названный фрактальным трафиком, впервые был использо­ ван в качестве модели входного потока в работе Норроса. Выбор такого рода входных потоков продиктован с одной стороны функциональными предель­ ными теоремами, согласно которым гауссовские процессы возникают при су­ перпозиции большого числа независимых так называемых on/off-источников с тяжелыми хвостами на больших масштабах времени, с другой стороны – статистическим анализом реальных сетевых процессов.

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

Применительно к очередям обычно выделяют два типа асимптотик: асимпто­ тики при растущем размере буфере источников: число гауссовских источников растет и пропорционально рас­ тут размер буфера и скорость обслуживания. Например, для вероятности переполнения результаты вида 1, 2 – некоторые явно заданные функции, – стационарный процесс нагруз­ ки. Известно, что в гауссовской очереди с бесконечным буфером стационар­ ный процесс загрузки 1 Norros I. Studies on a model for connectionless traffic, based on fractional Brownian motion // Conference on Applied Probability in Engineering, Computer and Communication Sciences INRIA/ORSA/TIMS/SMAI, Paris. 1993.

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

дающие менее полную информацию о вероятности переполнения. Такого ро­ да асимптотики рассматривались в работах Н. Дуффилда, Н. О’Коннелла, В. И. Питербарга, Ю. Хюслера, О. Нараяна, Л. Массоли, А. Симоняна, К.

Дебицкого, М. Манджеса, К. Дуффи, Д. Льюиса, У. Салливана, А. Дикера.

Наряду с вероятностью переполнения другой важной характеристикой систем обслуживания является максимум процесса нагрузки на конечном ин­ [0, ] (пиковая нагрузка в системе). Для этой характеристики в рабо­ тервале тах А. Зееви, П. Глинна, В. И. Питербарга, Ю. Хюслера найдены асимптотики (при в случае входного процесса ДБД.

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

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

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

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

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

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

1. Асимптотика максимума стационарного процесса нагрузки, известная для входного потока ДБД обобщена на класс гауссовских систем, у ко­ торых дисперсия входного потока является правильно меняющейся на бесконечности функцией.

2. Исследованы свойства альтернативной статистической BMC-оценки ве­ роятности переполнения гауссовской системы обслуживания.

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

4. Разработана программа для имитационного моделирования гауссовских систем обслуживания.

Апробация работы Основные результаты диссертации докладывались на следующих конфе­ ренциях: международный научный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 19–20 мая 2009 г.); 2nd Northern Triangular seminar (Стокгольм, 15-17 марта 2010 г.); международный научный семинар «Advances in Methods of Information and Communication Technology»

(Петрозаводск, 25–26 мая 2010 г.); международный семинар «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems» в рамках конгресса ICUMT’10 (Москва, 18–20 октября 2010 г.); международная конференция «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей» (21-я Белорусская школа-семинар по теории массового обслуживания, Минск, 3- февраля 2011 г.); 3rd Northern Triangular seminar (Санкт-Петербург, 11-13 ап­ реля 2011 г.); всероссийская конференция с международным участием «Ин­ формационно-телекоммуникационные технологии и математическое модели­ рование высокотехнологичных систем» (Москва, 18-22 апреля, 2011 г.) меж­ дународный научный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 28 апреля 2011 г.); V Междуна­ родный семинар «Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем» (Светло­ горск, 10–16 октября 2011 г.); VIII Международная Петрозаводская конферен­ ция «Вероятностные методы в дискретной математике» (2–9 июня 2012 г. Пет­ розаводск); 9th International Workshop on Rare Event Simulation (Тронхейм, 25-27 июня 2012 г.); международная конференция «Теория вероятностей и ее приложения», посвященная 100-летию со дня рождения Б. В. Гнеденко (Москва, 26-30 июня 2012 г.).

Работа поддержана РФФИ, грант 10-07-00017.

Публикации рецензируемых журналах [1–3] (в том числе 2 работы в изданиях из переч­ ня российских рецензируемых журналов [1, 2]), статьи в сборниках трудов конференций [4–6] и тезиса докладов [7–10]. Получено свидетельство о ре­ гистрации электронного ресурса [11].

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

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

В первой главе представлены необходимые сведения из теории гауссов­ ских процессов, теории больших уклонений и теории правильно меняющихся функций, которые требуются для последующего анализа. Здесь же дано опи­ сание жидкостной модели входного потока в виде тации рассматриваются системы с одним обслуживающим устройством с по­ стоянной скоростью обслуживания Введем коэффициент имеющий смыл коэффициента загрузки и обозначим Пусть – величина нагрузки (незавершенная работа) в момент времени Если и система имеет неограниченный буфер, то справедливо соотношение Условие обеспечивает существование стационарного режима, и стацио­ нарная величина нагрузки при этом определяется следующим образом:

превысит некоторое пороговое значение (т. е. вероятность пере­ нагрузки полнения) определяется как распределенных (н. о. р.) гауссовских источников вида (1). В этом случае вероятность переполнения (4) запишется в виде:

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

ровать ее в дискретном времени. Динамика процесса нагрузки 1, 2,...} описывается следующим образом: в начальный момент времени си­ по следующему рекуррентному соотношению (один из вариантов так называ­ емой рекурсии Линдли):

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

Тогда стационарная вероятность потери определяется следующим образом:

когда этот предел существует.

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

с дисперсией = 1, 2.

Справедлива следующая Теорема 2.1.1. Для стационарной нагрузки (3) справедлив следующий асимптотический результат:

где = max(1, 2 ).

Данный результат говорит о том, что в асимптотическом анализе вероят­ ности переполнения буфера системы, на вход которой поступает сумма неза­ висимых ДБД, доминирующую роль играет ДБД с наибольшим значением параметра Херста. Доказательство логарифмической асимптотики (10) осно­ вано на технике, использованной в работе Н. Дуффилда и Н. О’Коннелла, где в качестве компоненты фигурирует единственный процесс ДБД. Более Формально результат (10) является следствием асимптотики (11), хотя строго говоря, соотношение (10) доказано лишь для дискретного времени, посколь­ ку рассматривается гораздо более широкий класс систем обслуживания (не обязательно гауссовских). В диссертации в ходе доказательства теоремы 2.1. было показано, что асимптотика (10) выполнена в непрерывном времени.

В третьей главе исследуется асимптотическое поведение максимума процесса нагрузки гауссовской компоненты входного процесса 2 Duffield N., O’Connell N. Large deviations and overflow probabilities for the general single server queue, with applications // Proceedings of the Cambridge Philosophical Society. 1995. Vol. 118. Pp. 363–374.

3 Duffy K., Lewis J. T., Sullivan W. G. Logarithmic asymptotics for the supremum of a stochastic process // Ann. Appl. Probab. 2003. Vol. 13, no. 2. Pp. 430–445.

() – медленно меняющаяся на бесконечности функция. Обозначим = где того, предположим, что также выполнены следующие условия (при что на одном вероятностном пространстве можно задать процесс одновременно выполнены условия = означает равенство по распределению, * () = min0 { ()}. Обо­ где значим и пусть Основной результат третьей главы содержит Теорема 3.1.1. Пусть дисперсия гауссовской компоненты входного процесса удовлетворяет условиям (14), (15), а также > 0. Тогда 4 Konstantopoulos T., Zazanis M., Veciana G. D. Conservation laws and reflection mappings with application to multiclass mean value analysis for stochastic fluid queues // Stochastic Processes and their Applications. 1996. Vol. 65. Pp. 139–146.

где означает сходимость по вероятности, а параметр удовлетворяет соотношению (12). Этот результат обобщает работу А. Зееви и П. Глинна, некоторых дополнительных ограничениях сходимость по вероятности можно усилить до сходимости в пространстве Теорема 3.2.1. Пусть выполнены условия теоремы 3.1.1, а условие (14) усилено до того, что существует предел Аналогичная асимптотика получена и для нестационарного случая, т. е.

для случая, когда параметр Теорема 3.3.1. Пусть < 0, тогда для максимума процесса нагрузки () справедлива следующая сходимость Теорема 3.1.1. позволяет получить асимптотику для другой важной ха­ рактеристики систем обслуживания, а именно времени достижения стацио­ нарным процессом нагрузки некоторого порогового значения Отметим, что распределение максимума стационарного процесса нагрузки 5 Zeevi A., Glynn P. On the maximum workload in a queue fed by fractional Brownian motion // Ann.

Appl. Probab. 2000. Vol. 10. Pp. 1084–1099.

Справедлива следующая Теорема 3.4.1. Пусть дополнительно к условиям теоремы 3.1.1. функ­ ция () монотонно возрастает на некотором луче [0, ), тогда имеет место сходимость Четвертая глава посвящена статистическому моделированию гауссов­ ских систем обслуживания, важность которого определяется отсутствием точ­ ных аналитических результатов. В начале главы описано функциональное назначение разработанной программы для оценивания характеристик гаус­ совских систем. В первом разделе приведен краткий обзор методов моде­ лирования гауссовских процессов (моделирования случайной компоненты входного потока (1)). Описана процедура моделирования процесса нагрузки, как в случае бесконечного, так и конечного размера буфера. Большое внима­ ние в данной главе уделено оцениванию вероятности переполнения в режиме большого числа н. о. р. источников, которая определяется соотношением (5).

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

мо применение специальных ускоренных методов, уменьшающих дисперсию оценки. В диссертации исследованы свойства следующей BMC-оценки (Bridge Monte Carlo), предложенной в работе С. Джордано, М. Губинелли и М. Па­ гано. Кратко поясним идею, лежащую в основе построения оценки. Фикси­ 6 Giordano S., Gubinelli M., Pagano M. Bridge Monte-Carlo: a novel approach to rare events of Gaussian processes // Proc. of the 5th St.Petersburg Workshop on Simulation. St. Petersburg, Russia: 2005. Pp. 281–286.

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

Хотя выбор значения произволен, на практике, как правило, выбирается полнения. Несмотря на то, что BMC-оценка не является асимптотически эф­ фективной, ее дисперсия меньше дисперсии оценки, полученной с помощью метода существенной выборки одинарным сдвигом (single-twist estimator).

Кроме того, данный метод оценивания является гибким в том смысле, что он функцией Для проверки качества оценки (28) были проведены численные эксперименты. Полученные по формуле (28) оценки для различных типов гауссовских процессов (в том числе ДБД, сумма независимых ДБД, инте­ гральный процесс Орнштейна-Уленбека) сравнивались с известными асимп­ тотическим результатами. Во всех случаях результаты моделирования хоро­ шо согласуются с теоретическими результатами. Так, например, при больших значениях минимум в (27) на практике почти всегда достигается около ятности порядка относительная ошибка все еще составляет не более 1%.

В четвертой главе также рассматривается задача оценивания вероятно­ лено частному случаю, когда входящий поток удовлетворяет соотношению:

где – процесс броуновского движения. В силу того, что приращения ским, а значит возможно применить регенеративную теорию. Моменты ре­ генерации (в данном случае моменты опустошения системы) определяются следующим образом:

Части траекторий процесса нагрузки регенерации, E – средний объем поступившей на цикле регенерации работы.

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

При регенеративном моделировании генерируется (достаточно большое чис­ (31) оценка стационарной вероятности потери примет вид:

Более того, данный подход позволяет построить асимптотический дове­ рительный интервал для вероятности потери (с заданной доверительной ве­ роятностью следующего вида:

где а – функция Лапласа.

В Заключении сформулированы основные итоги диссертационной ра­ боты.

Основные итоги диссертационной работы состоят в следующем:

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

2. Исследовано асимптотическое поведение максимума процесса нагруз­ ки в жидкостной системе обслуживания с одним сервером. На вход си­ стемы поступает процесс, содержащий линейную (детерминированную) компоненту и случайную компоненту, описываемую центрированным гауссовским процессом, у которого дисперсия является правильно ме­ ответствующей нормировке максимум процесса нагрузки на интервале [0, ] сходится по вероятности (при ) к явно выписанной констан­ 3. Проведено имитационного моделирование гауссовских систем обслужи­ вания для оценивания вероятности переполнения/потери. Представлен­ ные результаты численных экспериментов дают хорошее согласие с при­ веденными аналитическими результатами.

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

5. Исследованы свойства альтернативной статистической BMC-оценки ве­ роятности переполнения гауссовской системы обслуживания.

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

Список публикаций Лукашенко О. В., Морозов Е. В. Асимптотика максимума про­ цесса нагрузки для некоторого класса гауссовских очередей // Информатика и ее применения. 2012. Т. 6, № 3. С. 81–89.

Лукашенко О. В., Морозов Е. В., Пагано М. Статистическое мо­ делирование гауссовской очереди // Труды Карельского науч­ ного центра Российской академии наук. 2011. № 5. С. 55–62.

3. Лукашенко О. В., Морозов Е. В., Пагано М. Применение гауссовских про­ цессов в моделировании сетевого трафика // Труды Карельского научно­ го центра Российской академии наук. 2010. № 3. С. 51–58.

4. Goricheva R. S., Lukashenko O. V., Morozov E. V., Pagano M. Regenerative analysis of a finite buffer fluid queue // Proceedings of 2010 International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT). 2010. Pp. 1132–1136.

5. Lukashenko O. V., Morozov E. V. Gaussian Processes in Communication Networks // Proceedings of AMICT’2009. 2009. Pp. 112–118.

6. Lukashenko O. V., Morozov E. V., Pagano M. Estimation of loss probability in Gaussian queues // Proceedings of the International Conference “Mod­ ern Probabilistic Methods for Analysis and optimization of Information and Telecommunication Networks”. 2011. Pp. 142–147.

7. Лукашенко О. В. Имитационное моделирование гауссовских систем с потерями // Тезисы докладов Всероссийской конференции с междуна­ родным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» Москва, РУДН. 2011. С. 257–259.

8. Lukashenko O. V., Morozov E. V. Estimation of the overflow and loss prob­ ability in some gaussian queus // XXIX International Seminar on Stabili­ ty Problems for Stochastic Models and V International Workshop «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems», Book of Abstracts. Moscow: Institute of Informatics Problems, RAS. 2011. Pp. 79–80.

9. Lukashenko O. V. Gaussian queues in communication networks // Third Northern Triangular seminar. Programe and abstract. 2011. P. 14.

10. Lukashenko O. V., Morozov E. V. On the maximum workload for a class of Gaussian queues // International conference «Probability theory and its applications» in Commemoration of the Centennial of B. V. Gnedenko. 2012.

Pp. 231–232.

http://ofernio.ru/portal/newspaper/ofernio/2012/8.doc, свободный.