prosdo.ru
добавить свой файл
1

модель расчета характеристик систем активного управления очередями на основе марковской системы с двумя входящими потоками и различными приоритетами

Зарядов И.С, Королькова А.В.

Российский университет дружбы народов, izaryadov@sci.pfu.edu.ru

Российский университет дружбы народов, akorolkova@sci.pfu.edu.ru

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

Ключевые слова: система активного управления, пороговый механизм сброса, приоритетный трафик, приоритетное обслуживание.

Введение


В современных пакетных сетях передачи данных для регулирования интенсивности потока широко применяются механизмы активного управления очередью (Active Queue Management, AQM), которые позволяют задать определённую политику обслуживания разным типам. В частности, к механизмам AQM относятся RED-подобные алгоритмы (Random Early Detection, RED) [1, 2], которые позволяют регулировать интенсивность потока с помощью выборочного сброса пакетов до того, как очередь будет заполнена полностью.

Математические модели процесса передачи трафика, учитывающие, в частности, влияние процесса регулирования состояния потока на изменение его интенсивности, позволяют проанализировать поведение трафика во времени, оценить различные параметры качества функционирования сети. Для построения и анализа таких моделей и их характеристик применяются разные подходы и методы [3-6].

В данной работе предлагается модель с двумя видами входящего трафика различной приоритетности и пороговым механизмом сброса пакетов при их поступлении в систему, что характерно при описании RED-подобных систем [1-4].

Описание модели


Рассматривается система массового обслуживания , состоящая из одного прибора, накопителя конечной ёмкости R с двумя пороговыми значениями qmin и qmax: qmin < qmax, с двумя поступающими пуассоновскими потоками пакетов интенсивности (неприоритетный поток) и (приоритетный поток). Пакет каждого типа имеет экспоненциальное распределение времени обслуживания с параметром (i=1,2). Сброс пакета каждого типа происходит в момент поступления в зависимости от значений параметра управления и определяется следующими функциями для каждого типа трафика:

(1)

Поведение системы описывается двумерным марковским процессом , где – число пакетов -го типа () в системе в момент времени со множеством состояний . Через обозначается стационарная вероятность того, что в системе находится пакетов 1-го (неприоритетного) типа и пакетов 2-го (приоритетного) типа ().

Вероятности потери поступающих пакетов первого и второго типов соответственно вычисляются по формулам:

(2)


Здесь – число пакетов в системе вне зависимости от типа ().

Вероятность потери пакета вне зависимости от его типа:

(3)

Вероятности того, что поступающий в систему пакет соответствующего типа будет принят и передан далее, имеют вид: и

Пусть поступающие в систему пакеты обслуживаются в порядке поступления. Тогда в терминах преобразований Лапласа-Стилтьеса стационарные функции распределения времен ожидания начала обслуживания имеют вид:

(4)

(5)

Пусть теперь пакеты второго типа имеют приоритет при обслуживании над пакетами первого типа – неприоритетные пакеты обслуживаются (передаются) только при отсутствии приоритетных пакетов. Тогда для приоритетных пакетов функция распределения времени ожидания имеет вид



Здесь – вероятность того, что поступающий приоритетный пакет застанет в системе пакетов своего типа, а – функция распределения Эрланга с параметрами и .

Вычисление распределения времени ожидания начала обслуживания пакетов неприоритетного типа будет рассмотрено в дальнейших работах.

Заключение

Данная работа является лишь началом исследования авторов по представленной тематике. Построена математическая модель системы с двумя типами входящего трафика, двумя порогами в накопителе и механизмом сброса. Получены основные вероятностно-временные характеристики.


Интерес представляет построение математической модели систем, реализующих пороговые механизмы усечения/сброса входящего трафика для следующих задач:


  • различные типы входящего трафика (потоки общего рекуррентного, марковского типа);

  • отличное от экспоненциального время обслуживания и/или несколько приборов;

  • введение в модель механизма гистерезиса;

  • построение математических моделей в дискретном времени (см., например, [7]).

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант № 11-07-00112).

Литература


1. Floyd S., Jacobson V., Random Early Detection Gateways for Congestion Avoidance // IEEE/ACM Transactions on Networking, No 1(4), Aug. 1993. – Pp. 397–413.

2. Королькова А. В.; Кулябов Д. С., Черноиванов, А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика». – 2009. – № 3. – С. 34-46.

3. Королькова А. В. Математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока. Дисс. …к.ф.-м.н.: М. РУДН, 2010. – 115 с.

4. Korolkova A.V., Zaryadov I.S. The Mathematical Model of the Traffic Transfer Process with a Rate Adjustable by RED // IEEE / International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Moscow, October 18-20, 2010.

5. Зарядов И.С. Расчёт показателей качества функционирования систем передачи и обработки данных с помощью обобщённого обновления. Дисс. …к.ф.-м.н.: М. РУДН, 2010. – 160 с.

6. Зарядов И. С., Королькова А. В. Применение модели с обобщенным обновлением к анализу характеристик систем активного управления очередями типа Random Early Detection (RED) // T-Comm - Телекоммуникации и транспорт. — 2011. — С. 84-88.

7. Печинкин А.В., Разумчик Р.В. Система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени. // Автоматика и телемеханика. – 2009. – № 12. – С. 109-120.

The Mathematical model of active queue management systems analysis based on Marcovian queueing system with two types of traffic and different priorities

Zaryadov I.S, Korolkova A.V.

Peoples’ Friendship University of Russia, izaryadov@sci.pfu.edu.ru

Peoples’ Friendship University of Russia, akorolkova@sci.pfu.edu.ru

The one-server queueing system with two input Poisson flaws with different intensities and priorities (non-priority traffic and a priority one), finite buffer with two thresholds, exponential service time is considered. The thresholds drop mechanism is introduced. The first type packets are dropped more often than the packets of second type. Also two types of service disciplines are introduced: packets are served in order of arrival (non-priority case) and packets are served with different priorities. Analytical expressions for time-probability characteristics are obtained.

Кеу words: active queue management system, thresholds drop mechanism, priority traffic, priority service.