Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами
Розроблено алгоритмічний підхід для дослідження моделі обслуговування з обмеженими чергами і стрибкоподібними пріоритетами. Передбачено, що при надходженні виклику низького пріоритету один виклик такого типу з певною ймовірністю може перейти в чергу викликів високого пріоритету. Ймовірність переходу...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2012 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207548 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2012. — № 6. — С. 114–124. — Бібліогр.: 16 назв. - рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860014360046338048 |
|---|---|
| author | Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон |
| author_facet | Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон |
| citation_txt | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2012. — № 6. — С. 114–124. — Бібліогр.: 16 назв. - рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розроблено алгоритмічний підхід для дослідження моделі обслуговування з обмеженими чергами і стрибкоподібними пріоритетами. Передбачено, що при надходженні виклику низького пріоритету один виклик такого типу з певною ймовірністю може перейти в чергу викликів високого пріоритету. Ймовірність переходу залежить від стану черги різнотипних викликів. Запропоновано алгоритми розрахунку головних характеристик таких моделей обслуговування.
An algorithmic approach to study queuing models with finite queues and jump-like priorities is developed. It is assumed that upon arrival of a low-priority call, one such call may be transferred to the end of the high-priority calls queue with a certain probability. The transfer probability depends on the state of the queue of heterogeneous calls. Algorithms for calculating the main features of such queuing models are proposed.
|
| first_indexed | 2025-12-07T16:43:34Z |
| format | Article |
| fulltext |
© А.З. МЕЛИКОВ, Л.А. ПОНОМАРЕНКО, ЧИ СОН КИМ, 2012
114 ISSN 0572-2691
УДК 519.872:621.394.74
А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким
АЛГОРИТМИЧЕСКИЙ ПОДХОД К АНАЛИЗУ
СИСТЕМЫ ОБСЛУЖИВАНИЯ
С ОГРАНИЧЕННЫМИ ОЧЕРЕДЯМИ
И СКАЧКООБРАЗНЫМИ ПРИОРИТЕТАМИ
Введение
В современных сетях коммутации пакетов разнотипные трафики (видео и ре-
чевая информация, данные и т.д.) предъявляют различные требования к показате-
лям качества обслуживания (Quality of Service — QoS). Так, трафики реального
времени чувствительны к возможным задержкам, в то время как трафики нере-
ального времени требуют как можно меньше потерь их пакетов. Для удовлетво-
рения противоречивых требований разнотипных вызовов (пакетов) наиболее эф-
фективным средством являются разного рода приоритеты. Достаточно подробную
информацию по этому направлению можно найти в фундаментальной работе [1].
Не будем останавливаться на перечислении известных результатов, а дадим лишь
необходимые сведения, связанные с проводимыми здесь исследованиями.
В последнее десятилетие интенсивно исследуется новый тип приоритетов —
множественные приоритеты [2–5]. В отличие от классических приоритетов, при
использовании множественных приоритетов пакеты реального времени имеют
высокие временные и низкие пространственные приоритеты, а пакеты нереально-
го времени имеют низкие временные и высокие пространственные приоритеты.
Заметим, что пространственные приоритеты используются для разрешения кон-
фликтных ситуаций, связанных с занятием мест в буферном накопителе при по-
ступлении пакетов, а временные приоритеты определяют порядок выбора пакета
из буфера для передачи в канал обслуживания. Достаточно подробный обзор ра-
бот в этом направлении можно найти в соответствующих главах книги [6].
По признаку изменчивости классические приоритеты делятся на следующие
классы: статические, динамические по времени и динамические по состояниям (си-
туационные). Статическими (относительными) называются приоритеты, которые
устанавливаются до начала работы системы и не изменяются за все время ее рабо-
ты. Здесь каждый трафик имеет свой приоритет и в момент освобождения канала
выбирается вызов из головы той очереди, которая имеет наивысший приоритет сре-
ди всех непустых очередей. Эти приоритеты в англоязычной литературе называют-
ся HOL-приоритетами (Head-Of-Line). При использовании динамических (по вре-
мени) приоритетов приоритет вызова каждого типа изменяется (увеличивается либо
уменьшается) в зависимости от времени его пребывания в очереди. При этом мож-
но использовать различные функции, которые определяют закон изменения этих
приоритетов. Подобные приоритеты впервые были введены в работе [7]. Ситуаци-
онные приоритеты предполагают, что приоритет вызова каждого типа определяется
в зависимости от состояния очереди, при этом состояние очереди обычно задается с
помощью вектора, компоненты которого указывают число разнотипных вызовов
в очереди. Эти приоритеты впервые были введены в работе [8]; теория и области
приложения ситуационных приоритетов были развиты в [9].
Работа поддержана исследовательским грантом университета Санджи (Республика Корея)
за 2012 год.
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 6 115
В последние годы появились работы [10–15], в которых изучается новый тип
HOL-приоритетов. Первой работой в этом направлении является [10], ее авторы
назвали эти приоритеты Head-Of-Line with Priority Jumps (HOL-PJ). Краткое описа-
ние модели, изученной в [10], состоит в следующем. На вход одноканальной систе-
мы с бесконечными раздельными очередями поступают вызовы N типов, .1N
Считается, что вызовы типа i (i-вызовы) имеют высокие (относительные) приорите-
ты перед вызовами типа .1,...,1,1 Nii Для трафика типа i определяются де-
терминированные параметры ,iD ....0 21 NDDD Если время ожида-
ния
i-вызова, стоящего во главе i-й очереди, достигает величины ,1 ii DD то он пере-
ходит в очередь ,1i .,...,2 Ni Этот процесс продолжается до тех пор, пока вы-
зов любого типа либо получит доступ в канал, либо достигнет очереди с наивыс-
шим приоритетом (т.е. 1-й очереди). Поскольку точный анализ состояния очереди
и распределение времени ожидания в данной модели оказываются сложными про-
блемами, то в [10] рассматриваются формулы для расчета среднего времени ожида-
ния разнотипных вызовов. Следует отметить, что предложенные в [10] HOL-PJ не-
удобны в практической реализации, поскольку требуют дополнительных техниче-
ских средств для мониторинга времени ожидания разнотипных вызовов.
В работах [11–15] предложены различные виды HOL-PJ для системы обслужи-
вания с дискретным временем (в которой время разделено на слоты) и с двумя типа-
ми вызовов — вызовы высокого приоритета (H-вызовы) и вызовы низкого приори-
тета (L-вызовы). Для ожидания вызовов каждого типа имеются бесконечные очере-
ди. В работе [11] предложена схема HOL-MBP (Head-Of-Line Merge-By-Probability),
согласно которой в конце каждого временного слота все L-вызовы переходят в конец
очереди H-вызовов с вероятностью .10, Иными словами, в конце каждого
временного слота очереди H- и L-вызовов объединяются (укрупняются) с вероятно-
стью . Модификация схемы HOL-MBP изучена в [12]. Она получила название
HOL-JOS (Head-Of-Line Jump-Or-Serve), и в отличие от предыдущей схемы, здесь
только один L-вызов из головы очереди переходит в H-очередь. При этом воз-
можный переход в начале каждого временного слота зависит от состояния
H-очереди в начале слота, т.е. если H-очередь не является пустой, то происходит
переход; иначе L-вызов немедленно передается в канал. В схеме HOL-JIA1 (Head-
Of-Line Jump-If-Arrival) [13], в отличие от схемы HOL-JOS, возможный переход
L-вызова в H-очередь зависит не только от содержания H-очереди в начале слота,
но и от числа поступлений L-вызовов в течение данного слота, точнее, внутри вре-
менного слота, в течение которого передается H-вызов, переход L-вызова в H-оче-
редь разрешается лишь тогда, когда в течение данного слота поступают L-вызовы.
В данной схеме поступившим L-вызовам не разрешается немедленно переходить в
H-очередь. И, наконец, в работе [14] предложена схема HOL-JIA2. Единственное
отличие схемы HOL-JIA
1
от схемы HOL-JIA
2
состоит в том, что в последней схеме
поступившим L-вызовам разрешается немедленно переходить в H-очередь.
В работах [11–15] получены формулы для производящих функций длины
очереди вызовов обоих типов и времени ожидания в очереди H-вызовов, а также
их моменты, они также смогли найти среднее время ожидания в очереди L-вызо-
вов. Отмечается, что определение производящей функции времени ожидания в
очереди L-вызовов является сложной проблемой.
Отметим, что основная цель введения скачкообразных приоритетов — раз-
решение проблемы старения L-вызовов в системах с HOL-приоритетами. Эта
проблема особенно актуальна в системах, где нагрузки H-вызовов намного пре-
вышают нагрузки L-вызовов. При этом очевидно, что введение скачкообразных
116 ISSN 0572-2691
приоритетов позволяет разрешить данную проблему за счет увеличения времени
ожидания в очереди H-вызовов. Следовательно, при введении скачкообразных
приоритетов необходимо учитывать допустимые границы увеличения времени
ожидания в очереди H-вызовов.
В работах [10–15] исследуются модели систем с бесконечными очередями,
которые не могут быть приняты как адекватные модели реальных систем теле-
коммуникации, поскольку реальные системы, как правило, имеют ограниченные
буферные накопители для временного хранения разнотипных вызовов (пакетов).
Иными словами, для широкого внедрения приоритетов типа HOL-PJ потребуется
определить их эффективность в реальных системах.
В настоящей работе для систем обслуживания с непрерывным временем и
ограниченными очередями вводится новый класс скачкообразных приоритетов,
которые имеют рандомизированный характер. Они позволяют осуществить пере-
ход из L-очереди в H-очередь лишь в моменты поступления L-вызовов, при этом
вероятность такого перехода зависит от числа разнотипных вызовов в очередях.
Введение ограничений на размер буферов для ожидания разнотипных вызовов
приводит к необходимости определения нового показателя QoS — вероятности
потери пакетов (Cell Loss Probability — CLP). Другим важным моментом этой
работы, отличающим ее от [10–15], является то, что здесь для анализа системы
используется подход, основанный на теории фазового укрупнения состояний
двумерных цепей Маркова [16]. С использованием этого подхода разработаны
простые вычислительные процедуры для нахождения всех показателей QoS изу-
чаемой системы.
1. Определение скачкообразных приоритетов
Структурная схема исследуемой системы обслуживания показана на рис. 1.
Ее подробное описание состоит в следующем. На вход одноканальной системы
поступает два пуассоновских потока разнотипных вызовов, при этом интенсив-
ность k-го потока равна .2,1, kk Первый поток представляет собой поток вы-
зовов реального времени (H-вызовы), в то время как второй является потоком вы-
зовов нереального времени (L-вызовы). Время занятия канала является случайной
величиной, подчиненной показательному закону распределения c параметром
для вызовов обоих типов, обозначим .2,1,/ kkk
μ
Первая очередь
пустая
Выход
Потерянные вызовы
первого типа
Вызовы первого
типа
Вызовы второго
типа
λ2
λ1
Потерянные вызовы
второго типа
R1 1
1 2
2
R2
Рис. 1
Для ожидания в очереди разнотипных вызовов имеются раздельные буфера,
при этом размер буфера для вызовов k-го типа равен ,kR .2,1,0 kRk Огра-
ниченность раздельных буферов означает, что если в момент поступления вызова
любого типа соответствующий буфер полностью заполнен, то такой вызов теряется
независимо от состояния другого буфера. Вызовы реального времени имеют высо-
кие относительные приоритеты перед вызовами нереального времени. Это означает,
что при освобождении канала на обслуживание из очереди всегда выбирается вызов
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 6 117
первого типа независимо от количества вызовов второго типа в очереди, а также
времени их ожидания в очереди. Внутри каждого потока используется дисциплина
«первый пришел — первым обслужился» (First Come — First Serviced).
Скачкообразные приоритеты вводятся для увеличения шансов L-вызовов
быть обслуженными, при этом допускается лишь несущественное ухудшение по-
казателей QoS H-вызовов. При введении скачкообразных приоритетов определя-
ются основные вопросы: а) момент перехода от L-очереди к H-очереди; б) число
L-вызовов, переходящих в H-очередь.
Прежде всего отметим, что H-вызовы всегда принимаются с вероятностью 1,
если в момент их поступления имеется хотя бы одно свободное место в H-буфере;
в противном случае они теряются с вероятностью 1. Если в момент поступления
L-вызова количество вызовов данного типа в буфере равно ,, 2Rii и при этом
имеется свободное место в H-очереди, то с вероятностью )(i один L-вызов мгно-
венно переходит в H-буфер (предположим, что в H-буфер переходит L-вызов, сто-
ящий в голове очереди). С дополнительной вероятностью )(1 i поступивший L-
вызов присоединяется к очереди, если имеется свободное место. Если в момент по-
ступления L-вызова нет свободных мест в H-очереди, то с вероятностью 1 посту-
пивший L-вызов присоединяется к L-очереди, если имеется свободное место; в про-
тивном случае с вероятностью 1 он теряется.
Если в момент поступления L-вызова нет свободных мест в L-очереди, то с
вероятностью )( 2R поступивший L-вызов присоединяется к H-очереди, если
имеется свободное место. В противном случае поступивший L-вызов с вероятно-
стью )(1 2R теряется.
Отметим, что всегда в случае успешного «прыжка» L-вызов становится H-вы-
зовом и в дальнейшем обслуживается как H-вызов согласно HOL-приоритету.
Как видно из описания скачкообразных приоритетов, они включаются в мо-
менты поступления L-вызовов, зависят лишь от числа таких вызовов в буфере и
только один L-вызов может осуществить переходит в H-очередь. Такая схема
определения приоритетов объясняется следующими причинами. Во-первых, по-
скольку эти приоритеты вводятся для увеличения шансов L-вызовов обслужиться
в приемлемые сроки (обслужить вызов прежде чем он устареет), то естественно
полагать, что они должны включаться при их поступлении. Во-вторых, разреше-
ние только одному L-вызову перейти в H-очередь объясняется тем, что при таком
предположении промежуточные математические выкладки окажутся достаточно
простыми, и поэтому удается получить хорошо интерпретируемые аналитические
результаты. В-третьих, как будет видно из дальнейшего изложения, разработан-
ный подход позволяет при определении вводимых приоритетов учитывать и ко-
личество H-вызовов в очереди.
Отметим некоторые важные (частные) схемы применения введенных выше
скачкообразных приоритетов.
1. Равномерная схема — это схема, в которой вероятности )(i являются по-
стоянными и не зависят от числа L-вызовов в буфере, т.е. )(i для любого
.,...,1,0 2Ri
2. Пороговая схема, вводятся пороговые параметры ,kL ,...,,1 rk и веро-
ятности )(i определяются так:
. если,
,1,...,2,1, если,
)(
1
1
rrr
kkk
LiL
rkLiL
i (1)
Здесь полагается, что ,0:0 L .: 2RLr При этом вероятности ,k
,,...,1 rk могут быть определены различными способами. Схему, в которой
имеют место соотношения ,1 kk назовем оптимистической, а схему при
kk 1 — пессимистической.
118 ISSN 0572-2691
2. Методы вычислений
Рассмотрим задачу нахождения показателей QoS этой модели. Основные по-
казатели QoS — стационарная вероятность блокировки вызовов k-го типа
),( kCLP среднее количество вызовов каждого типа в буферах ),( kQ а также
средние времена их ожидания в буфере .2,1),( kCTDk
Состояние буферов в произвольный момент времени можно описать с помо-
щью двумерного вектора ),,( 21 nnn где in — количество k-вызовов в буфере,
.2,1k Иными словами, функционирование данной системы описывается дву-
мерной цепью Маркова со следующим фазовым пространством состояний (ФПС):
).2,1,,...,1,0:(: kRnS kkn
Переходы между состояниями системы происходят лишь в моменты поступ-
ления вызовов и ухода их из системы после завершения обслуживания. C учетом
изложенного выше получаем, что неотрицательные элементы Q-матрицы данной
многомерной цепи определяются из следующих соотношений (рис. 2):
случаях,остальных в0
,~,0 или
~,0 если,
,~ если)),,(1))((1(),(
,~ если),(
)~,(
1
11
21122112
1221
nn
enn
enn
enn
nn
n
n
RnnRn
n
q (2)
где .)1,0(),0,1( 21 ee Здесь и в дальнейшем ),( yx — символы Кронекера.
При любых положительных значениях параметров входящих трафиков все со-
стояния являются сообщающимися и, следовательно, система эргодическая. Стаци-
онарную вероятность состояния Sn обозначим ).(np Стандартный путь опреде-
ления стационарных вероятностей состояний — составление и решение соответ-
ствующей системы уравнений равновесия (СУР) с учетом соотношений (2), при
этом к ней добавляется нормирующее условие
.1)(
n
n S
(3)
Из-за очевидности составления явный вид СУР здесь не приводится.
0, 0 1, 0 2, 0 R1, 0
0, 1
1, 1
2, 1
R1, 1
0, R2
1, R2
2, R2
R1, R2
1 2(0)
1 2(1)
2(1 (0))
2(1 (0)) λ2
2(1 (R2 1))
S0
S1
1 2(0) 1 2(0)
2(1 (0))
1 2 (1) 1 2 (1)
λ2
2(1 (0)) 2(1 (0)) 2(1 (0))
2RS
λ2 2(1 (R2 1)) 2(1 (R2 1))
1 2(R2) 1 2(R2) 1 2(R2)
Рис. 2
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 6 119
После нахождения вероятностей состояний системы можно определить ее
показатели QoS. Вероятность потери H-вызовов определяется так:
).,( 1
0
1
2
kRpCLP
R
k
(4)
Вероятность потери L-вызовов определяется следующим образом:
).,())(1)(,( 2122
1
0
2
1
RRpRRkpCLP
R
k
(5)
Для нахождения среднего количества разнотипных пакетов в очереди
,2,1, kQk используется стандартный способ определения среднего значения
дискретной случайной величины:
),(
1
iiQ k
R
i
k
k
(6)
где
S kk kinpi
n
n ,2,1),,()()( — маргинальные распределения исходной
модели.
После нахождения показателей QoS (4)–(6) с помощью модифицированной
формулы Литтла определяются средние времена задержки передачи разнотипных
вызовов:
.2,1,
)1(
k
CLP
Q
CTD
kk
k
k (7)
Таким образом, для определения точных значений показателей QoS (4)–(7)
необходимо решить СУР для вероятностей состояний. Она не имеет аналитического
решения, но ее решение можно получить с использованием известных численных
методов линейной алгебры. Описанный метод определения показателей QoS (4)–(7)
назовем точным. Заметим, что он может использоваться лишь при небольших раз-
мерностях ФПС (1), а с их ростом становится неэффективным, поэтому необходимо
разработать более действенный способ решения этой задачи.
Теперь перейдем к описанию приближенного метода решения поставленной
задачи. Такой метод имеет высокую точность для моделей с высокой нагрузкой
вызовов первого типа, т.е. принимается следующее допущение: 21 (иными
словами, ).21 Отметим, что это допущение не является экстраординар-
ным, так как именно в системах с высокими нагрузками H-вызовов имеет смысл
введение скачкообразных приоритетов для L-вызовов.
Рассматривается следующее расщепление ФПС модели, обозначенное S :
,,,
2
0
jiSSSS jii
R
i
(8)
где .,...,2,1,0},:{ 22 RiinSSi n
Принятое выше допущение относительно соотношения нагрузок разнотип-
ных вызовов обеспечивает выполнение условия корректного применения алго-
ритмов фазового укрупнения двумерных цепей Маркова [16].
Классы микросостояний iS объединяются в отдельные укрупненные состоя-
ния i , и на исходном ФПС (1) вводится функция укрупнения
,)( iU n если ,iSn (9)
которая определяет укрупненную модель с ФПС }.,...,1,0:{ 2Rii Стаци-
онарную вероятность состояния ),( ik в расщепленной модели с ФПС iS обозна-
120 ISSN 0572-2691
чим ;,...,1,0),( 2Riki .,...,1,0 1Rk Каждая расщепленная модель с ФПС iS
является одномерным процессом размножения и гибели со следующими парамет-
рами (рис. 2):
случаях.остальных в0
,1 если,
,1 если),(
),( 12
1221
21 kk
kki
kkqi (10)
Из (10) видно, что для определения искомых )(ki могут использоваться фор-
мулы расчета стационарных вероятностей состояний системы массового обслужи-
вания (СМО) c зависящей от состояния интенсивностью входящего трафика
121 1)()(( RMiM (здесь и далее для обозначения СМО прибегаем к мо-
дифицированной символике Кендалла, где в скобках указаны параметры соответ-
ствующих распределений). Следовательно, для определения ,,...,1,0),( 2Riki
могут использоваться следующие формулы:
,,...,1,0,
1
1
)( 111
Rkk
R
i
ik
ii
(11)
где ).(21 ii
Для краткости здесь приводятся формулы лишь для случая .1i
Согласно алгоритму фазового укрупнения двумерных цепей Маркова [16]
элементы производящей матрицы укрупненной модели ,,),,( jijiq
определяются так (см. рис. 2):
случаях.остальных в0
,1 если),0(
,1 если),())(1))((1(
),(
1212
ij
ijRRi
jiq i
ii
(12)
Следовательно, стационарные вероятности укрупненных состояний ),( i
, i определяются так:
,,...,2,1),0()( 2
1
RiAi j
i
j
(13)
где ,
)0(
)())(1)(1(1( 1111
2
j
jj
j
RRj
A
.11)0(
11
2
/
i
k
i
R
k
A
С учетом (11)–(13) после определенных преобразований получим следующие
формулы (приближенные) для вычисления показателей QoS исследуемой модели
(см. (3)–(7)):
);()( 1
0
1
2
kRCLP k
R
k
(14)
));())(1))((1)((( 11222 22
RRRRCLP RR (15)
);()(
21
01
1
ikkQ i
R
i
R
k
(16)
).(
2
1
2
kkQ
R
k
(17)
После нахождения параметров kCLP и kQ из формул (14)–(17) определяются
и параметры .2,1, kCTDk
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 6 121
В частном случае, когда )(i для любого i (равномерная схема определе-
ния скачкообразных приоритетов), предложенные формулы (14)–(17) существен-
ным образом упрощаются. В этом случае стационарные вероятности состояний
внутри классов ,,...,1,0, 2RiSi не зависят от индекса i, т.е.
,,...,1,0,
1
1
)( 111
Rkk
R
k
(18)
где .21 Вероятности укрупненных состояний в данном случае опреде-
ляются из следующих простых формул:
,,...,2,1),0()( 2RiAi i (19)
где ,
)0(
)())(1)(1( 11
2
RR
A .11)0(
2
1
/
k
R
k
A
Тогда для равномерной схемы определения скачкообразных приоритетов по-
лучим следующие формулы:
);( 11 RCLP (20)
));())(1)(1)((( 1122 RRRCLP (21)
);(
1
1 kkQ
R
k
(22)
).(
2
1
2
kkQ
R
k
(23)
Из (20), (22) видно, что показатели QoS для H-вызовов определяются как соответ-
ствующие характеристики классической СМО типа .1)()( 121 RMM Этого
следовало ожидать, так как согласно принятому выше допущению имеет место
соотношение .21 Иными словами, указанные формулы — косвенное
(аналитическое) подтверждение высокой точности разработанного приближенно-
го метода.
Аналогичные формулы можно записать и для пороговой схемы определения
скачкообразных приоритетов. Однако в этом случае полученные формулы не яв-
ляются такими же компактными, как формулы (18)–(23).
3. Численные результаты
Полученные формулы позволяют исследовать поведение показателей QoS
рассмотренной системы относительно изменения ее структурных и нагрузочных
параметров. Здесь приводится лишь небольшая часть вычислительных эксперимен-
тов для гипотетической модели со следующими параметрами: ,152 R ,21
,12 .8,0 Цель проведенных вычислительных экспериментов — изучение
поведения показателей QoS исследуемой системы относительно изменения размера
буфера для вызовов первого типа (т.е. )1R и параметров ),(i которые характери-
зуют вероятности переходов L-вызовов в очередь H-вызовов. Рассматривается три
схемы определения скачкообразных приоритетов: равномерная, оптимистическая
и пессимистическая. Для указанных схем параметры )(i определяются так: для
равномерной схемы 7,0)( i для всех ;,...,1,0 1Ri для оптимистической схемы
),2/()1(:)( iii а для пессимистической схемы )2/(1:)( ii для
.,...,1,0 2Ri Соответствующие результаты показаны на рис. 3–5 (кривая 1 —
7,0)( i ; кривая 2 — );2/()1(:)( iii кривая 3 — )2/(1:)( ii ).
122 ISSN 0572-2691
0 5 10 15 20 25 30 35
0,64
0,68
0,72
0,76
0,8
CLP1
1
2
3
R1
0 5 10 15 20 25 30 35
0,65
0,7
0,75
0,85
0,95
CLP2
1
3
2
0,8
0,9
1
R1
а б
Рис. 3
0 5 10 15 20 25 30 35
5
10
15
20
R1
1
2
3
Q1
25
30
35
40
0 5 10 15 20 25 30 35
14,7
14,75
14,8
14,85
R1
1
2
3
Q2
14,9
14,95
15
15,05
а б
Рис. 4
0 5 10 15 20 25 30 35
10
20
30
40
50
CTD1
1
2
3
R1
60
70
0 5 10 15 20 25 30 35
100
200
300
400
500
CTD2
1
2
3
R1
600
700
а б
Рис. 5
Вероятность потери H-вызовов уменьшается с ростом размера буфера для
вызовов данного типа, что является вполне ожидаемым результатом (рис. 3, а).
Следует отметить идентичность характера изменения функции 1CLP при всех
схемах определения параметров ),(i т.е. при 51 R эта функция уменьшается с
очень малой скоростью. Это объясняется тем, что с увеличением размера буфера
для H-вызовов одновременно увеличиваются и шансы (интенсивность) поступле-
ния L-вызовов в этот буфер. Интересны также следующие факты: значения функ-
ции 1CLP при применении оптимистической схемы определения параметров )(i
(т.е. когда вероятность перехода L-вызовов в очередь H-вызовов растет с увели-
чением числа L-вызовов в очереди) всегда больше соответствующих значений
этой функции при применении пессимистической схемы определения параметров
)(i (т.е. когда вероятность перехода L-вызовов в очередь H-вызовов уменьшает-
ся с увеличением числа L-вызовов в очереди). Равномерная схема в этом смысле
промежуточная между оптимистической и пессимистической схемами.
Увеличение вероятности потери L-вызовов с ростом размера буфера для H-вы-
зовов также является вполне ожидаемым результатом (рис. 3, б), так как увеличение
размера буфера для H-вызовов, вообще говоря, уменьшает шансы L-вызовов быть
обслуженными. Также следует отметить идентичность характера изменения функ-
ции 2CLP при всех схемах определения параметров ),(i т.е. при 51 R она уве-
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 6 123
личивается с очень малой скоростью. В отличие от функции ,1CLP для функции
2CLP оптимистическая схема более выгодна, чем пессимистическая и равномерная
схемы. Эти факты имеют вполне логическое объяснение: возрастание функции
)(i увеличивает шансы L-вызовов быть обслуженными (либо в H-, либо в L-очере-
ди). Здесь также равномерная схема в смысле изменения вероятности потери L-вы-
зовов промежуточная между оптимистической и пессимистической схемами.
Функция 1Q растет практически линейно относительно размера буфера для
H-вызовов при всех трех схемах определения параметров ),(i при этом оптими-
стическая и пессимистическая схемы дают почти одинаковые результаты, а при
равномерной схеме длина очереди оказывается чуть меньше по сравнению с
остальными двумя схемами (рис. 4, а). Другая зависимость наблюдается для
функции 2Q (рис. 4, б). Здесь при 51 R буфер для L-вызовов почти полностью
заполнен при всех трех схемах определения параметров ).(i
Функции 1CTD и 2CTD являются неубывающими относительно размера бу-
фера для H-вызовов, но характер их изменения различен (рис. 5). Так, функция
1CTD при всех трех схемах определения параметров )(i практически линейная
(рис. 5, а), в то время как функция 2CTD при малых значениях 1R имеет нели-
нейный характер, а при 51 R становится почти постоянной (рис. 5, б). Эти свой-
ства полностью соответствуют характеру изменения функций kCLP и 2,1, kQk
(см. рис. 3 и рис. 4). Следует отметить, что для функции 1CTD наиболее благо-
приятной является пессимистическая схема определения параметров ),(i а для
функции ,2CTD наоборот, наиболее благоприятна оптимистическая схема опре-
деления параметров ).(i Для обеих функций равномерная схема промежуточная
между оптимистической и пессимистической схемами.
Авторы также проанализировали изменение показателей QoS данной систе-
мы относительно других ее параметров (структурных и нагрузочных). Однако из-
за ограниченности объема работы эти результаты не приводятся. поэтому не при-
водятся также результаты исследования точности разработанных приближенных
формул. При этом точные значения искомых показателей QoS для моделей малой
и умеренной размерности находились из соответствующих СУР (некоторые ана-
литические соображения относительно высокой точности разработанных формул
приведены в разд. 2). Здесь лишь отметим, что точные и приближенные значения
искомых показателей QoS в худшем случае отличаются одно от другого третьим
знаком после десятичной точки.
Заключение
В настоящей статье предложен эффективный подход к вычислению показа-
телей качества обслуживания разнотипных вызовов в системах со скачкообраз-
ными приоритетами. Важное преимущество предложенного подхода — возмож-
ность его использования для моделей любой размерности, так как искомые пока-
затели вычисляются с помощью явных формул. Предложенный подход может
использоваться для исследования моделей с общей ограниченной очередью раз-
нотипных вызовов, а также в случаях, когда вероятности )(i зависят и от числа
вызовов первого типа. Эти проблемы представляют интерес для дальнейших ис-
следований.
124 ISSN 0572-2691
А.З. Меліков, Л.А. Пономаренко, Чі Сон Кім
АЛГОРИТМІЧНИЙ ПІДХІД ДО АНАЛІЗУ СИСТЕМИ
ОБСЛУГОВУВАННЯ З ОБМЕЖЕНИМИ ЧЕРГАМИ
І СТРИБКОПОДІБНИМИ ПРІОРИТЕТАМИ
Розроблено алгоритмічний підхід для дослідження моделі обслуговування
з обмеженими чергами і стрибкоподібними пріоритетами. Припускається, що
на момент надходження виклику низького пріоритету один виклик такого типу
з певною ймовірністю може перейти в кінець черги викликів високого пріори-
тету. Ймовірність переходу залежить від стану черги різнотипних викликів.
Наведено алгоритми розрахунку головних характеристик таких моделей обслу-
говування.
A.Z. Melikov, L.A. Ponomarenko, Che Soong Kim
ALGORITHMIC APPROACH TO ANALYSIS
OF QUEUING SYSTEM WITH FINITE
QUEUES AND JUMP-LIKE PRIORITIES
An algorithmic approach to study the queuing models with finite queues and jump-
like priorities is developed. It is assumed that upon a call with low priority arriving
one call of such kind might be transfered to the end of queue of high priority calls.
Transfer probability depends on state of the queue of heterogeneous calls. The algo-
rithms to calculate the quality of main feature of such queuing models are proposed.
1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. — М. : Ком-
книга, 2005. — 400 с.
2. Lee Y., Choi B.D. Queuing system with multiple delay and loss priorities for ATM networks // In-
formation Sciences. — 2001. — 138. — P. 7–29.
3. Melikov A.Z., Feyziev V.S., Rustamov A.M. Analysis of model of data packet processing in ATM
networks with multiple space and time priorities // Automatic Control and Comput. Sci. — 2006.
— 40, N 6. — P. 38–45.
4. Melikov A.Z., Ponomarenko L.A., Kim C.S. Approximation method for performance analysis of
queuing systems with multimedia traffics // Appl. and Comput. Mathemat. — 2007. — 6, N 2. —
P. 1–8.
5. Demoor T., Fiems D., Walraevens J. Partially shared buffers with full or mixed priority // Journ.
of Industrial and Management Optimization. — 2011. — 7, N 3. — Р.735–751.
6. Меликов А.З., Пономаренко Л.А., Фаттахова М.И. Управление мультисервисными сетями
связи с буферными накопителями. — Киев : НАУ-друк, 2008. — 156 с.
7. Kleinrock L. A delay dependent queue discipline // Naval Res. Logist. Quart. — 1964. — 11. —
Р. 329–341.
8. Мова В.В., Пономаренко Л.А. Об оптимальных приоритетах, зависящих от текущего состо-
яния обслуживающей системы с конечным числом мест для ожидания // Изв. АН СССР.
Техн. кибернетика. — 1974. — № 5. — С. 74-81.
9. Меликов А.З., Пономаренко Л.А., Рюмшин Н.А. Математические модели многопотоковых
систем обслуживания. — Киев : Техніка, 1991. — 160 с.
10. Lim Y., Kobza J.E. Analysis of delay dependent priority discipline in an integrated multiclass traffic
fast packet switch // IEEE Transact. on Comm. — 1990. — 38, N 5. — P. 659–665.
11. Maertens T., Walraevens J., Bruneel H. On priority queues with priority jumps // Performance
Evaluation. — 2006. — 63, N 12. — P. 1235–1252.
12. Maertens T., Walraevens J., Bruneel H. A modified HOL priority scheduling discipline: perfor-
mance analysis // Europ. Journ. of Oper. Res. — 2007. — 180, N 3. — P. 1168–1185.
13. Maertens T., Walraevens J., Moeneclaey M., Bruneel H. A new dynamic priority scheme: per-
formance analysis // Proc. of the 13th Intern. Conf. on Analytical and Stochastic Modeling Tech-
niques and Appl. (ASMTA). — 2006. — P. 74–84.
14. Maertens T., Walraevens J., Bruneel H. Performance comparison of several priority schemes with
priority jumps // Annals of Oper. Res. — 2008. — 162. — P. 109–125.
15. Walraevens J., Steyaert B., Bruneel H. Performance analysis of single-server ATM queue with
priority scheduling // Comput. and Oper. Res. — 2003. — 30, N 12. — P. 1807–1829.
16. Ponomarenko L., Kim C.S., Melikov A. Performance analysis and optimization of multi-traffic on
communication networks. — Heidelberg; Dordtrecht; London; New York : Springer, 2010. —
208 р.
Получено 29.02.2012
|
| id | nasplib_isofts_kiev_ua-123456789-207548 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:43:34Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон 2025-10-09T12:18:44Z 2012 Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2012. — № 6. — С. 114–124. — Бібліогр.: 16 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207548 519.872:621.394.74 10.1615/JAutomatInfScien.v44.i12.50 Розроблено алгоритмічний підхід для дослідження моделі обслуговування з обмеженими чергами і стрибкоподібними пріоритетами. Передбачено, що при надходженні виклику низького пріоритету один виклик такого типу з певною ймовірністю може перейти в чергу викликів високого пріоритету. Ймовірність переходу залежить від стану черги різнотипних викликів. Запропоновано алгоритми розрахунку головних характеристик таких моделей обслуговування. An algorithmic approach to study queuing models with finite queues and jump-like priorities is developed. It is assumed that upon arrival of a low-priority call, one such call may be transferred to the end of the high-priority calls queue with a certain probability. The transfer probability depends on the state of the queue of heterogeneous calls. Algorithms for calculating the main features of such queuing models are proposed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы управления и обработки информации Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами Алгоритмічний підхід до аналізу системи обслуговування з обмеженими чергами і стрибкоподібними пріоритетами Algorithmic Approach to Analysis of Queuing System with Finite Queues and Jump-Like Priorities Article published earlier |
| spellingShingle | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон Методы управления и обработки информации |
| title | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| title_alt | Алгоритмічний підхід до аналізу системи обслуговування з обмеженими чергами і стрибкоподібними пріоритетами Algorithmic Approach to Analysis of Queuing System with Finite Queues and Jump-Like Priorities |
| title_full | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| title_fullStr | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| title_full_unstemmed | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| title_short | Алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| title_sort | алгоритмический подход к анализу системы обслуживания с ограниченными очередями и скачкообразными приоритетами |
| topic | Методы управления и обработки информации |
| topic_facet | Методы управления и обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207548 |
| work_keys_str_mv | AT melikovaz algoritmičeskiipodhodkanalizusistemyobsluživaniâsograničennymiočeredâmiiskačkoobraznymiprioritetami AT ponomarenkola algoritmičeskiipodhodkanalizusistemyobsluživaniâsograničennymiočeredâmiiskačkoobraznymiprioritetami AT kimčison algoritmičeskiipodhodkanalizusistemyobsluživaniâsograničennymiočeredâmiiskačkoobraznymiprioritetami AT melikovaz algoritmíčniipídhíddoanalízusistemiobslugovuvannâzobmeženimičergamiístribkopodíbnimipríoritetami AT ponomarenkola algoritmíčniipídhíddoanalízusistemiobslugovuvannâzobmeženimičergamiístribkopodíbnimipríoritetami AT kimčison algoritmíčniipídhíddoanalízusistemiobslugovuvannâzobmeženimičergamiístribkopodíbnimipríoritetami AT melikovaz algorithmicapproachtoanalysisofqueuingsystemwithfinitequeuesandjumplikepriorities AT ponomarenkola algorithmicapproachtoanalysisofqueuingsystemwithfinitequeuesandjumplikepriorities AT kimčison algorithmicapproachtoanalysisofqueuingsystemwithfinitequeuesandjumplikepriorities |