Постановка задачи оптимизации СПД с использованием аппарата "Теории массового обслуживания"

Оглавление

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

При проектировании сети, оптимизирующей время доставки сообщения, необходимо выбирать следующие конструктивные переменные:

Процедура выбора маршрутов;
Процедура управления потоком;
Пропускная способность;
Дисциплина обслуживания сообщений в очередях с приоритетами;
Топология первичной сети;
Надежность каналов сети и аппаратных средств.

I. Процедура выбора маршрутов

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

Узел приема сообщения от абонента и узел-получатель;
Приоритет сообщения;
Возможность использования или не использования ряда каналов сети.

Основные процедуры выбора пути:

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

II. Процедура управления потоком

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

III. Дисциплина обслуживания сети

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

Управляющая;
Осведомляющая (например, о состоянии сети);
Преобразующая.

Приоритеты сообщений могут также разделяться:

По срочности передачи сообщения;
По важности информации.

IV. Топология

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

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

D = f (C _i).
Включая стоимость оборудования узла в стоимость канала, тогда, если стоймостная функция линейна, то

где (d _i) - стоимостной коэффициент, зависящий от типа канала, его длины и пропускной способности.

Если функция стоимости ступенчатая, степенная или иная, что ближе к истине, то аналитическое решение усложняется.

Задача использования аппарата ТМО решается аналитически при следующих ограничениях:

Маршрутизация фиксированная.
Длины сообщений, поступающих в узел независимы, т.е. длина сообщения выбирается всякий раз, когда сообщение поступает в узел.
Функция стоимости каналов и узлов линейная.
Пропускные способности каналов выбираются из непрерывного множества.
Каналы симплексные.
Надежность узлов и каналов P_у = Р_к = 1.
Поток сообщений распределен по закону Пуассона, длины сообщений по экспоненциальному.
Задержка сообщения равна T _i = T _ожд + Т_пер + T_обр.

Тогда каждый канал сети может быть представлен СМО типа М/M/1 c пуассоновским распределением потока сообщений на входе и показательным временем обслуживания:

Предыдущий

Следующий