Наименование темы: 1.Классификация потоков. 2.Поток освобождения серверов

Наименование темы: 1.Классификация потоков. 2.Поток освобождения серверов

Классификация потоков.

Пуассоновский (простейший) поток запросов

Стационарный ординарный поток без последействия называют простейшим. Он задается набором вероятностей P_i(t) поступления i требований в промежутке длиной t.

 

Можно показать, что при этих предположениях формула для P _i(t) дается формулой Пуассона (Poisson):

.

Проанализируем основные характеристики пуассоновского потока. Рассмотрим отношение P_i(t)/P_i-1(t). При i ≤ λt вероятность растет, а при обратном соотношении – убывает. Графики функции распределения Пуассона в зависимости от величины λt для различных значений k приведены на рис. 1.

Рис. 1. Графики Пуассоновского распределения в зависимости от lt для различных k.

Наряду с распределением P_i(t) используют вероятности поступления не менее i требований в интервал t или не более i требований за время t:

Если рассмотреть закон распределения вероятностей промежутка между поступлением соседних требований τ, то можно показать, что

.

Дифференцируя, получаем плотность распределения вероятностей: .

Случайная величина с такой плотностью вероятностей называется экспоненциально - распределенной (с показательным распределением). Математическое ожидание экспоненциально распределенной случайной величины равно

,

а дисперсия и среднеквадратическое отклонение соответственно будут равны:

,

.

Определим математическое ожидание и дисперсию числа требований за промежуток t:

,

.

Одним из важных свойств пуассоновского потока является аддитивность.

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

 

При разъединении пуассоновского потока на несколько потоков так, что каждое требование исходного потока с вероятностью p _i (S p _i = 1 ) поступает на i- тоенаправление, поток i направления будет также пуассоновским с интенсивностью l p _i.

 

Нестационарный пуассоновский поток.

Это ординарный поток без последействия, для которого в любой момент времени существует конечный параметр потока λ(t). Пусть P_i(t₀,τ) – вероятность поступления i -требований за интервал [ t₀,t₀+τ ], которая определяется формулой:

, где .

Этот параметр имеет смысл среднего числа требований на промежутке [t₀,t₀+τ]. Средняя интенсивность определяется как: .

Выбором закона изменения λ(t) можно описать реальные потоки заявок на АТС (например, отразить наличие ЧНН).

Примитивный поток.

Это ординарный поток, параметр которого прямо пропорциона­лен числу свободных источников N_i =(N-i). Здесь N – общее число источников требований, i - число обслуживаемых в данный момент источников. Для примитивного потока параметр потока определяется как λ_i=αN_i=α(N-i) с некоторым коэффициентом α. Среднее значе­ние параметра примитивного потока: , где f_­i - вероятность того, что об­служивается i источников. Средняя интенсивность потока заявок от одного источника: .

 

Поток с повторными вызовами.

Он состоит из потока первичных запросов – пуассоновский поток и повторных запросов. Параметр общего потока равен сумме параметров первичных и повторных заявок и может быть описан как примитивный с параметром:

Здесь обозначено: i - число обслуживаемых источников, j - число источников, повторяющих запрос, α – интенсивность первичного источника, β – интенсивность источника повторного запроса. Если α ≈ ß, то потоки неразличимы. Во многих городских АТС ß >> α и можно произвести сепарацию потоков заявок по среднему времени обслуживания.

Поток Эрланга

Частный случай и получается “просеиванием” потока Пальма. Если отбрасывать каждую вторую заявку – то получается поток Эрланга второго порядка, если каждую третью – третьего порядка и т.д.

Простейший пуассоновский поток можно рассматривать как поток Эрланга первого порядка. Обозначим p_n(t) плотность вероятности промежутка между заявками. Можно получить что: .

Закон распределения для потока Эрланга n-го порядка:

,

.

Нормируем масштаб времени так, чтобы параметр потока не зависел от n.

Τ_н (n)=τ(n)/n; интенсивность Λ_n

Нормированный поток Эрланга n – го порядка:

Обобщенный поток Эрланга n –го порядка.

Если τ(n) есть сумма случайных величин, каждая из которых распределена по показательному закону с параметром λ_i

,

,

, .

Поток освобождения серверов

 

Пусть x_k –длительность обслуживания k –ой заявки. При детерминированном характере обслуживания задается набор этих значений. При x = x_k время обслуживания постоянно и поток освобождения совпадает по характеристикам с потоком заявок. При случайном характере обслуживания задают вероятность того, что обслуживание займет время меньшее, чем x: .

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

Рис. 2. Гистограммы измерений длительности занятий при x = 60,3 с, s = 84,4 и разговоров при x = 81,2 с, s = 90,1

Если освободившийся сервер сразу же занимается новым обслуживанием, то отношение , где V – общее число серверов, а – среднее время обслуживания. Вероятность того, что за промежуток времени t произойдет i освобождений, будет равна:

.

В более общем случае, когда занято k серверов, вероятность освобождения i серверов за время t при показательном законе распределения времени обслуживания получим

.

Вероятность того, что не освободится ни один сервер: .

Параметр потока освобождений при занятии k серверов можно найти как предел

.

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

 

СРС 2 по дисциплине “Теория распределение информации»

A/b/c:d/e/f

a – распределение поступающего потока запросов.

b – закон распределения времени обслуживания.

Типовые условные обозначения:

М – экспоненциальное (Марковское) распределение,

D – детерминированное распределение,

E^k – эрланговское распределение k-го порядка,

HM^k – гиперэкспоненциальное,

HE^k – гиперэрланговское распределение порядка k,

GI – произвольное распределение независимых промежутков между заявками,

G – произвольное распределение длительностей обслуживания.

c – структура системы обслуживания (обычно число серверов).

d – дисциплина обслуживания (параметры после двоеточия иногда опускают).

Обычно используется сокращенное символическое обозначение, например FF вместо FIFO, LF, PR и т.п.

e – максимальное число запросов, воспринимаемое системой, может употребляться символ ¥.

f – максимальное число запросов к системе обслуживания.

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

Формула Литтла (Little).

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

 

С увеличением числа требований растет время ожидания. Установим соотношение между средним числом требований в системе, интенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени (0, t) требований как функцию времени α(t).

Число исходящих из системы заявок (обслуженных) на этом интервале обозначим δ(t). На рисунке 2 показаны примеры функциональных зависимостей этих двух случайных процессов от времени.

Рис. 2 Зависимость между средним числом требований в системе, интенсивностью потока и средним времени пребывания в системе.

 

Число требований, находящихся в системе в момент t будет равно:

.

Площадь между двумя рассматриваемыми кривыми от 0 до t - дает общее время, проведенное всеми заявками в системе за время t.

Обозначим эту накопленную величину γ(t). Если интенсивность входного потока равна λ, а средняя интенсивность за время t: ,то время, проведенное одной заявкой в системе, усредненное по всем заявкам будет равно:

.

Наконец, определим среднее число требований в системе в промежутке (0,t):

.

Из последних трех уравнений следует, что: , (где ).

Если в СМО существует стационарный режим, то при t → ∞, будут иметь место соотношения:

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

Интересно, что в качестве СМО можно рассмотреть только очередь из заявок в буфере. Тогда формула Литтла приобретает иной смысл - средняя длина очереди равна произведению интенсивности входного потока заявок на среднее время ожидания в очереди: .

Если наоборот рассматривать СМО только как серверы, то формула Литтла дает:

,

где – среднее число заявок в серверах, а – среднее время обработки в сервере.

В любом случае: .

Одним из основных параметров, которые используются при описании СМО, является коэффициент использования (utilization factor). Это фундаментальный параметр, так как он определяется как отношение интенсивности входного потока к пропускной способности системы. Поскольку пропускная способность СМО содержащей m серверов может быть определена как: , то коэффициент использования может быть определен как:

.

Нетрудно видеть, что коэффициент использования равен в точности интенсивности нагрузки, если СМО с одним сервером и в m раз меньше для систем с m серверами. Величина коэффициента использования равна среднему значению от доли занятых серверов и .

Если в СМО типа G/G/1 существует стационарный режим и можно определить вероятность того, что в некоторый случайный момент сервер будет свободный, то

.

 

 

СРС 3 по дисциплине “Теория распределение информации»

Наименование темы: Стационарные вероятности р_к для СМО типа М/М/1.

На рис. 1 приведен график вероятностей того, что в очереди находится k заявок в установившемся режиме.

Рис. 1 Стационарные вероятности р_к для СМО типа М/М/1.

Важной характеристикой системы является средняя длина очереди. Зная вероятности каждого из возможных значений длины, найдем математическое ожидание:

.

График средней длины очереди заявок в системе в зависимости от значения коэффициента использования или нагрузки показан на рис. 2.

Найдем теперь дисперсию длины очереди: .

 

Рисунок 2 Среднее число требований Рисунок 3 Среднее время пребывания

в системе типа М/М/1 требования в системе типа М/М/1 как функция ⍴

 

Для нахождения среднего значения времени пребывания в очереди воспользуемся формулой Литтла.

.

На рис. 3 приведен график зависимости среднего времени пребывания в очереди в зависимости от коэффициента использования (нагрузки).

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

Наконец найдем вероятность того, что в очереди будет находиться не менее чем k заявок и того, что в очереди менее k заявок.

 

Итак, в ходе анализа простейшей системы М/М/1 удалось в аналитическом виде найти все практически интересные характеристики Q_oS системы.

 

 

СРС 4 по дисциплине “Теория распределение информации»

Лекция №1

по дисциплине “Теория распределение информации»

Эрл

120

Час

Рис. 2. Результаты измерения интенсивности нагрузки на нескольких городских АТС.

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

Ненулевое значение потерянной или избыточной нагрузки говорит о ненулевой вероятности блокировки или пропуска требований или ненулевом значении задержки требований во входной очереди. Значения вероятности блокировки или пропуска, а также параметры функции распределения задержки, чаще всего среднее значение задержки, определяют показатели качества обслуживания (QoS-Quality of Service).

Важными характеристиками СМО являются ее производительность и пропускная способность.

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

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

3. Модели потока требований

Поступающие на вход СМО требования (заявки, запросы) образуют поток дискретных событий, полностью определяемый множеством моментов времени их поступления . Для детерминированного потока значения t_n задаются таблицей или формулой. На практике этот поток случайный и значения моментов поступления запросов есть значения случайной величины, задаваемой функциями распределения вероятности t_n либо интервала между поступлениями D t: .

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

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

Последействие - вероятность поступления требований в интервале (t₁ , t₂) зависит от событий, произошедших до момента t₁.

Ординарность - вероятность поступления двух и более требований за бесконечно малый интервал времени Δt есть величина бесконечно малая более высокого порядка, чем Δt.

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

Ведущей функцией потока называют математическое ожидание числа требований в промежутке времени (0,t).

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

.

Для стационарного потока параметр потока постоянный и равен:

.

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

 

 

Лекция №2

по дисциплине “Теория распределение информации»

Теорема 1.

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

Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме.

Теорема 2.

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

А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состояния не существует;

Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей:

Состояние называется эргодическим, если оно апериодично и возвратно ненулевое. Если все состояния цепи Маркова эргодичны, то вся цепь называется эргодической. Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует.

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

Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования.

Рис. 1. Цепь Маркова.

 

У однородных Марковских процессов вероятности переходов не зависят от времени.

Вероятности перехода системы из состояния i на m -том шаге в состояние j на n -том шаге для n > m.

Эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова. (Chapman - Kolmogorov)

.

Для однородных цепей Маркова эти уравнения упрощаются так

.

 

Лекция № 3

по дисциплине “Теория распределение информации»

Непрерывные цепи Маркова.

2.Анализ систем массового обслуживания с марковскими потоками требований. Система М/M/1. Анализ

Непрерывные цепи Маркова.

 

Случайный процесс X(t) с дискретным множеством значений образует непрерывную цепь Маркова, если

.

Будущие состояния зависят от прошлого только через текущее состояние. Для непрерывный цепей Маркова основным также является уравнение Чепмена –Колмогорова, для однородной цепи имеющее вид: .

Здесь матрица H (t) = [ p_ij(t) ] - матрица вероятностей перехода из состояния i в состояние j в момент времени t, а матрица Q называется матрицей интенсивностей переходов. Ее элементы имеют следующий смысл: если в момент времени t система находилась в состоянии E_i, то вероятность перехода в течение промежутка времени (t,t+Δt) в произвольное состояние E_j задается величиной q_ij(t)Δt + o(Δt), а вероятность ухода из состояния E_i величиной -q_iiΔt + o(Δt).

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

Наиболее важным для дальнейшего использования является класс непрерывных цепей Маркова называемых «процессами гибели - размножения»( Birth – death process ). Для таких систем из состояния k возможны переходы только в состояния k, k -1 и k +1 в следующие моменты времени:

· в момент t объем популяции был равен k и в течение времени (t,t+Δt) не произошло изменения состояния

· в момент t объем популяции был равен k -1 и в течение времени (t,t+Δt) родился один член популяции

· в момент времени t объем популяции был равен k +1 и в течение времени (t,t + Δt) погиб один член популяции

Рис. 2 Возможные переходы в состояние Ек.

 

Диаграмма переходов для дискретных цепей Маркова (Рис 3)

Рис.3 Диаграмма интенсивностей переходов для процесса размножения и гибели.

 

Овалам здесь соответствуют дискретные состояния, а стрелки определяют интенсивности потоков вероятности (а не вероятности!) переходов от одного состояния к другому.

Имеет место своеобразный «закон сохранения»:

Разность между суммой интенсивностей, с которой система попадает в состояние k и суммой интенсивностей, с которой система покидает это состояние должна равняться интенсивности изменения потока в это состояние (производной по времени).

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

Система М/M/1. Анализ.

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

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

Рис. 1. СМО типа М/М/1.

Поскольку входной процесс ординарный, то в каждый момент времени к очереди может добавиться только одна заявка, поскольку сервер один, то в каждый момент времени может быть обслужена, то есть уйти из очереди только одна заявка. Таким образом, рассматриваемая СМО относится к процессу класса «гибели-размножения». Для анализа необходимо конкретизировать параметры системы. Распределение вероятностей входного потока и времени обслуживания позволяет полагать интенсивности вероятностей в модели постоянными.

Здесь t – среднее время обслуживания в сервере.

На рис 2 приведена диаграмма интенсивностей переходов для рассматриваемой системы.

Рис. 2 Диаграмма интенсивности переходов для СМО типа М/М/1.

 

Полученное ранее общее решение позволяет сразу записать вероятность того, что в стационарном состоянии в очереди будет находиться k заявок

Найдем начальное значение вероятности, учитывая сходимость соответствующего ряда

.

Окончательно получаем формулу для вероятности длины очереди

.

 

 

Лекция №4

по дисциплине “Теория распределение информации»

Наименование темы: Анализ систем массового обслуживания с марковскими потоками требований

Лекция №5

по дисциплине “Теория распределение информации»

Наименование темы: Анализ систем массового обслуживания с марковскими потоками требований

Система типа M/M/m:m

Система типа M/M/m:m

Систему, имеющую одинаковое число входных линий и обслуживающих серверов, например выходных линий. Очевидно, что блокировка в такой системе невозможна. Диаграмма интенсивностей переходов состояний может быть представлена в виде совокупности несвязных m простейших подсистем с двумя состояниями – свободно/занято. (Рис. 1.20)

Рис. 1.20 Диаграмма интенсивностей переходов состояний для СМО типа M/M/m:m.

Вероятности того, что k подсистем находятся в состоянии «занято», описывается формулой Энгсета:

.

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

Полученное распределение вероятностей носит название биноминального или распределения Бернулли. Величина a определяет вероятность занятости сервера, а величина (1-a) – вероятность его простоя. Поскольку таких серверов m, то распределение вероятностей будет таким же, как для классической задачи о бросании m монет. Следует отметить также что

 

Лекция №6

по дисциплине “Теория распределение информации»

Модель Эрланга.

Вероятность попадания вызова на заблокированную систему не зависит от состояния системы и в результате вероятность потери вызова совпадает с вероятностью блокировки по времени:

.

Модель Энгсета.

Здесь для примитивного потока можно записать вероятности через интенсивности

Последняя строка задает среднюю интенсивность вызовов по всем состояниям. Теперь вероятность потерь вызова может быть записана через интенсивности и далее вычислена через функцию Энгсета:

 

Как видно, .

Если рассмотреть предел при стремлении числа входов к бесконечности, так что суммарная интенсивность потока останется постоянной, т.е. , , то модель Энгсета превратится в модель Эрланга.

· Интенсивность обслуженной нагрузки

Лекция №7

по дисциплине “Теория распределение информации»

Наименование темы: 1.Классификация потоков. 2.Поток освобождения серверов

Классификация потоков.

Пуассоновский (простейший) поток запросов

Стационарный ординарный поток без последействия называют простейшим. Он задается набором вероятностей P_i(t) поступления i требований в промежутке длиной t.

 

Можно показать, что при этих предположениях формула для P _i(t) дается формулой Пуассона (Poisson):

.

Проанализируем основные характеристики пуассоновского потока. Рассмотрим отношение P_i(t)/P_i-1(t). При i ≤ λt вероятность растет, а при обратном соотношении – убывает. Графики функции распределения Пуассона в зависимости от величины λt для различных значений k приведены на рис. 1.

Рис. 1. Графики Пуассоновского распределения в зависимости от lt для различных k.

Наряду с распределением P_i(t) используют вероятности поступления не менее i требований в интервал t или не более i требований за время t:

Если рассмотреть закон распределения вероятностей промежутка между поступлением соседних требований τ, то можно показать, что

.

Дифференцируя, получаем плотность распределения вероятностей: .

Случайная величина с такой плотностью вероятностей называется экспоненциально - распределенной (с показательным распределением). Математическое ожидание экспоненциально распределенной случайной величины равно

,

а дисперсия и среднеквадратическое отклонение соответственно будут равны:

,

.

Определим математическое ожидание и дисперсию числа требований за промежуток t:

,

.

Одним из важных свойств пуассоновского потока является аддитивность.

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

 

При разъединении пуассоновского потока на несколько потоков так, что каждое требование исходного потока с вероятностью p _i (S p _i = 1 ) поступает на i- тоенаправление, поток i направления будет также пуассоновским с интенсивностью l p _i.