ГЛАВА 5. Развитие теории мультипликативных сетей очередей

5.1 Основные направления развития теории мультипликативных сетей

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

В ряде других работ в последние годы получено значительное количество теоретических результатов, обобщающих и расширяющих теорему ВСМР. В частности, в работе Ноетзелла введена обобщенная дисциплина обслуживания LBPS (Last Batch Processor Sharing), определяющая большой класс дисциплин обслуживания, при которых стационарные вероятности состояний сети МО имеют мультипликативную форму для произвольного распределения длительностей обслуживания в центрах сети.

Наиболее общая теорема о необходимых и достаточных условиях существования мультипликативной формы решения для сети МО с несколькими классами сообщений доказана в [160].

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

Рассмотрим открытую ВСМР-сеть, в которую поступает L пуассоновских потоков сообщений. Дополнительно к обозначениям п. 2.3.2 введем вектор агрегированного состояния сети

На множестве L-мерных, целочисленных, неотрицательных векторов заданы два набора функций: , которые могут принимать значения в множестве 0,1. Поступающее в сеть сообщение подцепи принимается на обслуживание, если функция потерь и теряется, если «Триггерная» функция если в момент ухода из сети сообщения подцепи новое сообщение указанной подцепи мгновенно вводится в сеть, и в противном случае.

Введем следующие обозначения:

где D и V - соответственно допустимые множества векторов . Тогда справедлива следующая теорема.

Теорема. Пусть функция потерь и «триггерные» функции удовлетворяют условию , для всех пар у и из V. Тогда стационарное распределение вероятностей состояний сети МО имеет мультипликативную форму:

где

- нормализующая константа.

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

Другие направления развития - сети с зависимым обслуживанием и -сети [18] рассматриваются в последующих разделах настоящей главы.