Информационные сети и телекоммуникационные каналы. Теоретические основы современных информационных сетей. Теория очередей (массового обслуживания)

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

Такие параметры, как число и длина пакетов, поступающих в сеть или проходящих через неё в любой момент времени, число вызовов, поступающих на вход сети за заданное время, продолжительность занятия (ресурса) – в общем случае подвержены статистическим изменениям. Поэтому для изучения их воздействия на сеть и получения соответствующих количественных характеристик должны применяться вероятностные методы.

Ключевую роль в анализе сетей играет теория очередей (называемая также теорией массового обслуживания)

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

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

Рассмотрим простейшую модель обслуживания:

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

Пакты поступают случайным образом со скоростью l в единицу времени. Они ожидают обслуживания в накопителе, и обслуживаются в соответствии с некоторой конкретной дисциплиной со средней скоростью m пакетов в единицу времени. На рисунке показана одна обслуживающая линия. В более же общем случае могут быть доступны несколько обслуживающих линий, и в этом случае одновременно могут обслуживаться несколько пакетов. В контексте сети передачи данных обслуживающая линия ѕ это средство передачи (исходящий канал или линия, передающие пакеты или, в случае систем с коммутацией каналов, обрабатывающие вызовы), которое передает данные с предписанной скоростью C блоков данных в единицу времени. Таким образом, процесс обслуживания определяется длиной пакета или продолжительностью соединения.

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

Для однолинейных систем обслуживания стабильность обеспечивается при l < m . Введём параметр r = l / m . Его называют коэффициентом использования канала или интенсивностью нагрузки. Когда r приближается к 1 или превышает её, возникает область перегрузки, и поступающие пакеты блокируются более часто.

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

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

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

Рассмотрим бесконечно малый промежуток времени D t (D t® 0), проходящий между моментами t и t+D t. При определении пуассоновского процесса используются три основные предпосылки:

Если теперь рассмотреть большой промежуток времени Т, то вероятность p(k) того, что в промежутке Т произойдут k поступлений, равна:

Это равенство называется распределением Пуассона. Оно нормировано:

Теперь рассмотрим большой промежуток времени и отметим на нём моменты, в которые наступили события Пуассоновского процесса.

Очевидно, что t - это положительная случайная величина с непрерывным распределением. Оказывается, что для Пуассоновского распределения величина t распределена по показательному закону:

Среднее значение показательного распределения:

Рассмотрим очередь из нескольких вызовов, ожидающих обслуживания. Отметим время завершения обслуживания:

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

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

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

Ещё одно полезное свойство, объединяющее одну из причин, по которой Пуассоновский процесс часто используется для моделирования входящих потоков, заключается в том, что при объединении m независимых Пуассоновских потоков с произвольными интенсивностями l ₁, l ₂, … l _m, объединённый поток также будет Пуассоновским с интенсивностью

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

Система обслуживания М/М/1 – это система с одной обслуживающей линией, Пуассоновским входящим потоком, показательным распределением обслуживания и дисциплиной ОПП (обслуживание в порядке поступления).

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

Пусть процессы поступления и обслуживания определяются соответственно параметрами l и m . Определим вероятность p_n(t+D t) того, что в момент времени t+D t в системе будет находиться n клиентов (пакетов или вызовов). Из диаграммы видно, что в момент времени t система могла находиться только в состоянии n-1, n или n+1. Тогда мы можем записать:

Вероятности перехода из одного состояния в другое получены в результате рассмотрения путей, по которым происходят эти переходы, и расчёта соответствующих вероятностей. Например, если система осталась в состоянии n, то могли произойти либо уход и одно поступление с вероятностью m D t, либо ни одного ухода или поступления с вероятностью

, что и показано в первом случае.

Производя упрощения, иcпользуя разложение

в ряд Тейлора, можно получить следующее уравнение:

Для стационарного состояния вероятность p_n(t) приближается к некоторому постоянному значению, поэтому

= 0. Тогда последнее уравнение для стационарного случайного процесса упрощается и принимает вид:

Форма уравнения (1) показывает, что при работе системы действует стационарный принцип равновесия: левая часть описывает интенсивность уходов из состояния n, а правая часть – интенсивность приходов в состояние n из n-1 или n+1. Чтобы существовали вероятности стационарного состояния, эти две интенсивности должны быть равны.

Рассмотрим диаграмму состояний для системы М/М/1

Ввиду предположений о Пуассоновском процессе поступления и уходов клиентов переходы имеют место только между соседними состояниями с показанными интенсивностями.

Уравнение (1) может быть решено несколькими способами. При простейшем их них может быть использовано условие равновесия. Если рассчитать общий “поток вероятности”, пересекающий границу области 1, и приравнять исходящий поток к входящему, получиться уравнение (1). Область 2 охватывает всё множество точек от 0 до n. Поток, поступающий в эту область, равен m p_n+1, а поток, покидающий её, равен l p_n. Приравнивая эти два потока, получим: m p_n+1=l p_n. Повторяя последнее уравнение n раз, получим:

Значение р₀ для случая бесконечной очереди можно найти, используя нормирующее условие:

. Просуммировав n вышеприведенных уравнений и учитывая нормировку, получим:

Используя это, можно записать решение для установившегося режима:

Распределение вероятностей (2) системы М/М/1 называется геометрическим распределением.

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

В частности, вероятность того, что очередь заполнена, совпадает с вероятностью блокировки:

На следующем рисунке приведён график вероятности блокировки в зависимости от нормированной нагрузки r .

Область r >1 называется областью перегрузки или скученности. Производительность системы, которая близка к нагрузке l при малых r , выравнивается и при возрастании r приближается к пропускной способности m .

Рассмотрим область r <1. На основании определения среднего значения p_n, проведя суммирование, получим среднее число E(n) клиентов в системе, включая находящихся на обслуживании:

При увеличении r среднее число клиентов в очереди резко возрастает за счёт (1-r ) в знаменателе.

Можно заметить, что при росте нагрузки системы растёт её производительность, однако при этом блокируется всё большее количество клиентов, а следовательно, растёт E(n), что ведёт к увеличению времени задержки в очереди.

Для нахождения времени задержки используют формулу Литтла:

l E(T) = E(n), где E(T) – среднее время задержки в системе.

Знаете ли Вы, что, когда некоторые исследователи, пытающиеся примирить релятивизм и эфирную физику, говорят, например, о том, что космос состоит на 70% из "физического вакуума", а на 30% - из вещества и поля, то они впадают в фундаментальное логическое противоречие. Это противоречие заключается в следующем.

Вещество и поле не есть что-то отдельное от эфира, также как и человеческое тело не есть что-то отдельное от атомов и молекул его составляющих. Оно и есть эти атомы и молекулы, собранные в определенном порядке. Также и вещество не есть что-то отдельное от элементарных частиц, а оно состоит из них как базовой материи. Также и элементарные частицы состоят из частиц эфира как базовой материи нижнего уровня. Таким образом, всё, что есть во вселенной - это есть эфир. Эфира 100%. Из него состоят элементарные частицы, а из них всё остальное. Подробнее читайте в FAQ по эфирной физике.