Содержание к диссертации
Введение
Глава 1. Самоподобные входящие потоки 14
1. Описание объекта исследования 14
1.1. Системы массового обслуживания 14
1.2. Технологии передачи информации в современных сетях связи 18
2. Вспомогательные понятия 32
2.1. Самоподобные процессы и их свойства 32
2.2. Распределения с тяжелыми хвостами 40
2.3. Дробное броуновское движение и устойчивый процесс Левп 43
2.4. Устойчивые распределения и самоиодобные процессы 47
3. Модели самоподобного трафика 49
3.1. ON/OFF-молелъ входящего потока 51
3.2. Модель Пуассона с бесконечным числом источников 57
3.3. Модель Б.С. Цыбакова 60
Глава 2. Новая модель входящего потока 67
1. Модель трафика с неоднородными источниками 69
1.1. Задача Гнеденко 69
1.2. ON/OFF-модель с неоднородными источниками 70
2. Асимптотические свойства случайных сумм 83
2.1. Постановка задачи 83
2.2. Вспомогательные результаты 85
2.3. Доказательство теоремы 12 92
Глава 3. Оценка качества обслуживания 95
1. Качество обслуживания в компьютерных сетях 95
2. Обзор известных результатов 97
2.1. Модель B.C. Цыбакова 99
3. Характеристики QoS модели с неоднородными источниками 103
3.1. ON/OFF-модєль с неоднородными источниками 104
3.2. Модель Пуассона с неоднородными источниками 109
3.3. Модель Б.С. Цыбакова с неоднородными источниками 113
Глава 4. Уточнение константы в оценке вероятности переполнения буфера 119
1. Моделирование редких событии 119
1.1. Моделирование редких событий и метод Монте-Карло 119
1.2. Методы ускорения симуляции 121
2. Метод расщепления 125
2.1. Вероятности переполнения буфера в цикле и в стационарном режиме 125
2.2. Алгоритм оценки вероятности переполнения буфера 126
2.3. Варианты метода расщепления 129
2.4. Подбор параметров 131
2.4. Определение уровней 135
3. Результаты моделирования 136
3.1. Имитационная модель 136
3.2. Анализ результатов 141
Заключение 146
Список использованной литературы 147
- Технологии передачи информации в современных сетях связи
- ON/OFF-модель с неоднородными источниками
- Модель Пуассона с неоднородными источниками
- Моделирование редких событий и метод Монте-Карло
Введение к работе
Актуальность темы. Связь является одним из важнейших компонентов инфраструктуры современного общества. Стремительно растущий спрос на услуги связи и прогресс в области современных технологий сбора, хранения, обработки и передачи информации стимулируют динамичное развитие данной отрасли. Менее чем за полтора столетия системы связи прошли путь от традиционных «голосовых» систем — телеграфных и телефонных сетей, появившихся соответственно в середине и конце XIX века, до современных цифровых систем связи, обеспечивающих передачу интегральной информации — речи, данных, видео и т.п., в рамках одной мулътисервисной сети связи.
Обеспечение гарантированного QoS подразумевает необходимость перераспределения внутренних ресурсов сети, для осуществления быстрой, стабильной и надежной передачи информации. Поскольку в мультисервисных сетях услуги носят интегральный характер, для обслуживания запросов пользователей, требуется одновременное предоставление нескольких сетевых ресурсов, число и пропускная способность которых всегда ограничены. Это может повлечь задержки и отказы в предоставлении услуг, то есть ухудшение стандартного договорного QoS для пользователей с одной стороны и потерю потенциального дохода для операторов сети с другой. Поэтому задачи, связанные с построением адекватных моделей трафика данных, а также с прогнозом производительности сети и оценки качества обслуживания для услуг разного вида являются на сегодняшний день не менее актуальными чем во времена К. Эрланга.
Первые эксперименты но созданию компьютерных систем связи начались в 60-х годах 20 века. Изначально при проектировании таких систем стали использовать не коммутацию каналов, как в традиционной телефонии, а коммутацию пакетов, которая существенно изменила структуру потоков дан-пых в сети и явилась впоследствии одной из причин возникновения проблемы самоподобия трафика. В отличие от технологий передачи информации развивавшихся очень быстро, теоретическая база, на основе которой проектировались компьютерные сети, долгое время оставалась практически неизменной. Вследствие этого до середины 90-х годов 20 века оценка производительности сетей осуществлялась с помощью стандартных методик, основанных на формулах Эрланга. На заре компьютерных систем, когда они носили преимущественно локальный характер, передаваемый трафик состоял из небольших текстовых файлов, а ресурсы, требуемые для его обслуживания не являлись дефицитными, трудностей такой подход не вызывал. Однако но мере появления и развития глобальных сетей типа Интернет, экспоненциального ро-сга числа их пользователей и усложнения структуры передаваемой информации это привело к серьезной недооценке реальной нагрузки и значительному ухудшению качества обслуживания (QoS). Примером является сбой в сети AT&T в 1990 году, когда на протяжении 9 часов она была недоступна большей части зданий Нью-Йорка, что вызвало большие финансовые потери. Требования к повышению QoS стимулировали развитие надежных систем с высокой устойчивостью к сбоям, что, в свою очередь, резко повысило интерес к исследованию свойств нагрузки в современных компьютерных системах.
Многочисленные эмпирические исследования [24], [25], [41], [44], [55], [65], [66], [67 показали что свойства компьютерного трафика кардинально отличаются от свойств трафика в традиционных «голосовых» системах, в том числе телефонных сетях.
В «голосовых» СМО входящие потоки хорошо аппроксимируются пуас-соновскими процессами или стационарными процессами типа ARMA, а интервалы времени между прибытиями заявок полагаются независимыми случайными величинами, имеющими распределения с легкими хвостами. В силу экспоненциального убывания корреляционной функции трафика в подобных моделях агрегированный поток при увеличении масштаба усреднения приближается по свойствам к белому шуму, то есть обладает короткой памятью. Если такой поток поступает на вход некоторой СМО, то характеристи ки ее производительности, в частности, вероятность переполнения буфера конечного размера, убывают экспоненциальным образом в зависимости от увеличения некоторого характерного параметра, например, размера буфера.
Компьютерный трафик имеет долгую память, у распределений длин периодов занятости/покоя наблюдаются тяжелые хвосты, агрегированный процесс нагрузки статистически выглядит одинаково пр любом масштабе усреднения, то есть является самоподобным {монофрактальным). В таких условиях вероятность переполнения буфера с ростом его. размера h убывает не по экспоненте, как в линейных СМО с марковскими потоками, а степенным образом [46], [45], [23] [75J — [77] или по закону Вейбула [63]. И если для эффективного обслуживания «голосового» трафика буфер в 3КБ (30 пакетов размера 100Б) более чем достаточен, вероятность переполнения в этом случае имеет порядок Ю-14, то при степенном убывании вероятности переполнения в условиях сильной загрузки даже буфер в несколько ГБ не гарантирует для самоподобного трафика надежного обслуживания. Вероятности переполнения для самоподобного процесса с параметрами Н = 0.85 и Н = 0.6 и буфера размером 2ГБ (2 • 107 пакетов размера 100Б) по некоторым оценкам (см. например [75] —[77] ) имеют порядок 10 4 и 10 "8 соответственно. Сегодня для стабильной работы СМО требуется, чтобы данная вероятность не превышала 1 • Ю-9.
СМО с самоподобным трафиком к настоящему времени хорошо изучены: построены модели, приводящие к самоиодобным процессам, для них описаны возможные предельные процессы для потоков нагрузки [60], [61], [73] и получены оценки для ряда показателей QoS. Данные результаты являются важным шагом вперед в рамках анализа немарковских СМО, однако они не позволяют охватить все многообразие свойств трафика в современных условиях.
Следует отметить, что широко используемые сегодня технологии обработки информации позволяют передавать трафик с разными требованиями к параметрам QoS по одному каналу, вследствие чего поток может быть крайне неоднородным. Исследования трафика в ряде систем [34j, [72] подтверждают, что самоподобие проявляется асимптотически, на крупных временных шкалах, а для малых периодов усреднения поведение трафика больше похоже на мультифрактал. СМО с мультифрактальными потоками изучены слабо: основной вывод из нескольких работ, посвященных моделям трафика, порождаемого источниками с различными распределениями длин активных периодов, состоит в том, что свойства трафика и параметры QoS определяются источниками с самым длинным активным периодом/«тяжелыми» заявками [73]. Поведение трафика и параметров QoS в случае, когда «тяжелые» заявки приходят редко, а основную нагрузку порождают более «легкие» требования, практически не изучено. На первый взгляд наиболее очевидным в этой ситуации кажется определение размера буфера на основе потока с самыми «тяжелыми» заявками. Однако необоснованное увеличение размера буфера может не оказать желаемого влияния на СМО, так так выигрыш от уменьшения потерь информации, будет нивелирован из-за увеличения стоимости сетевой аппаратуры и ее обслуживания и ухудшения других параметров QoS, например, увеличения задержки при обработке информации в большом буфере.
Оптимизация затрат на создание и эксплуатацию сетей в сочетании с сохранением их высокой производительности и гарантированного для пользователей качества обслуживания требует повышения адекватности существующих моделей трафика и подходов оценке параметров QoS, поэтому выбранная для исследования тема является на сегодняшний день очень актуальной.
Цели и научные задачи. Целью диссертации является разработка математических моделей трафика, отражающих мультифрактальное поведение потоков данных в реальных системах связи и исследование влияния мульти-фрактального трафика на асимптотическое поведение вероятности переполнения буфера.
Для достижения этой цели в работе решены научные задачи: 1. Построены математические модели входящих потоков: неоднородная ON/OFF-моделъ, неоднородная модель Пуассона в непрерывном и дискретном времени, длины активных периодов источников в которых имеют распределения с правильно меняющимися хвостами с различными показателями 1 a k 2, к = 1,г, г со. Установлены условия, при которых источники любого типа нетривиально влияют на характеристики процесса нагрузки.
2. В неоднородной ON/OFF-модели в режиме «Slow Growth Condition» (SGC) найден новый предельный процесс для агрегированного процесса нагрузки.
3. Найдено асимптотическое распределение случайной суммы независимых случайных слагаемых, имеющих конечное число различных распределений.
4. Доказано, что вероятность переполнения буфера в неоднородной ON/OFF-модели и неоднородной модели Пуассона в непрерывном вреліени и асимптотические границы для вероятностей переполнения буфера и поте ри пакета в неоднородной модели Пуассона в дискретном времени убывают степенным образом с ростом размера буфера. Найдены условия при которых скорость убывания может совпадать с любым из а к\ к = 1,г.
5. С помощью имитационного моделирования исследованы свойства асимптотических границ для вероятности переполнения буфера в неоднородной модели Пуассона в дискретном времени.
Методы исследования. При получении теоретических результатов использовались методы теории вероятностей, теории случайных процессов и асимптотические методы математического анализа. Для проверки и уточнения полученных результатов использовалось имитационное моделирование.
Положения, выносимые на защиту.
1. Модели входящих потоков, построенные с учетом того, что доли источников разных типов в общем потоке различны.
2. Асимптотическое распределение случайной суммы независимых случайных величин, имеющих конечное число разных распределений, найденное с помощью сведения суммы со случайным числом слагаемых к сумме с неслучайным числом слагаемых.
3. Асимптотика вероятности переполнения буфера в СМО с неоднородными потоками, отражающая вклад источников разных типов.
4. Методика построения имитационной модели, основанная на использовании методов ускорения симуляции, и ее применение для уточнения константы в оценке вероятности переполнения буфера.
Научная новизна и теоретическая значимость. Результаты диссертации развивают теорию массового обслуживания в классе систем с немарковскими входящими потоками. По сравнению с существующими подходами новые модели являются более гибкими, так как учитывают влияние разных компонент трафика на свойства всего потока и на характеристики его обслуживания. Асимптотическое распределение случайных сумм, найденное ранее для одинаково распределенных св., перенесено на случай, конечного числа различных распределений. Данный результат обеспечиваег единый подход к анализу ON/OFF модели и модели Пуассона с непрерывным временелі в однородном и неоднородном случае, в огличие от известных результатов для однородного случая, при получении которых ранее использовались разные методы. Полученная в рамках разработанных моделей трафика асимптотика для вероятностей переполнения буфера и потери пакета позволяет более адекватно оценивать потери информации и отказы в обслуживании.
Практическая значимость. Практическая значимость работы состоит в том, что результаты диссертации могут служить базой для численного анализа современных СМО с мультифрактальными входящими потоками и установления минимально необходимого размера буфера при проектировании новых систем связи
Достоверность и обоснованность научных результатов базируются на корректном использовании вероятностно-статистических методов, теории случайных процессов и математического анализа. Все сформулированные теоре тические положения имеют строгие математические доказательства. Используемые в диссертации методы имитационного моделирования подтверждают обоснованность полученных результатов.
Апробация работы. Основные результаты работы докладывались на международном семинаре по проблемам устойчивости стохастических моделей (г. Юрмала, Латвия, 2004), (Салерно, Италия, 2005), на конференции «Ломоносовские чтения» (г. Москва, МГУ, 2005), на 31 международной конференции по стохастическим процессам и их применениям (г. Париж, Франция, 2006), на 5 международной конференции по процессам Леви (г. Копенгаген, Дания, 2007), на 13 Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар-Ола, 2007), на научно-практической конференции «Моделирование и принятие решений в условиях неопределенности» (г. Тверь, ТвГУ, 2008).
Публикации. По материалам диссертации опубликовано 12 работ, среди них — 3 в изданиях рекомендованных ВАК Минобрнауки России.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 155 листах, содержит 17 рисунков, 3 таблицы и список литературы, включающий 83 наименования.
Во введении отражена актуальность выбранной темы, приведен обзор научной литературы, освещающий состояние проблемы, сформулированы цели и задачи исследования и положения, выносимые на защиту. Введение также содержит основные научные результаты с обоснованием их новизны и практической ценности и краткое содержание диссертационной работы.
В первой главе определен объект исследования, даны определения, вспомогательные понятия и описания моделей, приводящих к самоподобному трафику.
В параграфе 1 описывается объект исследования и объясняются причины самоподобия трафика в современных системах связи. В параграфе 2 даются определения процессов с короткой и длинной памятью, распределений с тяжелыми хвостами, строго самоподобных, самоно-добных в широком смысле и асимптотически самоподобных процессов непрерывного и дискретного аргумента. Приводятся определения дробного броуновского движения и а-устойчивого движения Лсви, 0 а 2.
В параграфе 3 описаны модели, порождающие самоподобный трафик и область их возможного применения.
Вторая глава посвящена исследованию свойств процесса нагрузки в ON/OFF-модели с неоднородными источниками.
В параграфе 1 предложена неоднородная ON/OFF- модель, построенная с учетом того что доли источников разных типов в общем потоке различны. В рамках предложенной модели найден предельный процесс для агрегированного процесса нагрузки.
В параграфе 2 обоснована возможносгь замены случайного индекса в сумме независимых св. на его среднее значение в доказательстве теоремы 9. Найденное асимптотическое распределение для случайной суммы независимых случайных слагаемых, имеющих конечное число разных распределений имеет и самостоятельный интерес в теории случайных сумм.
Третья глава посвящена анализу характеристик QoS в СМО с самоподобными и мультифрактальными входящими потоками.
В параграфе 1 приводятся примеры основных характеристик QoS.
В параграфе 3 мы анализируем поведение вероятностей переполнения буфера и потери пакета в СМО с неоднородными источниками, когда каждый из них способен нетривиальным образом влиять на поведение системы.
В четвертой главе описывается имитационная модель для СМО Y /D/1/h и анализируется качество оценок для вероятности переполнения буфера
В параграфе 1 обоснована необходимость применения имитационного моделирования для изучения свойств оценок вероятностей переполнения буфера в модели Цыбакова Б.С. с неоднородными источниками. В параграфе 2 обосновывается невозможность применения стандартного метода Монте-Карло (ММК) для анализа редких событий и описывается метод ускоренной симуляции, используемый в данной имитационной модели.
В параграфе 3 описывается имитационная модель системы Y /D/lfh и приводятся результаты ее численного моделирования.
В заключении приводится обзор результатов, полученных в данной работе.
Технологии передачи информации в современных сетях связи
До недавнего времени теоретическую основ} для проектирования и модернизации различных телекоммуникационных систем обеспечивала теория телетрафика, созданная стараниями А.К. Эрланга, Г. О Делла, Т. Энгсетта, К. Пальма, Литтл а, Линдли, Полачека, А. Я. Хинчина, Б.В. Гнеденко, В. Феллера, Д. Кенделла и многих других. Данная теория с достаточной степенью точности описывает процессы происходящие в «голосовых» системах связи например, в телефонных сетях. Наиболее часто в качестве модели входящего потока в таких СМО используется стационарный однородный потюк без последействия, то есть пуассоновский (в общем случае, марковский) процесс, с показательно распределенным временем обслуживания требований. Относительная простота анализа, обусловленная тем, что пуассоновский процесс обладает многими полезными аналитическими свойствами и легкость в интерпретации полученных результатов обеспечили данной модели высокую популярность на долгие годы.
Анализ показывает, что потоки трафика в современных высокоскоростных телекоммуникационных сетях обладают тремя важными характерными особенностями: 1. наличием тяэюслых хвостов у распределений вероятностей длин периодов активности и покоя; 2. самоподобием; 3. свойством долгой памяти. Вследствие этого их поведение кардинальным образом отличается от традиционных моделей. Впервые о самоподобном телетрафике заговорили с момента его обнаружения в 1993 году группой ученых (W. Leland, М. Taqqu, W. Willinger и D. Wilson), которые исследовали Ethernet-трафик в сети корпорации Bellcore и обнаружили, что он выглядит качественно одинаково почти при любых масштабах временной оси. Дальнейшие исследования показали, что в условиях самоподобного трафика методы расчета характеристик современных компьютерных сетей — пропускной способности каналов, емкости буферов и прочих, основанные на пуассоновских моделях и формулах Эрланга, которые более полувека с успехом применялись при проектировании телефонных сетей, приводят к серьезной недооценке реальной нагрузки. На рисунке 2 представлены траектории реального трафика в сети Ethernet и сложного процесса Пуассона соответственно. Ось Y — это число пакетов в единицу времени, ось X — единица времени: a) 100 сек.; b) 10 сек.; c) 1 сек.; d) 0.1 сек.; e) 0.01 сек..
На графиках хорошо видно насколько различными являются свойства двух процессов: процесс Пуассона с увеличением масштаба усреднения сглаживается, становится похожим на белый шум, тогда как агрегированный .Еї/гегггеі-трафик остается случайным и статистически выглядит одинаково при любом масштабе усреднения, то есть является самоподобным.
Одна из главных причин возникновения столь сильных различий между современными и традиционными системами связи кроется, по-видимому, в использовании различных механизмов передачи информации.
В настоящее время выделяют 2 основных подхода к решению задач коммутации абонентов: коммутация каналов (circuit switching); коммутация пакетов (packet switching).
Коммутация каналов. Выше уже отмечалось, что принцип коммутации каналов лежит в основе «голосовых» систем связи, в том числе и традиционной телефонии. При использовании такой технологии между конечными узлами образуется непрерывный физический канал из последовательно соединенных коммутаторами промежуточных канальных участков.
Условием организации такого канала является равенство скоростей передачи данных в каждом из составляющих физических каналов. Иначе говоря, коммутаторы такой сети не должны буферизоваїпь передаваемые данные.
Коммутация каналов. В сетях с коммутацией каналов перед передачей данных необходимо выполнить процедуру установления соединения, в процессе которой и создается составной канал. И только после этого можно начинать передавать данные.
ON/OFF-модель с неоднородными источниками
Отказ может случиться когда на некотором участке сети соединение задействует канал, через который уже проходит максимально возможное количество информационных потоков или, если абонент способен поддерживать только одно соединение, что характерно для многих телефонных сетей (при поступлении второго вызова к уже разговаривающему абоненту сеть передает вызывающему абоненту сигнал «занято»). Нерациональное использование пропускной способности физических каналов. При установлении соединения, отводимая составному каналу пропускная способность, сохраняется за ним до тех пор, пока соединение не будет разорвано. Однако абонентам не всегда нужна пропускная способность канала во время соединения, например в телефонном разговоре могут быть паузы, еще более неравномерно во времени взаимодействуют компьютеры. Невозможность динамического перераспределения пропускной способности представляет собой принципиальное ограничение сети с коммутацией каналов, так как единицей коммутации здесь является информационный поток в целом. Обязательная задерэюка перед передачей данных из-за фазы установления соединения.
В сетях с коммутацией каналов основные задероіски передачи сообщения связаны с необходимостью установления канала и скоростью распространения сигнала в соответствующей среде.
Следует заметить, что достоинства и недостатки любой сетевой технологии всегда относительны. При определенных условиях определяющим фактором являются достоинства, а недостатки становятся несущественными. В частности, техника коммутации каналов хорошо работает при передаче телефонного трафика, когда можно мириться с тем, что нельзя вырезать паузы из разговора, и, тем самым, более рационально использовать каналы между коммутаторами.
Сети с коммутацией каналов, унаследовали от первых телефонных сетей богатую историю, вследствие чего, их характеристики к настоящему моменту хорошо изучены и разработаны строгие методики их расчетов.
Однако результаты экспериментов с первыми глобальными компьютерными сетями в конце 60-х годов 20 века выявили необходимость применения иных технологии передачи данных. Дело в том, что компьютерный трафик, как правило, является очень неравномерным и характеризуется высо ким уровнем пульсации. Например, при обращении к удаленному серверу пользователь сначала просматривает содержимое каталога этого сервера, что порождает передачу небольшого объема данных. Затем он открывает требуемый файл в текстовом редакторе, и эта операция может создать достаточно интенсивный обмен данными, особенно для файлов, содержащих объемные графические включения. После отображения нескольких страниц файла пользователь некоторое время работает с ними локально, что вообще не требует передачи данных по сети, а затем возвращает модифицированные копии страниц на сервер, что снова порождает интенсивную передачу данных по сети. Коэффициент пульсации трафика отдельного пользователя сети, равный отношению средней интенсивности обмена данными к максимально возможной, может достигать 1:50 или даже 1:100. Если в этой ситуации организовать коммутацию канала между компьютером пользователя и сервером, то большую часть времени канал будет простаивать, а коммутационные возможности, закрепленные за данной парой абонентов на все время сессии, окажутся недоступными другим пользователям сети. Следовательно, при передаче компьютерного трафика нерациональное использование пропускной способности каналов выходит на первый план.
II. Коммутация пакетов. В основу большинства компьютерных сетей был положен принцип коммутации пакетов. В этом случае все передаваемые пользователем сообщения — логически завершенные порции данных, включающие запрос на передачу файла, ответ на этот запрос, содержащий весь файл и т.д. разбиваются в исходном узле на сравнительно небольшие части, называемые пакетами. Сообщения могут иметь произвольную длину, от нескольких байт до сотен мегабайт. Пакеты также могут иметь переменную длину, но в узких пределах, например от 46 до 1500 байт. Каждый пакет снабжается заголовком, в котором указывается адресная информация, необходимая для досгавки пакета на узел назначения, а также номер пакета, который будет использоваться узлом назначения для сборки сообщения. Пакеты транспортируются по сети как независимые информационные блоки. Коммутаторы сети принимают пакеты от конечных узлов и на основании адресной информации передают их друг другу, а в конечном итоге — узлу назначения, в котором происходит сборка сообщения.
Коммутаторы пакетной сети в отличие от коммутаторов каналов имеют буферную память для временного хранения пакетов. Таким образом, если выходной порт коммутатора в момент прихода нового пакета занят передачей другого пакета, пришедший пакет помещается в буфер и начинает обслуживаться тогда, когда до него дойдет очередь в соответствии с принятой в сети дисциплиной обслуживания. Такая схема передачи данных сглаживает пульсацию трафика между коммутаторами и позволяет наиболее эффективно использовать их для повышения пропускной способности сети в целом.
Модель Пуассона с неоднородными источниками
Однако, трафик в современных мультисервисных сетях является интегральным, то есть состоит из множества потоков заявок, сгенерированных различными приложениями, которые могут отличатся друг от друга разными требованиями к обслуживанию и рабочим характеристикам сети. Так, например, в зависимости от того, какие требования предъявляются в отношении задержки информации при передаче, трафик условно делят на три категории: «трафик реального времени», «трафик транзакций» и «трафик данных».
«Трафик реального времени» (передача мультиимедийных данных) является критичным к задержкам при передаче: допустимые значения задержек обычно не превышают 0.1 с. Кроме того, задержка должна иметь малые флуктуации, поскольку с ними связан эффект «дрожания». Задержка при передаче или превышение допустимого порога «дрожания» могут приводить к ощутимым искажениям изображения и звука или потере синхронизации между ними. При сжатии информации трафик данной категории становится очень чувствительным к ошибкам при передаче, а из-за жестких требований к задержкам при передаче потоков в режиме реального времени возникающие ошибки не могут быть исправлены с помощью повторной посылки.
При передаче «трафика транзакций» (обработка финансовых транзакций) задержки не должны превышать 1 с. В противном случае пользователи будут вынуждены ждать ответа на свои сообщения, потому что только после получения ответа они могут продолжить отправлять свои данные. Такая схема обмена информацией снижает производительность труда, а разброс в значениях задержек может привести к возникновению чувства дискомфорта у пользователей. В некоторых случаях превышение допустимого времени задержек приводит к сбою рабочей сессии.
Задержки при передаче «трафика данных» (электронная почта, пересылка файлов) могут иметь практически любые значения и достигать даже нескольких минут, и даже часов. Для такого трафика полоса пропускания более важна, чем время задержек: увеличение пропускной способности сети влечет за собой уменьшение времени передачи. Приложения, передающие большие объемы данных, разработаны, в основном, так, что захватывают всю доступную полосу пропускания сети.
Редкими исключениями являются приложения потокового видео. Для них важны и пропускная способность и. минимизация времени задержки.
Сложная структура и высокая неоднородность в плане требований к параметрам сети современных потоков данных способны таким образом неограниченно расширить круг «главных» характеристик QoS. Поэтому проектировщики систем выделяют ряд основных показателей QoS, связанных с процессом буферизации данных (который, в основном, и можно контролировать при разработке и создании СМО) важных для потока с любыми свойствами:
В данной работе в качестве оценки производительности СМО мы рассматриваются вероятность переполнения буфера и вероятность потери пакета.
Всюду далее мы будем рассматриваеть систему связи, состоящую из одного сервера (обслуживающего прибора, канала), на который поступает нагрузка от других узлов сети — пользователей. Предполагается, что сервер имеет буфер конечного размера, что является типичной ситуацией для современной системы связи в условиях сильной загрузки. Подобная модель рассматривается в литературе как базовая математическая модель коммутатора или маршрутизатора, которая позволяет с достаточной степенью точности воспроизводить реальные процессы и, что очень важно, является доступной для анализа даже в случае потоков нагрузки с очень сложной структурой.
Наиболее хорошо исследованными на сегодняшний день являются линейные СМО с марковскими входящими потоками. Для таких систем где случайная величина Q — есть длина очереди и г) 0.
Данный результат справедлив и в случае, когда на вход СМО подается агрегированный поток от нескольких, возможно неоднородных марковских источников.
Из формулы (84) вытекает, что с ростом размера буфера вероятность переполнения убывает экспоненциальным образом (см. например формулы Эр-ланга), и в традиционных моделях увеличение размера буфера может рассматриваться как один из методов борьбы с перегрузкой в сети.
Для потоков с долговременной зависимостью вероятность переполнения с увеличением размера буфера убывает гораздо медленнее, чем в предыдущем случае. В частности, для фрактального броуновского движения (см., например, (63]) при больших х где 7 0 — некоторый параметр, Р = 2(1 — Н). Для самоподобных процессов с долгой памятью 1/2 Н 1, следовательно (З (0,1). Для самоподобного процесса Леви с Н = 1/а, вероятность переполнения убывает с ростом размера буфера степенным образом (см., например, [46], [45]), то есть где 5(a) 0 — некоторый параметр. В последние годы возрос интерес к изучению СМО вида G/D/C/h. Это обусловлено тем, что в современных системах связи, использующих режим асинхронной передачи данных — ATM, время обслуживания пакетов является детерминированным. В частности, в работах Б.С. Цыбакова для СМО с самоподобным входящим потоком и детерминированным временем обслуживания были получены верхние и нижние асимптотические границы для вероятности переполнения буфера и вероятности потери пакета. Соответствующие границы при h — оо убывают степенным образом, причем скорость их убывания зависит от значения параметра самоподобия Н изучаемого процесса. Рассмотрим систему связи Y/D/C/h с дискретным временем t є Z, которая состоит из конечной буферной памяти (буфера) и канала (обслуживающего устройства). На вход буфера поступает трафик Y = (... ,У_і,1о, Yi,...), где Yt обозначает число пакетов, приходящих момент t. Мы полагаем, что Y = (Yt, t є Z) — это трафик описанный в разделе 2.3. главы 1, имеющий источники, генерирующие пакеты с постоянной скоростью R — 1. В этом случае при фиксированном t св. Yt имеет распределение Пуассона со средним E(Yt) — ХЕт. Изучаемая система имеет буфер конечного размера (в пакетах) — h оо, постоянное время обслуживания для пакета — D и пропускная способность канала (в пакетах) — С. В каждом временном окне [t, +1) канал передает не более чем С пакетов, которые берутся либо из буфера, либо из Yt новых пакетов. Пакет, который передается в окне t, уходит из рассматриваемой системы в момент t + 1. Далее мы полагаем С = 1 и D = 1.
Моделирование редких событий и метод Монте-Карло
Существуют разные методы исследования характеристик современных систем телекоммуникации, в том числе аналитические и численные методы, имитационное моделирование. Поскольку аналитические и численные методы хорошо работают только в тех случаях когда структура СМО, входящего потока и дисциплины обслуживания относительно просты, имитационное моделирование — это почти универсальный подход, позволяющий эффективно решать задачи практически любой сложности. На сегодняшний день самым известным и широко применяемым методом имитационного моделирования является метод Монте-Карло (ММК).
Имитационное моделирование СМО обычно используется для оценки некоторых стационарных или переходных характеристик, от которых, с точки зрения пользователя, зависит качество данной системы. Как правило, это так называемые параметры качества обслуживания: время ожидания обслуживания в очереди, вероятность переполнения буфера заявок, вероятность потери требования при переполнении буфера и т.п..
В современных высокоскоростных сетях связи пользователи предъявляют очень жесткие требования к качеству обслуживания. Для обеспечения надежной работы отдельных приложений и систем в целом типичные значения для таких важных параметров QoS как вероятность переполнения буфера или вероятность потери пакета не должны превышать Ю-9. При моделировании такие события появляются крайне редко, поэтому стандартный метод симуляции — метод Монте-Карло оказывается в этой случае малоэффективным.
Обозначим через -у = у(А) вероятность некоторого события А. Если 7 О, событие А будем называть редким.
Несмещенной оценкой вероятности 7 по ММК является случайная величина Если мы хотим, чтобы относительная ошибка НЕ(/умс) оценки не превышала некоторую величину г, то есть то минимальное число траекторий — п необходимых для достижения заданного уровня точности г должно быть равно Так например, если 7 = Ю-9, то для достижения точности г = 0.01 необходимо взять п 1013. Этот пример показывает, что при 7 — 0, как правило, требуется рассматриват ь огромное число траектории, поэтому, с учетом затрат на симуляцию, моделирование в таких условиях моэюет занимать от нескольких часов до нескольких лет. Кроме того RE MC) (п7)_1//2 — сю при 7 — 0, то есть относительная ошибка оценки неограниченно возрастает. Из вышесказанного следует, что при моделировании редких событий нужно использовать более эффективные методы. В настоящее время применяется 2 различных подхода к моделированию событий вероятность которых мала: увеличение числа событий в единицу времени за счет использования быстрых процессоров или параллельного моделирования; увеличение вероятности интересующего события за счет использования некоторых статистических свойств рассматриваемой модели. Среди методов ускорения симуляции можно выделить 1. параллельное и распределенное моделирование] 2. гибридные методы, объединяющие аналитические решения и симуляцию; 3. методы снижения дисперсии (в комбинации с другими методами); 4. методы увеличивающие вероятность появления редкого события. Так как применение распределенного моделирования и гибридных методов при решении большинства практических задач затруднительно, а методы снижения дисперсии сами по себе не применяются при моделировании редких событий, в дальнейшем мы будем рассматривать только методы из последней группы. В настоящее время для моделирования и анализа событий, вероятности появления которых малы, широко применяются два метода: метод существенной выборки или Importance Sampling; метод расщепления или Importance Splitting.
Оба метода специальным образом увеличивают частоты появления редких событий и дают несмещенные оценки для изучаемых характеристик. Более того, при оптимальном подборе параметров, оценки, полученные с помощью этих методов, имеют меньшую стандартную ошибку по сравнению с обычным ММК.
Метод существенной выборки. Идея метода заключается в изменении исходного распределения вероятностей системы или процесса, в результате которого редкое событие становится «менее редким», то есть происходит более часто. Применительно к системам массового обслуживания можно менять распределения времени между прибытиями заявок и/или времени обслуживания.
Пусть X это некоторая случайная величина с плотностью распределения р(х) и Оценкой для вероятности -) будет случайная величина где величины (Xfc, к = 1, п) имеют новое распределение вероятностей с плотностью р {х).
Эффективность метода напрямую зависит от выбора функции р (х). Оптимальное изменение меры, при котором D(j) — 0, возможно при известном 7, иными словами, ко?да существует аналитическое решение. Но в большинстве случаев очень трудно, а для сложных систем практически невозможно найти преобразование, которое позволит снизить дисперсию оценки. «Плохой выбор» может привести к тому, что полученная оценка окажется хуже, нежели оценка по ММК. В определенных случаях изменение исходного распределения (даже оптимальное) не снижает вариацию и более того может получиться, что D(7) = со.
