Управление маршрутизацией в сетях массового обслуживания

Фокина, Надежда Петровна

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

Фокина, Надежда Петровна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Саратов МЕСТО ЗАЩИТЫ

2007 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Управление маршрутизацией в сетях массового обслуживания»

Автореферат диссертации на тему "Управление маршрутизацией в сетях массового обслуживания"

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

Фокина Надежда Петровна

УПРАВЛЕНИЕ МАРШРУТИЗАЦИЕЙ В СЕТЯХ МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

Ф&сим»/

003161712

Саратов - 2007

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

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

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

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

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

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

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

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

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

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

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

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

Защита состоится 12 ноября 2007 г в 16 час 30 мин на заседании диссертационного совета К 212.243.02 в Саратовском государственном университете им Н. Г. Чернышевского по адресу: 410012, г. Саратов, ул Астраханская, 83, Саратовский государственный университет, механико-математический факультет.

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

Автореферат разослан /' октября 2007 г

Ученый секретарь диссертационного совета к.ф.-м н., доцент

В В Корнев

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

Актуальность темы. Проектирование и развитие больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС), широко используемых на современном этапе развития общества, как правило, требуют решения соответствующих задач анализа, синтеза и оптимизации систем этого класса (примерами БСС могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы). Наличие развитых подсистем управления в системах этого класса, имеющих сложные алгоритмы управления, существенно повышает уровень требований к используемым при решении этих задач математическим моделям и методам Практический опыт решения таких задач показал перспективность и эффективность использования сетей массового обслуживания (СеМО) в качестве математических моделей БСС. Это обусловило интенсивное развитие в течение последних четырех десятилетий теории сетей массового обслуживания и методов их анализа и синтеза. Большой вклад в развитие теории, методов анализа, синтеза и оптимизации сетей массового обслуживания внесли А. А Боровков, Г П. Башарин, В. М Вишневский, П П. Бочаров, В. А. Ивницкий, В. В. Рыков. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых, как Дж. Джексон (J. Jackson), Л. Клейнрок (L. Kleinrock), Ф. Келли (F. Kelly), К. Чэнди (К Chandy), Д. Тауслей (D. Towsley), Дж. Уолрэнд (J.Walrand)

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

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

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

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

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

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

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

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

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

Основные результаты и научная новизна.

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

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

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

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

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

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

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

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

Апробация работы. Результаты докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Международной научной конференции «Компьютерные науки и информационные технологии», посвященной памяти проф. АМ. Богомолова (14-18 мая 2002 года, 2-4 июля 2007 года, г Саратов), Международной конференции «Проблемы и перспективы прецизионной механики и управления в машиностроении» (14-19 октября 2002 года, г. Саратов), межвузовской научной конференции «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г Саратов), представлены и обсуждались на Седьмом Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия, 2-8 мая 2006 года, г. Кисловодск; зимняя сессия, 16-22 декабря 2006 года, г Йошкар-Ола).

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

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

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

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

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

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

Пусть № - замкнутая экспоненциальная сеть массового обслуживания с X системами массового обслуживания S,, f = 1,...,L, типа MIMI1 синтенсив-ностями обслуживания р,, Q требованиями одного класса, неприводимой маршрутной матрицей 0 = (8у), i,j = l,...,L. Топология сети определяется матрицей смежности W = (wy) ориентированного графа Q. Вершины орграфа Q соответствуют системам обслуживания, а дуги - возможным переходам требований между системами Состояние с номером п сети определяется вектором = (s,w), где s,M - число требований, находящихся в S,. Множество X состояний сети имеет мощность сх = Щ; множество номеров состояний сети В = { 1, ,сх).

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

Качество функционирования сети определяется значением ее некоторой стационарной характеристики, называемой ведущей. Например, в качестве ведущей характеристики может быть выбрана пропускная способность А или коэффициент использования ресурсов Целью управления в сети N может являться также выравнивание нагрузки между системами, определяемое, например, требуемыми значениями математического ожидания (м.о.) числа требований 5 = (хг) или м.о. длительности пребывания требований и = (к,) в системах сети

Для каждого состояния е X задана характеристика - потенциал состояния (неотрицательное вещественное число), который определяет значимость пребывания сети в данном состоянии для достижения сетью наилучшего значения ведущей характеристики. Нумерация состояний производится по убыванию значений их потенциалов. Состояние с максимальным потенциалом называется базовым. Множество X делится на подмножества Г и Ъ доминантных и ординарных состояний, су =(у| и с2 - Щ. В множество У включаются состояния, пребывание в которых обеспечивает значение ведущей характеристики сети более близкое к оптимальному значению, чем пребывание в ординарных состояниях, К = Поэтому повышение качества функционирования сети непосредственно связано с увеличением стационарной вероятности л(У) пребывания сети в множестве доминантных состояний У.

В сети N реализуется интервальный принцип управления маршрутизацией, заключающийся в следующем. Различаются два режима функционирования сета N - нормальный и коррективный. Периоды функционирования сети в этих режимах называются соответственно нормальными и коррективными тактами, обозначаемыми х и х. В нормальном такте используется матрица 0, и он имеет постоянную длительность <р. В коррективном такте используется управляющая маршрутная матрица в-7'11 = (9^*), /,/ = 1,. зависящая от начального состояния такта и параметра управления к е{1,2,...,¿}. Параметр к задается системой управления до начала функционирования сети и определяет число переходов между состояниями сети, в течение которых должна быть использована данная матрица. Поэтому длительность коррективного такта определяется как мо. длительности интервала времени, за который сеть из соответствующего такту начального состояния при заданной маршрутной матрице совершит к пе-

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

Рассмотрим процесс эволюции сети N с первым методом управления. В момент окончания каждого такта производится идентификация состояния сети; если s(g) е Y, то следующий такт является нормальным, в противном случае - коррективным. В зависимости от состояния s^ е Z различаются сг типов коррекгавных тактов. В течение такта х используется маршрутная матрица ©, в течение коррективного такта xJ типа J = g~cY, Jе {1,- .,cz}> - управляющая маршрутная матрица @J,K. Параметры с¥, Ф и к являются параметрами метода управления маршрутизацией, их значения задаются до начала функционирования сети и не изменяются в процессе ее функционирования.

Пусть Yb с Y - подмножество, включающее базовое состояние s(1), 4=|Fé|. Множество Y6 называется базой, Zh =X\Yb, chz = \zb\. Процесс

эволюции сети N со вторым методом управлением аналогичен рассмотренному ранее. Одним из отличий данного метода управления является условие смены тактов: если s^ е Y*, то очередной такт является нормальным, иначе — коррективным. Поэтому различаются с| типов коррективных тактов. Целью коррективных тактов является возвращение сети в базу Yb. Для каждого состояния s(s) е zb при построении матрицы ©J'K формируется значение Kg < к, соответствующее предполагаемому числу шагов использования матрицы ©l/,K. Параметрами второго метода управления второго типа являются параметры су,

сь, <р и к.

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

Оптимальной маршрутной матрицей © сети № будем называть такую матрицу, которая обеспечивает выполнение условий:

= PgHi. 1 = ,

или

где рд и \q - константы, индекс Q означает пребывание в сети Q требований.

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

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

Теорема 2.3. Для сети № регулярного типа относительная интенсивность потока требований в систему S,

где

i=i

Теорема 2.4. Для сети № равномерного типа относительная интенсивность потока требований в систему S,

Теорема 2.S. Для сети массового обслуживания регулярного или равномерного типа с заданным вектором © = (©,), i = 1,. ,L; заданной топологией, определенной матрицей смежностей W орграфа Q, заданным множеством констант S~{bt]}, 0<Ьу < 1, j, i,j е{1,. .,L), заданным множеством коэффициентов обмена Я = {гц}, 0<гу<оо, j, i,je{l,..,L}, маршрутная матрица 0 = (ßv), б„ = 0, =1,...,L, существует, если совместна система уравнений

iev=l, i = l,..,L, i

®,0ff =0, i,j e{l,.. ,1},

с условиями

Значения неизвестных маршрутных вероятностей для такой сети определяются решением этой системы уравнений

Пусть Q["\ i е {!,. ,L}, - множество состояний, смежных с состоянием s{n), в которые возможен переход сети при завершении обслуживания требования в системе S,. Состояние eQj"K имеющее наибольший потенциал У(> по сравнению с другими состояниями множества i2,(n), называется остовным состоянием множества üja). Для каждого состояния s(n) определим нуль-

единичную матрицу Ы(я) =(у ),/,./= 1, называемую матрицей передач, обеспечивающую переход сети из состояния в одно из смежных остовных состояний. Для каждого состояния $(п) на основании матрицы передач и. вероятностей у, „, г е {!,...,£}, событий, содержанием которых является то, что

уход сети из состояния обусловлен завершением обслуживания требования в системе Э,, построим матрицу Я(и) = (йуИ)), /,/ = 1,...,£, элементы которой положим равными

Матрица Н^"1 является матрицей вероятностей перехода из в остовные состояния множеств I е {!,...,.£}, с учетом вероятностей завершения обслуживания в соответствующих системах обслуживания.

Пусть "Н - ориентированный граф с множеством вершин В и множеством дуг, соответствующих упорядоченным парам смежных состояний сети. Обозначим через } множество всех путей в графе *Н из в проходящих по остовным состояниям Введем три характеристики пути (X -индекс пути): длину, потенциал и продолжительность, которые обозначим соответственно через и и определим выражениями

М ап к=1аик(Х)

где тх - число промежуточных остовных состояний, ик(А.), к = 1, но-

мера промежуточных остовных состояний, входящих в путь с индексом X, а ат - интенсивность выхода из состояния .

Каналом состояния ¿(я) называется путь К^ с минимальной длиной,

максимальным потенциалом н минимальной продолжительностью.

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

МЕТОД 1. При построении управляющей маршрутной матрицы вЛк, используемой в течение коррективного такта, начинающегося из состояния п = У + су, последовательно просматриваются остовные состояния, расположенные на расстоянии 1,2,. ., к -1 шагов от исходного состояния Считается, что равноудаленные от состояния находятся на одном уровне (состояние находится на уровне 0). Алгоритм формирования маршрутной матрицы основывается на алгоритме поиска кратчайших путей между вершинами в графе Л Для каждой просмотренной вершины г графа К, соответствующей ос-товному состоянию формируется матрица Н^. Управляющая мар-

шрутная матрица &J* строится на основе суммы матриц для вершин re В, расположенных на уровнях 0, 1, , к-1 от начальной вершины яе#, п = cY + J Допускается, что одна и та же вершина может быть просмотрена более одного'раза Выполнение алгоритма завершается после просмотра к-1 уровней.

При использовании в сети N второго метода управления предлагается следующий метод формирования управляющих маршрутных матриц

МЕТОД 2 При формировании управляющей маршрутной матрицы QJ,K, используемой в течение коррективного такта, начинающегося из состояния 5(«>€2ь, n = cy+j, строится канал Маршрутная матрица ®J'K,

J = и - Су, формируется на основе суммы-

N(»>+gNC,-,№»/,,

i=Z

где к„ - min{к, А^ }. Заметим, что данная маршрутная матрица определена на кп <к переходов.

Множество состояний Zb можно разделить на к непересекающихся подмножеств Zy , % = 1,2,.. ,к. Состояние тогда и только тогда, когда

длина канала Дрп) =%. Для состояний s Z* при ке{1,...,х} используются

различные управляющие маршрутные матрицы &J,K в течение тактов соответствующих длительностей r\J„\а при ке{% + 1,.. ,ic} - матрица QJ'1 в течение такта длительности r\J„'x.

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

Введем следующие обозначения* ру, pz - параметры, зависящие от метода управления, р у =су, pz =cz - для сети N с первым методом управления и ру = су, pz=c| - для сети N со вторым методом управления, D = {1,2,. ,pj,}, U = {ру+1,ру+2, ..,py+pz}.

Обозначим через S случайный процесс с множеством состояний В = {1,2,.,.,сх}, описывающий эволюцию сети N. Процесс Е представляет собой последовательность фрагментов, соответствующих нормальным и коррективным тактам. Эволюция сети N в течение нормальных и коррективных тактов описывается соответственно модельными цепями Маркова С и

Су, </ = 1,. -,р2, с множеством состояний В и непрерывным временем. Длительности реализаций цепей Си Сравны длительностям соответственно нормального такта ср и коррективного такта

Теорема 3.1. Математическое ожидание длительности интервала времени, за который цепь С3 совершит к переходов, определяется выражением.

«в 1=1 /=1 а!

где Рп! (0 — вероятность перехода из т в I за г шагов марковской цепи скачков, связанной с цепью С"7

Длительность коррективного такта полагается равной Во втором методе управления вместо значения к используется кт = 1Шп{к,А(™'}

Обозначим через 5„ такт сети Лг, начинающийся в состоянии е!,и рассмотрим случайный процесс А с множеством состояний {8И}, п,сх Положим длительности пребывания процесса А в состояниях 8],...,8ру равны-

ми

Ф, а в состояниях 5Рг+-/, .7 = 1,. ,р2, - равными т}п'к, п - рг + 3. Вероятность перехода процесса А из состояния 5„ в состояние бт

пе5,теВ,

Чпт ~ 1 «и ~ _

№ и,пе1/,теВ Введем в рассмотрение матрицы Р = (р„т), п,т = \, ,.,сх, и А = (а„т), элементы которых определим следующим образом.

а. =

Рвт [ 0. и = т,

пт | -а„, п-т,

где

|1/ф, п е {1,. ,рг},

пе{ру+1,...,сх}.

Теорема 3.2. Стационарное распределение С = (Сп)> л = 1... ,сх, процесса А существует, является единственным и приближенно равно стационарному распределению £ = <£„), и е В, являющемуся решением уравнения

С4 = о

с условием

яеВ

Степень приближения распределения С, распределением С, определяется

значением тах дт. пев

Замечание 3.1. Степень приближения распределения С, распределением С, определяется значением максимальной погрешности таxq„t¡, допускаемой

пеВ

при определении матрицы вероятностей скачков Р - (р„т) цепи С, в отличие от аналогичной матрицы процесса Д. Следовательно, чем меньше эта погрешность, тем более точным является определение ^ через £.

Обозначим через (т,ф) и 7с°(/и,г|^,к) средние вероятности пребывания в состоянии п е В соответственно цепи С в течение интервала времени длительности ф при исходе из состояния тебя цепи С"1 в течение интервала времени длительности при исходе из состояния те1/ Так как вероятности пребывания этих цепей в момент времени г в состоянии п при исходном состоянии теВ равны вероятностям их перехода из яг в и за время то

= пеВ, теВ,

Фо

Пда О

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

теб теО

Замечание 3.2. Точность определения стационарных вероятностей ж„, пеВ, состояний сети N через вероятности %„, зависит от длительностей тактов. чем они больше, тем меньше шах дпп, и тем выше точность.

пеВ

Следствие 3.1. Стационарная вероятность С,]д нормального такта в

процессе функционирования сети N при любом значении параметра управления к стремится к 1 при ф —> со

Следующее утверждение устанавливает адекватность выбранной модели поведению сети N при ф оо.

Следствие 3.2. При ф со стационарное распределение вероятностей состояний сети N стремится к стационарному распределению вероятностей состояний сети №

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

Теорема 3.4. Математическое ожидание длительности очередного такта у* и интенсивность управления Кк определяются выражениями

иеб пгО

Теорема 3.5. Если при к, и к2 таких, что К] <к2, выполнены условия'

Ф^+^-^и-фДСб'-сЬ1)'

то имеют место соотношения

Ч/к' >, Лк' < Л*2. Управление маршрутизацией в сети N, очевидно, имеет смысл только в том случае, если значение ведущей характеристики сети я(7) превосходит значение аналогичной характеристики тс0 (7) сети №. Более того, доход, обусловленный наличием управления в сети N, должен превышать затраты на его реализацию.

Пусть - доход, получаемый при пребывании сети N в состоянии $(п) в единицу времени, и

¿ОН тсуЬ\

где с - некоторая положительная константа.

Введем обозначения. Рс - м.о. дохода сети в единицу времени, Е,- м о. затрат на реализацию управления в единицу времени, сЛ - стоимость одного управляющего воздействия, ^ - чистые средние доходы в единицу времени, сетей N и № соответственно. Тогда

пеВ

где Л - интенсивность управления,

пеВ

где я® - стационарная вероятность пребывания сети № в состоянии

Показатель эффективности управления определим выражением.

Значение /9 определяет прирост дохода сети N по сравнению с доходом сети №. Будем называть управление эффективным, если /д >0.

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

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

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

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

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

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

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

1 Фокина, Н.П. Анализ сетей массового обслуживания с динамическим управлением маршрутизацией / Ю.И Митрофанов, Н.П. Фокина // Известия Са-рат. ун-та. Сер. Математика. Механика. Информатика. - 2007. - Т 7, Вып. 1. -С. 27-33.

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

2. Фокина, НП. Параметрический метод управления маршрутизацией в сетях массового обслуживания / Ю И. Митрофанов, Н.П Фокина // Обозрение прикладной и промышленной математики, тез. докл VII Всерос. симпоз. по прикл. и пром. матем, Йошкар-Ола, 16-22 дек. 2006 г. - М.- Науч. изд-во «ОПиПМ», 2007 - Т. 14, Выл. 2. - С. 327-328.

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

3 Фокина, Н.П. Управление маршрутизацией в сетях массового обслуживания / Н.П. Фокина // Обозрение прикладной и промышленной математики/ Тез. докл. VII Всерос симпоз по прикл. и пром. матем,

Тез докл. VII Всерос. симпоз. по прикп. и пром. матем., Кисловодск, 2-8 мая 2006 г. - М : Науч изд-во «ОПиПМ», 2006. - Т. 13, Вып. 4 - С. 734.

4. Решетникова (Фокина), Н.П. Методы анализа сетей массового обслуживания с управлением маршрутизацией / Ю И. Митрофанов, Н.П. Решетникова; Сарат. гос. ун-т. - Саратов, 2002. - 55 с. - Деп. в ВИНИТИ 31.05.02, № 973-В2002.

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

5. Решетникова (Фокина), Н.П О динамическом управлении маршрутизацией в замкнутых сетях массового обслуживания / Ю.И. Митрофанов, Н.П. Решетникова // Теоретические проблемы информатики и ее приложений* сб. науч тр - Саратов: Изд-во Сарат. ун-та, 2003. - Вып. 5. - С. 103-106.

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

6. Решетникова (Фокина), Н.П. Организация управления маршрутизацией в сетях массового обслуживания / Ю.И. Митрофанов, Н.П. Решетникова // Проблемы и перспективы прецизионной механики и управления в машиностроении* матер, междунар. конф. Саратов, 14-19 окт. 2002 г. / Институт проблем точной механики и управления РАН. - Саратов, 2002. - С. 207-209.

Н. П Фокиной принадлежит метод формирования маршрутных матриц

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

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

8. Фокина, Н.П. Моделирование сетей массового обслуживания с управлением маршрутизацией / Н.П. Фокина // Теоретические проблемы информатики и ее приложений: сб. науч. тр. - Саратов* Изд-во Сарат. ун-та, 2006. - Вып. 7. -С. 153-159.

9 Фокина, Ц.П. Исследование сетей массового обслуживания с управлением маршрутизации / Н.П. Фокина, Е С. Рогачко // Компьютерные науки и информационные технологии: тез. докл междунар. науч конф, посвящ. памяти проф. А. М. Богомолова, 2-4 июля 2007 г., Саратов. - Саратов: Изд-во Сарат. ун-та, 2007.-С. 134-136

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

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

Подписано в печать 03.10 2007 Формат 60x84 1/16. Бумага офсетная. Гарнитура Times. Печать RISO. Объем 1,0 печ. л Тираж 100 экз. Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю Б. Свидетельство № 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. Метод анализа открытых сетей с управлением входящим потоком требований

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

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

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

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

Проектирование и развитие больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС), широко используемых на современном этапе развития общества, как правило, требуют решения соответствующих задач анализа, синтеза и оптимизации систем этого класса (примерами БСС могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы). Наличие развитых подсистем управления в системах этого класса, имеющих сложные алгоритмы управления, существенно повышает уровень требований к используемым при решении этих задач математическим моделям и методам. Практический опыт решения таких задач показал перспективность и эффективность использования сетей массового обслуживания (СеМО) в качестве математических моделей БСС. Это обусловило интенсивное развитие в течение последних четырех десятилетий теории сетей массового обслуживания и методов их анализа и синтеза [3-5, 7-10, 12, 13, 19, 20, 22, 32, 46, 50, 55, 60, 74-76, 89, 92, 93]. Большой вклад в развитие теории, методов анализа, оптимизации и синтеза сетей массового обслуживания внесли А. А. Боровков, Г. П. Башарин, В. М. Вишневский, П. П. Бочаров, В. А. Ивницкий, В. В. Рыков. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых, как Дж. Джексон (J. Jackson), JI. Клейнрок (L. Kleinrock), Ф. Келли (F. Kelly), К. Чэнди (К. Chandy), Д. Тауслей (D. Towsley), Дж. Уолрэнд (J. Walrand).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Международной научной конференции «Компьютерные науки и информационные технологии», посвященной памяти проф. A.M. Богомолова (14-18 мая 2002 года, 2-4 июля 2007 года, г. Саратов), Международной конференции «Проблемы и перспективы прецизионной механики и управления в машиностроении» (14-19 октября 2002 года, г. Саратов), Ежегодной межвузовской научной конференции «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г. Саратов), представлены и обсуждались на Седьмом Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия, 2-8 мая 2006 года, г. Кисловодск; зимняя сессия, 16-22 декабря 2006 года, г. Йошкар-Ола).

Основные результаты диссертации опубликованы в работах [33-35, 38, 39, 45, 52-54]. Результаты диссертационной работы получены автором самостоятельно.

В работе [33] Н. П. Фокиной (Решетниковой) принадлежит обзор результатов по методам анализа сетей массового обслуживания с распределенной маршрутизацией. Ю. И. Митрофанову принадлежат обзор результатов по методам анализа сетей с маршрутизацией, зависящей от состояния и методам оптимальной маршрутизации в сетях обслуживания.

В работе [34] Н. П. Фокиной (Решетниковой) принадлежит метод формирования маршрутных матриц, используемых при управлении маршрутизацией в сетях массового обслуживания. Ю. И. Митрофанову принадлежит постановка задачи управления маршрутизацией в сетях массового обслуживания.

В работе [35] Н. П. Фокиной (Решетниковой) принадлежит постановка задачи управления маршрутизацией в замкнутых сетях массового обслуживания. Ю. И. Митрофанову принадлежат принципы организации управления маршрутизацией в замкнутых сетях массового обслуживания.

В работе [38] Н. П. Фокиной принадлежат алгоритм метода формирования маршрутных матриц, используемых при динамическом управлении маршрутизацией в сетях массового обслуживания, приближенный метод анализа сетей с управлением (теоремы 3.2, 3.3, 3.4) и результаты исследования методами численного моделирования сетей с предложенным методом управления маршрутизацией. Ю. И. Митрофанову принадлежат основные положения метода управления маршрутизацией в сетях массового обслуживания.

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

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

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

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

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

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Фокина, Надежда Петровна, Саратов

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

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

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

4. Башарин Г.П., Толмачев А.Л. Некоторые результаты теории сетей массового обслуживания // Методы развития теории телетрафика. М.: Наука, 1979. С. 52-65.

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

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

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

8. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей МО конечной емкостью с потерями или блокировками // Автоматика и телемеханика. 1987. № 1. С. 55-65.

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

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

11. Гнеденко Б.И., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966.432 с.

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

13. Евдокимович В.Е., Малинковский Ю.В. Сети массового обслуживания с динамической маршрутизацией и динамическими вероятностными обходами узлов заявками // Проблемы передачи информации. 2001. Т. 37. № 3. С. 55-66.

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

15. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Теория вероятностей и ее применения. 1997. Т. 42. № 1. С. 179-184.

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

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

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

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

20. Климов Г.П. Теория вероятностей и математическая статистика. М.: Изд-во МГУ, 1983.328 с.

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

22. Крыленко А.В. Сети массового обслуживания с несколькими типами заявок, немедленным обслуживанием и обходами узлов заявками // Проблемы передачи информации. 1997. Т. 33. № 3. С. 91-101.

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

24. Кузнецов Д.Ю., Назаров А.А. Исследование сетей связи с конечным числом абонентских станций, управляемых адаптивными протоколами случайного множественного доступа в условиях перегрузки // Автоматика и телемеханика. 1999. № 12. С. 99-113.

25. Липский В. Комбинаторика для программистов. М.: Мир, 1988.112 с.

26. Малинковский Ю.В. Инвариантность стационарного распределения состояний модифицированных сетей Джексона и Гордона-Ньюэлла // Автоматика и телемеханика. 1998. № 9 С. 29-36.

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

28. Митрофанов Ю.И. Анализ сетей массового обслуживания. Саратов: Изд-во «Научная книга», 2005. 175 с.

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

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

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

32. Митрофанов Ю.И., Решетникова Н.П. Методы анализа сетей массового обслуживания с управлением маршрутизацией. Саратов, 2002. Деп. в ВИНИТИ 31.05.02, № 973-В2002. 55 с.

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

34. Митрофанов Ю.И., Решетникова Н.П. Организация управления маршрутизацией в сетях массового обслуживания // Проблемы и перспективы прецизионной механики и управления в машиностроении:

35. Материалы международной конференции Саратов: Институт проблем точной механики и управления РАН. 2002. С. 207-209.

36. Митрофанов Ю.И., Тананко И.Е. Оптимизация сетей массового обслуживания. Саратов, 1997. Деп. в ВИНИТИ 17Ш.98, № 462-В98. 21с.

37. Митрофанов Ю.И., Тананко И.Е. Синтез оптимального управления потоками в сетях массового обслуживания. Саратов, 1999. Деп. в ВИНИТИ 04.06.99, № 1782-В99. 15с.

38. Митрофанов Ю.И., Фокина Н.П. Анализ сетей массового обслуживания с динамическим управлением маршрутизацией // Известия Сарат. ун-та. Серия Математика. Механика. Информатика. 2007. Т. 7. Вып. 1.С. 27-33.

39. Митрофанов Ю.И., Юдаева Н.В. Методы определения оптимальных параметров управления маршрутизацией в сетях массового обслуживания // Автоматика и телемеханика. 2001. № 8. С. 109-117.

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

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

42. Печинкин А.В. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритетом и раздельными очередями // Автоматика и телемеханика. 1998. № 1. С. 107115.

43. Пономаренко JT.A., Меликов А.З. Оптимизация марковских неполнодоступных сетей со сложными механизмами обслуживания // Автоматика и вычислительная техника. 1989. № 3. С.33-37.

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

45. Солодянников Ю.В. О статистике систем и сетей массового обслуживания // Проблемы устойчивости стохастических моделей: Труды X Всесоюзного семинара. Куйбышевский гос. ун-т. 1987. С. 101-116.

46. Сухов Ю.М., Введенская Н.Д. Быстрые сети Джексона с динамической маршрутизацией // Проблемы передачи информации. 2002. Т. 38. №2. С. 44-63.

47. Тананко И.Е. Метод оптимизации маршрутных матриц открытых сетей массового обслуживания // Автоматика и вычислительная техника. 2002. № 4. С. 39-46.

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

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

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

51. Фокина Н. П. Моделирование сетей массового обслуживания с управлением маршрутизацией // Теоретические проблемы информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2006. Вып. 7. С. 153-159.

52. Цициашвили Г.Ш., Осипова М.А. Новые мультипликативные теоремы для сетей массового обслуживания // Проблемы передачи информации. 2005. Т. 41. № 2. С. 111-122.

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

54. Юдаева Н.В. Сети массового обслуживания с динамической локальной маршрутизацией и задержкой информации // Автоматика и вычислительная техника. 2006. № 1. С. 57-66.

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

56. Altman E., Gaujal В., Hordijk A. Balanced sequences and optimal routing // INRIA Report No. RR-3180, Sophia-Antipolis, France, June, 1997.

57. Baskett F., Chandy K.M., Muntz R.R., Palacios F.G. Open, closed, and mixed networks of queues with different classes of customers // J. Assoc. Comput. Mach. 1975. Vol. 22. P. 248-260.

58. Bertsimas D., Chryssikou T. Bounds and policies for dynamic routing in loss networks // Oper. Res. 1999. Vol. 47. No. 3. P. 379-394.

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

60. 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.

61. Boucherie R.J., Dijk N.M. A generalization of Norton's theorem for queueing networks // Queueing Systems. 1993. No. 13. P. 251-289.

62. Boucherie R.J., Dijk N.M. Product forms for queueing networks with state-dependent multiple job transitions // Adv. Appl. Prob. 1991 No. 23. P. 152187.

63. Calvert В., Solomon W., Ziedins I. Braess's paradox in a queueing network with state-dependent routing // J. Appl. Prob. 1997. No. 34. P. 134-154.

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

65. 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.

66. 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.

67. Gafni E.M., Bertsekas D.P. Asymptotic optimally of shortest path routing algorithms // IEEE Transactions on Information Theory, 1987, IT-33. No. l.P. 83-90.

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

69. Hajek B. The proof of a folk the theorem on queueing delay with applications to routing in networks // J. ACM. 1983. No. 30. P. 834-851.

70. Hajek В., Ogier R.G. Optimal dynamic in communication networks with continuous traffic//Networks. 1984. No. 14. P. 457-487.

71. 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.

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

73. Kelly F.P. Routing in circuit-switched networks: optimization, shadow and decentralization // Adv. Appl. Prob. 1988. No. 20. P. 112-144.

74. 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.

75. 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.

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

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

78. Kushner H.J., Ramachandran K.M. Optimal and approximately optimal control policies for queues in heavy traffic // SIAM J. Control and Optimization. 1989. Vol. 27. No. 6. P. 1293-1318.

79. Martins L.F., Kushner H.J. Routing and singular control for queueing networks in heavy traffic // SIAM J. Control and Optimization. 1990. Vol. 28. No. 5. P. 1209-1233.

80. Meyn S.P. Feedback regulation for sequencing and routing in multiclass queueing networks // 2000 IEEE International Symposium on Information Theoiy, Sorrento, Italy, June 25- June 30,2000.

81. Mitra D., Seery J.B. Comparative evaluations of randomized and dynamic routing strategies for circuit-switched networks // IEEE Transactions on Communications. 1990. Vol. 39. No. 1. P. 102-116.

82. Miyazawa M. Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing // Queueing Networks. 1997. Vol. 25. P. 45-75.

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

84. Rumsewicz M., Henderson W. Insensitivity with age-dependent routing // Adv. Appl. Prob. 1984. Vol. 21. No. 2. P. 398-408.

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

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

87. Tassiulas L. Adaptive back-pressure congestion control-based on local information // IEEE Transaction on Automatic Control. 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.l.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. Whitt W. Open and closed models for networks of queues// AT&T Bell. Lab. Techn. J. 1984. Vol. 63, No. 9. P. 1911-1979.