3.6 Теория очередей и расчет параметров сети:

3.6.1.Рассмотрим еще один пример:

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

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

3.6.2 Определение параметров системы с очередями

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

Рисунок 1 - Базовая схема системы с очередью к серверу

Центральным элементом этой системы является сервер, который производит определенные действия с элементами данных (пакетами, кадрами, дейтаграммами). Для рассмотрения этой системы примем некоторые допущения. Все элементы данных, поступающие в систему, сохраняются. Если сервер в определенный момент времени простаивает (свободен), элемент данных обрабатывается немедленно. В противном случае поступающие элементы данных сохраняются в очереди. После выполнения сервером обработки определенного элемента данных, он немедленно отправляется по назначению. Если в очереди находятся другие элементы данных, то один из них немедленно поступает на обработку в сервер.

На рисунке 1 также показаны некоторые важные параметры, которые используются при расчетах. Элементы данных поступают в эту систему с некоторой средней скоростью поступления λ, (она измеряется в элементах в секунду). На определенный момент времени некоторое количество элементов данных будет находиться в очереди. Обозначим среднее число элементов данных, находящихся в очереди, буквой ω, а среднее время, которое элементы данных должны ожидать в очереди — символом Т_ω. Этот параметр определен и имеет смысл для всех входящих элементов данных. Сервер обрабатывает входящие элементы данных, затрачивая на это среднее время обработки Ts. Этот временной интервал отсчитывается от момента поступления элемента данных на сервер вплоть до обработки его сервером, (то есть отправки). Утилизация (степень загрузки) сервера ρ — это доля общего времени, в течение которой сервер был занят.

Кроме того, существуют еще два параметра, характеризующие систему в целом. К ним относятся: среднее число элементов данных, находящихся во всей системе, включая элементы данных, которые начали обрабатываться, и элементы, ожидающие обработки, — q и среднее время, которое эти элементы данных находятся в системе, ожидая своей очереди или уже находясь в обработке, - Тq.

Если предположить, что емкость очереди бесконечна, то в такой системе не будет потерянных элементов данных — элементы просто ожидают в очереди до тех пор, пока не будут обработаны. С учетом этого допущения, средняя скорость отправления элементов данных равна средней скорости поступления. Если скорость поступления элементов данных, (которая определяется трафиком, входящим в систему) увеличивается, то, естественно, возрастает нагрузка на сервер, а значит, и утилизация сервера. Из таких же естественных соображений мы заключаем, что увеличение размеров очереди повышает (или, по крайней мере, может повысить, но никак не уменьшить) время ожидания элементов данных в ней. При ρ = 1 сервер загружается до предела, работая 100 % своего времени. Следовательно, теоретическая максимальная скорость поступления элементов данных, при которой они могут быть обработаны сервером, вычисляется по следующей формуле:

λ мах = 1/ Ts

Однако размер очереди резко возрастает при вхождении системы в режим насыщения, стремясь к бесконечности при ρ=1. Поэтому на практике обычно ограничивают скорость поступления данных на сервер до 70-90 % от теоретического максимума.

В таблице 2 перечислены все параметры, которые будут использованы далее при проведении расчетов.

Таблица 2 - Используемые расчетные параметры

Символ	Описание
λ	Средняя скорость поступления элементов данных в систему (число элементов в секунду)
TS	Среднее время обслуживания поступивших элементов (в секундах)
ρ	Утилизация сервера при обслуживании (доля времени, когда сервер занят)
u	Интенсивность трафика
q	Среднее количество элементов данных в системе
Tq	Среднее время, которое элементы данных проводят в системе (в секундах)
ω	Среднее количество элементов данных, ожидающих обслуживания в очереди (размер очереди)
Tω	Среднее время, которое элементы данных ожидают обслуживания (в секундах)
Td	Среднее время ожидания обслуживания для элементов данных, находившихся в очереди (то есть, не включая элементы, для которых время ожидания равно 0)
N	Число серверов
mх(r)	x меньше или равно тx(r) в r процентах случаев

Основная задача при проведении анализа очередей заключается в получении информации о:

• скорости поступления элементов данных в очередь;

• времени обслуживания этих элементов на сервере на входе в систему;

• общем количестве ожидающих элементов;

• времени ожидания элементов в системе.

Для проведения оценки системы определим параметр, характеризующий интенсивность работы системы. Так как рассматриваются средние величины, важно, чтобы норма поступления элементов данных не превосходила общего уровня обслуживания, то есть λ < ρN, или λ /ρN < 1. Эта величина и определяет интенсивность работы системы.

Для обобщения всех вероятных случаев организации системы с очередями, был разработан удобный подход. Все такие системы можно разделить, исходя из применяемых законов распределения времен обслуживания и поступления в систему. Система (в том аспекте, который рассматривается) может быть определена тройкой X/Y/N, где X — это закон распределения времени поступления элементов данных в систему; Y — закон распределения времени обслуживания элементов данных сервером и N — число серверов. Для рассматриваемых здесь систем характерны следующие возможные законы распределения (ниже также указаны буквы, которыми обозначаются эти законы):

• G — нормальное распределение времени поступления или времени обслуживания элементов данных;

• М — пуассоновское распределение времени поступления; пуассоновское или экспоненциальное распределение времени обслуживания элементов данных;

• D — детерминированное время поступления или время обслуживания элементов данных.

Следовательно, модель М/М/1 (таблица 3) определяет систему с одним сервером, пуассоновским распределением времени поступления элементов данных в систему и экспоненциальным временем обслуживания элементов на сервере.

Таблица 3 - Формулы для определения параметров системы с одним сервером

Модель с экспоненциальным распределением времени обслуживания (М/М/1)
q = ρ/1- ρ; ω = ρ^2/1- ρ	mTq(r) = Tqln100/100-r
Tq = TS /1- ρ; Tω = ρ TS/1- ρ	mTω(r) = Tω ln100/100-r

Практика показывает, что наихудшую производительность демонстрирует система с экспоненциальным распределением времени обслуживания, а наилучшую производительность — система с постоянным временем обслуживания. Поэтому обычно можно рассматривать систему с экспоненциальным распределением времени обслуживания, как систему с худшими параметрами.

3.6.3 Расчет параметров системы с одним сервером

ЛВС филиала имеет в своем составе 185 рабочих станций и один сервер (N=1), который обслуживает общую базу данных. Среднее время ответа сервера на запрос – 0,5с (рисунок 2). Стандартное отклонением этого времени также равно 0,5с. В пиковые периоды работы локальной сети скорость поступления запросов к серверу достигает значения 30 запросов в минуту.

Рисунок 2 - Временная диаграмма обработки запросов сервером

Для рассмотрения этой ситуации используем модель M/M/1. Будем считать, что сеть работает без задержек.

Вычислим параметры сети. Сначала определим скорость поступления λ:

λ = 30/60 = 1/2 поступлений в секунду

Утилизацию сервера вычислим по формуле:

ρ =λ T_S = 1/2 · 0,5 = 0,25

Вычислим среднее время ответа:

T_q = T_S /(1- ρ) = 0,5/(1-0,25) = 0,67с

Если допустить, что в некоторых случаях максимальное время ответа сервера будет превышать 1,2с. То можно предположить, что в 90% ответы сервера будут даны менее чем за 1,2с. Если примем такое допущение, то сможем воспользоваться формулой из таблицы 3.6:

m_Tq(r) = T_qln(100/(100-r)), где r- процент ответов сервера менее чем за 1,2с;

Получим:

m_Tq(90) = T_qln(100/(100-90)) = T_S /(1- ρ) · 2,3 = 0,5/(1- ρ) · 2,3 = 1,2с

Учитывая, что T_S= 0,5с, получаем утилизацию (занятие) сервера ρ = 0,04, то есть 4%.

Из этих выкладок следует, что при увеличении загрузки сервера (ρ растет) время обработки запроса (сумма t_ожид. и t_{обработки}) растет медленнее, чем собственно загрузка сервера. Например, при увеличении ρ от 0,25 до 0,5 время обработки увеличится от 0,67с до 1с, то есть на 0,33с, что означает увеличение времени ответа сервера на 49,3%.