Динамическое распределение нагрузки в сетях массового обслуживания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

□ ОЗОьи1 1 '

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

Рогачко Екатерина Сергеевна

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

01 01 09 - Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

2 4 МАЙ 2007

Саратов - 2007

003060117

Работа выполнена на кафедре системного анализа и автоматического управления Саратовского государственного университета

им Н Г Чернышевского

Научный руководитель

доктор технических наук, профессор

Митрофанов Юрий Иванович

Официальные оппоненты

доктор физико-математических наук, профессор

Розен Виктор Владимирович

кандидат физико-математических наук, доцент

Орлов Сергей Дмитриевич

Ведущая организация

Институт проблем точной механики и управления РАН

Защита состоится 31 мая 2007 г в 16 час 30 мин на заседании диссертационного совета К 212 243 02 в Саратовском государственном университете им Н Г Чернышевского по адресу. 410012, г Саратов, ул Астраханская, 83

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета им Н Г. Чернышевского

Автореферат разослан с^^5~алреля 2007 г

Ученый секретарь диссертационного совета к ф -м н, доцент ^ОЙо^ В В Корнев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы При проектировании, развитии и эксплуатации больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС), получивших в настоящее время широкое распространение и использование, возникает необходимость решения широкого спектра задач анализа, синтеза и оптимизации систем этого класса Примерами БСС могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы Использование в данных системах развитых подсистем управления существенно повышает уровень требований к используемым при решении этих задач математическим моделям и методам Практический опыт решения данных задач показал перспективность и эффективность использования в качестве математических моделей БСС сетей массового обслуживания Это обусловило интенсивное развитие в течение последних четырех десятилетий теории сетей массового обслуживания и методов их управления и анализа. Большой вклад в развитие теории, методов управления, анализа, оптимизации и синтеза сетей массового обслуживания внесли отечественные ученые А А Боровков, Г П Башарин, В М Вишневский, П П Бочаров, В А Ивницкий, В. В. Рыков, А В Печинкин, В А Жожикашвили. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых, как Дж Джексон, Л Клейнрок, Ф. Келли, К Чэнди, Д Тауслей, М Райзер, Дж. Уолрэнд

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

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

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

В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ «Теория и методы управления сетями массового обслуживания» (шифр «Звено», roc per № 01960007744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», roc per №01200001098), «Динамическое управление сетями массового обслуживания» (шифр «Темп», roc per № 01200201953), «Анализ сетей массового обслуживания с динамическим управлением» (шифр «Тракт», roc per. № 01200602692), «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», roc per № 01200002986)

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

Основные задачи

1. Исследование зависимости эволюции сетей массового обслуживания от их параметров

2 Разработка и исследование методов управления распределением нагрузки в сетях массового обслуживания

3 Разработка и исследование методов анализа сетей массового обслуживания с управлением распределением нагрузки.

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

Научная новизна Полученные в диссертационной работе результаты являются новыми Основными результатами являются следующие

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

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

3 Проведено исследование эффективности методов динамического управления распределением нагрузки в сетях массового обслуживания

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

Теоретическая и практическая значимость Работа носит теоретический характер Научные результаты диссертационной работы представляют вклад

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

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

Апробация работы. Результаты докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Международной научной конференции «Компьютерные науки и информационные технологии» (14—18 мая 2002 года, г Саратов), Международной конференции «Проблемы и перспективы прецизионной механики и управления в машиностроении» (14-19 октября 2002 года, г. Саратов), Ежегодной межвузовской научной конференции «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г Саратов), представлены и обсуждались на Шестом и Седьмом Всероссийских симпозиумах по прикладной и промышленной математике (1-7 октября 2005 года, г Сочи-Дагомыс, 2-8 мая 2006 года, г. Кисловодск)

Публикации По результатам диссертации опубликовано 7 работ

Структура и объем диссертации Диссертация состоит из введения, четырех глав и заключения Объем диссертации 102 страницы. Диссертация содержит 15 таблиц. Список литературы включает 94 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит общую характеристику работы

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

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

Рассматривается замкнутая экспоненциальная сеть массового обслуживания N с Ь системами массового обслуживания 5,, / = 1, . типа М/М/1 с интенсивностями обслуживания /у,, О требованиями одного класса, неприводимой маршрутной матрицей 0 = (0у), /,у = 1, и управлением распределением нагрузки Состояние с номером п сети определяется вектором s{") = где - число требований, находящихся в 5, Мно-

жество X состояний сети имеет мощность сх = ¡Л^, множество номеров состояний сети В = {1, ,сх} Для каждого состояния л'-"'1 е X задана характеристика У^") — потенциал состояния (неотрицательное вещественное число), который определяет значимость пребывания сети в данном состоянии для достижения требуемых значений заданных характеристик качества ее функционирования Если для состояний .у'"' и имеет место соотношение у(") > у(т>) т0 полагается, что качество функционирования сети при ее пребывании в состоянии л(п) выше, чем при пребывании в состоянии Нумерация состояний производится по убыванию потенциалов

В процессе функционирования сети N производится динамическое управление распределением нагрузки в сети централизованной системой управления, реализуемое посредством соответствующего управления маршрутизацией и интенсивностями обслуживания. Под управлением распределением нагрузки понимается управление распределением требований по системам сети массового обслуживания с целью обеспечения наилучшего приближения математического ожидания числа требований в системах сети к их требуемому распределению Требуемое распределение нагрузки определяется соответствующим заданием некоторого состояния сети = (я°), называемого базовым Базовое состояние имеет номер 1 и наибольший потенциал Выбор в качестве базового некоторого состояния сети обуславливается необходимостью достижения требуемых значений заданной стационарной характеристики сети, например, пропускной способности сети, общих задержек обслуживания или коэффициентов использования ресурсов сети массового обслуживания.

Обозначим я* — математическое ожидание числа требований в 5,, и* - математическое ожидание длительности пребывания требований в 5, Введем условие и* <£, где 8 > О - заданная величина

Теорема 2.1. Если для сети N без управления выполняется условие * — 0 — 1 т

то интенсивность обслуживания в системе 5,

77 -^«б-'К+б) Т

где

Вектор со = (со,), i=l, , X, является решением уравнения соО = со с условием нормировки со, = 1

В качестве вектора // = (/;,) для сети N может быть выбран вектор

/7 = (Д,)> i = Л

Теорема 2 2. Если для сети N без управления при векторе интенсив-ностей обслуживания ,« = (//,), г = 1, ,L, выполняются равенства

s* = сг, z = l, ,L,

где сг = Q/L, то стационарные вероятности состояний сети N без управления

/>(5(»)) = -1_, s(»)ej5T

сх

Множество X делится на подмножества Y и Z доминантных и ординарных состояний, сг = |У| и сz = \Z\ В множество Y включаются состояния сети, пребывание в которых обеспечивает значение основной характеристики качества функционирования сети более близкое к требуемому значению, чем пребывание в ординарных состояниях При определении потенциалов и формировании множеств У и Z используется вектор Ь = (bt), b,> О, i = l, ,L, граничных значений числа требований в системах обслуживания Состояния /"'el, для которых -sjj < Ь,, íg{1,. ,L}, относятся к

множеству Y, остальные состояния - к множеству Z

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

Метод управления распределением нагрузки в сети N состоит в следующем Различаются два режима функционирования сети N - нормальный и коррективный Периоды функционирования сети в этих режимах называются соответственно нормальными и коррективными тактами Вид очередного такта определяется типом состояния (доминантное или ординарное) сети в момент завершения предшествующего такта Нормальный такт длительности (р начинается в некотором доминантном состоянии, а заканчивается или в доминантном состоянии или в ординарном состоянии Коррективный такт начинается в некотором ординарном состоянии, а заканчивается либо в

базовом состоянии s° в момент перехода в него сети, если это событие происходит до завершения такта длительности <р, либо в доминантном или ординарном состоянии в момент завершения такта длительности <р Обозначим через T]J длительность коррективного такта, начавшегося в состоянии

Нормальный и коррективный такты отличаются способами маршрутизации требований и используемыми в течение тактов интенсивностями обслуживания в системах В нормальном такте маршрутизация осуществляется с использованием маршрутной матрицы ©, в коррективном такте - с использованием матриц передач N^ (нуль-единичных матриц, определяющих маршруты требований, завершивших обслуживание в системах, при пребывании сети в определенном состоянии) В нормальном такте используется вектор интенсивностей обслуживания fi = {ju,), i = 1, ,L, в коррективном такте, если предшествующий такт закончился в ординарном состоянии s(Cr +J\ J е{ 1, , cz}, - коррективный вектор J2J = (juf) Теорема 2.8. Матрицы передач

М<> обеспечивают в течение коррективного такта эволюцию сети N в направлении базового состояния s°

Теорема 2.9. Если коррективный такт начинается в состоянии S(cr+J) е х, то вектор интенсивностей обслуживания pJ обеспечивает в течение этого такта эволюцию сети N в направлении базового состояния

о

S

Рассмотрим модель эволюции сети обслуживания с управлением распределением нагрузки Эволюция сети N в течение нормальных тактов описывается цепью Маркова С с множеством состояний В, непрерывным временем и множеством начальных состояний {1, ,cY}, а в течение коррективных тактов - цепями Маркова CJ, J е {1, .,cz}, с множеством состояний В, непрерывным временем и начальными состояниями cY + J Длительности реализаций цепей С и С"7 равны длительностям соответственно нормального такта <р и коррективного такта T]J Обозначим iw=(p®),

pWJ = (РтУ), т, п = 1, ,сх, матрицы вероятностей перехода за время t

соответствующих цепей Маркова С и CJ

Теорема 2.10. Если коррективный такт начинается в состоянии s(cy+j)^ jgjj^ ,сz}, то математическое ожидание его длительности

tjj-' =]tdFJ(t) + <p[l-FJ(<P)l о

где FJ (t) - функция распределения времени первого достижения сетью N состояния s° при начале эволюции сети N из состояния s^CY

8

Теорема 2.11. При заданном значении <р стационарное распределение и = (тгп ), п = 1, , Су , вероятностей состояний сети N существует, является единственным и удовлетворяет системе уравнений = + . »

т=1 J=l

с условием

2>»=1

пеВ

Нахождение стационарного распределения вероятностей состояний сети Л^ по теореме 2 11 связано с решением системы линейных алгебраических уравнений С увеличением мощности множества состояний сети в существенной степени возрастает объем необходимых вычислений Далее в теореме 2 13 предлагается другой метод вычисления стационарного распределения вероятностей состояний сети N, являющийся приближенным

Обозначим ртп{<р) - средняя вероятность пребывания цепи С в состоянии п е В в течение интервала времени <р при начальном состоянии т е{\, , с}}, Pcy+J л07Л*) ~ средняя вероятность пребывания цепи С"7 в

состоянии п в течение интервала времени г}'3,'

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

п _/ Р' и = 1> >сУ>

Рп~\ Л» 1 г

[т)',п=сг+\, ,сх^-п-су

Обозначим через С, - (£"„), п = I,. ,сх, стационарное распределение процесса Г

Теорема 2.13. При заданном значении (р средние значения л" стационарных вероятностей я„, пеВ, состояний сети N определяются по формулам

< = I (п, Ртп (?) + £ Ссг ^ К^ я^-7'*)' иеб

т=1 ./=1

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

Рассматривается сеть N с параметрами, определенными в главе 2, состоящая из J подсетей NЕ, ^ = 1, Множество номеров подсетей обозначим через Д = {1, Множество X состояний сети определяется так

9

же, как и в главе 2 Введем в рассмотрение вектор cr(t) = F = 1, , J,

/t 6 {], определяющий £-й способ распределения требований меж-

ду J подсетями, - число требований, находящихся в NF, ЛГ - число способов распределения требований между подсетями В случае, когда распределение требований в сети N определено вектором сг1к>, сеть будем называть к-й реализацией сети N и обозначать N(k) Учитывая все способы распределения и соответственно все реализации сети N, можно считать, что сеть N является совокупностью всех реализаций N(k) этой сети Реализация N(k) имеет множество состояний Хк; множество номеров принадлежащих Хк состояний обозначим Вк Вектор назовем макросостоянием сети N, множество макросостояний сети N обозначим через Е

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

В качестве матрицы 0 сети N без управления может использоваться маршрутная матрица, обеспечивающая значения математических ожиданий числа требований в подсетях близкими к значениям, определенным базовым распределением сг(1\ более точно, некоторьм состоянием i^elj, которое

будем обозначать s° Рассмотрим сеть массового обслуживания N, которая отличается от сети N без управления только маршрутной матрицей Определим вектор То относительных интенсивностей потоков требований для сети N, при котором математическое ожидание s' числа требований в системе S, равно s°, i = l, ,L Затем для полученного вектора со формируется маршрутная матрица сети массового обслуживания

Теорема 3.1. Если для сети N выполняется условие

Sj ^ , Z = 1, , ,

то относительная интенсивность потока требований в систему S,

<о,=-^-/ j L

(Q-1K+Q/

Множество Е макросостояний сети разбивается на два подмножества Н и U — доминантных и ординарных макросостояний соответственно К доминантным относятся макросостояния, при пребывании в которых распределение требований между подсетями ближе к требуемому, чем при пребывании в ординарных макросостояниях, в частности, сг(1) е Н Обозначим через D и W множества номеров соответственно доминантных и ординарных макросостояний При формировании множеств Н и U используются векто-

10

ры <5 <*)=(5^)), =а<гк)-ар, * = 1, .,К, ^ = I, .,7, и вектор = граничных значений числа требований в подсетях Макросостояния сг(*\ Ле{1, ,А'}, для которых справедливы неравенства F = 1, ,./, относятся к множеству Н, остальные макросостояния - к множеству и

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

Рассмотрим метод динамического управления распределением нагрузки в сети N Так же, как и в главе 2, предполагается, что в сети обслуживания реализована централизованная система управления. Различаются нормальные и коррективные такты функционирования сети Нормальный такт начинается всегда в одном из доминантных, а коррективный такт — в одном из ординарных макросостояний В момент окончания каждого такта формируются управляющие воздействия, направляемые системам обслуживания с целью идентификации макросостояния сети в данный момент времени и определяющие новые значения элементов маршрутной матрицы сети Все такты имеют фиксированную длительность (р. Режимы функционирования отличаются используемыми в сети маршрутными матрицами - в нормальном такте используется всегда матрица 0 = ), в коррективном такте - матрица

= (в^), соответствующая макросостоянию сети сг(*\ к е IV, в момент окончания предшествующего такта

При формировании матрицы в качестве исходной используется матрица ©, которая модифицируется соответственно концепции «замыкания» потоков требований в сети обслуживания Граничными далее будут называться системы, непосредственно связанные с системами обслуживания из других подсетей Граничные системы могут быть трех типов - входные, выходные и стандартные Входной называется система, в которую могут только поступать требования из других подсетей Выходной - система, из которой возможен только переход требований в другие подсети. Стандартной - система, в которую могут поступать требования из других подсетей и из которой могут переходить требования в другие подсети Этапы формирования матрицы ©^ 1. Определяются подсети Nх и Nу такие, что

ГеК у

Обозначим С1Х и £1у множества номеров подсетей, смежных соответственно подсети Nх и подсети Nу

2 Потоки требований, выходящих из граничных выходных или стандартных систем подсети Nх в граничные входные или стандартные системы смежных подсетей Ыс, С е направляются в соответствующие системы подсети N:c

3. Для всех подсетей Ыс, СбПу, потоки требований, выходящих из граничных выходных или стандартных систем подсети Ма в граничные входные или стандартные системы подсети Nу, направляются в соответствующие системы подсети

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

Рассмотрим модель эволюции сети N Принимая во внимание параметры и алгоритмы функционирования сети N, ее эволюцию в течение нормальных тактов можно описывать цепью Маркова С с множеством состояний В, непрерывным временем и множеством начальных состояний ,

кеБ, а в течение коррективных тактов - цепями Маркова С*, к е IV, с множеством состояний В, непрерывным временем и множествами начальных состояний Вк соответственно Длительности реализаций цепей С и С* равны (р Обозначим Р^ ={р<$1), т, п -1, . ,сх, - матрица вероятностей перехода за время ф цепи С, = (р^'к) - матрица вероятностей пере-

хода за время ф цепи Ск, к е IV

Теорема 3.3. При заданном значении ф стационарное распределение п - (я-„), и = 1, , сх, вероятностей состояний сети N существует, является единственным и удовлетворяет уравнению

п=1

где Р = (рт„), т,п = 1, ,сх, — матрица вероятностей перехода описывающего эволюцию сети N случайного процесса Е,

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

К — 7сР

с условием

почти полностью разложимой, те Р = Р* + ¿А, где Р' - полностью разложимая матрица, Д - вещественная матрица, <1 — вещественное число Если предполагается, что сеть N является почти полностью декомпозируемой, то возможно ее представление на коротких периодах времени в виде полностью декомпозируемой сети Ы', образованной отдельными несвязанными подсетями Ыр, Р = 1, , У В течение длительного периода времени сеть N можно рассматривать как множество отношений между J связанными подсетями, пренебрегая отношениями внутри каждой подсети Обозначим через л'„(к) стационарную вероятность пребывания сети N в состоянии

Теорема 3.4. Вероятности перехода рк1 между макросостояниями, соответствующими множествам Хк и Хг, случайного процесса Z, описывающего эволюцию сети N в течение длительного периода времени, определяются по формулам

Рк1=Цят(к)^рщпг к,Ы\, ,К

т-1 п 1

Обозначим через £ = & = 1, -, К, вектор стационарного распределения процесса Ъ, а я = (л(к)), л (к) = (лп(к)), п = \, ,сХк, вектор стационарного распределения сети N

Теорема 3.5. Приближенные значения л'¡¡(к) вероятностей лп (к) определяются по формулам

яая(к) = $кяп{к), п = \,.,сХк.к = \, ,К,

обеспечивающим точность приближения порядка величины с1 из равенства Р = Р* +с!А

В четвертой главе приводятся и обсуждаются результаты исследования замкнутых сетей обслуживания с динамическим управлением распределением нагрузки Проводится сравнительный анализ методов динамического управления распределением нагрузки между системами в сети массового обслуживания, основанных на использовании управления интенсивностями обслуживания и маршрутизацией. Приводятся результаты исследования эффективности предложенных методов динамического управления распределением нагрузки в сетях обслуживания Сравнение результатов аналитического и имитационного моделирования показывает приемлемую для практических приложений точность методов анализа сетей массового обслуживания с динамическим управлением распределением нагрузки Важным параметром метода управления является длительность такта <р При уменьшении ср интенсивность управления и эффективность управления возрастают, что приводит к росту /г(К) (или л(Н)).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 Разработаны методы динамического управления распределением нагрузки между системами и между подсетями в сетях массового обслуживания и проведено исследование их эффективности

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Митрофанов Ю И, Рогачко Е С. Анализ сетей массового обслуживания с управлением распределением нагрузки // Тезисы докл Шестого Всероссийского симпозиума по прикладной и промышленной математике. Обозрение прикладной и промышленной математики, 2005, Том 12, Вып 4, С 1039-1040

Е С Рогачко принадлежат метод анализа сетей массового обслуживания с управлением распределением нагрузки между системами и результаты исследования методом численного моделирования эффективности метода управления

Ю И Митрофанову принадлежат принципы динамического управления распределением нагрузки между системами в сетях массового обслуживания

2 Митрофанов Ю И., Рогачко Е С Динамическое управление распределением нагрузки между подсетями замкнутой сети массового обслуживания // Тезисы докл Седьмого Всероссийского симпозиума по прикладной и промышленной математике Обозрение прикладной и промышленной математики, 2006, Том 13, Вып 3, С 521-522

Е С Рогачко принадлежит метод анализа сетей массового обслуживания с управлением распределением нагрузки между подсетями

Ю И Митрофанову принадлежат основные положения метода динамического управления распределением нагрузки между подсетями в сетях массового обслуживания

3 Митрофанов Ю И, Рогачко Е С Метод динамического управления распределением нагрузки между подсетями замкнутой сети массового обслуживания // Автоматика и вычислительная техника, 2006, № 4, С 3-13

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

Ю И Митрофанову принадлежат концепция динамического управления распределением нагрузки между подсетями в сети массового обслуживания и модель эволюции сети с управлением распределением нагрузки между подсетями

4 Митрофанов Ю И, Рогачко Е С Модели и анализ сетей массового обслуживания с динамическим управлением распределением нагрузки // Автоматика и вычислительная техника, 2006, № 5, С. 69-77.

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

Ю И Митрофанову принадлежат постановка задачи управления распределением нагрузки в сетях массового обслуживания и модели эволюции сети с управлением распределением нагрузки между системами

5 Митрофанов Ю И, Рогачко Е С Об управлении распределением нагрузки в замкнутых сетях массового обслуживания // Теоретические проблемы информатики и ее приложений Сб науч тр Саратов изд-во Сарат унта, 2003, Выл 5, С 107-111

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

Ю И Митрофанову принадлежат принципы управления распределением нагрузки между подсетями в сетях массового обслуживания

6 Митрофанов Ю И, Рогачко Е С Оптимизация потоков в открытых сетях массового обслуживания // Проблемы и перспективы прецизионной механики и управления в машиностроении Материалы Международной конференции Саратов, 2002, С 210-211

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

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

7 Рогачко Е.С, Фокина Н П Динамическое управление распределением нагрузки в замкнутых сетях массового обслуживания Саратов, 2005 Деп в ВИНИТИ 17 05 05, №711-В2005 16 с

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

Н П Фокиной принадлежат алгоритмы методов маршрутизации, использованные при разработке программы имитационного моделирования

Работы [1, 2] опубликованы в журнале, включенном в перечень ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени кандидата наук

Подписано в печать 20 04 2007 Формат 60x84 1/16 Бумага офсетная Гарнитура Times Печать RISO Объем 1,0 печ л Тираж! 00 экз Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю Б Свидетельство № 304645506500043 410600, г Саратов, ул Московская, 152, офис 19

Введение

Глава 1. Обзор основных результатов исследования сетей массового обслуживания с управлением распределением нагрузки

1.1. Динамическое распределение нагрузки

1.2. Оптимальное распределение нагрузки

1.3. Анализ сетей обслуживания с управлением распределением нагрузки

Глава 2. Динамическое распределение нагрузки в сетях массового обслуживания

2.1. Постановка задачи

2.2. Формирование оптимального вектора интенсивностей обслуживания

2.3. Выбор базового состояния

2.4. Метод динамического управления распределением нагрузки в сети обслуживания

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

Глава 3. Динамическое распределение нагрузки между подсетями в сетях массового обслуживания

3.1. Постановка задачи

3.2. Формирование оптимальной маршрутной матрицы

3.3. Алгоритм формирования коррективных маршрутных матриц

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

Глава 4. Исследование сетей массового обслуживания с управлением распределением нагрузки

4.1. Исследование методов динамического управления распределением нагрузки в сети обслуживания

4.2. Исследование эффективности метода управления распределением нагрузки в сети обслуживания

4 .3. Исследование эффективности метода управления распределением нагрузки между подсетями в сети обслуживания

При проектировании и эксплуатации больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС), имеющих на современном этапе развития общества широкое распространение и использование, возникает необходимость решения задач анализа, синтеза и оптимизации систем этого класса. Примерами БСС могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы. Использование в системах этого класса развитых подсистем управления со сложными алгоритмами управления существенно повышает уровень требований к используемым при решении задач анализа, синтеза и оптимизации математическим моделям и методам. Практический опыт решения этих задач показал перспективность и эффективность использования сетей массового обслуживания в качестве математических моделей БСС. Это обусловило интенсивное развитие в течение последних четырех десятилетий теории сетей массового обслуживания и методов их анализа и синтеза [3-8, 11, 12, 16-19, 23, 27, 28, 30, 45, 52, 58, 60-62, 67, 69, 82]. Большой вклад в развитие теории, методов анализа, оптимизации и синтеза сетей массового обслуживания внесли А. А. Боровков, Г. П. Башарин, В. М. Вишневский, П. П. Бочаров, В. А. Ивницкий, В. В. Рыков, А. В. Печинкин, В. А. Жожикашвили. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых как Дж. Джексон, Л. Клейнрок, Ф. Келли, К. Чэнди, Д. Тауслей, М. Райзер, Дж. Уолрэнд.

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

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

В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ: «Теория и методы управления сетями массового обслуживания» (шифр «Звено», гос. per. № 01960007744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», гос. per. № 01200001098), «Динамическое управление сетями массового обслуживания» (шифр «Темп», гос. per. № 01200201953), «Анализ сетей массового обслуживания с динамическим управлением» (шифр «Тракт», гос. per. № 01200602692), «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», гос. per. № 01200002986).

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

Основными задачами, решаемыми в диссертации, являются следующие.

1. Исследование зависимости эволюции сетей массового обслуживания от их параметров.

2. Разработка и исследование методов управления распределением нагрузки в сетях массового обслуживания.

3. Разработка и исследование методов анализа сетей массового обслуживания с управлением распределением нагрузки.

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

В диссертационной работе получены следующие основные результаты.

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

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

3. Проведено исследование эффективности методов динамического управления распределением нагрузки в сетях массового обслуживания.

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

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

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

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

Результаты диссертации докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Международной научной конференции «Компьютерные науки и информационные технологии» (14-18 мая

2002 года, г. Саратов), Международной конференции «Проблемы и перспек6 тивы прецизионной механики и управления в машиностроении» (14-19 октября 2002 года, г. Саратов), Ежегодной межвузовской научной конференции «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г. Саратов), представлены и обсуждались на Шестом и Седьмом Всероссийских симпозиумах по прикладной и промышленной математике (1-7 октября 2005 года, г. Сочи-Дагомыс; 2-8 мая 2006 года, г. Кисловодск).

Основные результаты диссертации опубликованы в работах [32-37, 41]. Результаты диссертационной работы получены автором самостоятельно.

В работе [32] Е. С. Рогачко принадлежат метод анализа сетей массового обслуживания с управлением распределением нагрузки между системами (теорема 2.10,2.11) и результаты исследования методом численного моделирования эффективности метода управления. Ю. И. Митрофанову принадлежат принципы динамического управления распределением нагрузки между системами в сетях массового обслуживания.

В работе [33] Е. С. Рогачко принадлежит метод анализа сетей массового обслуживания с управлением распределением нагрузки между подсетями (теорема 3.3). Ю. И. Митрофанову принадлежат основные положения метода динамического управления распределением нагрузки между подсетями в сетях массового обслуживания.

В работе [34] Е. С. Рогачко принадлежат метод динамического управления распределением нагрузки между подсетями в сетях массового обслуживания и результаты исследования методами численного и имитационного моделирования сетей с управлением распределением нагрузки. Ю. И. Митрофанову принадлежат концепция динамического управления распределением нагрузки между подсетями в сети массового обслуживания и модель эволюции сети с управлением распределением нагрузки между подсетями.

В работе [35] Е. С. Рогачко принадлежат метод динамического управления распределением нагрузки между системами в сетях массового обслуживания (теоремы 2.8,2.9), приближенный метод анализа сетей с управлением (теоремы 2.12, 2.13) и результаты исследования методами численного и имитационного моделирования точности метода анализа сетей обслуживания с управлением. Ю. И. Митрофанову принадлежат постановка задачи управления распределением нагрузки в сетях массового обслуживания и модели эволюции сети с управлением распределением нагрузки между системами.

В работе [36] Е. С. Рогачко принадлежит метод формирования маршрутных матриц, используемых при управлении распределением нагрузки между подсетями в сетях массового обслуживания. Ю. И. Митрофанову принадлежат принципы управления распределением нагрузки между подсетями в сетях массового обслуживания.

В работе [37] Е. С. Рогачко принадлежит метод формирования маршрутных матриц, используемых при оптимизации потоков в сетях массового обслуживания. Ю. И. Митрофанову принадлежит постановка задачи оптимизации потоков в сетях массового обслуживания.

В работе [41] Е. С. Рогачко принадлежат постановка задачи исследования методов управления распределением нагрузки между системами в сетях массового обслуживания, имитационные модели сетей массового обслуживания с различными методами управления распределением нагрузки и результаты исследования методом имитационного моделирования эффективности различных методов управления распределением нагрузки. Н. П. Фокиной принадлежат алгоритмы методов маршрутизации, использованные при разработке программы имитационного моделирования.

Диссертация состоит из введения, четырех глав, заключения, списка литературы. Объем диссертации 102 страницы. Диссертация содержит 15 таблиц. Список литературы включает 94 наименования.

Заключение

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

1. Разработаны методы динамического управления распределением нагрузки между системами и между подсетями в сетях массового обслуживания и проведено исследование их эффективности.

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

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

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

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

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

1. Баканов A.C., Вишневский В.М., Ляхов А.И. Метод оценки показателей производительности беспроводных сетей с централизованным управлением // Автоматика и телемеханика, 2000, № 4, С. 97-105.

2. Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения / Пер. с англ. М.: Наука, ГРФМЛ, 1969. 512 с.

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

4. Беляков В.Г., Митрофанов Ю.И. К исследованию замкнутых сетей массового обслуживания большой размерности // Автоматика и телемеханика, 1981, №7, С. 61-69.

5. Боровков A.A. Асимптотические методы в теории массового обслуживания. М.: Наука, 1980. 384 с.

6. Боровков A.A. Предельные теоремы для сетей обслуживания // Теория вероятностей и ее применения, 1986, Т. 31, Вып. 3, С. 474-490; 1987, Т. 32, Вып. 2, С. 282-298.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. 512 с.

8. Вишневский В.М., Ляхов А.И., Терещенко Б.Н., Моделирование беспроводных сетей с децентрализованным управлением // Автоматика и телемеханика, 1999, № 6, С. 88-99.

9. Герасимов А.И. Оптимизация и балансировка вычислительных систем и сетей с учетом поступающей информации // Автоматика и вычислительная техника, 2006, № 1, С. 67-81.

10. Гурьянов А.И., Митрофанов Ю.И. Определение параметров замкнутых линейных сетей систем массового обслуживания // Системное моделирование. Новосибирск: Вычислительный центр СО АН СССР, 1970, Вып. 1, С. 39-49.

11. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ.: Радио и связь, 1988.192 с.

12. Ивницкий В.А. О стационарных вероятностях состояний замкнутой звездообразной экспоненциальной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Автоматика и вычислительная техника, 1994, № 6, С. 29-37.

13. Карлин С. Основы теории случайных процессов / Пер. с англ. М.: Мир, 1971.536 с.

14. Кемени Д.Д., Снелл Д.Л. Конечные цепи Маркова / Пер. с англ. М.: Наука, 1970. 272 с.

15. Кениг Д., Штойян Д. Методы теории массового обслуживания/ Пер. с нем. М.: Радио и связь, 1981.128 с.

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

17. Клейнрок Л. Теория массового обслуживания / Пер. с англ. М.: Машиностроение, 1979.432 с.

18. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения/Пер. с фр. М.: Мир, 1965.303 с.

19. Крыленко A.B., Малинковский Ю.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками П. Модели с несколькими типами заявок // Автоматика и телемеханика, 1998, № 2, С. 62-71.

20. Ляхов А.И. Асимптотический анализ замкнутых сетей очередей, включающих устройства с переменной интенсивностью обслуживания // Автоматика и телемеханика, 1997, № 3, С. 131-143.

21. Малинковский Ю.В., Якубович О.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками I. Модели с одним типом заявок // Автоматика и телемеханика, 1998, № 1, С. 92-106.

22. Митрофанов Ю.И. Анализ сетей массового обслуживания. Саратов: Научная книга, 2005.175 с.

23. Митрофанов Ю.И. Анализ сетей массового обслуживания с управлением интенсивностями обслуживания// Автоматика и вычислительная техника, 2005, № 6, С. 22-31.

24. Митрофанов Ю.И. Метод синтеза замкнутых сетей массового обслуживания с экспоненциальным распределением длительностей обслуживания // Автоматика и вычислительная техника, 2002, № 1, С. 77-84.

25. Митрофанов Ю.И. Метод управления маршрутизацией в замкнутых экспоненциальных сетях массового обслуживания // Известия РАН. Теория и системы управления, 2002, № 6, С. 86-92.

26. Митрофанов Ю.И. Основы теории сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1993.116 с.

27. Митрофанов Ю.И. Синтез сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1995.164 с.

28. Митрофанов Ю.И. Управление интенсивностями обслуживания в замкнутых экспоненциальных сетях массового обслуживания // Автоматика и вычислительная техника, 2005, № 3, С. 23-34.

29. Митрофанов Ю.И., Беляков В.Г., Курбангулов В.Х. Методы и программные средства аналитического моделирования сетевых систем. Препринт научного совета АН СССР по комплексной проблеме "Кибернетика", 1982. 68 с.

30. Митрофанов Ю.И., Долгов В.И. Сети массового обслуживания с управлением интенсивностями обслуживания: синтез, метод управления, исследование. Саратов, 2005. Деп. в ВИНИТИ 13.05.05, № 688-В2005.26 с.

31. Митрофанов Ю.И., Рогачко Е.С. Метод динамического управления распределением нагрузки между подсетями замкнутой сети массового обслуживания // Автоматика и вычислительная техника, 2006, № 4, С. 3-13.

32. Митрофанов Ю.И., Рогачко Е.С. Модели и анализ сетей массового обслуживания с динамическим управлением распределением нагрузки // Автоматика и вычислительная техника, 2006, № 5, С. 69-77.

33. Митрофанов Ю.И., Рогачко Е.С. Об управлении распределением нагрузки в замкнутых сетях массового обслуживания // Теоретические проблемы информатики и ее приложений: Сб. науч. тр. Саратов: изд-во Сарат. ун-та, 2003, Вып. 5, С. 107-111.

34. Митрофанов Ю.И., Рогачко Е.С. Оптимизация потоков в открытых сетях массового обслуживания // Проблемы и перспективы прецизионной механики и управления в машиностроении. Материалы Международной конференции. Саратов, 2002, С. 210-211.

35. Митрофанов Ю.И., Юдаева Н.В. Модели и анализ сетей массового обслуживания с управлением маршрутизацией // Автоматика и телемеханика, 2000, №6, С. 104-113.

36. Митрофанов Ю.И., Юдаева Н.В. Управление маршрутизацией в сетях массового обслуживания // Автоматика и телемеханика, 1999, № 11, С. 46-57.

37. Печинкин A.B., Рыков В.В. О декомпозиции замкнутых сетей с зависимым обслуживанием // Автоматика и телемеханика, 1999, № 11, С. 5868.

38. Рогачко Е.С., Фокина Н.П. Динамическое управление распределением нагрузки в замкнутых сетях массового обслуживания. Саратов, 2005. Деп. в ВИНИТИ 17.05.05, № 711-В2005.16 с.

39. Столяр A.A. Об оптимальном управлении нагрузкой сети массового обслуживания // Автоматика и телемеханика, 1989, № 5, С. 184-187.

40. Тананко И.Е. О стационарном распределении сетей массового обслуживания с управлением маршрутизацией // Математика. Механика: Сборник научных трудов. Саратов: изд-во Сарат. ун-та, 2001, Вып. 3, С. 214-217.

41. Толмачев АЛ. Сети обслуживания заявок с регенерирующими траекториями // Проблемы передачи информации, 1986, Т. 22, № 2, С. 59-68.

42. Уолрэнд Дж. Введение в теорию сетей массового обслуживания. М.: Мир, 1993. 335 с.

43. Феллер В. Введение в теорию вероятностей и ее приложения / Пер. с англ. М.: Мир, 1967. Т. 1.499 с.

44. Харари Ф. Теория графов. М.: Мир, 1973.336 с.

45. Чжун Кай-лай. Однородные цепи Маркова / Пер. с англ. М.: Мир, 1964.428 с.

46. Alanyali М., Hajek В. Analysis of simple algorithms for dynamic load balancing//Math. Oper. Res., 1997, Vol. 22, No. 4, P. 840-871.

47. Alidrisi M. Optimal control of the service rate of an exponential queue-ing network using Markov decision theory // Int. J. Syst. Sei., 1990, Vol. 21, P. 2553-2563.

48. Azaron A., Ghomi S.M. Optimal control of the service rates and arrivals in Jackson networks //Eur. J. Oper. Res., 2003, Vol. 147, No. 1, P. 17-31.

49. Baskett F., Chandy K.M., Müntz R.R., Palacios F.G. Open, closed and mixed networks of queues with different classes of customers // J. ACM., 1975, Vol. 22, No. 2, P. 248-280.

50. Boel R.K., Schuppen J.H. Distributed routing for load balancing // Discrete Event Dynamic Systems Analyzing Complexity and Performance in the Modern World, 1992, P. 237-248.

51. Bonald Т., Jonckheere M., Proutiere A. Insensitive load balancing // Sigmetrics / performance, New York, N. Y., 2004, P. 6367-6378.

52. Boucherie R.J. Norton's equivalent for queueing networks comprised of quasireversible components linked by state-dependent routing // Performance Evaluation, 1998, Vol. 32, No. 2, P. 83-99.

53. Bovopoulos A.D., Lazar A.A. Optimal load balancing for markovian queueing networks // 30th Midwest Symp. Circ. and Syst., Syracuse, N.Y., Aug. 17-18, 1987: Proc.- New York, 1988, P. 1428-1432.

54. Bruell S.C., Balbo G., Afshari P.V. Mean value analysis of mixed, multiple class BCMP networks with load dependent service stations // Performance Evaluation, 1984, Vol. 4, P. 241-260.

55. Buzen J.P. Computational algorithms of closed queueing networks with exponential servers // Commun. of ACM, 1973, Vol. 16, No. 9, P. 527-531.

56. Cao J., Nyberg C. An approximate analysis of load balancing using stale state information for servers in parallel // Proc. 2nd IASTED Int. Conf. on Communications Internet and Information Technology, November 2003.

57. Chandy K.M., Herzog U., Woo L. Approximate analysis of general queueing networks // IBM J. Res. Dev., 1975, Vol. 19, No. 1, P. 43-49.

58. Chandy K.M., Herzog U., Woo L. Parametric analysis of queueing networks // IBM J. Res. Dev., 1975, Vol. 19, No. 1, P. 38-42.

59. Chandy K.M., Howard J.H.Jr., Towsley D.F. Product form and local balance in queueing networks // J. ACM., 1977, Vol. 24, No. 2, P. 250-263.

60. Courtois P.J. Error analysis in nearly-completely decomposable stochastic systems // Econometrica, 1975, Vol. 43, No. 4, P. 691-709.

61. Daskalaki S., Smith J.M. Real-time routing in finite queueing networks // Queueing Network Blocking: Proc. 1st Int. Workshop, Raleigh, N.C., 1988, P. 313-324.

62. Down D.G., Lewis M.E. Dynamic load balancing in parallel queueing systems: stability and optimal control // Eur. J. Oper. Res., 2006, Vol. 168, No. 2, P. 509-519.

63. Gibbens R., Kelly F.P., Turner S. Dynamic routing in multiparented networks // IEEE/ACM Transactions on Networking, 1993, Vol. 1, P. 261-270.

64. Gordon W.J., Nowell G.F. Closed queueing systems with exponential servers // Oper. Res., 1967, Vol. 15, No. 2, P. 254-265.

65. Hjalmtysson G., Whitt W. Periodic load balancing // Queueing Systems, 1998, Vol. 30, P. 203-250.

66. Jakson J.R. Networks of waiting lines // Oper. Res., 1957, Vol. 5, No. 4, P. 131-142.

67. Kameda H., Zhang Y. Uniqueness of the solution for optimal static routing in open BCMP queueing networks // Math. Comput. Modelling, 1995, Vol. 22, No. 10-12, P. 119-130.

68. Kato M., Oie Y., Miyahara H. Performance analysis of reactive congestion control based upon queue length threshold values // Performance Evaluation, 1997, Vol. 29, P. 105-125.

69. Kelly F.P. Dynamic routing in stochastic networks / In Stochastic Networks (ed. F.P. Kelly and R.J. Williams) The IMA Volumes in Mathematics and its Applications, 71, Springer-Verlag, New York, 1995, P. 169-186.

70. Kelly F.P. Network Routing // Philosophical Transactions of the Royal Society, 1991, A 337, P. 343-367.

71. Kelly F.P., Laws C.N. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling // Queueing Systems, 1993, No. 13, P. 47-86.

72. Kerbache L., Smith J.M. Multiple-objective routing within large scale facilities using open finite queueing networks // European Journal of Operational Research, 2000, No. 121, P. 105-123.

73. Korilis Y.A., Lazar A.A., Orda A. Achieving network optima using stackelberg routing strategies // IEEE Transactions on Networking, February, 1997, Vol. 5, No. 1,P. 161-173.

74. Krzesinski A.E. Multiclass queueing networks with state-dependent routing // Performance Evaluations, 1987, Vol. 7, No. 2, P. 125-143.

75. Li J., Kameda H. Load balancing problems for multiclass jobs in distributed/ parallel computer systems // IEEE Trans, on Comput., 1998, Vol.47, No. 3, P. 322-332.

76. Mandelbaum A., Massey W.A. Reiman M.I. Strong approximations for Markovian service networks // Queueing Systems, 1998, Vol. 30, P. 149-201.

77. Menich R., Serfozo R.F. Optimality of routing and servicing independent parallel processing systems // Queueing Systems, 1991, Vol. 9, P. 403-418.

78. Mitra D., McKenna J. Asymptotic expansions for closed markovian networks with state-dependent service rates // J. ACM, 1986, Vol. 33, No. 3, P. 568-592.

79. Reiser M., Lavenberg S.S. Mean-value analysis of closed multichain queueing networks // Journal of ACM, 1980, Vol. 27, No. 2, P. 313-322.

80. Ridder A. A linear programming problem in separable closed queueing network // IEEE Transaction on Automatic Control, Febr. 1989, Vol. 34, No. 2, P. 214-217.

81. Ross K.W. Optimal dynamic routing in Markov queueing networks // Automatica, 1986, Vol. 22, No. 3, P. 367-370.

82. Serfozo R.F. Markovian network processes: congestion-dependent routing and processing // Queueing Systems, 1989, No. 5, P. 5-36.

83. Simon H.A., Ando A. Aggregation of variables in dynamic systems // Econometrica, 1961, Vol. 29, No. 2, P. 111-138.

84. Stidham S.Jr., Weber R. A survey of Markov decision models for control of networks of queues // Queueing Systems, 1993, Vol. 13, No. 1-3, P. 291314.

85. Stoyan D. Queueing networks insensitivity and a heuristic approximation// Electron. Informat. und Kybern., 1978, Vol. 14, No. 3, P. 135143.

86. Tantawi A.N., Towsley D. Optimal static load balancing in distributed computer systems // J. Assoc. Comput. Mach., 1985, Vol. 32, P. 445-465.

87. Tassiulas L. Adaptive back-pressure congestion control based on local information // IEEE Trans, on Automat. Contr., 1995, Vol. 40, No. 2, P. 236-250.

88. Tassiulas L., Ephremides A. Throughput properties of a queueing network with distributed dynamic routing and flow control // Adv. Appl. Prob., 1996, Vol. 28, No. 1, P. 285-307.

89. Towsley D. Queuing network models with state-dependent routing // J. of ACM, 1980, Vol. 27, No. 2, P. 323-337.

90. Veatch M.H., Wein L.M. Monotone control of queueing networks // Queueing Systems, 1992, Vol. 12, P. 391-408.

91. Weber R., Stidham S. Optimal control of service rates in networks of queues // Adv. Appl. Prob., 1987, Vol. 19, P. 202-218.