6.3.3 Локальное управление буферами

Как упоминалось в разделе 6.1, различают статическое и динамическое управление буферами. Последнее полностью обобщает статические стратегии управления, поэтому ниже в первую очередь рассматривается динамическое управление буферами.

Динамическое ситуационное управление, определенное в [42,53], основывается на информации о текущем состоянии УК. Оно состоит в принятии решения о вводе пакета в момент его поступления в зависимости от состояния буферной памяти узла. Сетевая модель УК, описанная в разделе 6.4, в данном случае включает R классов пуассоновских потоков поступлений пакетов с интенсивностями соответственно , определяемыми потоками в R выходящих из узла каналов.

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

С каждой стратегией связано допустимое множество состояний. Равнодоступная для всех классов память CS (Complete Sharing) определяет допустимое множество Полное разделение CP (Complete Partitioning), при котором каждому классу пакетов выделяется изолированная от других классов часть памяти, имеет допустимое множество Произвольная стратегия Q определяется только правилом ввода-вывода пакетов в УК, а не их уходом из узла, поэтому

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

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

Утверждение. Для простой стратегии, определенной на координатно-выпуклом множестве состояний стационарные вероятности сетевой модели УК имеют мультипликативную форму

где функции введены ранее;

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

Выражение (6.19) непосредственно следует из достаточных условий мультипликативности стационарных вероятностей открытых ло-кально-сбалансированных сетей с зависимостью интенсивностей пуассоновских потоков поступлений от количества пакетов в сети [53,183]. Триггерная функция, определяющая правило ухода из сети пакетов класса

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

Рис. 6.5

Во избежание громоздких выкладок проиллюстрируем проблему оптимального динамического управления на упрощенной модели УК (рис. 6.5), традиционно рассматриваемой для анализа локального управления буферами. В такой модели УК представляется R выходящими каналами связи и буферной памятью размером в N буферов, каждый канал - однолинейной системой М/М/1 с интенсивностью обслуживания и дисциплиной обслуживания FCFS («первым пришел - первым обслужен»). Весь узел состоит из набора R таких очередей. Эти очереди имеют N общих мест для ожидания. Пакеты, не принятые в очередь, получают отказ. Поток поступлений в узел представляется R классами пуассоновских потоков, характеризующимися направлением передачи и интенсивностью

Рис. 6.6

Состояние УК описывается марковским процессом , где - количество пакетов класса в узле. Допустимое множество состояний произвольной стратегии управления

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

где - стационарная вероятность состояния . При выражение (6.20) дает пропускную способность УК.

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

В (6.21) используются обозначения

Введение переменных

преобразует систему (6.21) в линейную систему ограничений задачи линейного программирования относительно Значения управляющих переменных определяются из (6.21) после решения задачи линейного программирования.

Как известно, всякому опорному плану задачи линейного программирования соответствует целочисленный набор вероятностей состоящий из нулей и единиц. Это поясняет смысл переменных как «разрешений» на ввод пакетов в память узла и позволяет получить из (6.22) дополнительные ограничения для задачи линейного программирования .

Рассмотрим модель УК с двумя каналами передачи и буферами памяти (см. рис. 6.5). В этом случае анализ оптимального управления показывает [53], что оптимальные стратегии определены на координатно-выпуклом пространстве состояний

где граница (рис. 6.5). При этом переходы управляемого процесса ограничиваются не только на границе но и внутри этой области. Увеличение загрузки второго канала при фиксированной меняет границы области запрещая ввод пакетов обоих классов даже при наличии свободных буферов (штриховые линии на рис. 6.6). Однако общий вид оптимального управления даже в этом случае получить не удается. Для простых стратегий на координатно-выпуклых множествах состояний и трех каналов в [183] получен вид допустимого пространства состояний, соответствующий оптимальной стратегии:

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

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

Пусть - потери, связанные с вытеснением из памяти пакетов класса . Тогда в прежних обозначениях функционал (6.34) примет вид

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

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

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

Наиболее простыми статическими схемами управления являются упомянутые выше равный доступ CS и полное разбиение СР. В последней вся память разделена на R частей, каждая из которых постоянно закрепляется за соответствующим классом пакетов. Очевидно, такая схема будет давать лучшие показатели только при чрезмерных по всем R классам входящих в узел потоков. В иных случаях она не обеспечивает эффективного использования памяти. Во избежание захвата буферов более интенсивными потоками было предложено несколько схем статического управления [233]. Ниже рассматриваются эти схемы с учетом многоэтапного процесса буферизации в УК.

Схема SMXQ. Эта схема управления ограничивает количество буферов, доступных пакетам каждого класса. При этом вводятся границы , такие, что

Возможные состояния определяются в виде

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

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

Схема SMQMA. Данная схема по существу является объединением двух предыдущих схем. В отличие от SMA, в этой схеме налагаются ограничения на число пакетов каждого класса в общем пуле буферов В. При этом допустимое множество состояний

Очевидно, схема SMQMA обобщает все рассмотренные схемы статического управления буферами. Допустимые множества для них могут быть непосредственно получены из (6.23).

При статическом управлении, как и для любой простой стратегии управления на координатно-выпуклых множествах, стационарная вероятность сетевой модели УК имеет мультипликативный вид (6.33). Вычисление и требуемых характеристик УК для схем статического управления может быть осуществлено алгоритмами свертки для сетей МО с несколькими классами при некоторой их модификации относительно допустимого пространства состояний, соответствующего схеме управления. Вероятность отказа приема в УК пакетов класса для общей схемы SMQMA

Характеристики упрощенной модели УК (см. рис. 6.5) могут быть получены в явном виде в терминах нормализующей константы G. Для некоторых схем управления они имеют весьма простой вид [75]. Выбор конкретной схемы статического управления или, что то же самое, параметров схемы SMQMA основывается на компромиссе между пропускной способностью узла и задержкой пакетов в нем. Последние существенным образом зависят от особенностей многоэтапного процесса буферизации УК.