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

• Название: Учебник для студентов высших учебных заведений, обучаемых по направлениею
• Анкор: Приложения теории массового обслуживания
• Дата: 30.06.2022
• Размер: 1.27 Mb.
• Имя файла: lozhkovskii_ag_teoriia_massovogo_obsluzhivaniia_v_telekommun.pdf
• Тип: Учебник; #621010
• страница: 10 из 14

7.8 Модель обслуживания мультисервисного трафика
В мультисервисных сетях связи, основанных на пакетных технологиях передачи информации, по общим трактами связи передаются речевые потоки, потоки данных, видео и др. При этом передача отдельных видов информации требует разных скоростей передачи. Поэтому в зависимости от категории требования на предоставление определенного сервиса (услуги) для каждого из потоков информации необходимо занять определенный ресурс из общего ресурса пропускной способности (Кбит/с). Например, передача речи требует гарантированной скорости передачи 64 Кбит/с, связь видео-конференции с кодеком H.263 – 320 Кбит/с, обмен файлами, например, 1024 Кбит/с [17]. Для распределения общего ресурса скорости передачи между этими услугами весь ресурс можно представить определенным количеством условных портов, где скорость передачи каждого составляет минимальную скорость одной из услуг.
В данном случае скорость передачи одного условного порта составит 64 Кбит/с и, в зависимости от категории требования, выполняется одновременное занятие одного или нескольких портов, через которые передаются пакеты с заданной битовой скоростью. Таким образом, при поступлении требования на предоставление услуги передачи речи будет одновременно занят 1 порт, на видео-конференцсвязь – 5, а на передачу файлов – 16 условных портов.
Примечание.
1. Без изменения сущности модели масштаб скорости передачи условного порта может быть и другим. Например, она может быть кратной скорости передачи одного или нескольких пакетов переданной информации.
Таким образом, изменяется только количество занимаемых условных портов, каждый из которых представляет собой ячейку памяти накопления и передачи пакетов.
2. При поступлении требования на предоставление определенного сервиса устанавливается соединение между соответствующими потребителями сервиса, а потом в границах этого соединения переда- ются информационные пакеты с заданной для сервиса скоростью.
Каждое требование требует установления одного соединения.
В такой модели обслуживания мультисервисного трафика надо отличать поток требований на предоставление сервиса от потока занятия портов, поскольку они сильно отличаются по своим свойствам. Очевидно, если поток требований на предоставление сервиса ординарный, то поток занятия портов будет неординарным, так как для обслуживания отдельных соединений порты занимаются группами. С учетом указанного обстоятельства следует различать и два понятия нагрузки: нагрузка по требованиям и нагрузка на порты.
Для СМО (системы серверов) мгновенная интенсивность обслуженной нагрузки по требованиям в момент времени t имеет значения j(t), что равно количеству одновременно обслуживаемых требований (соединений). В отличие от этого, интенсивность обслуженной нагрузки на порты – это количество i(t) одновременно занятых портов в момент t. В общем случае i(t) ≠ j(t), так как одно требование (соединение) может занимать сразу несколько портов.

68
Аналогично надо различать соответствующие виды входной нагрузки: по требованиям и на порты. Мгновенная интенсивность входной нагрузки по требованиям в момент времени t есть случайная величина, равная количеству требований, обслуживаемых в этот момент в СМО с бесконечным количеством одновременных соединений (см. п. 5.1: один сервер – одно соединение).
Рассмотрим частный случай, когда для обслуживания каждого входного требования необходимо одинаковое количество m свободных портов. Тогда в любой момент времени обслуженная нагрузка на порты будет в m раз больше нагрузки по требованиям: i(t)= mj(t). Если поток требований экспоненциальный и характеризуется параметром λ, то входная нагрузка по требованиям будет пуассоновской, а её математическое ожидание Λ
В
и дисперсию D
В
можно вычислить с помощью следующего соотношения:
x
D
В
В




, где x – среднее время обслуживания одного требования (соединения).
В воображаемой системе с бесконечным количеством портов, как и в реальной, количество занятых портов будет в m раз больше количества обслуженных требований (соединений). Отсюда следуют формулы, по которым можно определить интенсивность входной нагрузки на порты и ее дисперсию:
x
m
m
В
П





,
x
m
D
m
D
В
П



2 2
(7.98)
Здесь применяется правило, известное из теории вероятностей: если случайная величина увеличивается на постоянный коэффициент, то на этот же коэффициент нужно умножить ее математическое ожидание, а дисперсия должна увеличиваться на коэффициент в квадрате.
Из этих формул видно, что D
П
> Λ
П
, и нагрузка есть скученной из-за неординарности потока занятий портов. Коэффициент скученности S
П
(5.4) равен количеству портов, необходимых для обслуживания одного требования:
m
x
m
x
m
D
S
П
П
П






2
(7.99)
При поступлении требований от источников разных категорий формулы
(7.98) справедливые для математического ожидания и дисперсии нагрузки на порты, которая создается требованиями i-й категории, i = 1, …, n:
i
i
i
i
x
m 


,
i
i
i
i
x
m
D


2
Подставляя эти соотношения в формулу (5.8) и (5.7), можем найти коэффициент скученности объединенной нагрузки на порты:













n
i
i
i
i
n
i
i
i
i
n
i
i
n
i
i
П
x
m
x
m
D
S
0 0
2 0
0
(7.100)
Коэффициент скученности мультисервисной нагрузки равен средневзве- шенному количеству портов m, необходимых для обслуживания требований отдельных категорий, с весами
i
i
i
x
m 
, которые равны интенсивности нагрузки на порты, создаваемой требованиями этих категорий, i = 1, …, n.

69
7.8.1 Аппроксимация Хейворда
На полнодоступную систему из V портов поступает пуассоновский поток требований с интенсивностью λ, причем каждое требование требует для своего обслуживания одновременно т портов, т > 1. Порты занимаются на случайное время обслуживания, средняя продолжительность которого равна x . В случае завершения обслуживания все порты из группы одновременно освобождаются.
Если в момент поступления требования в системе отсутствует необходимое количество свободных портов, то требование теряется.
При расчете вероятности потерь требований π для анализируемой систе- мы, названной системой U, непосредственное применение B-формулы Эрланга невозможно из-за неординарного потока занятий портов. Вместо этого исследуем видоизмененную систему U’, состоящую из v = V / m комплектов, каждый из которых содержит т портов. Теперь каждому входному требованию для обслуживания будет необходим один комплект и потому поток занятия комплектов ординарный. Нагрузка в системе U’ определяются количеством занятых комплектов (а не портов), т.е. совпадает с нагрузкой по требованиям и есть пуассоновской с интенсивностью Λ
В
= λ x . Поэтому, для расчета вероятности потерь требований в системе U’ применяем B-формулу Эрланга:








v
i
i
В
В
v
i
v!
E
0
'
!
)
(
С точки зрения статистических характеристик процесса обслуживания требований, системы U и U’ целиком эквивалентны и, в частности, очевидно, что π = π'. Отсюда с учетом соотношений (7.99) и (7.100) следует:





 








П
П
S
V
S
E
п
(7.101)
Итак, когда мультисервисная нагрузка создается несколькими категориями источников с разной кратностью требований m
i
, суперпозицию входных потоков можно заменить одним потоком, который имеет такие же значения математического ожидания Λ
П
и дисперсии D
П
нагрузки на порты.
Хотя в действительности непуассоновськие потоки имеют довольно сложные статистические свойства, и для полного описания таких потоков нужно использование большего количества характеристик, на практике обычно предполагают, что вероятность потери требования слабо зависит от моментов распределения нагрузки более высокого порядка и их можно не учитывать.
Если известна вероятность потерь требований π в некоторой системе из V портов при мультисервисной нагрузке с интенсивностью Λ
П
и коэффициентом скученности S
П
, то в любой системе с такими же параметрами V, Λ
П
и S
П
потери требований будут приблизительно равны π.
Вычислив коэффициент скученности объединенного потока требований по формуле (7.100), можем потом при помощи соотношения (7.101) определить

70 вероятность потери любого требования, что дает приближенную оценку средних (или общих) потерь. Для разных категорий источников нагрузки требования теряются при разных состояниях системы и, как следствие, вероятностные характеристики качества обслуживания требований отличаются.
Для расчета индивидуальных потерь, то есть вероятности потерь требований i-й категории, при i = 1, …, n, можно применить приближенное соотношение:



i
i
i
S
m
Таким образом, при обслуживании мультисервисной нагрузки, имеющей непуассоновский характер, расчет потерь требований в исходной системе заменяется аналогичной задачей для эквивалентной системы, где такая задача может быть решена с использованием B-формулы Эрланга. Сравнительный анализ такого подхода и имитационного моделирования свидетельствует, что предлагаемые приближенные формулы имеют точность, целиком достаточную для решения инженерных задач.
Формула (7.101) называется формулой или аппроксимацией Хейворда и ее обоснование исследовано в некоторых научных работах [18].
7.8.2 Пример расчета вероятности потерь
На систему из V = 45 портов поступают требования п = 2 категорий.
Поток требований сервиса телефонии (1-я категория) с параметрами:
λ
1
= 0,14 требования за 1 с,
100 1

x
с, m
1
= 1.
Поток требований сервиса видео-телефонии (2-я кат.) с параметрами:
λ
2
= 0,05 требования за 1 с,
56 2

x
с, m
2
= 5.
Определить общие (средние) и индивидуальные потери требований.
Решение задачи.
Общая интенсивность нагрузки на порты от источников всех категорий:
Λ
П
=
1 1
1
x
m 
+
2 2
2
x
m 
= 1 ∙ 0,14 ∙ 100 + 5 ∙ 0,05 ∙ 56 = 28 (Эрл).
Дисперсия нагрузки на порты от источников всех категорий:
D
П
=
1 1
2 1
x
m 
+
2 2
2 2
x
m 
= 1 2
∙ 0,14 ∙ 100 + 5 2
∙ 0,05 ∙ 56 = 84.
Коэффициент скученности нагрузки:
S
П
= D
П
/ Λ
П
= 84/28 = 3.
По формуле Хейворда и из таблиц B-формулы Эрланга определяем среднюю вероятность потерь для общего входного потока требований:





 










П
П
П
S
E
S
V
=












3 28 3
45
E
= E
15
(9,33) = 0,027.
Индивидуальные вероятности потерь для требований 1-й и 2-й категорий:
π
1
= (m
1
/ S
П
) ∙ π = (1/3) ∙ 0,027 = 0,009,
π
2
= (m
2
/ S
П
) ∙ π = (5/3) ∙ 0,027 = 0,045.
С таким качеством система с пропускной способностью 45 ∙ 64 Кбит/с =
2,88 Мбит/с обслуживает нагрузку сервисов телефонии и видео-телефонии.

71
8 АНАЛИЗ СМО В УСЛОВИЯХ РЕАЛЬНОГО ПОТОКА ТРЕБОВАНИЙ
Интегральный характер мультисервисных сетей с широким спектром услуг предопределяет разнородность трафика, которая сильно изменяет его параметры и математическую модель. Параметры трафика – это интенсивность нагрузки Λ (среднее количество требований, поступивших в систему за среднюю длительность обслуживания) и дисперсия интенсивности нагрузки σ
2.
Математической моделью трафика есть вероятностная функция распределения случайного количества требований i за среднюю длительность обслуживания x.
В модели пуассоновского потока требований интервал времени между требованиями z распределен по экспонентному закону. Степень отклонения других потоков от пуассоновского можно оценить по коэффициенту вариации
ν
z
функции распределения интервала z. Для экспонентного распределения
ν
z
≡ 1. Модель пуассоновского потока не всегда адекватно описывает реальные потоки требований в телекоммуникациях и потому нужны иные распределения для их описания, обеспечивающие лучшее согласие с данными измерений.
Замена экспонентного распределения другими функциями заметно усложняет модель, а сложные модели не всегда поддаются аналитическому решению.
Реальные потоки требований в мультисервисных сетях формируются множеством источников с разной удельной интенсивностью нагрузки (разно- родные потоки). В процессе создания потока требований участвуют источники, принадлежащие к разным группам потребителей сервисов с близкими интенсивности нагрузки. Значения интенсивности результирующего потока требований в каждый момент времени зависит от того, к какой группе по интенсивности нагрузки принадлежит источник и каково соотношение численности этих источников. Более адекватно описать поток или распределе- ние интервалов времени между требованиями можно не экспонентным распре- делением (M), а их смесью – гиперэкспонентнымраспределением (HM):
z
i
k
i
i
i
e
p
z
P






1
)
(
при
1 1



k
i
i
p
Этому распределению соответствует прерывистый пуассоновский поток
k-го порядка. Практические измерения показывают, что реальные потоки достаточно аппроксимировать с k = 2. Так можно описать больший разброс величины интервала времени между требованиями z и обеспечить значения коэффициентов ν
z
≥ 1, а это позволяет описывать потоки с дисперсией интен- сивности нагрузки σ
2
, превышающей ее математическое ожидание Λ от единиц до десятков раз. Соотношение σ
2
и Λ иногда называется пикфактором трафика.
Гиперэкспонентный интервал времени между требованиями приводит к такому распределению количества требований на интервале в среднюю длительность обслуживания, которое хорошо аппроксимируется нормальным
(Гаусса) законом. Для реальных потоков требований мультисервисных сетей связи адекватна математическая модель с гиперэкспонентным распределением интервала времени между требованиями, количество которых на интервале времени аппроксимируется нормальным распределением.

72
8.1 Функция распределения состояний системы с потерями HM/D/m
Полнодоступная схема СМО с m серверами работает по дисциплине обслуживания с потерями. Длительность обслуживания постоянная и равна
x
В систему поступает поток требований с интенсивностью Λ, а интервал между требованиями с гиперэкспонентным распределением. Количество требований в единицу времени
x
распределено по нормальному закону Определить стационарное распределение вероятностей состояний системы P
k
(k = 0, …, m)...
Состояние системы определяется количеством занятых серверов. Случай- ный процесс поступления требований модифицирует состояния системы со скоростью, обусловленной интенсивностью нагрузки Λ. Здесь Λ – это суммар- ное количество требований j, поступивших за время средней длительности обслуживания
x
. Интенсивность перехода системы из одного состояния в другое зависит от свойств потока требований, описываемого соответствующим распределением вероятностей Q
j
, где j в диапазоне от 0 до ∞ – количество требований за время
x
. Все события поступления требований принадлежат пространству состояний Q. События занятия серверов образуют новое дискрет- ное подпространство P, описываемое распределением вероятностей P
i
, где i – количество занятых серверов (i = 0, …, m). Пространство P меньше простран- ства Q, ибо состояния i > m для системы невозможны, а j может быть огромно.
В системе с потерями независимо от ее текущего состояния для каждого из случаев поступления j > m требований происходит событие „отказ в обслуживании”. Это очевидно, ибо за время
x
(постоянная длительность занятия серверов) поступит j > m требований и ни один из вновь занятых серверов за это же время не освободится. Если система находится в начальном состоянии i = 0 (все серверы свободные), то для каждого из вариантов поступления за один и тот же отрезок времени j  m требований событие „отказ в обслуживании” не произойдет. События поступления за время
x
точно j
требований, образуют полную группу несовместных гипотез H
0
, H
1
, … , H
j
с априорными вероятностями Q(H
0
), Q(H
1
), … , Q(H
j
) и потому
1
)
(
0




j
j
H
Q
.
Событие A, состоящее в „отсутствии отказа в обслуживании” может произойти только вместе с одной из гипотез группы H
0
, H
1
, …, H
m
. Условные вероятности гипотез поступления j  m требований (апостериорные), при условии осущест- вления события A (отсутствие потерь) вычисляются по формуле Байеса:



m
k
k
k
j
j
j
H
A
Q
H
Q
H
A
Q
H
Q
A
H
Q
0
)
|
(
)
(
)
|
(
)
(
)
|
(
(8.1)
Так как событие A (отсутствие отказа в обслуживании), появляющееся с каждой из гипотез группы H
0
, H
1
, …, H
m
есть достоверным, то условные вероятности Q(A|H
j
)= 1. Поэтому, если для осуществления события возможна только часть гипотез, а другие невозможны, то для получения апостериорных вероятностей надо каждую из априорных вероятностей этой части возможных гипотез разделить на их сумму. Поэтому:

73



m
k
k
j
H
Q
j
H
Q
A
H
Q
0
)
(
)
(
)
|
(
Для системы, будущей в начальном состоянии (все серверы свободны), условные вероятности Q(H
j
|A) соответствуют вероятностям занятия i = j
серверов, т.е. вероятностям P
i
. Онитакже образуют полную группу несовмест- ных событий подпространства P и потому
1 0



m
i
i
P
. Итак, вероятности занятия серверов P
i
представлены через вероятности поступления требований Q(H
j
), т.е.



m
k
k
i
i
H
Q
H
Q
P
0
)
(
)
(
(8.2)
Условием стационарности распределения есть эргодичность процесса обслуживания требований. Это значит, что полученные вероятности состояний системы (количества занятых серверов) не должны зависеть от того, в каком состоянии система была в начальный момент времени (принято, что в начальный момент все серверы свободны). Известно, что свойство эргодичности имеют марковские процессы и для любого такого процесса после довольно продолжительного времени работы системы обязательно настанет стационарный режим, где вероятность того, что система будет в i-м состоянии, не зависит от того, в каком состоянии она находилась в начальный момент времени. Соответственно теореме Маркова условием эргодичности процесса есть (7.10) и тогда система работает в состоянии статистического равновесия.
Подставив в (8.2) вместо вероятностей Q(H
i
) вероятности из распределе- ния Пуассона (7.48), получим первое распределение Эрланга (7.11), верное для модели M/G/m, и по которому рассчитываем вероятности всех состояний системы. Однако, в этом случае математическое ожидание случайного процесса поступления требований с интенсивностью Λ равно его дисперсии σ
2.
Но если в
(8.2) вместо вероятностей Q(H
i
) и Q(H
k
) подставить вероятности, найденные по нормальному закону, то будет формула расчета состояний модели HM/D/m:






























m
k
m
k
k
i
i
i
k
i
k
e
e
P
0 2
0 2
/
)
(
2
/
)
(
2
)
)(
2
(
exp
1 2
1 2
1 2
2 2
2
. (8.3)
При σ
2
= Λ нормальный случайный процесс есть марковским и при этом в соответствии с (7.10) при Λ < m расчетные значения, получаемые по формулам распределения Эрланга (7.11) и (8.3) довольно близки – расхождение не более
1 %. При σ
2
> Λ распределение интервалов времени между требованиями уже не экспоненциально и поток требований теряет свойство отсутствия последействия. Процесс обслуживания становится сложнее и возникает зависимость вероятностей состояний системы от ее начального состояния.

74
Возникает зависимость и от вида распределения продолжительности обслуживания требований, в отличие от распределения Эрланга, верного при любом законе распределения длительности обслуживания.
Поэтому, вероятность занятия всех серверов системы уже не совпадает с вероятностью отказа в обслуживании, как это наблюдается при пуассоновском потоке.
Данную задачу для модели HM/D/m можно решить и другим способом.
В условиях неограниченного количества серверов (модель HM/D/∞) требования обслуживаются без потерь. При постоянной длительности обслуживания x, когда нет потерь, свойства потока освобождений совпадают со свойствами потока поступления требований, так как происходит только сдвиг во времени на величину x между моментом поступления требования и моментом его выхода из системы (завершения обслуживания). При этом, состояния системы полностью определяются свойствами потока требований, а вероятностные функции распределения количества требований в системе i и поступающего за время x количества требований j, полностью совпадают. При нормальном распределении количества требований, поступающих в систему за среднюю длительность их обслуживания, нормальная функция распределения потока требований P
j
определит функцию распределения состояний системы P
i
:


2 2
2 2
1








i
i
j
e
P
P
(8.4)
При ограниченном до m количестве серверов пространство состояний системы также ограничено от 0 до m. Вероятностную функцию распределения состояний системы HM/D/m можно аппроксимировать усеченным нормальным законом, определяющим вероятности состояний системы P
i
при 0 ≤ j ≤ m:


2 2
2 2







j
i
e
A
P
,
(8.5) где

























0 0
2 0
2 2
2 2
1 1
du
e
du
e
A
u
m
u
Если m = ∞, то A = 1 и потому (8.4) и (8.5) совпадают. При всех других m значения формул (8.3) и (8.5) совпадают, что подтверждает правильность обеих способов решения задачи. Для (8.3), (8.4) и (8.5) выполняется
1 0



m
i
i
P
На рис. 8.1 даны графики аппроксимации функции распределения состоя- ний системы, обслуживающей поток с параметрами: интенсивность Λ = 100
Эрл и дисперсия σ
2
= 400 (пикфактор σ
2/
Λ = 4). Пунктирная линия – система с неограниченным количеством серверов, где m = ∞, непрерывная – система с
m = 125, штриховая – с m = 115 и штрихпунктирная – с m = 110 серверов.

75
Рисунок 8.1 – Аппроксимация состояний усеченным нормальным законом
В широком диапазоне изменения параметров трафика  и σ
2
и количества серверов m относительная погрешность предложенной аппроксимации усеченным нормальным законом не превышает 1% для всех значений P
i
, кроме
P
j=m
. Процесс обслуживания требований в системе является эргодическим или не зависит от начального состояния системы при условии m > Λ [2]. Если количество серверов m существенно превышает значение интенсивности Λ, то начальное состояние системы не оказывает большого влияния на функцию распределения состояний системы. При уменьшении m начальное состояние системы проявляет свое наибольшее влияние именно на вероятность P
i=m
. Это происходит из-за „скученности” потока требований реального трафика, которая следует из его свойства σ
2
> Λ. Именно в случае „перегрузки” системы, когда заняты все серверы, при освобождении любого из серверов он тут же занимается очередным требованием из-за скученности требований на данном интервале времени, а это поддерживает систему более продолжительное время в состоянии „насыщения”, то есть в состоянии P
i=m
При σ
2
≡ Λ законы Гаусса и Пуассона почти совпадают уже при Λ > 20.
Здесь данное усеченное нормальное распределение дает значения вероятностей состояний системы, очень близкие к значениям, получаемых по распределению
Эрланга (7.11), которым определяются состояния системы типа M/G/m с экспонентным распределением интервала времени между требованиями потока и где σ
2
≡ Λ. Гиперэкспонентное распределение при k = 1 обращается в экспонентное и оно есть обобщающим. В отличие от распределения Эрланга, верного при любом (G) законе распределения длительности обслуживания, усеченное нормальное распределение состояний системы при σ
2
> Λ верно только для модели HM/D/m, т.е. для постоянной длительности обслуживания.
Регулярным (постоянным) законом распределения длительности обслу- живания описывается работа управляющих устройств узлов коммутации или длительность обработки пакетов в пакетных сетях передачи данных, где потоки не есть пуассоновскими. Здесь применение данной аппроксимации адекватно.

76