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

На правах рукописи

Ильяшенко Александр Сергеевич

МОДЕЛИ И МЕТОД ИССЛЕДОВАНИЯ ПРИОРИТЕТНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ВЕРОЯТНОСТНЫМ ВЫТАЛКИВАЮЩИМ МЕХАНИЗМОМ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата фнзнко-математических наук

2 2 ЯНВ 2015

Санкт-Петербург - 2014

005557988

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Санкт-Петербургский государственный политехнический университет» на кафедре «Телематика (при ЦНИИ РТК)» Института прикладной математики и механики

Научный руководитель: кандидат физико-математических наук,

Заяц Олег Иванович

Официальные оппоненты: доктор физико-математических наук, доцент,

заведующий лабораторией, Санкт-

Петербургский Институт Информатики и Автоматизации Российской Академии Наук (СПИИРАН)

Тулуньев Александр Львович

доктор технических наук, профессор, заведующий кафедрой, ФГБОУ ВПО «Петербургский Государственный Университет Путей Сообщения Императора Александра I» Хомоненко Анатолий Дмитриевич

Ведущая организация: ФГАОУ ВО «Российский Университет Дружбы Народов», г. Москва

Защита состоится «_/£» 2015 г. в /% часов на заседании

диссертационного совета Д 212.229.13 при ФГАОУ ВО «Санкт-Петербургский государственный политехнический университет», расположенном по адресу: 195251, Санкт-Петербург, Политехническая ул., д. 29, / уч. корп., ауд.

С диссертацией можно ознакомиться в фундаментальной библиотеке ФГАОУ ВО «Санкт-Петербургский государственный политехнический университет» по адресу 195251, Санкт-Петербург, Политехническая ул., д. 29. Автореферат диссертации доступен на официальном сайте ФГАОУ ВО «СПбПУ» (http://www.spbstu.ru/').

Автореферат разослан « ^Ла^л 201 ^г.

Ученый секретарь

диссертационного совета Д 212.229.13 /у7 / доктор технических наук, профессор 4 / Григорьев

/ Борис Семёнович

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

Первый период наиболее интенсивного развития ТМО относится к 50-70-ым годам прошлого века. Важные результаты, полученные в этот период, по системам массового обслуживания (СМО) с приоритетами принадлежат Б.В. Гнеденко, Г.П. Башарину, И.Н. Коваленко, О.И. Бронштейну, И.М. Духовному, П.П. Бочарову, A.B. Печинкину, В.А. Кокотушкину, В.П. Рыкову, Г.П. Климову, Д.Г. Михалеву, Э.А. Даниеляну, М.Ю. Китаеву, Д. Кёнигу, Н. Джейсуолу, T.JI. Саати, X. Уайту, Л.С. Кристи, Ф. Стефану, а также другим ученым. Тогда были детально изучены важнейшие типовые модели СМО. Далее развитие ТМО несколько замедлилось. Для большинства задач, допускающих простое решение, оно уже было известно. Кроме того, широкое распространение вычислительной техники стимулировало развитие методов статистического (имитационного) моделирования, что снизило число работ, посвященных теоретическому анализу новых моделей СМО.

Новый подъем исследований в области ТМО начался в 90-е годы. Он был вызван нарастающей популярностью сетевых технологий, развитие которых сильно опережало их теоретическое понимание. Классических простейших однопотоковых моделей СМО уже было недостаточно для моделирования реальных сетевых взаимодействий, хотя бы потому, что потоки в сетях сложны и формируются многими источниками и различаются по ряду признаков (скорости передачи, пропускной способности каналов связи, доступности буферной памяти, допустимому уровню потерь и т.п.).

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

В ТМО основными видами приоритетов (по Б.В. Гнеденко1) являются: абсолютный, относительный, чередующийся и вероятностный. Но, приоритизация как метод управления пропускной способностью эффективна только в двух случаях: при бесконечном буфере, либо в слабозагружснной системе. Если буфер ограничен, а загрузка низкоприоритетными требованиями

' Гнеденко Б.В., Даннелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М.: МГУ, 1973.

высока, то возможно «забивание» системы, сводящее на нет эффект приоритизации.

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

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

Несмотря на обилие работ по общей теории приоритетных СМО, лишь единицы из них допускают выталкивание. Применительно к детерминированному выталкивающему механизму имеется только цикл работ Г.П. Башарина, две статьи В.А. Кокотушкина и Д.Г. Михалева и еще несколько работ зарубежных авторов.

В начале этого века Н.О. Вильчевский, К.Е. Авраченков и Г.Л. Шевляков2 изучили одноканальную марковскую СМО при наличии относительного приоритета и вероятностного выталкивания. Авторы работы2 детально разобрали марковскую двухпотоковую одноканальную систему с абсолютным приоритетом, считая, что выталкивание с канала обслуживания осуществлялось с вероятностью, равной вероятности выталкивания3.

Для сокращения записей далее удобно воспользоваться системой обозначений приоритетных СМО, предложенной Г.П. Башариным4 . Для описания приоритета в системе был использован символ вида/;'. В оригинале у

Башарина нижний индекс / принимал значения: 1=0 (без приоритета), /'= 1 (относительный приоритет), /=2 (абсолютный приоритет). Верхний индекс j выбирался из двух значений: /=0 (без выталкивания), j=2 (детерминированное выталкивание). Следуя рекоммендациям Н.О. Вильчевского, используем j= 1 для обозначения вероятностного выталкивания. Кроме того, в данной работе предлагается зарезервировать /'=3 для чередующегося приоритета, а /=4 для вероятностного приоритета.

Настоящая диссертационная работа содержит исследование двухпотоковых марковских моделей СМО, снабженных вероятностным

2 Avrachenkov К.Е., Vilchevsky N.O., Shevlyakov G.L. Priority queueing with finite buffer size and randomized push-out mechanism // Performance evaluation, 2005, vol. 61, no. 1, p. 1-16.

3 Заяц О.И., Заборовский B.C., Мулюха B.A., Вербенко A.C. Управление пакетными коммутациями в телематических устройствах с ограниченным буфером при использовании абсолютного приоритета и вероятностного выталкивающего механизма. Части 1,2 // Программная инженерия; 2012, №2, с. 22-27; №3, с. 21-29.

4 Башарин Г.П. Некоторые результаты для систем с приоритетами // Массовое обслуживание в системах передачи информации М: Наука, 1969, с. 39-53.

выталкивающим механизмом, для основных типов приоритетов (абсолютного, относительного, чередующегося и вероятностного). В обозначениях Башарина с введенными дополнениями рассматриваемые в диссертации модели относятся

к классам Мг1 М III к I f', где 1 < / < 4.

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

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

1. Введены новые модели приоритетных СМО с вероятностным выталкиванием;

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

3. Разработан программный комплекс, реализующий алгоритмы вычисления вероятностей потери требований с использованием: исходной системы уравнений равновесия; «укороченной» системы уравнений, полученной по результатам применения метода;

4. Детально изучена зависимость вероятности потери требований от параметра выталкивающего механизма и выявлен ряд качественных эффектов;

5. Введено понятие областей «запирания» системы для низкоприоритетного потока требований и определены их границы;

6. Введено понятие области «линейности» системы для каждого типа требований и определены их границы.

Объектом исследования в работе служат приоритетные СМО, снабженные вероятностным выталкивающим механизмом.

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

Основные положения, выносимые на защиту:

1. Математическая постановка задачи, включающая выбор фазового пространства, построение размеченного графа состояний, запись системы уравнений равновесия (СУР) Колмогорова для СМО классов

~M1IMI\lklf] при 1 </<4;

2. Метод понижения размерности СУР, основанный на методе производящих функций и условиях их аналитичности;

3. Программный комплекс для расчета вероятностей потери требований в рассматриваемых системах;

4. Понятие областей «запирания» СМО относительно низкоприоритетных заявок;

5. Понятие области «линейности» относительно высокоприоритетных и низкоприоритетных заявок.

Научная новизна. В работе введены в научный оборот новые модели приоритетных СМО, снабженные вероятностным выталкивающим механизмом. В дополнение к известной ранее модели с относительным приоритетом рассмотрены также системы с абсолютным, чередующимся и вероятностным приоритетом. Тем самым завершено теоретическое изучение всех основных видов приоритетов в комбинации с вероятностным выталкивающим механизмом для марковских двухпотоковых СМО. Автором впервые получены следующие результаты:

1. Построены фазовые пространства, размеченные графы состояний и СУР для всех моделей приоритетных СМО класса Мг/ М III к/ f' при 1 </<4;

2. Разработан метод понижения размерности СУР, основанный на теории производящих функций и условиях их аналитичности;

3. Проведено детальное исследование влияния параметра выталкивающего

механизма на вероятности потерь СМО классов Мг/М/1/к/f] при 1</<4;

4. Введено понятие областей «запирания» и построены их границы для СМО приведенных выше классов для низкоприоритетного трафика;

5. Введено понятие областей «линейности» и построены границы этих областей как диаграмм загрузки, где имеет силу линейный закон потерь в зависимости от параметра выталкивающего механизма. Обоснованность и достоверность всех полученных в диссертации

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

Практическая значимость работы. Построенные в работе новые математические модели приоритетных СМО позволяют создавать новые, более эффективные сетевые устройства обработки данных и рационально выбирать режимы их работы при различных состояниях сетевой среды. Результаты диссертационного исследования используются на практике при проектировании и изготовлении ряда сетевых устройств, в частности, межсетевых экранов отечественного производства (модель ССПТ-2 и ее модификации). Другим успешным примером приложения разработанной теории является ее использование при проектировании системы удаленного управления робототехническими комплексами в условиях ограниченной пропускной способности каналов связи в отечественных космических экспериментах «Контур» и «Контур-2».

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на следующих конференциях и семинарах: Научном семинаре «Проблемы современных информационно-вычислительных систем» (Москва, МГУ, 2011), XXII Международной

конференции «Экстремальная робототехника» (Санкт-Петербург, ЦНИИ РТК, 2012), Международной конференции «Numerical Computations: theory and algorithms» (Италия, Фалерна, 2013), XIV Международной конференции «Next generation wired/wireless advanced networks and systems» (Санкт-Петербург, 2014). Результаты, полученные автором работы, дважды удостоены грантов правительства Санкт-Петербурга (2012 и 2013 гг.), а также отмечены именной стипендией Президента РФ молодым ученым и аспирантам.

Личный вклад. Автор участвовал в постановке задачи, формулировке целей и задач исследования, и лично дорабатывал метод понижения размерности СУР на основе ранее опубликованных работ других исследователей. Модели СМО с чередующимся и вероятностным приоритетом являются новыми и предложены автором. Автором также собственноручно разработан комплекс программ для расчета основных характеристик рассматриваемых в работе СМО и проведен весь численный эксперимент. Статьи и доклады, отражающие содержание работы, писались при личном участии автора.

Публикации. По результатам диссертационного исследования опубликовано 8 печатных работах, в том числе 3 из них в изданиях, входящих в перечень ВАК Минобрнауки РФ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Объем диссертации составил 146 страниц, в том числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 135 стр., библиография из 111 наименований - 10 стр.

Содержание работы

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

Первая глава является вводной и содержит вспомогательный материал, необходимый при последующих аналитических вычислениях и доказательствах. В раздел 1.1 помещен обзор литературы. Особо следует отметить подраздел 1.1.2. трактующий классификацию приоритетных СМО по Г.П. Башарину и предложения автора по расширению этой классификации. Раздел 1.2 посвящен основному для диссертации методу производящих функций. В подразделе 1.2.1 приведено классическое решение для СМО класса М2/М/1//2 с неограниченным накопителем, принадлежащее Х.Уайту, Л.С. Кристи и Ф. Стефану'. В последующих главах показана эффективность этого метода и в случае ограниченного накопителя, для которого метод, хотя

5 White H., Christie L.S. Queueing with preemptive priorities or with breakdown // Operations research, 1958, vol. 6, no. I, p. 79-95.

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

Вторая глава посвящена решению задач для двух наиболее употребительных классических типов приоритетов: абсолютного (модель М2/M/I/к//2) и относительного (модель М2/M 11/к//¡'), причем основное внимание уделено первой из них, которая ранее в литературе детально не рассматривалась.

Состояние системы М21M /XI к I /2 характеризуется фазовым вектором {vV,(/),./V,(i)}, где N^t) обозначает число требований /-го типа в системе в момент /. Фазовое пространство такой системы задается равенством

n = {(/J):/ = ÔXy = <),*-/}. (1)

Пусть интенсивность /'-го потока равняется At , интенсивность обслуживания равна /.I , причем первый поток обладает приоритетом и по обслуживанию и по постановке в очередь, тогда размеченный граф состояний имеет вид, представленный на рис. 1, где а обозначает вероятность выталкивания неприоритетного требования приоритетным.

Рассматриваемая СМО является эргодической, и в ней существует установившийся режим. Далее ограничимся получением только финальных вероятностей Р:,,(/' = 0,k;j = 0,к -/'). При записи СУР удобно записывать эти

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

Лемма 2.1. Система уравнений равновесия Колмогорова для СМО класса М2/M lllkl/2 имеет вид

440- s»., )+О - )sik4 + (1 - , + л, (1 - sik4) +

„Ч! + (1 - А/: = 0,(0 < / < ¿;0 < j < к - 0,

Для фактического получения вероятностей Pi, одно из уравнений системы (2) следует отбросить, заменив его на условие нормировки, требующее, чтобы сумма всех PLi равнялась единице. Непосредственное решение системы (2) затруднительно по причине быстрого роста ее порядка, который асимптотически пропорционален к2 с ростом объема накопителя.

Одним из наиболее известных методов решения СУР является принадлежащий Г.П. Башарину метод рекуррентных соотношений (MPC)6. Он основан на рекуррентных матричных вычислениях и эффективен при

6 Башарин Г.П. О пуассоновских обслуживающих системах с абсолютным приоритетом // Массовое обслуживание в системах передачи информации М.: Наука, 1969, с. 3-20

сравнительно небольших к. При увеличении к вычислительная сложность метода существенно возрастает.

--.. --- À

0,0//1 1,0 I у

г

К

од !iz:i и L у

/' /У

А---s ,-

.ч 1 А—10 i I

Я 'ЧУ

.JÙ I

:,и 1 м од-

JL

П U-

'»Л,

Рис. 1. Размеченный граф состояний для СМО М2/M /1/к//2'.

В настоящей работе используется альтернативный MPC метод производящих функций в трактовке, близкой к классическим работам Уайта-Кристи и Стефана5. Для случая абсолютного приоритета техника вычислений близка к работе3, для остальных типов приоритета внесен ряд изменений и уточнений, диктуемых конкретным содержанием решаемых задач. Преобразование СУР осуществляется методом, аналогичным статье Авраченкова, Вильчевского и Шевлякова".

Выбор в качестве основного пал на метод производящих функций (МПФ) по следующим соображениям. MPC6 является алгоритмическим и дает лишь последовательность действий, приводящих к решению. Получение с помощью MPC аналитических результирующих формул затруднено. Между тем МПФ дает аналитическое решение при к = со 5, при а = 0 , а = 1 2 3 и в некоторых других случаях3. Имеются примеры, когда при одновременном применении к одной и той же СМО как MPC, так и МПФ последний давал более удобную и компактную форму представления решения".

Введем производящую функцию (ПФ) вероятностей Pt .

G(u,v) = YZP:,ll'vi ■

(3)

/=о

Для ПФ, заданной в виде (3), в разделе 2.1.2 установлен следующий факт.

Теорема 2.1. Производящая функция (3) для СМО класса М21М IIIkl/2' удовлетворяет уравнению

[Я,м(1 - и) + Ajii(l-v) + //(и - l)]vG(n,v) = р{и - v)G(0, v) +

+pu(v - 1)G(0,0) + сЦг/+| (v - a)Pk{) + (1 - a)A,Pokvka(u - v) (4)

+[аЛ, (г/ - v) + 4(1 - !i)v + Я2(1 - v)v]h£ Pa-,i<'vk".

Выражение (4) еще не будет являться искомым решением так как содержит в правой част» два набора неизвестных вероятностен и

=о • Для их нахождения применяется алгоритм, аналогичный работам и

включающий два этапа. Во-первых, записываются условия аналитичности функции С по аргументу и в точках и = г/, и и = и2. Во-вторых, из числителя выражения для (7 последовательно вычитаются левые части уравнений, дающих условия аналитичности, с последующим сокращением числителя и знаменателя <7 на (и - и С) и (и - ит).

В результате получаем выражение для (7, в правой части которого сохраняются только вероятности , соответствующие «диагональным»

состояниям размеченного графа рис.1. Далее, приравнивая коэффициенты при степенях , выводим систему линейных уравнений для «диагональных» вероятностей, которую в дальнейшем будем называть «укороченной» системой уравнений. Реализации описанного метода вычислений посвящен раздел 2.1.3. где доказана следующая теорема.

Теорема 2.2. Вероятности всех состояний С МО М2/ М Шк/ /2 выражаются через вероятности состояний р, = Ркч, той же СМО с полностью заполненным накопителем при всех у = 0,/ -1 как

П-и=я-р1'2с;±,)ра +

и, ' (5)

л-1 Л=0

где =Л(.///- коэффициенты использования по /-му типу требований; сп -полином Гегенбауэра порядка п с индексом у , взятый при аргументе

С использованием выражений (5) в разделе 2.1.4 дается описание алгоритма построения «укороченной» системы уравнений для системы с абсолютным приоритетом, результаты применения которого приводятся в теореме 2.3.

Теорема 2.3. Вероятности состояний р1 = Рк_:,системыМг IМ /I/ к/ /2,

соответствующие полностью заполненному накопителю, определяются «укороченной» системой уравнений

V _ к

л'С а> + Х^-.//'/ -а<р,р*>I 1 = = од -Р, = , (6)

где коэффициенты и ¡определяютсяравенствами

м>

а гп обозначают вероятности распределения общего числа требований

#■„ = Р{ЛГ, + n2 = п} = (Л + р2у,(п = о(8)

1-(Р| + А)

совпадающие с однопотоковой моделью М/ М/1 / к.

Система (6) имеет порядок (к+1), меньший, чем порядок исходной системы (2), равный к(к+1)/2. Кроме того система (6) обладает удобной квазитреугольной структурой, что позволяет предложить для ее решения простой итерационный алгоритм, описанный в разделе 2.1.4.

Завершает вторую главу раздел 2.2. посвященный СМО с относительным приоритетом М2/ М III к I Эта система ранее изучалась в работе2, однако в указанной работе, во-первых, применялось иное построение фазового пространства; во-вторых, вычислялись не все вероятности состояний накопителя;, а лишь вероятности потери; в-третьих, отсутствовало полное

численное исследование модели. В диссертации доказаны лемма 2.2, задающая вид СУР, теорема 2.4, определяющая выражение производящей функции, теорема 2.5, выражающая все вероятности через «диагональные», а также теорема 2.6, дающая вид укороченной системы уравнений в случае действия относительного приоритета. Эти теоремы аналогичны ранее разобранным, и в автореферате не приводятся.

Решение, полученное для этих двух систем, позволяет сделать вывод о возможности создание общего метода решения подобных задач. Для получения решения с использованием предложенного метода для рассматриваемых систем вначале выводится полная СУР, затем по ней вычисляется производящая функция, используя условия аналитичности которой, получается выражения вероятностей состояний системы только через «опорные» состояния и строится «укороченная» система, решение которой позволяет найти полный набор вероятностей состояний модели. Убедимся, что метод дает результаты и для систем с более сложными приоритетными дисциплинами.

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

Вначале изучается чередующийся приоритет для системы класса

Мг1 М III к I fl , состояния которой характеризуется трехмерным фазовым вектором {7V0 (/), TV, (i), (/)}, где N\ и N2 имеют тот же смысл, что и в случае относительного приоритета, a N0 задает тип требования, которое в данный момент обслуживается. Фазовое пространство задается в виде

П = {(/;,/, J): п = U; / = О.Л-1; j = 0,*-1-/},

а размеченный граф состояний состоит из двух подграфов, аналогичных графу для системы с относительным приоритетом и связанных друг с другом системой переходов, представленной на рис. 2.

Как и раньше, довольствуемся изучением только установившегося режима, обозначив финальные вероятности через Р'"] , где п означает тип

обслуживаемого требования, а г и_/ - число требований в накопителе. Вид СУР описанной СМО определяется леммой 3.1.

........... '<!....................................¡' 0 !■••■■

..я

' -■ ■■"•»■■-. . <<, .........:: .. ..........■■*-.,.

■i t.0.0 I ц \ i.1,0 \ Li' jj "l.i ц lu-u); . 2 an......... .'.!,"

if.....;................Д&

7...........i................ , и ".......... # 41"

* .............J/>,(u'l.....1 f 2>| jA • :.«-!)>

* .............ii* Л чк. ^

.■!»■» I.....H»^ •

-с........ .......' ы т; .......

.-«'. \ ..1 :.... - «A

/Ш-lj ,,

Рис. 2. Размеченный граф состояний для СМО М2 / М III к/ /3'.

Лемма 3.1. Система уравнений равновесия для СМО М21М IIIkl/3' имеет вид

(М + (Л, + A,XI ■"S,tJk ,) + ,(1 -Sj0))P*'; = Л, (1 -Sia)/>">, + Л(1 -SJja)l*>, +

(ц + (Л, + Л)(1 -S,м) + аЛ,Slt)к ,(1 -S, 0))/><;> = ЛДЛ.оЯ0 + Л, (1 - $ л )f*. +

где индексы i и / удовлетворяют условиям i = 0,k-\-, j = 0,k-\-i.

Из-за наличия двух различных наборов вероятностей состояния Ff"} , отвечающих п = 1 и и = 2, определение производящей функции (3) требует обобщения и приобретает вид

2 А-1 i-1-i

<7(«,г,И-) = ]Г£ £ ^j'»'^""1 =Cni(»,v) + u'Cl2|(«,v). (11)

и=| /=0 j=0

где G{n)(u,v) означает условную производящую функцию при условии, что обслуживается требование и-го типа.

В разделе 3.1.2 доказана теорема, устанавливающая конкретный вид каждой из функций G("'(z/,v) при п=12.

Теорема 3.1. Для СМО с чередующимся приоритетом

M2/M/iikif;

условные производящие функции Gm(u,v) и G{2\u,v), определяемые согласно (11), удовлетворяют уравнениям

[(1 + р) - (р,н + /V') -11и]вт(11, V) = рхРа + ((р -ар,)- (р,ч + Р2у) +

+ар,и / + т О'*О "«' / V) + (//,()) - Р™ - С'"(О, V)] / и,

(12)

[(1 + р) - (р,;/ + р2г) -1 / у^1-1 (г/, V) = р2Р0 + ((р - ар,) - (р,н + р, V) +

+ар,у / ;/)£ + [-С2)(", 0)-+ С'ЧО, V)-О7 у+ I и).

1=0

Подобно ранее полученному для случая абсолютного приоритета выражению (4), выражения (12) представляют собой лишь промежуточный результат вычислений из-за наличия в них четырех наборов неизвестных пока вероятностей Л^&оЛО^ЛС^ Для . вычисления этих

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

Эти четыре группы уравнений вытекают из условий аналитичности и выводятся тем же путем, как и в главе 2. Вначале приравниваем к нулю

значения С'"(", V) по аргументу и в точках и = и\ и н = г/2, являющихся корнями знаменателя (7(1)(г;,у). Затем сокращаем числитель и знаменатель на (и-и\) и (и-и2). Подобным же образом поступаем с корнями знаменателя С'2](и,\') по аргументу у. В результате функция С(<>(и,у) оказывается выраженной через вероятности и/*21, а С'21 - через Выделяя в этих выражениях

коэффициенты при членах, имеющих суммарную (£-1,)-ю степень по и и V, а также переходя к пределу при и —»0 в выражении для С(|)(г/,у) и при V—>0 в выражении для (712)(и,у) , получаем искомую систему 4£-2 «укороченных» уравнений относительно такого же числа неизвестных.

Подробные выкладки приведены в разделе 3.1.3, где доказана следующая теорема, аналогичная теоремам 2.2 и 2.5.

Теорема 3.2. Вероятности произвольных состояний СМО

М2 / М /1/ к / /3 вЫражаются через вероятности «диагональных» состояний „(1) _ р(0 „(2) _ р(2)

р, — 1 к /Л — ¡,к-\-1 и вероятности «граничных» состоянии = Сл'2' = Раформулам

-«2>Г 5-Д'М , 2(С)+ (13)

¿•=0 Л'=0

+р(:~'р21 лет,

где С = р,12(1 + д + = р-]'2( 1 + р,+ /л);Д = -р2р~ш-,Р2 = 1/2.

Для получения итоговой «укороченной» системы уравнений необходимо найти пределы при и—>0 в выражении для СП)(»,у) и при v—»0 в выражении для 0<2)(»,у), используя (13). Эти выражения дают 2к-2 условий. Также еще 2к уравнений дают условия, которые получаются после подстановки у = к-\ в выражения (13). Ввиду их громоздкости в автореферате они не приводятся, но описаны в третьей главе диссертации. Таким образом, разработанный в диссертации метод позволяет снизить порядок решаемой СУР (10), равный А'(&+1), до величины 4к-2.

Завершает третью главу анализ системы с вероятностным приоритетом класса М2/МII/к//4'. В этой СМО формируются две очереди из требований различных типов, суммарная длина которых ограничена общей емкостью накопителя, равной к-1. При освобождении канала обслуживания на него с заданной вероятностью Э3| поступает требование из очереди первого типа, а с вероятностью эй2=1-эв1 берется требование из очереди второго типа.

Фазовое пространство здесь строится аналогично случаю относительного приоритета, разобранному в разделе 2.5. Компоненты фазового вектора характеризуют число требований в накопителе, а размеченный граф состояний имеет вид, представленный на рис. 3.

Исследование данной системы удается провести тем же самым общим методом, который применялся к другим рассмотренным в работе системам. Вначале строится исходная СУР (лемма 3.2), по ней выводится выражение для производящей функции (теорема 3.4). Далее устраняются корни знаменателя н=п\ и и=и2, в результате чего все вероятности состояний выражаются через «диагональные» и «граничные» вероятности размеченного графа на рис. 3 (теорема 3.5), а для последних описан алгоритм получения «укороченной» системы.

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

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

"1

; «-о 1. .£.." И \

-г

АЛ /«г. /ц

л - Л

//эе. 1,1 А*, их.

V - , У ч

Л; А . Л

Рис. 3. Размеченный граф состояний для СМО Мг/М 1\1к//4'.

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

Лемма 4.1. Вероятности потери каждого типа заявок выражаются в случае абсолютного приоритета в виде (14), относительного и вероятностного в виде (15), а чередующегося приоритета в виде (16).

-1 I,- ~ 1

. Р\ ^ „ , Р\

1=1 Рг /=1 Рг

ы Рг м

С = А1," + О -«)£ А<" + «'Л(2) + X АИ, /=1 А] (=1 ;»о

=А1,21+о ■- «)Е р!»+«а1"+Ё А1"-

/.1 Аг

(14)

(15)

(16)

Необходимо отдельно отметить удобство полученных «укороченных» систем линейных уравнений для вычисления такой характеристики как вероятность потери требований. В качестве неизвестных в системе рассматриваются все необходимые для вычисления вероятности. Выталкивающий механизм в рассмотренных системах проявляет себя только в случае сильной загруженности систем, поэтому в качестве основных случаев для рассмотрения были выбраны случаи суммарной относительной загрузки системы большие единицы. На рис. 4 приведены зависимости для системы с абсолютным приоритетом при нагрузках: р, =0.2,р2 =0.9И р] =1.2,р2 =0.2

Рис. 4. Вероятность потери заявок для системы с абсолютным приоритетом с

Я =0.2,А=0.9и д =1.2,^=0.2.

Полученные зависимости позволяют сделать вывод о существовании вариантов загрузки системы, при которых наблюдается линейный характер зависимости вероятности потери от параметра выталкивающего механизма. Ранее было показано, что МПФ дает возможность получения аналитического решения при значениях а = О и а = 1 для рассматриваемых систем. Это позволяет ввести понятие области линейности - областей в пространстве аргументов (рх,рг), в которых зависимость вероятности потери от параметра вероятностного выталкивающего механизма а имеет линейный вид или по крайней мере близка к нему. Для построения таких областей используется линейная аппроксимация, которая может быть построена по двум крайним точкам с известным заранее аналитическим решением. Примеры этих областей показаны на рис. 5.

Рис. 5. Области линейности по высокоприоритетным и низкоприоритетным заявкам для системы с вероятностным приоритетом при параметре ее, = 0.5

Еще один эффект, который можно выявить по результатам анализа рис. 4 - это существование набора загрузок системы, при которых происходит «запирание» (близость вероятности потери к единице) системы для неприоритетных требований. Таким же образом, как и для областей линейности, вводится понятие области запирания - области в пространстве коэффициентов загрузки (р,,р2) , в которой вероятность потери низкоприоритетного требования превосходит заданный уровень при достаточно больших значениях параметра

вероятностного выталкивающего механизма а . Примеры таких областей приведены на рис. 6.

Рис. 6. Области запирания системы с вероятностным приоритетом при

аз, е{0;0.5;1}

Основные результаты работы:

1. Предложено расширение системы обозначений приоритетных СМО Г.П. Башарина на случаи чередующегося и вероятностного приоритетов;

2. Предложены новые модели приоритетных СМО с вероятностным выталкиванием. В качестве новых моделей предлагаются системы классов М2/ М/\/к/ f. при 2 < i < 4;

3. Разработан метод исследования указанных моделей, основанный на методе производящих функций, позволяющий снизить вычислительную сложность задачи для всех рассматриваемых систем с величины пропорциональной к' до к\

4. Разработан программный комплекс на языке математического пакета MATLAB, реализующий алгоритмы вычисления вероятностей потери требований с использованием: исходной системы уравнений равновесия; «укороченной» системы уравнений, полученной по результатам применения метода;

5. Детально изучена зависимость вероятности потери требований от параметра выталкивания. Исследована зависимость вероятности потери от интенсивностей входящих потоков, объема накопителя и параметра выталкивающего механизма. Детально исследована характеристика вероятностей потери требований, поступающих на вход системы;

6. Введено понятие области «запирания» системы и найдены границы этих областей для всех рассматриваемых систем;

7. Введено понятие области «линейности» для вероятности потери требований и найдены границы этих областей для всех рассмотренных систем и всех типов требований.

Список публикаций автора по теме диссертации

1. Ilyashenko A., Zayats О., Muliukha V., Laboshin L. Further Investigations of the Priority Queuing System with Preemptive Priority and Randomized Push-Out Mechanism // Lecture Notes in Computer Science, vol. 8638,2014, p. 433-443

2. Заборовскнй B.C., Кондратьев А.С., Силиненко А.В., Мулюха В.А., Ильяшенко А.С., Филиппов М.С. Удаленное управление робототехническими объектами в космических экспериментах серии «Контур» // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление, 2012, №6, с. 23-32

3. Заборовскнй B.C., Гук М.Ю., Ильяшенко А.С., Мулюха В.А., Силиненко А.В., Селезнев К.С. Программное обеспечение для отработки алгоритмов сетевого интерактивного управления роботами с борта МКС // Программная инженерия, 2013, №12, с. 20-26

4. Заборовскнй B.C., Ильяшенко А.С., Мулюха В.А. Алгоритмы управления характеристиками потоков пакетных данных в сетевой среде с использованием приоритетного вероятностного выталкивающего механизма // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление, 2013, №6, с. 35-44

5. Muliukha V., Ilyashenko A., Zayats О., Zaborovsky V. Randomized push-out mechanism in priority queuing systems // Proceedings of the International Conference "Numerical Computations: Theory and Algorithms", Falerna: 2013, p. 102

6. Zaborovsky V., Mulyukha V., Ilyashenko A., Zayats O. Access control in a form of active queuing management in multipurpose operation networks // International Journal On Advances in Networks and Services, 2011, vol. 4, no. 3/4, p. 363-374

7. Zaborovsky V.,Mulyukha V.,Ilyashenko A.,Zayats O. Preemptive priority queueing system with finite buffer size and randomized push-out mechanism // Modem Traffic and Transportation Engineering Research,2012,vol.l,no.2,p.46-53

8. Ильяшенко A.C., Заяц О.И., Заборовскнй B.C. Моделирование вероятностного выталкивающего механизма для двухпотоковой системы массового обслуживания с абсолютным приоритетом // Материалы XLII Недели науки СПбГПУ, Институт прикладной математики и механики, 2014, с. 283-285

9. Ильяшенко А.С., Заборовскнй B.C. Программное обеспечение для расчета вероятностных характеристик двухпотоковых систем массового обслуживания с вероятностным выталкивающим механизмом. Свидетельство о государственной регистрации программы для ЭВМ № 2012619598, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 24.10.2012.

Подписано в печать 16.12.2014. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Тираж 100. Заказ 12585b.

Отпечатано с готового оригинал-макета, предоставленного автором, в Типографии Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.: (812) 552-77-17; 550-40-14