Об одной системе массового обслуживания с активным управлением очередью

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Математическая теория телетрафика и сети телекоммуникаций
УДК 621. 39
Об одной системе массового обслуживания с активным управлением очередью
Ю. В. Гайдамака*, А. Г. Масленников^
* Кафедра систем телекоммуникаций Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, 117 198, Россия
^ Представительство компании «Аастра Европа АГ» ул. Обручева, 23, копр. 3, Москва, 117 630, Россия
В статье рассмотрена система передачи данных с активным управлением очередью, предназначенным для предотвращения перегрузок, где в качестве функции управления используется нечёткий регулятор. Решена задача построения математической модели, учитывающей особенности функционирования системы передачи данных с активным управлением очередью, целью которого является удержание длины очереди в области значений, близких к заданному эталонному значению длины очереди. При построении модели использован метод гистерезисного управления поступающей нагрузкой с двумя порогами. Математической моделью является система массового обслуживания с пороговым управлением очередью, которая предназначена для анализа возможностей применения метода гистерезисного управления нагрузкой в системах с активным управлением. Модель описывается марковским процессом, для которого численно решена система уравнения равновесия, найдены стационарные вероятности состояний. Основными вероятностно-временными характеристиками модели являются средняя длина очереди, среднеквадратическое отклонение длины очереди и вероятность отклонения длины очереди от эталонного значения в заданных пределах. Результаты численного анализа в диапазоне нагрузки, включающем перегрузки системы, показали адекватность построенной математической модели с гистерезисным управлением нагрузкой системе с активным управлением очередью на базе нечёткого регулятора.
Ключевые слова: система массового обслуживания, активное управление очередью, гистерезисное управление, марковский процесс, система уравнений равновесия, средняя длина очереди.
1. Введение
Несмотря на постоянный рост скоростей передачи данных в сетях TCP/IP, проблема возникновения перегрузок остаётся по-прежнему актуальной. Экономически оправданно в пакетных сетях предоставлять абонентам суммарную скорость подключения большую, чем доступно на узле агрегации. Поэтому всегда существует вероятность перегрузки и переполнения выходного буфера маршрутизатора и ухудшения параметров качества обслуживания, таких как процент потерянных пакетов, задержка и джиттер. Использование функции управления поступающими в буфер заявками на основе нечёткого регулятора позволяет в моменты перегрузки эффективно управлять нелинейной динамикой нагрузки и поддерживать длину очереди на заданном уровне, что обеспечивает стабильность задержки [1, 2].
Рассматривается система передачи данных с буфером емкости В, для которого определена величина Qref (0 & lt- Qref & lt- В) эталонной длины очереди. На систему поступает поток пакетов, которые передаются в канал в порядке «первым пришёл
Статья поступила в редакцию 25 июля 2013 г.
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (гранты 12−07−108, 13−07−953) и Министерства образования и науки Российской Федерации (проект 8. 7962. 2013).
— первым обслужен» с постоянной скоростью передачи. В моменты ^ измерений модуль «Монитор» (рис. 1) фиксирует два параметра системы — текущую длину ^ очереди и интенсивность г^ поступления пакетов на последнем закончившемся интервале наблюдения Д^ = ^ -, г ^ 1.
Функция управления
^ АР ф^погт^ д_еггог
Актуатор
Монитор
Входящий поток Р ^ ]
о
Очередь
(^геГ
Ч Обслуживание
^Г^ Сброс
Рис. 1. Система передачи данных с активным управлением очередью
Модуль «Монитор» на вход модуля «Функция управления» передаёт нормированное значениееггогпогт отклонения длины очереди от эталонного значения и нормированное значение интенсивности поступления пакетов на интервале Д^, которые вычисляются по формулам:
^еггогпогт
41 —
В — QTei'- д* - Qтei QYef
^ ^^, & lt- QYef,
(1)
Г — ^
— ^ 2,
(2)
1, — & gt- 2,
где ^ - интенсивность обслуживания.
Модуль «Функция управления» использует значение входных параметров? Гг0гП0гт иПогт для расчета выходного параметра — приращения вероятности сброса пакета ДРг на следующем интервале наблюдения Д^г+1, ^ ^ 1. В рассматриваемой нами системе функция управления получена с помощью метода нечёткой логики в [3,4], и ее вид показан на рис. 2.
Рассчитанное с помощью функции управления значение приращения сброса пакета ДРг Е [-1,1] используется модулем «Актуатор» для вычисления вероятности сброса пакета по формуле
Р?+1 = Р* + ДРг • Рт
г & gt- 1,
(3)
где 0 & lt- Ртах & lt- 1 максимальное значение приращения вероятности сброса на любом интервале наблюдения. Таким образом, на интервале Д^ с вероятностью Рг модуль «Актуатор» сбрасывает пакеты на входе в буфер маршрутизатора.
Задачей данной статьи является построение математической модели, учитывающей особенности функционирования системы передачи данных с активным управлением очередью, а также исследование возможности применения в такой системе гистерезисного управления нагрузкой.
г
В разделе 2 статьи мы строим модель в виде системы массового обслуживания (СМО) с гистерезисным управлением нагрузкой аналогично [5,6], в разделе 3 выводится система уравнений марковского процесса, описывающего функционирование СМО, а в разделе 4 приводим пример численного анализа ее основных вероятностно-временных характеристик (ВВХ).
Рис. 2. Функция активного управления очередью
2. Модель СМО с гистерезисным управлением
Проведем дискретизацию параметров функции управления очередью, введя параметр г Е {0,1, 2, 3, 4}, характеризующий уровень интенсивности нагрузки на систему, и параметр й Е {0,1, 2, 3, 4} статуса перегрузки, который определяет уровень загрузки системы, т. е. степень наполненности буфера. При этом состояниям с одинаковым уровнем интенсивности нагрузки гможет соответствовать разный статус перегрузки й.
В табл. 1 показано соответствие значений параметра г диапазонам изменения интенсивности поступления пакетов г^, а в табл. 2 — соответствие значения статуса перегрузки.
Таблица 1
Уровни интенсивности нагрузки
Уровень нагрузки Значение параметра г Диапазон параметра г^огт
Малая 0 [-1- -0,6)
Средняя 1 [-0,6- -0,2)
Норма 2 [-0,2- 0,2)
Высокая 3 [0,2- 0,6)
Перегрузка 4 [0,6- 1]
Для управления интенсивностью предложенной нагрузки в очереди системы вводятся два порога — нижний порог Ь и верхний порог Н таким образом, что выполняется соотношение Ь & lt- Qтef & lt- Н. Пока общее число заявок в системе не
Таблица 2
Уровни статуса перегрузки
Статус перегрузки Значение параметра 5
Малая нагрузка 0
Нормальная нагрузка 1
Начало перегрузки 2
Перегрузка 3
Сброс нагрузки 4
превышает значение Н + 1, система функционирует в нормальном режиме (малая и нормальная нагрузка). Если число заявок в системе превысило значение Н + 1, система переходит в режим перегрузки (начало перегрузки и перегрузка). Система остается в режиме перегрузки до тех пор, пока число заявок в очереди д не достигнет значения — 1 или В. При достижении длиной очереди значения QYef — 1 система возвращается в нормальный режим функционирования, а при достижении длиной очереди значения В система переходит в режим сброса нагрузки, в котором остается до тех пор, пока длина очереди превышает порог Н, и возвращается в режим перегрузки, когда число заявок в очереди становится равным Н.
Рассмотрим изображенную на рис. 3 СМО. На систему с буферным накопителем емкости В, нижним порогом Ь, верхним порогом Н и эталонным значением длины очереди Qтef поступает пуассоновский поток заявок с интенсивностью А (з, д, г), зависящей от состояния системы. Заявки обслуживаются в порядке поступления по экспоненциальному закону с интенсивностью? и.
Входящий поток Очередь
ф
ЛС^г) В Н (}геГ Ь О Сброс
Обслуживание
Рис. 3. СМО с активным пороговым управлением очередью
Множество состояний СМО представим в виде
X = Хо и Хх и Х2 и Хэ и ,
(4)
где непересекающиеся множества Хг описывают состояния, соответствующие уровням г интенсивности нагрузки на СМО: Х0 — множество состояний малой нагрузки, Х1 — множество состояний средней нагрузки, Х2 — множество состояний нормальной нагрузки, Хэ — множество состояний высокой нагрузки и Х4 — множество состояний перегрузки.
Множества уровней г интенсивности нагрузки, в свою очередь, также могут быть представлены в виде объединения непересекающихся множеств по следующей формуле:
^0,0,
хг = { Хв1, ги, 5 = Г, Г = 1, 2, 3
^4,4,
где множества Х3, г имеют следующий вид:
(6)
Хс, о = {(з, д, г): 5 = 0, г = 0, 0 & lt- я & lt- Я^}, Хол = {(5,): 5 = 0, г = 1, 1 & lt- д & lt- +1 } ,
Хц = {(з, д, г): 5 = 1, г = 1, Ь & lt- я & lt- Н}, Хх, 2 = {(«, д, г): 5 = 1, г = 2, Ь + 1 & lt- д & lt- Н +1},2,2 = {(з, я, г): 5 = 2, г = 2^ & lt- я & lt- В — 3},2,3 = {(8, Я, г): 5 = 2, г = 3, дге? +1 & lt- я & lt- В — 2}, Хз, з = {(в, д, г): 5 = 3, г = 3, Я & lt- д & lt- Б — 1},4,4 = {(5, ^г): 5 = 4, г = 4, Н +1 & lt- д & lt- Б}.
Обозначим Аг, г = 0,1, 2, 3, 4, интенсивность поступающего потока на СМО на г-м уровне интенсивности нагрузки, причем А0 = Л. Тогда интенсивность Л (й, д, г) потока, поступающего на СМО, определяется формулой
Ао,
А (в, д, г) = ^ (1 — Рг) Аг-1 0,
(в, ъг) е Хоо,
(з, д, г) е X (Хо, о и Х4,4),
(в, д, г) е ^4,4,
(7)
где рг — вероятность сброса пакетов на г-м уровне. Вид функции А (з, д, г) схематично изображен на рис. 4. Здесь сплошными линями показаны значения функции интенсивности потока и пунктирными стрелками направления переходов между множествами состояний системы.
Рис. 4. Гистерезисное управление нагрузкой в СМО с активным управлением длиной очереди
3. Система уравнений равновесия
Функционирование построенной в предыдущем разделе СМО с активным управлением очередью описывается марковским процессом X (?) на множестве X. Нетрудно убедиться, что диаграмма интенсивностей переходов марковского процесса X (?) имеет вид, показанный на рис. 5.
АО
(4. Н+1. 4) ^-'- М
Рис. 5. Диаграмма интенсивностей переходов марковского процесса
Из диаграммы интенсивностей переходов может быть получена система уравнений равновесия марковского процесса X (?) в следующем виде:
'- АоРо, о, о = № 0,1,0 + № 1,1,1,
(Ло + ^)р0,д, 0 = АоРо, д-1,0 + № 0,д+1,0, Ч = 1, Яте! — 1, (Ао + M) Pо, Qref, 0 = ^0Р0& amp-Ге{-1,0, (А1 + м) ро, 1,1 = МР0,2,1,
(А1 + р) Ро, д,1 = А1 Ро, д-1,1 + № 0,д+1,1, Ч = 1,? — 2, Ч = ь, Яте!,
(А1 + м) ро, ь-1,1 = А1 Р0, ь-2,1 + №о, ь,1 + № 1,ь, 1,
(А1 + +1,1 = Ро, я^, 0 + А1, 1, (А1 + у) Р1,ь, 1 = № 1,ь+1,1 + № 1,Ь+1,2,
(А1 + ^)р1,д, 1 = А1 Р1, д-1,1 + № 1^+1,1, Ч = Ъ + 1, Яте! + 1, Ч = Яте! + 3, Н — 1,
(А1 + +2,1 = А1 Pl, Qref +1,1 + Ро, я^+1,1 + № 1,Я^+3,1,
(А1 + р) р1,Н, 1 = А1 Р1, н-1,1, (А2 + м) р1,Ь+1,2 = № 1,Ь+2,2,
(А2 + р) р1,д, 2 = А2Р1, д-1,2 + № 1^+1,2, Ч = Ъ + 2, Яте! — 2, Ч = Яте!, Н, & lt- (А2 + -1,2 = А1 -2,2 + MPl, Qref, 2 + № 2,2,
(А2 + р) р1,Н+1,2 = А1 Р1, Я, 2 + А1 Р1, Н, 1, (А2 + ^Р2^гел, 2 = № 2^+12 + MP2, Qref+1,3,
(А2 + ^)Р22 =2Р2,д-1,2 + № 2,д+1,2, Ч = Яте! + 1, Н + 1, Ц = Н + 3, В — 4,
(А2 + ^)р2,Н+2,2 = А2Р2, Н +1,2 + А2Р1, Н +1,2 + № 2,Н+3,2, (А2 + ^)Р2,В-3,2 =2Р2,В-4,2, (Аз + Р) Р2& amp-^+1,3 = MP2, Qref+2,3,
(А3 + ^)Р2л3 = А2Р2, д-1,3 + № 2,д+1,3, Ч = Яте! + 2, Н — 2, Ц = Н, В — 3,
(А3 + ^)Р2,Н-1,3 = А3Р2, Н-2,3 + № 2,Н, 3 + № 3,Н, 3, (А3 + ^)р2,В-2,3 =3Р2,В-3,3 + А22, Б-3,2, (А3 + ^)Р3,Н, 3 = № 3,Н+1,3 + № 4,Н +1,4, (А3 + ^)р3,д, 3 =3Р3,д-1,3 + МР3, д+1,3, 4 = Н + 1, В — 2, (А3 + д)^3,Б-1,3 = А3 Р3, В-2,3 + А3 Р2, В-2,3, № 4,В, 4 = МР3, В-1,3,, Р4, о-1,4 = Р4, о, 4, Ч = Н + 1, В.
Для численного анализа вероятностных характеристик исследуемой СМО, система уравнений равновесия решалась численно с использованием метода ЬИ-разложения.
4. Численный анализ
Обозначим У множество тех состояний СМО, в которых длина очереди находится в диапазоне д? [Ь, Н], и представим его в виде
У = Ю + У1 + У2, (8)
где
Уо = {(8, д, г): в = 0, г = 0, Ь & lt- д & lt- QTef } и
и {(в, д, г): в = 0, г = 1, Ь & lt- д & lt- ^ + 1 } -
У1 = {(в, д, г): в = 1, г = 1, Ь & lt- д & lt- Н } и
и {(в, д, г): в = 1, г =2, Ь + 1 & lt- д & lt- Н } -
12 = {(в, д, г): з = 2, г =2, QTef & lt- д & lt- Н} и
и {(в, д, г): в = 2, г =3, ^ +1 & lt- д & lt- Н}.
Необходимо оптимизировать систему с целью достижения максимального значения вероятности Р (У) отклонения длины очереди от эталонного значения в пределах Ь & lt- д & lt- Н.
Для проведения численного анализа в качестве исходных данных выберем емкость буферного накопителя В = 50, значение эталонной длины очереди QIef = 25, значения порогов Ь = 20 и Н = 30. Заметим, что при данных значениях мощность множества состояний СМО и, следовательно, размерность системы уравнений равновесия, равна 160. Подберём значения интенсивностей предложенной нагрузки такими, чтобы вероятность Р (У) достигла максимального значения. В рассматриваемом нами примере при значениях интенсивностей Ао = 1. 95, Л1 = 1. 2, Л2 = 0. 47, Аэ = 0. 43, Л4 = 0 и интенсивности обслуживания р = 1 эта вероятность достигает значения Р (У) = 0,68. Стационарные вероятности пребывания системы в подмножествах множества состояний марковского процесса X (?) показаны на рис. 6.
На рис. 7 показаны рассчитанные для данного численного примера зависимости средней длины очереди, среднеквадратического отклонения (СКО) длины очереди и вероятности Р (У) отклонения длины очереди от эталонного значения в пределах Ь ^ д ^ Н в зависимости от нагрузки на систему р в диапазоне, включающем перегрузки системы р? [0, 2].
Из графиков на рис. 7 видно, что с увеличением нагрузки и переходе системы в режим перегрузки р & gt- 1 средняя длина очереди стремится к заданному эталонному значению длины очереди QIef = 25, а вероятность отклонения длины очереди от эталонного значения в пределах порогов от Ь = 20 до Н = 30 с началом перегрузки также достигает максимального значения Р (У) = 0, 68.
5. Заключение
В статье построена математическая модель системы передачи данных с активным управлением очередью. Модель построена с целью исследования возможности применения гистерезисной политики при активном управлении очередью и качественного анализа ее вероятностно-временных характеристик.
Результаты численного анализа показывают адекватность построенной математической модели с гистерезисным управлением нагрузкой системы с активным управлением очередью на базе нечёткого регулятора.
1. 0
0. 8
Порядковый номер подмножества
Рис. 6. Вероятности пребывания СМО в подмножествах
Хо, о, Хо, 1, Х, 1, Х, 2, Х2,2, Х2,3, Хз, з, Х4,4
Рис. 7. Средняя длина очереди, среднеквадратическое отклонение длины очереди и вероятность отклонения длины очереди от эталонного значения
Литература
1. Fengyuan R., Yong R., Xiuming S. Design of Fuzzy Logic Controller for Active Queue Management // Computer Communications. — 2002. — No 25. — Pp. 874 883.
2. Chrysostomou C., Pitsillides A., Sekercioglu Y. A. Fuzzy Explicit Marking: a Unified Congestion Controller for Best-Effort and Diff-Serv Networks // Computer Networks. — 2009. — No 53. — Pp. 650−667.
3. Пегат А. Нечёткое моделирование и управление / пер. с англ. — М.: Бином. Лаборатория знаний, 2009. — 798 с. [Piegat A. Fuzzy Modeling and Control. — Moscow: Binom. Laboratory of knowledge, 2009. — 798 p. ]
4. Деарт В. Ю, Масленников А. Г. Исследование влияния параметров канала передачи данных на процедуры управления очередью // T-Comm. — 2012. — № 7. — С. 77−81. [Deart V., Maslennikov A. Investigation of Influence of Data Transmission Link Parameters on Queue Management Procedures // T-Comm. -
2012. — No 7. — P. 77−81. ]
5. Абаев П. О., Гайдамака Ю. В., Самуйлов К. Е. Гистерезисное управление сигнальной нагрузкой в сети SIP-серверов // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2011. — № 4. — С. 54−71. [Abaev P.O., Gaidamaka Yu.V., Samouylov K.E. Signaling Load Hysteretic Control in the SIP-servers Network // Bulletin of Peoples'- Friendship University of Russia. Series & quot-Mathematics. Informatics. Physics& quot-. — 2011. — No 4. — P. 54−71. ]
6. Gaidamaka Y. V. Model with Threshold Control for Analyzing a Server with an SIP Protocol in the Overload Mode // Automatic Control and Computer Sciences. -
2013. — Vol. 47, No 4. — Pp. 211−218.
UDC 621. 39
On a Queuing System with an Active Queue Management Yu. V. Gaidamaka*, A. G. Maslennikovt
* Telecommunication Systems Department Peoples'- Friendship University of Russia Miklukho-Maklaya str., 6, Moscow, 117 198, Russia
^ Representative office of Aastra Europe AG Obrucheva str., 23, bld. 3, Moscow, 117 630, Russia
We consider a data transfer system with an active queue management designed to prevent overloading, where fuzzy logic controller is used. We developed a mathematical model that takes into account the features of the data transfer system with an active queue management, which keeps the queue length in the range of values close to a given reference value of the queue length. The method of hysteretic control for incoming load with two thresholds was used as a basis of the model. The mathematical model is a queuing system with a threshold control, which is designed for the analysis of the possibility of hysteresis in modeling of systems with active queue management. The model was described by a Markov process, for which the numerical solution of the equilibrium equations was obtained, steady state probabilities were calculated. The main probabilistic measures are the following: the mean value and the standard deviation of a queue length, and the probability for the queue length of being within the specified limits from the reference value. The numerical analysis in the load range, which includes a system overload, indicated the adequacy of the constructed mathematical model with hysteretic control and system with an active queue management based on fuzzy logic controller.
Key words and phrases: queuing system, active queue management, hysteretic control, Markov process, system of equilibrium equations, average queue length.

ПоказатьСвернуть
Заполнить форму текущей работой