6.4.4 Анализ динамической памяти с цепочкой буферов

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

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

В рассматриваемом случае УК может быть формально представлен моделью открытой сети МО с несколькими классами сообщений, отказами, блокировкой и пуассоновским потоком поступлений интенсивностью . Сообщения класса требуют для ввода в сеть свободных приборов обслуживания первого в сети центра «Память». Этот многолинейный центр состоит из N приборов буферов каждый объемом

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

Число классов R определяется наименьшим целым, удовлетворяющим неравенству , где - максимальная длина сообщений. Длина сообщений класса имеет распределение

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

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

где при при

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

Обозначим, как и раньше, - вероятность того, что сообщение класса после окончания обслуживания в центре поступает в центр - вероятность поступления внешнего потока класса в центр

Состояние сети определяется вектором где - количество сообщений класса в центре . Обозначим также через , где количество сообщений класса в состоянии сети . Допустимое множество состояний сети

Легко видеть, что условие (6.25) при определяет зависимость потоков, входящих в сеть от ее состояния. Справедливо следующее утверждение.

Утверждение. Если центры рассматриваемой сети МО удовлетворяют условиям теоремы ВСМР, то стационарные вероятности сети имеют мультипликативную форму:

где - функции, определенные в п. 2.2.1:

и для приборов обслуживания

Здесь так же как и раньше, однозначно определяется из системы уравнений

Для центра с дисциплиной обслуживания FCFS предполагается, что . Нормализующая константа имеет вид

Для доказательства (6.26) используем достаточные условия мультипликативности стационарных вероятностей сетей МО, сформулированные в разделе 2.3.4. Пусть - вектор с неотрицательными компонентами;

Введем функцию потерь, определяющую условия ввода в сеть сообщений класса ,

и «триггерную» функцию, определяющую правило ухода из сети сообщений класса

Условие мультипликативности имеет вид тогда и только тогда, когда для . Для сетевой модели памяти УК с резервированием буферов это условие, очевидно, выполняется, что обеспечивает справедливость (6.26).

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

Рассмотрим вероятность того, что в сетевой модели УК С приборов центра «Память» заняты обслуживанием или блокированы:

где

Обозначим , где имеем

Отказ в приеме в буферную память сообщению, требующему буферов, соответствует множеству состояний

Отсюда вероятность отказа приема сообщений в память из N буферов, каждый объемом

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

(6.29)

Здесь - символ свертки векторов

где функции

- маргинальная стационарная вероятность условия

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

Здесь определяется из системы уравнений (6.27). При этом допустимое множество состояний имеет вид . Из (6.26) следует, что для изолированного центра стационарная вероятность определяется выражением

где нормализующая константа имеет вид

Стационарная вероятность условия (6.30) для изолированного центра

Очевидно, и с учетом выражения для полагать, что при

Можно показать, что в центрах типа IS удовлетвлоряет уравнению

Справедливо следующее утверждение.

Утверждение. Стационарная вероятность любого изолированного центра сетевой модели УК удовлетворяет уравнению

где - математическое ожидание числа занятых обслуживающих приборов из R при условии (6.30).

Доказательство. Обозначим . Уравнения локального баланса для центра могут быть записаны в виде

где

- математическое ожидание количества приборов из R, занятых обслуживанием сообщений класса в состоянии Суммирование (6.33) по и по всем дает

Следовательно,

Левая часть (6.34) может быть записана в виде

что и требовалось доказать.

Следствие 1. Для центров типа IS (N приборов) с учетом (6.31)

где . Это выражение определяет среднее число сообщений в центре при фиксированном

Следствие 2. Для однолинейного центра , что преобразует (6.32) к виду

Для многолинейного центра определение проблематично. В этом случае возможна аппроксимация выражением (6.35) с учетом неравенства что дает приближенный способ вычисления

Для имеем для справедливо Такая аппроксимация дает наилучшие приближения для небольших R, что вполне приемлемо для равнодоступных пучков каналов передачи УК.

Выражения (6.31), (6.36), (6.37) определяют рекурсии для вычисления что в свою очередь дает возможность определить и, следовательно, вероятность отказа приема сообщений в память . Эти рекуррентные вычислительные процедуры требуют малой памяти и весьма эффективны для практических расчетов при очень большом числе классов R и количестве буферов N. Общий объем требуемой памяти

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

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