Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
8.2 Вероятность потерь системы HM/D/m Соотношение первых двух моментов случайного количества требований за среднюю длительность обслуживания (интенсивность нагрузки) определяет скученность интенсивности нагрузки или пикфактор трафика 2 S В наиболее часто применяемой математической модели пуассоновского потока требований σ 2 ≡ Λ, поскольку интервал времени между требованиями z распределен по экспонентному закону, а количество требований за среднюю длительность обслуживания распределено по закону Пуассона. Реальным потокам присуща повышенная неравномерность трафика, где дисперсия интенсивности нагрузки σ 2 превышает ее математическое ожидание Λ от 2 до 15 раз. Иногда данное соотношение бывает еще больше, но это происходит или за пределами ЧНН, или на небольших пучках каналов. Поэтому для реальных потоков, как правило, S > 1. Определение основной характеристики QoS – вероятности отказа в обслуживании из-за занятости всех серверов системы – базируется на определении вероятностной функции распределения состояний системы P i В модели HM/D/m вероятность отказа в обслуживании зависит от пикфактора интенсивности нагрузки S и при условии m > Λ равна вероятности занятия всех m серверов системы (8.3), умноженной на S: 2 0 2 2 ) )( 2 ( exp 1 m k B m k m k P (8.6) В [10] показано, что регулярный закон распределения продолжительности обслуживания с точки зрения качества обслуживания наихудший и потому формула (8.6) есть не что иное, как верхняя оценка возможных значений вероятности отказа в обслуживании. Для других законов распределения продолжительности обслуживания требований к формуле (8.6) применяется специальная аппроксимирующая функция, полученная по результатам имитационного моделирования [9], и в которой коэффициентом h задается вид закона распределения длительности обслуживания: ) 5 ( ) )( 1 ( 1 2 ) )( 2 ( exp 2 2 0 h h S m S S m k m k S P m k B , (8.7) где h равно 4.25, 3.55 и 2.85 для равномерного, экспонентного и логарифмически нормального законов распределения длительности обслуживания соответственно. Видно, что при S = 1 (то есть σ 2 = Λ) данная формула превращается в формулу (8.3) для случая i = m – состояние системы m (занятые все серверы). 77 На рис. 8.2 приведены зависимости вероятности потерь P B от количества серверов в системе HM/G * /m и вида закона распределения продолжительности обслуживания при Λ = 100 Эрл и S = 8 (G * – регулярный, равномерный, экспоненциальный и логарифмически нормальный законы распределения продолжительности обслуживания). Рисунок 8.2 – Зависимость P B от m и закона распределения длительности обслуживания Пунктирная кривая E m (Λ) показывает зависимость потерь от m, рассчитанную по B-формуле Эрланга. Штриховыми линиями 1, 2, 3 и 4 показаны зависимости вероятности потерь требований для регулярного, равномерного, экспонентного и логарифмически нормального законов распределения продолжительности занятия соответственно. Графики демонстрируют, что, например, при емкости системы m = 125 серверов вероятность потери требования, рассчитанная по B-формуле Эрланга, составит P B = 0,002. В то же время, если в систему поступает не пуассоновский поток, а более неравномерный с пикфактором S = 8, то при постоянной длительности обслуживания требований реальные потери составят P B = 0,07, что в 35 раз больше. Для того чтобы удержать качество обслуживания на заданном уровне P B = 0,002 необходимо в системе иметь реально m = 172 сервера, а не 125. Такова ошибка в расчетах СМО, когда используются неадекватные методы, не учитывающие характер входного потока требований. Видно, что при значительной (S = 8) дисперсии интенсивности нагрузки лучшее качество обслуживания будет там, где в законе распределения длитель- ности обслуживания больше доля (вероятность) коротких требований. Менее короткие по длительности обслуживания требования скорее покидают систему, освобождая серверы для использования их следующими требованиями. В табл. 1 Приложения даны сведения об интенсивности нагрузки Y, обслуженной m-серверным полнодоступным пучком при потерях 1, 3 и 5 ‰ и коэффициентескученности нагрузки S = 1, …, 5. При S = 1 представленные значения совпадают со значениями, рассчитанными по B-формуле Эрланга. 78 8.3 Система с неограниченной очередью HM/D/m/∞ В полнодоступную m-серверную систему с неограниченной очередью поступает гиперэкспонентный поток требований с интенсивностью Λ, пикфак- тором S > 1 и нормальным распределением количества требований за единицу времени x, где x – постоянная длительность обслуживания требования. Выбор из очереди – в порядке поступления. Определить характеристики QoS: вероятность ожидания P w>0 ; среднюю длину очереди Q; среднюю продолжительность ожидания требований в системе W; среднюю продолжительность ожидания требований в очереди t q Распределение вероятностей P i случайного количества требований i, поступающих в систему за единицу времени x,описанного нормальным законом распределения: 2 2 2 2 1 i i e P (8.8) Независимо от вида потока требований W и Q находятся по формулам (7.44) и (7.45) на основании определения и формулы Литтла. Из формул видно, что данные характеристики QoS зависят от P w>0 и t q , которые определяются из функций распределения состояний системы P j и времени ожидания требований в очереди P(t q ). Однако, для непуассоновского потока не существует общего метода получения таких функций, и формулы для них не являются простыми. Для расчета t q применим такие, установленные раньше, результаты: из C-формулы Эрланга следует, что в системе M/M/m/∞ средняя длительность ожидания требований в очереди t q(M) = 1 / (m – ); из формулы Поллачека-Хинчина следует, что в системе M/D/1/∞ средняя длительность ожидания требований в очереди t q(D) = t q(M) / 2. Очевидно, что в искомом выражении для расчета t q системы HM/D/m/∞ должны учитываться данные выводы. Первый – потому, что пуассоновский поток (M) есть частным случаем гиперэкспонентного (Н). Второй – поскольку односерверная система (m = 1) есть частным случаем многосерверной. В [11] для системы HM/D/m/∞ показано, что t q(D) > t q(M) в S / (k = 2) раз при количестве серверов m = . Это хорошо согласуется с приведенными выше соотношениями – через пикфактор S учтено отличие гиперэкспонентного потока от пуассоновского, и отличие в два раза средней продолжительности ожидания при постоянной и экспонентной длительности обслуживания, но отнесено это к характерной точке m = . С ростом емкости системы m коэффициент k = 2 убывает приблизительно со скоростью k(m) ≈ (m + ) / m. По результатам имитационного моделирования системы HM/D/m/∞ установлено, что точность расчета t q повышается при замене данной зависимости на k(m) ≈ (m + + 1 + / m) / m. Окончательная формула для расчета t q системы HM/D/m/∞ имеет вид: 79 ] / 1 [ 1 / 1 1 2 m m S m m m S m t q (8.9) Для расчета P w>0 применим такие аргументы. Вероятность P w>0 – это вероятность занятости всех m серверов (7.47). Аналогично модели M/D/m/∞, при конечном числе m и неограниченном количестве мест ожидания требования обслуживаются без потерь. На серверы системы поступают требования из первичного потока с интенсивностью и из очереди с интенсивностью P > 0 t w (см. 7.34). Поэтому общая интенсивность нагрузки на систему увеличивается до величины 2 = + Q (см. п. 7.4). При гиперэкспонентном потоке функция распределения количества требований в системе (обслуживаются и в очереди) или состояний системы P j отличается от функции распределения P i количества поступающих требований. На рис. 8.3 даны распределения состояний систем с m = 105, 110 и 120 серверов (m > ) при гиперэкспонентном потоке требований с Λ = 100 Эрл и S = 4. Рисунок 8.3 – Распределение состояний системы HM/D/m/∞ Из рис. 8.3 видно, что при уменьшении m разброс отдельных значений функции распределения состояний системы от среднего значения увеличивается. Из чего следует, что дополнительный поток требований из очереди увеличивает общую интенсивность нагрузки 2 и ее дисперсию 2 2 Заметно, что уже при m = 120 (пунктирная линия) функция распределения состояний системы достаточно симметричная, что позволяет ее целиком аппроксимировать нормальным законом распределения. Аппроксимация этих функций нормальным законом (8.8) с параметрами 2 = + Q ; (8.10) 2 2 Q (8.11) 80 дает хорошие результаты на левом отрезке функции распределения состояний системы, обусловленном границами суммирования в (7.47), т.е. от 0 до m – 1: 1 0 0 1 m i i w P P Из этого следует простой итерационный алгоритм расчета основных характеристик качества обслуживания системы HM/D/m/∞: – из (8.9) для заданных , S и m рассчитывается t q ; – из (7.47) и (8.8) для заданных и σ 2 определяется первичная вероятность P w>0 (как для случая, когда требования из очереди не идут в систему и не увеличивают нагрузки на нее); – для рассчитанных t q и P w>0 в соответствии с (7.44) и (7.45) определяются первичные значения W и Q; – для рассчитанных из (8.10) и (8.11) значений 2 и σ 2 в соответствии с (7.47) и (8.8) определяется уточненная вероятность P w>0 , т. е. с учетом влияния дополнительной нагрузки на серверы системы из очереди. (При этом длина очереди более реальная, поскольку требования, которые не идут из системы немедленно, оказывают содействие возрастанию очереди); – по уточненному P w>0 из (7.44) и (7.45) уточняются значения W и Q. Путем имитационного моделирования установлено, что реализация этого алгоритма в большом диапазоне варьирования параметров , S и m дает всегда заниженную оценку вероятности P w>0 , однако, при этом относительная ошибка никогда не превышает -10 %. Поэтому, поскольку на последнем шаге снова уточняются значения W и Q, то можно еще раз пересчитать P w>0 с более точными значениями 3 и σ 3. Проверка этого шага показала, что результаты расчетов после третьей итерации всегда дают верхнюю оценку вероятности P w>0 , которая не превышает +10 % [11]. 81 8.4 Система с неограниченной очередью fBM/D/1/∞ Трафик мультисервисных сетей с коммутацией пакетов характеризуется наличием долгосрочных зависимостей в интенсивности нагрузки и существенным отличием статистических свойств потоков пакетов от пуассоновского потока. Адекватной моделью потоков в таких сетях считаются самоподобные (self-similarity) процессы, где входной поток описывается фрактальним броуновским движением (модель fBM). Однако, исследование характеристик качества обслуживания СРИ в этих условиях является очень сложной математической задачей. Причиной тому есть слабая формализованность модели самоподобных потоков, вследствие чего и невозможно получить аналитически обоснованные результаты для оценки параметров QoS в системах распределения информации. Для односерверной системы с бесконечной очередью и постоянным временем обслуживания (модель fBM/D/1/∞) приближенное решение приведено в [1], где показано, что количество требований в рассмотренной системе в любой момент времени t может быть представлено случайной величиной )) ( ) ( ) ( ( sup ) ( s t t A t A t N t s , где ) ( ) ( t Z a t t A Случайный процесс Z(t)является нормализованным фрактальным броуновским движением с параметром Херста Н (H = 0,5 ... 1), а положительный коэффициент а является некоторым множителем масштаба. В состоянии статистического равновесия при 1 вероятность того, что количество требований в системе N превысит заданную величина х, представлена в виде функции: a a f a x t a t Z x N H H t / ) 1 ( 0 ) ( sup Pr ) Pr( Для случая, когда эта вероятность равна заведомо заданной величине Рг(N > х) = ε из вышеприведенного следует, что const ) ( 1 5 0 1 5 0 5 0 f a x H H H H H H , а это означает, что 1 5 0 1 ) 1 ( H H H x N (8.12) 82 Величина х найдена из предыдущего в предположении, что const = 1. Вероятность, равная единице – это достоверное событие и, поэтому, х – это количество требований в системе, которое не может быть превышено, то есть это может быть верхняя оценка среднего количества требований N в системе fBM/D/1/∞. Поскольку из формулы Литтла следует, что Т = N /λ, то среднее время пребывания требования в системе при μ = 1, то есть в единицах времени продолжительности обслуживания, определяется формулой: 1 5 0 1 1 5 0 1 ) 1 ( 1 ) 1 ( H H H H H H H T (8.13) Исходя из того, что для любой односерверной системы средняя длина очереди Q = N – ρ, то с учетом (8.12) получим: 1 5 0 1 ) 1 ( H H H Q (8.14) Результат (8.12), (8.13) и (8.14) считается аналитическим решением для системы fBM/D/1/∞. Однако, при анализе этого результата можно заметить, что при задании коэффициента Херста H = 0,5 (несамоподобный процесс) имеем известный результат для среднего количества требований, средней продолжительности пребывания и средней длины очереди в системе типа М/М/1/∞. Это достаточно нелогичный результат, поскольку исследовалась система с детерминированным временем обслуживания fBM/D/1/∞. При изменении коэффициента Херста от значения H = 1 (максимальное значение) до H = 0,5 (минимальное значение), несомненно, видоизменяется поток требований и соответствующая функция распределения вероятности интервала времени между требованиями, но не изменяется функция распределения продолжительности обслуживания. Разумеется, при H = 0,5 поток теряет свойства самоподобности, но в этом случае результаты (8.12–8.14) должны коррелироваться с результатами для некоторой модели с постоянной длительностью обслуживания, а не экспонентной [12]. Из приведенного на рис. 8.6 графика зависимости среднего времени пребывание требований в системе T следует, что при нагрузке ρ > 0,3 система fBM/D/1/∞ с входным потоком требований, имеющим характер самоподобного процесса, будет затрачивать на обработку больше времени, чем при отсутствии свойства самоподобия, то есть чем системы M/M/1/∞ и M/D/1/∞. 83 Рисунок 8.6 – Зависимость среднего времени пребывания требований в системе Т для моделей M/M/1/∞, M/D/1/∞ и fBM/D/1/∞ при H = 0,7 Из приведенного на рис. 8.7 графика зависимости среднего количества требований в системе N для систем M/M/1/∞, M/D/1/∞ и fBM/D/1/∞ следует аналогичный вывод, что при нагрузке ρ > 0,3 в системе с входным потоком требований, имеющим характер самоподобного процесса, будет больше требований, чем при отсутствии самоподобности. Рисунок 8.7 – Зависимость среднего количества требований в системе N для моделей M/M/1/∞, M/D/1/∞ и fBM/D/1/∞ при H = 0,7 84 К подобному выводу можно прийти и после анализа графика зависимости средней длины очереди Q от ρ в тех же системах, приведенному на рис. 8.8. Рисунок 8.8 – Зависимость средней длины очереди Q для моделей M/M/1/∞, M/D/1/∞ и fBM/D/1/∞ при H = 0,7 На всех графиках можно видеть, что с ростом интенсивности нагрузки ρ ухудшаются характеристики качества обслуживания T, N и Q, но еще более существенным образом они ухудшаются при наличии свойств самоподобия во входном потоке требований. Результат в виде выражений (8.12), (8.13) и (8.14) показывает степень этого влияния в зависимости от величины коэффициента H. Однако, для данного результата (формулы Норроса), полученного в предположении постоянной продолжительности обслуживания, при H = 0,5 выражения (8.12), (8.13) и (8.14) дают оценки параметров качества обслуживания, характерные для пуассоновского потока с экспонентным законом распределения продолжительности обслуживания, а не регулярного (модель M/M/1/∞). Установить степень точности данного результата можно при помощи имитационного моделирования. При имитационном моделировании достаточно оценить только один из параметров, например N, поскольку параметры Q и T связаны с N известными функциональными зависимостями. Результаты имитационного моделирования СМО типа fBM/D/1/∞ при H = 0,7 приведены на рис. 8.9 и показаны линией, в виде знаков „+”. 85 Рисунок 8.9 – Моделирования среднего количества требований в системе N для модели fBM/D/1/∞ при H = 0,7 Результаты моделирования показывают, что для входного потока со свойствами самоподобия с ростом интенсивности нагрузки ρ ухудшаются характеристики качества обслуживания, но не настолько, как это определяется формулой Норроса. Расхождение результатов моделирования и оценок, полученных по формулам (8.12), (8.13) и (8.14) может составлять сотни процентов. Оценка Норроса сильно завышена и надо более точное решение. Наиболее перспективным есть метод оценки параметров качества обслуживания самоподобного трафика, в котором предложено использовать методы расчета известных классических распределений, энтропия которых наиболее близка к энтропии распределения состояний системы в условиях обслуживания самоподобного трафика [13]. При этом возможен расчет характеристик QoS в моделях с самоподобным трафиком при любом законе распределения длительности обслуживания по формуле Полачека-Хинчина. Случайный процесс (СП) поступления пакетов в СРИ, образует поток пакетов (трафик) характеризуется определенным законом распределения. Он устанавливает связь между значением случайной величины (количеством пакетов) и вероятностью появления этого значения. В большинстве случаев для расчета параметров QoS достаточно знать о законе распределения только некоторые его числовые характеристики – моменты распределения разных порядков. Для расчета пуассоновского распределения достаточно математичес- кого ожидания Λ, а для нормального – необходимы Λ и дисперсия D. Основные характеристики случайного процесса Λ и D, хотя и важны, в то же время не являются исчерпывающими, а иногда и недостаточными для прогнозирования значения случайной величины. Иногда СП характеризуются 86 одинаковыми значениями Λ и D, но внутренняя структура этих процессов разная. Одни могут иметь плавно меняющиеся реализации, а другие – ярко выраженную колебательную структуру при скачкообразном изменении отдельных значений случайной величины (например, резкое возрастание количества пакетов в сети, приводящее к „пачечности” трафика). Для „плавных” процессов характерна большая предсказуемость реализаций, а для „пачечных” – очень малая вероятностная зависимость между двумя случайными величинами СП. В таких случаях закон распределения, характери- зующий СП, несет в себе некоторую неопределенность и позволяет с большей или меньшей надежностью прогнозировать значение случайной величины. Итак, используемые вероятностные законы распределения, описывающие трафик в пакетных сетях, не дают такой количественной оценки неопределенности состояния СМО, как энтропия распределения: j m j j P P m H log 1 ) ( Энтропия не зависит от значений, которые приобретает случайная величина, а только от их вероятностей. Оценка параметров качества обслуживания самоподобного трафика возможна энтропийным методом, сводящимся к использованию методов расчета известных распределений, энтропия которых совпадает или наиболее близкая к энтропии состояний системы при обслуживании самоподобного трафика [13]. Результатами моделирования установлено, что в тех точках, где одинакова энтропия распределения состояний системы, одинаковы и исследуемые параметры качества обслуживания, такие как средняя длина очереди Q и средняя продолжительность ожидания требований W. Например, для моделей M/M/1/∞ и fBM/D/1/∞ при коэффициенте Херста H = 0,8 и ρ = 0,6 энтропии распределений состояний системы довольно близки и равны 1,683 и 1,719 соответственно. При этом для модели fBM/D/1/∞ средняя длина очереди Q = 0,982 и средняя продолжительность ожидания всех требований W = 1,611, что превышает соответствующие значения для модели M/M/1/∞всего на 3 % (на столько же отличие и значений энтропии). Такое же совпадение основных параметров качества обслуживания СМО с очередью наблюдается во всех других точках, для которых одинаковые значения энтропии распределения состояний системы, независимо от закона распределения продолжительности обслуживания. Поэтому для этих расчетов можно применять формулы Поллачека-Хинчина из табл. 7.1 модели M/G/1/∞. Алгоритм применения энтропийного метода расчета QoS такой: 1. Для установленного закона распределения состояний системы определяется энтропия распределения H fBM (по известными формулам). 2. Изменением коэффициента вариации ν x для модели, например M/HM/1/∞, достигается совпадение значений энтропии H M/HM/1 = H fBM 87 3. С помощью данного коэффициента вариации ν x определяется среднее количество пакетов в системе N по формуле Поллачека-Хинчина (табл. 7.1). 4. Через известные соотношения находятся другие характеристики QoS. Расчет характеристик QoS в модели с самоподобным трафиком при любом законе распределения длительности обслуживания возможен. Необходи- мое условие такого – определение энтропии распределения состояний системы. Доказательство свойства самоподобия реального трафика выполняется методом абсолютных моментов. В качестве значений случайного процесса рассматривается количество требований, поступающее в СМО за единицу времени. Исходную последовательность количества требований длиной N разделим на блоки длиной m (отдельные агрегированные процессы размером m). На непересекающихся временных интервалах, то есть на границах каждого блока k-я последовательность имеет среднее значение: m j m k m k X m X 1 1 ) 1 ( ) ( 1 , k = 1, 2, 3 …, [N / m] После расчета среднего значения X для всей последовательности, потом для каждого блока k рассчитаем дисперсию D k : m j m k m k X X m N D 1 2 ) ( ) ( / 1 Для самоподобного процесса дисперсия агрегированных процессов должна убывать медленнее, чем величина, обратная размеру выборки m [1]. Для выявления этого свойства построим дисперсионно-временной график зависимости дисперсий агрегированных процессов от степени агрегирования m. Поскольку Херстом было показано, что: 2 log min max log N H D D D (m) k , это график этой зависимости строим тоже в логарифмическом масштабе. Выражение в левой части этого уравнения ) ( min max m k D D D называется R/S статистикой или нормированным размахом. Из полученного графика определяем коэффициент , как тангенс угла наклона аппроксимирующей кривой к построенной зависимости. Данная аппроксимация выполняется методом минимального среднеквадратичного отклонения от экспериментальных данных. Коэффициент (0 < < 1), задающий асимптотические свойства характеристик самоподобного случайного процесса связан с параметром Херста следующим соотношением [1]: 2 1 H Для реальных процессов, не имеющих свойства самоподобия, H < 0,5, а для самоподобных процессов с долгосрочной зависимостью этот параметр изменяется в границах 0,65-0,8 (процесс имеет продолжительную память). |