Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
8.5 Система с неограниченной очередью G/M/1/∞ В мультисервисных пакетных сетях связи входные информационные потоки могут иметь постоянную (CBR), переменную (VBR) и смешанную битовую скорость, от чего математическая модель потока может быть от простейшей пуассоновской до сложной модели фрактальних процессов (самоподобный трафик). Закон распределения интервала времени между требованиями в этих потоках может быть произвольный и потому в обобщенной модели резонно исследовать обобщенный (G) вид распределения случайной величины этого интервала. Длина пакетов каждой из служб общей для них мультисервисной сети (остюда и продолжительность обслуживания) может быть разной – для одних служб постоянной, а для других – переменной. В таком случае также желательно исследовать общий вид распределения случайной величины продолжительности обслуживания. Системы с очередью типа G/G/m/∞ – очень важные модели, рассматриваемые в теории телетрафика. При их исследовании применялись разные методы и получено много приближенных результатов. Частный случай – система с очередью и одним сервером (m = 1) рассматривался, например в [7], где получены только приближенные результаты. Однако, до сих пор в общем случае не существует простых и точных, непосредственно применяемых на практике, формул для расчета характеристик QoS в стационарном режиме. Во многих случаях односерверной системы хорошим приближением есть экспонентная функция распределения продолжительности обслуживания требований. Поэтому, определим характеристики QoS для модели G/M/1/∞ [14]. Коэффициент использования серверов системы ρ (utilization factor) определяется как отношение интенсивности входного потока требований λ к интенсивности обслуживания µ. В m-серверной системе все серверы обеспечат интенсивность обслуживания x m m 1 . Итак, в m-серверной системе m x . В односерверной системе ρ в m раз больше и совпадает с интенсивностью нагрузки Λ (5.3) или с интенсивностью входного потока требований λ, если x является одной условной единицей времени обслуживания. При условии 0 ≤ ρ < 1 процесс в системе эргодичен и стационарное распределение вероятностей состояний системы существует. Для всех односерверных систем ρ = 1 – p 0 , где p 0 – вероятность свобод- ности системы (состояние p 0 – занято 0 серверов). Итак, ρ – численно совпадает с вероятностью занятости системы P зн (состояние p 1 – занят единственный сервер, соответствует доле времени занятости сервера). С учетом требований очереди в стационарном режиме существует стационарное распределение количества требований в системе p k , где k – количество требований. Это распределение не зависит от момента прибытия требования в систему. При пуассоновском потоке вероятность ожидания P w>0 совпадает с вероятностью занятости системы P зн (см. 7.47). Для односерверной модели M/G/1/∞ с произвольным распределением длительности обслуживания данные вероятности одинаковы и P w>0 = ρ. Однако, для модели G/M/1/∞ такого 89 равенства нет, т.е. по этому параметру модели не инвариантны. В [5, с. 272] показано, что система G/M/1∞ приводит к геометрическому распределению r k количества требований в системе в моменты поступления новых требований, где k – количество требований. Распределение p k отличается от распределения r k тем, что p 0 = 1 – P зн (или p 0 = 1 – ρ), в то время как r 0 = 1– P w>0 . Для системы M/G/1/∞ выполняется равенство p k = r k Требование должно ожидать обслуживания с вероятностью P w>0 = 1 – r 0 Поэтому при экспонентном распределении длительности обслуживания безусловное распределение длительности ожидания найдем так: t w P w e P t W ) 0 1 ( м 0 1 ) ( , при t ≥ 0. (8.15) Из этого можно рассчитать среднее время ожидания в системе W и все остальные параметры качества обслуживания: зн Р ; N Р w 1 0 ; 0 0 1 w w Р Р W ; 0 0 1 w w Р Р Q ; 0 1 1 w q P T t ; 0 1 w P N Поскольку µ = 1, т.е. средняя длительность обслуживания x = 1 / µ принимается за условную единицу времени, то W, t q и T оцениваются в единицах средней длительности обслуживания. В табл. 8.1 приведены зависимости между основными параметрами QoS для модели G/M/1/∞. Таблица 8.1 – Зависимости между параметрами QoS в системе G/M/1/∞ Характеристика QoS Характеристика QoS Q W t q N Р зн P w>0 Q Q W W 1 q t 1 1 N 1 N Q Q – W ) 1 ( q t N 0 w P N W Q – 1 q t 1 N t q Q 1 W 1 – N N Q ) 1 ( W q t – 0 w Р Q T Q 1 W 1 q t N 90 Из таблицы следует, что при наличии лишь одного известного параметра (например, известен параметр Q, W, t q или N) все остальные параметры рассчитываются через приведенные в таблице соотношения. Для модели G/M/1/∞ выявлены и проверены с помощью имитационного моделирования важные свойства односерверной системы, выполняемые только при экспонентной длительности обслуживания (выделены рамкой в табл. 8.1). Во-первых, среднее время ожидания в очереди t q численно совпадает со средним временем пребывания требования в системе T. Это означает, что среднее время ожидания в системе W меньше среднего времени ожидания в очереди t q на величину средней длительности обслуживания (единица времени x ): 1 q t W (8.16) Во-вторых, вероятность ожидания можно определить как N Q P w 0 (8.17) По определению (6.2) вероятность ожидания P w>0 – это отношение количества задержанных требований к общему количеству поступивших требований, но как в данном случае, долю ожидающих требований можно определить и как отношение среднего количества требований в очереди Q к среднему количеству требований в системе N. Отсюда, с учетом формулы Литтла, вытекают несколько важных соотношений между параметрами QoS, справедливых уже для моделей G/G/1/∞ и G/G/m/∞ (в правой колонке табл. 8.1). Для системы GI/G/1/∞ Маршаллом предложена приближенная верхняя (High) оценка среднего стационарного времени ожидания W H [1]: ) ( 2 2 2 x z W x z H Нижняя (Low) оценка среднего стационарного времени ожидания W L предложена Штойяном в [7]: 2 ) ( 2 2 x x z W x L Анализ системы типа GI/G/1/∞, в которой учитывается вид функции распределения интервала времени между требованиями входного потока и продолжительности обслуживания требований, с помощью приведенных приближенных верхней и нижней оценок иногда дает более точный результат сравнительно с максимальными оценками, которые получаются при использовании марковских моделей. 91 8.6 Система с неограниченной очередью G/D/1/∞ В мультисервисных сетях связи трафик имеет сложную структуру, требующую для своего описания существенного усложнения математической модели потока требований. Закон распределения интервала времени между требованиями в этих потоках может быть произвольный и потому в модели, обслуживающей мультисервисный трафик, резонно исследовать обобщенный (G) вид распределения случайной величины этого интервала. В мультисервисных пакетных сетях требованием на обслуживание можно считать каждый отдельный пакет информации. Длина пакетов может быть неизменной при постоянной продолжительности их обслуживания, например, как в технологии ATM. В таком случае в исследованиях можно ограничиться только детерминированным законом распределения продолжительности обслуживания (D). Однако, и для переменной длины пакетов при анализе пакетных коммутаторов следует учитывать наличие у каждого пакета заголовка фиксированной длины, который требует учета в продолжительности обслуживания некоторого постоянного слагаемого, даже если распределение длин пакетов есть, например, экспонентным. Итак, разработка метода расчета основных характеристик качества обслуживания требований в системах, представленных моделью G/D/1/∞ также есть актуальной. В п. 8.7 показано, что для модели G/M/1/∞ с геометрическим распределением r k (распределение количества требований в системе в моменты поступления новых требований) при экспонентном законе распределения продолжительности обслуживания среднее время ожидания в системе W определяется как 0 0 1 w w Р Р W (8.18) С учетом этого результата и формулы Литтла в табл. 8.2 приведены формулы расчета характеристик качества обслуживания для модели G/M/1/∞ и известный результат для модели M/D/1/∞, который следует из формулы Поллачека-Хинчина (7.66). В формулы расчета характеристик QoS модели G/G/1/∞ введем величину t q – W (табл. 8.2). Правильность этого шага легко проверить подстановкой в каждую из них справедливого по определению для любой модели уравнения: q w t W P 0 Для расчета характеристик QoS модели G/D/1/∞ используем выявленное в п. 8.7 свойство модели G/M/1/∞, а именно: t q = T. Поскольку из определения среднего времени пребывания требования в любой системе (в том числе и в модели G/G/1/∞) следует, что 1 W T , (8.19) 92 то с учетом приведенного свойства модели G/M/1/∞ 1 W t q (8.20) Видно, что при выполнении условия (8.20), каждая из формул расчета характеристик QoS модели G/G/1/∞ совпадает с аналогичной формулой модели G/M/1/∞. Также известно, что для модели M/D/1/∞: 5 , 0 W t q (8.21) Поэтому, при выполнении условия (8.21) вместе с условием P w>0 = ρ, присущему пуассоновскому потоку, каждая из формул модели G/G/1/∞ превратится в соответствующую формулу модели M/D/1/∞ (столбики 4 и 2 табл. 8.2). Таблица 8.2 – Основные параметры качества обслуживания Модель G/G/1/∞ G * /D/1/∞ Хар-ка QoS M/D/1/∞ G/M/1/∞ точно приблизительно Р зн , 0 w q P t Q P w>0 N 1 q t W , q t Q Q ) 1 ( 2 2 0 0 1 w w P P ) ( 1 0 0 W t P P q w w ) 1 ( 2 0 0 w w P P W ) 1 ( 2 0 0 1 w w P P ) ( 1 0 0 W t P P q w w ) 1 ( 2 0 0 w w P P t q ) 1 ( 2 1 0 1 1 w P ) ( 1 1 0 W t P q w ) 1 ( 2 1 0 w P N ) 1 ( 2 2 0 1 w P ) ( 1 0 0 W t P P q w w ) 1 ( 2 ) 2 ( 0 0 w w P P T ) 1 ( 2 1 0 1 1 w P ) ( 1 1 0 0 W t P P q w w ) 1 ( 2 2 0 0 w w P P Если предположить, что условие (8.21) осуществимо и при P w>0 ≠ ρ, то с тех же формул модели G/G/1/∞ можно получить соответствующие формулы расчета характеристик QoS модели G/D/1/∞ (столбик 5 табл. 8.2). Но поскольку, как показывает имитационное моделирование, полученные таким образом формулы дают не совсем точные и разные результаты для разных входных потоков, то лучше назвать такую модель с условно общим распределением случайной величины интервала времени между требованиями и обозначить G * /D/1/∞. 93 Для модели G * /D/1/∞ разность (8.21) не всегда равна 0,5. По результатам имитационного моделирования, выполненного с помощью алгоритма [9], установлено, что для потоков, в которых коэффициент вариации продолжительности интервала времени между требованиями v z < 1 (более выровненный поток по сравнению с пуассоновским) t q – W < 0,5. Например, при равномерном распределении интервала времени между требованиями (модель U/D/1/∞) v z = 0,58. Для пуассоновского потока с экспонентным распределением указанного интервала при v z ≡ 1 или с распределением Вейбулла при подобранном коэффициенте формы распределения так, чтобы v z = 1, условие (8.20) выполняется. Для гиперэкспонентного, логарифмически нормального или распределений Парето и Вейбулла при параметрах распределений, которые обеспечивают значение v z от единиц до нескольких десятков (очень неравномерные потоки), разность t q и W всегда немного больше 0,5. В случае t q – W < 0,5 результаты расчетов немного выше результатов моделирования, при t q – W = 0,5 – они целиком совпадают, а при t q – W > 0,5 – результаты расчетов оказываются немного заниженными. При этом наибольшая погрешность вычислений по формулам модели G * /D/1/∞ сравнительно с результатами моделирования наблюдается в случае самоподобного потока требований, сгенерированному по распределениию Парето. Например, при задании параметра формы распределения a = 1,3 (соответствует коэффициенту самоподобности трафика H = 0,85 [13] и v z ≥ 30) погрешность вычислений не превышает 20 % для всех параметров QoS. При увеличении a и связанным с этим уменьшением H, например, до значений 1,9 и 0,55 соответственно (еще самоподобный процесс), данная погрешность не превышает уже 10 %. Следует отметить, что точность расчетов несколько повышается при уменьшении интенсивности нагрузка ρ и во многих случаях при ρ < 0,5 погрешность расчетов не превышает 5 %. Важность данного метода мотивируется существенным усложнением моделей трафика в современных сетях связи и отсутствием адекватных этому усложнению методов расчета параметров качества обслуживания. В особенности полезным данный метод может быть в случае обслуживания самоподобного трафика, поскольку его точность несравненно выше точности существующих методов расчета. 94 9 ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СМО 9.1 Метод статистических испытаний Математические модели функционирования СМО, рассмотренные в гл. 7 и 8, ориентированы на возможность получения в той или иной форме аналитических решений для обусловленных характеристик СМО. Возможность получения таких решений существенным образом ограничивается видом входных потоков, законом распределения длительности обслуживания и структурой СМО. Использование методов моделирования позволяет заметно ослабить ограничения, относящиеся к виду входных потоков требований. Поэтому, основным инструментарием исследования задач, не поддающимся аналитическим и численным методам, есть имитационное моделирование. Метод статистических испытаний (метод Монте-Карло) основан на моделировании исследуемого процесса. Основной его принцип – построение такой искусственной вероятностной модели, параметры которой представляют собой решение поставленной задачи. Если такая модель построена, то, пользуясь методами математической статистики, можно оценить неизвестные параметры, то есть найти приближенное решение задачи. Для моделирования процесса на ЭВМ необходимо превратить его математическую модель СМО в специальный моделирующий алгоритм. При статистическом моделировании реализация моделирующего алгоритма есть имитация элементарных явлений, составляющих исследуемый процесс, с сохранением их логической структуры, последовательности протекания во времени и в особенности характера и состава информации о состояниях процесса. Можно указать на имеющуюся аналогию с исследованием процессов в действительности. В том и другом случае есть возможность использовать для решения поставленных задач любую информацию о состояниях процесса, если только она доступна соответствующей регистрации. Отсюда следует, что структура моделирующего алгоритма может слабо зависеть от совокупности искомых величин, а определяется главным образом построением математической модели. При исследовании СМО этот метод позволяет учитывать: вид всех потоков событий; нестационарность потоков в системе; разного рода ограничения (например, ограничения на время пребывания в СМО); влияние состояния СМО на интенсивность потоков и т.п. Вместе с тем, результаты моделирования, как и при любом численном методе, всегда носят исключительный характер. Для получения качественных выводов нужно исследовать большое количество СМО, причем и в этом случае качественный результат может носить исключительный характер. В ряде случаев может сказываться принципиально ограниченная точность получаемых результатов, в особенности, если используется ЭВМ с небольшой длиной разрядной сетки. Необходимость наличия довольно мощной универсальной ЭВМ также может быть важным препятствием к использованию метода. Поэтому, несмотря на несомненные достоинства, метод имитационного моделирования не может заменить аналитических исследовательских приемов СМО, а является их дополнением. |