Анализ очередей компьютерных сетей

Анализ очередей компьютерных сетей

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Уральский государственный университет путей сообщения»

(УрГУПС)

Электротехнический факультет Кафедра ”Автоматика, телемеханика и связь”

КУРСОВОЙ ПРОЕКТ

По дисциплине “Сети ЭВМ”

на тему: «Анализ очередей компьютерных сетей»

Вариант №11

Выполнил:

студент группы ИТ-519 Зинчук Н.Д.

Проверил:

Преподаватель Пащенко О.Н.

Екатеринбург

Содержание

Введение

.Параметры системы с очередями

.1 Описание параметров систем с очередями

.2 Расчёт параметров для случая один сервер-одна очередь (M/M/1)

. Расчёт параметры системы с очередями

.1 Расчёт параметров для случая один сервер-одна очередь (M/M/1)

.2 Расчёт параметров для случая несколько серверов-несколько очередей (nM/M/n)

.2.1 Расчёт параметров для случая 2 сервера-2 очереди (2M/M/2)

.2.2 Расчёт параметров для случая 4 сервера-2 очереди (2M/M/2)

.3 Расчёт параметров для случая несколько серверов - одна очередь (nM/M/1)

.3.1 Расчёт параметров для случая 2 сервера-1 очередь (2M/M/1)

.3.2 Расчёт параметров для случая 4 сервера-1 очередь (4M/M/1)

Заключение

Введение

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

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

·    Проведение анализа производительности сети после ее внедрения, основываясь на значениях показателей, которые актуальны в данном конкретном случае;

·        Выполнение простой оценки работоспособности будущей среды, основанной на существующем опыте разработки и построении подобных сетей;

·        Разработка и применение аналитической модели, основанной на теории очередей;

·        Разработка и применение простейшей программы, моделирующей поведение сети.

Первый вариант предполагает пассивную позицию разработчика сети. Разработчик просто ожидает результатов своей деятельности. Естественно, такой метод чреват непредсказуемыми последствиями. Полученным результатом, как правило, оказываются недовольны и пользователи, и руководители организации. Их можно понять - они понесли неоправданные затраты, но, в итоге, так и не получили сети с желаемыми параметрами.

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

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

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

1.   Параметры системы с очередями

1.1 Описание параметров систем с очередями

компьютерная сеть сервер очередь

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

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

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

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

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

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

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

Рисунок. 2. Модели одной очереди а) к нескольким серверам

б) к каждому серверу.

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

Если в системе N идентичных серверов, а ρ обозначает утилизацию каждого сервера, то можно рассматривать Nρ как утилизацию всей системы. Этот показатель часто рассматривают как интенсивность трафика (в табл. обозначена символом u) или интенсивность работы системы. Следовательно, теоретическая максимальная утилизация такой системы будет равна Nx100%. Максимальная скорость поступления элементов данных в такую систему будет определяться по формуле:

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

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

Эти формулы могут быть полезны для вычисления некоторых параметров при «интуитивном» выборе структуры системы. Для получения формулы

ρ = λTs достаточно заметить, что для скорости поступления элементов данных λ, среднее время между поступлениями элементов будет определяться выражением Т = 1/λ. Если интервал времени Т меньше интервала времени Ts, то можно будет записать Тs/Т = λTs. Аналогичные рассуждения подходят и в случае со множеством серверов: р = (λTs)/N.

Рассмотрим момент времени прихода очередного элемента данных. При поступлении этого элемента в систему в очереди находится в среднем ω элементов данных, которые ожидают обслуживания. В момент, когда этот элемент покидает очередь для обслуживания, он оставляет после себя такое же среднее количество элементов в очереди (на то оно и среднее количество, что не меняется). Среднее время, которое элемент ждет своей очереди до обслуживания, равно Ts. А так как элементы поступают в очередь со скоростью λ, то можно утверждать, что за промежуток времени Tω должно поступить λTω элементов данных. Следовательно, ω = λTω. Рассуждая аналогично, можно заключить, что q = λТq.

Из табл. П4.2 видно, что время, которое элемент данных находится в системе, равно сумме времени ожидания обслуживания и времени самого обслуживания. На любой момент времени количество элементов во всей системе равно сумме количества элементов, ожидающих обслуживания, и количества элементов, которые уже обслуживаются. Для одного сервера среднее число элементов, которые обслуживаются в данный момент времени, равно ρ. Следовательно, q = ω +ρ для одного сервера. Аналогично, q = ω + Nρ, если рассматривать случай с N серверами.

Входной информацией для очередей является :

·    скорость поступления запросов;

·        время обслуживания;

·        количество серверов.

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

·        время ожидания;

·        количество запросов в очереди;

·        время нахождения запроса в системе.

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

·    Поступление одного элемента данных не зависит от поступления другого элемента, то есть события происходят независимо;

·        Никогда не поступают сразу два или более элементов данных;

·        Среднее количество поступлений не изменяется со временем (то есть распределение статично).

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

где е - основание натуральных логарифмов;

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

n - количество элементов, поступивших за время t.

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

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

где X - это закон распределения времени поступления элементов данных в систему;

У - закон распределения времени обслуживания элементов данных сервером ;- число серверов.

Для рассматриваемых здесь систем характерны следующие возможные законы распределения (ниже также указаны буквы, которыми обозначаются эти законы):

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

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

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

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

Формулы для определения параметров системы с одним сервером

В первом столбце показаны формулы для определения некоторых параметров системы с одним сервером, которая подчиняется модели М/G/1. В соответствии с этой моделью скорость поступления элементов данных подчиняется пуассоновскому закону, а время обслуживания - нормальному распределению. Использование масштабирующего коэффициента А в значительной мере упрощает формулы для вычисления основных выходных параметров. Следует учесть, что коэффициент масштабирования зависит только от отношения стандартного (среднеквадратичного) отклонения времени обслуживания к среднему времени обслуживания . При этом не требуется никакой другой информации о времени обслуживания.

Другие два случая это - модель с распределением времени ожидания по пуассоновскому закону, а времени обслуживания по экспоненциальному закону (М/М/1, второй столбец) и модель, в которой время обслуживания всех элементов одинаково (а значит, отклонение времени обслуживания равно нулю), а время поступления элементов подчиняется пуассоновскому закону (M/D/1, третий столбец). Вычисления при помощи этих формул носят приближенный характер, но для практического применения их точности вполне достаточно.

Формулы для определения параметров системы со множеством серверов

В таблице приведены формулы для определения основных параметров в случае работы с системой со множеством серверов. Эти формулы применимы только для случая использования модели M/M/N. То есть предполагается пуассоновский характер распределения времен поступления элементов данных и экспоненциальный характер времени обслуживания этих элементов. При этом формула Пуассона для распределения времени обслуживания применима для всех N серверов. Во всех выражениях используется функция Эрланга С, которая, в одних случаях, определяет вероятность того, что все сервера заняты в определенный момент времени, а в других случаях - вероятность того, что количество элементов данных, находящихся в данный момент времени в системе (ожидающих в очереди или обслуживающийся), будет больше или равно количеству серверов. Для вычисления функции С применима следующая формула:

где К - коэффициент пуассоновского распределения.

Значение этой функции зависит от количества серверов (N) и их утилизации (ρ).

1.2 Расчёт параметров для случая один сервер-одна очередь (m/m/1)

Исходные данные:

Расчёт параметров для случая один сервер-одна очередь (M/M/1):

1)   Коэффициент использования сервера ρ (утилизация)

ρ=nλT_s= 65*0,083*0,1=0,542

2)   Среднее время пребывания запроса на сервере, среднеквадратичное отклонение времени пребывания запроса на сервере T_q; σ_Tq;

T_q= =  = 0,218 (сек)

σ_Tq=  = =0,476 (сек)

3)      Среднее количество запросов в системе, ожидающих обслуживания и среднеквадратичное отклонение числа запросов в системе, ожидающих обслуживанияq;σ_q

4)     

q=== 1,182

σ_q =  = = 1,606

5)      90; 95 процентили времени ожиданияm_Tω(90); m_Tω(95);

m_Tω(90) = T_ω= 0,118 *=0,200_Tω(95) = T_ω= 0,118 *=0,282

6)      Среднее количество запросов ожидающих обслуживания ω

ω= =0,640

T_ω =  =  = 0,118 (сек)

2.   Расчёт параметры системы с очередями

.1 Расчёт параметров для случая один сервер-одна очередь (m/m/1)

1)      Коэффициент использования сервера ρ (утилизация)

ρ=nλT_s= 65*0,083*0,1=0,542

2)      90; 95 процентили времени ожидания m_Tω(90); m_Tω(95);

m_Tω(90) = T_ω= 0,118 *=0,200_Tω(95) = T_ω= 0,118 *=0,282

3)      Среднее время ожидания обслуживания T_ω

T_ω =  =  = 0,118 (сек)

2.2 Расчёт параметров для случая несколько серверов - несколько очередей (nm/M/n)

.2.1 Расчёт параметров для случая 2 сервера-2 очереди(2m/m/2)

1)      Коэффициент использования сервера ρ (утилизация)

ρ===0,133

2)      90; 95 процентили времени ожидания m_Tω(90); m_Tω(95);

m_Tω(90) = T_ω= 0,015*=0,004_Tω(95) = T_ω= 0,015*=0,015

3)      Среднее время ожидания обслуживания T_ω

T_ω =  =  = 0,015 (сек)

2.2.2 Расчёт параметров для случая 4 сервера-4 очереди(4m/m/4)

1)      Коэффициент использования сервера ρ (утилизация)

ρ===0,033

2)      90; 95 процентили времени ожидания m_Tω(90); m_Tω(95);

m_Tω(90) = T_ω= 0,003*=-0,004_Tω(95) = T_ω= 0,003*=-0,001

3)      Среднее время ожидания обслуживания T_ω

T_ω =  =  = 0,003(сек)

2.3 Расчёт параметров для случая несколько серверов-одна очередь (nm/M/1)

.3.1 Расчёт параметров для случая 2 сервера -1 очередь (2m/m/2)

1)      Коэффициент использования сервера ρ (утилизация)

ρ===0,271

K=0,91311054

2)      90; 95 процентили времени ожидания m_Tω(90); m_Tω(95);

m_Tω(90) = = *= 0,010_Tω(95) = = *= 0,057

3)      Среднее время ожидания обслуживания T_ω

T_ω =*  = =0,008(сек)

2.3.2 Расчёт параметров для случая 4 сервера -1 очередь(4m/m/4)

4)      Коэффициент использования сервера ρ (утилизация)

ρ===0,135

=0,997912713

5)      90; 95 процентили времени ожидания m_Tω(90); m_Tω(95);

m_Tω(90) = = *= -0,108_Tω(95) = = *= -0,088

6)      Среднее время ожидания обслуживания

T_ω =* = = 0,000070 (сек)

Таблица 2- Параметры системы с очередями

ρ

T_ω

m_Tω(90)

m_Tω(95)

N=1(M/M/1)

0,542

0,118

0,200

0,282

N=2(2M/M/2)

0,133

0,015

0,004

0,015

N=4(2M/M/4)

0,033

0,003

-0,004

-0,001

N=2(2M/M/1)

0,271

0,008

0,010

0,057

N=4(4M/M/1)

0,135

0,000070

-0,108

-0,088

Заключение

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

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