Моделирование процесса диспетчеризации очередей в иерархической системе классов качества обслуживания

Размещено на http://www.allbest.ru/

Моделирование процесса диспетчеризации очередей в иерархической системе классов качества обслуживания

Фролов А.И.

При построении современных распределенных информационно-телекоммуникационных систем обязательным требованием является обеспечение качества обслуживания в них [1]. Одна из основных функций обеспечения качества обслуживания - управление очередями, возникающими в результате перегрузок коммутационных узлов. В настоящее время предложено и исследовано множество подходов к диспетчеризации очередей и реализующих их алгоритмов. Однако при разработке новых моделей обеспечения качества обслуживания или в процессе выбора существующих методов при проектировании распределенных информационных систем необходимо решать задачи их исследования. Необходимо отметить, что наиболее развитые модели обеспечения качества обслуживания имеют иерархическую структуру (дерево классов обслуживания) [2,3]. Применение иерархических моделей позволяет упростить процесс реализации и повысить эффективность (по времени) функционирования системы. Поэтому построение эффективных и простых моделей процессов диспетчеризации очередей в иерархических системах классов качества обслуживания является актуальной задачей.

В работе [4] была предложена одноуровневая модель обеспечения качества обслуживания по критерию важности своевременности обработки заявки на информационное обслуживание. Модель определяет логику работы системы управления порядком предоставления информационных ресурсов в распределенной информационной среде предприятия. Данная система является составной частью сервера приложений в трехуровневой клиент-серверной архитектуре распределенной информационной среды и реализует функции управления рабочими потоками сервера приложений с целью обеспечения дифференцированного качества обслуживания запросов пользователей. Предложенная модель включает:

Условие справедливости обслуживания.

Распределение ресурса обслуживающего устройства является справедливым, если в любой момент времени отношение текущих задержек d' двух последовательно выбранных заявок классов i и j стремится к отношению их приоритетов :

.

Формальные правила выбора заявки на обслуживание.

Право занять обслуживающее устройство предоставляется заявке из очереди i-го класса обслуживания, где:

,

где А - множество активных классов обслуживания.

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

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

Дисциплина частично кругового циклического обслуживания с выбором позиции описывается следующим образом:

1. Вновь поступающая заявка в очереди с n заявками устанавливается в позицию n+1 (конец очереди).

2. На обслуживание выбирается заявка из позиции 1 (голова очереди).

3. Активная заявка после завершения такта обслуживания удаляется из системы, если ее обработка завершена. В противном случае она возвращается в очередь в позицию k, такую, что , где k = 1…n+1. При этом заявки, занимавшие позиции k…n, сдвигаются на позиции k+1…n+1.

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

Для простоты описания принято, что все листовые узлы дерева располагаются на одном уровне h (высота дерева). Каждому классу обслуживания K может быть сопоставлена абстрактная очередь Q (для листа она является реальной) и весовой коэффициент , определяющий неизменную составляющую приоритета класса. Очередь листового класса можно представить как множество элементов, на котором задано отношение полного порядка. Тогда под абстрактной очередью внутреннего класса понимается множество элементов, на котором задано отношение полного порядка, являющееся объединением попарно непересекающихся подмножеств дочерних классов, которые, в свою очередь, также являются абстрактными очередями.

Фрагмент иерархической структуры классов представлен на рисунке 1. На уровне листовых узлов h порядок следования элементов в множестве класса , являющегося l-ым потомком класса с индексом i, определяется их текущими задержками dh=d'. На предпоследнем уровне множество элементов абстрактной очереди класса является объединением подмножеств своих потомков . Причем порядок следования элементов в соответствии со сформулированной одноуровневой моделью определяется взвешенными значениями текущих задержек , где - весовой коэффициент класса на уровне h. На уровне h-2 представлено множество с порядком по величине

.

На основе данного описания можно получить рекуррентную зависимость, формально описывающую величину, определяющую порядок выбора заявки на обслуживание на произвольном уровне k дерева классов:

Так как окончательный выбор при подъеме по дереву рекурсии осуществляется на корневом уровне, зависимость была приведена к замкнутому виду. Отсюда были получены условие справедливости обслуживания и формальные правила выбора для иерархической структуры классов соответственно:

;

,

где - весовой коэффициент класса i на уровне k.

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

Однако формальное описание иерархических моделей затруднено. Поэтому необходимо свести ее к одноуровневой модели, т.е. смоделировать ситуацию одной приоритетной очереди (неэффективность по времени в данном случае является допустимой), реализующей предложенную модель. При этом будем рассматривать очередь с приоритетным исключением, так как приоритеты заявок меняются с течением времени и поддержание их упорядоченности не представляется возможным.

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

В теории массового обслуживания [5,6] оценка дисциплин обслуживания очередей обычно производится путем анализа общей продолжительности пребывания заявки в системе обслуживания - условного среднего времени обработки ? и продолжительности пребывания заявки в очереди. информационный телекоммуникационный качество обслуживание

Аналитические выражения для этих характеристик получены только для простейших дисциплин обслуживания очередей при наложении ряда жестких ограничений [5-7] таких, как:

время квантовано на -секундные интервалы;

обслуживание заявок производится тактами длительностью по секунд;

в конце такта может прибыть с вероятностью только одна новая заявка (дискретный аналог пуассоновского входящего потока);

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

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

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

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

Любую дисциплину обслуживания очередей можно задать, определив четыре положения:

1. Позиция в очереди, в которую будет устанавливаться вновь прибывшая или не завершившая обработку заявка.

2. Поведение очереди при постановке в позицию l новой заявки.

3. Правило выбора заявки на обработку.

4. Поведение очереди при выборе заявки на обработку.

В случае очереди с приоритетным исключением вставка заявки в очередь с n заявками всегда производится в позицию n+1, при этом перенумерация позиций не происходит. Тогда можно считать положения 1 и 2 заданными.

Таким образом, для формального описания дисциплины обслуживания в процессе моделирования достаточно определить две функции [8]. Первая - определяет номер позиции m в очереди , из которой необходимо выбрать заявку. Выбор заявки осуществляется на основании приоритета, который в общем случае является динамическим и зависит как от параметров заявки, так и от состояния системы. Состояние заявки опишем следующим образом: , где Т - тип заявки, ta - время постановки в очередь F - весовой коэффициент заявки в системе, определяемый приоритетами всех классов от листового до второго уровня, p - количество тактов обслуживания, которое прошла эта заявка, s - число тактов обслуживания, выделенное требованию для полного обслуживания. В соответствии с предложенной иерархической моделью качества обслуживания весовой коэффициент заявки i (такое же значение коэффициент будет принимать для всех заявок того же типа, что и i) в системе можно определить как:

.

Описание состояния очереди определяет длину очереди и соответствие позиций очереди заявкам, ожидающим обслуживания , где j - номер позиции в очереди.

Вторая процедура определяет состояние очереди, в которое она перейдет при выборе на обслуживание заявки из позиции m.

На основе введенных обозначений опишем на формальном уровне предложенную дисциплину обслуживания:

,

где S - множество заявок в очереди;

,

.

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

Литература

1. Вегешна Ш. Качество обслуживания в сетях IP / Ш. Вегешна - М.: Издательский дом «Вильямс», 2003. - 368 с.

2. Bennett J.C. Hierarchical packet fair queueing algorithms / J.C. Bennett, H. Zhang // In Proceedings of the ACM-SIGCOMM96, 1996. - Р. 143-156.

3. Stoica I. Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services / I. Stoica, H. A. Zhang // In Proceedings of the ACM-SIGCOMM97, 1997. - Р. 249-262.

4. Фролов А.И. Управление процессами информационного обмена в распределенной информационной среде предприятия: Автореферат диссертации на соискание ученой степени кандидата технических наук / А.И. Фролов - Орел: ОрелГТУ, 2005. - 16с.

5. Клейнрок Л. Вычислительные системы с очередями / Л. Клейнрок - М.: Мир, 1979. - 600 с.

6. Башарин Г.П. Анализ очередей в вычислительных сетях. Теория и методы расчета / Г.П. Башарин, П.П. Бочаров, Я.А Коган. - М.: Наука, 1989. - 336 с.

7. Клейнрок Л. Коммутационные сети / Л. Клейнрок - М.: Наука, 1975. - 256 с.

8. Константинов И.С. Организация управления процессами автоматизированного контроля сложных динамических объектов: дис. … канд. техн. наук: 05.13.01 / И.С. Константинов - Белгород.: БТИСМ, 1987. - 247 с.

Размещено на Allbest.ru