Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.4.2 Анализ однородного пула равнодоступных буферов

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

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

Во втором однолинейном центре «Процессор» длительность обслуживания равна времени обработки сообщения в процессоре УК. Обслуживание сообщений в этом центре осуществляется в соответствии с дисциплиной FCFS. Выделим группу из L центров, формализующих работу L выходящих каналов УК. Каждое сообщение, обслуженное во втором центре, с вероятностью поступает на обработку в центр группы выходящих каналов Дисциплина обслуживания очередей в центрах этой группы - FCFS. Сообщения, прошедшие обслуживание в центре упомянутой группы, с вероятностью поступают в соответствующий центр АСК, нормализующий ожидание логического подтверждения передачи по каналу j. В противном случае с вероятностью эти сообщения поступают в центр моделирующий задержку time-out, после которой осуществляется повторное обслуживание сообщения в центре группы выходящих каналов.

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

Рис. 6.7

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

Математическая модель УК позволяет определить зависимость вероятности отказа от количества мест (буферов) накопителя. По этой зависимости, исходя из допустимой вероятности отказов входящим в узел сообщениям, легко определить объем буферной памяти.

Анализ описанной МО в общем случае при произвольных распределениях длительности обслуживания сообщений в центрах с дисциплиной FCFS можно осуществить с помощью приближенных методов, описанных в гл. 4. Решение задачи значительно упрощается, если в моделях УК перейти к локально-сбалансированной сети МО. При этом вся сеть МО включает лишь два типа центров: с дисциплиной обслуживания LCFS или IS. Длительность обслуживания в центрах FCFS распределена по экспоненциальному закону; в центрах IS она имеет произвольное распределение, допускающее рациональное преобразование Лапласа.

Открытая сеть МО, моделирующая функционирование УК, эквивалентна замкнутой сети МО. Для перехода от открытой сети к замкнутой достаточно ввести однолинейный центр обслуживания «Источник» с номером 0 (см. рис. 6.7), из которого сообщения направляются в центр 1. Длительность обслуживания в «Источнике» распределена по экспоненциальному закону с параметром . В замкнутой сети МО, включающей центров обслуживания, постоянно циркулирует N сообщений (количество буферов общего накопителя).

Обозначим через вектор состояние сети МО. Здесь - число сообщений в нулевом центре, интенсивность обслуживания которого не зависит от нагрузки; - число сообщений в центре «Память», интенсивность обслуживания которого зависит от нагрузки; - число сообщений ожидающих обработки в центре «Процессор», интенсивность обслуживания которого не зависит от нагрузки; k - число сообщений, ожидающих передачи и передаваемых по каналу связи ), интенсивность обслуживания которого не зависит от нагрузки; - число сообщений, переданных по каналу и ожидающих подтверждения АСК. Процесс передачи АСК моделируется центром с дисциплиной обслуживания IS и интенсивностью обслуживания зависящей от нагрузки; - число сообщений, переданных по каналу и требующих повторения по time-out.

Этот процесс моделируется центром с дисциплиной обслуживания IS и интенсивностью обслуживания

Обозначим также через

вектор относительных интенсивностей потоков. Индексы координат этого вектора соответствуют обозначению центров сети. Тогда легко видеть, что решение системы уравнений (1.4) имеет вид:

Стационарные вероятности рассматриваемой сети МО имеют вид

где

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

где

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

Для определения объема памяти УК при заданной допустимой вероятности отказа Рдоп последовательным изменением числа буферов N находится минимальное N. удовлетворяющее неравенству

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

где - среднее число сообщений, пребывающих в источнике.

Из формул раздела 2.3 легко определяются выражения для других характеристик УК. Например, производительность УК, представляющая собой поток сообщений, проходящий через источник (или процессор), имеет вид Вычисление и других характеристик УК осуществляется по формулам (3.3) в соответствии с алгоритмом, описанным в разделе 3.1. Алгоритм вычисления можно упростить, используя специфику модели УК - наличие двух типов центров: IS и однолинейных центров с дисциплиной обслуживания FCFS.

Объединим все центры с дисциплиной обслуживания IS в один укрупненный центр, число сообщений в котором -Тогда стационарная вероятность укрупненного состояния имеет вид

где

При вычислении нормализующей константы укрупненному центру типа IS необходимо присваивать номер один, тогда в соответствии с алгоритмом Бузена расчет упрощается. Дальнейшее упрощение вычислительной процедуры достигается, если часть центров обладает одинаковыми параметрами . Это обычно выполняется на практике, так как сообщения с идентичным распределением длин зачастую равномерно распределяются между исходящими из УК каналами, имеющими одинаковую скорость передачи. Из алгоритма Бузена также следует, что наиболее трудным с точки зрения затрат времени и памяти ЭВМ является расчет сети, зависящей от нагрузки.

Это соответствует случаю, когда для передачи сообщений из УК в отдельных направлениях используются пучки каналов.

<< Предыдущий параграф Следующий параграф >>
Оглавление