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

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

6.4 Приоритетные системы
В современных ТКС и сетях используется приоритетное обслуживание передаваемых и обрабатываемых данных. Аналитические методы исследования приоритетных дисциплин обслуживания требований разработаны, в основном, для дисциплин с одним классом приоритетов, и большинство результатов получено при разных допущениях и предположениях, ограничивающих их применение на практике. Поэтому, для исследования влияние приоритетов на характеристики QoS системы целесообразно применять моделирование.
Комбинированные системы с ограничениями на длину очереди и время ожидания наиболее распространены в телекоммуникациях. В условиях разнородного трафика (речь, видео, данные) такую систему дополняют механизмом приоритетов, в котором все требования разделяют на категории и требования более высокой категории при обслуживании имеют определенные преимущества (приоритеты) перед требованиями более низкой категории. Для количественной оценки качества обслуживания систем с приоритетами рассчитываются такие же характеристики, как и для системы с очередями, но для каждого из введенных приоритетов в отдельности. Например, среднее время ожидания в очереди требования k-гоприоритета, среднее количество требований в системе k-гоприоритета и т.п.
Примером системы с потерями может быть телефонная станция – абонент, являющийся инициатором телефонного вызова, получает отказ в обслуживании, если необходимый канал связи уже занят (технология коммутации каналов). Модель системы с очередью, комбинированной системы и с приоритетами применяема для сетей, базирующихся на технологии коммутации пакетов.

31
6.5 Пропускная способность и производительность
В любой из СРИ качество обслуживания сильно влияет на такие характеристики системы, как пропускная способность и производительность.
При этом, критерием качества обслуживания для систем с потерями есть вероятность потери требования, а для систем с очередями – вероятность ожида- ния. Чем больше допустимая норма потерь, тем хуже качество обслуживания.
Пропускная способность – это максимальная интенсивность нагрузки, обслуживаемая системой при обеспечении заданного качества обслуживания.
При малой вероятности потерь интенсивность обслуженной нагрузки близка к интенсивности входной и пропускная способность близка к интенсив- ности входной нагрузки. Однако при больших потерях это отличие велико, и ухудшение допустимого качества обслуживания позволяет увеличить пропускную способность. Чем выше норма качества обслуживания, тем больше серверов нужно для обеспечения заданной пропускной способности.
Пропускная способность системы не равна количеству серверов в ней, поскольку интенсивность обслуженной нагрузки – это среднее количество занятых серверов. Из-за случайности потоков нагрузки среднее количество занятых серверов не достигает имеющегося количества серверов в системе.
Задача состоит лишь в приближении среднего количества занятых серверов к количеству серверов системы.
Производительность – это предельное, статистически усредненное количество требований, обслуживаемые системой за единицу времени при заданном качестве обслуживания. Эта характеристика используется, как правило, для оценки систем управления и управляющих устройств.
Пропускная способность и производительность СРИ зависят не только от вероятности потерь, но и от структуры системы (количества серверов и схемы их включения), дисциплины обслуживания и закона распределения продолжи- тельности обслуживания.
На пропускную способность и качество обслуживания влияет и вид потока требований или его математическая модель.
При измерении пропускной способности СРИ важно понятие блокирова- ния требования – это событие, состоящее в отсутствии свободных и доступных путей соединения в нужном направлении в момент поступления требования (в момент попытки установления соединения). В системе с потерями блокирован- ные требования теряются и показателем пропускной способности есть доля потерянных требований.
Для системы с очередью различают неограниченную и ограниченную очереди (количество мест ожидания). Если накопитель очереди имеет неограниченную емкость, то основными характеристиками есть среднее время ожидания и вероятность ожидания (вероятность блокирования). В случае накопителя с ограниченной емкостью добавляется еще одна характеристика – вероятность потери требования, тогда вероятность блокирования равна сумме двух вероятностей – ожидания и потери требования.
В системе с повторными попытками подсчитывается количество повторных попыток на одно требование и прочие характеристики.

32
7 АНАЛИЗ СМО С ПУАССОНОВСКИМ ПОТОКОМ ТРЕБОВАНИЙ
Исследование работы СМО под влиянием случайных факторов возможно только с помощью случайных процессов. Случайный процесс – это функция
X(t), значения которой случайные величины. Выбор случайных процессов, используемых для описания и анализа систем, зависит от структуры и типа системы, от предположения о независимости или зависимости случайных величин в системе, от вида их функций распределений.
Если все функции распределения, характеризующие поведение элементов системы, экспонентные, то систему можно описать с помощью однородных непрерывных марковских цепей или их подвида однородных процессов
размножения и гибели, как модели СМО. При этом аналитическое определение величин, характеризующих систему, относительно несложно.
В условиях случайных потоков требований расчеты степени загружен- ности или пропускной способности и характеристик качества обслуживания ведутся на основе вероятностных функций распределениясостояний системы, определяющие эти характеристики. При пуассоновском потоке для определе- ния стационарных вероятностей состояний системы используется математичес- кий аппарат марковского процесса с составлением и решением системы линейных алгебраических уравнений равновесия. Состояние системы – это текущее количество требований, которые обслуживаются в серверах или ожидают в очереди. Изменение состояний системы – это случайный процесс, являющийся результатом общего процесса поступления и обслуживания требований. Закон распределения состояний системы, в отличие от среднего количества требований в ней (загруженности), более полно характеризует функционирования СМО под влиянием случайных факторов.
Самый эффективный математический аппарат анализа разработан для систем, работа которых описывается однородными цепями или процессами
Маркова. Характеристики марковских моделей определяются путем решения систем линейных уравнений (алгебраических, дифференциальных или интегральных). Гипотезы о марковости работы системы сильно ограничивают, поэтому в качестве математических моделей очень сложных реальных систем применят более общие классы случайных процессов. Марковости модели можно достичь усложнением фазового пространства моделирующего процесса.
Процесс есть марковский (без последействия), если для любого момента времени поведение системы в будущем зависит только от текущего состояния системы и не зависит от того, когда и как система в это состояние пришла.
Марковский процесс с дискретным пространством состояний – это цепь
Маркова. Множество {S} образует цепь Маркова, если вероятность того, что следующее состояние будет S
k+1
зависит только от текущего состояния S
k
, или влияние всей предыстории процесса сосредоточено на текущем состоянии.
В цепи Маркова поток случайных величин определяется только вероят- ностью перехода от предыдущего значения случайной величины (состояния системы) к следующему. Для однородной цепи Маркова вероятности этих переходов не зависят от номера шага, на котором система достигает опреде-

33 ленного состояния. В соответствии с теоремой Маркова, если количество сос- тояний системы S конечно, и из каждого состояния можно перейти за опреде- ленное количество шагов в любое другое состояние, то предельные вероят- ности состояний существуют и не зависят от начального состояния системы.
Условием применения цепей Маркова для нахождения вероятностей сос- тояний системы есть экспонентное распределение интервалов времени между требованиями потока. Экспонентное распределение единственное из всех непрерывных законов, имеющее свойство отсутствия последействия. Оно означает: если продолжительность интервала между требованиями экспонен- циальная, то с любого момента от начала этого интервала остаток времени до его конца не зависит от событий до этого момента, и будет иметь тоже экспоненциальное распределение с тем же параметром, что и весь интервал.
Экспонентное распределение интервалов времени между требованиями вызывает пуассоновское распределение количества требований за условную единицу времени и поэтому свойство отсутствия последействия переносится и на пуассоновский поток требований, который вместе с тем есть:
 стационарным, так как вероятность количества требований на отрезке времени зависит только от продолжительности этого отрезка и не зависит от того, где именно на оси времени он размещен;
 ординарным, так каквероятность поступления более одного требова- ния за бесконечно малый отрезок времени есть бесконечно малой сравнительно с вероятностью поступления ровно одного требования
(это означает, что требования поступают только по одному);
 без последействия, так как для любых отрезков времени, которые не пересекаются, количество требований одного отрезка не зависит от того, сколько требований поступило на другом.
Для такого потока интенсивность λ, то есть среднее количество требований на единицу времени, есть величина постоянная (неизменная).
Если в модели не все распределения экспонентные, ищут такие аналитические приемы, которые приводят исследуемые процессы к
марковским, или ищут такие моменты времени, в которых процесс становится
марковским. Далее простыми методами дискретных марковских цепей вычисляются искомые величины или вероятности, характеризующие состояние системы, после чего они превращаются в соответствующие величины исходного процесса. Для решения задач такого типа применяются методы полумарковских процессов или вложенных цепей Маркова. Однако, реальные результаты с применением этих методов полученные для небольшого класса систем (например, формула Поллачека-Хинчина для системы типа M/G/1/∞), или получены только частичные и приближенные результаты (например, для систем типа M/G/m/∞, GI/G/1/∞ и др.).
При максимальной точности описания работы реальных сложных систем соответствующие математические модели становятся все более и более сложными. При этом усложняется их математический анализ, аппарат анализа становится громоздким и часто недоступным в инженерной практике.

34
7.1 Система с потерями M/M/m
Полнодоступная схема СРИ с m серверами обслуживает пуассоновский поток требований по дисциплине с потерями. Интервал времени между требованиями и длительность обслуживания распределены экспоненциально.
Параметр потока требований λ, а средняя продолжительность обслуживания –
x
. Определить стационарное распределение вероятностей состояний системы
P
k
(k = 0 … m) и характеристики качества обслуживания (QoS).
Для ординарного потока интенсивность поступления требований совпадает с параметром потока λ. Совокупность моментов завершения обслуживания требований образуют поток освобождения серверов системы с параметром µ, называемый интенсивностью обслуживания требований и рассчитываемый как обратная величина к продолжительности обслуживания:
x
1


(7.1)
Дискретные состояния системы S
k
изменяются при каждом поступлении требования или окончании его обслуживания. Цепь Маркова с конечным количеством состояний изображается в виде диаграммы переходов (рис. 7.1).
Рисунок 7.1 – Диаграмма переходов m-серверной системы с потерями
Для пуассоновского потока интенсивность поступления требований λ постоянна. Если система находится в состоянии S
k и поступает требование, то система переходит с одинаковой интенсивностью λ в состояние S
k+1
при любом
k. При окончании обслуживания требования интенсивность, с которой система переходит из состояния S
k
в состояние S
k-1
, зависит от количества занятых серверов или текущего состояния системы. Если, например, система находится в состоянии S
1
, то по окончании обслуживания требования, занимающего один сервер, система переходит в состояние S
0
с интенсивностью µ. Если система в состоянии S
2
, то она может перейти в состояние S
1
с интенсивностью уже 2µ, поскольку может закончиться обслуживание любого из двух требований, занимающих два сервера системы, и т.д. Если обслуживанием заняты k
серверов, то поток освобождения серверов, переводящих систему из состояний
S
k
в S
k-1
, будет в k раз интенсивнее.
Стационарное распределение вероятностей состояний системы P
k
для однородной дискретной цепи Маркова определяется системой линейных алгебраических уравнений:


i
k
i
i
k
p
P
P
,
,
(7.2)
…
S
m
λ
λ
λ
λ
2µ
µ
3µ
…
kµ
S
0
S
1
S
2
S
3
λ
S
m

35 где p
i,k
– вероятность перехода системы из состояния i в состояние k [5]. При этом распределение (7.2) должно удовлетворять условию нормировки



m
k
k
P
0 1
Сумма в (7.2) вычисляется для всех возможных вариантов состояний i, из которых можно перейти в состояние k. В случае ординарного потока в это состояние можно перейти только из состояний k – 1, k и k + 1. Поэтому, за счет уменьшения количества возможных вероятностей p
i,k
система уравнений (7.2) сократится:
k
k
k
k
k
k
k
k
k
k
p
P
p
P
p
P
P
,
1 1
,
,
1 1







(7.3)
Переход из состояния k – 1 в состояние k возможен в случае поступления требования, вероятность чего пропорциональна параметру λ, а переход из k + 1 в состояние k возможен в случае окончания обслуживания требования, вероятность чего при экспонентном распределении продолжительности обслуживания х пропорциональна параметру µ. Поэтому, вероятность p
k-1,k
= λ, а вероятность p
k+1,k
= µ(k + 1) (см. рис. 7.1).
Вероятность перехода системы из состояния k в состояние k очевидна – система не может перейти из состояния k ни в состояние k – 1, ни в состояние
k + 1, так как её состояние неизменно:










k
p
p
p
k
k
k
k
k
k
1 1
1
,
1
,
,
(7.4)
Итак, из (7.3) с учетом (7.4) в итоге имеем
1 1
)
1
(
]
1
[












k
k
k
k
P
k
k
P
P
P
(7.5)
После раскрытия скобок и объединения последовательно получаем:
1 1
)
1
(












k
k
k
k
k
k
P
k
P
kP
P
P
P
,
1 1
)
1
(
)
(
0











k
k
k
P
k
P
k
P
, а после переноса:
1 1
)
1
(
)
(










k
k
k
P
k
P
P
k
(7.6)
Система уравнений (7.6) описывает стационарный режим в цепи Маркова и является математической моделью процесса обслуживания требований потока. В этом режиме выполняется закон сохранения интенсивности вероятностей – интенсивность потока вероятностей в состояние k равна интенсивности потока из этого состояния в состояния k – 1 или k + 1. Поэтому
(7.6) является уравнением равновесия или баланса.
Решение уравнения баланса начнем со значения k = 0, при котором из
(7.6) получаем
1 1
0
P
P
P






Вероятность P
–1
≡ 0 как вероятность несуществующего состояния и потому
1 0
P
P



, откуда следует, что:
0 1
P
P



При k = 1 из (7.6) получаем
2 0
1 2
)
(
P
P
P







и потому

36 0
2 0
1 2
1 2
1 2
2
P
P
P
P


















При k = 2 из (7.6) получаем
3 2
3
)
2
(
1
P
P
P







и потому
0 3
0 2
3 1
2 3
1 2
3 3
P
P
P
P





















Без продолжения из приведенных расчетов (индукции) видно, что
1




k
k
P
k
P
,
(7.7) и
0
!
1
P
k
P
k
k









(k = 1, 2, … m)...
(7.8)
С учетом условия нормировки, внесенного в стационарное распределение вероятностей состояний системы (7.2), вероятность P
0
определится так:
1 0
0
!
1




















m
i
i
i
P
(7.9)
Распределение (7.8) является искомым стационарным распределением вероятностей состояний полнодоступной системы с потерями, обслуживающей пуассоновский поток требований.
Данная задача впервые решена
А.К. Эрлангом в предположении об экспонентном распределении продолжительности обслуживания, но со временем доказано, что (7.8) верно для любого произвольного закона, то есть и для модели M/G/m.
Относительная простота решения данной задачи поясняется следующим.
Здесь исследуется стационарный режим системы, которая достигается системой на бесконечном отрезке времени, когда система обслуживания работает в состоянии статистического равновесия. Для того чтобы полученные вероятности состояний системы (количества занятых серверов) не зависели от того, в каком состоянии система была в начальный момент, данный процесс должен быть эргодическим. В соответствии с теоремой Маркова любой
транзитивный (из любого состояния можно перейти в любое другое)
однородный (вероятности перехода из состояния в состояние не зависят от того, в какой момент времени начало перехода) процесс с конечным количеством состояний имеет эргодическое свойство [6, с. 149]. Для любого марковского процесса, имеющего эргодическое свойство, после довольно продолжительного времени функционирования системы обязательно наступит стационарный режим, где вероятность того, что система будет в k-м состоянии, не зависит от того, в каком состоянии она находилась в начальный момент времени.
Соответственно указанному в эргодической теореме [7] достаточному критерию эргодичности марковского процесса, процесс будет эргодическим, если выполняется условие:

37
m



(7.10)
Это означает, что в среднем должно поступать меньше требований, чем их можно обслужить, или среднее количество требований за единицу времени обслуживания не должно превышать количества серверов.
С учетом (5.3) и (7.1) выясняется, что параметром стационарного распределения вероятностей состояний системы
(7.8) и
(7.9) есть интенсивность входной нагрузки Λ, и, таким образом, можно записать:





m
i
k
k
i
i
k
P
0
!
! (k = 1, 2, … m)...
(7.11)
Распределение (7.11) называется первым распределением Эрланга, по которому можно рассчитать вероятность занятости k серверов полнодоступной
m-серверной системы с потерями при обслуживании пуассоновского потока требований.
Для состояния k = m из (7.11) получаем B-формулу Эрланга, обозначаемую как E
m
(Λ), и по которой можно рассчитать основную характеристику качества обслуживания потока требований – вероятность потери требования P
В
(6.1). Для упрощения вычислений значения E
m
(Λ) приводятся в таблицах Эрланга.
Фактически при k = m из (7.11) получаем значение вероятности занятия всех серверов системы или вероятности потерь по времени (см. гл. 6).
Очередное требование, поступающее в систему, будет утрачено
(заблокировано) в том случае, когда все серверы заняты. Но только при условии пуассоновского потока значение вероятности занятия всех серверов системы совпадает с вероятностью потери требования независимо от того, поступает в этот момент требование или нет. Из-за свойства отсутствия последействия интенсивность поступления требований не зависит от состояния системы.
Для односерверной системы M/G/1 из (7.11) при условии m = 1 можно рассчитать:
– вероятность того, что сервер свободный P
0
:



1 1
0
P
;
– вероятность того, что сервер занятый P
1
:











1
)
(
1 0
1
N
Y
E
P
P
P
m
B
;
Как видим, вероятность P
1
совпадает с вероятностью потери требования
P
B и с интенсивностью обслуженной нагрузки Y, а также со средним количеством требований в системе N .

38