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

3.3.2 Оценка эффективности вычислительного алгоритма

Рассмотрим вначале алгоритм анализа средних значений для сети, состоящей из однолинейных центров с дисциплиной обслуживания FCFS, LCFS, PS или центров с дисциплиной обслуживания IS. В этом случае из (3.39)следует

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

Алгоритм расчета среднего времени ожидания средней длины очереди и пропускной способности не требует вычисления маргинального распределения и включает следующие шаги:

Шаг 1. Инициализация: для всех

Шаг 3. Главные циклы: для выполнять шаги 3, 4, 5.

Шаг 3. Вычислить

для всех .

Шаг 4? Формула Литтла для сообщения класса

Шаг 5. Формула Литтла для узлов

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

Рассмотрим теперь расширение вычислительной процедуры для случая, когда сеть включает многолинейные центры с дисциплиной обслуживания FCFS. Выражение (3.39) в этом случае по аналогии с (2.45) представляется в виде

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

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

где - среднее число занятых обслуживающих приборов, которое определяется по формуле Литтла: Таким образом,

Теперь все подготовлено для формального описания алгоритма. Шаг 1. Инициализация: для

Шаг 3. Основной цикл по Такой же, как и в предыдущем алгоритме.

Шаг 3. Вычислить

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

Шаг 4 и шаг 5. аналогичны предыдущему алгоритму.

Шаг 6. Дополнительный шаг в основном цикле для вычисления маргинальных вероятностей. Для всех многолинейных центров и вычислить:

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

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

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