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

4.2.2 Приближенный декомпозиционный алгоритм

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

(4.6)

Первое условие отражает закон равенства нормализованных пропускных способностей (пропускная способность центра пропорциональна относительной интенсивности потока е. Второе состоит в том, что в замкнутой сети сумма средних значений длин очередей должна быть равна N. Отметим, что оба условия не зависят от вида функций распределения и дисциплин обслуживания в центрах сети.

Формально указанные условия можно представить в виде системы М нелинейныъх уравнений с М неизвестными:

где - функции переменных .

Следуя [90], перейдем от задачи решения системы нелинейных уравнений (4.7) к эквивалентной задаче минимизации функции

где

Введем барьерную функцию задачу (4.8) можно заменить задачей безусловной минимизации функции

где - весовой коэффициент.

Алгоритм решения исходной задачи расчета характеристик замкнутой сети с произвольно распределенной длительностью обслуживания в узлах может базироваться либо на решении оптимизационной задачи (4.9) [90], либо на непосредственной проверке условий Однако в обоих случаях алгоритм реализует итеративную процедуру преобразования исходной сети в сеть с двумя центрами. Указанная сеть включает центр исходной сети с произвольной функцией распределения длительности обслуживания и дополнительный (композиционный) центр В с экспоненциальным распределением длительности обслуживания.

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

Итерационный вычислительный алгоритм включает следующие основные шаги.

Шаг 1. Инициализация: интенсивности обслуживания устанавливаются равными интенсивностям , заданным для исходной сети, т. е. ; устанавливается в нуль счетчик числа итераций

Шаг 2. Для каждого центра определяются параметры композиционного центра . В зависимости от значения коэффициента вариации функция распределения времени обслуживания в центре аппроксимируется соответственно экспоненциальным, обобщенным эрланговским или гиперэкспоненциальным распределением.

Шаг 4- Рассчитывается замкнутая сеть с двумя центрами. Вычисляются производительность и средняя длина очереди

Шаг . Если , где - заданная точность решения, то для тех , для которых устанавливается (здесь ). Если таких центров нет, то для всех устанавливается и осуществляется переход к шагу 7.

Шаг 5. Если то для тех , для которых , устанавливается . Если таких центров нет, то для всех устанавливается и осуществляется переход к шагу 7.

Шаг 6. Если то для всех установим . Алгоритм завершает работу, если выполняются все неравенства . В противном случае осуществляется переход к шагу 7.

Шаг 7. Устанавливается и осуществляется переход к шагу 2.

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